Instruction combiner: converting arithmetic into bit operations

Hi,
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?

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.

Any comments?

-Krzysztof

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.

-Chris

I looked in Reassociate.cpp and I saw that it internally converts shifts into multiplications. I think it would be worthwhile to at least investigate this possibility further.

-K

Sure, go for it!

-Chris