[ConstraintElim] Simplify `MinMaxIntrinsic` (#75306)

This patch replaces min/max intrinsic with one of its operands if
possible.
Alive2: https://alive2.llvm.org/ce/z/LoHfYf
Fixes #75155.

2 files changed, 283 insertions, 0 deletions

diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
index ae8e229..97cf5eb 100644
--- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
+++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp
@@ -1065,6 +1065,9 @@ void State::addInfoFor(BasicBlock &BB) {
     case Intrinsic::umax:
     case Intrinsic::smin:
     case Intrinsic::smax:
+      // TODO: handle llvm.abs as well
+      WorkList.push_back(
+          FactOrCheck::getCheck(DT.getNode(&BB), cast<CallInst>(&I)));
       // TODO: Check if it is possible to instead only added the min/max facts
       // when simplifying uses of the min/max intrinsics.
       if (!isGuaranteedNotToBePoison(&I))
@@ -1395,6 +1398,26 @@ static bool checkAndReplaceCondition(
   return false;
 }
 
+static bool checkAndReplaceMinMax(MinMaxIntrinsic *MinMax, ConstraintInfo &Info,
+                                  SmallVectorImpl<Instruction *> &ToRemove) {
+  auto ReplaceMinMaxWithOperand = [&](MinMaxIntrinsic *MinMax, bool UseLHS) {
+    // TODO: generate reproducer for min/max.
+    MinMax->replaceAllUsesWith(MinMax->getOperand(UseLHS ? 0 : 1));
+    ToRemove.push_back(MinMax);
+    return true;
+  };
+
+  ICmpInst::Predicate Pred =
+      ICmpInst::getNonStrictPredicate(MinMax->getPredicate());
+  if (auto ImpliedCondition = checkCondition(
+          Pred, MinMax->getOperand(0), MinMax->getOperand(1), MinMax, Info))
+    return ReplaceMinMaxWithOperand(MinMax, *ImpliedCondition);
+  if (auto ImpliedCondition = checkCondition(
+          Pred, MinMax->getOperand(1), MinMax->getOperand(0), MinMax, Info))
+    return ReplaceMinMaxWithOperand(MinMax, !*ImpliedCondition);
+  return false;
+}
+
 static void
 removeEntryFromStack(const StackEntry &E, ConstraintInfo &Info,
                      Module *ReproducerModule,
@@ -1695,6 +1718,8 @@ static bool eliminateConstraints(Function &F, DominatorTree &DT, LoopInfo &LI,
                                          ReproducerCondStack, DFSInStack);
         }
         Changed |= Simplified;
+      } else if (auto *MinMax = dyn_cast<MinMaxIntrinsic>(Inst)) {
+        Changed |= checkAndReplaceMinMax(MinMax, Info, ToRemove);
       }
       continue;
     }
diff --git a/llvm/test/Transforms/ConstraintElimination/minmax.ll b/llvm/test/Transforms/ConstraintElimination/minmax.ll
index 82b932f..68513ea 100644
--- a/llvm/test/Transforms/ConstraintElimination/minmax.ll
+++ b/llvm/test/Transforms/ConstraintElimination/minmax.ll
@@ -343,6 +343,264 @@ end:
   ret i32 0
 }
 
+; Test from PR75155
+define i32 @simplify_slt_smax_val(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_slt_smax_val
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 1
+; CHECK-NEXT:    ret i32 [[B]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp slt i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nsw i32 %a, 1
+  %max = call i32 @llvm.smax.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_slt_smax_val_commuted(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_slt_smax_val_commuted
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 1
+; CHECK-NEXT:    ret i32 [[B]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp slt i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nsw i32 %a, 1
+  %max = call i32 @llvm.smax.i32(i32 %add, i32 %b)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_slt_smax_val_at_use(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_slt_smax_val_at_use
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[A]], [[B]]
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 1
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[B]], i32 [[ADD]])
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    ret i32 [[MAX]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp slt i32 %a, %b
+  %add = add nsw i32 %a, 1
+  %max = call i32 @llvm.smax.i32(i32 %b, i32 %add)
+  br i1 %cmp, label %then, label %else
+then:
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_sgt_smax_val(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_sgt_smax_val
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 1
+; CHECK-NEXT:    ret i32 [[ADD]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp sgt i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nsw i32 %a, 1
+  %max = call i32 @llvm.smax.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_sle_smax_val(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_sle_smax_val
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 1
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[B]], i32 [[ADD]])
+; CHECK-NEXT:    ret i32 [[MAX]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp sle i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nsw i32 %a, 1
+  %max = call i32 @llvm.smax.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_sge_smax_val(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_sge_smax_val
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 1
+; CHECK-NEXT:    ret i32 [[ADD]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp sge i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nsw i32 %a, 1
+  %max = call i32 @llvm.smax.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_ult_umax_val(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_ult_umax_val
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nuw i32 [[A]], 1
+; CHECK-NEXT:    ret i32 [[B]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nuw i32 %a, 1
+  %max = call i32 @llvm.umax.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_slt_smin_val(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_slt_smin_val
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 1
+; CHECK-NEXT:    ret i32 [[ADD]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp slt i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nsw i32 %a, 1
+  %max = call i32 @llvm.smin.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_ult_umin_val(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_ult_umin_val
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nuw i32 [[A]], 1
+; CHECK-NEXT:    ret i32 [[ADD]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nuw i32 %a, 1
+  %max = call i32 @llvm.umin.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_slt_smax_val_fail1(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_slt_smax_val_fail1
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 2
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[B]], i32 [[ADD]])
+; CHECK-NEXT:    ret i32 [[MAX]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp slt i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nsw i32 %a, 2
+  %max = call i32 @llvm.smax.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
+define i32 @simplify_ult_smax_val_fail2(i32 %a, i32 %b) {
+; CHECK-LABEL: define i32 @simplify_ult_smax_val_fail2
+; CHECK-SAME: (i32 [[A:%.*]], i32 [[B:%.*]]) {
+; CHECK-NEXT:  start:
+; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[A]], [[B]]
+; CHECK-NEXT:    br i1 [[CMP]], label [[THEN:%.*]], label [[ELSE:%.*]]
+; CHECK:       then:
+; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[A]], 1
+; CHECK-NEXT:    [[MAX:%.*]] = call i32 @llvm.smax.i32(i32 [[B]], i32 [[ADD]])
+; CHECK-NEXT:    ret i32 [[MAX]]
+; CHECK:       else:
+; CHECK-NEXT:    ret i32 -1
+;
+start:
+  %cmp = icmp ult i32 %a, %b
+  br i1 %cmp, label %then, label %else
+then:
+  %add = add nsw i32 %a, 1
+  %max = call i32 @llvm.smax.i32(i32 %b, i32 %add)
+  ret i32 %max
+else:
+  ret i32 -1
+}
+
 declare i32 @llvm.smin.i32(i32, i32)
 declare i32 @llvm.smax.i32(i32, i32)
 declare i32 @llvm.umin.i32(i32, i32)