[InstCombine] move add after min/max intrinsic

[spatel]

Summary

This is another regression noted with the proposal to canonicalize to the min/max intrinsics in D98152.

Here are Alive2 attempts to show correctness without specifying exact constants:
https://alive2.llvm.org/ce/z/bvfCwh (smax)
https://alive2.llvm.org/ce/z/of7eqy (smin)
https://alive2.llvm.org/ce/z/2Xtxoh (umax)
https://alive2.llvm.org/ce/z/Rm4Ad8 (umin)
(if you comment out the assume and/or no-wrap, you should see failures)

The different output for the umin test is due to a fold added with c4fc2cb5b2d98125 :

// umin(x, 1) == zext(x != 0)

We probably want to adjust that, so it applies more generally (umax --> sext? or patterns where we can fold to select-of-constants). Some folds that were ok when starting with cmp+select may increase instruction count for the equivalent intrinsic, so we have to decide if it's worth altering a min/max.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

766

Even without undef/poison elts, can this not support constant vectors from the beginning?

790

I'm not sure what this assertion is doing.
Perhaps you want to initialize Overflow to true?

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

766

It's more work because we have to check that no element overflows its subtract op. We can't rely on instsimplify to fold that for us either (see next comment).

I want to make sure that we have the base case correct first, and it's really only that (the scalar case) that shows up currently in D98152 if I'm seeing it properly.

790

This is verifying that this min/max has been analyzed by -instsimplify already. If the constant math overflows, we should not be here. Not sure if we can make that clearer on the comment at line 775. Or could just move that down here?

We expect APInt to set Overflow either way, so initializing it here could hide a bug in APInt if that implementation ever broke.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

790

Not sure if this was clear, but the transform does not hold if the sub-of-constants overflows:
https://alive2.llvm.org/ce/z/3TScp5

So if we don't want to rely on instsimplify handling that, we would have to bail out on overflow.

And if we want to extend this transform to handle arbitrary vector constants, then we have to evaluate each element of the vector, check for overflow on each one, and bail out if any of the subtract ops overflows.

[lebedev.ri]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

790

No, all that was obvious to me.
The thing i was pointing at, if you happen to not early-return,
and not call *sub_ov, then Overflow is uninitialized,
and the assertion becomes useless.
But if Overflow was init'd to true, then it would just fire.

[spatel]

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

790

Ah, I see - so it's a trade-off whether the initialization provides some more guarantees about the code here vs. in the called code.

We could restructure it so there's no room for things to go wrong in this code between the Overflow declaration and assert:

// Check for necessary no-wrap and overflow constraints.
bool IsSigned = MinMaxID == Intrinsic::smax || MinMaxID == Intrinsic::smin;
auto *Add = cast<BinaryOperator>(Op0);
if ((IsSigned && !Add->hasNoSignedWrap()) ||
    (!IsSigned && !Add->hasNoUnsignedWrap()))
  return nullptr;

// If the constant difference overflows, then instsimplify should reduce the
// min/max to the add or C1.
bool Overflow;
APInt CDiff =
    IsSigned ? C1->ssub_ov(*C0, Overflow) : C1->usub_ov(*C0, Overflow);
assert(!Overflow && "Expected simplify of min/max");

[spatel]

Patch updated:
Refactored to make assert clearer (I hope).

[lebedev.ri]

LG under assumption that support for vectors/non-splat vectors/vectors w. undef
will be added in followups.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp

if (Known.isNonNegative())
     return false;
   if (Known.isNegative())
     return true;
 
   return isImpliedByDomCondition(
       ICmpInst::ICMP_SLT, Op, Constant::getNullValue(Op->getType()), CxtI, DL);
 }
 
