diff --git a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp --- a/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp +++ b/llvm/lib/Transforms/Scalar/ConstraintElimination.cpp @@ -576,30 +576,46 @@ } 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(Inst)) { + assert(match(Inst, m_Intrinsic())); + return true; + } + return false; + } + + bool isConditionFact() const { return !IsCheck && isa(Inst); } }; /// Keep state required to build worklist. struct State { DominatorTree &DT; - SmallVector WorkList; + SmallVector WorkList; State(DominatorTree &DT) : DT(DT) {} @@ -644,16 +660,20 @@ #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(&I)) { + WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), Cmp)); + continue; + } + + if (match(&I, m_Intrinsic())) { + 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(m_Value(Cond))) && @@ -661,14 +681,11 @@ 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(Cond), false); + WorkList.emplace_back(FactOrCheck::getFact(DT.getNode(I.getParent()), + cast(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(Cond), false); - } + WorkList.emplace_back( + FactOrCheck::getFact(DT.getNode(I.getParent()), &I)); } } GuaranteedToExecute &= isGuaranteedToTransferExecutionToSuccessor(&I); @@ -705,7 +722,8 @@ while (!CondWorkList.empty()) { Value *Cur = CondWorkList.pop_back_val(); if (auto *Cmp = dyn_cast(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)))) { @@ -727,9 +745,11 @@ 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) { @@ -919,29 +939,41 @@ 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(B.Condition->getOperand(0)) && - !isa(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(B.Inst->getOperand(0)) && + !isa(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 ToRemove; // Finally, process ordered worklist and eliminate implied conditions. SmallVector 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()) { @@ -970,25 +1002,19 @@ 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(&I)) { - Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove); - continue; - } - auto *Cmp = dyn_cast(&I); - if (!Cmp) - continue; - + if (CB.IsCheck) { + if (auto *II = dyn_cast(CB.Inst)) { + Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove); + } else if (auto *Cmp = dyn_cast(CB.Inst)) { Changed |= checkAndReplaceCondition(Cmp, Info); } continue; @@ -996,7 +1022,9 @@ 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(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); diff --git a/llvm/test/Transforms/ConstraintElimination/assumes.ll b/llvm/test/Transforms/ConstraintElimination/assumes.ll --- a/llvm/test/Transforms/ConstraintElimination/assumes.ll +++ b/llvm/test/Transforms/ConstraintElimination/assumes.ll @@ -371,7 +371,7 @@ ; 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]] @@ -510,7 +510,7 @@ ; 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]] diff --git a/llvm/test/Transforms/ConstraintElimination/debug.ll b/llvm/test/Transforms/ConstraintElimination/debug.ll --- a/llvm/test/Transforms/ConstraintElimination/debug.ll +++ b/llvm/test/Transforms/ConstraintElimination/debug.ll @@ -5,11 +5,11 @@ 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