[PATCH] Fix PR optimization/12340

[Eric Botcazou <ebotcazou at libertysurf dot fr>]

Hi,

This is a regression from GCC 3.2.3 present on the 3.3 branch (and latent on 
mainline).

The GCSE pass produces the following sequence of insns:

(insn 609 604 810 4 0x40a5565c (parallel [
            (set (reg:SI 173)
                (plus:SI (reg:SI 185)
                    (const_int 1 [0x1])))
            (clobber (reg:CC 17 flags))
        ]) 146 {*addsi_1} (nil)
    (nil))

(insn 810 609 610 4 (nil) (set (reg:SI 185)
        (reg:SI 173)) 38 {*movsi_1} (nil)
    (nil))

...

(insn 812 765 103 4 (nil) (set (reg:SI 185)
        (reg:SI 173)) 38 {*movsi_1} (nil)
    (nil))

which the loop optimizer (basic_induction_var) interprets as meaning that the 
biv (reg 185) is incremented twice. So the total increment is 2, which leads 
to a wrong number of loop iterations and eventually fools the unroller.

Glen Nakamura pointed out that this is a known problem, which we have decided 
to live with since

2003-03-21  Glen Nakamura  <glen@imodulo.com>

	PR opt/10087
	* loop.c (loop_givs_reduce): Skip bivs with duplicate locations
	while incrementing giv.
	(record_biv): Check for duplicate biv locations and
	set (struct induction *) v->same if found.

which introduced a new semantics for (struct induction).same for bivs.

The proposed fix simply propagates this new semantics in two other places and 
documents it in loop.h. Bootstrapped/regtested on i586-redhat-linux-gnu (3.3 
branch except Ada).

The testcase is not attached because it has not yet been reduced (the 
original one weights about 50000 lines). As I experienced while reducing the 
testcase for PR opt/11646, C++ programs are really a mess to untangle and 
doing so can be 3 times as long as writing the fix.


2003-09-24  Eric Botcazou  <ebotcazou@libertysurf.fr>

	PR optimization/12340
	* loop.h (struct induction): Document the new semantics
	of the 'same' field for bivs.
	* unroll.c (biv_total_increment): Don't count the same
	biv increment several times.
	(loop_iterations) [GENERAL_INDUCT]: Likewise.

2003-09-24  Eric Botcazou  <ebotcazou@libertysurf.fr>

	* g++.dg/opt/loop1.C: New test.


-- 
Eric Botcazou

Index: loop.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/loop.h,v
retrieving revision 1.65
diff -u -p -r1.65 loop.h
--- loop.h	13 Dec 2002 00:17:20 -0000	1.65
+++ loop.h	23 Sep 2003 11:00:16 -0000
@@ -143,9 +143,12 @@ struct induction
 				   based on the same biv.  For bivs, links
 				   together all biv entries that refer to the
 				   same biv register.  */
-  struct induction *same;	/* If this giv has been combined with another
-				   giv, this points to the base giv.  The base
-				   giv will have COMBINED_WITH nonzero.  */
+  struct induction *same;	/* For givs, if the giv has been combined with
+				   another giv, this points to the base giv.
+				   The base giv will have COMBINED_WITH nonzero.
+				   For bivs, if the biv has the same LOCATION
+				   than another biv, this points to the base
+				   biv.  */
   HOST_WIDE_INT const_adjust;	/* Used by loop unrolling, when an address giv
 				   is split, and a constant is eliminated from
 				   the address, the -constant is stored here
Index: unroll.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/unroll.c,v
retrieving revision 1.184.2.5
diff -u -p -r1.184.2.5 unroll.c
--- unroll.c	21 Jul 2003 17:49:59 -0000	1.184.2.5
+++ unroll.c	23 Sep 2003 11:00:28 -0000
@@ -2478,7 +2478,13 @@ biv_total_increment (bl)
       if (v->always_computable && v->mult_val == const1_rtx
 	  && ! v->maybe_multiple
 	  && SCALAR_INT_MODE_P (v->mode))
-	result = fold_rtx_mult_add (result, const1_rtx, v->add_val, v->mode);
+	{
+	  /* If we have already counted it, skip it.  */
+	  if (v->same)
+	    continue;
+
+	  result = fold_rtx_mult_add (result, const1_rtx, v->add_val, v->mode);
+	}
       else
 	return 0;
     }
@@ -3538,6 +3544,10 @@ loop_iterations (loop)
 				 REGNO (biv_inc->add_val));
 			return 0;
 		    }
+
+		  /* If we have already counted it, skip it.  */
+		  if (biv_inc->same)
+		    continue;
 
 		  offset -= INTVAL (biv_inc->add_val);
 		}