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 > 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 > 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. > Sure we can move the BC-optimization into a separate > pass. As you and Richard already have explained, this would be indeed > in some cases better, as there is more freedom in operating on > gimple-statements. This makes for sure sense. > > But the logic itself we need in normal sequence-representation for > folding seems not to be that what we need for BC.\ Sure, it's exactly the same data structure we can use. > For general gimple > passes we want to have compact form on linear-sequence without > sub-sequences and we want compact final-representation in output. In > BC we have slightly different requirements. We need a > comparison-expanded form and of course with sub-sequences to do > split-up right dependent on the actual branch-costs. You can trivially split up a predicate combination into multiple ones. Richard.
