[ConstraintElim] Queue facts and checks directly.

[fhahn]

Summary

This allows interleaving facts and checks in a single block. In
particular this enables using facts from assumes for conditions in the
same block that come after the assume.

This could be extended to only try to simplify checks at the point where
a condition is used.

[nikic]

LGTM. A question I had is why we use this kind of upfront collection + sort approach at all. Wouldn't it be possible to do essentially the same in a single walk over the dominator tree?

[fhahn]

In D138452#3971049, @nikic wrote:

LGTM. A question I had is why we use this kind of upfront collection + sort approach at all. Wouldn't it be possible to do essentially the same in a single walk over the dominator tree?

Thanks! IIRC the main reason was to t make it easier to inject additional conditions for which no direct IR instruction exists, but that's not used in the version on main at the moment. I haven't thought a lot about what a single DT walk would look like, but a straight forward walk would probably be a recursive implementation and the worklist approach seems slightly simpler compared to that. I could look into the DT walk approach a bit more, if you think there's a significant benefit.

[uabelho]

Hi,
The following starts crashing with this patch:

opt -passes=constraint-elimination bbi-76661.ll -o /dev/null

I get

opt: ../lib/IR/Instruction.cpp:124: bool llvm::Instruction::comesBefore(const llvm::Instruction *) const: Assertion `Parent == Other->Parent && "cross-BB instruction order comparison"' failed.

bbi-76661.ll613 BDownload

[fhahn]

In D138452#3974011, @uabelho wrote:

Hi,
The following starts crashing with this patch:

opt -passes=constraint-elimination bbi-76661.ll -o /dev/null

I get

opt: ../lib/IR/Instruction.cpp:124: bool llvm::Instruction::comesBefore(const llvm::Instruction *) const: Assertion `Parent == Other->Parent && "cross-BB instruction order comparison"' failed.

bbi-76661.ll613 BDownload

Thanks for the report. Is it possible this is over-reduced? I cannot reproduce it locally or on godbolt: https://llvm.godbolt.org/z/T8f1q33hq

[bjope]

! In D138452#3974119, @fhahn wrote:

Thanks for the report. Is it possible this is over-reduced? I cannot reproduce it locally or on godbolt: https://llvm.godbolt.org/z/T8f1q33hq

uabelho seem to be offline right now, but I'll try to verify if the reproducer works for me or not. (Or I'll try to make a new reproducer, because I can see the test case that failed.) It might take me awhile though, but I'm on to it.

[bjope]

Ok, here is a godbolt repro: https://llvm.godbolt.org/z/98PvGaTe9

The difference is that the branch in the entry block now looks like:

br i1 %0, label %trap, label %1

[fhahn]

In D138452#3974418, @bjope wrote:

Ok, here is a godbolt repro: https://llvm.godbolt.org/z/98PvGaTe9

The difference is that the branch in the entry block now looks like:

br i1 %0, label %trap, label %1

Thanks, interestingly this doesn't seem to crash on macOS, but I was able to reproduce on Linux. Should be fixed in 9eda78107c4d

[bjope]

In D138452#3976219, @fhahn wrote:

In D138452#3974418, @bjope wrote:

Ok, here is a godbolt repro: https://llvm.godbolt.org/z/98PvGaTe9

The difference is that the branch in the entry block now looks like:

br i1 %0, label %trap, label %1

Thanks, interestingly this doesn't seem to crash on macOS, but I was able to reproduce on Linux. Should be fixed in 9eda78107c4d

Great! Fix seem to work. I've cherrypicked the fix and re-enabled ConstraintElimination in our (downstream) fuzzy testing again. Time will tell if we find more problems :-)

[uabelho]

In D138452#3974119, @fhahn wrote:

In D138452#3974011, @uabelho wrote:

Hi,
The following starts crashing with this patch:

opt -passes=constraint-elimination bbi-76661.ll -o /dev/null

I get

