On Thu, Nov 10, 2011 at 11:49 AM, Kai Tietz <ktiet...@googlemail.com> wrote: > 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.
AND [0] ~ (a != 0) [1] ~ (b != 0) just because I chose to draw simple pictures does not mean a more complex one would be not supported (we'd want general comparisons anway). Nowhere did I specify that it should only work on boolean variables. >>> 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. See above. >>> 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 >
