A patch for the loop alias bug

[hjl at lucon dot org (H.J. Lu)]

Hi,

This is the patch for the loop alias bug. It fixes

http://www.cygnus.com/ml/egcs-bugs/1998-Jul/0307.html

as well as

http://www.cygnus.com/ml/egcs-bugs/1998-Jul/0050.html

The problem is the interaction between true_dependence and rtx_varies_p
called from invariant_p. invariant_p is called for a loop. But
rtx_varies_p doesn't realy work very well on a loop. true_dependence
will miss dependency within a loop when rtx_varies_p is used.

This patch intrudoce a new function, loop_rtx_varies_p, which works on
a loop. Before we scan a loop, we first set up loop_set_regs, which is
used by loop_rtx_varies_p to check if a pseudo register varies within
a loop.

That patch may not be perfect. I hope someone can come up with a better
one.

BTW, the same problem exists in the scheduler. If someone can tell me
I am on the right track, I will try to fix the scheduler in a similar
fashion.

Thanks.


-- 
H.J. Lu (hjl@gnu.org)
---
Sun Jul 12 09:57:56 1998  H.J. Lu  (hjl@gnu.org)

	* loop.c (loop_max_regno): New static variable for the maximum
	register number plus 1 in a loop.
	(loop_set_regs): New static variable. Array of sources of SETs
	with register as destination in a loop.
	(scan_loop): Setup loop_max_regno and loop_set_regs before
	prescan_loop. Cleanup after.
	(loop_rtx_varies_p): New static function.
	(note_set_reg): New static function.
	(note_addr_stored): Call note_set_reg for none memory reference.
	(invariant_p): Use loop_rtx_varies_p instead of rtx_varies_p
	when call true_dependence ().

--- ../../../src/egcs/gcc/loop.c	Sat Jul 11 19:08:42 1998
+++ ./loop.c	Sun Jul 12 10:54:47 1998
@@ -192,6 +192,12 @@ static char *moved_once;
 #define NUM_STORES 30
 static rtx loop_store_mems[NUM_STORES];
 
+/* The maximum register number plus 1 in a loop.  */
+static int loop_max_regno;
+
+/* Array of sources of SETs with register as destination in a loop.  */
+static rtx *loop_set_regs;
+
 /* Index of first available slot in above array.  */
 static int loop_store_mems_idx;
 