opt: ../lib/IR/Instruction.cpp:124: bool llvm::Instruction::comesBefore(const llvm::Instruction *) const: Assertion `Parent == Other->Parent && "cross-BB instruction order comparison"' failed.

bbi-76661.ll613 BDownload

Thanks for the report. Is it possible this is over-reduced? I cannot reproduce it locally or on godbolt: https://llvm.godbolt.org/z/T8f1q33hq

(I've been OOO a couple of days)
Strange. I tried again and the reproducer I uploaded indeed crashes for me on the commit on main that I tried on last week (83b3304dd2a).
Anyway, I see that @bjope fixed another repro so you could solve this.
Thanks both of you!

llvm/lib/Transforms/Scalar/ConstraintElimination.cpp

case CmpInst::ICMP_SGE:
     if (doesHold(CmpInst::ICMP_SGE, B, ConstantInt::get(B->getType(), 0))) {
       addFact(CmpInst::ICMP_UGE, A, B, NumIn, NumOut, DFSInStack);
     }
     break;
   }
 }
 
 namespace {
-/// Represents either a condition that holds on entry to a block or a basic
-/// block, with their respective Dominator DFS in and out numbers.
-struct ConstraintOrBlock {
+/// Represents either
+///  * a condition that holds on entry to a block (=conditional fact)
+///  * an assume (=assume fact)
+///  * an instruction to simplify.
+/// It also tracks the Dominator DFS in and out numbers for each entry.
+struct FactOrCheck {
+  Instruction *Inst;
   unsigned NumIn;
   unsigned NumOut;
-  bool IsBlock;
+  bool IsCheck;
   bool Not;
-  union {
-    BasicBlock *BB;
-    CmpInst *Condition;
-  };
 
-  ConstraintOrBlock(DomTreeNode *DTN)
-      : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(true),
-        BB(DTN->getBlock()) {}
-  ConstraintOrBlock(DomTreeNode *DTN, CmpInst *Condition, bool Not)
-      : NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), IsBlock(false),
-        Not(Not), Condition(Condition) {}
+  FactOrCheck(DomTreeNode *DTN, Instruction *Inst, bool IsCheck, bool Not)
+      : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()),
+        IsCheck(IsCheck), Not(Not) {}
+
+  static FactOrCheck getFact(DomTreeNode *DTN, Instruction *Inst,
+                             bool Not = false) {
+    return FactOrCheck(DTN, Inst, false, Not);
+  }
+
+  static FactOrCheck getCheck(DomTreeNode *DTN, Instruction *Inst) {
+    return FactOrCheck(DTN, Inst, true, false);
+  }
+
+  bool isAssumeFact() const {
+    if (!IsCheck && isa<IntrinsicInst>(Inst)) {
+      assert(match(Inst, m_Intrinsic<Intrinsic::assume>()));
+      return true;
+    }
+    return false;
+  }
+
+  bool isConditionFact() const { return !IsCheck && isa<CmpInst>(Inst); }
 };
 
 /// Keep state required to build worklist.
 struct State {
   DominatorTree &DT;
-  SmallVector<ConstraintOrBlock, 64> WorkList;
+  SmallVector<FactOrCheck, 64> WorkList;
 
   State(DominatorTree &DT) : DT(DT) {}
 
   /// Process block \p BB and add known facts to work-list.
   void addInfoFor(BasicBlock &BB);
 
   /// Returns true if we can add a known condition from BB to its successor
   /// block Succ. Each predecessor of Succ can either be BB or be dominated
static void dumpWithNames(ArrayRef<int64_t> C,
                           DenseMap<Value *, unsigned> &Value2Index) {
   ConstraintSystem CS;
   CS.addVariableRowFill(C);
   dumpWithNames(CS, Value2Index);
 }
 #endif
 
 void State::addInfoFor(BasicBlock &BB) {
-  WorkList.emplace_back(DT.getNode(&BB));
-
   // True as long as long as the current instruction is guaranteed to execute.
   bool GuaranteedToExecute = true;
-  // Scan BB for assume calls.
-  // TODO: also use this scan to queue conditions to simplify, so we can
-  // interleave facts from assumes and conditions to simplify in a single
-  // basic block. And to skip another traversal of each basic block when
-  // simplifying.
+  // Queue conditions and assumes.
   for (Instruction &I : BB) {
+    if (auto Cmp = dyn_cast<ICmpInst>(&I)) {
+      WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), Cmp));
+      continue;
+    }
+
+    if (match(&I, m_Intrinsic<Intrinsic::ssub_with_overflow>())) {
+      WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), &I));
+      continue;
+    }
+
     Value *Cond;
     // For now, just handle assumes with a single compare as condition.
     if (match(&I, m_Intrinsic<Intrinsic::assume>(m_Value(Cond))) &&
         isa<ICmpInst>(Cond)) {
       if (GuaranteedToExecute) {
         // The assume is guaranteed to execute when BB is entered, hence Cond
         // holds on entry to BB.
-        WorkList.emplace_back(DT.getNode(&BB), cast<ICmpInst>(Cond), false);
+        WorkList.emplace_back(FactOrCheck::getFact(DT.getNode(I.getParent()),
+                                                   cast<Instruction>(Cond)));
       } else {
-        // Otherwise the condition only holds in the successors.
-        for (BasicBlock *Succ : successors(&BB)) {
-          if (!canAddSuccessor(BB, Succ))
-            continue;
-          WorkList.emplace_back(DT.getNode(Succ), cast<ICmpInst>(Cond), false);
-        }
+        WorkList.emplace_back(
+            FactOrCheck::getFact(DT.getNode(I.getParent()), &I));
       }
     }
     GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I);
   }
 
   auto *Br = dyn_cast<BranchInst>(BB.getTerminator());
   if (!Br || !Br->isConditional())
     return;
if (canAddSuccessor(BB, Successor)) {
         if (SeenCond.insert(V).second)
           CondWorkList.push_back(V);
       };
       QueueValue(Op1);
       QueueValue(Op0);
       while (!CondWorkList.empty()) {
         Value *Cur = CondWorkList.pop_back_val();
         if (auto *Cmp = dyn_cast<ICmpInst>(Cur)) {
-          WorkList.emplace_back(DT.getNode(Successor), Cmp, IsOr);
+          WorkList.emplace_back(
+              FactOrCheck::getFact(DT.getNode(Successor), Cmp, IsOr));
           continue;
         }
         if (IsOr && match(Cur, m_LogicalOr(m_Value(Op0), m_Value(Op1)))) {
           QueueValue(Op1);
           QueueValue(Op0);
           continue;
         }
         if (IsAnd && match(Cur, m_LogicalAnd(m_Value(Op0), m_Value(Op1)))) {
           QueueValue(Op1);
           QueueValue(Op0);
           continue;
         }
       }
     }
     return;
   }
 
   auto *CmpI = dyn_cast<ICmpInst>(Br->getCondition());
   if (!CmpI)
     return;
   if (canAddSuccessor(BB, Br->getSuccessor(0)))
-    WorkList.emplace_back(DT.getNode(Br->getSuccessor(0)), CmpI, false);
+    WorkList.emplace_back(
+        FactOrCheck::getFact(DT.getNode(Br->getSuccessor(0)), CmpI));
   if (canAddSuccessor(BB, Br->getSuccessor(1)))
-    WorkList.emplace_back(DT.getNode(Br->getSuccessor(1)), CmpI, true);
+    WorkList.emplace_back(
+        FactOrCheck::getFact(DT.getNode(Br->getSuccessor(1)), CmpI, true));
 }
 
 static bool checkAndReplaceCondition(CmpInst *Cmp, ConstraintInfo &Info) {
   LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n");
 
   CmpInst::Predicate Pred = Cmp->getPredicate();
   Value *A = Cmp->getOperand(0);
   Value *B = Cmp->getOperand(1);
static bool eliminateConstraints(Function &F, DominatorTree &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. Also make sure conditions with constant
-  // operands come before conditions without constant operands. This increases
-  // the effectiveness of the current signed <-> unsigned fact transfer logic.
-  stable_sort(
-      S.WorkList, [](const ConstraintOrBlock &A, const ConstraintOrBlock &B) {
-        auto HasNoConstOp = [](const ConstraintOrBlock &B) {
-          return !B.IsBlock && !isa<ConstantInt>(B.Condition->getOperand(0)) &&
-                 !isa<ConstantInt>(B.Condition->getOperand(1));
-        };
+  // Next, sort worklist by dominance, so that dominating conditions to check
+  // and facts come before conditions and facts dominated by them. If a
+  // condition to check and a fact have the same numbers, conditional facts come
+  // first. Assume facts and checks are ordered according to their relative
+  // order in the containing basic block. Also make sure conditions with
+  // constant operands come before conditions without constant operands. This
+  // increases the effectiveness of the current signed <-> unsigned fact
+  // transfer logic.
+  stable_sort(S.WorkList, [](const FactOrCheck &A, const FactOrCheck &B) {
+    auto HasNoConstOp = [](const FactOrCheck &B) {
+      return !isa<ConstantInt>(B.Inst->getOperand(0)) &&
+             !isa<ConstantInt>(B.Inst->getOperand(1));
+    // If both entries have the same In numbers, conditional facts come first.
+    // Otherwise use the relative order in the basic block.
+    if (A.NumIn == B.NumIn) {
+      if (A.isConditionFact() && B.IsCheck)
+        return true;
+      if (B.isConditionFact() && A.IsCheck)
+        return false;
+      if (A.isConditionFact() && B.isConditionFact()) {
         bool NoConstOpA = HasNoConstOp(A);
         bool NoConstOpB = HasNoConstOp(B);
-        return std::tie(A.NumIn, A.IsBlock, NoConstOpA) <
-               std::tie(B.NumIn, B.IsBlock, NoConstOpB);
-      });
+        return NoConstOpA < NoConstOpB;
+      }
+      return A.Inst->comesBefore(B.Inst);
+    }
+    return A.NumIn < B.NumIn;
 
   SmallVector<Instruction *> ToRemove;
 
   // Finally, process ordered worklist and eliminate implied conditions.
   SmallVector<StackEntry, 16> DFSInStack;
-  for (ConstraintOrBlock &CB : S.WorkList) {
+  for (FactOrCheck &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
                         << "\n");
       LLVM_DEBUG(dbgs() << "CB: " << CB.NumIn << " " << CB.NumOut << "\n");
       assert(E.NumIn <= CB.NumIn);
while (!DFSInStack.empty()) {
       for (Value *V : E.ValuesToRelease)
         Mapping.erase(V);
       Info.popLastNVariables(E.IsSigned, E.ValuesToRelease.size());
       DFSInStack.pop_back();
     }
 
     LLVM_DEBUG({
       dbgs() << "Processing ";
-      if (CB.IsBlock)
-        dbgs() << *CB.BB;
+      if (CB.IsCheck)
+        dbgs() << "condition to simplify: " << *CB.Inst;
       else
-        dbgs() << *CB.Condition;
+        dbgs() << "fact to add to the system: " << *CB.Inst;
       dbgs() << "\n";
     });
 
     // For a block, check if any CmpInsts become known based on the current set
     // of constraints.
-    if (CB.IsBlock) {
-      for (Instruction &I : make_early_inc_range(*CB.BB)) {
-        if (auto *II = dyn_cast<WithOverflowInst>(&I)) {
-          Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove);
-          continue;
-        }
-        auto *Cmp = dyn_cast<ICmpInst>(&I);
-        if (!Cmp)
-          continue;
-
+    if (CB.IsCheck) {
+      if (auto *II = dyn_cast<WithOverflowInst>(CB.Inst)) {
+      } else if (auto *Cmp = dyn_cast<ICmpInst>(CB.Inst)) {
         Changed |= checkAndReplaceCondition(Cmp, Info);
       }
       continue;
     }
 
     ICmpInst::Predicate Pred;
     Value *A, *B;
-    if (match(CB.Condition, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
+    Value *Cmp = CB.Inst;
+    match(Cmp, m_Intrinsic<Intrinsic::assume>(m_Value(Cmp)));
+    if (match(Cmp, m_ICmp(Pred, m_Value(A), m_Value(B)))) {
       // Use the inverse predicate if required.
       if (CB.Not)
         Pred = CmpInst::getInversePredicate(Pred);
 
       Info.addFact(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
       Info.transferToOtherSystem(Pred, A, B, CB.NumIn, CB.NumOut, DFSInStack);
     }
   }

llvm/test/Transforms/ConstraintElimination/assumes.ll

 define i1 @assume_same_bb_after_may_exiting_call(i8 %a, i8 %b, i1 %c) {
 ; CHECK-LABEL: @assume_same_bb_after_may_exiting_call(
 ; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw nsw i8 [[A:%.*]], 1
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ule i8 [[ADD_1]], [[B:%.*]]
 ; CHECK-NEXT:    call void @may_unwind()
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP_1]])
 ; CHECK-NEXT:    [[T_1:%.*]] = icmp ule i8 [[ADD_1]], [[B]]
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8 [[A]], [[B]]
-; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[T_1]], [[T_2]]
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 true, true
 ; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw nsw i8 [[A]], 2
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i8 [[ADD_2]], [[B]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[C_1]]
 ; CHECK-NEXT:    br label [[EXIT:%.*]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret i1 [[RES_2]]
 ;
   %add.1 = add nsw nuw i8 %a, 1

 ; CHECK-LABEL: @assume_single_bb_conditions_after_assume(
 ; CHECK-NEXT:    [[ADD_1:%.*]] = add nuw nsw i8 [[A:%.*]], 1
 ; CHECK-NEXT:    [[CMP_1:%.*]] = icmp ule i8 [[ADD_1]], [[B:%.*]]
 ; CHECK-NEXT:    [[C_1:%.*]] = icmp ule i8 [[ADD_1]], [[B]]
 ; CHECK-NEXT:    call void @use(i1 [[C_1]])
 ; CHECK-NEXT:    call void @may_unwind()
 ; CHECK-NEXT:    call void @llvm.assume(i1 [[CMP_1]])
 ; CHECK-NEXT:    [[T_2:%.*]] = icmp ule i8 [[A]], [[B]]
-; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[C_1]], [[T_2]]
+; CHECK-NEXT:    [[RES_1:%.*]] = xor i1 [[C_1]], true
 ; CHECK-NEXT:    [[ADD_2:%.*]] = add nuw nsw i8 [[A]], 2
 ; CHECK-NEXT:    [[C_2:%.*]] = icmp ule i8 [[ADD_2]], [[B]]
 ; CHECK-NEXT:    [[RES_2:%.*]] = xor i1 [[RES_1]], [[C_2]]
 ; CHECK-NEXT:    ret i1 [[RES_2]]
 ;
   %add.1 = add nsw nuw i8 %a, 1
   %cmp.1 = icmp ule i8 %add.1, %b
   %c.1 = icmp ule i8 %add.1, %b

llvm/test/Transforms/ConstraintElimination/debug.ll

 ; RUN: opt -passes=constraint-elimination -S -debug %s 2>&1 | FileCheck %s
 
 ; REQUIRES: asserts
 
 declare void @use(i1)
 
 define i1 @test_and_ule(i4 %x, i4 %y, i4 %z) {
-; CHECK:      Processing   %c.1 = icmp ule i4 %x, %y
+; CHECK:      Processing fact to add to the system:  %c.1 = icmp ule i4 %x, %y
 ; CHECK-NEXT: Adding 'ule %x, %y'
 ; CHECK-NEXT:  constraint: %x + -1 * %y <= 0
 
-; CHECK:      Processing   %c.2 = icmp ule i4 %y, %z
+; CHECK:      Processing fact to add to the system:  %c.2 = icmp ule i4 %y, %z
 ; CHECK-NEXT: Adding 'ule %y, %z'
 ; CHECK-NEXT:  constraint: %y + -1 * %z <= 0
 
 ; CHECK: Checking   %t.1 = icmp ule i4 %x, %z
 ; CHECK: Condition   %t.1 = icmp ule i4 %x, %z implied by dominating constraints
 
 entry:
   %c.1 = icmp ule i4 %x, %y