2011/8/3 Michael Matz <m...@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. 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
