[patch] for PR 23361

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

Hello,

one of the reasons for this PR is that we fail to fold expressions like
a + 10 > MIN_INT + 2, that are always true (assuming that the
arithmetics in the considered type does not overflow).  Such expressions
are fairly often produced by number of iterations analysis.
This patch implements such simplifications.

Bootstrapped & regtested on i686 and x86_64.

Zdenek

Index: fold-const.c
===================================================================
*** fold-const.c	(revision 121710)
--- fold-const.c	(working copy)
*************** maybe_canonicalize_comparison (enum tree
*** 7999,8004 ****
--- 7999,8099 ----
    return maybe_canonicalize_comparison_1 (code, type, arg1, arg0);
  }
  
+ /* Given a comparison var CODE CSTL CMP CSTR in that the addition/subtraction
+    on the left-hand side does not overflow, returns true if the result
+    of the comparison is always true or false.  In that case, the result
+    of the comparison is stored to RESULT.  ADD_P is true if CSTL is added
+    and false if it is subtracted.  */
+ 
+ static bool
+ fold_offsetted_comparison_p (enum tree_code code, tree cstl, enum tree_code cmp,
+ 			     tree cstr, bool *result)
+ {
+   tree type = TREE_TYPE (cstl);
+   tree lhs_min, lhs_max, type_min, type_max;
+   bool interval_at_bottom;
+   
+   if (!INTEGRAL_TYPE_P (type))
+     return false;
+ 
+   type_min = TYPE_MIN_VALUE (type);
+   type_max = TYPE_MAX_VALUE (type);
+ 
+   if (!type_min || !type_max)
+     return false;
+ 
+   /* First, determine the range of lhs.  The range starts with type_min
+      if CODE==PLUS_EXPR and CSTL is negative, or CODE==MINUS_EXPR and
+      CSTL is positive.  */
+   interval_at_bottom = (code == PLUS_EXPR) == (tree_int_cst_sgn (cstl) < 0);
+ 
+   if (interval_at_bottom)
+     {
+       lhs_min = type_min;
+       lhs_max = fold_binary (code, type, type_max, cstl);
+     }
+   else
+     {
+       lhs_min = fold_binary (code, type, type_min, cstl);
+       lhs_max = type_max;
+     }
+ 
+   /* Now compare the position of CSTR with the position of the value range
+      of LHS.  */
+   cstr = fold_convert (type, cstr);
+   switch (cmp)
+     {
+     case EQ_EXPR:
+     case NE_EXPR:
+       if (tree_int_cst_lt (cstr, lhs_min)
+ 	  || tree_int_cst_lt (lhs_max, cstr))
+ 	{
+ 	  *result = (cmp == NE_EXPR);
+ 	  return true;
+        	}
+       return false;
+ 
+     case LT_EXPR:
+       if (tree_int_cst_compare (cstr, lhs_min) <= 0)
+ 	*result = false;
+       else if (tree_int_cst_compare (lhs_max, cstr) < 0)
+ 	*result = true;
+       else
+ 	return false;
+       return true;
+ 
+     case LE_EXPR:
+       if (tree_int_cst_compare (cstr, lhs_min) < 0)
+ 	*result = false;
+       else if (tree_int_cst_compare (lhs_max, cstr) <= 0)
+ 	*result = true;
+       else
+ 	return false;
+       return true;
+ 
+     case GT_EXPR:
+       if (tree_int_cst_compare (lhs_max, cstr) <= 0)
+ 	*result = false;
+       else if (tree_int_cst_compare (cstr, lhs_min) < 0)
+ 	*result = true;
+       else
+ 	return false;
+       return true;
+ 
+     case GE_EXPR:
+       if (tree_int_cst_compare (lhs_max, cstr) < 0)
+ 	*result = false;
+       else if (tree_int_cst_compare (cstr, lhs_min) <= 0)
+ 	*result = true;
+       else
+ 	return false;
+       return true;
+ 
+     default:
+       return false;
+     }
+ }
+ 
  /* Subroutine of fold_binary.  This routine performs all of the
     transformations that are common to the equality/inequality
     operators (EQ_EXPR and NE_EXPR) and the ordering operators
*************** fold_comparison (enum tree_code code, tr
*** 8038,8046 ****
        tree const2 = arg1;
        tree variable = TREE_OPERAND (arg0, 0);
        tree lhs;
!       int lhs_add;
!       lhs_add = TREE_CODE (arg0) != PLUS_EXPR;
  
        lhs = fold_build2 (lhs_add ? PLUS_EXPR : MINUS_EXPR,
  			 TREE_TYPE (arg1), const2, const1);
        if (TREE_CODE (lhs) == TREE_CODE (arg1)
--- 8133,8147 ----
        tree const2 = arg1;
        tree variable = TREE_OPERAND (arg0, 0);
        tree lhs;
!       int lhs_add = TREE_CODE (arg0) != PLUS_EXPR;
!       bool true_p;
  
+       if (fold_offsetted_comparison_p (TREE_CODE (arg0),
+ 				       const1, code, const2, &true_p))
+ 	return omit_one_operand (boolean_type_node,
+ 				 constant_boolean_node (true_p,
+ 							boolean_type_node),
+ 				 variable);
        lhs = fold_build2 (lhs_add ? PLUS_EXPR : MINUS_EXPR,
  			 TREE_TYPE (arg1), const2, const1);
        if (TREE_CODE (lhs) == TREE_CODE (arg1)
Index: testsuite/gcc.dg/fold-compare-3.c
===================================================================
*** testsuite/gcc.dg/fold-compare-3.c	(revision 0)
--- testsuite/gcc.dg/fold-compare-3.c	(revision 0)
***************
*** 0 ****
--- 1,159 ----
+ /* { dg-do compile } */
+ /* { dg-options "-O2 -fdump-tree-cleanup_cfg1" } */
+ 
+ #include <limits.h>
+ 
+ void this_comparison_is_false (void);
+ void this_comparison_is_true (void);
+ void this_comparison_is_not_decidable (void);
+ 
+ void bla1eq (int var)
+ {
+   if (var + 10 == INT_MIN + 9)
+     this_comparison_is_false ();
+ }
+ 
+ void bla2eq (int var)
+ {
+   if (var + 10 == INT_MIN + 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3eq (int var)
+ {
+   if (var - 10 == INT_MAX - 9)
+     this_comparison_is_false ();
+ }
+ 
+ void bla4eq (int var)
+ {
+   if (var - 10 == INT_MAX - 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla1ne (int var)
+ {
+   if (var + 10 != INT_MIN + 9)
+     this_comparison_is_true ();
+ }
+ 
+ void bla2ne (int var)
+ {
+   if (var + 10 != INT_MIN + 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3ne (int var)
+ {
+   if (var - 10 != INT_MAX - 9)
+     this_comparison_is_true ();
+ }
+ 
+ void bla4ne (int var)
+ {
+   if (var - 10 != INT_MAX - 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla1lt (int var)
+ {
+   if (var + 10 < INT_MIN + 10)
+     this_comparison_is_false ();
+ }
+ 
+ void bla2lt (int var)
+ {
+   if (var + 10 < INT_MIN + 11)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3lt (int var)
+ {
+   if (var - 10 < INT_MAX - 9)
+     this_comparison_is_true ();
+ }
+ 
+ void bla4lt (int var)
+ {
+   if (var - 10 < INT_MAX - 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla1le (int var)
+ {
+   if (var + 10 <= INT_MIN + 9)
+     this_comparison_is_false ();
+ }
+ 
+ void bla2le (int var)
+ {
+   if (var + 10 <= INT_MIN + 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3le (int var)
+ {
+   if (var - 10 <= INT_MAX - 10)
+     this_comparison_is_true ();
+ }
+ 
+ void bla4le (int var)
+ {
+   if (var - 10 <= INT_MAX - 11)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla1gt (int var)
+ {
+   if (var + 10 > INT_MIN + 9)
+     this_comparison_is_true ();
+ }
+ 
+ void bla2gt (int var)
+ {
+   if (var + 10 > INT_MIN + 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3gt (int var)
+ {
+   if (var - 10 > INT_MAX - 10)
+     this_comparison_is_false ();
+ }
+ 
+ void bla4gt (int var)
+ {
+   if (var - 10 > INT_MAX - 11)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla1ge (int var)
+ {
+   if (var + 10 >= INT_MIN + 10)
+     this_comparison_is_true ();
+ }
+ 
+ void bla2ge (int var)
+ {
+   if (var + 10 >= INT_MIN + 11)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ void bla3ge (int var)
+ {
+   if (var - 11 >= INT_MAX - 10)
+     this_comparison_is_false ();
+ }
+ 
+ void bla4ge (int var)
+ {
+   if (var - 10 >= INT_MAX - 10)
+     this_comparison_is_not_decidable ();
+ }
+ 
+ /* { dg-final { scan-tree-dump-times "this_comparison_is_false" 0 "cleanup_cfg1" } } */
+ /* { dg-final { scan-tree-dump-times "this_comparison_is_true" 6 "cleanup_cfg1" } } */
+ /* { dg-final { scan-tree-dump-times "this_comparison_is_not_decidable" 12 "cleanup_cfg1" } } */
+ /* { dg-final { scan-tree-dump-times "if " 12 "cleanup_cfg1" } } */
+ 
+ /* { dg-final { cleanup-tree-dump "cleanup_cfg1" } } */