[patch] Prevent DOM from creating overlapping live ranges of ivs

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

if DOM sees the following code:

while (1)
  {
    i_1 = phi(0, i_2);
    i_2 = i_1 + 1;

    if (something)
      break;

    foo (i_2 + 3);
  }

It transforms it to

while (1)
  {
    i_1 = phi(0, i_2);
    i_2 = i_1 + 1;

    if (something)
      break;

    foo (i_1 + 4);
  }

This by itself is a missoptimization, since it does not help anything
and forces us to use two registers for i instead of one.  But things
get only worse.

Loop header copying then creates the following code:

if (!something)
  goto somewhere;

i_1 = 0;
i_2 = 1;
while (1)
  {
    i_1 = phi (0, i_3);
    i_2 = phi (1, i_4);

    foo (i_1 + 4);

    i_3 = i_2;
    i_4 = i_3 + 1;

    if (something)
      break;
  }

This copy propagates to

if (!something)
  goto somewhere;

i_1 = 0;
i_2 = 1;
while (1)
  {
    i_1 = phi (0, i_2);
    i_2 = phi (1, i_4);

    foo (i_1 + 4);
    i_4 = i_2 + 1;

    if (something)
      break;
  }

Now we have two induction variables, and worse, i_1 is defined by
cycling around the loop (i_1 == i_2 from previous iteration), which
confuses iv analysis.  There is a patch by Sebastian for scev to handle
this case, but I think the proper fix is to prevent dom from
creating such monstrosities.

The patch below detects simple bivs and prevents dom from propagating
the value of the iv before increment across the increment.

Bootstrapped & regtested on i686.

Zdenek

	* tree-ssa-dom.c (simple_iv_increment_p): New function.
	(simplify_rhs_and_lookup_avail_expr, eliminate_redundant_computations):
	Do not propagate value of iv before increment over the increment.

Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-dom.c,v
retrieving revision 2.91
diff -c -3 -p -r2.91 tree-ssa-dom.c
*** tree-ssa-dom.c	10 Feb 2005 17:53:46 -0000	2.91
--- tree-ssa-dom.c	16 Feb 2005 10:34:47 -0000
*************** unsafe_associative_fp_binop (tree exp)
*** 1635,1640 ****
--- 1635,1680 ----
             && FLOAT_TYPE_P (TREE_TYPE (exp)));
  }
  
+ /* Returns true when STMT is a simple iv increment.  It detects the
+    following situation:
+    
+    i_1 = phi (..., i_2)
+    i_2 = i_1 +/- ...  */
+ 
+ static bool
+ simple_iv_increment_p (tree stmt)
+ {
+   tree lhs, rhs, preinc, phi;
+   unsigned i;
+ 
+   if (TREE_CODE (stmt) != MODIFY_EXPR)
+     return false;
+ 
+   lhs = TREE_OPERAND (stmt, 0);
+   if (TREE_CODE (lhs) != SSA_NAME)
+     return false;
+ 
+   rhs = TREE_OPERAND (stmt, 1);
+ 
+   if (TREE_CODE (rhs) != PLUS_EXPR
+       && TREE_CODE (rhs) != MINUS_EXPR)
+     return false;
+ 
+   preinc = TREE_OPERAND (rhs, 0);
+   if (TREE_CODE (preinc) != SSA_NAME)
+     return false;
+ 
+   phi = SSA_NAME_DEF_STMT (preinc);
+   if (TREE_CODE (phi) != PHI_NODE)
+     return false;
+ 
+   for (i = 0; i < (unsigned) PHI_NUM_ARGS (phi); i++)
+     if (PHI_ARG_DEF (phi, i) == lhs)
+       return true;
+ 
+   return false;
+ }
+ 
  /* STMT is a MODIFY_EXPR for which we were unable to find RHS in the
     hash tables.  Try to simplify the RHS using whatever equivalences
     we may have recorded.
*************** simplify_rhs_and_lookup_avail_expr (stru
*** 1688,1693 ****
--- 1728,1738 ----
      {
        tree rhs_def_stmt = SSA_NAME_DEF_STMT (TREE_OPERAND (rhs, 0));
  
+       /* If the statement defines an induction variable, do not propagate
+ 	 its value, so that we do not create overlapping life ranges.  */
+       if (simple_iv_increment_p (rhs_def_stmt))
+ 	goto dont_fold_assoc;
+ 
        /* See if the RHS_DEF_STMT has the same form as our statement.  */
        if (TREE_CODE (rhs_def_stmt) == MODIFY_EXPR)
  	{
*************** eliminate_redundant_computations (struct
*** 2551,2557 ****
        || ! def
        || TREE_CODE (def) != SSA_NAME
        || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
!       || NUM_V_MAY_DEFS (v_may_defs) != 0)
      insert = false;
  
    /* Check if the expression has been computed before.  */
--- 2596,2605 ----
        || ! def
        || TREE_CODE (def) != SSA_NAME
        || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)
!       || NUM_V_MAY_DEFS (v_may_defs) != 0
!       /* Do not record equivalences for increments of ivs.  This would create
! 	 overlapping live ranges for a very questionable gain.  */
!       || simple_iv_increment_p (stmt))
      insert = false;
  
    /* Check if the expression has been computed before.  */