[LLVMdev] Instruction combiner: converting arithmetic into bit operations

Chris Lattner clattner at apple.com
Wed Oct 17 09:57:50 PDT 2012

On Oct 17, 2012, at 8:31 AM, Krzysztof Parzyszek <kparzysz at codeaurora.org> wrote:
> I've noticed that for a while, the instruction combiner would convert certain arithmetic operations (like + or *) into bit-manipulation operations.  Specific example I have in mind is converting "2*x+1" into "(x<<1)|1".  What is the intention of doing this?

We want a single canonical form for operations that do the same thing.  2*x+1 and 2*x|1 produce the same result, so we want to canonicalize one to the other.  We've chosen (admittedly somewhat arbitrarily) to use | instead of + for the canonical form, because | is strictly simpler: there is no carry ripple.  This means that things like SimplifyDemandedBits and other bit propagation problems are simpler.

> The reason I ask is that this kind of transformation makes it harder for later code to analyze it.  In general, it's a lot easier to reason about arithmetic operations, when they are not interleaved with bit operations.  For example, if we subtract 1 in the example above, the expression (A+1)-1 can be simplified to A without having to know that A is 2*x.  This is not possible to do in case of (B|1)-1 without knowing that B has the lowest bit 0.
> In my opinion it would be better to leave arithmetic expressions as they are in the bitcode, and leave conversions like the one from 2^N*x to x<<N to the backends.

We do want one canonical form, but it would be an interesting experiment to see what happens when we turned 'or' into 'add' instead of the other way around.  We'd have to make sure that simplifydemandedbits and friend can handle the add case as well as the or case, but I think it is already close to smart enough to do that.


More information about the llvm-dev mailing list