[ConstraintElimination] Simplify ssub(a,b) if a s>=b && a s>=0.

[fhahn]

Summary

A first patch to use the reasoning in ConstraintElimination to simplify
sub with overflow to a regular sub, if the operation is guaranteed to
not overflow.

[nikic]

Would it be sufficient to only replace the m_ExtractValue<1>? I believe that's what we usually do. (Would also work if only the extractvalue is dominated.)

[fhahn]

In D125264#3501773, @nikic wrote:

Would it be sufficient to only replace the m_ExtractValue<1>? I believe that's what we usually do. (Would also work if only the extractvalue is dominated.)

And leave the removal of the actual intrinsic call to instcombine (or some other existing transform)? If that's what we do elsewhere I think it should work, the current placement in the regular optimization pipeline means we run instcombine shortly after ConstraintElimiantion.

[nikic]

In D125264#3501812, @fhahn wrote:

In D125264#3501773, @nikic wrote:

Would it be sufficient to only replace the m_ExtractValue<1>? I believe that's what we usually do. (Would also work if only the extractvalue is dominated.)

And leave the removal of the actual intrinsic call to instcombine (or some other existing transform)? If that's what we do elsewhere I think it should work, the current placement in the regular optimization pipeline means we run instcombine shortly after ConstraintElimiantion.

Yeah, that's what I had in mind. Though checking now, it looks like both CVP (https://github.com/llvm/llvm-project/blob/72831a592edf1bdcca15354181867079a17d4f76/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp#L572) and SimplifyIndVars (https://github.com/llvm/llvm-project/blob/72831a592edf1bdcca15354181867079a17d4f76/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp#L423) do replace the with.overflow intrinsic itself, so maybe it's fine as is.

[spatel]

In D125264#3501823, @nikic wrote:

In D125264#3501812, @fhahn wrote:

In D125264#3501773, @nikic wrote:

Would it be sufficient to only replace the m_ExtractValue<1>? I believe that's what we usually do. (Would also work if only the extractvalue is dominated.)

And leave the removal of the actual intrinsic call to instcombine (or some other existing transform)? If that's what we do elsewhere I think it should work, the current placement in the regular optimization pipeline means we run instcombine shortly after ConstraintElimiantion.

Yeah, that's what I had in mind. Though checking now, it looks like both CVP (https://github.com/llvm/llvm-project/blob/72831a592edf1bdcca15354181867079a17d4f76/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp#L572) and SimplifyIndVars (https://github.com/llvm/llvm-project/blob/72831a592edf1bdcca15354181867079a17d4f76/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp#L423) do replace the with.overflow intrinsic itself, so maybe it's fine as is.

Those examples also do eraseFromParent(). I don't know if there's any official guideline for the behavior, but cleaning up dead values here makes it less likely that things will break if some other pass gets inserted in the pipeline between this and the next round of instcombine.

[fhahn]

In D125264#3503308, @spatel wrote:

In D125264#3501823, @nikic wrote:

In D125264#3501812, @fhahn wrote:

In D125264#3501773, @nikic wrote:

Would it be sufficient to only replace the m_ExtractValue<1>? I believe that's what we usually do. (Would also work if only the extractvalue is dominated.)

And leave the removal of the actual intrinsic call to instcombine (or some other existing transform)? If that's what we do elsewhere I think it should work, the current placement in the regular optimization pipeline means we run instcombine shortly after ConstraintElimiantion.

Yeah, that's what I had in mind. Though checking now, it looks like both CVP (https://github.com/llvm/llvm-project/blob/72831a592edf1bdcca15354181867079a17d4f76/llvm/lib/Transforms/Scalar/CorrelatedValuePropagation.cpp#L572) and SimplifyIndVars (https://github.com/llvm/llvm-project/blob/72831a592edf1bdcca15354181867079a17d4f76/llvm/lib/Transforms/Utils/SimplifyIndVar.cpp#L423) do replace the with.overflow intrinsic itself, so maybe it's fine as is.

Those examples also do eraseFromParent(). I don't know if there's any official guideline for the behavior, but cleaning up dead values here makes it less likely that things will break if some other pass gets inserted in the pipeline between this and the next round of instcombine.

That's a good point, thanks! I updated the code to remove both the extracts and the intrinsic, if possible.

[spatel]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

537–538

