[patch] for PR 26900

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

Hello,

to get rid of the assumptions for # of iterations of the loop in this
PR, we need to be able to fold expressions like

x <= y + 1 && x - 1 > y

to false (of course assuming that the arithmetics does not overflow,
otherwise the conditions may be satisfied by x == INT_MIN).

Another class of comparisons that we currently do not simplify is

x > y + 10 && x > y + 20

which is equivalent to just x > y + 20.

Originally, I thought I might be able to rewrite the inequalities as x -
y <= 1 && x - y > 1 and use fold_range_test (the transformation itself
is invalid, since it may introduce overflows, but thought that as long
as I am only interested in true/false return values, I won't mind).
However, this transformation may break things -- x <= y + INT_MAX is a
nontrivial inequality, while x - y <= INT_MAX is always true.

Therefore, I have written a separate functions to fold the pair of
inequalities in two variables.

Another problem is that scev_const_prop won't replace the final values
in the loop in this PR, since it considers the expression that
gives its number of iterations too expensive.  I had seen problems
like this before, and given that final value elimination is a
prerequisite for many other loop optimizations, I think it is worth
a try to remove the check for expensiveness of the calculation
(the worst case is that we may introduce a division by the step of the
control variable of the loop).

Bootstrapped & regtested on x86_64.

Zdenek

	PR tree-optimization/26900
	* tree-scalar-evolution.c (expression_expensive_p): Removed.
	(scev_const_prop): Do not use expression_expensive_p.
	* fold-const.c (analyze_interval_relationship, sign_of_subterm_1,
	sign_of_subterm, separate_term, separate_variable,
	fold_two_comparisons): New functions.
	(fold_binary): Use fold_two_comparisons.

	* gcc.dg/tree-ssa/pr26899.c: Update outcome.
	* gcc.dg/tree-ssa/loop-26.c: New test.
	* gcc.dg/fold-compare-4.c: New test.

Index: tree-scalar-evolution.c
===================================================================
*** tree-scalar-evolution.c	(revision 121793)
--- tree-scalar-evolution.c	(working copy)
*************** scev_finalize (void)
*** 2875,2888 ****
    BITMAP_FREE (already_instantiated);
  }
  
- /* Returns true if EXPR looks expensive.  */
- 
- static bool
- expression_expensive_p (tree expr)
- {
-   return force_expr_to_var_cost (expr) >= target_spill_cost;
- }
- 
  /* Replace ssa names for that scev can prove they are constant by the
     appropriate constants.  Also perform final value replacement in loops,
     in case the replacement expressions are cheap.
--- 2875,2880 ----
*************** scev_const_prop (void)
*** 2969,2978 ****
  	continue;
  
        niter = number_of_latch_executions (loop);
!       if (niter == chrec_dont_know
! 	  /* If computing the number of iterations is expensive, it may be
! 	     better not to introduce computations involving it.  */
! 	  || expression_expensive_p (niter))
  	continue;
  
        /* Ensure that it is possible to insert new statements somewhere.  */
--- 2961,2967 ----
  	continue;
  
        niter = number_of_latch_executions (loop);
!       if (niter == chrec_dont_know)
  	continue;
  
        /* Ensure that it is possible to insert new statements somewhere.  */
Index: fold-const.c
===================================================================
*** fold-const.c	(revision 121793)
--- fold-const.c	(working copy)
*************** fold_to_nonsharp_ineq_using_bound (tree 
*** 6815,6820 ****
--- 6815,7208 ----
    return fold_build2 (GE_EXPR, type, a, y);
  }
  
