Patchwork [RFA] Improve VRP of COND_EXPR_CONDs

login
register
mail settings
Submitter Jeff Law
Date April 6, 2013, 12:48 p.m.
Message ID <516019AE.1050103@redhat.com>
Download mbox | patch
Permalink /patch/234430/
State New
Headers show

Comments

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
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

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;
 }