[LLVMdev] [PATCH] Lost instcombine opportunity: "or"s of "icmp"s (commutability)
eslee3 at uiuc.edu
Wed Oct 8 15:58:52 PDT 2008
Here's an initial stab, but I'm not too happy about the temporarily
adding new instructions then removing it because returning it will
have it added back in to replace other uses. I also added a couple
test cases pass with the new InstructionCombining changes (the old
code only passes one of the added tests).
Also, this change exposes some simplification for
test/Transforms/InstCombine/2006-05-06-Infloop.ll. The original code
truncates two i32 values to i8 and eventually ORs them together. The
patch has it optimized to OR the two values first then truncate a
%tmp264not = xor i8 %tmp264, -1 ; <i8> [#uses=1]
%tmp212 = trunc i32 %iftmp.36.0 to i8 ; <i8> [#uses=2]
%tmp265 = trunc i32 %tmp261 to i8 ; <i8> [#uses=1]
%tmp266 = or i8 %tmp212, %tmp264not ; <i8> [#uses=2]
%tmp268 = or i8 %tmp266, %tmp265 ; <i8> [#uses=1]
%tmp264not = xor i8 %tmp264, -1 ; <i8> [#uses=2]
%a.c45 = or i32 %iftmp.36.0, %tmp261 ; <i32> [#uses=1]
trunc i32 %a.c45 to i8 ; <i8>:0 [#uses=1]
%tmp268 = or i8 %0, %tmp264not ; <i8> [#uses=1]
On Wed, Oct 8, 2008 at 11:59 AM, Edward Lee <eslee3 at uiuc.edu> wrote:
> instcombine can handle certain orders of "icmp"s that are "or"ed together:
> x != 5 OR x > 10 OR x == 8 becomes..
> x != 5 OR x == 8 becomes..
> x != 5
> However, a different ordering prevents the simplification:
> x == 8 OR x > 10 OR x != 5 becomes..
> %or.eq8.gt10 OR x != 5
> and that can't be simplified because we now have an "or" OR "icmp".
> What would I need to implement to restore the commutative property?
> Perhaps a first stab would be to take (A|B)|C create two binaryOp A|C
> and B|C and recursively call visitOr on each of them to see if they
> simplify. Using the example above..
> %or.eq8.gt10 = .. ; [uses=1]
> %res = or %or.eq8.gt10, %ne5 ; original instruction
> %or.eq8.gt10 = .. ; [uses=0]
> %or.eq8.ne5 = %ne5 ; instcombine recursively simplified this [uses=1
> or 0 see next]
> %res = or %or.eq8.ne5, %gt10 ; even better: %res = or %ne5, %gt10
> The recursive call of A|C would also let C see further "or"s, so if A
> is actually composed of (a1|a2), it could potentially try to simplify
> a1|C and a2|C.
> I'm not entirely sure right now, but potentially there could be issues
> of creating too many additional "or" instructions. E.g., %or.eq.8.gt10
> originally had more than 1 use.
> Am I on the right track (or does LLVM already support this in another
> optimization pass?)
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 3090 bytes
Desc: not available
More information about the llvm-dev