This is an archive of the discontinued LLVM Phabricator instance.

Unsigned saturation subtraction canonicalization [Instcombine part]
ClosedPublic

Authored by yulia_koval on Dec 20 2017, 11:55 PM.

Details

Summary

This is the instcombine part of unsigned saturation canonicalization patch.(Backend patches already commited: https://reviews.llvm.org/D37510, https://reviews.llvm.org/D37534)

It converts unsigned saturated subtraction patterns to pattern, recognized by backend:
(a > b) ? a - b : 0 -> ((a > b) ? a : b) - b)
(b < a) ? a - b : 0 -> ((a > b) ? a : b) - b)
(b > a) ? 0 : a - b -> ((a > b) ? a : b) - b)
(a < b) ? 0 : a - b -> ((a > b) ? a : b) - b)
((a > b) ? b - a : 0) -> - ((a > b) ? a : b) - b)
((b < a) ? b - a : 0) -> - ((a > b) ? a : b) - b)
((b > a) ? 0 : b - a) -> - ((a > b) ? a : b) - b)
((a < b) ? 0 : b - a) -> - ((a > b) ? a : b) - b)

Diff Detail

Event Timeline

yulia_koval created this revision.Dec 20 2017, 11:55 PM
yulia_koval added reviewers: zvi, spatel, DavidKreitzer.
yulia_koval removed subscribers: spatel, zvi, DavidKreitzer.
zvi added inline comments.Dec 21 2017, 4:46 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
922

"subus" might be too X86-specific in a target-independent pass? Maybe a better function name would be something like "canonicalizeSaturatedSubtract"?

test/Transforms/InstCombine/unsigned_saturated_sub.ll
5

Missing vector tests?

Fixed comments,

zvi added a comment.Dec 23 2017, 11:45 PM

LGTM, but would like to see a more seasoned InstCombine contributer take a look before giving a final ok

spatel added inline comments.Dec 28 2017, 8:03 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
579–582

Let's avoid 'psubus' in these comments too. Use 'unsigned saturated subtraction' or something generic.

592–593

We should not create an unnecessary instruction here. We just want to swap the operands of the sub when 'IsNegative' is true?

  %cmp = icmp ugt i8 %lhs, %rhs
  %sub = sub i8 %rhs, %lhs
  %r = select i1 %cmp, i8 %sub, i8 0
=>
  %cmp2 = icmp ugt i8 %lhs, %rhs
  %sel1 = select i1 %cmp2, i8 %lhs, i8 %rhs
  %r = sub i8 %rhs, %sel1

https://rise4fun.com/Alive/dcC

test/Transforms/InstCombine/unsigned_saturated_sub.ll
21–36

The '256' and '512' tests are low-value. If one vector type works, we can generally assume that all vector types work in IR.

I'd like to see at least 1 test for each of the 8 formulas shown in the summary. A comment with that formula above the test would also make it clearer what's changing in each test. You can alternate scalar and vector types to provide more coverage.

yulia_koval added inline comments.Dec 28 2017, 8:26 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
592–593

Right, it is legal just to swap. The question is - do we consider the result with swapped operands a cannonical form?
%cmp2 = icmp ugt i8 %lhs, %rhs
%sel1 = select i1 %cmp2, i8 %lhs, i8 %rhs
%r = sub i8 %rhs, %sel1

rhs - (lhs > rhs ? lhs : rhs) <=> rhs - umax(lhs,rhs)

While we currenty consider cannonical only these forms:
umax(a,b) - b -> subus(a,b)
a - umin(a,b) -> subus(a,b)

So, what do you think, where should we do the transformation b - umax(a,b) => -(umax(a,b) - b) ?
Or whether we should handle -psubus(a,b) pattern at all?

spatel added inline comments.Dec 28 2017, 8:34 AM
lib/Transforms/InstCombine/InstCombineSelect.cpp
592–593

I don't understand the question. Instcombine is going to optimize this:

define i8 @subneg(i8 %x, i8 %y) {
  %a = sub i8 %x, %y
  %b = sub i8 0, %a
  ret i8 %b
}

So we don't have a choice here, right? The backend has to recognize that pattern. The important part (I think - let me know if I'm missing something) is that we have the canonical min/max pattern where the cmp and select operands are the same because that is recognized by value tracking:

%cmp2 = icmp ugt i8 %lhs, %rhs
%sel1 = select i1 %cmp2, i8 %lhs, i8 %rhs

Fixed the comments

spatel added a comment.EditedFeb 2 2018, 2:45 PM

Some tests were not actually providing coverage for this code, so I checked them in and fixed them - rL324143.
I think this is correct now and tested properly (although you might want to add more tests to check UGE/ULE preds - just noticed that I forgot about that). Please rebase and address the small code/comment suggestions.

lib/Transforms/InstCombine/InstCombineSelect.cpp
541–542

This doesn't read clearly to me. How about:
Transform patterns such as: (a > b) ? a - b : 0
into: ((a > b) ? a : b) - b)
This produces a canonical max pattern that is more easily recognized by the backend and converted into saturated subtraction instructions if those exist.
There are 8 commuted/swapped variants of this pattern.

552–554

Sink these declarations down closer to their use.

579–584

It's easier to follow the logic if you do all of the sub matching in one place, so sink the hasOneUse check down here:

// We need a sub with the same operands as the compare.
bool SelOnRight;
if (match(TrueVal, m_OneUse(m_Sub(m_Specific(CmpL), m_Specific(CmpR)))))
  SelOnRight = false;
else if (match(TrueVal, m_OneUse(m_Sub(m_Specific(CmpR), m_Specific(CmpL)))))
  SelOnRight = true;
else
  return nullptr;
spatel added inline comments.Feb 2 2018, 2:47 PM
lib/Transforms/InstCombine/InstCombineSelect.cpp
552–554

Also, it's easier to read if your variable names match the comments:

Value *A = ICI->getOperand(0);
Value *B = ICI->getOperand(1);

Thank you for your comments, fixed them.

spatel accepted this revision.Feb 5 2018, 6:13 AM

LGTM - see inline for small bits.

Thanks for getting this fixed from codegen to IR!

lib/Transforms/InstCombine/InstCombineSelect.cpp
586

This comment isn't correct. We wouldn't duplicate the existing sub; we just wouldn't be able to eliminate it. So the transform could create more instructions than it removes which we usually try to avoid in this pass.

590–591

Here and above, please put a period at the end of a sentence:
http://llvm.org/docs/CodingStandards.html#commenting

This revision is now accepted and ready to land.Feb 5 2018, 6:13 AM

Fixed last comments. Thank you for your help, could you please commit it for me?

This revision was automatically updated to reflect the committed changes.