llvm dev - Oct 2012 - [LLVMdev] 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

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation

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.

-Chris

On 10/17/2012 11:57 AM, Chris Lattner wrote:
>
> 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.
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

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, 
hosted by The Linux Foundation