LLVM Discussion Forums

Reducing complements in pattern rewriter

So I want to determine the following:
and(..., x, not(x)) -> and(..., 0)
So in this case, given two constants, see if x and not(x) exist, and if they do, drop them and add a zero in the rewrite.

A simple manner of approaching this is getting their constant values value1, value2 and see if value1 & value2 == 0. However, this does require comparing all constants. So my question: Is there a better way to do this? Are there any guarantees about x and not(x) being next each other or something else that I’m missing?

Documentation and examples very welcome. Thanks!

There’s probably some useful interaction with the ‘commutative’ concept here and the pattern rewrite infrastructure. Ideally, for commutative operations, we should be able to specify a rewrite rule like what you have above and efficiently match it. This is a place where BDD representations have some native advantages.

Yeah, the builtin canonicalization stuff won’t do anything like that. I am also slightly opposed to make it it tooo fancy (certainly BDD’s would be a step too far :-). I’d recommend something like having a SmallPtrSet, doing a scan over the operands looking for not’s tracking the not’d operands in the set, then do a second pass to see if any of the un-negated values exist.

There are fancier things that can be done (e.g. BDDs, breaking things down to bitwise operations to drop logic on individual bits etc) but that should a dedicated pass, not part of the canonicalization pass.

I agree with this. The above transformation with the smallPtrSet might even be too much.

Yeah. I’d probably just do the binary case (x&~x) and leave the rest for more powerful dedicated optimization pass.

So I began writing something simple, thinking of constant values such that x1 & x2 == 0.

I also realized that this case is already taken care of by constant folding, followed by annulment. For non-constants, is it possible to determine the not(x) given an x through some sort of function call?

The concern here is that we only want canonicalization patterns to include simple and local changes that “hill climb” (in a lattice theory sense) towards a local maxima. This isn’t the right place to put more complex analysis or things that require complicated cost models. Such things should go into their own (possibly RTL dialect specific) analsys/transformation pass.