+/// Try to canonicalize min/max(X + C0, C1) as min/max(X, C1 - C0) + C0. This
+/// can trigger other combines.
+static Instruction *moveAddAfterMinMax(IntrinsicInst *II,
+                                       InstCombiner::BuilderTy &Builder) {
+  Intrinsic::ID MinMaxID = II->getIntrinsicID();
+  assert((MinMaxID == Intrinsic::smax || MinMaxID == Intrinsic::smin ||
+          MinMaxID == Intrinsic::umax || MinMaxID == Intrinsic::umin) &&
+         "Expected a min or max intrinsic");
+
+  // TODO: Match vectors with undef elements, but undef may not propagate.
+  Value *Op0 = II->getArgOperand(0), *Op1 = II->getArgOperand(1);
+  Value *X;
+  const APInt *C0, *C1;
+  if (!match(Op0, m_OneUse(m_Add(m_Value(X), m_APInt(C0)))) ||
+      !match(Op1, m_APInt(C1)))
+    return nullptr;
+
+  // Check for necessary no-wrap and overflow constraints.
+  bool IsSigned = MinMaxID == Intrinsic::smax || MinMaxID == Intrinsic::smin;
+  auto *Add = cast<BinaryOperator>(Op0);
+  if ((IsSigned && !Add->hasNoSignedWrap()) ||
+      (!IsSigned && !Add->hasNoUnsignedWrap()))
+    return nullptr;
+
+  // If the constant difference overflows, then instsimplify should reduce the
+  // min/max to the add or C1.
+  bool Overflow;
+  APInt CDiff =
+      IsSigned ? C1->ssub_ov(*C0, Overflow) : C1->usub_ov(*C0, Overflow);
+  assert(!Overflow && "Expected simplify of min/max");
+
+  // min/max (add X, C0), C1 --> add (min/max X, C1 - C0), C0
+  // Note: the "mismatched" no-overflow setting does not propagate.
+  Constant *NewMinMaxC = ConstantInt::get(II->getType(), CDiff);
+  Value *NewMinMax = Builder.CreateBinaryIntrinsic(MinMaxID, X, NewMinMaxC);
+  return IsSigned ? BinaryOperator::CreateNSWAdd(NewMinMax, Add->getOperand(1))
+                  : BinaryOperator::CreateNUWAdd(NewMinMax, Add->getOperand(1));
+}
+
 /// If we have a clamp pattern like max (min X, 42), 41 -- where the output
 /// can only be one of two possible constant values -- turn that into a select
 /// of constants.
 static Instruction *foldClampRangeOfTwo(IntrinsicInst *II,
                                         InstCombiner::BuilderTy &Builder) {
   Value *I0 = II->getArgOperand(0), *I1 = II->getArgOperand(1);
   Value *X;
   const APInt *C0, *C1;
auto moveNotAfterMinMax = [&](Value *X, Value *Y) -> Instruction * {
       return nullptr;
     };
 
     if (Instruction *I = moveNotAfterMinMax(I0, I1))
       return I;
     if (Instruction *I = moveNotAfterMinMax(I1, I0))
       return I;
 
+    if (Instruction *I = moveAddAfterMinMax(II, Builder))
+      return I;
+
     // smax(X, -X) --> abs(X)
     // smin(X, -X) --> -abs(X)
     // umax(X, -X) --> -abs(X)
     // umin(X, -X) --> abs(X)
     if (isKnownNegation(I0, I1)) {
       // We can choose either operand as the input to abs(), but if we can
       // eliminate the only use of a value, that's better for subsequent
       // transforms/analysis.

llvm/test/Transforms/InstCombine/minmax-intrinsics.ll

;
   %yk = sub i8 %k, %notb
   %mk = sub i8 %k, %notg
   call void @use4(i8 %ck, i8 %mk, i8 %yk, i8 %k)
   ret void
 }
 
 define i8 @smax_offset(i8 %x) {
 ; CHECK-LABEL: @smax_offset(
-; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X:%.*]], 3
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[A]], i8 -124)
+; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.smax.i8(i8 [[X:%.*]], i8 -127)
+; CHECK-NEXT:    [[M:%.*]] = add nsw i8 [[TMP1]], 3
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add nsw i8 %x, 3
   %m = call i8 @llvm.smax.i8(i8 %a, i8 -124)
   ret i8 %m
 }
 
+; This is handled by InstSimplify; testing here to confirm assert.
+
 define i8 @smax_offset_limit(i8 %x) {
 ; CHECK-LABEL: @smax_offset_limit(
 ; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i8 [[A]]
 ;
   %a = add nsw i8 %x, 3
   %m = call i8 @llvm.smax.i8(i8 %a, i8 -125)
   ret i8 %m
 }
 
+; This is handled by InstSimplify; testing here to confirm assert.
+
 define i8 @smax_offset_overflow(i8 %x) {
 ; CHECK-LABEL: @smax_offset_overflow(
 ; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i8 [[A]]
 ;
   %a = add nsw i8 %x, 3
   %m = call i8 @llvm.smax.i8(i8 %a, i8 -126)
   ret i8 %m
 }
 
+; negative test - require nsw
+
 define i8 @smax_offset_may_wrap(i8 %x) {
 ; CHECK-LABEL: @smax_offset_may_wrap(
 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[X:%.*]], 3
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[A]], i8 -124)
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add i8 %x, 3
   %m = call i8 @llvm.smax.i8(i8 %a, i8 -124)
   ret i8 %m
 }
 
