Re: miscompiled loop condition

[Bernd Schmidt <bernds at pathia dot cygnus dot co dot uk>]

On Thu, 25 Nov 1999, Stephen L Moshier wrote:
> 
> In this test case the expression in the while condition gets
> miscompiled with -O2 on i386 and sparc.  The result is that the
> program loops endlessly when it is run.

This is due an error in my recent loop changes.  We're trying to do copy
propagation when we see something like:
 (set (reg 1) (reg 2))

The problem is that the code still does substitutions if there's a store
to reg 2 between this insn and another one that uses reg 1.

The patch below ought to fix this by making try_copy_prop more conservative.
It is now restricted to extended basic blocks.  The way the loop optimizer
is written (no good information about control flow available) makes it hard
to do better.  However, it should still catch most of the interesting cases,
which are temporaries created to load a memory location into a register.
These temporaries typically shouldn't live across multiple basic blocks.

I'd like to install this variant of the testcase in the testsuite.  OK?

int x, y;

int
main()
{
  x = 2;
  y = x;
  do
    {
      x = y;
      y = 2 * y;
    }
  while ( ! ((y - x) >= 20));
}

(Patch bootstrapped on i586-linux, now running make check)

Bernd
         
	* loop.c (note_reg_stored): New function.
	(set_seen): New static var.
	(try_copy_prop): Replace only within one extended basic block, and
	stop replacing when an assignment to REPLACEMENT is seen.

Index: loop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.c,v
retrieving revision 1.201
diff -c -p -r1.201 loop.c
*** loop.c	1999/11/26 11:44:37	1.201
--- loop.c	1999/11/29 13:57:24
*************** static void load_mems PROTO((rtx, rtx, r
*** 339,344 ****
--- 339,345 ----
  static int insert_loop_mem PROTO((rtx *, void *));
  static int replace_loop_mem PROTO((rtx *, void *));
  static int replace_loop_reg PROTO((rtx *, void *));
+ static void note_reg_stored PROTO((rtx, rtx, void *));
  static void try_copy_prop PROTO((rtx, rtx, rtx, rtx, int));
  static int replace_label PROTO((rtx *, void *));
  
*************** load_mems (scan_start, end, loop_top, st
*** 9944,9949 ****
--- 9945,9965 ----
      }
  }
  
+ /* For communication between note_reg_stored and its caller.  */
+ static int set_seen;
+ 
+ /* Called via note_stores, record in SET_SEEN whether X, which is written,
+    is equal to ARG.  */
+ static void
+ note_reg_stored (x, setter, arg)
+      rtx x, setter;
+      void *arg;
+ {
+   rtx reg = (rtx) arg;
+   if (arg == x)
+     set_seen = 1;
+ }
+ 
  /* Try to replace every occurrence of pseudo REGNO with REPLACEMENT.
     There must be exactly one insn that sets this pseudo; it will be
     deleted if all replacements succeed and we can prove that the register
*************** try_copy_prop (scan_start, loop_top, end
*** 9954,9974 ****
       rtx scan_start, loop_top, end, replacement;
       int regno;
  {
    rtx init_insn = 0;
    rtx insn;
    for (insn = next_insn_in_loop (scan_start, scan_start, end, loop_top);
         insn != NULL_RTX;
         insn = next_insn_in_loop (insn, scan_start, end, loop_top))
      {
        rtx set;
-       rtx array[3];
  
!       array[0] = regno_reg_rtx[regno];
!       array[1] = replacement;
!       array[2] = insn;
  
        if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
  	continue;
        set = single_set (insn);
        if (set
  	  && GET_CODE (SET_DEST (set)) == REG
--- 9970,9998 ----
       rtx scan_start, loop_top, end, replacement;
       int regno;
  {
+   /* This is the reg that we are copying from.  */
+   rtx reg_rtx = regno_reg_rtx[regno];
    rtx init_insn = 0;
    rtx insn;
+   /* These help keep track of whether we replaced all uses of the reg.  */
+   int replaced_last = 0;
+   int store_is_first = 0;
+ 
    for (insn = next_insn_in_loop (scan_start, scan_start, end, loop_top);
         insn != NULL_RTX;
         insn = next_insn_in_loop (insn, scan_start, end, loop_top))
      {
        rtx set;
  
!       /* Only substitute within one extended basic block from the initializing
!          insn.  */
!       if (GET_CODE (insn) == CODE_LABEL && init_insn)
! 	break;
  
        if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
  	continue;
+ 
+       /* Is this the initializing insn?  */
        set = single_set (insn);
        if (set
  	  && GET_CODE (SET_DEST (set)) == REG
*************** try_copy_prop (scan_start, loop_top, end
*** 9976,9996 ****
  	{
  	  if (init_insn)
  	    abort ();
  	  init_insn = insn;
  	}
-       for_each_rtx (&insn, replace_loop_reg, array);
      }
    if (! init_insn)
      abort ();
    if (apply_change_group ())
      {
!       if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (end))
  	{
  	  PUT_CODE (init_insn, NOTE);
  	  NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
  	}
        if (loop_dump_stream)
! 	fprintf (loop_dump_stream, "  Replaced reg %d.\n", regno);
      }
  }
  
--- 10000,10046 ----
  	{
  	  if (init_insn)
  	    abort ();
+ 
  	  init_insn = insn;
+ 	  if (REGNO_FIRST_UID (regno) == INSN_UID (insn))
+ 	    store_is_first = 1;
+ 	}
+ 
+       /* Only substitute after seeing the initializing insn.  */
+       if (init_insn && insn != init_insn)
+ 	{	
+ 	  rtx array[3];
+ 	  array[0] = reg_rtx;
+ 	  array[1] = replacement;
+ 	  array[2] = insn;
+ 
+ 	  for_each_rtx (&insn, replace_loop_reg, array);
+ 	  if (REGNO_LAST_UID (regno) == INSN_UID (insn))
+ 	    replaced_last = 1;
+ 
+ 	  /* Stop replacing when REPLACEMENT is modified.  */
+ 	  set_seen = 0;
+ 	  note_stores (PATTERN (insn), note_reg_stored, replacement);
+ 	  if (set_seen)
+ 	    break;
  	}
      }
    if (! init_insn)
      abort ();
    if (apply_change_group ())
      {
!       if (loop_dump_stream)
! 	fprintf (loop_dump_stream, "  Replaced reg %d", regno);
!       if (store_is_first && replaced_last)
  	{
  	  PUT_CODE (init_insn, NOTE);
  	  NOTE_LINE_NUMBER (init_insn) = NOTE_INSN_DELETED;
+ 	  if (loop_dump_stream)
+ 	    fprintf (loop_dump_stream, ", deleting init_insn (%d)",
+ 		     INSN_UID (init_insn));
  	}
        if (loop_dump_stream)
! 	fprintf (loop_dump_stream, ".\n");
      }
  }