+ /* Analyzes relative positions of two intervals -- integers that satisfy
+    x CODE1 BND1 and x CODE2 BND2.  UNION_IS_EVERYTHING is set to true
+    if any integer satisfies one of the inequalities.  INTERSECTION_IS_EMPTY
+    is set to true if no integer satisfies both of them.  I1_SUBSET_I2
+    is set to true if the first inequality implies the second one, and
+    I2_SUBSET_I1 if the second one implies the first one.  */
+ 
+ static void
+ analyze_interval_relationship (enum tree_code code1, tree bnd1,
+ 			       enum tree_code code2, tree bnd2,
+ 			       bool *union_is_everything,
+ 			       bool *intersection_is_empty,
+ 			       bool *i1_subset_i2,
+ 			       bool *i2_subset_i1)
+ {
+   tree pos, tree_tmp;
+   enum tree_code code_tmp;
+   bool swapped = false, tmp;
+   tree type1, type2;
+   int cmp;
+ 
+   *union_is_everything = false;
+   *intersection_is_empty = false;
+   *i1_subset_i2 = false;
+   *i2_subset_i1 = false;
+ 
+   /* Make the first compare == or != if possible.  */
+   if (code2 == EQ_EXPR || code2 == NE_EXPR)
+     {
+       code_tmp = code1; code1 = code2; code2 = code_tmp;
+       tree_tmp = bnd1; bnd1 = bnd2; bnd2 = tree_tmp;
+       swapped = true;
+     }
+ 
+   if (code1 == EQ_EXPR)
+     {
+       pos = fold_relational_const (code2, boolean_type_node, bnd1, bnd2);
+ 
+       if (operand_equal_p (bnd1, bnd2, 0))
+ 	{
+ 	  *union_is_everything = (code2 == NE_EXPR);
+ 	  *i2_subset_i1 = (code2 == EQ_EXPR);
+ 	}
+ 
+       if (integer_zerop (pos))
+ 	*intersection_is_empty = true;
+       else
+ 	*i1_subset_i2 = true;
+     }
+   else if (code1 == NE_EXPR)
+     {
+       pos = fold_relational_const (code2, boolean_type_node, bnd1, bnd2);
+      
+       if (integer_onep (pos))
+ 	*union_is_everything = true;
+       else
+ 	*i2_subset_i1 = true;
+ 
+       if (operand_equal_p (bnd1, bnd2, 0))
+ 	{
+ 	  *intersection_is_empty = (code2 == EQ_EXPR);
+ 	  *i1_subset_i2 = (code2 == NE_EXPR);
+ 	}
+     }
+   else
+     {
+       /* Both CODE1 and CODE2 are inequalities.  If they have the same
+ 	 orientation, we are interested in the subset relationships.
+ 	 If they have reverse orientations, their union and intersection
+ 	 becomes interesting.  But first, canonicalize both comparisons
+ 	 to non-sharp inequalities.  */
+ 
+       type1 = TREE_TYPE (bnd1);
+       if (code1 == LT_EXPR)
+ 	{
+ 	  code1 = LE_EXPR;
+ 	  bnd1 = fold_binary (MINUS_EXPR, type1, bnd1, build_int_cst (type1, 1));
+ 	}
+       else if (code1 == GT_EXPR)
+ 	{
+ 	  code1 = GE_EXPR;
+ 	  bnd1 = fold_binary (PLUS_EXPR, type1, bnd1, build_int_cst (type1, 1));
+ 	}
+       if (TREE_OVERFLOW (bnd1))
+ 	return;
+ 
+       type2 = TREE_TYPE (bnd2);
+       if (code2 == LT_EXPR)
+ 	{
+ 	  code2 = LE_EXPR;
+ 	  bnd2 = fold_binary (MINUS_EXPR, type2, bnd2, build_int_cst (type2, 1));
+ 	}
+       else if (code2 == GT_EXPR)
+ 	{
+ 	  code2 = GE_EXPR;
+ 	  bnd2 = fold_binary (PLUS_EXPR, type2, bnd2, build_int_cst (type2, 1));
+ 	}
+       if (TREE_OVERFLOW (bnd2))
+ 	return;
+ 
+       if ((code1 == LE_EXPR) == (code2 == LE_EXPR))
+ 	{
+ 	  /* The directions of the inequalities are the same.  */
+ 	  cmp = tree_int_cst_compare (bnd1, bnd2);
+ 
+ 	  /* Make us deal with the case X <= BND.  */
+ 	  if (code1 == GE_EXPR)
+ 	    cmp = -cmp;
+ 
+ 	  *i1_subset_i2 = cmp <= 0;
+ 	  *i2_subset_i1 = cmp >= 0;
+ 	}
+       else
+ 	{
+ 	  /* The directions of the inequalities differ.  */
+ 	  if (code1 != LE_EXPR)
+ 	    {
+ 	      code_tmp = code1; code1 = code2; code2 = code_tmp;
+ 	      tree_tmp = bnd1; bnd1 = bnd2; bnd2 = tree_tmp;
+ 	      type2 = type1;
+ 	    }
+ 	  bnd2 = fold_binary (MINUS_EXPR, type2, bnd2, build_int_cst (type2, 1));
+ 	  if (TREE_OVERFLOW (bnd2))
+ 	    return;
+ 
+ 	  /* Now we are in the shape X <= BND1, X > BND2.  */
+ 	  cmp = tree_int_cst_compare (bnd1, bnd2);
+ 
+ 	  *intersection_is_empty = cmp <= 0;
+ 	  *union_is_everything = cmp >= 0;
+ 	}
+     }
+ 
+   if (swapped)
+     {
+       tmp = *i1_subset_i2; *i1_subset_i2 = *i2_subset_i1; *i2_subset_i1 = tmp;
+     }
+ }
+ 
+ /* Tries to determine with what sign a simple term X appears in TERM.  If it
+    succeeds, *SIGN is set to true if the X appears positively and to false if
+    it appears negated, and true is returned.  Otherwise, false is returned.  */
+ 
+ static bool
+ sign_of_subterm_1 (tree term, tree x, bool *sign)
+ {
+   switch (TREE_CODE (term))
+     {
+     case PLUS_EXPR:
+       return (sign_of_subterm_1 (TREE_OPERAND (term, 0), x, sign)
+ 	      || sign_of_subterm_1 (TREE_OPERAND (term, 1), x, sign));
+     case MINUS_EXPR:
+       if (sign_of_subterm_1 (TREE_OPERAND (term, 0), x, sign))
+ 	return true;
+       if (sign_of_subterm_1 (TREE_OPERAND (term, 1), x, sign))
+ 	{
+ 	  *sign = !*sign;
+ 	  return true;
+ 	}
+       return false;
+ 
+     case NEGATE_EXPR:
+       if (sign_of_subterm_1 (TREE_OPERAND (term, 0), x, sign))
+ 	{
+ 	  *sign = !*sign;
+ 	  return true;
+ 	}
+       return false;
+ 
+     default:
+       if (operand_equal_p (term, x, 0))
+ 	{
+ 	  *sign = true;
+ 	  return true;
+ 	}
+ 
+       return false;
+     }
+ }
+ 
+ /* Tries to determine with what sign SUBTERM appears in TERM.  If it succeeds,
+    *SIGN is set to true if the SUBTERM appears positively and to false if
+    it appears negated, and true is returned.  Otherwise, false is returned.  */
+ 
+ static bool
+ sign_of_subterm (tree term, tree subterm, bool *sign)
+ {
+   bool negate = false, ret;
+   tree x;
+ 
+   if (!term)
+     return false;
+ 
+   /* First, find an atomic term X in SUBTERM.  We use the sign of X in TERM
+      as a return value.  Note that this may mean that we return true even
+      if SUBTERM as a whole is not a subterm of TERM, but since we use
+      the result of this function only as a heuristics, this does not
+      matter.  */
+   x = subterm;
+   while (1)
+     {
+       if (TREE_CODE (x) == NEGATE_EXPR)
+ 	{
+ 	  x = TREE_OPERAND (x, 0);
+ 	  negate = !negate;
+ 	}
+       else if (TREE_CODE (x) == PLUS_EXPR
+ 	       || TREE_CODE (x) == MINUS_EXPR)
+ 	x = TREE_OPERAND (x, 0);
+       else
+ 	break;
+     }
+ 
+   ret = sign_of_subterm_1 (term, x, sign);
+   if (ret && negate)
+     *sign = !*sign;
+ 
+   return ret;
+ }
+ 
+ /* Tries to express TERM as X + CST.  Returns true if it succeeds, false
+    otherwise.  */
+ 
+ static bool
+ separate_term (tree term, tree *x, tree *cst)
+ {
+   tree op0, op1, type = TREE_TYPE (term);
+ 
+   *x = term;
+   *cst = build_int_cst (type, 0);
+ 
+   if (TREE_CODE (term) == PLUS_EXPR)
+     {
+       op0 = TREE_OPERAND (term, 0);
+       op1 = TREE_OPERAND (term, 1);
+       if (TREE_CODE (op1) == INTEGER_CST)
+ 	{
+ 	  *x = op0;
+ 	  *cst = op1;
+ 	}
+       else
+ 	{
+ 	  *x = term;
+ 	  *cst = build_int_cst (type, 0);
+ 	}
+     }
+   else if (TREE_CODE (term) == MINUS_EXPR)
+     {
+       op0 = TREE_OPERAND (term, 0);
+       op1 = TREE_OPERAND (term, 1);
+       if (TREE_CODE (op1) == INTEGER_CST)
+ 	{
+ 	  *x = op0;
+ 	  *cst = fold_unary (NEGATE_EXPR, type, op1);
+ 	}
+       else if (TREE_CODE (op0) == INTEGER_CST)
+ 	{
+ 	  *x = fold_build1 (NEGATE_EXPR, type, op1);
+ 	  *cst = op0;
+ 	}
+     }
+ 
+   if (TREE_OVERFLOW (*cst))
+     return false;
+ 
+   return true;
+ }
+ 
+ /* Tries to express the inequality L CMP R in shape variable (stored to L)
+    cmp (stored to CMP) constant (stored to R).  If VAR is not NULL, we try
+    to make the variable to be equal to VAR.  Returns true if it succeeds,
+    false otherwise.  */
+ 
+ static bool
+ separate_variable (tree *l, enum tree_code *cmp, tree *r, tree var)
+ {
+   tree xl, cl, xr, cr, type = TREE_TYPE (*l);
+   bool positive;
+ 
+   if (!separate_term (*l, &xl, &cl)
+       || !separate_term (*r, &xr, &cr)
+       || (!xl && !xr))
+     return false;
+ 
+   *r = fold_binary (MINUS_EXPR, type, cr, cl);
+   if (TREE_OVERFLOW (*r))
+     return false;
+ 
+   /* The comparison is now in shape XL cmp XR + *R.  Move both variable
+      terms to the left-hand side.  */
+ 
+   if (xr)
+     {
+       if (xl)
+ 	*l = fold_build2 (MINUS_EXPR, type, xl, xr);
+       else
+ 	*l = fold_build1 (NEGATE_EXPR, type, xr);
+     }
+ 
+   /* If the variable appears negated in VAR, negate the whole expression.  */
+   if (sign_of_subterm (var, *l, &positive)
+       && !positive)
+     {
+       *l = fold_build1 (NEGATE_EXPR, type, *l);
+       *r = fold_unary (NEGATE_EXPR, type, *r);
+       if (TREE_OVERFLOW (*r))
+ 	return false;
+       *cmp = swap_tree_comparison (*cmp);
+     }
+ 
+   return true;
+ }
+ 
+ /* Tries to prove that two comparisons COMP1 and COMP2 are contradictory,
+    or one of them is redundant.  CONJUNCTION is true if the folded expression
+    is COMP1 && COMP2, false if it is COMP1 || COMP2.  Returns the folded
+    expression, or NULL if it fails to simplify the expression.  */
+ 
+ static tree
+ fold_two_comparisons (tree comp1, tree comp2, bool conjunction)
+ {
+   tree l1 = TREE_OPERAND (comp1, 0), r1 = TREE_OPERAND (comp1, 1);
+   enum tree_code code1 = TREE_CODE (comp1);
+   tree l2 = TREE_OPERAND (comp2, 0), r2 = TREE_OPERAND (comp2, 1);
+   enum tree_code code2 = TREE_CODE (comp2);
+   tree type1, type2;
+   bool union_is_everything;
+   bool intersection_is_empty;
+   bool i1_subset_i2, i2_subset_i1;
+ 
+   STRIP_SIGN_NOPS (l1);
+   STRIP_SIGN_NOPS (r1);
+   STRIP_SIGN_NOPS (l2);
+   STRIP_SIGN_NOPS (r2);
+ 
+   /* Types of both comparisons should match, otherwise we cannot combine
+      them.  Also, we require that the arithmetic operations do not
+      overflow, so that we may behave like if they were computed in
+      an infinite precision.  */
+   type1 = TREE_TYPE (l1);
+   type2 = TREE_TYPE (l2);
+   if (!INTEGRAL_TYPE_P (type1)
+       || !INTEGRAL_TYPE_P (type2)
+       || TYPE_PRECISION (type1) != TYPE_PRECISION (type2)
+       || TYPE_UNSIGNED (type1) != TYPE_UNSIGNED (type2)
+       || !TYPE_OVERFLOW_UNDEFINED (type1)
+       || !TYPE_OVERFLOW_UNDEFINED (type2))
+     return NULL_TREE;
+ 
+   /* Transform the inequalities to VAR CMP CST shape (this transformation would
+      not necessarily be correct in a limited precision).  The variables
+      compared in both of them should be the same.  */
+   if (!separate_variable (&l1, &code1, &r1, NULL_TREE)
+       || !separate_variable (&l2, &code2, &r2, l1)
+       || !operand_equal_p (l1, l2, 0))
+     return NULL_TREE;
+ 
+   /* Find the relative positions of the intervals corresponding to the ranges
+      of values on that the inequalities are satisfied.  */
+   analyze_interval_relationship (code1, r1, code2, r2,
+ 				 &union_is_everything, &intersection_is_empty,
+ 				 &i1_subset_i2, &i2_subset_i1);
+ 
+   if (conjunction)
+     {
+       if (intersection_is_empty)
+ 	return boolean_false_node;
+       if (i1_subset_i2)
+ 	{
+ 	  /* COMP1 being satisfied implies COMP2 being satisfied.  */
+ 	  return comp1;
+ 	}
+       if (i2_subset_i1)
+ 	return comp2;
+     }
+   else
+     {
+       if (union_is_everything)
+ 	return boolean_true_node;
+       if (i1_subset_i2)
+ 	return comp2;
+       if (i2_subset_i1)
+ 	return comp1;
+     }
+ 
+   return NULL_TREE;
+ }
+ 
  /* Fold a sum or difference of at least one multiplication.
     Returns the folded tree or NULL if no simplification could be made.  */
  
