[PATCH] Robustify simplify_truth_ops_using_ranges (PR tree-optimization/37662, PR tree-optimization/37663)

[PATCH] Robustify simplify_truth_ops_using_ranges (PR tree-optimization/37662, PR tree-optimization/37663)

[Jakub Jelinek]

Hi!

The newly added simplify_truth_ops_using_ranges seems to be too fragile,
assumes the first argument must be always a SSA_NAME and only very few
possibilities for the second argument.  The first assumption isn't true
e.g. when ccp or other passes substituted one of the truth op operands
but fab hasn't happened yet to swap the commutative operands to the
preferred order.  The second might happen because of TREE_OVERFLOW prevented
folding, or similar reasons.  It seems only fold and 3 further cases swap
commutative operands, while we could do that in ccp, relying on it in vrp
is too risky.  The patch swaps the operands itself (just in op0/op1
variables) if needed, and bails out if get_value_range would be called on
non-SSA_NAME, furthermore replaces the two gcc_asserts with a conditional
return false.  The patch looks bigger than it really is, most of the changes
are caused by reindentation.

Ok for trunk if bootstrap/regtest succeeds?

2008-09-30  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/37662
	PR tree-optimization/37663
	* tree-vrp.c (simplify_truth_ops_using_ranges): Swap operands if needed
	(and not TRUTH_NOT_EXPR).  Don't call get_value_range with non-SSA_NAME.
	Don't assert operands have been folded, instead just bail out.

	* gcc.c-torture/compile/pr37662.c: New test.
	* gcc.dg/pr37663.c: New test.

