[InstCombine] reduce unsigned saturated add with 'not' op

We want to use the sum in the icmp to allow matching with
m_UAddWithOverflow and eliminate the 'not'. This is discussed
in D51929 and is another step towards solving PR14613:
https://bugs.llvm.org/show_bug.cgi?id=14613

(The matching here is incomplete. Trying to take minimal steps
to make sure we don't induce infinite looping from existing
canonicalizations of the 'select'.)

llvm-svn: 354221

1 files changed, 28 insertions, 11 deletions

diff --git a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
index 5922e6f7506..8b5dd7923c4 100644
--- a/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
+++ b/llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
@@ -677,19 +677,36 @@ static Value *canonicalizeSaturatedSubtract(const ICmpInst *ICI,
 
 static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal,
                                        InstCombiner::BuilderTy &Builder) {
-  // Match an unsigned saturated add with constant.
-  Value *X = Cmp->getOperand(0);
-  const APInt *CmpC, *AddC;
-  if (!Cmp->hasOneUse() || Cmp->getPredicate() != ICmpInst::ICMP_ULT ||
-      !match(Cmp->getOperand(1), m_APInt(CmpC)) || !match(FVal, m_AllOnes()) ||
-      !match(TVal, m_Add(m_Specific(X), m_APInt(AddC))) || ~(*AddC) != *CmpC)
+  if (!Cmp->hasOneUse() || Cmp->getPredicate() != ICmpInst::ICMP_ULT)
     return nullptr;
 
-  // Commute compare and select operands:
-  // select (icmp ult X, C), (add X, ~C), -1 -->
-  // select (icmp ugt X, C), -1, (add X, ~C)
-  Value *NewCmp = Builder.CreateICmp(ICmpInst::ICMP_UGT, X, Cmp->getOperand(1));
-  return Builder.CreateSelect(NewCmp, FVal, TVal);
+  // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
+  // TODO: There are more variations of this pattern.
+  Value *Cmp0 = Cmp->getOperand(0);
+  Value *Cmp1 = Cmp->getOperand(1);
+  Value *X, *Y;
+  if (match(TVal, m_AllOnes()) && match(Cmp0, m_Not(m_Value(X))) &&
+      match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) {
+    // Change the comparison to use the sum (false value of the select). That is
+    // the canonical pattern match form for uadd.with.overflow and eliminates a
+    // use of the 'not' op:
+    // (~X u< Y) ? -1 : (X + Y) --> ((X + Y) u< Y) ? -1 : (X + Y)
+    // (~X u< Y) ? -1 : (Y + X) --> ((Y + X) u< Y) ? -1 : (Y + X)
+    Value *NewCmp = Builder.CreateICmp(ICmpInst::ICMP_ULT, FVal, Y);
+    return Builder.CreateSelect(NewCmp, TVal, FVal);
+  }
+
+  // Match unsigned saturated add with constant.
+  const APInt *C, *CmpC;
+  if (match(TVal, m_Add(m_Value(X), m_APInt(C))) && X == Cmp0 &&
+      match(FVal, m_AllOnes()) && match(Cmp1, m_APInt(CmpC)) && *CmpC == ~*C) {
+    // Commute compare predicate and select operands:
+    // (X u< ~C) ? (X + C) : -1 --> (X u> ~C) ? -1 : (X + C)
+    Value *NewCmp = Builder.CreateICmp(ICmpInst::ICMP_UGT, X, Cmp1);
+    return Builder.CreateSelect(NewCmp, FVal, TVal);
+  }
+
+  return nullptr;
 }
 
 /// Attempt to fold a cttz/ctlz followed by a icmp plus select into a single