2011/11/10 Richard Guenther <richard.guent...@gmail.com>: > On Wed, Nov 9, 2011 at 10:09 PM, Kai Tietz <ktiet...@googlemail.com> wrote: >> 2011/11/9 Jeff Law <l...@redhat.com>: >>> -----BEGIN PGP SIGNED MESSAGE----- >>> Hash: SHA1 >>> >>> On 11/07/11 15:36, Richard Guenther wrote: >>> >>>> >>>> Yes. tree-affine does this for a sum of expressions of the form a >>>> + b * c. It collects such sum, optimizes it (and you can >>>> add/subtract or scale these things) and re-emit the new simplified >>>> form. >>> Kai, what what were the concerns with this kind of approach? >>> Richard's suggestion seems sound to me. From a maintenance standpoint >>> reusing/extending the tree-affine code seems like a better route. >>> jeff >> >> Well, such a comparison-logic-folder helper - like affine-tree for >> add/subtract/scale) - is for sure something good for inner gimple >> passes building up new logic-truth expressions, but such a pass >> doesn't meet requirements need to fold for BC optimization AFAICS. > > tree-affine is not a "affine folder" either. It is an on-the side > representation > of a sum of affine components that you can operate on (for example, > you can simplify it). > >> The difference is that for BC we don't want to fold at all. Also it >> isn't necessarily "simplified" statement we want. For example 'if ((a >> | b) == 0 & ...) ...'. If the costs of such pattern '(a | b) == 0' >> are too high, we want to representation it instead as 'if (a == 0) if >> (b == 0) ...'. > > The "affine tree" of (a | b) == 0 is > > AND > [0] ~a > [1] ~b
Well, this is just true, if a and b are boolean-typed. But we need to handle also elements with different types, which are always comparisons. I have choosen exactly this sample, as it works on any integral-type. So using predicate "not" is not that what we need here in general. We have indeed to make up element-chains via comparison to operate on. >> So for BC optimization we need to have a fully compare-expanded >> sequence of bitwise-operations including for sub-sequences. For normal >> folding we don't need sub-sequence expansion in most cases. > > the predicate infrastructure isn't meant to be for folding - it is mean > to be a data structure that is well suited for operating on predicate > expressions in all ways (well, including folding). > >> The cause why we need for BC fully compare-expanded sequence I try to >> demonstrate on the following example. >> >> We have an condition 'if ((A | B) == 0 && C == 0) ...' where the >> joining of A == 0 and C == 0 would be profitable by BC-optimization, >> but the join of A != 0 and B != 0 isn't. >> So we do - as my patch does - first an expand to element >> comparison-sequence view. > > AND > [0] ~A > [1] ~B > [2] ~C Again, not true, as ~ works only on boolean-typed invariant elements A, B, and C. The attribute logical not is only of interest within a fina operand of an invariant argument of an element. It is no predicate for the bitwise-binary-chain itself. If we have a bitwise-chain with different type as boolean, an "inverse" might be a candidate for predicates, but we try to operate here on conditions. >> So we get for it the transformed form 'if (A == 0 && B == 0 && C == 0)'. >> Now we can begin to search for valid patterns in the condition for >> joining by searching from left-to-right for a profitable pattern. So >> we end-up with final statement 'if ((A | C) == 0 && C)' > >> So as conclusion to answer your question about tree-affine >> implementation. > > It's exactly what you implemented (well, sort-of). You just did not > properly abstract it away. I know, but this can be done. Kai
