[LLVMdev] [PATCH] Lost instcombine opportunity: "or"s of "icmp"s (commutability)

[Edward Lee]

Oh. Seems like you can get something similar by running -instcombine
twice but stick in a -reassociate in between the two. ;)

Hmm.. I wonder how much faster/smaller would instcombine get without
any associative/commutative code compared to running it twice with
-reassociate.

Ed

On Wed, Oct 8, 2008 at 5:58 PM, Edward Lee <eslee3 at uiuc.edu> 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).
>
> 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]
>
> Ed
> 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..
>>
>> Before:
>> %or.eq8.gt10 = .. ; [uses=1]
>> %res = or %or.eq8.gt10, %ne5 ; original instruction
>>
>> After:
>> %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?)
>>
>> Ed
>>
>
>
>
> --
> Ed
>



-- 
Ed