This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

[patch] for PR 18529


Hello,

for loop in shape

void f(int start, int end)
{
  int i;
  for (i = start; i < end ; i++)
    a[i] = 0;
}

we are currently unable to determine that the number of iterations is
not 0 even if the loop header is copied.

Two new fold transformations are needed for this:

1) We need to be able to fold init_2 < max_4 && max_4 == -2147483648 to
   false (there is no integer smaller than -2147483648).

   To achieve this, we transform A == S && WHATEVER to
   A == S && WHATEVER[A := S]

   (provided that S is simple enough that the substitution does not
   increase cost of the expression, and being careful about the case
   when WHATEVER has side effects).

   I.e. the expression above is transformed to
   init_2 < -2147483648 && max_4 == -2147483648, which folds to false.

2) init_2 < max_4 && init_2 + 1 > max_4 needs to be folded to false.
   To achieve this, we fold A < X && A + 1 > Y to A < X && A >= Y
   (which is correct, since A < X <= MAX and therefore A + 1 cannot
   overflow).

   So the case above is transformed to init_2 < max_4 && init_2 >= max_4,
   which is (after a minor fix to the appropriate transformation) folded
   to false.

Bootstrapped & regtested on i686 and ia64.

Zdenek

	PR tree-optimization/18529
	* fold-const.c (subst, fold_to_nonsharp_ineq_using_bound): New
	functions.
	(simple_operand_p): Use STRIP_NOPS.  Consider SSA names simple.
	(fold): Fold A == S && W to A == S && W[A:=S].  Call
	fold_to_nonsharp_ineq_using_bound.
	* tree-ssa-loop-niter.c (number_of_iterations_cond): Fold the
	expressions before futher processing.

Index: fold-const.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/fold-const.c,v
retrieving revision 1.475
diff -c -3 -p -r1.475 fold-const.c
*** fold-const.c	18 Nov 2004 12:09:36 -0000	1.475
--- fold-const.c	18 Nov 2004 13:53:02 -0000
*************** eval_subst (tree arg, tree old0, tree ne
*** 2833,2838 ****
--- 2833,2870 ----
        return arg;
      }
  }
+ 
+ /* Substitute NEW for OLD in EXPR.  OLD must match by pointer comparison
+    (this function should primarily be used for ssa names as OLD).  */
+ 
+ static tree
+ subst (tree expr, tree old, tree new)
+ {
+   unsigned i, n;
+   tree ret = NULL_TREE, e, se;
+ 
+   if (expr == old)
+     return new;
+ 
+   if (!EXPR_P (expr))
+     return expr;
+ 
+   n = TREE_CODE_LENGTH (TREE_CODE (expr));
+   for (i = 0; i < n; i++)
+     {
+       e = TREE_OPERAND (expr, i);
+       se = subst (e, old, new);
+       if (e == se)
+ 	continue;
+ 
+       if (!ret)
+ 	ret = copy_node (expr);
+ 
+       TREE_OPERAND (ret, i) = se;
+     }
+ 
+   return (ret ? fold (ret) : expr);
+ }
  
  /* Return a tree for the case when the result of an expression is RESULT
     converted to TYPE and OMITTED was previously an operand of the expression
*************** static int
*** 3424,3436 ****
  simple_operand_p (tree exp)
  {
    /* Strip any conversions that don't change the machine mode.  */
