Unsigned saturation subtraction canonicalization [Instcombine part]

[yulia_koval]

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)

[zvi]

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?

[yulia_koval]

Fixed comments,

[zvi]

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

[spatel]

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]

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]

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

[yulia_koval]

Fixed the comments

[spatel]

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]

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);

[yulia_koval]

Thank you for your comments, fixed them.

[spatel]

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

[yulia_koval]

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

lib/Transforms/InstCombine/InstCombineSelect.cpp

if (C2Log > C1Log) {
     V = Builder.CreateZExtOrTrunc(V, Y->getType());
 
   if (NeedXor)
     V = Builder.CreateXor(V, *C2);
 
   return Builder.CreateOr(V, Y);
 }
 
+/// 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.
+/// TODO: Also support a - UMIN(a,b) patterns.
+static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI,
+                                            const Value *TrueVal,
+                                            const Value *FalseVal,
+                                            InstCombiner::BuilderTy &Builder) {
+  ICmpInst::Predicate Pred = ICI->getPredicate();
+  if (!ICmpInst::isUnsigned(Pred))
+    return nullptr;
+
+  // (b > a) ? 0 : a - b -> (b <= a) ? a - b : 0
+  if (match(TrueVal, m_Zero())) {
+    Pred = ICmpInst::getInversePredicate(Pred);
+    std::swap(TrueVal, FalseVal);
+  }
+
+  if (!match(FalseVal, m_Zero()))
+    return nullptr;
+
+  Value *A = ICI->getOperand(0);
+  Value *B = ICI->getOperand(1);
+
+  if (Pred == ICmpInst::ICMP_ULE || Pred == ICmpInst::ICMP_ULT) {
+    // (b < a) ? a - b : 0 -> (a > b) ? a - b : 0
+    std::swap(A, B);
+    Pred = ICmpInst::getSwappedPredicate(Pred);
+  }
+
+  assert((Pred == ICmpInst::ICMP_UGE || Pred == ICmpInst::ICMP_UGT) &&
+         "Unexpected isUnsigned predicate!");
+
+  bool IsNegative = false;
+
+  // Notice negative form of unsigned saturated subtraction ((a > b) ? b - a :
+  // 0).
+  if (match(TrueVal, m_Sub(m_Specific(B), m_Specific(A)))) {
+    IsNegative = true;
+  } else if (!match(TrueVal, m_Sub(m_Specific(A), m_Specific(B))))
+    return nullptr;
+
+  // If sub is used anywhere else, we wouldn't be able to eliminate it
+  // afterwards.
+  if (!TrueVal->hasOneUse())
+    return nullptr;
+
+  // All check passed, convert to cannonical unsigned saturated
+  // subtraction form sub(max()).
+  // (a > b) ? a - b : 0 -> ((a > b) ? a : b) - b)
+  Value *Sel = Builder.CreateSelect(Builder.CreateICmp(Pred, A, B), A, B);
+  Value *Sub =
+      IsNegative ? Builder.CreateSub(B, Sel) : Builder.CreateSub(Sel, B);
+  return Sub;
+}
+
 /// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single
 /// call to cttz/ctlz with flag 'is_zero_undef' cleared.
 ///
 /// For example, we can fold the following code sequence:
 /// \code
 ///   %0 = tail call i32 @llvm.cttz.i32(i32 %x, i1 true)
 ///   %1 = icmp ne i32 %x, 0
 ///   %2 = select i1 %1, i32 %0, i32 32
Instruction *InstCombiner::foldSelectInstWithICmp(SelectInst &SI,
   }
 
   if (Value *V = foldSelectICmpAndOr(ICI, TrueVal, FalseVal, Builder))
     return replaceInstUsesWith(SI, V);
 
   if (Value *V = foldSelectCttzCtlz(ICI, TrueVal, FalseVal, Builder))
     return replaceInstUsesWith(SI, V);
 
+  if (Value *V = canonicalizeSaturatedSubtract(ICI, TrueVal, FalseVal, Builder))
+    return replaceInstUsesWith(SI, V);
+
   return Changed ? &SI : nullptr;
 }
 
-
 /// SI is a select whose condition is a PHI node (but the two may be in
 /// different blocks). See if the true/false values (V) are live in all of the
 /// predecessor blocks of the PHI. For example, cases like this can't be mapped:
 ///
 ///   X = phi [ C1, BB1], [C2, BB2]
 ///   Y = add
 ///   Z = select X, Y, 0
 ///

