EGCS Optimization bug on HPUX

[Jeffrey A Law]

  In message <199904212134.RAA16049@hiauly1.hia.nrc.ca>you write:
  > I created this test program:
  > 
  > #define NUL 0
  > void loop (char * pz, char * pzDta)
  > {
  >     for (;;) {
  >         switch (*(pz++) = *(pzDta++)) {
  >         case NUL:
  >   	    goto loopDone2;
  > 
  > 	case '"':
  > 	case '\\':
  > 	    pz[-1]  = '\\';
  >             *(pz++) = pzDta[-1];
  > 	}
  >     } loopDone2:;
  > }
  > 
Thanks.  This turned out to be a bug in the loop optimizer.  In a nutshell
the loop optimizer incorrectly determined that both increments of pz would
be executed each iteration of the loop.  This caused loop to create incorrect
code.


The loop had a basic structure like:

(note 11 10 12 "" NOTE_INSN_LOOP_BEG)

(code_label 12 11 14 3 "" [num uses: 3])

[ ... ]

(insn 41 40 43 (set (reg/v:SI 94)
        (plus:SI (reg/v:SI 94)
            (const_int 1 [0x1]))) 161 {addsi3} (nil)
    (nil))

[ ... ]

(jump_insn 45 43 49 (set (pc)
        (if_then_else (eq (reg:SI 102)
                (reg:SI 103))
            (label_ref 22)
            (pc))) 47 {bleu+1} (nil)
    (nil))

[ ... ]

(jump_insn 52 51 53 (set (pc)
        (label_ref 12)) -1 (nil)
    (nil))

[ ... ]

(code_label 22 16 25 10 "" [num uses: 1])

[ ... ]

(insn 31 30 64 (set (reg/v:SI 94)
        (plus:SI (reg/v:SI 94)
            (const_int 1 [0x1]))) 161 {addsi3} (nil)
    (nil))

(note 64 31 66 "" NOTE_INSN_LOOP_CONT)

(jump_insn 66 64 67 (set (pc)
        (label_ref 12)) -1 (nil)
    (nil))


That's the important flow control.  Of particular interest is that it is
possible to jump to the top of the loop via insn 52 without ever executing
insn 31.  Also note that code_label 22 is the last label in the loop.

This loop structure confused this optimization in strength_reduce:

      /* Unlike in the code motion pass where MAYBE_NEVER indicates that
         an insn may never be executed, NOT_EVERY_ITERATION indicates whether
         or not an insn is known to be executed each iteration of the
         loop, whether or not any iterations are known to occur.

         Therefore, if we have just passed a label and have no more labels
         between here and the test insn of the loop, we know these insns
         will be executed each iteration.  */

      if (not_every_iteration && GET_CODE (p) == CODE_LABEL
          && no_labels_between_p (p, loop_end)
          && loop_insn_first_p (p, loop_cont))
        not_every_iteration = 0;


ie, we could incorrectly clear not_every_iteration when we passed code_label 22
which in turn caused the loop optimizer to incorrectly believe that insn 31
would be executed every iteration of the loop.

	* loop.c (strength_reduce): Do not clear NOT_EVERY_ITERATION at the
	last CODE_LABEL in a loop if we have previously passed a jump
	to the top of the loop.
	
Index: loop.c
===================================================================
RCS file: /egcs/carton/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.156.4.1
diff -c -3 -p -r1.156.4.1 loop.c
*** loop.c	1999/05/23 19:42:50	1.156.4.1
--- loop.c	1999/05/24 20:30:57
*************** strength_reduce (scan_start, end, loop_t
*** 3669,3674 ****
--- 3669,3677 ----
    /* This is 1 if current insn may be executed more than once for every
       loop iteration.  */
    int maybe_multiple = 0;
+   /* This is 1 if we have past a branch back to the top of the loop
+      (aka a loop latch).  */
+   int past_loop_latch = 0;
    /* Temporary list pointers for traversing loop_iv_list.  */
    struct iv_class *bl, **backbl;
    /* Ratio of extra register life span we can justify
*************** strength_reduce (scan_start, end, loop_t
*** 3836,3851 ****
  	    loop_depth--;
  	}
  
        /* Unlike in the code motion pass where MAYBE_NEVER indicates that
  	 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
  	 or not an insn is known to be executed each iteration of the
  	 loop, whether or not any iterations are known to occur.
  
  	 Therefore, if we have just passed a label and have no more labels
! 	 between here and the test insn of the loop, we know these insns
! 	 will be executed each iteration.  */
! 
!       if (not_every_iteration && GET_CODE (p) == CODE_LABEL
  	  && no_labels_between_p (p, loop_end)
  	  && loop_insn_first_p (p, loop_cont))
  	not_every_iteration = 0;
--- 3839,3868 ----
  	    loop_depth--;
  	}
  
+       /* Note if we pass a loop latch.  If we do, then we can not clear
+ 	 NOT_EVERY_ITERATION below when we pass the last CODE_LABEL in
+ 	 a loop since a jump before the last CODE_LABEL may have started
+ 	 a new loop iteration.
+ 
+ 	 Note that LOOP_TOP is only set for rotated loops and we need
+ 	 this check for all loops, so compare against the CODE_LABEL
+ 	 which immediately follows LOOP_START.  */
+       if (GET_CODE (p) == JUMP_INSN && JUMP_LABEL (p) == NEXT_INSN (loop_start))
+ 	past_loop_latch = 1;
+ 
        /* Unlike in the code motion pass where MAYBE_NEVER indicates that
  	 an insn may never be executed, NOT_EVERY_ITERATION indicates whether
  	 or not an insn is known to be executed each iteration of the
  	 loop, whether or not any iterations are known to occur.
  
  	 Therefore, if we have just passed a label and have no more labels
! 	 between here and the test insn of the loop, and we have not passed
! 	 a jump to the top of the loop, then we know these insns will be
! 	 executed each iteration.  */
! 
!       if (not_every_iteration 
! 	  && ! past_loop_latch
! 	  && GET_CODE (p) == CODE_LABEL
  	  && no_labels_between_p (p, loop_end)
  	  && loop_insn_first_p (p, loop_cont))
  	not_every_iteration = 0;