On Thu, May 11, 2017 at 4:07 PM, Jeff Law <l...@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
