giv combination patch

[Richard Henderson <rth at cygnus dot com>]

>     1. Combining related General Induction Variables.

The following code is a first step along this path.  It works correctly
for givs related by a constant as below, or a simple constant as with
higher order ranks of staticly dimensioned arrays.

It fails for givs with higher order relations, as with second-order
ranks of dynamicly dimensioned arrays.  This can be fixed in two ways.

First, I'd canonized the giv expressions to make comparing them easier
and faster.  But this yields expressions that are not necessarily 
canonized for base+index matching on machines that support that.  We
either need some heuristic for reconstructing valid index patterns or
drop the canonization and enhance the search.  

Second, we add a second-order combine pass that combines givs based
on other givs, not just on bivs as we do now.  

Finally, I should warn that -frerun-loop-opt now actually seems to
hurt optimization slightly.  In the cases that I've tried, the first
pass gets more or less optimal recognition (within the constraints
listed above) and the second pass degrades that.  I've not looked
into the cause of this.


r~
Fri Dec 12 08:34:49 1997  Richard Henderson  <rth@cygnus.com>

	* loop.c (canonize_giv_add_val): New function.
	(record_giv): Canonize add_val before storing.
	(basic_induction_var) [REG]: Don't just search the previous insn,
	but continue back to the beginning of the loop or to a label.
	(express_from_1): New function.
	(express_from): Allow more complex add_val than just CONST_INT.
	(combine_givs_p): Use rtx_cost if ADDRESS_COST is not available.
	(giv_sort_1): New function.
	(giv_sort): Handle more complex add_val genericly.
	(combine_givs): Always sort givs.


Index: loop.c
===================================================================
RCS file: /cvs/cvsfiles/egcs/gcc/loop.c,v
retrieving revision 1.22
diff -u -p -d -r1.22 loop.c
--- loop.c	1997/12/07 00:28:53	1.22
+++ loop.c	1997/12/12 16:32:46
@@ -4602,6 +4602,35 @@ record_biv (v, insn, dest_reg, inc_val, 
     }
 }
 
+static rtx
+canonize_giv_add_val (add_val)
+     rtx add_val;
+{
+  rtx a, b, t;
+
+  if (GET_CODE (add_val) != PLUS)
+    return add_val;
+
+  a = canonize_giv_add_val (XEXP (add_val, 0));
+  b = canonize_giv_add_val (XEXP (add_val, 1));
+
+  if (GET_CODE (a) == CONST_INT
+      || GET_CODE (a) == PLUS
+      || (GET_CODE (a) == REG && GET_CODE (b) == REG 
+          && REGNO (a) > REGNO (b)))
+    t = a, a = b, b = t;
+
+  if (GET_CODE (b) == PLUS 
+      && GET_CODE (a) == REG
+      && GET_CODE (XEXP (b, 0)) == REG
+      && REGNO (a) > REGNO (XEXP (b, 0)))
+    t = XEXP (b, 0), XEXP (b, 0) = a, a = t;
+
+  if (a == XEXP (add_val, 0) && b == XEXP (add_val, 1))
+    return add_val;
+  return gen_rtx (PLUS, GET_MODE (add_val), a, b);
+}
+  
 /* Fill in the data about one giv.
    V is the `struct induction' in which we record the giv.  (It is
    allocated by the caller, with alloca.)
@@ -4639,7 +4668,7 @@ record_giv (v, insn, src_reg, dest_reg, 
   v->giv_type = type;
   v->dest_reg = dest_reg;
   v->mult_val = mult_val;
-  v->add_val = add_val;
+  v->add_val = add_val = canonize_giv_add_val (add_val);
   v->benefit = benefit;
   v->location = location;
   v->cant_derive = 0;
@@ -5146,30 +5175,36 @@ basic_induction_var (x, mode, dest_reg, 
       return 0;
 
     case REG:
-      /* If this register is assigned in the previous insn, look at its
+      /* If this register is assigned in a previous insn, look at its
 	 source, but don't go outside the loop or past a label.  */
 