+; negative test
+
 define i8 @smax_offset_uses(i8 %x) {
 ; CHECK-LABEL: @smax_offset_uses(
 ; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    call void @use(i8 [[A]])
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smax.i8(i8 [[A]], i8 -124)
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add nsw i8 %x, 3
   call void @use(i8 %a)
   %m = call i8 @llvm.smax.i8(i8 %a, i8 -124)
   ret i8 %m
 }
 
 define <3 x i8> @smin_offset(<3 x i8> %x) {
 ; CHECK-LABEL: @smin_offset(
-; CHECK-NEXT:    [[A:%.*]] = add nuw nsw <3 x i8> [[X:%.*]], <i8 124, i8 124, i8 124>
-; CHECK-NEXT:    [[M:%.*]] = call <3 x i8> @llvm.smin.v3i8(<3 x i8> [[A]], <3 x i8> <i8 -3, i8 -3, i8 -3>)
+; CHECK-NEXT:    [[TMP1:%.*]] = call <3 x i8> @llvm.smin.v3i8(<3 x i8> [[X:%.*]], <3 x i8> <i8 -127, i8 -127, i8 -127>)
+; CHECK-NEXT:    [[M:%.*]] = or <3 x i8> [[TMP1]], <i8 124, i8 124, i8 124>
 ; CHECK-NEXT:    ret <3 x i8> [[M]]
 ;
   %a = add nsw nuw <3 x i8> %x, <i8 124, i8 124, i8 124>
   %m = call <3 x i8> @llvm.smin.v3i8(<3 x i8> %a, <3 x i8> <i8 -3, i8 -3, i8 -3>)
   ret <3 x i8> %m
 }
 
+; This is handled by InstSimplify; testing here to confirm assert.
+
 define i8 @smin_offset_limit(i8 %x) {
 ; CHECK-LABEL: @smin_offset_limit(
 ; CHECK-NEXT:    ret i8 -3
 ;
   %a = add nsw i8 %x, 125
   %m = call i8 @llvm.smin.i8(i8 %a, i8 -3)
   ret i8 %m
 }
 
+; This is handled by InstSimplify; testing here to confirm assert.
+
 define i8 @smin_offset_overflow(i8 %x) {
 ; CHECK-LABEL: @smin_offset_overflow(
 ; CHECK-NEXT:    ret i8 -3
 ;
   %a = add nsw i8 %x, 126
   %m = call i8 @llvm.smin.i8(i8 %a, i8 -3)
   ret i8 %m
 }
 
+; negative test - require nsw
+
 define i8 @smin_offset_may_wrap(i8 %x) {
 ; CHECK-LABEL: @smin_offset_may_wrap(
 ; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[X:%.*]], 124
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[A]], i8 -3)
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add nuw i8 %x, 124
   %m = call i8 @llvm.smin.i8(i8 %a, i8 -3)
   ret i8 %m
 }
 
+; negative test
+
 define i8 @smin_offset_uses(i8 %x) {
 ; CHECK-LABEL: @smin_offset_uses(
 ; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X:%.*]], 124
 ; CHECK-NEXT:    call void @use(i8 [[A]])
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.smin.i8(i8 [[A]], i8 -3)
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add nsw i8 %x, 124
   call void @use(i8 %a)
   %m = call i8 @llvm.smin.i8(i8 %a, i8 -3)
   ret i8 %m
 }
 
+; Note: 'nsw' must not propagate here.
+
 define <3 x i8> @umax_offset(<3 x i8> %x) {
 ; CHECK-LABEL: @umax_offset(
-; CHECK-NEXT:    [[A:%.*]] = add nuw nsw <3 x i8> [[X:%.*]], <i8 127, i8 127, i8 127>
-; CHECK-NEXT:    [[M:%.*]] = call <3 x i8> @llvm.umax.v3i8(<3 x i8> [[A]], <3 x i8> <i8 -126, i8 -126, i8 -126>)
+; CHECK-NEXT:    [[TMP1:%.*]] = call <3 x i8> @llvm.umax.v3i8(<3 x i8> [[X:%.*]], <3 x i8> <i8 3, i8 3, i8 3>)
+; CHECK-NEXT:    [[M:%.*]] = add nuw <3 x i8> [[TMP1]], <i8 127, i8 127, i8 127>
 ; CHECK-NEXT:    ret <3 x i8> [[M]]
 ;
   %a = add nsw nuw <3 x i8> %x, <i8 127, i8 127, i8 127>
   %m = call <3 x i8> @llvm.umax.v3i8(<3 x i8> %a, <3 x i8> <i8 130, i8 130, i8 130>)
   ret <3 x i8> %m
 }
 
+; This is handled by InstSimplify; testing here to confirm assert.
+
 define i8 @umax_offset_limit(i8 %x) {
 ; CHECK-LABEL: @umax_offset_limit(
 ; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i8 [[A]]
 ;
   %a = add nuw i8 %x, 3
   %m = call i8 @llvm.umax.i8(i8 %a, i8 3)
   ret i8 %m
 }
 
+; This is handled by InstSimplify; testing here to confirm assert.
+
 define i8 @umax_offset_overflow(i8 %x) {
 ; CHECK-LABEL: @umax_offset_overflow(
 ; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    ret i8 [[A]]
 ;
   %a = add nuw i8 %x, 3
   %m = call i8 @llvm.umax.i8(i8 %a, i8 2)
   ret i8 %m
 }
 
+; negative test - require nuw
+
 define i8 @umax_offset_may_wrap(i8 %x) {
 ; CHECK-LABEL: @umax_offset_may_wrap(
 ; CHECK-NEXT:    [[A:%.*]] = add i8 [[X:%.*]], 3
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umax.i8(i8 [[A]], i8 4)
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add i8 %x, 3
   %m = call i8 @llvm.umax.i8(i8 %a, i8 4)
   ret i8 %m
 }
 
+; negative test
+
 define i8 @umax_offset_uses(i8 %x) {
 ; CHECK-LABEL: @umax_offset_uses(
 ; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[X:%.*]], 3
 ; CHECK-NEXT:    call void @use(i8 [[A]])
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umax.i8(i8 [[A]], i8 4)
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add nuw i8 %x, 3
   call void @use(i8 %a)
   %m = call i8 @llvm.umax.i8(i8 %a, i8 4)
   ret i8 %m
 }
 
 define i8 @umin_offset(i8 %x) {
 ; CHECK-LABEL: @umin_offset(
-; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[X:%.*]], -5
-; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[A]], i8 -4)
+; CHECK-NEXT:    [[DOTNOT:%.*]] = icmp eq i8 [[X:%.*]], 0
+; CHECK-NEXT:    [[M:%.*]] = select i1 [[DOTNOT]], i8 -5, i8 -4
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add nuw i8 %x, 251
   %m = call i8 @llvm.umin.i8(i8 %a, i8 252)
   ret i8 %m
 }
 
+; This is handled by InstSimplify; testing here to confirm assert.
+
 define i8 @umin_offset_limit(i8 %x) {
 ; CHECK-LABEL: @umin_offset_limit(
 ; CHECK-NEXT:    ret i8 -4
 ;
   %a = add nuw i8 %x, 252
   %m = call i8 @llvm.umin.i8(i8 %a, i8 252)
   ret i8 %m
 }
 
+; This is handled by InstSimplify; testing here to confirm assert.
+
 define i8 @umin_offset_overflow(i8 %x) {
 ; CHECK-LABEL: @umin_offset_overflow(
 ; CHECK-NEXT:    ret i8 -4
 ;
   %a = add nuw i8 %x, 253
   %m = call i8 @llvm.umin.i8(i8 %a, i8 252)
   ret i8 %m
 }
 
+; negative test - require nuw
+
 define i8 @umin_offset_may_wrap(i8 %x) {
 ; CHECK-LABEL: @umin_offset_may_wrap(
 ; CHECK-NEXT:    [[A:%.*]] = add nsw i8 [[X:%.*]], -5
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[A]], i8 -4)
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add nsw i8 %x, 251
   %m = call i8 @llvm.umin.i8(i8 %a, i8 252)
   ret i8 %m
 }
 
+; negative test
+
 define i8 @umin_offset_uses(i8 %x) {
 ; CHECK-LABEL: @umin_offset_uses(
 ; CHECK-NEXT:    [[A:%.*]] = add nuw i8 [[X:%.*]], -5
 ; CHECK-NEXT:    call void @use(i8 [[A]])
 ; CHECK-NEXT:    [[M:%.*]] = call i8 @llvm.umin.i8(i8 [[A]], i8 -4)
 ; CHECK-NEXT:    ret i8 [[M]]
 ;
   %a = add nuw i8 %x, 251
   call void @use(i8 %a)
   %m = call i8 @llvm.umin.i8(i8 %a, i8 252)
   ret i8 %m
 }
 
+; TODO: This could transform, but undef element must not propagate to the new add.
+
 define <3 x i8> @umax_vector_splat_undef(<3 x i8> %x) {
 ; CHECK-LABEL: @umax_vector_splat_undef(
 ; CHECK-NEXT:    [[A:%.*]] = add nuw <3 x i8> [[X:%.*]], <i8 undef, i8 64, i8 64>
 ; CHECK-NEXT:    [[R:%.*]] = call <3 x i8> @llvm.umax.v3i8(<3 x i8> [[A]], <3 x i8> <i8 13, i8 -126, i8 -126>)
 ; CHECK-NEXT:    ret <3 x i8> [[R]]
 ;
   %a = add nuw <3 x i8> %x, <i8 undef, i8 64, i8 64>
   %r = call <3 x i8> @llvm.umax.v3i8(<3 x i8> %a, <3 x i8> <i8 13, i8 130, i8 130>)
   ret <3 x i8> %r
 }