[RFA] Improve tree-ssa-uninit.c's predicate simplification

[RFA] Improve tree-ssa-uninit.c's predicate simplification

[Jeff Law]

[-- Attachment #1: Type: text/plain, Size: 3273 bytes --]


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 :-)




[-- Attachment #2: P --]
[-- Type: text/plain, Size: 5247 bytes --]

	* 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;

Re: [RFA] Improve tree-ssa-uninit.c's predicate simplification

[Richard Biener]

On Wed, May 10, 2017 at 11:59 PM, Jeff Law <law@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;
>

Re: [RFA] Improve tree-ssa-uninit.c's predicate simplification

[Jeff Law]

On 05/11/2017 01:50 AM, Richard Biener wrote:

> 
> It actually seems to handle negation as well.  Which means it
> handles disjunctive normal form.
Negation is "handled" by allowing an individual predicate to be negated. 
  However, the predicate must still be is_neq_zero_form_p to really 
participate in expansion, normalization & simplification (and negated 
predicates do not fit that form).  Furthermore, you can only negate an 
individual predicate, not a chain of predicates.  Thus you can express 
!A, but you can not express !(A & B) AFAICT.

Thus I was left with just looking for simplifications where I could 
eliminate a common term and the result would fit in the forms supported 
by tree-ssa-uninit.c


> 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).
THe disjunctive normal form can't actually be expressed with the 
infrastructure in tree-ssa-uninit.c.  Adding it seems like a huge amount 
of work with marginal benefit.  Maybe I'm missing something.

> 
> Adding a single special-case doesn't look so useful to me.
It's certainly not something that brings us a huge benefit -- adding 
disjunctive normal form would would be a much larger change conceptually 
as well as significantly complicate the existing code and it's not clear 
it would actually be a larger benefit than just supporting the 
elimination of a common term.

Filtering of uninit warnings isn't all that interesting of a problem 
IMHO.  When this code does something useful it really means that either 
an earlier pass (usually jump threading) missed an optimization or that 
the optimization was too expensive relative to the gain.  The regression 
of uninit-pred-8 falls into both categories -- we can't detect the jump 
thread and even if we did, the cost (in terms of blocks copied) would be 
huge relative to the elimination of a single runtime branch.


> 
> 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. 
Right.  It doesn't build a tree of operations, but it does build a chain 
of normalized predicates in conjunctive normal form.   In theory, any 
transformation that works on conjunctive normal form should be 
supportable in this code.


> 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?
That's probably a larger project than I can justify tackling at this time.

FWIW, I have asked folks in the past to look into pulling out the 
predicate building and analysis bits for re-use by other passes -- that 
code is probably the most interesting long term.  That would seem to be 
the natural time to rethink some of the implementation decisions, 
particularly since improvements we made to the predicate analysis would 
likely help multiple passes rather than just filtering uninit warnings.

Jeff

Re: [RFA] Improve tree-ssa-uninit.c's predicate simplification

[Richard Biener]

On Thu, May 11, 2017 at 4:07 PM, Jeff Law <law@redhat.com> wrote:
> On 05/11/2017 01:50 AM, Richard Biener wrote:
>
>>
>> It actually seems to handle negation as well.  Which means it
>> handles disjunctive normal form.
>
> Negation is "handled" by allowing an individual predicate to be negated.
> However, the predicate must still be is_neq_zero_form_p to really
> participate in expansion, normalization & simplification (and negated
> predicates do not fit that form).  Furthermore, you can only negate an
> individual predicate, not a chain of predicates.  Thus you can express !A,
> but you can not express !(A & B) AFAICT.

Yes, because that's not normal form.  !(A && B) -> !A || !B, normalization can
cause quite some "duplication" as it simply spells out all possible combinations
where the result is true.

> Thus I was left with just looking for simplifications where I could
> eliminate a common term and the result would fit in the forms supported by
> tree-ssa-uninit.c
>
>
>> 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).
>
> THe disjunctive normal form can't actually be expressed with the
> infrastructure in tree-ssa-uninit.c.  Adding it seems like a huge amount of
> work with marginal benefit.  Maybe I'm missing something.

It seems to exactly support disjunctive normal form.

>>
>> Adding a single special-case doesn't look so useful to me.
>
> It's certainly not something that brings us a huge benefit -- adding
> disjunctive normal form would would be a much larger change conceptually as
> well as significantly complicate the existing code and it's not clear it
> would actually be a larger benefit than just supporting the elimination of a
> common term.

Adding "proper" normalization of all cases might be complicated, yes.

> Filtering of uninit warnings isn't all that interesting of a problem IMHO.
> When this code does something useful it really means that either an earlier
> pass (usually jump threading) missed an optimization or that the
> optimization was too expensive relative to the gain.  The regression of
> uninit-pred-8 falls into both categories -- we can't detect the jump thread
> and even if we did, the cost (in terms of blocks copied) would be huge
> relative to the elimination of a single runtime branch.
>
>
>>
>> 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.
>
> Right.  It doesn't build a tree of operations, but it does build a chain of
> normalized predicates in conjunctive normal form.   In theory, any
> transformation that works on conjunctive normal form should be supportable
> in this code.

might have swapped conjunctive for disjunctive, whatever - it supports exactly
one of the normal forms so my question was why it doesn't "simply"
properly normalize all predicate trees rather than having ad-hoc handling of
some special cases.

>> 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?
>
> That's probably a larger project than I can justify tackling at this time.

Pulling it out yes - but making the uninit normal form working properly?

Honestly I didn't try (otherwise you'd have seen a patch ;)) but before looking
yesterday I had the impression the code was much farther away from working
on one of the normal forms.

Richard.

> FWIW, I have asked folks in the past to look into pulling out the predicate
> building and analysis bits for re-use by other passes -- that code is
> probably the most interesting long term.  That would seem to be the natural
> time to rethink some of the implementation decisions, particularly since
> improvements we made to the predicate analysis would likely help multiple
> passes rather than just filtering uninit warnings.
>
> Jeff