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]

Re: [PATCH] Canonicalize comparisons, fix PR26899


On Fri, 27 Oct 2006, Roger Sayle wrote:

> 
> Hi Richard,
> 
> On Wed, 25 Oct 2006, Richard Guenther wrote:
> > +       /* CST <= B  ->  CST-1 < B.  */
> > +       /* A - CST < B  ->  A - CST-1 <= B.  */
> > ...
> > +   /* Now build the reduced constant.  */
> > +   *arg0p = int_const_binop (sgn0 == -1 ? PLUS_EXPR : MINUS_EXPR, cst0,
> > + 			    build_int_cst (TREE_TYPE (cst0), 1), 0);
> > +   if (code0 != INTEGER_CST)
> > +     *arg0p = fold_build2 (code0, TREE_TYPE (arg0),
> > + 			  TREE_OPERAND (arg0, 0), *arg0p);
> 
> I think there's an potential problem here that you're not checking
> whether the CST-1 operation overflowed.  For example, "INT_MIN <= x"
> would be transformed into "INT_MAX' < x".  Of course, a more realistic
> example, is "A - INT_MIN < B"...  I think adding a simple
> TREE_OVERFLOW test after the call to int_const_binop should be
> sufficient.

The CST +- 1 operation cannot overflow, as it is assured perviously that
CST is not zero and CST will decrease in magnitude by the constant
adjustment (otherwise the transformation would be invalid as it might
introduce undefined overflow).  I reworked the initial check and added
some comments to clarify this

> It might also be possible to tidy up the maybe_canonicalize_comparison
> <-> maybe_canonicalize_comparison_1 API a little bit.  The large use
> of pointer indirection in maybe_canonicalize_comparison_1 looks a bit
> ugly.  One approach might be to pass in a swapped flag and both arguments
> form maybe_canonicalize_comparison, and then return a tree if anything
> changed.

and reworked the patch according to this suggestion.  It indeed looks
cleaner this way.

Bootstrapped and tested on x86_64-unknown-linux-gnu.

Ok for mainline?
Thanks,
Richard.

2006-10-28  Richard Guenther  <rguenther@suse.de>

	PR middle-end/26899
	* fold-const.c (maybe_canonicalize_comparison_1): Helper
	for maybe_canonicalize_comparison.
	(maybe_canonicalize_comparison): New function for canonicalizing
	comparison trees.
	(fold_comparison): Call it to canonicalize comparisons with
	constants involved.

	* gcc.dg/tree-ssa/pr26899.c: New testcase.

Index: fold-const.c
===================================================================
*** fold-const.c	(revision 118105)
--- fold-const.c	(working copy)
*************** fold_minmax (enum tree_code code, tree t
*** 7749,7754 ****
--- 7749,7874 ----
    return NULL_TREE;
  }
  