@@ -285,6 +291,8 @@ static rtx libcall_other_reg PROTO((rtx,
 static int labels_in_range_p PROTO((rtx, int));
 static void count_loop_regs_set PROTO((rtx, rtx, char *, rtx *, int *, int));
 static void note_addr_stored PROTO((rtx, rtx));
+static void note_set_reg PROTO((rtx, rtx));
+static int loop_rtx_varies_p PROTO((rtx));
 static int loop_reg_used_before_p PROTO((rtx, rtx, rtx, rtx, rtx));
 static void scan_loop PROTO((rtx, rtx, int, int));
 #if 0
@@ -629,6 +637,9 @@ scan_loop (loop_start, end, nregs, unrol
   scan_start = p;
 
   /* Set up variables describing this loop.  */
+  loop_max_regno = max_reg_num ();
+  loop_set_regs = (rtx *) alloca ((loop_max_regno) * sizeof (rtx));
+  memset (loop_set_regs, 0, (loop_max_regno) * sizeof (rtx));
   prescan_loop (loop_start, end);
   threshold = (loop_has_call ? 1 : 2) * (1 + n_non_fixed_regs);
 
@@ -1086,6 +1097,8 @@ scan_loop (loop_start, end, nregs, unrol
   if (flag_strength_reduce)
     strength_reduce (scan_start, end, loop_top,
 		     insn_count, loop_start, end, unroll_p);
+
+  loop_max_regno = 0;
 }
 
 /* Add elements to *OUTPUT to record all the pseudo-regs
@@ -2833,17 +2846,119 @@ labels_in_range_p (insn, end)
   return 0;
 }
 
-/* Record that a memory reference X is being set.  */
+/* Return 1 if X has a value that can vary in the current loop.
+   It is very similar to rtx_varies_p (), but it only checks the
+   current loop. */
+
+static int
+loop_rtx_varies_p (x)
+     rtx x;
+{
+  register RTX_CODE code = GET_CODE (x);
+  register int i;
+  register char *fmt;
+
+  switch (code)
+    {
+    case MEM:
+    case QUEUED:
+      return 1;
+
+    case CONST:
+    case CONST_INT:
+    case CONST_DOUBLE:
+    case SYMBOL_REF:
+    case LABEL_REF:
+      return 0;
+
+    case REG:
+      /* Note that we have to test for the actual rtx used for the frame
+	 and arg pointers and not just the register number in case we have
+	 eliminated the frame and/or arg pointer and are using it
+	 for pseudos.  */
+      if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx
+		|| x == arg_pointer_rtx || x == pic_offset_table_rtx)
+	return 0;
+      else
+	{
+	  int regno = REGNO (x);
+
+	  if (regno < FIRST_PSEUDO_REGISTER || regno >= loop_max_regno)
+	    return 1;
+
+	  x = loop_set_regs [regno];
+	  if (x)
+	    {
+	      /* Return 1 if it is set at least twice in a loop. */
+	      if (x == (rtx) -1)
+		return 1;
+	      else
+		return loop_rtx_varies_p (x);
+	    }
+	  else
+	    return 0;
+	}
+      break;
+
+    case LO_SUM:
+      /* The operand 0 of a LO_SUM is considered constant
+	 (in fact is it related specifically to operand 1).  */
+      return loop_rtx_varies_p (XEXP (x, 1));
+      
+    default:
+      break;
+    }
+
+  fmt = GET_RTX_FORMAT (code);
+  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
+    if (fmt[i] == 'e')
+      if (loop_rtx_varies_p (XEXP (x, i)))
+	return 1;
+  return 0;
+}
+
+/* Record a pseudo register X is being set.  */
+
+static void
+note_set_reg (x, pat)
+     rtx x;
+     rtx pat;
+{
+  /* Store the source of PAT in loop_set_regs if the destination
+     is X and X is a pseudo register. */
+  if (GET_CODE (x) == REG && REGNO (x) >= FIRST_PSEUDO_REGISTER
+      && REGNO (x) < loop_max_regno)
+    {
+      if (GET_CODE (pat) != SET)
+	pat = single_set (pat);
+
+      if (pat && rtx_equal_p (SET_DEST (pat), x))
+	{
+	  if (loop_set_regs [REGNO (x)]
+	      || reg_mentioned_p (x, SET_SRC (pat)))
+	    loop_set_regs [REGNO (x)] = (rtx) -1;
+	  else
+	    loop_set_regs [REGNO (x)] = SET_SRC (pat);
+	}
+    }
+}
+
+/* Record that a memory reference/pseudo register X is being set.  */
 
 static void
 note_addr_stored (x, y)
      rtx x;
-     rtx y ATTRIBUTE_UNUSED;
+     rtx y;
 {
   register int i;
 
-  if (x == 0 || GET_CODE (x) != MEM)
+  if (x == 0)
     return;
+  else if (GET_CODE (x) != MEM)
+    {
+      note_set_reg (x, y);
+      return;
+    }
 
   /* Count number of memory writes.
      This affects heuristics in strength_reduce.  */
@@ -2960,7 +3075,8 @@ invariant_p (x)
 
       /* See if there is any dependence between a store and this load.  */
       for (i = loop_store_mems_idx - 1; i >= 0; i--)
-	if (true_dependence (loop_store_mems[i], VOIDmode, x, rtx_varies_p))
+	if (true_dependence (loop_store_mems[i], VOIDmode, x,
+			     loop_rtx_varies_p))
 	  return 0;
 
       /* It's not invalidated by a store in memory