When looking at the arith dialect, I find one op is conspicuous in its absence: noti, i.e. bit-wise NOT. I imagine that this was a conscious decision as I know that LLVM also lacks an op for NOT. And I know that NOT can represented as x XOR 111..., however I assume that arith is meant to be at a higher level of abstraction than LLVM and I think there is value in having a noti op. Would there be any objection to a noti op being added?
Maybe you could elaborate on what you see as value of having this operation?
Sorry, yes, I should have expanded on that point!
There are currently many bitwise op identities that are missing from the canonicalization, e.g.:
x & ~x = 0
x | ~x = 1
x ^ ~x = 1
~x & ~y = ~(x | y)
~x | ~y = ~(x & y)
etc.
I think that these would be far more naturally expressed if a not op existed. I suppose, also, that having a not op just feels right to me at this abstraction level, though I appreciate that is highly subjective.
The big problem with adding a not operator is that it makes peepholes harder in general to write, without making the cases you list easier to implement. The typical way to implement these (assuming you’re using a framework like the Matchers.h framework) is to implement a predicate like m_Complement and then implement the pattern in a natural way e.g. here is x & ~x in the comb dialect.
Take your other examples though. You don’t want to simplify just x | ~x = -1, it is more powerful to implement this on the xor form, handling x | (x^cst) = x|cst, which then recursively simplifies to -1 for the complement case. If you have a complement operator in your IR, then often you only implement one or the other.
If you’re interested in other models for arithmetic, I’d strongly suggest considering making the fully associative operators (+, *, and, or, xor, etc) be variadic. This has worked out really well for CIRCT and has defined away a number of challenging cases, e.g. by making it simple to handle (~x&y)&x as the link above does.
-Chris
Thanks a lot Chris for the detailed response, and thank you also for pointing me at CIRCT, which is highly relevant!