test/Transforms/InstCombine/unsigned_saturated_sub.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -instcombine -S < %s | FileCheck %s
 
 ; Transforms for unsigned saturated subtraction idioms are tested here.
 ; In all cases, we want to form a canonical min/max op (the compare and
 ; select operands are the same), so that is recognized by the backend.
 ; The backend recognition is tested in test/CodeGen/X86/psubus.ll.
 
 declare void @use(i64)
 
 ; (a > b) ? a - b : 0 -> ((a > b) ? a : b) - b)
 
 define i64 @max_sub_ugt(i64 %a, i64 %b) {
 ; CHECK-LABEL: @max_sub_ugt(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[A]], [[B]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i64 [[SUB]], i64 0
-; CHECK-NEXT:    ret i64 [[SEL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[A]], i64 [[B]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP2]], [[B]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %cmp = icmp ugt i64 %a, %b
   %sub = sub i64 %a, %b
   %sel = select i1 %cmp, i64 %sub ,i64 0
   ret i64 %sel
 }
 
+; (a >= b) ? a - b : 0 -> ((a >= b) ? a : b) - b)
+
+define i64 @max_sub_uge(i64 %a, i64 %b) {
+; CHECK-LABEL: @max_sub_uge(
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[B]], i64 [[A]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP2]], [[B]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
+;
+  %cmp = icmp uge i64 %a, %b
+  %sub = sub i64 %a, %b
+  %sel = select i1 %cmp, i64 %sub ,i64 0
+  ret i64 %sel
+}
+
 ; Again, with vectors:
 ; (a > b) ? a - b : 0 -> ((a > b) ? a : b) - b)
 
 define <4 x i32> @max_sub_ugt_vec(<4 x i32> %a, <4 x i32> %b) {
 ; CHECK-LABEL: @max_sub_ugt_vec(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt <4 x i32> [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub <4 x i32> [[A]], [[B]]
-; CHECK-NEXT:    [[SEL:%.*]] = select <4 x i1> [[CMP]], <4 x i32> [[SUB]], <4 x i32> zeroinitializer
-; CHECK-NEXT:    ret <4 x i32> [[SEL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt <4 x i32> [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select <4 x i1> [[TMP1]], <4 x i32> [[A]], <4 x i32> [[B]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub <4 x i32> [[TMP2]], [[B]]
+; CHECK-NEXT:    ret <4 x i32> [[TMP3]]
 ;
   %cmp = icmp ugt <4 x i32> %a, %b
   %sub = sub <4 x i32> %a, %b
   %sel = select <4 x i1> %cmp, <4 x i32> %sub, <4 x i32> zeroinitializer
   ret <4 x i32> %sel
 }
 
 ; Use extra ops to thwart icmp swapping canonicalization.
 ; (b < a) ? a - b : 0 -> ((a > b) ? a : b) - b)
 
 define i64 @max_sub_ult(i64 %a, i64 %b) {
 ; CHECK-LABEL: @max_sub_ult(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[A]], [[B]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i64 [[SUB]], i64 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[A]], i64 [[B]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP2]], [[B]]
 ; CHECK-NEXT:    [[EXTRASUB:%.*]] = sub i64 [[B]], [[A]]
 ; CHECK-NEXT:    call void @use(i64 [[EXTRASUB]])
-; CHECK-NEXT:    ret i64 [[SEL]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %cmp = icmp ult i64 %b, %a
   %sub = sub i64 %a, %b
   %sel = select i1 %cmp, i64 %sub ,i64 0
   %extrasub = sub i64 %b, %a
   call void @use(i64 %extrasub)
   ret i64 %sel
 }
 
 ; (b > a) ? 0 : a - b -> ((a > b) ? a : b) - b)
 
 define i64 @max_sub_ugt_sel_swapped(i64 %a, i64 %b) {
 ; CHECK-LABEL: @max_sub_ugt_sel_swapped(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[A]], [[B]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i64 0, i64 [[SUB]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i64 [[B:%.*]], [[A:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[B]], i64 [[A]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP2]], [[B]]
 ; CHECK-NEXT:    [[EXTRASUB:%.*]] = sub i64 [[B]], [[A]]
 ; CHECK-NEXT:    call void @use(i64 [[EXTRASUB]])
-; CHECK-NEXT:    ret i64 [[SEL]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %cmp = icmp ugt i64 %b, %a
   %sub = sub i64 %a, %b
   %sel = select i1 %cmp, i64 0 ,i64 %sub
   %extrasub = sub i64 %b, %a
   call void @use(i64 %extrasub)
   ret i64 %sel
 }
 
 ; (a < b) ? 0 : a - b -> ((a > b) ? a : b) - b)
 
 define i64 @max_sub_ult_sel_swapped(i64 %a, i64 %b) {
 ; CHECK-LABEL: @max_sub_ult_sel_swapped(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[A]], [[B]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i64 0, i64 [[SUB]]
-; CHECK-NEXT:    ret i64 [[SEL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[B]], i64 [[A]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP2]], [[B]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %cmp = icmp ult i64 %a, %b
   %sub = sub i64 %a, %b
   %sel = select i1 %cmp, i64 0 ,i64 %sub
   ret i64 %sel
 }
 
 ; ((a > b) ? b - a : 0) -> (b - ((a > b) ? a : b))
 
 define i64 @neg_max_sub_ugt(i64 %a, i64 %b) {
 ; CHECK-LABEL: @neg_max_sub_ugt(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[B]], [[A]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i64 [[SUB]], i64 0
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[A]], i64 [[B]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[B]], [[TMP2]]
 ; CHECK-NEXT:    [[EXTRASUB:%.*]] = sub i64 [[A]], [[B]]
 ; CHECK-NEXT:    call void @use(i64 [[EXTRASUB]])
-; CHECK-NEXT:    ret i64 [[SEL]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %cmp = icmp ugt i64 %a, %b
   %sub = sub i64 %b, %a
   %sel = select i1 %cmp, i64 %sub ,i64 0
   %extrasub = sub i64 %a, %b
   call void @use(i64 %extrasub)
   ret i64 %sel
 }
 
 ; ((b < a) ? b - a : 0) -> - ((a > b) ? a : b) - b)
 
 define i64 @neg_max_sub_ult(i64 %a, i64 %b) {
 ; CHECK-LABEL: @neg_max_sub_ult(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[B]], [[A]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i64 [[SUB]], i64 0
-; CHECK-NEXT:    ret i64 [[SEL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ugt i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[A]], i64 [[B]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[B]], [[TMP2]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %cmp = icmp ult i64 %b, %a
   %sub = sub i64 %b, %a
   %sel = select i1 %cmp, i64 %sub ,i64 0
   ret i64 %sel
 }
 
 ; ((b > a) ? 0 : b - a) -> - ((a > b) ? a : b) - b)
 
 define i64 @neg_max_sub_ugt_sel_swapped(i64 %a, i64 %b) {
 ; CHECK-LABEL: @neg_max_sub_ugt_sel_swapped(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ugt i64 [[B:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[B]], [[A]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i64 0, i64 [[SUB]]
-; CHECK-NEXT:    ret i64 [[SEL]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[B]], i64 [[A]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[B]], [[TMP2]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %cmp = icmp ugt i64 %b, %a
   %sub = sub i64 %b, %a
   %sel = select i1 %cmp, i64 0 ,i64 %sub
   ret i64 %sel
 }
 
 ; ((a < b) ? 0 : b - a) -> - ((a > b) ? a : b) - b)
 
 define i64 @neg_max_sub_ult_sel_swapped(i64 %a, i64 %b) {
 ; CHECK-LABEL: @neg_max_sub_ult_sel_swapped(
-; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i64 [[A:%.*]], [[B:%.*]]
-; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[B]], [[A]]
-; CHECK-NEXT:    [[SEL:%.*]] = select i1 [[CMP]], i64 0, i64 [[SUB]]
+; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i64 [[A:%.*]], [[B:%.*]]
+; CHECK-NEXT:    [[TMP2:%.*]] = select i1 [[TMP1]], i64 [[B]], i64 [[A]]
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[B]], [[TMP2]]
 ; CHECK-NEXT:    [[EXTRASUB:%.*]] = sub i64 [[A]], [[B]]
 ; CHECK-NEXT:    call void @use(i64 [[EXTRASUB]])
-; CHECK-NEXT:    ret i64 [[SEL]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
 ;
   %cmp = icmp ult i64 %a, %b
   %sub = sub i64 %b, %a
   %sel = select i1 %cmp, i64 0 ,i64 %sub
   %extrasub = sub i64 %a, %b
   call void @use(i64 %extrasub)
   ret i64 %sel
 }