Re: loop.c patch: do some copy propagation

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

> You should probably use BITMAP_XMALLOC + BITMAP_XFREE.  We're trying to
> get away from alloca'd bitmaps.

I'm now using "regset_head"s instead of allocating things dynamically.  (This
means the patch depends on the one I sent earlier today).

> Instead of referencing basic-block.h in the Makefile.in dependency list for
> loop you should use BASIC_BLOCK_H.

Ok.

> I was also unable to convince myself your code is correct when a register
> in COPIES is live after the loop.  What ensures that such a register has the
> correct value after the loop if we delete the insns which set it from within
> the loop?

Nothing, apparently.  I've added a test to try_copy_prop:
      if (uid_luid[REGNO_LAST_UID (regno)] < INSN_LUID (end))
which is copied from another place in loop.c.

Below is a new version (only the loop.c part).

Thanks for reviewing.

Bernd

Index: loop.c
===================================================================
RCS file: /cvs/gcc/egcs/gcc/loop.c,v
retrieving revision 1.198
diff -c -p -r1.198 loop.c
*** loop.c	1999/11/22 16:40:32	1.198
--- loop.c	1999/11/22 17:57:11
*************** Boston, MA 02111-1307, USA.  */
*** 41,46 ****
--- 41,47 ----
  #include "obstack.h"
  #include "function.h"
  #include "expr.h"
+ #include "basic-block.h"
  #include "insn-config.h"
  #include "insn-flags.h"
  #include "regs.h"
