Hi Richard,
On 09/08/16 20:22, Richard Biener wrote:
On Tue, Aug 9, 2016 at 4:51 AM, Kugan Vivekanandarajah
<kugan.vivekanandara...@linaro.org> wrote:
Hi Richard,
Thanks for the review.
On 29 April 2016 at 20:47, Richard Biener <richard.guent...@gmail.com> wrote:
On Sun, Apr 17, 2016 at 1:14 AM, kugan
<kugan.vivekanandara...@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
I have changed this. I don't think this would be the only
VR_ANTI_RANGE. Others like TYPE_MIN + 1, TYPE_MIN + 2 should come as
VR_RANGE.
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.
I am not sure how this will be represented as value range. Is this for
enum types where thhere is no valid values between 3 and 7 ?
+ 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)
I have changed this.
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).
I have now canonicalized it in the beginning. I don't think it will
affect other simplifications that comes after this transformation.
+ && 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 '='.
Done.
+
+ 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
I checked with some simple test-cases. In those cases it either improves
or no difference.
&& single_imm_use (rhs2, &use_p, &use_stmt)
&& gimple_code (use_stmt) == GIMPLE_COND
Done.
The testcase won't work on targets with small integers thus please
require int32plus. With the existing scan-dumps it's not obvious
Done.
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.
Done.
ASM difference for x86-64 is
@@ -11,11 +11,7 @@
movl $1, 12(%rsp)
movl 12(%rsp), %eax
testl %eax, %eax
- movl $972195717, %eax
- setne %cl
- sarl %cl, %eax
- cmpl $486097858, %eax
- jne .L5
+ je .L5
xorl %eax, %eax
addq $24, %rsp
.cfi_remember_state
function bar in the test-case is already optimized so no difference. I
just added to make sure that the operation is correct.
Bootstrapped and regression tested on x86_64-linux-gn with no new
regressions. Is this OK for trunk now.
Thanks,
Kugan
Thanks,
Richard.
Thanks,
Kugan
gcc/testsuite/ChangeLog:
2016-08-09 Kugan Vivekanandarajah <kug...@linaro.org>
PR tree-optimization/61839
* gcc.dg/tree-ssa/pr61839.c: New test.
gcc/ChangeLog:
2016-08-09 Kugan Vivekanandarajah <kug...@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 --git a/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c
index e69de29..abe46a0 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr61839.c
@@ -0,0 +1,44 @@
+/* PR tree-optimization/61839. */
+/* { dg-do run } */
+/* { dg-options "-O2 -fdump-tree-vrp1 -fdump-tree-optimized" } */
+/* { dg-require-effective-target int32plus } */
+
+__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 ();
+}
+
+/* Scan for c = 972195717) >> [0, 1] in function foo. */
+/* { dg-final { scan-tree-dump-times "972195717 : 486097858" 1 "vrp1" } } */
+/* Scan for c = 972195717) >> [2, 3] in function bar. */
+/* { dg-final { scan-tree-dump-times "243048929 : 121524464" 2 "vrp1" } } */
+/* { dg-final { scan-tree-dump-times "486097858" 0 "optimized" } } */
diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
index 7c7ad91..b9013b3 100644
--- a/gcc/tree-vrp.c
+++ b/gcc/tree-vrp.c
@@ -10004,6 +10004,39 @@ simplify_internal_call_using_ranges
(gimple_stmt_iterator *gsi, gimple *stmt)
return true;
}
+/* Return true if VAR is a two-valued variable. Set a and b with the
+ two-values when it is true. Return false otherwise. */
+
+static bool
+two_valued_val_range_p (tree var, tree *a, tree *b)
+{
+ value_range *vr = get_value_range (var);
+ if ((vr->type != VR_RANGE
+ && vr->type != VR_ANTI_RANGE)
+ || !range_int_cst_p (vr))
+ return false;
+
+ if (vr->type == VR_RANGE
+ && wi::sub (vr->max, vr->min) == 1)
+ {
+ *a = vr->min;
+ *b = vr->max;
+ return true;
+ }
+
+ /* ~[TYPE_MIN + 1, TYPE_MAX - 1] */
+ if (vr->type == VR_ANTI_RANGE
+ && wi::sub (vr->min, wi::min_value (TREE_TYPE (var))) == 1
+ && wi::sub (wi::max_value (TREE_TYPE (var)), vr->max) == 1)
+ {
+ *a = TYPE_MIN_VALUE (TREE_TYPE (var));
+ *b = TYPE_MAX_VALUE (TREE_TYPE (var));
+ return true;
+ }
+
+ return false;
+}
+
/* Simplify STMT using ranges if possible. */
static bool
@@ -10014,6 +10047,61 @@ 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 val1 = NULL_TREE, val2 = NULL_TREE;
+ use_operand_p use_p;
+ gimple *use_stmt;
+
+ /* First canonicalize to simplify tests. */
+ if (commutative_tree_code (rhs_code)
+ && TREE_CODE (rhs2) == INTEGER_CST)
+ std::swap (rhs1, rhs2);
+
+ /* Convert:
+ LHS = CST BINOP VAR
+ Where VAR is two-valued and LHS is used in GIMPLE_COND only
+ 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
+ && single_imm_use (lhs, &use_p, &use_stmt)
+ && gimple_code (use_stmt) == GIMPLE_COND
+ && two_valued_val_range_p (rhs2, &val1, &val2))
+
+ {
+ tree new_rhs1 = NULL_TREE;
+ tree new_rhs2 = NULL_TREE;
+ switch (rhs_code)
+ {
+ case TRUNC_DIV_EXPR:
+ case CEIL_DIV_EXPR:
+ case FLOOR_DIV_EXPR:
+ case ROUND_DIV_EXPR:
+ case EXACT_DIV_EXPR:
+ /* Prevent divide by zero. */
+ if (integer_zerop (val1)
+ || integer_zerop (val2))
+ break;
+ default:
+ new_rhs1 = int_const_binop (rhs_code, rhs1, val1);
+ new_rhs2 = int_const_binop (rhs_code, rhs1, val2);
+ break;
+ }
+
+ if (new_rhs1 && new_rhs2)
+ {
+ tree cond = build2 (EQ_EXPR, TREE_TYPE (rhs2), rhs2, val1);
+ gimple_assign_set_rhs_with_ops (gsi,
+ COND_EXPR, cond,
+ new_rhs1,
+ new_rhs2);
+ update_stmt (gsi_stmt (*gsi));
+ return true;
+ }
+ }
switch (rhs_code)
{
