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

[Kai Tietz]

2011/8/3 Michael Matz <matz@suse.de>:
> Hi,
>
> On Wed, 3 Aug 2011, Kai Tietz wrote:
>
>> > 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.
>>
>> What you mean by existing machinery for negate expression here?
>
> tree-reassoc can handle chains of NEGATE/PLUS/MINUS/MULT/DIV expressions,
> including undistribution (A*X + B*X -> (A+B)*X).  It does have some
> deficiencies with mixed chains (e.g. mixture of PLUS and MULT
> expressions).
>
> Now, in the usual mathematical parlance we have these correspondences:
>  NOT == NEGATE
>  AND == MULT
>  IOR == PLUS
> hence, if you extend the existing reassoc machinery to first deal nicely
> with mixed chains and then handle NOT/AND/IOR like their arithmetic
> counterparts you will have improved reassoc for arithmetic operations
> _and_ extended it to also handle logical operation chains.  Without
> hacking a completely different way of walking and collection operands for
> logicals in parallel to the one for arithmetics.
>
>> This machinery doen't work in this case
>
> That's why you have to extend it.

The issue about this machinery is that it assumes that the statement
itself gets transformed, but for normalized form of invert of bitwise
operations it is essential to perform invert operation on the
operands, too.

>> Eg: the case (~(a | c) & (b & ~d))  would be expanded (by code in
>> patch) to ~a & ~c & b & ~d.
>
> That's what I mean with better handling of mixed chains.  -(a+b) is
> already (sometimes) rewritten into -a + -b (see negate_value).  That's
> just slightly different from rewriting ~(a|b) into ~a & ~b.

Yes, it affects just one operand. And its weakness is that a (which
might be a more complex statement) doesn't get folded for the negate
operation here.  Eg.  a = 1 - d; c = - (a + b); should become d - b -
1 and optimized form of (d - (b + 1)).

But AFAIR the code the thing is different what break_up_substract
does.  It modifies (a - b) -> a + (-b),  which is for sure worth to
simplify and ease arithmetic plus optimization.  But doesn't match the
point you are talking about.

>> 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.
>
> And that would be done by undistribute_ops_list, if it were properly
> extended.
>
>> 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.
>
> That's why you do this whole excercise in tree-reassoc, where it indeed
> belongs.  My point is that you should extend the existing means to support
> your operations, instead of implementing a similar-but-different approach
> in parallel.

As I tried to pointed out before is the approach in reassoc only well
working for single statements (not to talk here about non-single-used
statements, which seems to be something my patch needs to handle
better - a Richard said, it might walks statements so multiple times).
 But for an invert the operands and the expression-codes are changing,
too.
As later reassoc pass just walk the tree and combines simliar
operation-codes in its vector by rank, and later optimization just
happens within this range,  it is essential to feed this vector with
proper (normalized) expression-codes.

>> 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.
>
> What you descrive as "flattening" is actually building a normal form.
> reassoc uses a vector of operand extries to hold such normal form (as
> said, not yet dealing with mixed chains).  linearize_expr_tree does the
> flattening, and you would have to extend it (and its associated helper
> routines) to handle mixed chains and then you logical operations.

Well, it does this in a very limited approach and is strictly bound to
an underlying statement.

> Once a linearized array of operands (possibly of level two to handle mixed
> chains) exists undistribute_ops_list and optimize_ops_list will optimize
> those operands again, and rewrite_expr_tree will produce statements
> implementing the so optimized operand list.  You will have to extend that
> too for your logical operations (and possibly compares).
>
>
> Ciao,
> Michael.

Actually it might be also a way to rewrite reassociation pass in a way
that it just operates on normalized predicated trees made out of the
orignal tree.  Operates on it, and then write it out in a denormalized
form.  Such a tree would need information flags for inverted, negated,
code, operands (maybe also altered), Which means that such a tree gets
easily more complex.
Nevertheless the creation of final result out of a normalized
predicated tree would mean a re-write of tree anyway - even if there
might be in some rare cases the opportunity to reuse present
statements and avoid their rewriting.

Regards,
Kai