This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [patch tree-optimization 1/2]: Branch-cost optimizations
On Wed, Nov 9, 2011 at 10:09 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/11/9 Jeff Law <law@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.