diff mbox

[RFC,PR61839] Convert CST BINOP COND_EXPR to COND_EXPR ? (CST BINOP 1) : (CST BINOP 0)

Message ID CAELXzTNArY7QfBpNuA1C+xY75uxzgT4NxfNX-40K=B8ztzBr+Q@mail.gmail.com
State New
Headers show

Commit Message

Kugan Vivekanandarajah Aug. 9, 2016, 2:51 a.m. UTC 
Hi Richard,

Thanks for the review.

On 29 April 2016 at 20:47, Richard Biener <richard.guenther@gmail.com> wrote:
> On Sun, Apr 17, 2016 at 1:14 AM, kugan
> <kugan.vivekanandarajah@linaro.org> wrote:
>> As explained in PR61839,
>>
>> Following difference results in extra instructions:
>> -  c = b != 0 ? 486097858 : 972195717;
>> +  c = a + 972195718 >> (b != 0);
>>
>> As suggested in PR, attached patch converts CST BINOP COND_EXPR to COND_EXPR
>> ? (CST BINOP 1) : (CST BINOP 0).
>>
>> Bootstrapped and regression tested for x86-64-linux-gnu with no new
>> regression. Is this OK for statege-1.
>
> You are missing a testcase.
>
> I think the transform can be generalized to any two-value value-range by
> instead of
>
>   lhs = cond_res ? (cst binop 1) : (cst binop 0)
>
> emitting
>
>   lhs = tmp == val1 ? (cst binop val1) : (cst binop val2);
>
> In the PR I asked the transform to be only carried out if cond_res and
> tmp have a single use (and thus they'd eventually vanish).
>
> I'm not sure if a general two-value "constant" propagation is profitable
> which is why I was originally asking for the pattern to only apply
> if the resulting value is used in a comparison which we could then
> in turn simplify by substituting COND_RES (or ! COND_RES) for it.
> For the general two-value case we'd substitute it with tmp [=!]= val[12]
> dependent on which constant is cheaper to test for.
>
> So I think this needs some exploring work on which way to go
> and which transform is profitable in the end.  I think the general
> two-value case feeding a condition will be always profitable.


Please find a modified version which checks for two-valued variable
and uses this to optimize. In the attached test case (in function
bar), we end up doing the conversion twice.

Bootstrapped and regression tested on x86_64-linux-gnu without no new
regressions. Is this OK for trunk?

Thanks,
Kugan

gcc/testsuite/ChangeLog:

2016-08-09  Kugan Vivekanandarajah  <kuganv@linaro.org>

    PR tree-optimization/61839
    * gcc.dg/tree-ssa/pr61839.c: New test.

gcc/ChangeLog:

2016-08-09  Kugan Vivekanandarajah  <kuganv@linaro.org>

    PR tree-optimization/61839
    * tree-vrp.c (two_valued_val_range_p): New.
    (simplify_stmt_using_ranges): Convert CST BINOP VAR where VAR is
    two-valued to VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2).

Comments