-      for (insn = PREV_INSN (p);
-	   (insn && GET_CODE (insn) == NOTE
-	    && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
-	   insn = PREV_INSN (insn))
-	;
+      insn = p;
+      while (1)
+	{
+	  do {
+	    insn = PREV_INSN (insn);
+	  } while (insn && GET_CODE (insn) == NOTE
+	           && NOTE_LINE_NUMBER (insn) != NOTE_INSN_LOOP_BEG);
 
-      if (insn)
-	set = single_set (insn);
+          if (!insn)
+	    break;
+	  set = single_set (insn);
+	  if (set == 0)
+	    break;
 
-      if (set != 0
-	  && (SET_DEST (set) == x
-	      || (GET_CODE (SET_DEST (set)) == SUBREG
-		  && (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
-		      <= UNITS_PER_WORD)
-		  && SUBREG_REG (SET_DEST (set)) == x)))
-	return basic_induction_var (SET_SRC (set),
-				    (GET_MODE (SET_SRC (set)) == VOIDmode
-				     ? GET_MODE (x)
-				     : GET_MODE (SET_SRC (set))),
-				    dest_reg, insn,
-				    inc_val, mult_val);
+	  if ((SET_DEST (set) == x
+	       || (GET_CODE (SET_DEST (set)) == SUBREG
+		   && (GET_MODE_SIZE (GET_MODE (SET_DEST (set)))
+		       <= UNITS_PER_WORD)
+		   && SUBREG_REG (SET_DEST (set)) == x))
+	      && basic_induction_var (SET_SRC (set),
+				      (GET_MODE (SET_SRC (set)) == VOIDmode
+				       ? GET_MODE (x)
+				       : GET_MODE (SET_SRC (set))),
+				      dest_reg, insn,
+				      inc_val, mult_val))
+	    return 1;
+	}
       /* ... fall through ...  */
 
       /* Can accept constant setting of biv only when inside inner most loop.
@@ -5713,7 +5748,77 @@ consec_sets_giv (first_benefit, p, src_r
 
    So G2 = (c/a) * G1 + (d - b*c/a)  */
 
-#ifdef ADDRESS_COST
+static rtx
+express_from_1 (a, b, mult)
+     rtx a, b;
+     HOST_WIDE_INT mult;
+{
+  /* Since these structures are sorted, we can simplify the operation.
+     Remove from A those registers that are present in B.  Add the 
+     constant at the end.  */
+
+  while (GET_CODE (a) == PLUS && GET_CODE (b) == PLUS)
+    {
+      /* Shouldn't happen.  */
+      if (GET_CODE (XEXP (a, 0)) != REG || GET_CODE (XEXP (b, 0)) != REG)
+	return NULL_RTX;
+
+      /* Indicates that a register is missing -- abort, since we don't 
+	 want to deal with minus' here.  */
+      if (REGNO (XEXP (a, 0)) < REGNO (XEXP (b, 0)))
+	return NULL_RTX;
+
+      /* Indicates an extra register in B -- add to the output.  */
+      if (REGNO (XEXP (a, 0)) > REGNO (XEXP (b, 0)))
+	{
+	  rtx c, d;
+
+	  d = express_from_1 (a, XEXP (b, 1), mult);
+	  if (d == NULL_RTX)
+	    return NULL_RTX;
+
+	  return gen_rtx (PLUS, GET_MODE (b), XEXP (b, 0), c);
+	}
+
+      /* We matched: remove one reg completely.  */
+      a = XEXP (a, 1);
+      b = XEXP (b, 1);
+    }
+
+  if (GET_CODE (a) == PLUS)
+    {
+      if (GET_CODE (b) != REG || GET_CODE (XEXP (a, 0)) != REG
+	  || REGNO (b) != REGNO (XEXP (a, 0)))
+	return NULL_RTX;
+
+      if (GET_CODE (XEXP (a, 1)) != CONST_INT)
+	return NULL_RTX;
+
+      return GEN_INT (- INTVAL (XEXP (a, 1)) * mult);
+    }
+  else if (GET_CODE (a) == REG)
+    {
+      if (GET_CODE (b) == PLUS)
+	{
+	  if (GET_CODE (XEXP (b, 0)) != REG
+	      || REGNO (a) != REGNO (XEXP (b, 0)))
+	    return NULL_RTX;
+	  return XEXP (b, 1);
+	}
+      if (GET_CODE (b) != REG
+	  || REGNO (a) != REGNO (b))
+	return NULL_RTX;
+      return const0_rtx;
+    }
+  else if (GET_CODE (a) == CONST_INT)
+    {
+      return plus_constant (b, -INTVAL (a) * mult);
+    }
+  else
+    return NULL_RTX;
+}
+  
+
 static rtx
 express_from (g1, g2)
      struct induction *g1, *g2;
@@ -5725,13 +5830,15 @@ express_from (g1, g2)
      for notation) is also an integer.  */
   if (GET_CODE (g1->mult_val) != CONST_INT
       || GET_CODE (g2->mult_val) != CONST_INT
-      || GET_CODE (g1->add_val) != CONST_INT
       || g1->mult_val == const0_rtx
       || INTVAL (g2->mult_val) % INTVAL (g1->mult_val) != 0)
