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.

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

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

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

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.

Reply via email to