This pre-condition is not correct - if A is 0 and B is SMIN for a given width, that overflows.

Double-check to make sure I got the right pattern, but we should have a test like this:
https://alive2.llvm.org/ce/z/t9G3TQ

[fhahn]

Fix check to ensure B s>= 0, this also ensures A s>= 0.

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

537–538

Thanks, this needs to check if B >= 0, which also implies A >= 0. I added additional tests in 1911843c3126 based on the shared alive2 code (I think the one you shared had different compares for %c.2 in @src and @tgt, so the verification failure was about that, here's a slightly updated one: https://alive2.llvm.org/ce/z/L_K648)

[spatel]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

537–538

Ah, yes - I messed up that alive code.
I think the patch is correct now, but we could do better if we check the constraints like this:

%a_is_neg = icmp slt i8 %a, 0
%b_is_neg = icmp slt i8 %b, 0
%same_sign = icmp eq i1 %a_is_neg, %b_is_neg

https://alive2.llvm.org/ce/z/D-uuBW

I'm not sure how to best translate that to the getConstraint() framework.

[fhahn]

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

537–538

I think we would have to separately check for s>=0 and s<0 case. I could further extend this patch or do it as follow up.

[spatel]

LGTM

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

537–538

A different patch is probably better.

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/ConstraintSystem.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
+#include "llvm/IR/IRBuilder.h"
 #include "llvm/IR/Instructions.h"
 #include "llvm/IR/PatternMatch.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/DebugCounter.h"
 #include "llvm/Support/MathExtras.h"
 #include "llvm/Transforms/Scalar.h"
void State::addInfoFor(BasicBlock &BB) {
   if (!CmpI)
     return;
   if (canAddSuccessor(BB, Br->getSuccessor(0)))
     WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
   if (canAddSuccessor(BB, Br->getSuccessor(1)))
     WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
 }
 
+static void
+tryToSimplifyOverflowMath(IntrinsicInst *II, ConstraintInfo &Info,
+                          SmallVectorImpl<Instruction *> &ToRemove) {
+  auto DoesConditionHold = [](CmpInst::Predicate Pred, Value *A, Value *B,
+                              ConstraintInfo &Info) {
+    DenseMap<Value *, unsigned> NewIndices;
+    auto R = getConstraint(
+        Pred, A, B, Info.getValue2Index(CmpInst::isSigned(Pred)), NewIndices);
+    if (R.size() < 2 || R.needsNewIndices(NewIndices) || !R.isValid(Info))
+      return false;
+
+    auto &CSToUse = Info.getCS(CmpInst::isSigned(Pred));
+    return CSToUse.isConditionImplied(R.Coefficients);
+  };
+
+  if (II->getIntrinsicID() == Intrinsic::ssub_with_overflow) {
+    // If A s>= B && B s>= 0, ssub.with.overflow(a, b) should not overflow and
+    // can be simplified to a regular sub.
+    Value *A = II->getArgOperand(0);
+    Value *B = II->getArgOperand(1);
+    if (!DoesConditionHold(CmpInst::ICMP_SGE, A, B, Info) ||
+        !DoesConditionHold(CmpInst::ICMP_SGE, B,
+                           ConstantInt::get(A->getType(), 0), Info))
+      return;
+
+    IRBuilder<> Builder(II->getParent(), II->getIterator());
+    Value *Sub = nullptr;
+    for (User *U : make_early_inc_range(II->users())) {
+      if (match(U, m_ExtractValue<0>(m_Value()))) {
+        if (!Sub)
+          Sub = Builder.CreateSub(A, B);
+        U->replaceAllUsesWith(Sub);
+      } else if (match(U, m_ExtractValue<1>(m_Value())))
+        U->replaceAllUsesWith(Builder.getFalse());
+      else
+        continue;
+
+      if (U->use_empty()) {
+        auto *I = cast<Instruction>(U);
+        ToRemove.push_back(I);
+        I->setOperand(0, PoisonValue::get(II->getType()));
+      }
+    }
+
+    if (II->use_empty())
+      II->eraseFromParent();
+  }
+}
+
 static bool eliminateConstraints(Function &F, DominatorTree &DT) {
   bool Changed = false;
   DT.updateDFSNumbers();
 
   ConstraintInfo Info;
   State S(DT);
 
   // First, collect conditions implied by branches and blocks with their
   // Dominator DFS in and out numbers.
   for (BasicBlock &BB : F) {
     if (!DT.getNode(&BB))
       continue;
     S.addInfoFor(BB);
   }
 
   // Next, sort worklist by dominance, so that dominating blocks and conditions
   // come before blocks and conditions dominated by them. If a block and a
   // condition have the same numbers, the condition comes before the block, as
   // it holds on entry to the block.
   sort(S.WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
     return std::tie(A.NumIn, A.IsBlock) < std::tie(B.NumIn, B.IsBlock);
   });
 
+  SmallVector<Instruction *> ToRemove;
+
   // Finally, process ordered worklist and eliminate implied conditions.
   SmallVector<StackEntry, 16> DFSInStack;
   for (ConstraintOrBlock &CB : S.WorkList) {
     // First, pop entries from the stack that are out-of-scope for CB. Remove
     // the corresponding entry from the constraint system.
     while (!DFSInStack.empty()) {
       auto &E = DFSInStack.back();
       LLVM_DEBUG(dbgs() << "Top of stack : " << E.NumIn << " " << E.NumOut
LLVM_DEBUG({
       else
         dbgs() << *CB.Condition;
       dbgs() << "\n";
     });
 
     // For a block, check if any CmpInsts become known based on the current set
     // of constraints.
     if (CB.IsBlock) {
-      for (Instruction &I : *CB.BB) {
+      for (Instruction &I : make_early_inc_range(*CB.BB)) {
+        if (auto *II = dyn_cast<WithOverflowInst>(&I)) {
+          tryToSimplifyOverflowMath(II, Info, ToRemove);
+          continue;
+        }
         auto *Cmp = dyn_cast<ICmpInst>(&I);
         if (!Cmp)
           continue;
 
         DenseMap<Value *, unsigned> NewIndices;
         auto R = getConstraint(Cmp, Info, NewIndices);
         if (R.IsEq || R.size() < 2 || R.needsNewIndices(NewIndices) ||
             !R.isValid(Info))
#ifndef NDEBUG
   unsigned SignedEntries =
       count_if(DFSInStack, [](const StackEntry &E) { return E.IsSigned; });
   assert(Info.getCS(false).size() == DFSInStack.size() - SignedEntries &&
          "updates to CS and DFSInStack are out of sync");
   assert(Info.getCS(true).size() == SignedEntries &&
          "updates to CS and DFSInStack are out of sync");
 #endif
 
+  for (Instruction *I : ToRemove)
+    I->eraseFromParent();
   return Changed;
 }
 
 PreservedAnalyses ConstraintEliminationPass::run(Function &F,
                                                  FunctionAnalysisManager &AM) {
   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
   if (!eliminateConstraints(F, DT))
     return PreservedAnalyses::all();

llvm/test/Transforms/ConstraintElimination/ssub-with-overflow.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes=constraint-elimination -S %s | FileCheck %s
 
 declare { i8, i1 } @llvm.ssub.with.overflow.i8(i8, i8)
 
 define i8 @ssub_no_overflow_due_to_or_conds(i8 %a, i8 %b) {
 ; CHECK-LABEL: @ssub_no_overflow_due_to_or_conds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sle i8 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i8 [[A]], 0
 ; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[C_2]], [[C_1]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[EXIT_FAIL:%.*]], label [[MATH:%.*]]
 ; CHECK:       math:
-; CHECK-NEXT:    [[OP:%.*]] = tail call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[B]], i8 [[A]])
-; CHECK-NEXT:    [[STATUS:%.*]] = extractvalue { i8, i1 } [[OP]], 1
-; CHECK-NEXT:    br i1 [[STATUS]], label [[EXIT_FAIL]], label [[EXIT_OK:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[B]], [[A]]
+; CHECK-NEXT:    br i1 false, label [[EXIT_FAIL]], label [[EXIT_OK:%.*]]
 ; CHECK:       exit.ok:
-; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i8, i1 } [[OP]], 0
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    ret i8 [[TMP0]]
 ; CHECK:       exit.fail:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %c.1 = icmp sle i8 %b, %a
   %c.2 = icmp slt i8 %a, 0
   %or.cond = or i1 %c.2, %c.1
   br i1 %or.cond, label %exit.fail, label %math

 define i8 @ssub_no_overflow_due_to_or_conds_result_used(i8 %a, i8 %b) {
 ; CHECK-LABEL: @ssub_no_overflow_due_to_or_conds_result_used(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sle i8 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp slt i8 [[A]], 0
 ; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[C_2]], [[C_1]]
 ; CHECK-NEXT:    br i1 [[OR_COND]], label [[EXIT_FAIL:%.*]], label [[MATH:%.*]]
 ; CHECK:       math:
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[B]], [[A]]
 ; CHECK-NEXT:    [[OP:%.*]] = tail call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[B]], i8 [[A]])
 ; CHECK-NEXT:    call void @use_res({ i8, i1 } [[OP]])
-; CHECK-NEXT:    [[STATUS:%.*]] = extractvalue { i8, i1 } [[OP]], 1
-; CHECK-NEXT:    br i1 [[STATUS]], label [[EXIT_FAIL]], label [[EXIT_OK:%.*]]
+; CHECK-NEXT:    br i1 false, label [[EXIT_FAIL]], label [[EXIT_OK:%.*]]
 ; CHECK:       exit.ok:
-; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i8, i1 } [[OP]], 0
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    ret i8 [[TMP0]]
 ; CHECK:       exit.fail:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %c.1 = icmp sle i8 %b, %a
   %c.2 = icmp slt i8 %a, 0
   %or.cond = or i1 %c.2, %c.1
   br i1 %or.cond, label %exit.fail, label %math

 define i8 @ssub_no_overflow_due_to_and_conds(i8 %a, i8 %b) {
 ; CHECK-LABEL: @ssub_no_overflow_due_to_and_conds(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i8 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sge i8 [[A]], 0
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], [[C_1]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[MATH:%.*]], label [[EXIT_FAIL:%.*]]
 ; CHECK:       math:
-; CHECK-NEXT:    [[OP:%.*]] = tail call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[B]], i8 [[A]])
-; CHECK-NEXT:    [[STATUS:%.*]] = extractvalue { i8, i1 } [[OP]], 1
-; CHECK-NEXT:    br i1 [[STATUS]], label [[EXIT_FAIL]], label [[EXIT_OK:%.*]]
+; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[B]], [[A]]
+; CHECK-NEXT:    br i1 false, label [[EXIT_FAIL]], label [[EXIT_OK:%.*]]
 ; CHECK:       exit.ok:
