[RFA] Improve VRP of COND_EXPR_CONDs

Submitted by Jeff Law on April 6, 2013, 12:48 p.m.

Details

Message ID 516019AE.1050103@redhat.com
State New
Headers show

Commit Message

Jeff Law April 6, 2013, 12:48 p.m.
Given something like this:

  <bb 6>:
   _23 = changed_17 ^ 1;
   _12 = (_Bool) _23;
   if (_12 != 0)
     goto <bb 10>;
   else
     goto <bb 7>;

Assume _23 and changed_17 have integer types wider than a boolean, but 
VRP has determined they have a range [0..1].

We should be turning that into:

  <bb 6>:
   _23 = changed_17 ^ 1;
   _12 = (_Bool) _23;
   if (_23 != 0)
     goto <bb 10>;
   else
     goto <bb 7>;

Note the change in the conditional.  This also makes the statement
_12 = (_Bool) _23 dead which should be eliminated by DCE.

This kind of thing happens regularly in GCC itself and is fixed by the 
attached patch.

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

OK for the trunk?
commit fd82eea6f208bb12646e0e0e307fb86f043c1649
Author: Jeff Law <law@redhat.com>
Date:   Sat Apr 6 06:46:58 2013 -0600

           * tree-vrp.c (simplify_cond_using_ranges): Simplify test of boolean
           when the boolean was created by converting a wider object which
           had a boolean range.
    
            * gcc.dg/tree-ssa/vrp87.c: New test

Comments

Steven Bosscher April 6, 2013, 1:08 p.m.
On Sat, Apr 6, 2013 at 2:48 PM, Jeff Law wrote:
>
> Given something like this:

...and the other one from earlier today. Nice finds! :-)

