[PATCH 2/2] Simplify and extend VRP edge-assertion code
Andrew Pinski
pinskia@gmail.com
Tue Nov 11 12:56:00 GMT 2014
On Tue, Nov 11, 2014 at 4:52 AM, Richard Biener
<richard.guenther@gmail.com> wrote:
> On Tue, Nov 11, 2014 at 4:52 AM, Patrick Palka <patrick@parcs.ath.cx> wrote:
>> This patch refactors the VRP edge-assertion code to make it always
>> traverse SSA-name definitions in order to find suitable edge assertions
>> to insert. Currently SSA-name definitions get traversed only when the
>> LHS of the original conditional is a bitwise AND or OR operation which
>> seems like a strange restriction. We should always try to traverse
>> the SSA-name definitions inside the conditional, in particular for
>> conditionals with the form:
>>
>> int p = x COMP y;
>> if (p != 0) -- edge assertion: x COMP y
>
> Of course this specific case should have been simplified to
>
> if (x COMP y)
>
> if that comparison cannot trap and -fnon-call-exceptions is in effect.
Except I have found that if p was used below also. We still have if(p
!= 0). I just saw that recently when I was working on enhancing
PHI-opt.
Thanks,
Andrew Pinski
>
>> To achieve this the patch merges the mutually recursive functions
>> register_edge_assert_for_1() and register_edge_assert_for_2() into a
>> single recursive function, register_edge_assert_for_1(). In doing so,
>> code duplication can be reduced and at the same time the more general
>> logic allows VRP to detect more useful edge assertions.
>>
>> The recursion of the function register_edge_assert_for_1() is bounded by
>> a new 'limit' argument which is arbitrarily set to 4 so that at most 4
>> levels of SSA-name definitions will be traversed per conditional.
>> (Incidentally this hard recursion limit makes the related fix for PR
>> 57685 unnecessary.)
>>
>> A test in uninit-pred-9_b.c now has to be marked xfail because in it VRP
>> (correctly) transforms the statement
>>
>> # prephitmp_35 = PHI <pretmp_9(8), _28(10)>
>> into
>> # prephitmp_35 = PHI <pretmp_9(8), 1(10)>
>>
>> and the uninit pass doesn't properly handle such PHIs containing a
>> constant value as one of its arguments -- so a bogus uninit warning is
>> now emitted.
>
> Did you try fixing that? It seems to me a constant should be easy
> to handle?
>
>> Full bootstrap + regtesting on x86_64-unknown-linux-gnu is in progress.
>> Is it OK to commit if testing finishes with no new regressions?
>
> Ok.
>
> Thanks,
> Richard.
>
>> 2014-11-11 Patrick Palka <patrick@parcs.ath.cx>
>>
>> gcc/
>> * tree-vrp.c (extract_code_and_val_from_cond_with_ops): Ensure
>> that NAME always equals COND_OP0 or COND_OP1.
>> (register_edge_assert_for, register_edge_assert_for_1,
>> register_edge_assert_for_2): Refactor and consolidate
>> edge-assertion logic into ...
>> (register_edge_assert_for_2): ... here. Add LIMIT parameter.
>> Rename to ...
>> (register_edge_assert_for_1): ... this.
>>
>> gcc/testsuite/
>> * gcc.dg/vrp-1.c: New testcase.
>> * gcc.dg/vrp-2.c: New testcase.
>> * gcc.dg/uninit-pred-9_b.c: xfail test on line 24.
>> ---
>> gcc/testsuite/gcc.dg/uninit-pred-9_b.c | 2 +-
>> gcc/testsuite/gcc.dg/vrp-1.c | 31 ++++
>> gcc/testsuite/gcc.dg/vrp-2.c | 78 ++++++++++
>> gcc/tree-vrp.c | 261 +++++++++++++++------------------
>> 4 files changed, 231 insertions(+), 141 deletions(-)
>> create mode 100644 gcc/testsuite/gcc.dg/vrp-1.c
>> create mode 100644 gcc/testsuite/gcc.dg/vrp-2.c
>>
>> diff --git a/gcc/testsuite/gcc.dg/uninit-pred-9_b.c b/gcc/testsuite/gcc.dg/uninit-pred-9_b.c
>> index d9ae75e..555ec20 100644
>> --- a/gcc/testsuite/gcc.dg/uninit-pred-9_b.c
>> +++ b/gcc/testsuite/gcc.dg/uninit-pred-9_b.c
>> @@ -21,7 +21,7 @@ int foo (int n, int l, int m, int r)
>> blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
>>
>> if ( (n <= 8) && (m < 99) && (r < 19) )
>> - blah(v); /* { dg-bogus "uninitialized" "bogus warning" } */
>> + blah(v); /* { dg-bogus "uninitialized" "bogus warning" { xfail *-*-* } } */
>>
>> return 0;
>> }
>> diff --git a/gcc/testsuite/gcc.dg/vrp-1.c b/gcc/testsuite/gcc.dg/vrp-1.c
>> new file mode 100644
>> index 0000000..df5334e
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/vrp-1.c
>> @@ -0,0 +1,31 @@
>> +/* { dg-options "-O2" } */
>> +
>> +void runtime_error (void) __attribute__ ((noreturn));
>> +void compiletime_error (void) __attribute__ ((noreturn, error ("")));
>> +
>> +static void
>> +compiletime_check_equals_1 (int *x, int y)
>> +{
>> + int __p = *x != y;
>> + if (__builtin_constant_p (__p) && __p)
>> + compiletime_error ();
>> + if (__p)
>> + runtime_error ();
>> +}
>> +
>> +static void
>> +compiletime_check_equals_2 (int *x, int y)
>> +{
>> + int __p = *x != y;
>> + if (__builtin_constant_p (__p) && __p)
>> + compiletime_error (); /* { dg-error "call to" } */
>> + if (__p)
>> + runtime_error ();
>> +}
>> +
>> +void
>> +foo (int *x)
>> +{
>> + compiletime_check_equals_1 (x, 5);
>> + compiletime_check_equals_2 (x, 10);
>> +}
>> diff --git a/gcc/testsuite/gcc.dg/vrp-2.c b/gcc/testsuite/gcc.dg/vrp-2.c
>> new file mode 100644
>> index 0000000..5757c2f
>> --- /dev/null
>> +++ b/gcc/testsuite/gcc.dg/vrp-2.c
>> @@ -0,0 +1,78 @@
>> +/* { dg-options "-O2" } */
>> +
>> +void runtime_error (void) __attribute__ ((noreturn));
>> +void compiletime_error (void) __attribute__ ((noreturn, error ("")));
>> +
>> +void dummy (int x);
>> +
>> +void
>> +bar (int x, int y, int z)
>> +{
>> + int p = ~(x & y & z) == 37;
>> + if (p)
>> + {
>> + if (!x || !y || !z)
>> + compiletime_error (); /* { dg-bogus "call to" } */
>> + }
>> +}
>> +
>> +void
>> +baz (int x)
>> +{
>> + int y = ~x;
>> + int p = y == 37;
>> + dummy (y);
>> + dummy (p);
>> + if (p)
>> + {
>> + int q = x != ~37;
>> + dummy (q);
>> + if (q)
>> + compiletime_error (); /* { dg-bogus "call to" } */
>> + }
>> +}
>> +
>> +void
>> +blah_1 (char x)
>> +{
>> + int y = x;
>> + int p = y == 10;
>> + dummy (p);
>> + if (p)
>> + {
>> + int q = x != 10;
>> + dummy (q);
>> + if (q)
>> + compiletime_error (); /* { dg-bogus "call to" } */
>> + }
>> +}
>> +
>> +void
>> +blah_2 (int x)
>> +{
>> + char y = x;
>> + int p = y != 100;
>> + dummy (y);
>> + dummy (p);
>> + if (p)
>> + {
>> + int q = x == 100;
>> + dummy (q);
>> + if (q)
>> + compiletime_error (); /* { dg-bogus "call to" } */
>> + }
>> +}
>> +
>> +void
>> +blah_3 (int x, int y)
>> +{
>> + int p = x > y;
>> + dummy (p);
>> + if (p)
>> + {
>> + int q = x <= y;
>> + dummy (q);
>> + if (q)
>> + compiletime_error (); /* { dg-bogus "call to" } */
>> + }
>> +}
>> diff --git a/gcc/tree-vrp.c b/gcc/tree-vrp.c
>> index f0a4382..f1b5839 100644
>> --- a/gcc/tree-vrp.c
>> +++ b/gcc/tree-vrp.c
>> @@ -4896,9 +4896,14 @@ extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
>> enum tree_code comp_code;
>> tree val;
>>
>> - /* Otherwise, we have a comparison of the form NAME COMP VAL
>> - or VAL COMP NAME. */
>> - if (name == cond_op1)
>> + if (name == cond_op0)
>> + {
>> + /* The comparison is of the form NAME COMP VAL, so the
>> + comparison code remains unchanged. */
>> + comp_code = cond_code;
>> + val = cond_op1;
>> + }
>> + else if (name == cond_op1)
>> {
>> /* If the predicate is of the form VAL COMP NAME, flip
>> COMP around because we need to register NAME as the
>> @@ -4907,12 +4912,7 @@ extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
>> val = cond_op0;
>> }
>> else
>> - {
>> - /* The comparison is of the form NAME COMP VAL, so the
>> - comparison code remains unchanged. */
>> - comp_code = cond_code;
>> - val = cond_op1;
>> - }
>> + gcc_unreachable ();
>>
>> /* Invert the comparison code as necessary. */
>> if (invert)
>> @@ -4976,16 +4976,31 @@ masked_increment (const wide_int &val_in, const wide_int &mask,
>> }
>>
>> /* Try to register an edge assertion for SSA name NAME on edge E for
>> - the condition COND contributing to the conditional jump pointed to by BSI.
>> + the condition COND (composed of COND_CODE, COND_OP0 and COND_OP1)
>> + contributing to the conditional jump pointed to by BSI.
>> +
>> + Further, try to recursively register edge assertions for the SSA names in
>> + the defining statements of COND's operands. This recursion is limited by
>> + LIMIT.
>> +
>> Invert the condition COND if INVERT is true. */
>>
>> static void
>> -register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>> - enum tree_code cond_code,
>> +register_edge_assert_for_1 (tree name, edge e, gimple_stmt_iterator bsi,
>> + unsigned int limit, enum tree_code cond_code,
>> tree cond_op0, tree cond_op1, bool invert)
>> {
>> tree val;
>> - enum tree_code comp_code;
>> + enum tree_code comp_code, def_rhs_code;
>> + gimple def_stmt;
>> +
>> + if (limit == 0 || TREE_CODE (name) != SSA_NAME)
>> + return;
>> +
>> + /* Do not attempt to infer anything in names that flow through
>> + abnormal edges. */
>> + if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
>> + return;
>>
>> if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
>> cond_op0,
>> @@ -5512,92 +5527,116 @@ register_edge_assert_for_2 (tree name, edge e, gimple_stmt_iterator bsi,
>> }
>> }
>> }
>> -}
>>
>> -/* OP is an operand of a truth value expression which is known to have
>> - a particular value. Register any asserts for OP and for any
>> - operands in OP's defining statement.
>>
>> - If CODE is EQ_EXPR, then we want to register OP is zero (false),
>> - if CODE is NE_EXPR, then we want to register OP is nonzero (true). */
>> + /* If COND is effectively an equality test of an SSA_NAME against
>> + the value zero or one, then we may be able to assert values
>> + for SSA_NAMEs which flow into COND. */
>>
>> -static void
>> -register_edge_assert_for_1 (tree op, enum tree_code code,
>> - edge e, gimple_stmt_iterator bsi)
>> -{
>> - gimple op_def;
>> - tree val;
>> - enum tree_code rhs_code;
>> -
>> - /* We only care about SSA_NAMEs. */
>> - if (TREE_CODE (op) != SSA_NAME)
>> + def_stmt = SSA_NAME_DEF_STMT (name);
>> + if (!is_gimple_assign (def_stmt))
>> return;
>>
>> - /* We know that OP will have a zero or nonzero value. If OP is used
>> - more than once go ahead and register an assert for OP. */
>> - if (live_on_edge (e, op)
>> - && !has_single_use (op))
>> - {
>> - val = build_int_cst (TREE_TYPE (op), 0);
>> - register_new_assert_for (op, op, code, val, NULL, e, bsi);
>> - }
>> + def_rhs_code = gimple_assign_rhs_code (def_stmt);
>>
>> - /* Now look at how OP is set. If it's set from a comparison,
>> - a truth operation or some bit operations, then we may be able
>> - to register information about the operands of that assignment. */
>> - op_def = SSA_NAME_DEF_STMT (op);
>> - if (gimple_code (op_def) != GIMPLE_ASSIGN)
>> - return;
>> + /* In the case of NAME != 0 or NAME == C (where C != 0), for BIT_AND_EXPR
>> + defining statement of NAME we can assert that both operands of the
>> + BIT_AND_EXPR have nonzero value. */
>> + if (def_rhs_code == BIT_AND_EXPR
>> + && ((comp_code == NE_EXPR && integer_zerop (val))
>> + || (comp_code == EQ_EXPR && TREE_CODE (val) == INTEGER_CST
>> + && integer_nonzerop (val))))
>> + {
>> + tree op0 = gimple_assign_rhs1 (def_stmt);
>> + tree op1 = gimple_assign_rhs2 (def_stmt);
>> + tree zero = build_zero_cst (TREE_TYPE (val));
>>
>> - rhs_code = gimple_assign_rhs_code (op_def);
>> + register_edge_assert_for_1 (op0, e, bsi, limit - 1,
>> + NE_EXPR, op0, zero, false);
>> + register_edge_assert_for_1 (op1, e, bsi, limit - 1,
>> + NE_EXPR, op1, zero, false);
>> + }
>>
>> - if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
>> + /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
>> + statement of NAME we can assert that both operands of the BIT_IOR_EXPR
>> + have value zero. */
>> + if (def_rhs_code == BIT_IOR_EXPR
>> + && ((comp_code == EQ_EXPR && integer_zerop (val))
>> + || (comp_code == NE_EXPR && integer_onep (val)
>> + && TYPE_PRECISION (TREE_TYPE (name)) == 1)))
>> {
>> - bool invert = (code == EQ_EXPR ? true : false);
>> - tree op0 = gimple_assign_rhs1 (op_def);
>> - tree op1 = gimple_assign_rhs2 (op_def);
>> + tree op0 = gimple_assign_rhs1 (def_stmt);
>> + tree op1 = gimple_assign_rhs2 (def_stmt);
>> + tree zero = build_zero_cst (TREE_TYPE (val));
>>
>> - if (TREE_CODE (op0) == SSA_NAME)
>> - register_edge_assert_for_2 (op0, e, bsi, rhs_code, op0, op1, invert);
>> - if (TREE_CODE (op1) == SSA_NAME)
>> - register_edge_assert_for_2 (op1, e, bsi, rhs_code, op0, op1, invert);
>> + register_edge_assert_for_1 (op0, e, bsi, limit - 1,
>> + EQ_EXPR, op0, zero, false);
>> + register_edge_assert_for_1 (op1, e, bsi, limit - 1,
>> + EQ_EXPR, op1, zero, false);
>> }
>> - else if ((code == NE_EXPR
>> - && gimple_assign_rhs_code (op_def) == BIT_AND_EXPR)
>> - || (code == EQ_EXPR
>> - && gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR))
>> +
>> + if (def_rhs_code == BIT_NOT_EXPR
>> + && (comp_code == EQ_EXPR || comp_code == NE_EXPR)
>> + && TREE_CODE (val) == INTEGER_CST)
>> {
>> - /* Recurse on each operand. */
>> - tree op0 = gimple_assign_rhs1 (op_def);
>> - tree op1 = gimple_assign_rhs2 (op_def);
>> - if (TREE_CODE (op0) == SSA_NAME
>> - && has_single_use (op0))
>> - register_edge_assert_for_1 (op0, code, e, bsi);
>> - if (TREE_CODE (op1) == SSA_NAME
>> - && has_single_use (op1))
>> - register_edge_assert_for_1 (op1, code, e, bsi);
>> + /* Recurse, inverting VAL. */
>> + tree rhs = gimple_assign_rhs1 (def_stmt);
>> + tree new_val = fold_build1 (BIT_NOT_EXPR, TREE_TYPE (val), val);
>> + register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
>> + comp_code, rhs, new_val, false);
>> }
>> - else if (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
>> - && TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (op_def))) == 1)
>> +
>> + /* In the case of NAME == [01] or NAME != [01], if NAME's defining statement
>> + is a TCC_COMPARISON then we can assert the defining statement itself or
>> + its negation. */
>> + if (TREE_CODE_CLASS (def_rhs_code) == tcc_comparison
>> + && (comp_code == EQ_EXPR || comp_code == NE_EXPR)
>> + && (integer_zerop (val) || integer_onep (val)))
>> {
>> - /* Recurse, flipping CODE. */
>> - code = invert_tree_comparison (code, false);
>> - register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e, bsi);
>> + tree op0 = gimple_assign_rhs1 (def_stmt);
>> + tree op1 = gimple_assign_rhs2 (def_stmt);
>> + bool invert = false;
>> +
>> + if ((comp_code == EQ_EXPR && integer_zerop (val))
>> + || (comp_code == NE_EXPR && integer_onep (val)))
>> + invert = true;
>> +
>> + register_edge_assert_for_1 (op0, e, bsi, limit - 1,
>> + def_rhs_code, op0, op1, invert);
>> + register_edge_assert_for_1 (op1, e, bsi, limit - 1,
>> + def_rhs_code, op0, op1, invert);
>> }
>> - else if (gimple_assign_rhs_code (op_def) == SSA_NAME)
>> +
>> + if (def_rhs_code == SSA_NAME)
>> {
>> /* Recurse through the copy. */
>> - register_edge_assert_for_1 (gimple_assign_rhs1 (op_def), code, e, bsi);
>> + tree rhs = gimple_assign_rhs1 (def_stmt);
>> + register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
>> + comp_code, rhs, val, false);
>> }
>> - else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def)))
>> +
>> + if (CONVERT_EXPR_CODE_P (def_rhs_code)
>> + && TREE_CODE (val) == INTEGER_CST)
>> {
>> - /* Recurse through the type conversion, unless it is a narrowing
>> - conversion or conversion from non-integral type. */
>> - tree rhs = gimple_assign_rhs1 (op_def);
>> + /* Recurse through the type conversion if possible. */
>> + tree rhs = gimple_assign_rhs1 (def_stmt);
>> +
>> if (INTEGRAL_TYPE_P (TREE_TYPE (rhs))
>> - && (TYPE_PRECISION (TREE_TYPE (rhs))
>> - <= TYPE_PRECISION (TREE_TYPE (op))))
>> - register_edge_assert_for_1 (rhs, code, e, bsi);
>> + /* If NAME is a widening conversion then from the condition
>> + (NAME = (T)RHS) == VAL we can extract RHS == VAL. */
>> + && ((comp_code == EQ_EXPR
>> + && TYPE_PRECISION (TREE_TYPE (name))
>> + >= TYPE_PRECISION (TREE_TYPE (rhs)))
>> + /* If NAME is a narrowing conversion then from the condition
>> + (NAME = (T)RHS) != VAL we can extract RHS != VAL. */
>> + || (comp_code == NE_EXPR
>> + && TYPE_PRECISION (TREE_TYPE (name))
>> + <= TYPE_PRECISION (TREE_TYPE (rhs)))))
>> + {
>> + tree new_val = fold_convert (TREE_TYPE (rhs), val);
>> + register_edge_assert_for_1 (rhs, e, bsi, limit - 1,
>> + comp_code, rhs, new_val, false);
>> + }
>> }
>> }
>>
>> @@ -5610,69 +5649,11 @@ register_edge_assert_for (tree name, edge e, gimple_stmt_iterator si,
>> enum tree_code cond_code, tree cond_op0,
>> tree cond_op1)
>> {
>> - tree val;
>> - enum tree_code comp_code;
>> + const int MAX_TRAVERSAL_DEPTH = 4;
>> bool is_else_edge = (e->flags & EDGE_FALSE_VALUE) != 0;
>>
>> - /* Do not attempt to infer anything in names that flow through
>> - abnormal edges. */
>> - if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
>> - return;
>> -
>> - if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
>> - cond_op0, cond_op1,
>> - is_else_edge,
>> - &comp_code, &val))
>> - return;
>> -
>> - /* Register ASSERT_EXPRs for name. */
>> - register_edge_assert_for_2 (name, e, si, cond_code, cond_op0,
>> - cond_op1, is_else_edge);
>> -
>> -
>> - /* If COND is effectively an equality test of an SSA_NAME against
>> - the value zero or one, then we may be able to assert values
>> - for SSA_NAMEs which flow into COND. */
>> -
>> - /* In the case of NAME == 1 or NAME != 0, for BIT_AND_EXPR defining
>> - statement of NAME we can assert both operands of the BIT_AND_EXPR
>> - have nonzero value. */
>> - if (((comp_code == EQ_EXPR && integer_onep (val))
>> - || (comp_code == NE_EXPR && integer_zerop (val))))
>> - {
>> - gimple def_stmt = SSA_NAME_DEF_STMT (name);
>> -
>> - if (is_gimple_assign (def_stmt)
>> - && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR)
>> - {
>> - tree op0 = gimple_assign_rhs1 (def_stmt);
>> - tree op1 = gimple_assign_rhs2 (def_stmt);
>> - register_edge_assert_for_1 (op0, NE_EXPR, e, si);
>> - register_edge_assert_for_1 (op1, NE_EXPR, e, si);
>> - }
>> - }
>> -
>> - /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
>> - statement of NAME we can assert both operands of the BIT_IOR_EXPR
>> - have zero value. */
>> - if (((comp_code == EQ_EXPR && integer_zerop (val))
>> - || (comp_code == NE_EXPR && integer_onep (val))))
>> - {
>> - gimple def_stmt = SSA_NAME_DEF_STMT (name);
>> -
>> - /* For BIT_IOR_EXPR only if NAME == 0 both operands have
>> - necessarily zero value, or if type-precision is one. */
>> - if (is_gimple_assign (def_stmt)
>> - && (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
>> - && (TYPE_PRECISION (TREE_TYPE (name)) == 1
>> - || comp_code == EQ_EXPR)))
>> - {
>> - tree op0 = gimple_assign_rhs1 (def_stmt);
>> - tree op1 = gimple_assign_rhs2 (def_stmt);
>> - register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
>> - register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
>> - }
>> - }
>> + register_edge_assert_for_1 (name, e, si, MAX_TRAVERSAL_DEPTH, cond_code,
>> + cond_op0, cond_op1, is_else_edge);
>> }
>>
>>
>> --
>> 2.2.0.rc1.16.g6066a7e
>>
More information about the Gcc-patches
mailing list