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

[Michael Matz]

Hi,

On Wed, 3 Aug 2011, Kai Tietz wrote:

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

Yes, and that is what break_up_subtract_bb and friends do for negates.  In 
particular if the defining statement is of the right type itself (right 
now simply a PLUS) it propagates the negate into the operands of that 
operation.  Extend it to handle AND/IOR/NOT and you're a step further.

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

No, it doesn't.

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

The folding you're talking about is done by undistribute_ops_list, 
optimize_ops_list and repropagate_negates.

I'm asking you to follow the same general scheme of tree-ssa-reassoc which 
is:
1) enabling transformations to make collecting operands easier
   (this possibly changes and adds statements, that's the breakup_subtract
   things)
2) collect operands of operation chains
   (this would sometimes require remembering some context like top
   level and second level operation in your case)
3) optimize that list of operands
4) transform this list into statements again
5) undo transformations done in 1) if they turned out to be
   unprofitable

I'm fairly certain that the transformations you want can be done with this 
scheme.

In particular (as said multiple times) you are missing step (5) even 
though you unconditionally do step (1).  And you don't do steps 2-4 at 
all.

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

I'm not sure what you think my point is.  It is: reuse existing schemes to 
do things, extending them as necessary to support your usecases.


> As I tried to pointed out before is the approach in reassoc only well
> working for single statements

That's completely wrong.  reassoc was precisely implemented to handle a 
chain of arithmetic operations, i.e. multiple statements.

> But for an invert the operands and the expression-codes are changing,
> too.

Right, that's why you (possibly) might want to handle chains of mixing 
AND/IOR operations, though I don't see those happening in your testcases.  
After the negates are folded into atomics (i.e. negates of AND and IOR are 
folded into operands) you always have a chain of either AND or IOR (with 
the atomics being negated or not).  That can trivially be handled with the 
currently implemented scheme.

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

That's step (1) above, and for arithmetics done by break_up_subtract.

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

Right, but ultimately it's the way forward.  Though, as I said, right now 
your testcase only have one common reducing operation.

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

The reusing of statements in tree-reassoc is merely an artifact, it's not 
an inherent design decision.


Ciao,
Michael.