> +  /* If we have a comparison of a SSA_NAME boolean against
> +     a constant (which obviously must be [0..1]).  See if the

"...be [0..1]), see if ..."


> +      if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
> +       {
> +         value_range_t *vr = get_value_range (innerop);
> +

I don't think the SSA_NAME_OCCURS_IN_ABNORMAL_PHI test is necessary,
get_value_range() will simply return a !VR_RANGE.

> +          if (vr->type == VR_RANGE
> +             && operand_equal_p (vr->min, integer_zero_node, 0)
> +             && operand_equal_p (vr->max, integer_one_node, 0))
> +           {

Better use range_int_cst_p(vr) followed by compare_tree_int instead of
operand_equal_p IMHO.

Print something to dump_file?

Ciao!
Steven
Jeff Law April 7, 2013, 2:38 a.m.
On 04/06/2013 07:08 AM, Steven Bosscher wrote:
>
>> +      if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
>> +       {
>> +         value_range_t *vr = get_value_range (innerop);
>> +
>
> I don't think the SSA_NAME_OCCURS_IN_ABNORMAL_PHI test is necessary,
> get_value_range() will simply return a !VR_RANGE.
It's not necessary -- the code was templated from an unsubmitted related 
change to tree-ssa-forwprop where that test is needed.  I'll remove it 
from this change to tree-vrp.c

>
>> +          if (vr->type == VR_RANGE
>> +             && operand_equal_p (vr->min, integer_zero_node, 0)
>> +             && operand_equal_p (vr->max, integer_one_node, 0))
>> +           {
>
> Better use range_int_cst_p(vr) followed by compare_tree_int instead of
> operand_equal_p IMHO.
Seems reasonable.

>
> Print something to dump_file?
Happens via existing machinery.  You'll get a Folded into ... message in 
the detail dumps.  The testcase actually checks for this and also 
verifies the following DCE pass kills the dead code.

jeff
Richard Guenther April 8, 2013, 9:45 a.m.
On Sat, Apr 6, 2013 at 2:48 PM, Jeff Law <law@redhat.com> wrote:
>
> Given something like this:
>
>  <bb 6>:
>   _23 = changed_17 ^ 1;
>   _12 = (_Bool) _23;
>   if (_12 != 0)
>     goto <bb 10>;
>   else
>     goto <bb 7>;
>
> Assume _23 and changed_17 have integer types wider than a boolean, but VRP
> has determined they have a range [0..1].
>
> We should be turning that into:
>
>  <bb 6>:
>   _23 = changed_17 ^ 1;
>   _12 = (_Bool) _23;
>   if (_23 != 0)
>     goto <bb 10>;
>   else
>     goto <bb 7>;
>
> Note the change in the conditional.  This also makes the statement
> _12 = (_Bool) _23 dead which should be eliminated by DCE.
>
> This kind of thing happens regularly in GCC itself and is fixed by the
> attached patch.
>
> Bootstrapped and regression tested on x86_64-unknown-linux-gnu.
>
> OK for the trunk?
>
>
> commit fd82eea6f208bb12646e0e0e307fb86f043c1649
> Author: Jeff Law <law@redhat.com>
> Date:   Sat Apr 6 06:46:58 2013 -0600
>
>            * tree-vrp.c (simplify_cond_using_ranges): Simplify test of
> boolean
>            when the boolean was created by converting a wider object which
>            had a boolean range.
>
>             * gcc.dg/tree-ssa/vrp87.c: New test
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 44797cc..d34ecde 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,5 +1,9 @@
>  2013-04-06  Jeff Law  <law@redhat.com>
>
> +       * tree-vrp.c (simplify_cond_using_ranges): Simplify test of boolean
> +       when the boolean was created by converting a wider object which
> +       had a boolean range.
> +
>         * gimple.c (canonicalize_cond_expr_cond): Rewrite x ^ y into
>         x != y.
>
> diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
> index 601ca66..6ed8af2 100644
> --- a/gcc/testsuite/ChangeLog
> +++ b/gcc/testsuite/ChangeLog
> @@ -1,5 +1,7 @@
>  2013-04-06  Jeff Law  <law@redhat.com>
>
> +       * gcc.dg/tree-ssa/vrp87.c: New test
> +
>         * gcc.dg/tree-ssa/forwprop-25.c: New test
>
>  2013-04-03  Jeff Law  <law@redhat.com>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp87.c
> b/gcc/testsuite/gcc.dg/tree-ssa/vrp87.c
> new file mode 100644
> index 0000000..7feff81
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp87.c
> @@ -0,0 +1,81 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-vrp2-details -fdump-tree-cddce2-details" }
> */
> +
> +struct bitmap_head_def;
> +typedef struct bitmap_head_def *bitmap;
> +typedef const struct bitmap_head_def *const_bitmap;
> +
> +
> +typedef unsigned long BITMAP_WORD;
> +typedef struct bitmap_element_def
> +{
> +  struct bitmap_element_def *next;
> +  unsigned int indx;
> +  BITMAP_WORD bits[((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u))];
> +} bitmap_element;
> +
> +
> +
> +
> +
> +
> +typedef struct bitmap_head_def
> +{
> +  bitmap_element *first;
> +
> +} bitmap_head;
> +
> +
> +
> +static __inline__ unsigned char
> +bitmap_elt_ior (bitmap dst, bitmap_element * dst_elt,
> +               bitmap_element * dst_prev, const bitmap_element * a_elt,
> +               const bitmap_element * b_elt, unsigned char changed)
> +{
> +
> +  if (a_elt)
> +    {
> +
> +      if (!changed && dst_elt)
> +       {
> +         changed = 1;
> +       }
> +    }
> +  else
> +    {
> +      changed = 1;
> +    }
> +  return changed;
> +}
> +
> +unsigned char
> +bitmap_ior_into (bitmap a, const_bitmap b)
> +{
> +  bitmap_element *a_elt = a->first;
> +  const bitmap_element *b_elt = b->first;
> +  bitmap_element *a_prev = ((void *) 0);
> +  unsigned char changed = 0;
> +
> +  while (b_elt)
> +    {
> +
> +      if (!a_elt || a_elt->indx == b_elt->indx)
> +       changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
> +      else if (a_elt->indx > b_elt->indx)
> +       changed = 1;
> +      b_elt = b_elt->next;
> +
> +
> +    }
> +
> +  return changed;
> +}
> +
> +/* Verify that VRP simplified an "if" statement.  */
> +/* { dg-final { scan-tree-dump "Folded into: if.*" "vrp2"} } */
> +/* Verify that DCE after VRP2 eliminates a dead conversion
> +   to a (Bool).  */
> +/* { dg-final { scan-tree-dump "Deleting.*_Bool.*;" "cddce2"} } */
> +/* { dg-final { cleanup-tree-dump "vrp2" } } */
> +/* { dg-final { cleanup-tree-dump "cddce2" } } */
> +
> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
> index 250a506..d76cead 100644
> --- a/gcc/tree-vrp.c
> +++ b/gcc/tree-vrp.c
> @@ -8584,6 +8584,43 @@ simplify_cond_using_ranges (gimple stmt)
>         }
>      }
>
> +  /* If we have a comparison of a SSA_NAME boolean against
> +     a constant (which obviously must be [0..1]).  See if the
> +     SSA_NAME was set by a type conversion where the source
> +     of the conversion is another SSA_NAME with a range [0..1].
> +
> +     If so, we can replace the SSA_NAME in the comparison with
> +     the RHS of the conversion.  This will often make the type
> +     conversion dead code which DCE will clean up.  */
> +  if (TREE_CODE (op0) == SSA_NAME
> +      && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE

Use

       (TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
        || (INTEGRAL_TYPE_P (TREE_TYPE (op0))
            && TYPE_PRECISION (TREE_TYPE (op0)) == 1))

to catch some more cases.

> +      && is_gimple_min_invariant (op1))