-; CHECK-NEXT:    [[RES:%.*]] = extractvalue { i8, i1 } [[OP]], 0
-; CHECK-NEXT:    ret i8 [[RES]]
+; CHECK-NEXT:    ret i8 [[TMP0]]
 ; CHECK:       exit.fail:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %c.1 = icmp sge i8 %b, %a
   %c.2 = icmp sge i8 %a, 0
   %and = and i1 %c.2, %c.1
   br i1 %and, label %math, label %exit.fail

 define i8 @ssub_no_overflow_due_to_and_conds_sub_result_not_used(i8 %a, i8 %b) {
 ; CHECK-LABEL: @ssub_no_overflow_due_to_and_conds_sub_result_not_used(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp sge i8 [[B:%.*]], [[A:%.*]]
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp sge i8 [[A]], 0
 ; CHECK-NEXT:    [[AND:%.*]] = and i1 [[C_2]], [[C_1]]
 ; CHECK-NEXT:    br i1 [[AND]], label [[MATH:%.*]], label [[EXIT_FAIL:%.*]]
 ; CHECK:       math:
-; CHECK-NEXT:    [[OP:%.*]] = tail call { i8, i1 } @llvm.ssub.with.overflow.i8(i8 [[B]], i8 [[A]])
-; CHECK-NEXT:    [[STATUS:%.*]] = extractvalue { i8, i1 } [[OP]], 1
-; CHECK-NEXT:    br i1 [[STATUS]], label [[EXIT_FAIL]], label [[EXIT_OK:%.*]]
+; CHECK-NEXT:    br i1 false, label [[EXIT_FAIL]], label [[EXIT_OK:%.*]]
 ; CHECK:       exit.ok:
 ; CHECK-NEXT:    ret i8 20
 ; CHECK:       exit.fail:
 ; CHECK-NEXT:    ret i8 0
 ;
 entry:
   %c.1 = icmp sge i8 %b, %a
   %c.2 = icmp sge i8 %a, 0