[LLVMdev] [PATCH] Lost instcombine opportunity: "or"s of "icmp"s (commutability)
nicholas at mxc.ca
Wed Oct 8 23:39:12 PDT 2008
Edward Lee wrote:
> 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).
Hi Edward. I was wondering whether your optimization could be
implemented using the AssociativeOpt framework already in InstCombine?
It has a built-in mini-reassociate just for this occasion.
> 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
> single value.
> %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?)
> LLVM Developers mailing list
> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu
More information about the llvm-dev