-    return 0;
+    return NULL_RTX;
 
   mult = GEN_INT (INTVAL (g2->mult_val) / INTVAL (g1->mult_val));
-  add = plus_constant (g2->add_val, - INTVAL (g1->add_val) * INTVAL (mult));
+
+  add = express_from_1 (g1->add_val, g2->add_val);
+  if (add == NULL_RTX)
+    return NULL_RTX;
 
   /* Form simplified final result.  */
   if (mult == const0_rtx)
@@ -5746,7 +5853,6 @@ express_from (g1, g2)
   else
     return gen_rtx (PLUS, g2->mode, mult, add);
 }
-#endif
 
 /* Return 1 if giv G2 can be combined with G1.  This means that G2 can use
    (either directly or via an address expression) a register used to represent
@@ -5767,36 +5873,69 @@ combine_givs_p (g1, g2)
       return 1;
     }
 
-#ifdef ADDRESS_COST
   /* If G2 can be expressed as a function of G1 and that function is valid
      as an address and no more expensive than using a register for G2,
      the expression of G2 in terms of G1 can be used.  */
   if (g2->giv_type == DEST_ADDR
       && (tem = express_from (g1, g2)) != 0
       && memory_address_p (g2->mem_mode, tem)
-      && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location))
+#ifdef ADDRESS_COST
+      && ADDRESS_COST (tem) <= ADDRESS_COST (*g2->location)
+#else
+      && rtx_cost (tem, MEM) <= rtx_cost (*g2->location, MEM)
+#endif
+      )
     {
       g2->new_reg = tem;
       return 1;
     }
-#endif
 
   return 0;
 }
 
-#ifdef GIV_SORT_CRITERION
 /* Compare two givs and sort the most desirable one for combinations first.
    This is used only in one qsort call below.  */
 
 static int
+giv_sort_1 (xa, ya)
+     rtx xa, ya;
+{
+  if (GET_CODE (xa) == GET_CODE (ya))
+    {
+      if (GET_CODE (xa) == CONST_INT)
+        return (INTVAL (xa) < INTVAL (ya) ? -1 :
+		INTVAL (xa) > INTVAL (ya) ? 1 : 0);
+      else if (GET_CODE (xa) == REG)
+	return REGNO (xa) - REGNO (ya);
+      else if (GET_CODE (xa) == PLUS)
+	{
+	  int tmp = giv_sort_1 (XEXP (xa, 0), XEXP (ya, 0));
+	  if (tmp != 0)
+	    return tmp;
+	  return giv_sort_1 (XEXP (xa, 1), XEXP (ya, 1));
+	}
+    }
+  else if (GET_CODE (xa) == CONST_INT)
+    return 1;
+  else if (GET_CODE (ya) == CONST_INT)
+    return -1;
+  else if (GET_CODE (xa) == REG)
+    return 1;
+  else if (GET_CODE (ya) == REG)
+    return -1;
+  else if (GET_CODE (xa) == PLUS)
+    return 1;
+  else if (GET_CODE (ya) == PLUS)
+    return -1;
+  return 0;
+}
+ 
+static int
 giv_sort (x, y)
      struct induction **x, **y;
 {
-  GIV_SORT_CRITERION (*x, *y);
-
-  return 0;
+  return giv_sort_1 ((*x)->add_val, (*y)->add_val);
 }
-#endif
 
 /* Check all pairs of givs for iv_class BL and see if any can be combined with
    any other.  If so, point SAME to the giv combined with and set NEW_REG to
@@ -5821,16 +5960,14 @@ combine_givs (bl)
   for (g1 = bl->giv; g1; g1 = g1->next_iv)
     giv_array[i++] = g1;
 
-#ifdef GIV_SORT_CRITERION
-  /* Sort the givs if GIV_SORT_CRITERION is defined.
-     This is usually defined for processors which lack
-     negative register offsets so more givs may be combined.  */
+  /* Sort the givs.  This not only helps out processors which lack negative
+     register offsets, but also often eliminates a pointless addition at the
+     start of the loop.  */
 
   if (loop_dump_stream)
     fprintf (loop_dump_stream, "%d givs counted, sorting...\n", giv_count);
 
   qsort (giv_array, giv_count, sizeof (struct induction *), giv_sort);
-#endif
 
   for (i = 0; i < giv_count; i++)
     {