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] Canonicalize comparisons, fix PR26899


This patch adds comparison canonicalization to fold_comparison.
Specifically we canonicalize to comparison codes which involve
the smallest constant like for example i - 1 < j to i <= j.

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

Ok for mainline?

Thanks,
Richard.

:ADDPATCH middle-end:

2006-10-24  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 118026)
--- fold-const.c	(working copy)
*************** fold_minmax (enum tree_code code, tree t
*** 7749,7754 ****
--- 7749,7873 ----
    return NULL_TREE;
  }
  
+ /* Helper that tries to canonicalize the comparison *ARG0P *CODEP arg1
+    by changing *CODEP to reduce the magnitude of constants involved in
+    the comparison.  Sets *SWAPP to true if *ARG0P and arg1 should be
+    swapped for the canonical form.
+    Returns true, if changes to *ARG0P, *CODEP or *SWAPP were made and
+    false if no simplification could be made.  */
+ 
+ static bool
+ maybe_canonicalize_comparison_1 (enum tree_code *codep,
+ 				 tree *arg0p, bool *swapp)
+ {
+   enum tree_code code0 = TREE_CODE (*arg0p), code = *codep;
+   tree cst0 = NULL_TREE, arg0 = *arg0p;
+   int sgn0;
+ 
+   /* Match A +- CST code arg1 and CST code arg1.  */
+   if (!(((code0 == MINUS_EXPR
+           || code0 == PLUS_EXPR)
+          && TREE_CODE (TREE_OPERAND (arg0, 1)) == INTEGER_CST
+ 	 && !TREE_OVERFLOW (TREE_OPERAND (arg0, 1)))
+ 	|| (code0 == INTEGER_CST
+ 	    && !TREE_OVERFLOW (arg0)
+ 	    && !integer_zerop (arg0))))
+     return false;
+ 
+   if (code0 == INTEGER_CST)
+     cst0 = arg0;
+   else
+     cst0 = TREE_OPERAND (arg0, 1);
+   sgn0 = tree_int_cst_sgn (cst0);
+ 
+   /* CST code B.  */
+   if (code0 == INTEGER_CST)
+     {
+       /* CST <= B  ->  CST-1 < B.  */
+       if (code == LE_EXPR && sgn0 == 1)
+ 	*codep = LT_EXPR;
+       /* -CST < B  ->  -CST-1 <= B.  */
+       else if (code == LT_EXPR && sgn0 == -1)
+ 	*codep = LE_EXPR;
+       /* CST > B  ->  CST-1 >= B.  */
+       else if (code == GT_EXPR && sgn0 == 1)
+ 	*codep = GE_EXPR;
+       /* -CST >= B  ->  -CST-1 > B.  */
+       else if (code == GE_EXPR && sgn0 == -1)
+ 	*codep = GT_EXPR;
+       else
+         return false;
+       *swapp = true;
+     }
+   else
+     {
+       /* A - CST < B  ->  A - CST-1 <= B.  */
+       if (code == LT_EXPR
+ 	  && code0 == ((sgn0 == -1) ? PLUS_EXPR : MINUS_EXPR))
+ 	*codep = LE_EXPR;
+       /* A + CST > B  ->  A + CST-1 >= B.  */
+       else if (code == GT_EXPR
+ 	       && code0 == ((sgn0 == -1) ? MINUS_EXPR : PLUS_EXPR))
+ 	*codep = GE_EXPR;
+       /* A + CST <= B  ->  A + CST-1 < B.  */
+       else if (code == LE_EXPR
+ 	       && code0 == ((sgn0 == -1) ? MINUS_EXPR : PLUS_EXPR))
+ 	*codep = LT_EXPR;
+       /* A - CST >= B  ->  A - CST-1 > B.  */
+       else if (code == GE_EXPR
+ 	       && code0 == ((sgn0 == -1) ? PLUS_EXPR : MINUS_EXPR))
+ 	*codep = GT_EXPR;
+       else
+ 	return false;
+     }
+ 
+   /* 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);
+ 
+   return true;
+ }
+ 
+ /* 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)
+ {
+   bool swap = false;
+ 
+   /* 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;
+ 
+   if (maybe_canonicalize_comparison_1 (&code, &arg0, &swap))
+     {
+       if (swap)
+         return fold_build2 (swap_tree_comparison (code), type, arg1, arg0);
+       return fold_build2 (code, type, arg0, arg1);
+     } 
+ 
+   code = swap_tree_comparison (code);
+   if (maybe_canonicalize_comparison_1 (&code, &arg1, &swap))
+     {
+       if (swap)
+         return fold_build2 (swap_tree_comparison (code), type, arg0, arg1);
+       return fold_build2 (code, type, arg1, arg0);
+     }
+ 
+   return NULL_TREE;
+ }
+ 
  /* 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 ****
--- 7996,8005 ----
  			    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);


/* { dg-do compile } */
/* { 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]