In this case it's simpler to test TREE_CODE (op1) == INTEGER_CST.

> +    {
> +      gimple def_stmt = SSA_NAME_DEF_STMT (op0);
> +      tree innerop;
> +
> +      if (!is_gimple_assign (def_stmt)
> +         || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
> +       return false;
> +
> +      innerop = gimple_assign_rhs1 (def_stmt);
> +
> +      if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))

As Steven said, the abnormal check is not necessary, but for completeness
you should check TREE_CODE (innerop) == SSA_NAME.  Valid (but
unfolded) GIMPLE can have (_Bool) 1, too.

> +       {
> +         value_range_t *vr = get_value_range (innerop);
> +
> +          if (vr->type == VR_RANGE
> +             && operand_equal_p (vr->min, integer_zero_node, 0)
> +             && operand_equal_p (vr->max, integer_one_node, 0))
> +           {
> +             tree newconst = fold_convert (TREE_TYPE (innerop), op1);
> +             gimple_cond_set_lhs (stmt, innerop);
> +             gimple_cond_set_rhs (stmt, newconst);
> +             return true;
> +           }
> +       }
> +    }
> +
>    return false;
>  }

Note that we already have code with similar functionality (see if a
conversion would alter the value of X) as part of optimizing
(T1)(T2)X to (T1)X in simplify_conversion_using_ranges.  Maybe
a part of it can be split out and used to simplify conditions for
a bigger range of types than just compares against boolean 0/1.

Richard.

>
Jeff Law April 8, 2013, 1:27 p.m.
On 04/08/2013 03:45 AM, Richard Biener wrote:

>> @@ -8584,6 +8584,43 @@ simplify_cond_using_ranges (gimple stmt)
>>          }
>>       }
>>
>> +  /* If we have a comparison of a SSA_NAME boolean against
>> +     a constant (which obviously must be [0..1]).  See if the
>> +     SSA_NAME was set by a type conversion where the source
>> +     of the conversion is another SSA_NAME with a range [0..1].
>> +
>> +     If so, we can replace the SSA_NAME in the comparison with
>> +     the RHS of the conversion.  This will often make the type
>> +     conversion dead code which DCE will clean up.  */
>> +  if (TREE_CODE (op0) == SSA_NAME
>> +      && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
>
> Use
>
>         (TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
>          || (INTEGRAL_TYPE_P (TREE_TYPE (op0))
>              && TYPE_PRECISION (TREE_TYPE (op0)) == 1))
>
> to catch some more cases.
Good catch.  Done.

>
>> +      && is_gimple_min_invariant (op1))
>
> In this case it's simpler to test TREE_CODE (op1) == INTEGER_CST.
Agreed & fixed.

