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 @@ -660,41 +660,68 @@ } } +static Instruction *getContextInstForUse(Use &U) { + Instruction *UserI = cast(U.getUser()); + if (auto *Phi = dyn_cast(UserI)) + UserI = Phi->getIncomingBlock(U)->getTerminator(); + return UserI; +} + namespace { /// Represents either /// * a condition that holds on entry to a block (=conditional fact) /// * an assume (=assume fact) -/// * an instruction to simplify. +/// * a use of a compare instruction to simplify. /// It also tracks the Dominator DFS in and out numbers for each entry. struct FactOrCheck { - Instruction *Inst; + union { + Instruction *Inst; + Use *U; + }; unsigned NumIn; unsigned NumOut; - bool IsCheck; + bool HasInst; bool Not; - FactOrCheck(DomTreeNode *DTN, Instruction *Inst, bool IsCheck, bool Not) + FactOrCheck(DomTreeNode *DTN, Instruction *Inst, bool Not) : Inst(Inst), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), - IsCheck(IsCheck), Not(Not) {} + HasInst(true), Not(Not) {} + + FactOrCheck(DomTreeNode *DTN, Use *U) + : U(U), NumIn(DTN->getDFSNumIn()), NumOut(DTN->getDFSNumOut()), + HasInst(false), Not(false) {} static FactOrCheck getFact(DomTreeNode *DTN, Instruction *Inst, bool Not = false) { - return FactOrCheck(DTN, Inst, false, Not); + return FactOrCheck(DTN, Inst, Not); } - static FactOrCheck getCheck(DomTreeNode *DTN, Instruction *Inst) { - return FactOrCheck(DTN, Inst, true, false); + static FactOrCheck getCheck(DomTreeNode *DTN, Use *U) { + return FactOrCheck(DTN, U); } - bool isAssumeFact() const { - if (!IsCheck && isa(Inst)) { - assert(match(Inst, m_Intrinsic())); - return true; - } - return false; + static FactOrCheck getCheck(DomTreeNode *DTN, CallInst *CI) { + return FactOrCheck(DTN, CI, false); } - bool isConditionFact() const { return !IsCheck && isa(Inst); } + bool isCheck() const { + return !HasInst || + match(Inst, m_Intrinsic()); + } + + Instruction *getContextInst() const { + if (HasInst) + return Inst; + return getContextInstForUse(*U); + } + Instruction *getInstructionToSimplify() const { + assert(isCheck()); + if (HasInst) + return Inst; + // The use may have been simplified to a constant already. + return dyn_cast(*U); + } + bool isConditionFact() const { return !isCheck() && isa(Inst); } }; /// Keep state required to build worklist. @@ -732,12 +759,19 @@ // Queue conditions and assumes. for (Instruction &I : BB) { if (auto Cmp = dyn_cast(&I)) { - WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), Cmp)); + for (Use &U : Cmp->uses()) { + auto *UserI = getContextInstForUse(U); + auto *DTN = DT.getNode(UserI->getParent()); + if (!DTN) + continue; + WorkList.push_back(FactOrCheck::getCheck(DTN, &U)); + } continue; } if (match(&I, m_Intrinsic())) { - WorkList.push_back(FactOrCheck::getCheck(DT.getNode(&BB), &I)); + WorkList.push_back( + FactOrCheck::getCheck(DT.getNode(&BB), cast(&I))); continue; } @@ -973,7 +1007,8 @@ } static bool checkAndReplaceCondition( - CmpInst *Cmp, ConstraintInfo &Info, Module *ReproducerModule, + CmpInst *Cmp, ConstraintInfo &Info, unsigned NumIn, unsigned NumOut, + Instruction *ContextInst, Module *ReproducerModule, ArrayRef ReproducerCondStack, DominatorTree &DT) { LLVM_DEBUG(dbgs() << "Checking " << *Cmp << "\n"); @@ -1018,7 +1053,16 @@ generateReproducer(Cmp, ReproducerModule, ReproducerCondStack, Info, DT); Constant *ConstantC = ConstantInt::getBool( CmpInst::makeCmpResultType(Cmp->getType()), IsTrue); - Cmp->replaceUsesWithIf(ConstantC, [](Use &U) { + Cmp->replaceUsesWithIf(ConstantC, [&DT, NumIn, NumOut, + ContextInst](Use &U) { + auto *UserI = getContextInstForUse(U); + auto *DTN = DT.getNode(UserI->getParent()); + if (!DTN || DTN->getDFSNumIn() < NumIn || DTN->getDFSNumOut() > NumOut) + return false; + if (UserI->getParent() == ContextInst->getParent() && + UserI->comesBefore(ContextInst)) + return false; + // Conditions in an assume trivially simplify to true. Skip uses // in assume calls to not destroy the available information. auto *II = dyn_cast(U.getUser()); @@ -1206,7 +1250,9 @@ return true; if (B.isConditionFact()) return false; - return A.Inst->comesBefore(B.Inst); + auto *InstA = A.getContextInst(); + auto *InstB = B.getContextInst(); + return InstA->comesBefore(InstB); } return A.NumIn < B.NumIn; }); @@ -1237,27 +1283,26 @@ DFSInStack); } - LLVM_DEBUG({ - dbgs() << "Processing "; - if (CB.IsCheck) - dbgs() << "condition to simplify: " << *CB.Inst; - else - dbgs() << "fact to add to the system: " << *CB.Inst; - dbgs() << "\n"; - }); + LLVM_DEBUG(dbgs() << "Processing "); // For a block, check if any CmpInsts become known based on the current set // of constraints. - if (CB.IsCheck) { - if (auto *II = dyn_cast(CB.Inst)) { + if (CB.isCheck()) { + Instruction *Inst = CB.getInstructionToSimplify(); + if (!Inst) + continue; + LLVM_DEBUG(dbgs() << "condition to simplify: " << *Inst << "\n"); + if (auto *II = dyn_cast(Inst)) { Changed |= tryToSimplifyOverflowMath(II, Info, ToRemove); - } else if (auto *Cmp = dyn_cast(CB.Inst)) { - Changed |= checkAndReplaceCondition(Cmp, Info, ReproducerModule.get(), - ReproducerCondStack, S.DT); + } else if (auto *Cmp = dyn_cast(Inst)) { + Changed |= checkAndReplaceCondition( + Cmp, Info, CB.NumIn, CB.NumOut, CB.getContextInst(), + ReproducerModule.get(), ReproducerCondStack, S.DT); } continue; } + LLVM_DEBUG(dbgs() << "fact to add to the system: " << *CB.Inst << "\n"); ICmpInst::Predicate Pred; Value *A, *B; Value *Cmp = CB.Inst; diff --git a/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll b/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll --- a/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll +++ b/llvm/test/Transforms/ConstraintElimination/and-implied-by-operands.ll @@ -203,7 +203,7 @@ ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[EXIT:%.*]] ; CHECK: then: ; CHECK-NEXT: [[C_4:%.*]] = icmp eq i32 [[Z:%.*]], 0 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[C_4]], i1 [[C_1]], i1 false +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[C_4]], i1 true, i1 false ; CHECK-NEXT: br label [[EXIT]] ; CHECK: exit: ; CHECK-NEXT: [[RES:%.*]] = phi i1 [ [[C_1]], [[ENTRY:%.*]] ], [ [[SEL]], [[THEN]] ] @@ -236,10 +236,10 @@ ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[EXIT:%.*]] ; CHECK: then: ; CHECK-NEXT: [[C_4:%.*]] = icmp eq i32 [[Z:%.*]], 0 -; CHECK-NEXT: [[SEL:%.*]] = select i1 [[C_4]], i1 [[C_1]], i1 false +; CHECK-NEXT: [[SEL:%.*]] = select i1 [[C_4]], i1 true, i1 false ; CHECK-NEXT: br i1 [[SEL]], label [[T_1:%.*]], label [[EXIT]] ; CHECK: t.1: -; CHECK-NEXT: ret i1 [[C_1]] +; CHECK-NEXT: ret i1 true ; CHECK: exit: ; CHECK-NEXT: [[RES:%.*]] = phi i1 [ [[C_1]], [[ENTRY:%.*]] ], [ [[SEL]], [[THEN]] ] ; CHECK-NEXT: ret i1 [[RES]] @@ -328,7 +328,7 @@ ; CHECK-NEXT: [[AND:%.*]] = and i1 [[C_1]], [[T_1]] ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: -; CHECK-NEXT: ret i1 [[T_1]] +; CHECK-NEXT: ret i1 true ; CHECK: else: ; CHECK-NEXT: ret i1 [[T_1]] ; @@ -356,7 +356,7 @@ ; CHECK: then: ; CHECK-NEXT: ret i1 [[T_1]] ; CHECK: else: -; CHECK-NEXT: ret i1 [[T_1]] +; CHECK-NEXT: ret i1 false ; entry: @@ -382,7 +382,7 @@ ; CHECK: then: ; CHECK-NEXT: ret i1 [[T_1]] ; CHECK: else: -; CHECK-NEXT: ret i1 [[T_1]] +; CHECK-NEXT: ret i1 false ; entry: 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 @@ -500,7 +500,6 @@ } ; The information of from the assume can be used to simplify %t.2. -; TODO define i1 @assume_single_bb_conditions_after_assume(i8 %a, i8 %b, i1 %c) { ; CHECK-LABEL: @assume_single_bb_conditions_after_assume( ; CHECK-NEXT: [[ADD_1:%.*]] = add nuw nsw i8 [[A:%.*]], 1 @@ -510,7 +509,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]], true +; CHECK-NEXT: [[RES_1:%.*]] = xor i1 true, 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]] @@ -575,7 +574,7 @@ ; 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: [[RES_1:%.*]] = xor i1 [[C_1]], [[T_2]] +; CHECK-NEXT: [[RES_1:%.*]] = xor i1 true, 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]] @@ -607,7 +606,7 @@ ; CHECK-NEXT: store volatile float 0.000000e+00, ptr [[DST:%.*]], align 4 ; CHECK-NEXT: [[C_2:%.*]] = icmp eq i16 [[A]], 20 ; CHECK-NEXT: tail call void @llvm.assume(i1 [[C_2]]) -; CHECK-NEXT: ret i1 [[C_2]] +; CHECK-NEXT: ret i1 true ; entry: %c.1 = icmp ult i16 %a, 10 diff --git a/llvm/test/Transforms/ConstraintElimination/cond-used-in-phi.ll b/llvm/test/Transforms/ConstraintElimination/cond-used-in-phi.ll --- a/llvm/test/Transforms/ConstraintElimination/cond-used-in-phi.ll +++ b/llvm/test/Transforms/ConstraintElimination/cond-used-in-phi.ll @@ -175,7 +175,7 @@ ; CHECK-NEXT: call void @llvm.assume(i1 [[CMP1]]) ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i1 [ [[CMP2]], [[IF]] ], [ false, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[PHI:%.*]] = phi i1 [ true, [[IF]] ], [ false, [[ENTRY:%.*]] ] ; CHECK-NEXT: ret i1 [[PHI]] ; entry: @@ -203,7 +203,7 @@ ; CHECK: then.1: ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i1 [ [[CMP2]], [[IF]] ], [ [[CMP2]], [[THEN_1]] ], [ false, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[PHI:%.*]] = phi i1 [ [[CMP2]], [[IF]] ], [ true, [[THEN_1]] ], [ false, [[ENTRY:%.*]] ] ; CHECK-NEXT: ret i1 [[PHI]] ; entry: @@ -235,7 +235,7 @@ ; CHECK: else.1: ; CHECK-NEXT: br label [[JOIN]] ; CHECK: join: -; CHECK-NEXT: [[PHI:%.*]] = phi i1 [ [[CMP2]], [[ELSE_1]] ], [ [[CMP2]], [[THEN_1]] ], [ false, [[ENTRY:%.*]] ] +; CHECK-NEXT: [[PHI:%.*]] = phi i1 [ false, [[ELSE_1]] ], [ true, [[THEN_1]] ], [ false, [[ENTRY:%.*]] ] ; CHECK-NEXT: ret i1 [[PHI]] ; entry: diff --git a/llvm/test/Transforms/ConstraintElimination/monotonic-pointer-phis-crashes.ll b/llvm/test/Transforms/ConstraintElimination/monotonic-pointer-phis-crashes.ll --- a/llvm/test/Transforms/ConstraintElimination/monotonic-pointer-phis-crashes.ll +++ b/llvm/test/Transforms/ConstraintElimination/monotonic-pointer-phis-crashes.ll @@ -66,7 +66,7 @@ ; CHECK-NEXT: br i1 [[C_1]], label [[IF:%.*]], label [[LOOP_HEADER]] ; CHECK: if: ; CHECK-NEXT: [[C_2:%.*]] = icmp ne ptr [[B]], null -; CHECK-NEXT: [[AND:%.*]] = and i1 [[C_2]], [[C_0]] +; CHECK-NEXT: [[AND:%.*]] = and i1 [[C_2]], true ; CHECK-NEXT: br i1 [[AND]], label [[THEN:%.*]], label [[EXIT]] ; CHECK: then: ; CHECK-NEXT: call void @clobber() diff --git a/llvm/test/Transforms/ConstraintElimination/uses-in-different-blocks.ll b/llvm/test/Transforms/ConstraintElimination/uses-in-different-blocks.ll --- a/llvm/test/Transforms/ConstraintElimination/uses-in-different-blocks.ll +++ b/llvm/test/Transforms/ConstraintElimination/uses-in-different-blocks.ll @@ -9,7 +9,7 @@ ; CHECK-NEXT: [[C_2:%.*]] = icmp ugt i8 [[X]], 5 ; CHECK-NEXT: br i1 [[C_1]], label [[THEN:%.*]], label [[ELSE:%.*]] ; CHECK: then: -; CHECK-NEXT: ret i1 [[T_1]] +; CHECK-NEXT: ret i1 true ; CHECK: else: ; CHECK-NEXT: ret i1 [[C_2]] ; @@ -38,7 +38,7 @@ ; CHECK: then.1: ; CHECK-NEXT: br i1 [[C_2]], label [[THEN_2:%.*]], label [[ELSE]] ; CHECK: then.2: -; CHECK-NEXT: ret i1 [[T_1]] +; CHECK-NEXT: ret i1 true ; CHECK: else: ; CHECK-NEXT: ret i1 [[C_3]] ;