[llvm-dev] [IR canonicalization] 6 ways to choose {-1,0,1}

[Sanjay Patel via llvm-dev]

Hi Nemanja -

No, I didn't make any IR transforms based on this, but I agree we should
canonicalize the IR. Like you, I was trying to improve the codegen (for x86
in particular), but that patch was growing every time I found a new way to
express this operation!

I'm going to rule out option #4 because #3 is better (always prefer a zext
over a sext for bit-tracking purposes). I'd also kill option #5 because it
doesn't offer any particular advantage, but needs more instructions than a
version with select. #6 might be the best option for codegen, but it has
more instructions and a subtract seems harder to reason about in IR than
select-of-constants.

If you agree with the above reasoning, then that brings us to a choice
about select vs. zext that goes back to the questions in:
https://reviews.llvm.org/D24480

I'm now in favor of creating more selects in IR (ie, abandon that patch and
reverse the other pattern). We used to treat selects in IR as more complex
operations than basic logic ops, but the backend has improved enough that
we probably don't need to do that anymore.

A few more DAGCombiner transforms in foldSelectOfConstants() are needed to
ensure that if we pick selects in IR that we will transform that to
zext/sext/logic when the select has -1/0/1 constants. This would probably
happen under an expanded version of the
TLI.convertSelectOfConstantsToMath() target hook.

If anyone agrees with me this far...the choice is down to #1 or #2. This
could be decided by putting the "larger" (signed or unsigned?) constant on
the left, or we just let that go and expect the backend to deal with it.


On Sun, Jul 9, 2017 at 11:28 PM, Nemanja Ivanovic <nemanja.i.ibm at gmail.com>
wrote:

> Hi Sanjay,
> I'm wondering if there was any progress on this since there don't appear
> to have been any responses. I don't have a particularly strong opinion on
> which form we should canonicalize to, but I do think we should settle on
> one.
>
> I've recently written a patch (not committed yet) for codegen that
> basically tries detecting all of these on the SDAG. I'd be quite happy if I
> can simplify that patch before committing.
>
> Nemanja
>
> On Sat, Jul 1, 2017 at 8:45 PM, Sanjay Patel via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> I'm looking at the output of memcmp() expansion (D34904), and I noticed
>> that there are many ways to produce the common positive/zero/negative
>> comparison result in IR.
>>
>> For the following 6 functionally equivalent C source functions, we
>> produce 6 different versions of IR which leads to 6 different asm outputs
>> for x86. Which of these should we choose as canonical IR form?
>>
>> 1. Two selects
>> int zero_negone_one(int x, int y) {
>>   if (x == y) return 0;
>>   if (x < y) return -1;
>>   return 1;
>> }
>>
>> define i32 @zero_negone_one(i32, i32) {
>>   %3 = icmp eq i32 %0, %1
>>   %4 = icmp slt i32 %0, %1
>>   %5 = select i1 %4, i32 -1, i32 1
>>   %6 = select i1 %3, i32 0, i32 %5
>>   ret i32 %6
>> }
>>
>>
>> 2. Two selects, but different
>> int zero_one_negone(int x, int y) {
>>   if (x == y) return 0;
>>   if (x > y) return 1;
>>   return -1;
>> }
>>
>> define i32 @zero_one_negone(i32, i32) {
>>   %3 = icmp eq i32 %0, %1
>>   %4 = icmp sgt i32 %0, %1
>>   %5 = select i1 %4, i32 1, i32 -1
>>   %6 = select i1 %3, i32 0, i32 %5
>>   ret i32 %6
>> }
>>
>>
>> 3. Select and zext
>> int negone_one_zero(int x, int y) {
>>   if (x < y) return -1;
>>   if (x > y) return 1;
>>   return 0;
>> }
>>
>> define i32 @negone_one_zero(i32, i32)  {
>>   %3 = icmp slt i32 %0, %1
>>   %4 = icmp sgt i32 %0, %1
>>   %5 = zext i1 %4 to i32
>>   %6 = select i1 %3, i32 -1, i32 %5
>>   ret i32 %6
>> }
>>
>>
>> 4. Select and sext
>> int negone_zero_one(int x, int y) {
>>   int sel = x < y ? -1 : 0;
>>   if (x > y) return 1;
>>   return sel;
>> }
>>
>> define i32 @negone_zero_one(i32, i32) {
>>   %3 = icmp sgt i32 %0, %1
>>   %4 = icmp slt i32 %0, %1
>>   %5 = sext i1 %4 to i32
>>   %6 = select i1 %3, i32 1, i32 %5
>>   ret i32 %6
>> }
>>
>>
>> 5. Subs and shifts
>> int neg101_sub_shifty(int x, int y) {
>>   int r = (x - y) >> 31;
>>   r += (unsigned)(y - x) >> 31;
>>   return r;
>> }
>>
>> define i32 @neg101_sub_shifty(i32, i32) {
>>   %3 = sub nsw i32 %0, %1
>>   %4 = ashr i32 %3, 31
>>   %5 = sub nsw i32 %1, %0
>>   %6 = lshr i32 %5, 31
>>   %7 = add nsw i32 %4, %6
>>   ret i32 %7
>> }
>>
>>
>> 6. Zexts and sub
>> int neg101_cmp_sub(int x, int y) {
>>   return (x>y) - (x<y);
>> }
>>
>> define i32 @neg101_cmp_sub(i32, i32) {
>>   %3 = icmp sgt i32 %0, %1
>>   %4 = zext i1 %3 to i32
>>   %5 = icmp slt i32 %0, %1
>>   %6 = zext i1 %5 to i32
>>   %7 = sub nsw i32 %4, %6
>>   ret i32 %7
>> }
>>
>>
>> https://godbolt.org/g/UnM9H7
>>
>> Show these are logically equivalent:
>> http://rise4fun.com/Alive/b4D
>>
>> Recent patch related to this pattern:
>> https://reviews.llvm.org/D34278
>>
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170710/c88b966f/attachment.html>