[patch tree-optimization]: Improve reassociation pass for bitwise-operations

[Richard Guenther]

On Wed, Aug 3, 2011 at 3:32 PM, Kai Tietz <ktietz70@googlemail.com> wrote:
> 2011/8/3 Michael Matz <matz@suse.de>:
>> Hi,
>>
>> On Tue, 2 Aug 2011, Kai Tietz wrote:
>>
>>> this patch improves the ability of reassociation pass to simplifiy
>>> more complex bitwise-binary
>>> operations with comparisons.  We break-up for this patch statements
>>> like (X | Y) != 0 to X != 0 | Y != 0,
>>> and (X | Y) == 0 to expanded X == 0 & Y == 0.
>>> Additionally we expand logical-not expressions like ~(A & B) -> ~A |
>>> ~B, ~(A & B) -> ~A | ~B, and
>>> ~(A ^ B) -> A ^ ~B.  These expansion are just temporary for this pass
>>> and getting later by fold
>>> reversed again back to their original form.
>>
>> Implement all of this in the normal reassoc machinery that already exists.
>> Don't implement your own walker (which btw is superlinear because you
>> recurse into both operands).  If no simplifications were possible you have
>> to fold back the NOTs into the shorter sequences again, which conveniently
>> reassoc already can do for negates and PLUS/MINUS chains.
>>
>> Hence extend the existing support for arithmetic operations to logical
>> operations.
>>
>>
>> Ciao,
>> Michael.
>
> What you mean by existing machinery for negate expression here?  This
> machinery doen't work in this case and additionally doesn't provide
> the opportunity to do a complete reassociation rewrite of
> bitwise-expression-chains.
>
> Eg: the case (~(a | c) & (b & ~d))  would be expanded (by code in
> patch) to ~a & ~c & b & ~d.
> This intermediate result is good to inspect doubles, or inverted optimizations.
> On rebuilding of tree the result gets transformed (or should) to ~(a |
> c | d) & b.

It depends on the context whether a conjunctive or a disjunctive normal
form is what you want.  As you are mixing two operation kinds reassoc
isn't the perfect place to deal with this (yet).

You don't seem to stop when single-use chains end (which is where
reassoc will give up) and even visit stmts multiple times that way.
You need to at least do this "unfolding" in a lot more controlled manner.

Richard.

> This opportunity is just present because we unwinded the intial tree.
> Classical folding pass isn't able to actual detect or do that on
> gimpled-trees.
>
> For comparisons it is somewhat the same, just that
> bitwise-binary-chain is then for sure boolean-typed.  So as example:
> (a == 1 & b != 0) & ~(a <= 1 | b == 0) would be transformed by the
> code in patch to a == 1 & b != 0 & a > 1 & b != 0. So the final tree
> is able to transform this into a >=1 & b != 0.  Again without
> expansion and flattening of bitwise tree, we aren't able to detect and
> combine that.
>
> I thought about using the same mechanism as for negate, but it doesn't
> work and has major weaknesses for bitwise-binary operations. The
> negate logic is here a predicate, but the unwinding and flattening of
> bitwise trees isn't a predicate.
>
> Regards,
> Kai
>