Re: [patch tree-optimization 1/2]: Branch-cost optimizations

[Kai Tietz <ktietz70 at googlemail dot com>]

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.

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) ...'.

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 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.

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.  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.  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.

Regards,
Kai


PS: There are several patch pending here about tree-reassoc (which
does folding on truth-bitwise operations pretty well, if it gets an
expanded view), about exactly the same subject, but here optimized for
simplest form for folding with compacted output.