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.