+ /* Helper that tries to canonicalize the comparison ARG0 CODE ARG1
+    by changing CODE to reduce the magnitude of constants involved in
+    ARG0 of the comparison.
+    Returns a canonicalized comparison tree if a simplification was
+    possible, otherwise returns NULL_TREE.  */
+ 
+ static tree
+ maybe_canonicalize_comparison_1 (enum tree_code code, tree type,
+ 				 tree arg0, tree arg1)
+ {
+   enum tree_code code0 = TREE_CODE (arg0);
+   tree t, cst0 = NULL_TREE;
+   int sgn0;
+   bool swap = false;
+ 
+   /* Match A +- CST code arg1 and CST code arg1.  */
+   if (!(((code0 == MINUS_EXPR
+           || code0 == PLUS_EXPR)
+          && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST)
+ 	|| code0 == INTEGER_CST))
+     return NULL_TREE;
+ 
+   /* Identify the constant in arg0 and its sign.  */
+   if (code0 == INTEGER_CST)
+     cst0 = arg0;
+   else
+     cst0 = TREE_OPERAND (arg0, 1);
+   sgn0 = tree_int_cst_sgn (cst0);
+ 
+   /* Overflowed constants and zero will cause problems.  */
+   if (integer_zerop (cst0)
+       || TREE_OVERFLOW (cst0))
+     return NULL_TREE;
+ 
+   /* See if we can reduce the mangitude of the constant in
+      arg0 by changing the comparison code.  */
+   if (code0 == INTEGER_CST)
+     {
+       /* CST <= arg1  ->  CST-1 < arg1.  */
+       if (code == LE_EXPR && sgn0 == 1)
+ 	code = LT_EXPR;
+       /* -CST < arg1  ->  -CST-1 <= arg1.  */
+       else if (code == LT_EXPR && sgn0 == -1)
+ 	code = LE_EXPR;
+       /* CST > arg1  ->  CST-1 >= arg1.  */
+       else if (code == GT_EXPR && sgn0 == 1)
+ 	code = GE_EXPR;
+       /* -CST >= arg1  ->  -CST-1 > arg1.  */
+       else if (code == GE_EXPR && sgn0 == -1)
+ 	code = GT_EXPR;
+       else
+         return NULL_TREE;
+       /* arg1 code' CST' might be more canonical.  */
+       swap = true;
+     }
+   else
+     {
+       /* A - CST < arg1  ->  A - CST-1 <= arg1.  */
+       if (code == LT_EXPR
+ 	  && code0 == ((sgn0 == -1) ? PLUS_EXPR : MINUS_EXPR))
+ 	code = LE_EXPR;
+       /* A + CST > arg1  ->  A + CST-1 >= arg1.  */
+       else if (code == GT_EXPR
+ 	       && code0 == ((sgn0 == -1) ? MINUS_EXPR : PLUS_EXPR))
+ 	code = GE_EXPR;
+       /* A + CST <= arg1  ->  A + CST-1 < arg1.  */
+       else if (code == LE_EXPR
+ 	       && code0 == ((sgn0 == -1) ? MINUS_EXPR : PLUS_EXPR))
+ 	code = LT_EXPR;
+       /* A - CST >= arg1  ->  A - CST-1 > arg1.  */
+       else if (code == GE_EXPR
+ 	       && code0 == ((sgn0 == -1) ? PLUS_EXPR : MINUS_EXPR))
+ 	code = GT_EXPR;
+       else
+ 	return NULL_TREE;
+     }
+ 
+   /* Now build the constant reduced in magnitude.  */
+   t = int_const_binop (sgn0 == -1 ? PLUS_EXPR : MINUS_EXPR,
+   		       cst0, build_int_cst (TREE_TYPE (cst0), 1), 0);
+   if (code0 != INTEGER_CST)
+     t = fold_build2 (code0, TREE_TYPE (arg0), TREE_OPERAND (arg0, 0), t);
+ 
+   /* If swapping might yield to a more canonical form, do so.  */
+   if (swap)
+     return fold_build2 (swap_tree_comparison (code), type, arg1, t);
+   else
+     return fold_build2 (code, type, t, arg1);
+ }
+ 
+ /* Canonicalize the comparison ARG0 CODE ARG1 with type TYPE with undefined
+    overflow further.  Try to decrease the magnitude of constants involved
+    by changing LE_EXPR and GE_EXPR to LT_EXPR and GT_EXPR or vice versa
+    and put sole constants at the second argument position.
+    Returns the canonicalized tree if changed, otherwise NULL_TREE.  */
+ 
+ static tree
+ maybe_canonicalize_comparison (enum tree_code code, tree type,
+ 			       tree arg0, tree arg1)
+ {
+   tree t;
+ 
+   /* In principle pointers also have undefined overflow behavior,
+      but that causes problems elsewhere.  */
+   if ((flag_wrapv || flag_trapv)
+       || (TYPE_UNSIGNED (TREE_TYPE (arg0))
+ 	  && !POINTER_TYPE_P (TREE_TYPE (arg0))))
+     return NULL_TREE;
+ 
+   /* Try canonicalization by simplifying arg0.  */
+   t = maybe_canonicalize_comparison_1 (code, type, arg0, arg1);
+   if (t)
+     return t;
+ 
+   /* Try canonicalization by simplifying arg1 using the swapped
+      comparsion.  */
+   code = swap_tree_comparison (code);
+   return maybe_canonicalize_comparison_1 (code, type, arg1, arg0);
+ }
+ 
  /* 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
*** 7877,7882 ****
--- 7997,8006 ----
  			    variable2);
      }
  
+   tem = maybe_canonicalize_comparison (code, type, arg0, arg1);
+   if (tem)
+     return tem;
+ 
    if (FLOAT_TYPE_P (TREE_TYPE (arg0)))
      {
        tree targ0 = strip_float_extensions (arg0);
Index: testsuite/gcc.dg/tree-ssa/pr26899.c
===================================================================
*** testsuite/gcc.dg/tree-ssa/pr26899.c	(revision 0)
--- testsuite/gcc.dg/tree-ssa/pr26899.c	(revision 0)
***************
*** 0 ****
--- 1,10 ----
+ /* { dg-options "-fdump-tree-gimple" } */
+ 
+ int foo (int i, int j)
+ {
+   return (i < j + 1) || (j > i - 1);
+ }
+ 
+ /* { dg-final { scan-tree-dump "j >= i" "gimple" } } */
+ /* { dg-final { cleanup-tree-dump "gimple" } } */
+ 


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