[RFA] Improve tree-ssa-uninit.c's predicate simplification
Jeff Law
law@redhat.com
Wed May 10 22:40:00 GMT 2017
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.
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.
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 :-)
-------------- next part --------------
* 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;
More information about the Gcc-patches
mailing list