--- gcc/tree-vrp.c.jj	2008-09-16 16:50:49.000000000 +0200
+++ gcc/tree-vrp.c	2008-09-30 13:50:58.000000000 +0200
@@ -6304,9 +6304,27 @@ simplify_truth_ops_using_ranges (gimple_
   bool need_conversion;
 
   op0 = gimple_assign_rhs1 (stmt);
-  vr = get_value_range (op0);
+  if (rhs_code == TRUTH_NOT_EXPR)
+    {
+      rhs_code = NE_EXPR;
+      op1 = build_int_cst (TREE_TYPE (op0), 1);
+    }
+  else
+    {
+      op1 = gimple_assign_rhs2 (stmt);
+      if (tree_swap_operands_p (op0, op1, true))
+	{
+	  op0 = op1;
+	  op1 = gimple_assign_rhs1 (stmt);
+	}
+    }
+
   if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
     {
+      if (TREE_CODE (op0) != SSA_NAME)
+	return false;
+      vr = get_value_range (op0);
+
       val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
       if (!val || !integer_onep (val))
         return false;
@@ -6316,48 +6334,46 @@ simplify_truth_ops_using_ranges (gimple_
         return false;
     }
 
-  if (rhs_code == TRUTH_NOT_EXPR)
+  /* Reduce number of cases to handle.  */
+  if (is_gimple_min_invariant (op1))
     {
-      rhs_code = NE_EXPR;
-      op1 = build_int_cst (TREE_TYPE (op0), 1);
+      /* Exclude anything that should have been already folded.  */
+      if (rhs_code != EQ_EXPR
+	  && rhs_code != NE_EXPR
+	  && rhs_code != TRUTH_XOR_EXPR)
+	return false;
+
+      if (!integer_zerop (op1)
+	  && !integer_onep (op1)
+	  && !integer_all_onesp (op1))
+	return false;
+
+      /* Limit the number of cases we have to consider.  */
+      if (rhs_code == EQ_EXPR)
+	{
+	  rhs_code = NE_EXPR;
+	  op1 = fold_unary (TRUTH_NOT_EXPR, TREE_TYPE (op1), op1);
+	}
     }
   else
     {
-      op1 = gimple_assign_rhs2 (stmt);
+      /* Punt on A == B as there is no BIT_XNOR_EXPR.  */
+      if (rhs_code == EQ_EXPR)
+	return false;
 
-      /* Reduce number of cases to handle.  */
-      if (is_gimple_min_invariant (op1))
+      if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
 	{
-          /* Exclude anything that should have been already folded.  */
-	  gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR
-		      || rhs_code == TRUTH_XOR_EXPR);
-	  gcc_assert (integer_zerop (op1) || integer_onep (op1)
-		      || integer_all_onesp (op1));
+	  if (TREE_CODE (op1) != SSA_NAME)
+	    return false;
+	  vr = get_value_range (op1);
 
-	  /* Limit the number of cases we have to consider.  */
-	  if (rhs_code == EQ_EXPR)
-	    {
-	      rhs_code = NE_EXPR;
-	      op1 = fold_unary (TRUTH_NOT_EXPR, TREE_TYPE (op1), op1);
-	    }
-	}
-      else
-	{
-	  /* Punt on A == B as there is no BIT_XNOR_EXPR.  */
-	  if (rhs_code == EQ_EXPR)
+	  val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+	  if (!val || !integer_onep (val))
 	    return false;
 
-	  if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
-	    {
-	      vr = get_value_range (op1);
-	      val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
-	      if (!val || !integer_onep (val))
-	        return false;
-
-	      val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
-	      if (!val || !integer_onep (val))
-	        return false;
-	    }
+	  val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+	  if (!val || !integer_onep (val))
+	    return false;
 	}
     }
 
--- gcc/testsuite/gcc.c-torture/compile/pr37662.c.jj	2008-09-30 13:57:08.000000000 +0200
+++ gcc/testsuite/gcc.c-torture/compile/pr37662.c	2008-09-30 13:56:08.000000000 +0200
@@ -0,0 +1,15 @@
+/* PR tree-optimization/37662 */
+
+extern int baz (void);
+
+static int
+foo (void)
+{
+  return 1;
+}
+
+int
+bar (void)
+{
+  return foo () >= 1 ^ (baz () || 0) || 0;
+}
--- gcc/testsuite/gcc.dg/pr37663.c.jj	2008-09-30 13:56:43.000000000 +0200
+++ gcc/testsuite/gcc.dg/pr37663.c	2008-09-30 13:55:33.000000000 +0200
@@ -0,0 +1,15 @@
+/* PR tree-optimization/37663 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fwrapv" } */
+
+extern void bar (void);
+
+void
+foo (int x)
+{
+  x = 1 >= x;
+  int y = -1885403717;
+  x = x + (x != y * y);
+  if (x)
+    bar ();
+}

	Jakub

Re: [PATCH] Robustify simplify_truth_ops_using_ranges (PR tree-optimization/37662, PR tree-optimization/37663)

[Richard Guenther]

On Tue, Sep 30, 2008 at 3:03 PM, Jakub Jelinek <jakub@redhat.com> wrote:
> Hi!
>
> The newly added simplify_truth_ops_using_ranges seems to be too fragile,
> assumes the first argument must be always a SSA_NAME and only very few
> possibilities for the second argument.  The first assumption isn't true
> e.g. when ccp or other passes substituted one of the truth op operands
> but fab hasn't happened yet to swap the commutative operands to the
> preferred order.  The second might happen because of TREE_OVERFLOW prevented
> folding, or similar reasons.  It seems only fold and 3 further cases swap
> commutative operands, while we could do that in ccp, relying on it in vrp
> is too risky.  The patch swaps the operands itself (just in op0/op1
> variables) if needed, and bails out if get_value_range would be called on
> non-SSA_NAME, furthermore replaces the two gcc_asserts with a conditional
> return false.  The patch looks bigger than it really is, most of the changes
> are caused by reindentation.
>
> Ok for trunk if bootstrap/regtest succeeds?

Ok.

Thanks,
Richard.

> 2008-09-30  Jakub Jelinek  <jakub@redhat.com>
>
>        PR tree-optimization/37662
>        PR tree-optimization/37663
>        * tree-vrp.c (simplify_truth_ops_using_ranges): Swap operands if needed
>        (and not TRUTH_NOT_EXPR).  Don't call get_value_range with non-SSA_NAME.
>        Don't assert operands have been folded, instead just bail out.
>
>        * gcc.c-torture/compile/pr37662.c: New test.
>        * gcc.dg/pr37663.c: New test.
>
> --- gcc/tree-vrp.c.jj   2008-09-16 16:50:49.000000000 +0200
> +++ gcc/tree-vrp.c      2008-09-30 13:50:58.000000000 +0200
> @@ -6304,9 +6304,27 @@ simplify_truth_ops_using_ranges (gimple_
>   bool need_conversion;
>
>   op0 = gimple_assign_rhs1 (stmt);
> -  vr = get_value_range (op0);
> +  if (rhs_code == TRUTH_NOT_EXPR)
> +    {
> +      rhs_code = NE_EXPR;
> +      op1 = build_int_cst (TREE_TYPE (op0), 1);
> +    }
> +  else
> +    {
> +      op1 = gimple_assign_rhs2 (stmt);
> +      if (tree_swap_operands_p (op0, op1, true))
> +       {
> +         op0 = op1;
> +         op1 = gimple_assign_rhs1 (stmt);
> +       }
> +    }
> +
>   if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
>     {
> +      if (TREE_CODE (op0) != SSA_NAME)
> +       return false;
> +      vr = get_value_range (op0);
> +
>       val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
>       if (!val || !integer_onep (val))
>         return false;
> @@ -6316,48 +6334,46 @@ simplify_truth_ops_using_ranges (gimple_
>         return false;
>     }
>
> -  if (rhs_code == TRUTH_NOT_EXPR)
> +  /* Reduce number of cases to handle.  */
> +  if (is_gimple_min_invariant (op1))
>     {
> -      rhs_code = NE_EXPR;
> -      op1 = build_int_cst (TREE_TYPE (op0), 1);
> +      /* Exclude anything that should have been already folded.  */
> +      if (rhs_code != EQ_EXPR
> +         && rhs_code != NE_EXPR
> +         && rhs_code != TRUTH_XOR_EXPR)
> +       return false;
> +
> +      if (!integer_zerop (op1)
> +         && !integer_onep (op1)
> +         && !integer_all_onesp (op1))
> +       return false;
> +
> +      /* Limit the number of cases we have to consider.  */
> +      if (rhs_code == EQ_EXPR)
> +       {
> +         rhs_code = NE_EXPR;
> +         op1 = fold_unary (TRUTH_NOT_EXPR, TREE_TYPE (op1), op1);
> +       }
>     }
>   else
>     {
> -      op1 = gimple_assign_rhs2 (stmt);
> +      /* Punt on A == B as there is no BIT_XNOR_EXPR.  */
> +      if (rhs_code == EQ_EXPR)
> +       return false;
>
> -      /* Reduce number of cases to handle.  */
> -      if (is_gimple_min_invariant (op1))
> +      if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
>        {
> -          /* Exclude anything that should have been already folded.  */
> -         gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR
> -                     || rhs_code == TRUTH_XOR_EXPR);
> -         gcc_assert (integer_zerop (op1) || integer_onep (op1)
> -                     || integer_all_onesp (op1));
> +         if (TREE_CODE (op1) != SSA_NAME)
> +           return false;
> +         vr = get_value_range (op1);
>
> -         /* Limit the number of cases we have to consider.  */
> -         if (rhs_code == EQ_EXPR)
> -           {
> -             rhs_code = NE_EXPR;
> -             op1 = fold_unary (TRUTH_NOT_EXPR, TREE_TYPE (op1), op1);
> -           }
> -       }
> -      else
> -       {
> -         /* Punt on A == B as there is no BIT_XNOR_EXPR.  */
> -         if (rhs_code == EQ_EXPR)
> +         val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> +         if (!val || !integer_onep (val))
>            return false;
>
> -         if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
> -           {
> -             vr = get_value_range (op1);
> -             val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
> -             if (!val || !integer_onep (val))
> -               return false;
> -
> -             val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> -             if (!val || !integer_onep (val))
> -               return false;
> -           }
> +         val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
> +         if (!val || !integer_onep (val))
> +           return false;
>        }
>     }
>
> --- gcc/testsuite/gcc.c-torture/compile/pr37662.c.jj    2008-09-30 13:57:08.000000000 +0200
> +++ gcc/testsuite/gcc.c-torture/compile/pr37662.c       2008-09-30 13:56:08.000000000 +0200
> @@ -0,0 +1,15 @@
> +/* PR tree-optimization/37662 */
> +
> +extern int baz (void);
> +
> +static int
> +foo (void)
> +{
> +  return 1;
> +}
> +
> +int
> +bar (void)
> +{
> +  return foo () >= 1 ^ (baz () || 0) || 0;
> +}
> --- gcc/testsuite/gcc.dg/pr37663.c.jj   2008-09-30 13:56:43.000000000 +0200
> +++ gcc/testsuite/gcc.dg/pr37663.c      2008-09-30 13:55:33.000000000 +0200
> @@ -0,0 +1,15 @@
> +/* PR tree-optimization/37663 */
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fwrapv" } */
> +
> +extern void bar (void);
> +
> +void
> +foo (int x)
> +{
> +  x = 1 >= x;
> +  int y = -1885403717;
> +  x = x + (x != y * y);
> +  if (x)
> +    bar ();
> +}
>
>        Jakub
>

Re: [PATCH] Robustify simplify_truth_ops_using_ranges (PR tree-optimization/37662, PR tree-optimization/37663)

[Paolo Bonzini]

[-- Attachment #1: Type: text/plain, Size: 2824 bytes --]

Jakub Jelinek wrote:
> Hi!
> 
> The newly added simplify_truth_ops_using_ranges seems to be too fragile,
> assumes the first argument must be always a SSA_NAME and only very few
> possibilities for the second argument.  The first assumption isn't true
> e.g. when ccp or other passes substituted one of the truth op operands
> but fab hasn't happened yet to swap the commutative operands to the
> preferred order.

First of all, thanks for this patch -- my comments aren't meant to bash
your work.

However, it does not feel right to have stuff not canonicalized,
especially on trees where we don't have the complication of recursive
data structures as is the case on RTL.

Indeed, my impression that something wrong is happening in
fold_gimple_assign, which has this:

      if (!result)
        result = fold_binary (subcode,
                              TREE_TYPE (gimple_assign_lhs (stmt)),
                              gimple_assign_rhs1 (stmt),
                              gimple_assign_rhs2 (stmt));

is easily confirmed.  The reason for this bug is that we do not try
harder to make valid GIMPLE if fold_binary produces something like this:

  (int) !(_Bool) D.1242_4;

And the attached patch fixes the root cause of the problem.

> The second might happen because of TREE_OVERFLOW prevented
> folding, or similar reasons.

Again, what are the "similar reasons"?  I hadn't thought of
TREE_OVERFLOW, which is basically the only case in which GCC can do some
kind of handwaving, and in this case simplify_truth_ops_using_ranges
should indeed bail out.  However, in "normal" cases the asserts should
not trigger, or some important optimization might have been missed
somewhere else.

If X is in [0,1], and vrp_evaluate_conditional (via fold_predicate_in)
does not fold X == 2, there is something wrong going on.  Such a
conditional should *never* reach simplify_truth_ops_using_ranges except
for *very special* reasons such as TREE_OVERFLOW.  Given the sheer
amount of changed code in 4.3/4.4 in very complex code as
CCP/VRP/tree-ssa-propagate.c due to tuplification, it's better to be
defensive.  (Even the integer_all_onesp (op1) condition should be IMO
written as

  integer_all_onesp (op1) && TYPE_PRECISION (TREE_TYPE (op1) == 1))

i.e. even stricter, because it can only happen for signed bitfields).

Later on in the release I'd be okay with something even harder like
Jakub's patch, i.e. assuming canonicalization and bailing out if the
assumption is not verified (instead of working around bugs).  But right
now I think that this is just highlighting a downright bug in *all*
passes using fold_stmt.  It might be more dangerous to fix it in 4.3,
and I'm not proposing the patch for the branch, but I think that for 4.4
the correct fix is the attached one (untested apart from the two PR
testcases).

Paolo

[-- Attachment #2: pr37662-3.patch --]
[-- Type: text/plain, Size: 1660 bytes --]

2008-09-30  Paolo Bonzini  <bonzini@gnu.org>

	PR tree-optimization/37662
	* tree-ssa-ccp.c (fold_gimple_assign): Ensure commutative tree
	codes are canonicalized properly.

	PR tree-optimization/37663
	* tree-vrp.c (simplify_truth_ops_using_ranges): Bail out on
	TREE_OVERFLOW operands.

Index: tree-ssa-ccp.c
===================================================================
--- tree-ssa-ccp.c	(revision 140778)
+++ tree-ssa-ccp.c	(working copy)
@@ -2711,6 +2711,17 @@ fold_gimple_assign (gimple_stmt_iterator
           STRIP_USELESS_TYPE_CONVERSION (result);
           if (valid_gimple_rhs_p (result))
 	    return result;
+
+	  /* Fold might have produced non-GIMPLE, so if we trust it blindly
+	     we lose canonicalization opportunities.  Do not go again
+	     through fold here though, or the same non-GIMPLE will be
+	     produced.  */
+          if (commutative_tree_code (subcode)
+              && tree_swap_operands_p (gimple_assign_rhs1 (stmt),
+                                       gimple_assign_rhs2 (stmt), false))
+            return build2 (subcode, TREE_TYPE (gimple_assign_lhs (stmt)),
+                           gimple_assign_rhs2 (stmt),
+                           gimple_assign_rhs1 (stmt));
         }
       break;
 
Index: tree-vrp.c
===================================================================
--- tree-vrp.c	(revision 140778)
+++ tree-vrp.c	(working copy)
@@ -6324,6 +6324,8 @@ simplify_truth_ops_using_ranges (gimple_
   else
     {
       op1 = gimple_assign_rhs2 (stmt);
+      if (TREE_OVERFLOW (op1))
+	return false;
 
       /* Reduce number of cases to handle.  */
       if (is_gimple_min_invariant (op1))

Re: [PATCH] Robustify simplify_truth_ops_using_ranges (PR tree-optimization/37662, PR tree-optimization/37663)

[Jakub Jelinek]

On Tue, Sep 30, 2008 at 03:53:05PM +0200, Paolo Bonzini wrote:
> Jakub Jelinek wrote:
> > The newly added simplify_truth_ops_using_ranges seems to be too fragile,
> > assumes the first argument must be always a SSA_NAME and only very few
> > possibilities for the second argument.  The first assumption isn't true
> > e.g. when ccp or other passes substituted one of the truth op operands
> > but fab hasn't happened yet to swap the commutative operands to the
> > preferred order.
> 
> First of all, thanks for this patch -- my comments aren't meant to bash
> your work.

As we talked on IRC, your fold_gimple_assign change looks good, and in
that case it doesn't make much sense to play with tree_swap_operands_p
in the tree-vrp.c case.

So here is an updated patch which I'll bootstrap/regtest together with
your fold_gimple_assign change.

2008-09-30  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/37662
	PR tree-optimization/37663
	* tree-vrp.c (simplify_truth_ops_using_ranges): Don't call
	get_value_range with non-SSA_NAME.  Don't assert operands have been
	folded, instead just bail out.

	* gcc.c-torture/compile/pr37662.c: New test.
	* gcc.dg/pr37663.c: New test.

--- gcc/tree-vrp.c.jj	2008-09-16 16:50:49.000000000 +0200
+++ gcc/tree-vrp.c	2008-09-30 16:22:40.000000000 +0200
@@ -6304,9 +6304,12 @@ simplify_truth_ops_using_ranges (gimple_
   bool need_conversion;
 
   op0 = gimple_assign_rhs1 (stmt);
-  vr = get_value_range (op0);
   if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
     {
+      if (TREE_CODE (op0) != SSA_NAME)
+	return false;
+      vr = get_value_range (op0);
+
       val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
       if (!val || !integer_onep (val))
         return false;
@@ -6329,10 +6332,15 @@ simplify_truth_ops_using_ranges (gimple_
       if (is_gimple_min_invariant (op1))
 	{
           /* Exclude anything that should have been already folded.  */
-	  gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR
-		      || rhs_code == TRUTH_XOR_EXPR);
-	  gcc_assert (integer_zerop (op1) || integer_onep (op1)
-		      || integer_all_onesp (op1));
+	  if (rhs_code != EQ_EXPR
+	      && rhs_code != NE_EXPR
+	      && rhs_code != TRUTH_XOR_EXPR)
+	    return false;
+
+	  if (!integer_zerop (op1)
+	      && !integer_onep (op1)
+	      && !integer_all_onesp (op1))
+	    return false;
 
 	  /* Limit the number of cases we have to consider.  */
 	  if (rhs_code == EQ_EXPR)
@@ -6349,7 +6357,10 @@ simplify_truth_ops_using_ranges (gimple_
 
 	  if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
 	    {
+	      if (TREE_CODE (op1) != SSA_NAME)
+		return false;
 	      vr = get_value_range (op1);
+
 	      val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
 	      if (!val || !integer_onep (val))
 	        return false;
--- gcc/testsuite/gcc.c-torture/compile/pr37662.c.jj	2008-09-30 13:57:08.000000000 +0200
+++ gcc/testsuite/gcc.c-torture/compile/pr37662.c	2008-09-30 13:56:08.000000000 +0200
@@ -0,0 +1,15 @@
+/* PR tree-optimization/37662 */
+
+extern int baz (void);
+
+static int
+foo (void)
+{
+  return 1;
+}
+
+int
+bar (void)
+{
+  return foo () >= 1 ^ (baz () || 0) || 0;
+}
--- gcc/testsuite/gcc.dg/pr37663.c.jj	2008-09-30 13:56:43.000000000 +0200
+++ gcc/testsuite/gcc.dg/pr37663.c	2008-09-30 13:55:33.000000000 +0200
@@ -0,0 +1,15 @@
+/* PR tree-optimization/37663 */
+/* { dg-do compile } */
+/* { dg-options "-O2 -fwrapv" } */
+
+extern void bar (void);
+
+void
+foo (int x)
+{
+  x = 1 >= x;
+  int y = -1885403717;
+  x = x + (x != y * y);
+  if (x)
+    bar ();
+}


	Jakub