>
>> +    {
>> +      gimple def_stmt = SSA_NAME_DEF_STMT (op0);
>> +      tree innerop;
>> +
>> +      if (!is_gimple_assign (def_stmt)
>> +         || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
>> +       return false;
>> +
>> +      innerop = gimple_assign_rhs1 (def_stmt);
>> +
>> +      if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
>
> As Steven said, the abnormal check is not necessary, but for completeness
> you should check TREE_CODE (innerop) == SSA_NAME.  Valid (but
> unfolded) GIMPLE can have (_Bool) 1, too.
Agreed & fixed.

>
> Note that we already have code with similar functionality (see if a
> conversion would alter the value of X) as part of optimizing
> (T1)(T2)X to (T1)X in simplify_conversion_using_ranges.  Maybe
> a part of it can be split out and used to simplify conditions for
> a bigger range of types than just compares against boolean 0/1.
That may be a follow-up -- there's still several of these things I'm 
looking at.  I wanted to go ahead and start pushing out those which were 
clearly improvements rather than queue them while I looked at all the 
oddities I'm seeing in the dumps.

jeff
Richard Guenther April 8, 2013, 2:11 p.m.
On Mon, Apr 8, 2013 at 3:27 PM, Jeff Law <law@redhat.com> wrote:
> On 04/08/2013 03:45 AM, Richard Biener wrote:
>
>>> @@ -8584,6 +8584,43 @@ simplify_cond_using_ranges (gimple stmt)
>>>          }
>>>       }
>>>
>>> +  /* If we have a comparison of a SSA_NAME boolean against
>>> +     a constant (which obviously must be [0..1]).  See if the
>>> +     SSA_NAME was set by a type conversion where the source
>>> +     of the conversion is another SSA_NAME with a range [0..1].
>>> +
>>> +     If so, we can replace the SSA_NAME in the comparison with
>>> +     the RHS of the conversion.  This will often make the type
>>> +     conversion dead code which DCE will clean up.  */
>>> +  if (TREE_CODE (op0) == SSA_NAME
>>> +      && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
>>
>>
>> Use
>>
>>         (TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
>>          || (INTEGRAL_TYPE_P (TREE_TYPE (op0))
>>              && TYPE_PRECISION (TREE_TYPE (op0)) == 1))
>>
>> to catch some more cases.
>
> Good catch.  Done.
>
>
>>
>>> +      && is_gimple_min_invariant (op1))
>>
>>
>> In this case it's simpler to test TREE_CODE (op1) == INTEGER_CST.
>
> Agreed & fixed.
>
>
>>
>>> +    {
>>> +      gimple def_stmt = SSA_NAME_DEF_STMT (op0);
>>> +      tree innerop;
>>> +
>>> +      if (!is_gimple_assign (def_stmt)
>>> +         || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
>>> +       return false;
>>> +
>>> +      innerop = gimple_assign_rhs1 (def_stmt);
>>> +
>>> +      if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
>>
>>
>> As Steven said, the abnormal check is not necessary, but for completeness
>> you should check TREE_CODE (innerop) == SSA_NAME.  Valid (but
>> unfolded) GIMPLE can have (_Bool) 1, too.
>
> Agreed & fixed.
>
>
>>
>> Note that we already have code with similar functionality (see if a
>> conversion would alter the value of X) as part of optimizing
>> (T1)(T2)X to (T1)X in simplify_conversion_using_ranges.  Maybe
>> a part of it can be split out and used to simplify conditions for
>> a bigger range of types than just compares against boolean 0/1.
>
> That may be a follow-up -- there's still several of these things I'm looking
> at.  I wanted to go ahead and start pushing out those which were clearly
> improvements rather than queue them while I looked at all the oddities I'm
> seeing in the dumps.

Fine with me.

Richard.

> jeff
>

Patch hide | download patch | download mbox

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 44797cc..d34ecde 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,9 @@ 
 2013-04-06  Jeff Law  <law@redhat.com>
 
+	* tree-vrp.c (simplify_cond_using_ranges): Simplify test of boolean
+	when the boolean was created by converting a wider object which
+	had a boolean range.
+
 	* gimple.c (canonicalize_cond_expr_cond): Rewrite x ^ y into
 	x != y.
 
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 601ca66..6ed8af2 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,5 +1,7 @@ 
 2013-04-06  Jeff Law  <law@redhat.com>
 
+	* gcc.dg/tree-ssa/vrp87.c: New test
+
 	* gcc.dg/tree-ssa/forwprop-25.c: New test
 
 2013-04-03  Jeff Law  <law@redhat.com>
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp87.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp87.c
new file mode 100644
index 0000000..7feff81
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp87.c
@@ -0,0 +1,81 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-vrp2-details -fdump-tree-cddce2-details" } */
+
+struct bitmap_head_def;
+typedef struct bitmap_head_def *bitmap;
+typedef const struct bitmap_head_def *const_bitmap;
+
+
+typedef unsigned long BITMAP_WORD;
+typedef struct bitmap_element_def
+{
+  struct bitmap_element_def *next;
+  unsigned int indx;
+  BITMAP_WORD bits[((128 + (8 * 8 * 1u) - 1) / (8 * 8 * 1u))];
+} bitmap_element;
+
+
+
+
+
+
+typedef struct bitmap_head_def
+{
+  bitmap_element *first;
+
+} bitmap_head;
+
+
+
+static __inline__ unsigned char
+bitmap_elt_ior (bitmap dst, bitmap_element * dst_elt,
+		bitmap_element * dst_prev, const bitmap_element * a_elt,
+		const bitmap_element * b_elt, unsigned char changed)
+{
+
+  if (a_elt)
+    {
+
+      if (!changed && dst_elt)
+	{
+	  changed = 1;
+	}
+    }
+  else
+    {
+      changed = 1;
+    }
+  return changed;
+}
+
+unsigned char
+bitmap_ior_into (bitmap a, const_bitmap b)
+{
+  bitmap_element *a_elt = a->first;
+  const bitmap_element *b_elt = b->first;
+  bitmap_element *a_prev = ((void *) 0);
+  unsigned char changed = 0;
+
+  while (b_elt)
+    {
+
+      if (!a_elt || a_elt->indx == b_elt->indx)
+	changed = bitmap_elt_ior (a, a_elt, a_prev, a_elt, b_elt, changed);
+      else if (a_elt->indx > b_elt->indx)
+	changed = 1;
+      b_elt = b_elt->next;
+
+
+    }
+
+  return changed;
+}
+
+/* Verify that VRP simplified an "if" statement.  */
+/* { dg-final { scan-tree-dump "Folded into: if.*" "vrp2"} } */
+/* Verify that DCE after VRP2 eliminates a dead conversion
+   to a (Bool).  */
+/* { dg-final { scan-tree-dump "Deleting.*_Bool.*;" "cddce2"} } */
+/* { dg-final { cleanup-tree-dump "vrp2" } } */
+/* { dg-final { cleanup-tree-dump "cddce2" } } */
+
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 250a506..d76cead 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -8584,6 +8584,43 @@  simplify_cond_using_ranges (gimple stmt)
 	}
     }
 