Richard Biener Aug. 9, 2016, 10:22 a.m. UTC | #1 
On Tue, Aug 9, 2016 at 4:51 AM, Kugan Vivekanandarajah
<kugan.vivekanandarajah@linaro.org> wrote:
> Hi Richard,
>
> Thanks for the review.
>
> On 29 April 2016 at 20:47, Richard Biener <richard.guenther@gmail.com> wrote:
>> On Sun, Apr 17, 2016 at 1:14 AM, kugan
>> <kugan.vivekanandarajah@linaro.org> wrote:
>>> As explained in PR61839,
>>>
>>> Following difference results in extra instructions:
>>> -  c = b != 0 ? 486097858 : 972195717;
>>> +  c = a + 972195718 >> (b != 0);
>>>
>>> As suggested in PR, attached patch converts CST BINOP COND_EXPR to COND_EXPR
>>> ? (CST BINOP 1) : (CST BINOP 0).
>>>
>>> Bootstrapped and regression tested for x86-64-linux-gnu with no new
>>> regression. Is this OK for statege-1.
>>
>> You are missing a testcase.
>>
>> I think the transform can be generalized to any two-value value-range by
>> instead of
>>
>>   lhs = cond_res ? (cst binop 1) : (cst binop 0)
>>
>> emitting
>>
>>   lhs = tmp == val1 ? (cst binop val1) : (cst binop val2);
>>
>> In the PR I asked the transform to be only carried out if cond_res and
>> tmp have a single use (and thus they'd eventually vanish).
>>
>> I'm not sure if a general two-value "constant" propagation is profitable
>> which is why I was originally asking for the pattern to only apply
>> if the resulting value is used in a comparison which we could then
>> in turn simplify by substituting COND_RES (or ! COND_RES) for it.
>> For the general two-value case we'd substitute it with tmp [=!]= val[12]
>> dependent on which constant is cheaper to test for.
>>
>> So I think this needs some exploring work on which way to go
>> and which transform is profitable in the end.  I think the general
>> two-value case feeding a condition will be always profitable.
>
>
> Please find a modified version which checks for two-valued variable
> and uses this to optimize. In the attached test case (in function
> bar), we end up doing the conversion twice.
>
> Bootstrapped and regression tested on x86_64-linux-gnu without no new
> regressions. Is this OK for trunk?

+/* Return true if VAR is a two-valued variable.  Set MIN and MAX when it is
+   true.  Return false otherwise.  */
+
+static bool
+two_valued_val_range_p (tree var, tree *min, tree *max)
+{

I'd use A and B, not MIN/MAX given it's two values, not necessarily
a two-valued range (for example for ~[1, UINT_MAX-1] which you
don't handle).  In theory VRP might get a more sophisticated range
representation to also allow a range consisting of just 3 and 7 for example.

+  tree tmp
+    = int_const_binop (PLUS_EXPR,
+                      vr->min,
+                      build_int_cst_type (TREE_TYPE (var), 1));
+  if (0 != compare_values (tmp, vr->max))
+    return false;

I think simply

   if (wi::sub (vr->max, vr->min) == 1)

might work as well and avoid building a tree node.

+      /* Convert:
+        LHS = CST BINOP VAR
+        where VAR is two-valued.
+
+        To:
+        LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2) */
+
+      if (TREE_CODE_CLASS (rhs_code) == tcc_binary
+         && TREE_CODE (rhs1) == INTEGER_CST
+         && TREE_CODE (rhs2) == SSA_NAME

Note that for all commutative tcc_binary operators the constant will be on the
other operand.  I think you need to handle the constant appearing in both places
(and for division for example watch out for a zero divisor).

+         && has_single_use (rhs2)
+         && two_valued_val_range_p (rhs2, &min, &max))
+
+       {
+         tree cond = build2 (EQ_EXPR, TREE_TYPE (rhs2), rhs2, min);
+         tree new_rhs1 =  int_const_binop (rhs_code, rhs1, min);
+         tree new_rhs2 =  int_const_binop (rhs_code, rhs1, max);

too many spaces after '='.

+
+         if (new_rhs1 && new_rhs2)

You didn't address my point about profitability - you test for a single use
but not for the kind of use.  Please instead use

    && single_imm_use (rhs2, &use_p, &use_stmt)
    && gimple_code (use_stmt) == GIMPLE_COND

The testcase won't work on targets with small integers thus please
require int32plus.  With the existing scan-dumps it's not obvious
what transform it is testing for - please add a comment before
the dump scan reflecting the desired transform.  Maybe also scan
"optimized" instead to also verify that followup transforms trigger.

Thanks,
Richard.

> Thanks,
> Kugan
>
> gcc/testsuite/ChangeLog:
>
> 2016-08-09  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>     PR tree-optimization/61839
>     * gcc.dg/tree-ssa/pr61839.c: New test.
>
> gcc/ChangeLog:
>
> 2016-08-09  Kugan Vivekanandarajah  <kuganv@linaro.org>
>
>     PR tree-optimization/61839
>     * tree-vrp.c (two_valued_val_range_p): New.
>     (simplify_stmt_using_ranges): Convert CST BINOP VAR where VAR is
>     two-valued to VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2).
diff mbox

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c b/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c
index e69de29..1bb77d1 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c
@@ -0,0 +1,40 @@ 
+/* PR tree-optimization/61839 */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-vrp1" } */
+
+__attribute__ ((noinline))
+int foo ()
+{
+  int a = -1;
+  volatile unsigned b = 1U;
+  int c = 1;
+  c = (a + 972195718) >> (1LU <= b);
+  if (c == 486097858)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+__attribute__ ((noinline))
+int bar ()
+{
+  int a = -1;
+  volatile unsigned b = 1U;
+  int c = 1;
+  c = (a + 972195718) >> (b ? 2 : 3);
+  if (c == 243048929)
+    ;
+  else
+    __builtin_abort ();
+  return 0;
+}
+
+int main ()
+{
+  foo ();
+  bar ();
+}
+
+/* { dg-final { scan-tree-dump-times "486097858 : 972195717" 1  "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "243048929 : 121524464" 2  "vrp1" } } */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 7c7ad91..d5e2fc3 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10004,6 +10004,27 @@  simplify_internal_call_using_ranges (gimple_stmt_iterator *gsi, gimple *stmt)
   return true;
 }
 
+/* Return true if VAR is a two-valued variable.  Set MIN and MAX when it is
+   true.  Return false otherwise.  */
+
+static bool
+two_valued_val_range_p (tree var, tree *min, tree *max)
+{
+  value_range *vr = get_value_range (var);
+  if (vr->type != VR_RANGE
+      || !range_int_cst_p (vr))
+    return false;
+  tree tmp
+    = int_const_binop (PLUS_EXPR,
+		       vr->min,
+		       build_int_cst_type (TREE_TYPE (var), 1));
+  if (0 != compare_values (tmp, vr->max))
+    return false;
+  *min = vr->min;
+  *max = vr->max;
+  return true;
+}
+
 /* Simplify STMT using ranges if possible.  */
 
 static bool
@@ -10014,6 +10035,38 @@  simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
     {
       enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
       tree rhs1 = gimple_assign_rhs1 (stmt);
+      tree rhs2 = gimple_assign_rhs2 (stmt);
+      tree lhs = gimple_assign_lhs (stmt);
+      tree min, max;
+
+      /* Convert:
+	 LHS = CST BINOP VAR
+	 where VAR is two-valued.
+
+	 To:
+	 LHS = VAR == VAL1 ? (CST BINOP VAL1) : (CST BINOP VAL2) */
+
+      if (TREE_CODE_CLASS (rhs_code) == tcc_binary
+	  && TREE_CODE (rhs1) == INTEGER_CST
+	  && TREE_CODE (rhs2) == SSA_NAME
+	  && has_single_use (rhs2)
+	  && two_valued_val_range_p (rhs2, &min, &max))
+
+	{
+	  tree cond = build2 (EQ_EXPR, TREE_TYPE (rhs2), rhs2, min);
+	  tree new_rhs1 =  int_const_binop (rhs_code, rhs1, min);
+	  tree new_rhs2 =  int_const_binop (rhs_code, rhs1, max);
+
+	  if (new_rhs1 && new_rhs2)
+	    {
+	      gimple_assign_set_rhs_with_ops (gsi,
+					      COND_EXPR, cond,
+					      new_rhs1,
+					      new_rhs2);
+	      update_stmt (gsi_stmt (*gsi));
+	      return true;
+	    }
+	}
 
       switch (rhs_code)
 	{