!   while ((TREE_CODE (exp) == NOP_EXPR
! 	  || TREE_CODE (exp) == CONVERT_EXPR)
! 	 && (TYPE_MODE (TREE_TYPE (exp))
! 	     == TYPE_MODE (TREE_TYPE (TREE_OPERAND (exp, 0)))))
!     exp = TREE_OPERAND (exp, 0);
  
    return (CONSTANT_CLASS_P (exp)
  	  || (DECL_P (exp)
  	      && ! TREE_ADDRESSABLE (exp)
  	      && ! TREE_THIS_VOLATILE (exp)
--- 3456,3465 ----
  simple_operand_p (tree exp)
  {
    /* Strip any conversions that don't change the machine mode.  */
!   STRIP_NOPS (exp);
  
    return (CONSTANT_CLASS_P (exp)
+ 	  || TREE_CODE (exp) == SSA_NAME
  	  || (DECL_P (exp)
  	      && ! TREE_ADDRESSABLE (exp)
  	      && ! TREE_THIS_VOLATILE (exp)
*************** try_move_mult_to_index (tree type, enum 
*** 6180,6185 ****
--- 6209,6260 ----
    return build1 (ADDR_EXPR, type, ret);
  }
  
+ 
+ /* Fold A < X && A + 1 > Y to A < X && A >= Y.  Normally A + 1 > Y
+    means A >= Y && A != MAX, but in this case we know that
+    A < X <= MAX.  INEQ is A + 1 > Y, BOUND is A < X.  */
+ 
+ static tree
+ fold_to_nonsharp_ineq_using_bound (tree ineq, tree bound)
+ {
+   tree a, typea, type = TREE_TYPE (ineq), a1, y;
+ 
+   if (TREE_CODE (bound) == LT_EXPR)
+     a = TREE_OPERAND (bound, 0);
+   else if (TREE_CODE (bound) == GT_EXPR)
+     a = TREE_OPERAND (bound, 1);
+   else
+     return NULL_TREE;
+ 
+   typea = TREE_TYPE (a);
+   if (!INTEGRAL_TYPE_P (typea)
+       && !POINTER_TYPE_P (typea))
+     return NULL_TREE;
+ 
+   if (TREE_CODE (ineq) == LT_EXPR)
+     {
+       a1 = TREE_OPERAND (ineq, 1);
+       y = TREE_OPERAND (ineq, 0);
+     }
+   else if (TREE_CODE (ineq) == GT_EXPR)
+     {
+       a1 = TREE_OPERAND (ineq, 0);
+       y = TREE_OPERAND (ineq, 1);
+     }
+   else
+     return NULL_TREE;
+ 
+   if (TREE_TYPE (a1) != typea)
+     return NULL_TREE;
+ 
+   if (!operand_equal_p (a1,
+ 			build2 (PLUS_EXPR, typea, a,
+ 				build_int_cst_type (typea, 1)), 0))
+     return NULL_TREE;
+ 
+   return fold (build2 (GE_EXPR, type, a, y));
+ }
+ 
  /* Perform constant folding and related simplification of EXPR.
     The related simplifications include x*1 => x, x*0 => 0, etc.,
     and application of the associative law.
*************** fold (tree expr)
*** 8023,8028 ****
--- 8098,8154 ----
  	  && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
  	return omit_one_operand (type, integer_zero_node, arg0);
  
+       /* A == B && WHATEVER ==> A == B && WHATEVER[A := B].  Only do something
+ 	 if A is a ssa name and B is either ssa name or invariant, to make
+ 	 things simple and to avoid problems when A or B is modified inside
+ 	 WHATEVER.  */
+       if (TREE_CODE (arg0) == EQ_EXPR
+ 	  && !TREE_SIDE_EFFECTS (arg1))
+ 	{
+ 	  tree arg00 = TREE_OPERAND (arg0, 0);
+ 	  tree arg01 = TREE_OPERAND (arg0, 1);
+ 	  
+ 	  if (TREE_CODE (arg00) == SSA_NAME
+ 	      && (TREE_CODE (arg01) == SSA_NAME
+ 		  || TREE_CODE (arg01) == INTEGER_CST))
+ 	    {
+ 	      tem = subst (arg1, arg00, arg01);
+ 	      if (tem != arg1)
+ 		return fold (build2 (code, type, arg0, tem));
+ 	    }
+ 	}
+       else if (TREE_CODE (arg1) == EQ_EXPR
+ 	       && !TREE_SIDE_EFFECTS (arg0))
+ 	{
+ 	  tree arg10 = TREE_OPERAND (arg1, 0);
+ 	  tree arg11 = TREE_OPERAND (arg1, 1);
+ 	  
+ 	  if (TREE_CODE (arg10) == SSA_NAME
+ 	      && (TREE_CODE (arg11) == SSA_NAME
+ 		  || TREE_CODE (arg11) == INTEGER_CST))
+ 	    {
+ 	      tem = subst (arg0, arg10, arg11);
+ 	      if (tem != arg0)
+ 		return fold (build2 (code, type, tem, arg1));
+ 	    }
+ 	}
+ 
+       /* A < X && A + 1 > Y ==> A < X && A >= Y.  Normally A + 1 > Y
+ 	 means A >= Y && A != MAX, but in this case we know that
+ 	 A < X <= MAX.  */
+ 
+       if (!TREE_SIDE_EFFECTS (arg0)
+ 	  && !TREE_SIDE_EFFECTS (arg1))
+ 	{
+ 	  tem = fold_to_nonsharp_ineq_using_bound (arg0, arg1);
+ 	  if (tem)
+ 	    return fold (build2 (code, type, tem, arg1));
+ 
+ 	  tem = fold_to_nonsharp_ineq_using_bound (arg1, arg0);
+ 	  if (tem)
+ 	    return fold (build2 (code, type, arg0, tem));
+ 	}
+ 
      truth_andor:
        /* We only do these simplifications if we are optimizing.  */
        if (!optimize)
*************** fold (tree expr)
*** 8120,8125 ****
--- 8246,8286 ----
  	  && operand_equal_p (arg0, TREE_OPERAND (arg1, 0), 0))
  	return omit_one_operand (type, integer_one_node, arg0);
  
+       /* A != B || WHATEVER ==> A != B || WHATEVER[A := B].  Only do something
+ 	 if A is a ssa name and B is either ssa name or invariant, to make
+ 	 things simple and to avoid problems when A or B is modified inside
+ 	 WHATEVER.  */
+       if (TREE_CODE (arg0) == NE_EXPR
+ 	  && !TREE_SIDE_EFFECTS (arg1))
+ 	{
+ 	  tree arg00 = TREE_OPERAND (arg0, 0);
+ 	  tree arg01 = TREE_OPERAND (arg0, 1);
+ 	  
+ 	  if (TREE_CODE (arg00) == SSA_NAME
+ 	      && (TREE_CODE (arg01) == SSA_NAME
+ 		  || TREE_CODE (arg01) == INTEGER_CST))
+ 	    {
+ 	      tem = subst (arg1, arg00, arg01);
+ 	      if (tem != arg1)
+ 		return fold (build2 (code, type, arg0, tem));
+ 	    }
+ 	}
+       else if (TREE_CODE (arg1) == NE_EXPR
+ 	       && !TREE_SIDE_EFFECTS (arg0))
+ 	{
+ 	  tree arg10 = TREE_OPERAND (arg1, 0);
+ 	  tree arg11 = TREE_OPERAND (arg1, 1);
+ 	  
+ 	  if (TREE_CODE (arg10) == SSA_NAME
+ 	      && (TREE_CODE (arg11) == SSA_NAME
+ 		  || TREE_CODE (arg11) == INTEGER_CST))
+ 	    {
+ 	      tem = subst (arg0, arg10, arg11);
+ 	      if (tem != arg0)
+ 		return fold (build2 (code, type, tem, arg1));
+ 	    }
+ 	}
+ 
        goto truth_andor;
  
      case TRUTH_XOR_EXPR:
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	18 Nov 2004 13:53:02 -0000
*************** number_of_iterations_cond (tree type, tr
*** 372,383 ****
  
  	  if (zero_p (step0))
  	    {
! 	      base0 = build2 (PLUS_EXPR, type, base0, delta);
  	      base0 = fold (build2 (MINUS_EXPR, type, base0, step));
  	    }
  	  else
  	    {
! 	      base1 = build2 (MINUS_EXPR, type, base1, delta);
  	      base1 = fold (build2 (PLUS_EXPR, type, base1, step));
  	    }
  
--- 372,383 ----
  
  	  if (zero_p (step0))
  	    {
! 	      base0 = fold (build2 (PLUS_EXPR, type, base0, delta));
  	      base0 = fold (build2 (MINUS_EXPR, type, base0, step));
  	    }
  	  else
  	    {
! 	      base1 = fold (build2 (MINUS_EXPR, type, base1, delta));
  	      base1 = fold (build2 (PLUS_EXPR, type, base1, step));
  	    }
  


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]