+  /* If we have a comparison of a SSA_NAME boolean against
+     a constant (which obviously must be [0..1]).  See if the
+     SSA_NAME was set by a type conversion where the source
+     of the conversion is another SSA_NAME with a range [0..1].
+
+     If so, we can replace the SSA_NAME in the comparison with
+     the RHS of the conversion.  This will often make the type
+     conversion dead code which DCE will clean up.  */
+  if (TREE_CODE (op0) == SSA_NAME
+      && TREE_CODE (TREE_TYPE (op0)) == BOOLEAN_TYPE
+      && is_gimple_min_invariant (op1))
+    {
+      gimple def_stmt = SSA_NAME_DEF_STMT (op0);
+      tree innerop;
+
+      if (!is_gimple_assign (def_stmt)
+	  || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
+	return false;
+
+      innerop = gimple_assign_rhs1 (def_stmt);
+
+      if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (innerop))
+	{
+	  value_range_t *vr = get_value_range (innerop);
+
+          if (vr->type == VR_RANGE
+	      && operand_equal_p (vr->min, integer_zero_node, 0)
+	      && operand_equal_p (vr->max, integer_one_node, 0))
+	    {
+	      tree newconst = fold_convert (TREE_TYPE (innerop), op1);
+	      gimple_cond_set_lhs (stmt, innerop);
+	      gimple_cond_set_rhs (stmt, newconst);
+	      return true;
+	    }
+	}
+    }
+
   return false;
 }