An aliasing tweak

[Richard Sandiford <rsandifo at redhat dot com>]

As I understand it, alias.c works out register base values by induction,
with step (n + 1) using base values calculated by step n, and potentially
adding a few more.  Or, to be more specific, say there are m assignments
to reg of the form:

   reg = rhs1
   reg = rhs2
   ....
   reg = rhsm

Step (n + 1) analyses each instruction in turn.  It calculates the base
value of rhs1, using base values from step n if rhs1 contains registers.
It then checks whether each subsequent set preserves this base value.

At the moment, rhs2...rhsm are all required to be simple modifications
of reg, such as reg = reg + offset.  So in code like:

    unsigned int y[4];
    ...
    x = &y[0];
    ...
    x = x + 1

x is known to stay within y[].  But the code doesn't handle cases in
which rhs2...rhsm are independent of reg, even if they have the same
base value as rhs1.  For example, if we have:

    unsigned int y[4];
    ...
    x = &y[0];
    ...
    x = &y[1];

then x will be marked as having an unknown base value.  Is there any
reason for this?  I can't see why the base value calculated for a
second or subsequent set is any less trustworthy than the first.
After all, the calculation is based on the register base values
from the previous step, which at this point are assumed to be sound.

The patch below extends alias.c:record_set so that a second or subsequent
set of a register will not cause the base value to be invalidated if the
source of the set has the same base value as the first set had.

To give a somewhat contrived cut-down example:

    void f (unsigned int *p1, int n)
    {
      unsigned int x[2] = { 1, 2 };
      unsigned int *p2 = &x[0];
      while (n--)
	{
	  *p1++ = *p2;
	  *p1++ = *p2;
	  p2 = &x[1];
	}
    }

was compiled as follows before the patch:

        ...
$L4:
        lw      $10,0($8)
        addiu   $4,$6,4
        addiu   $7,$7,-1
        sw      $10,0($6)
        lw      $3,0($8)        # <--- redundant: *p1 doesn't alias *p2
        addiu   $6,$6,8
        move    $8,$9
        bne     $7,$5,$L4
        sw      $3,0($4)
        ...

After the patch you get:

        ...
$L4:
        lw      $2,0($3)
        move    $4,$6
        addiu   $7,$7,-1
        addiu   $6,$6,4
        sw      $2,0($4)
        move    $3,$8
        sw      $2,0($6)
        bne     $7,$5,$L4
        addiu   $6,$6,4
        ...

Tests on proprietary embedded benchmarks showed a nice improvement in a
few tests.  Bootstrapped & regression tested on mips64{,el}-linux-gnu.
OK to install?

Richard


	* alias.c (record_set): Detect the case where a register is assigned
	a new value that has the same base term as the old one.

Index: alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/alias.c,v
retrieving revision 1.218
diff -u -p -F^\([(a-zA-Z0-9_]\|#define\) -r1.218 alias.c
--- alias.c	14 Mar 2004 22:25:59 -0000	1.218
+++ alias.c	17 Mar 2004 09:40:58 -0000
@@ -993,13 +993,24 @@ record_set (rtx dest, rtx set, void *dat
       return;
     }
 
-  /* This is not the first set.  If the new value is not related to the
-     old value, forget the base value. Note that the following code is
-     not detected:
-     extern int x, y;  int *p = &x; p += (&y-&x);
+  /* If this is not the first set of REGNO, see whether the new value
+     is related to the old one.  There are two cases of interest:
+
+	(1) The register might be assigned an entirely new value
+	    that has the same base value as the original set.
+
+	(2) The set might be a simple self-modification that
+	    cannot change REGNO's base value.
+
+     If neither condition holds, reject the original base value as invalid.
+     Note that the following situation is not detected:
+
+         extern int x, y;  int *p = &x; p += (&y-&x);
+
      ANSI C does not allow computing the difference of addresses
      of distinct top level objects.  */
-  if (new_reg_base_value[regno])
+  if (new_reg_base_value[regno] != 0
+      && find_base_value (src) != new_reg_base_value[regno])
     switch (GET_CODE (src))
       {
       case LO_SUM: