Re: number_of_iterations_in_loop issues

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

Hello,

in the following testcase

> int ca[N];
>
> int foo ()
> {
>   unsigned int i;
>   int n;
> 
>   for (i = 0; i < n; i++)
>     {
>       ca[i] = 2;
>     }
> }

# of iterations analysis does not recognize that the number of
# iterations cannot be zero, even though the entry condition is
copied in front of the loop.

The reason is the extra cast to unsigned; i.e. the code looks like

n.1_13 = (unsigned) n_5;
if (n_5 != 0)
  {
    i = 0;
    do
      {
        ...
	i++;
      } while (i < n.1_13);
  }

When we check for initial conditions we are unable to derive any useful
information, since the ssa name used in the test in loop is n.1_13 and
the one in condition is n_5 (the exact condition checked is
(n_5 != 0 && n.1_13 == 0).

The patch fixes the problem by replacing the ssa names that are defined
in a "simple" way (cast, increment by a constant) inside the expressions
during checking.  This way the checked condition becomes
(n_5 != 0 && (unsigned) n_5 == 0), which folds to false.

Bootstrapped & regtested on i686 and ia64.

Zdenek

	* tree-ssa-loop-niter.c (tree_simplify_using_condition): Expand simple
	definitions of ssa names in condition.  Split recusive part to ...
	(tree_simplify_using_condition_1): New function.
	(expand_simple_operations): New function.

Index: tree-ssa-loop-niter.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-loop-niter.c,v
retrieving revision 2.16
diff -c -3 -p -r2.16 tree-ssa-loop-niter.c
*** tree-ssa-loop-niter.c	15 Nov 2004 00:18:33 -0000	2.16
--- tree-ssa-loop-niter.c	17 Nov 2004 09:23:26 -0000
*************** simplify_using_outer_evolutions (struct 
*** 555,568 ****
    return expr;
  }
  
  /* Tries to simplify EXPR using the condition COND.  Returns the simplified
!    expression (or EXPR unchanged, if no simplification was possible).*/
  
  static tree
! tree_simplify_using_condition (tree cond, tree expr)
  {
    bool changed;
!   tree e, e0, e1, e2, notcond;
    enum tree_code code = TREE_CODE (expr);
  
    if (code == INTEGER_CST)
--- 555,624 ----
    return expr;
  }
  
+ /* Expand definitions of ssa names in EXPR as long as they are simple
+    enough, and return the new expression.  */
+ 
+ static tree
+ expand_simple_operations (tree expr)
+ {
+   unsigned i, n;
+   tree ret = NULL_TREE, e, ee, stmt;
+   enum tree_code code = TREE_CODE (expr);
+ 
+   if (is_gimple_min_invariant (expr))
+     return expr;
+ 
+   if (IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)))
+     {
+       n = TREE_CODE_LENGTH (code);
+       for (i = 0; i < n; i++)
+ 	{
+ 	  e = TREE_OPERAND (expr, i);
+ 	  ee = expand_simple_operations (e);
+ 	  if (e == ee)
+ 	    continue;
+ 
+ 	  if (!ret)
+ 	    ret = copy_node (expr);
+ 
+ 	  TREE_OPERAND (ret, i) = ee;
+ 	}
+ 
+       return (ret ? fold (ret) : expr);
+     }
+ 
+   if (TREE_CODE (expr) != SSA_NAME)
+     return expr;
+ 
+   stmt = SSA_NAME_DEF_STMT (expr);
+   if (TREE_CODE (stmt) != MODIFY_EXPR)
+     return expr;
+ 
+   e = TREE_OPERAND (stmt, 1);
+   if (/* Casts are simple.  */
+       TREE_CODE (e) != NOP_EXPR
+       && TREE_CODE (e) != CONVERT_EXPR
+       /* Copies are simple.  */
+       && TREE_CODE (e) != SSA_NAME
+       /* Assignments of invariants are simple.  */
+       && !is_gimple_min_invariant (e)
+       /* And increments and decrements by a constant are simple.  */
+       && !((TREE_CODE (e) == PLUS_EXPR
+ 	    || TREE_CODE (e) == MINUS_EXPR)
+ 	   && is_gimple_min_invariant (TREE_OPERAND (e, 1))))
+     return expr;
+ 
+   return expand_simple_operations (e);
+ }
+ 
  /* Tries to simplify EXPR using the condition COND.  Returns the simplified
!    expression (or EXPR unchanged, if no simplification was possible).  */
  
  static tree
! tree_simplify_using_condition_1 (tree cond, tree expr)
  {
    bool changed;
!   tree e, te, e0, e1, e2, notcond;
    enum tree_code code = TREE_CODE (expr);
  
    if (code == INTEGER_CST)
*************** tree_simplify_using_condition (tree cond
*** 574,590 ****
      {
        changed = false;
  
!       e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0));
        if (TREE_OPERAND (expr, 0) != e0)
  	changed = true;
  
!       e1 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 1));
        if (TREE_OPERAND (expr, 1) != e1)
  	changed = true;
  
        if (code == COND_EXPR)
  	{
! 	  e2 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 2));
  	  if (TREE_OPERAND (expr, 2) != e2)
  	    changed = true;
  	}
--- 630,646 ----
      {
        changed = false;
  
!       e0 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 0));
        if (TREE_OPERAND (expr, 0) != e0)
  	changed = true;
  
!       e1 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 1));
        if (TREE_OPERAND (expr, 1) != e1)
  	changed = true;
  
        if (code == COND_EXPR)
  	{
! 	  e2 = tree_simplify_using_condition_1 (cond, TREE_OPERAND (expr, 2));
  	  if (TREE_OPERAND (expr, 2) != e2)
  	    changed = true;
  	}
*************** tree_simplify_using_condition (tree cond
*** 603,624 ****
        return expr;
      }
  
    /* Check whether COND ==> EXPR.  */
    notcond = invert_truthvalue (cond);
!   e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node,
! 		   notcond, expr));
    if (nonzero_p (e))
      return e;
  
    /* Check whether COND ==> not EXPR.  */
!   e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node,
! 		   cond, expr));
    if (zero_p (e))
      return e;
  
    return expr;
  }
  
  /* Tries to simplify EXPR using the conditions on entry to LOOP.
     Record the conditions used for simplification to CONDS_USED.
     Returns the simplified expression (or EXPR unchanged, if no
--- 659,695 ----
        return expr;
      }
  
+   te = expand_simple_operations (expr);
+ 
    /* Check whether COND ==> EXPR.  */
    notcond = invert_truthvalue (cond);
!   e = fold (build2 (TRUTH_OR_EXPR, boolean_type_node, notcond, te));
    if (nonzero_p (e))
      return e;
  
    /* Check whether COND ==> not EXPR.  */
!   e = fold (build2 (TRUTH_AND_EXPR, boolean_type_node, cond, te));
    if (zero_p (e))
      return e;
  
    return expr;
  }
  
+ /* Tries to simplify EXPR using the condition COND.  Returns the simplified
+    expression (or EXPR unchanged, if no simplification was possible).
+    Wrapper around tree_simplify_using_condition_1 that ensures that chains
+    of simple operations in definitions of ssa names in COND are expanded,
+    so that things like casts or incrementing the value of the bound before
+    the loop do not cause us to fail.  */
+ 
+ static tree
+ tree_simplify_using_condition (tree cond, tree expr)
+ {
+   cond = expand_simple_operations (cond);
+ 
+   return tree_simplify_using_condition_1 (cond, expr);
+ }
+      
  /* Tries to simplify EXPR using the conditions on entry to LOOP.
     Record the conditions used for simplification to CONDS_USED.
     Returns the simplified expression (or EXPR unchanged, if no