*************** static void load_mems_and_recount_loop_r
*** 337,342 ****
--- 338,345 ----
  static void load_mems PROTO((rtx, rtx, rtx, rtx));
  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 try_copy_prop PROTO((rtx, rtx, rtx, rtx, int));
  static int replace_label PROTO((rtx *, void *));
  
  typedef struct rtx_and_int {
*************** load_mems (scan_start, end, loop_top, st
*** 9717,9722 ****
--- 9720,9726 ----
    rtx end_label = NULL_RTX;
    /* Nonzero if the next instruction may never be executed.  */
    int next_maybe_never = 0;
+   int last_max_reg = max_reg_num ();
  
    if (loop_mems_idx == 0)
      return;
*************** load_mems (scan_start, end, loop_top, st
*** 9756,9761 ****
--- 9760,9766 ----
    /* Actually move the MEMs.  */
    for (i = 0; i < loop_mems_idx; ++i) 
      {
+       regset_head copies;
        int written = 0;
        rtx reg;
        rtx mem = loop_mems[i].mem;
*************** load_mems (scan_start, end, loop_top, st
*** 9817,9822 ****
--- 9822,9829 ----
  	   loop, but later discovered that we could not.  */
  	continue;
  
+       INIT_REG_SET (&copies);
+ 
        /* Allocate a pseudo for this MEM.  We set REG_USERVAR_P in
  	 order to keep scan_loop from moving stores to this MEM
  	 out of the loop just because this REG is neither a
*************** load_mems (scan_start, end, loop_top, st
*** 9827,9840 ****
  
        /* Now, replace all references to the MEM with the
  	 corresponding pesudos.  */
        for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
  	   p != NULL_RTX;
  	   p = next_insn_in_loop (p, scan_start, end, loop_top))
  	{
  	  rtx_and_int ri;
! 	  ri.r = p;
! 	  ri.i = i;
! 	  for_each_rtx (&p, replace_loop_mem, &ri);
  	}
  
        if (! apply_change_group ())
--- 9834,9870 ----
  
        /* Now, replace all references to the MEM with the
  	 corresponding pesudos.  */
+       maybe_never = 0;
        for (p = next_insn_in_loop (scan_start, scan_start, end, loop_top);
  	   p != NULL_RTX;
  	   p = next_insn_in_loop (p, scan_start, end, loop_top))
  	{
  	  rtx_and_int ri;
! 	  rtx set;
! 
! 	  if (GET_RTX_CLASS (GET_CODE (p)) == 'i')
! 	    {
! 	      /* See if this copies the mem into a register that isn't
! 		 modified afterwards.  We'll try to do copy propagation
! 		 a little further on.  */
! 	      set = single_set (p);
! 	      if (set
! 		  /* @@@ This test is _way_ too conservative.  */
! 		  && ! maybe_never
! 		  && GET_CODE (SET_DEST (set)) == REG
! 		  && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER
! 		  && REGNO (SET_DEST (set)) < last_max_reg
! 		  && VARRAY_INT (n_times_set, REGNO (SET_DEST (set))) == 1
! 		  && rtx_equal_p (SET_SRC (set), loop_mems[i].mem))
! 		SET_REGNO_REG_SET (&copies, REGNO (SET_DEST (set)));
! 	      ri.r = p;
! 	      ri.i = i;
! 	      for_each_rtx (&p, replace_loop_mem, &ri);
! 	    }
! 
! 	  if (GET_CODE (p) == CODE_LABEL
! 	      || GET_CODE (p) == JUMP_INSN)
! 	    maybe_never = 1;
  	}
  
        if (! apply_change_group ())
*************** load_mems (scan_start, end, loop_top, st
*** 9842,9847 ****
--- 9872,9878 ----
  	loop_mems[i].optimize = 0;
        else
  	{
+ 	  int j;
  	  rtx set;
  
  	  /* Load the memory immediately before START, which is
*************** load_mems (scan_start, end, loop_top, st
*** 9874,9879 ****
--- 9905,9920 ----
  	      print_rtl (loop_dump_stream, mem);
  	      fputc ('\n', loop_dump_stream);
  	    }
+ 
+ 	  /* Attempt a bit of copy propagation.  This helps untangle the
+ 	     data flow, and enables {basic,general}_induction_var to find
+ 	     more bivs/givs.  */
+ 	  EXECUTE_IF_SET_IN_REG_SET
+ 	    (&copies, FIRST_PSEUDO_REGISTER, j,
+ 	     {
+ 	       try_copy_prop (scan_start, loop_top, end, loop_mems[i].reg, j);
+ 	     });
+ 	  CLEAR_REG_SET (&copies);
  	}
      }
  
*************** load_mems (scan_start, end, loop_top, st
*** 9901,9906 ****
--- 9942,9992 ----
      }
  }
  
+ /* 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
+    is not used after the loop.
+    The arguments SCAN_START, LOOP_TOP and END are as in load_mems.  */
+ static void
+ try_copy_prop (scan_start, loop_top, end, replacement, regno)
+      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] = { regno_reg_rtx[regno], replacement, insn };
+       if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
+ 	continue;
+       set = single_set (insn);
+       if (set
+ 	  && GET_CODE (SET_DEST (set)) == REG
+ 	  && REGNO (SET_DEST (set)) == regno)
+ 	{
+ 	  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);
+     }
+ }
+ 
  /* Replace MEM with its associated pseudo register.  This function is
     called from load_mems via for_each_rtx.  DATA is actually an
     rtx_and_int * describing the instruction currently being scanned
*************** replace_loop_mem (mem, data)
*** 9945,9950 ****
--- 10031,10058 ----
  
    /* Actually replace the MEM.  */
    validate_change (insn, mem, loop_mems[i].reg, 1);
+ 
+   return 0;
+ }
+ 
+ /* Replace one register with another.  Called through for_each_rtx; PX points
+    to the rtx being scanned.  DATA is actually an array of three rtx's; the
+    first one is the one to be replaced, and the second one the replacement.
+    The third one is the current insn.  */
+ 
+ static int
+ replace_loop_reg (px, data)
+      rtx *px;
+      void *data;
+ {
+   rtx x = *px;
+   rtx *array = (rtx *)data;
+ 
+   if (x == NULL_RTX)
+     return 0;
+ 
+   if (x == array[0])
+     validate_change (array[2], px, array[1], 1);
  
    return 0;
  }