On Wed, May 10, 2017 at 11:59 PM, Jeff Law <l...@redhat.com> wrote:
>
> So I have some improvements to jump threading that are regressing one of the
> uninit-preds testcases.
>
> The problem is we end up threading deeper into the CFG during VRP1. This
> changes the shape of the CFG such that the condition guarding a use changes
> in an interesting way.
>
> Background:
>
> The form of predicates in tree-ssa-uninit.c is a chain of IOR operations at
> the toplevel. Each IOR operand can be a chain of AND operations.
>
> ie we represent things like
>
>
> (X & Y) (no IOR operations at all, just a chain of ANDs)
>
> X | Y
>
> X | ( Y & Z)
>
> (A & B) | (Y & Z) | (P & D & Q)
>
> You hopefully get the idea.
It actually seems to handle negation as well. Which means it
handles disjunctive normal form.
> We can not represent something like this:
>
> (X | Y) & (A | B)
>
> In this case the IORs are operands of the AND.
>
> --
>
>
> Without the additional threading we have use predicate that looks something
> like this:
>
> _3 != 0 (.AND.) _9 != 0
> (.OR.)
> _3 != 0 (.AND.) (.NOT.) _9 != 0 (.AND.) r_10(D) <= 9
> (.OR.)
> (.NOT.) _3 != 0 (.AND.) r_10(D) <= 9
>
>
>
> Which simplifies nicely into:
>
> 9 != 0
> (.OR.)
> r_10(D) <= 9
>
>
> Which normalizes into:
>
>
> m_7(D) > 100
> (.OR.)
> n_5(D) <= 9
> (.OR.)
> r_10(D) <= 9
>
>
> Which is easily determined to be a subset of the problematical PHI's
> argument's guard.
>
> With the additional threading the predicate chain for the use instead looks
> something like this:
>
> _11 != 0 (.AND.) _30 != 0
>
> If we were to look inside each predicate we'd see each is set from a BIT_IOR
> and it ought to expand into something like this:
>
> (X | Y) & (X | Z)
>
> But that's not a form we can really represent. So no notable simplification
> or normalization occurs and the result is we're unable to determine the use
> guard is a subset of the conditions of the PHI argument's guard. Thus the
> use does not appear to be properly guarded and we issue the false positive
> warning.
>
> But you will notice that form has a common term, X. We can rewrite it as X
> | (Y & Z) which is a form suitable for tree-ssa-uninit.c. And that's
> precisely what this patch does.
The patch should "simply" transform the input into disjunctive normal form.
(X | Y) & (X | Z) happens to be conjunctive normal form (but I'm sure that
generally the input may be not in any of the two normal forms).
Adding a single special-case doesn't look so useful to me.
Ugh, looking at the code it seems to be full of special cases (read:
it's quite ad-hoc)
rather than building up a tree of |& conditions and then normalizing
it. Eventually
one can normalize and gather the preds iteratively (to be able to cut
off at some
predefined size). The advantage of normalized form is that if you have the ops
sorted simplification / comparison / testing is cheap (even trivial).
I've for long
wanted to have such facility in GCC ... too many passes do their own ad-hoc
thing here (ifcombine, threading / VRP, uninit, niter analysis).
Even if not pretty (vec<vec<pred_info> > ...) the data structure in uninit looks
sensible just it seems that while function sames suggest it should work the
way I'd like it to it doesn't (for some reason). Can't we fix that
instead please?
Thanks,
Richard.
> It walks through the toplevel pred_chain_union. Each element is a
> pred_chain. Within the pred_chain we look for cases where the predicate is
> set from a BIT_IOR. Given two predicates set from a BIT_IOR, we then check
> if there's a common term.
>
> If there is a common term, then we extract the common term and add it to the
> toplevel pred_chain_union (X above). The two existing predicates are
> replaced by the unique terms. (Y and Z above).
>
> By replacing the predicates within the pred_chain (as opposed to removal and
> pushing on new predicates), we can trivially look for additional
> opportunities to simplify the active pred_chain.
>
> Anyway once rewritten as X | (Y & Z) we can again see that use is properly
> guarded relative to the offending PHI argument and we do not warn for the
> use.
>
> Bootstrapped and regression tested on x86_64-linux-gnu. I wandered the bugs
> attached to our uninitialized meta BZ and didn't see anything which might
> obviously be fixed by this improvement (sigh).
>
> The testcase is derived from uninit-pred-8_b.c with the one jump thread
> manually applied. It will give a false positive uninit warning with the
> trunk, but does not with this patch applied.
>
> OK for the trunk?
>
> Jeff
>
> ps. This is blocking moving forward with eliminating VRP's jump threading
> dependency on ASSERT_EXPRs :-)
>
>
>
>
> * tree-ssa-uninit.c (simplify_preds_1): Simplify (X | Y) & (X | Z)
> into X | (Y & Z).
> (simplify_preds): Call it.
>
> * gcc.dg/uninit-pred-8_e.c: New test.
>
> diff --git a/gcc/testsuite/gcc.dg/uninit-pred-8_e.c
> b/gcc/testsuite/gcc.dg/uninit-pred-8_e.c
> new file mode 100644
> index 0000000..ede02a7
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/uninit-pred-8_e.c
> @@ -0,0 +1,52 @@
> +/* { dg-do compile } */
> +/* { dg-options "-Wuninitialized -O2" } */
> +
> +void bar (void);
> +void blah1 (int);
> +void blah2 (int);
> +int g;
> +int
> +foo (int n, int l, int m, int r)
> +{
> + int v;
> + _Bool _1;
> + _Bool _2;
> + _Bool _3;
> + _Bool _5;
> + _Bool _6;
> + _Bool _24;
> + _Bool _25;
> + _Bool _26;
> + _Bool _27;
> +
> + _1 = n <= 9;
> + _2 = m > 100;
> + _3 = _1 | _2;
> + _27 = r <= 19;
> + if (_3 != 0)
> + v = r;
> + else
> + {
> + _5 = l != 0;
> + _6 = _5 | _27;
> + if (_6 != 0)
> + v = r;
> + }
> +
> + if (m == 0)
> + bar ();
> + else
> + g++;
> +
> + _24 = _3 | _27;
> + if (_24 == 0)
> + return 0;
> +
> + blah1 (v); /* { dg-bogus "uninitialized" "bogus warning" } */
> + _25 = r <= 9;
> + _26 = _3 | _25;
> + if (_26 != 0)
> + blah2 (v); /* { dg-bogus "uninitialized" "bogus warning" } */
> +
> + return 0;
> +}
> diff --git a/gcc/tree-ssa-uninit.c b/gcc/tree-ssa-uninit.c
> index 60731b2..be99949 100644
> --- a/gcc/tree-ssa-uninit.c
> +++ b/gcc/tree-ssa-uninit.c
> @@ -1582,6 +1582,8 @@ pred_neg_p (pred_info x1, pred_info x2)
> (x != 0 AND y != 0)
> 5) (X AND Y) OR (!X AND Z) OR (!Y AND Z) is equivalent to
> (X AND Y) OR Z
> + 6) (X | Y) AND (X | Z) is equivalent to
> + X | (Y & Z)
>
> PREDS is the predicate chains, and N is the number of chains. */
>
> @@ -1648,6 +1650,125 @@ simplify_pred (pred_chain *one_chain)
> *one_chain = s_chain;
> }
>
> +/* If PREDS has a chain that looks like
> +
> + ((X OR Y) AND (X OR Z))
> +
> + Transform it into
> +
> + (X OR (Y AND Z).
> +
> +
> + Note that since we're creating a new toplevel OR, we have to
> + have the pred_chain_union, rather than just the pred_chain. */
> +
> +static void
> +simplify_preds_1 (pred_chain_union *preds)
> +{
> + int preds_len = preds->length ();
> + for (int i = 0; i < preds_len; i++)
> + {
> + pred_chain *one_chain = &(*preds)[i];
> +
> + /* Walk down ONE_CHAIN looking for a pred which is set from a
> + BIT_IOR_EXPR. */
> + tree term1 = NULL_TREE, term2 = NULL_TREE, term3 = NULL_TREE;
> + int chain_len = one_chain->length ();
> + for (int j = 0; j < chain_len - 1; j++)
> + {
> + pred_info *a_pred = &(*one_chain)[j];
> + if (!a_pred->pred_lhs)
> + continue;
> + if (!is_neq_zero_form_p (*a_pred))
> + continue;
> +
> + gimple *a_stmt = SSA_NAME_DEF_STMT (a_pred->pred_lhs);
> + if (gimple_code (a_stmt) != GIMPLE_ASSIGN
> + || gimple_assign_rhs_code (a_stmt) != BIT_IOR_EXPR)
> + continue;
> +
> + /* We've found a suitable starting BIT_IOR_EXPR, see if there's
> + another later in ONE_CHAIN that we can combine with. */
> + for (int k = j + 1; k < chain_len; k++)
> + {
> + pred_info *b_pred = &(*one_chain)[k];
> + if (!b_pred->pred_lhs)
> + continue;
> + if (!is_neq_zero_form_p (*b_pred))
> + continue;
> +
> + gimple *b_stmt = SSA_NAME_DEF_STMT (b_pred->pred_lhs);
> + if (gimple_code (b_stmt) != GIMPLE_ASSIGN
> + || gimple_assign_rhs_code (b_stmt) != BIT_IOR_EXPR)
> + continue;
> +
> + /* At this point we have two predicates that are set from
> + BIT_IOR_EXPRs. See if there is a common term. */
> + tree a_rhs0 = gimple_assign_rhs1 (a_stmt);
> + tree a_rhs1 = gimple_assign_rhs2 (a_stmt);
> + tree b_rhs0 = gimple_assign_rhs1 (b_stmt);
> + tree b_rhs1 = gimple_assign_rhs2 (b_stmt);
> +
> + /* Only transform if all the objects are SSA_NAMEs. */
> + if (TREE_CODE (a_rhs0) != SSA_NAME
> + || TREE_CODE (a_rhs1) != SSA_NAME
> + || TREE_CODE (b_rhs0) != SSA_NAME
> + || TREE_CODE (b_rhs1) != SSA_NAME)
> + continue;
> +
> + if (a_rhs0 == b_rhs0)
> + {
> + term1 = a_rhs0;
> + term2 = a_rhs1;
> + term3 = b_rhs1;
> + }
> +
> + if (a_rhs0 == b_rhs1)
> + {
> + term1 = a_rhs0;
> + term2 = a_rhs1;
> + term3 = b_rhs0;
> + }
> +
> + if (a_rhs1 == b_rhs0)
> + {
> + term1 = a_rhs1;
> + term2 = a_rhs0;
> + term3 = b_rhs1;
> + }
> +
> + if (a_rhs1 == b_rhs1)
> + {
> + term1 = a_rhs1;
> + term2 = a_rhs0;
> + term3 = b_rhs0;
> + }
> +
> + if (term1)
> + {
> + pred_info pred1;
> + pred1.pred_lhs = term1;
> + pred1.pred_rhs = integer_zero_node;
> + pred1.cond_code = NE_EXPR;
> + pred1.invert = false;
> +
> + /* We update ONE_CHAIN in place and push the new
> + term onto PREDS. So it is safe to continue
> + simplifying by breaking the K loop back into
> + the J loop which will look at the J+1 entry on
> + its next iteration. */
> + (*one_chain)[j].pred_lhs = term2;
> + (*one_chain)[k].pred_lhs = term3;
> + pred_chain new_chain = vNULL;
> + new_chain.safe_push (pred1);
> + preds->safe_push (new_chain);
> + break;
> + }
> + }
> + }
> + }
> +}
> +
> /* The helper function implements the rule 2 for the
> OR predicate PREDS.
>
> @@ -1882,6 +2003,8 @@ simplify_preds (pred_chain_union *preds, gimple
> *use_or_def, bool is_use)
> for (i = 0; i < preds->length (); i++)
> simplify_pred (&(*preds)[i]);
>
> + simplify_preds_1 (preds);
> +
> n = preds->length ();
> if (n < 2)
> return;
>
