RFC: improve induction variable choice

[Dale Johannesen <dalej at apple dot com>]

On Darwin, and probably others, some induction variables are not 
getting reduced that
ought to be.  For example:

int a[100];
int foo (int n)
{
  int i;
  for (i=0; i<100; i++)
    a[i] = 42;
}

produces

L8:
        slwi r0,r2,2
        addi r2,r2,1
        stwx r9,r11,r0
        bdnz L8

instead of

L8:
        stw r0,0(r2)
        addi r2,r2,4
        bdnz L8

It seems to me that the basic problem is the benefit computation 
doesn't take into account that
the original variable is going to be deleted.  We've had the following 
patch in place here for
some time with good results.  However, I'm not sure this will be an 
improvement on small-register
targets.  Ideas?

Index: loop.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.c,v
retrieving revision 1.470
diff -u -d -b -w -c -3 -p -r1.470 loop.c
cvs server: conflicting specifications of output style
*** loop.c      7 Sep 2003 05:21:35 -0000       1.470
--- loop.c      15 Sep 2003 19:17:53 -0000
*************** loop_giv_reduce_benefit (struct loop *lo
*** 4963,4968 ****
--- 4963,4986 ----
       determining code size than run-time benefits.  */
    benefit -= add_cost * bl->biv_count;

+   /* Adjust this computation to allow for the likelihood that the
+      original increment of the biv will be deleted.  This permits
+      induction variables to be selected correctly in simple
+      cases like for(i){a[i]=42;}   */
+   if ( v->replaceable && bl->eliminable )
+     {
+       int orig_add_cost = iv_add_mult_cost (bl->biv->add_val,
+                               bl->biv->mult_val, test_reg, test_reg);
+       benefit += orig_add_cost * bl->biv_count;
+     }
+
    /* Decide whether to strength-reduce this giv or to leave the code
       unchanged (recompute it from the biv each time it is used).  This
       decision can be made independently for each giv.  */