*************** fold_binary (enum tree_code code, tree t
*** 10691,10696 ****
--- 11079,11096 ----
  	}
  
      truth_andor:
+       if (COMPARISON_CLASS_P (arg0)
+ 	  && COMPARISON_CLASS_P (arg1)
+ 	  && !TREE_SIDE_EFFECTS (arg0)
+ 	  && !TREE_SIDE_EFFECTS (arg1))
+ 	{
+ 	  tem = fold_two_comparisons (arg0, arg1,
+ 				      (code == TRUTH_AND_EXPR
+ 				       || code == TRUTH_ANDIF_EXPR));
+ 	  if (tem)
+ 	    return tem;
+ 	}
+ 
        /* We only do these simplifications if we are optimizing.  */
        if (!optimize)
  	return NULL_TREE;
Index: testsuite/gcc.dg/tree-ssa/pr26899.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/pr26899.c	(revision 121793)
--- testsuite/gcc.dg/tree-ssa/pr26899.c	(working copy)
*************** int foo (int i, int j)
*** 5,10 ****
    return (i < j + 1) || (j > i - 1);
  }
  
! /* { dg-final { scan-tree-dump "j >= i" "gimple" } } */
  /* { dg-final { cleanup-tree-dump "gimple" } } */
  
--- 5,10 ----
    return (i < j + 1) || (j > i - 1);
  }
  
