[InstCombine] Fix miscompile into uadd.sat (PR48390)

[lebedev.ri]

Summary

We could create uadd.sat under incorrect circumstances if a select with -1 as the false value was canonicalized by swapping the T/F values. Unlike the other transforms in the same function, it is not invariant to equality.

Some alive proofs: https://alive2.llvm.org/ce/z/emmKKL
Fixes PR48390

[lebedev.ri]

Please can you precommit the tests?
The fix looks like it just workarounds the problem, which is elsewhere.
Let me know if i should commandeer the revision.

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

766–782

805–808

Undo this

[dmgreen]

Let me know if i should commandeer the revision.

Yeah sure, feel free to go ahead.

[lebedev.ri]

Ok, after all, this was roughly similar to what i ended up with, sorry for taking this over..

llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp

static Value *canonicalizeSaturatedAdd(ICmpInst *Cmp, Value *TVal, Value *FVal,
   if (Pred == ICmpInst::ICMP_ULT &&
       match(TVal, m_Add(m_Value(X), m_APInt(C))) && X == Cmp0 &&
       match(FVal, m_AllOnes()) && match(Cmp1, m_APInt(CmpC)) && *CmpC == ~*C) {
     // (X u< ~C) ? (X + C) : -1 --> uadd.sat(X, C)
     return Builder.CreateBinaryIntrinsic(
         Intrinsic::uadd_sat, X, ConstantInt::get(X->getType(), *C));
   }
 
   // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
   // There are 8 commuted variants.
-  // Canonicalize -1 (saturated result) to true value of the select. Just
-  // swapping the compare operands is legal, because the selected value is the
-  // same in case of equality, so we can interchange u< and u<=.
+  // Canonicalize -1 (saturated result) to true value of the select.
   if (match(FVal, m_AllOnes())) {
     std::swap(TVal, FVal);
-    std::swap(Cmp0, Cmp1);
+    Pred = CmpInst::getInversePredicate(Pred);
   }
   if (!match(TVal, m_AllOnes()))
     return nullptr;
 
-  // Canonicalize predicate to 'ULT'.
-  if (Pred == ICmpInst::ICMP_UGT) {
-    Pred = ICmpInst::ICMP_ULT;
+  // Canonicalize predicate to less-than or less-or-equal-than.
+  if (Pred == ICmpInst::ICMP_UGT || Pred == ICmpInst::ICMP_UGE) {
     std::swap(Cmp0, Cmp1);
+    Pred = CmpInst::getSwappedPredicate(Pred);
   }
-  if (Pred != ICmpInst::ICMP_ULT)
+  if (Pred != ICmpInst::ICMP_ULT && Pred != ICmpInst::ICMP_ULE)
     return nullptr;
 
   // Match unsigned saturated add of 2 variables with an unnecessary 'not'.
+  // Strictness of the comparison is irrelevant.
   Value *Y;
   if (match(Cmp0, m_Not(m_Value(X))) &&
       match(FVal, m_c_Add(m_Specific(X), m_Value(Y))) && Y == Cmp1) {
     // (~X u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
     // (~X u< Y) ? -1 : (Y + X) --> uadd.sat(X, Y)
     return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, X, Y);
   }
   // The 'not' op may be included in the sum but not the compare.
+  // Strictness of the comparison is irrelevant.
   X = Cmp0;
   Y = Cmp1;
   if (match(FVal, m_c_Add(m_Not(m_Specific(X)), m_Specific(Y)))) {
     // (X u< Y) ? -1 : (~X + Y) --> uadd.sat(~X, Y)
     // (X u< Y) ? -1 : (Y + ~X) --> uadd.sat(Y, ~X)
     BinaryOperator *BO = cast<BinaryOperator>(FVal);
     return Builder.CreateBinaryIntrinsic(
         Intrinsic::uadd_sat, BO->getOperand(0), BO->getOperand(1));
   }
   // The overflow may be detected via the add wrapping round.
-  if (match(Cmp0, m_c_Add(m_Specific(Cmp1), m_Value(Y))) &&
+  // This is only valid for strict comparison!
+  if (Pred == ICmpInst::ICMP_ULT &&
+      match(Cmp0, m_c_Add(m_Specific(Cmp1), m_Value(Y))) &&
       match(FVal, m_c_Add(m_Specific(Cmp1), m_Specific(Y)))) {
     // ((X + Y) u< X) ? -1 : (X + Y) --> uadd.sat(X, Y)
     // ((X + Y) u< Y) ? -1 : (X + Y) --> uadd.sat(X, Y)
     return Builder.CreateBinaryIntrinsic(Intrinsic::uadd_sat, Cmp1, Y);
   }
 
   return nullptr;
 }
 

llvm/test/Transforms/InstCombine/saturating-add-sub.ll

;
   %a = add i32 %x, %y
   %c = icmp ult i32 %a, %y
   %r = select i1 %c, i32 -1, i32 %a
   ret i32 %r
 }
 
 define i32 @uadd_sat_via_add_nonstrict(i32 %x, i32 %y) {
 ; CHECK-LABEL: @uadd_sat_via_add_nonstrict(
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[Y:%.*]], i32 [[X:%.*]])
-; CHECK-NEXT:    ret i32 [[TMP1]]
+; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[C_NOT:%.*]] = icmp ugt i32 [[A]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C_NOT]], i32 [[A]], i32 -1
+; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = add i32 %x, %y
   %c = icmp ule i32 %a, %y
   %r = select i1 %c, i32 -1, i32 %a
   ret i32 %r
 }
 
 define i32 @uadd_sat_via_add_swapped_select(i32 %x, i32 %y) {
 ; CHECK-LABEL: @uadd_sat_via_add_swapped_select(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[Y:%.*]], i32 [[X:%.*]])
 ; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %a = add i32 %x, %y
   %c = icmp uge i32 %a, %y
   %r = select i1 %c, i32 %a, i32 -1
   ret i32 %r
 }
 
 define i32 @uadd_sat_via_add_swapped_select_strict(i32 %x, i32 %y) {
 ; CHECK-LABEL: @uadd_sat_via_add_swapped_select_strict(
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[Y:%.*]], i32 [[X:%.*]])
-; CHECK-NEXT:    ret i32 [[TMP1]]
+; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[A]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C]], i32 [[A]], i32 -1
+; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = add i32 %x, %y
   %c = icmp ugt i32 %a, %y
   %r = select i1 %c, i32 %a, i32 -1
   ret i32 %r
 }
 
 define i32 @uadd_sat_via_add_swapped_cmp(i32 %x, i32 %y) {
 ; CHECK-LABEL: @uadd_sat_via_add_swapped_cmp(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[Y:%.*]], i32 [[X:%.*]])
 ; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %a = add i32 %x, %y
   %c = icmp ugt i32 %y, %a
   %r = select i1 %c, i32 -1, i32 %a
   ret i32 %r
 }
 
 define i32 @uadd_sat_via_add_swapped_cmp_nonstrict(i32 %x, i32 %y) {
 ; CHECK-LABEL: @uadd_sat_via_add_swapped_cmp_nonstrict(
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[Y:%.*]], i32 [[X:%.*]])
-; CHECK-NEXT:    ret i32 [[TMP1]]
+; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[C_NOT:%.*]] = icmp ugt i32 [[A]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C_NOT]], i32 [[A]], i32 -1
+; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = add i32 %x, %y
   %c = icmp uge i32 %y, %a
   %r = select i1 %c, i32 -1, i32 %a
   ret i32 %r
 }
 
 define i32 @uadd_sat_via_add_swapped_cmp_nonstric(i32 %x, i32 %y) {
 ; CHECK-LABEL: @uadd_sat_via_add_swapped_cmp_nonstric(
 ; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[Y:%.*]], i32 [[X:%.*]])
 ; CHECK-NEXT:    ret i32 [[TMP1]]
 ;
   %a = add i32 %x, %y
   %c = icmp ule i32 %y, %a
   %r = select i1 %c, i32 %a, i32 -1
   ret i32 %r
 }
 
 define i32 @uadd_sat_via_add_swapped_cmp_select_nonstrict(i32 %x, i32 %y) {
 ; CHECK-LABEL: @uadd_sat_via_add_swapped_cmp_select_nonstrict(
-; CHECK-NEXT:    [[TMP1:%.*]] = call i32 @llvm.uadd.sat.i32(i32 [[Y:%.*]], i32 [[X:%.*]])
-; CHECK-NEXT:    ret i32 [[TMP1]]
+; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], [[Y:%.*]]
+; CHECK-NEXT:    [[C:%.*]] = icmp ugt i32 [[A]], [[Y]]
+; CHECK-NEXT:    [[R:%.*]] = select i1 [[C]], i32 [[A]], i32 -1
+; CHECK-NEXT:    ret i32 [[R]]
 ;
   %a = add i32 %x, %y
   %c = icmp ult i32 %y, %a
   %r = select i1 %c, i32 %a, i32 -1
   ret i32 %r
 }