! /* { dg-final { scan-tree-dump "i <= j" "gimple" } } */
  /* { dg-final { cleanup-tree-dump "gimple" } } */
  
Index: testsuite/gcc.dg/tree-ssa/loop-26.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/loop-26.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/loop-26.c	(revision 0)
***************
*** 0 ****
--- 1,13 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O -fstrict-overflow -fdump-tree-empty" } */
+ 
+ int foo0(int i0, int i1)
+ {
+   int i, j = 0;
+   for (i=i0; i<=i1+1; ++i)
+     ++j;
+   return j;
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "Removing empty loop" 1 "empty" } } */
+ /* { dg-final { cleanup-tree-dump "empty" } } */
Index: testsuite/gcc.dg/fold-compare-4.c
===================================================================
*** testsuite/gcc.dg/fold-compare-4.c	(revision 0)
--- testsuite/gcc.dg/fold-compare-4.c	(revision 0)
***************
*** 0 ****
--- 1,121 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-cleanup_cfg1" } */
+ 
+ void this_comparison_is_false (void);
+ void this_comparison_is_true (void);
+ void this_comparison_is_not_decidable (void);
+ 
+ void bla0a (int x, int y)
+ {
+   if (x < y + 8 && x > y + 10)
+     this_comparison_is_false ();
+ }
+ 
+ void bla0b (int x, int y)
+ {
+   if (x < y + 8 && x >= y + 8)
+     this_comparison_is_false ();
+ }
+ 
+ void bla0c (int x, int y)
+ {
+   if (x < y + 8 && x >= y + 7)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla0d (int x, int y)
+ {
+   if (x == y + 8 && x >= y + 7)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla0e (int x, int y)
+ {
+   if (x == y + 8 && x > y + 9)
+     this_comparison_is_false ();
+ }
+ 
+ void bla0f (int x, int y)
+ {
+   if (x != y + 8 && x >= y + 7)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla0g (int x, int y)
+ {
+   if (x != y + 8 && x > y + 9)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla0h (int x, int y)
+ {
+   if (x != y + 8 && x != y + 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla1 (int x, int y)
+ {
+   if (x + 5 < y + 10 && y - 4 <= x - 9)
+     this_comparison_is_false ();
+ }
+ 
+ void bla2 (int x, int y)
+ {
+   if (x + 5 == y + 10 && 4 - y <= 6 - x)
+     this_comparison_is_false ();
+ }
+ 
+ void bla3a (int x, int y)
+ {
+   if (x < y + 8 || x > y + 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3b (int x, int y)
+ {
+   if (x < y + 8 || x >= y + 8)
+     this_comparison_is_true ();
+ }
+ 
+ void bla3c (int x, int y)
+ {
+   if (x < y + 8 || x >= y + 7)
+     this_comparison_is_true ();
+ }
+ 
+ void bla3d (int x, int y)
+ {
+   if (x == y + 8 || x >= y + 7)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3e (int x, int y)
+ {
+   if (x == y + 8 || x > y + 9)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3f (int x, int y)
+ {
+   if (x != y + 8 || x >= y + 7)
+     this_comparison_is_true ();
+ }
+ 
+ void bla3g (int x, int y)
+ {
+   if (x != y + 8 || x > y + 9)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3h (int x, int y)
+ {
+   if (x != y + 8 || x != y + 10)
+     this_comparison_is_true ();
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "this_comparison_is_false" 0 "cleanup_cfg1" } } */
+ /* { dg-final { scan-tree-dump-times "this_comparison_is_true" 4 "cleanup_cfg1" } } */
+ /* { dg-final { scan-tree-dump-times "this_comparison_is_not_decidable" 9 "cleanup_cfg1" } } */
+ /* { dg-final { scan-tree-dump-times "if " 14 "cleanup_cfg1" } } */
+ 
+ /* { dg-final { cleanup-tree-dump "cleanup_cfg1" } } */