Index: llvm/include/llvm/Analysis/MustExecute.h =================================================================== --- llvm/include/llvm/Analysis/MustExecute.h +++ llvm/include/llvm/Analysis/MustExecute.h @@ -275,16 +275,17 @@ using ExplorerTy = MustBeExecutedContextExplorer; MustBeExecutedIterator(const MustBeExecutedIterator &Other) - : Visited(Other.Visited), Explorer(Other.Explorer), - CurInst(Other.CurInst) {} + : Visited(Other.Visited), Backward(Other.Backward), + Explorer(Other.Explorer), CurInst(Other.CurInst) {} MustBeExecutedIterator(MustBeExecutedIterator &&Other) - : Visited(std::move(Other.Visited)), Explorer(Other.Explorer), - CurInst(Other.CurInst) {} + : Visited(std::move(Other.Visited)), Backward(std::move(Other.Backward)), + Explorer(Other.Explorer), CurInst(Other.CurInst) {} MustBeExecutedIterator &operator=(MustBeExecutedIterator &&Other) { if (this != &Other) { std::swap(Visited, Other.Visited); + std::swap(Backward, Other.Backward); std::swap(CurInst, Other.CurInst); } return *this; @@ -306,10 +307,10 @@ } ///} - /// Equality and inequality operators. Note that we ignore the history here. + /// Equality and inequality operators. ///{ bool operator==(const MustBeExecutedIterator &Other) const { - return CurInst == Other.CurInst; + return CurInst == Other.CurInst && Backward == Other.Backward; } bool operator!=(const MustBeExecutedIterator &Other) const { @@ -343,6 +344,9 @@ /// loops and recursion. VisitedSetTy Visited; + /// A backward history from given program point to current instruction. + SmallVector Backward; + /// A reference to the explorer that created this iterator. ExplorerTy &Explorer; @@ -429,6 +433,25 @@ getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP); + /// Return the previous instruction that is guaranteed to be executed before \p PP. + /// + /// \param It The iterator that is used to traverse the must be + /// executed context. + /// \param PP The program point for which the previous instruction + /// that is guaranteed to execute is determined. + const Instruction * + getMustBeExecutedPrevInstruction(MustBeExecutedIterator &It, + const Instruction *PP); + + + /// Store the instructions that is guaranteed to be executed before \p PP. + /// + /// \param It The iterator that is used to traverse the must be + /// executed context. + /// \param PP The program point traced backward. + void backwardToMustBeExecutedStartPoint(MustBeExecutedIterator &It, + const Instruction *PP); + /// Parameter that limit the performed exploration. See the constructor for /// their meaning. ///{ Index: llvm/lib/Analysis/MustExecute.cpp =================================================================== --- llvm/lib/Analysis/MustExecute.cpp +++ llvm/lib/Analysis/MustExecute.cpp @@ -487,6 +487,53 @@ return nullptr; } +const Instruction * +MustBeExecutedContextExplorer::getMustBeExecutedPrevInstruction( + MustBeExecutedIterator &It, const Instruction *PP) { + if (!PP) + return PP; + LLVM_DEBUG(dbgs() << "Find previous instruction for " << *PP << "\n"); + + // If we explore only inside a given basic block we stop at front of the + // block. + if (!ExploreInterBlock && &PP->getParent()->front() == PP) { + LLVM_DEBUG(dbgs() << "\tReached terminator in intra-block mode, done\n"); + return nullptr; + } + + if (&PP->getParent()->front() == PP) { + if (const BasicBlock *PrevBB = PP->getParent()->getSinglePredecessor()) + return PrevBB->getTerminator(); + + LLVM_DEBUG(dbgs() << "\tNot found single predecessor, done\n"); + + return nullptr; + } + + const Instruction *PrevPP = PP->getPrevNode(); + + // Check if the previous instruction is guaranteed to transfer execution to + // the successor. + bool TransfersExecution = isGuaranteedToTransferExecutionToSuccessor(PrevPP); + if (!TransfersExecution) + return nullptr; + + return PrevPP; +} + +void MustBeExecutedContextExplorer::backwardToMustBeExecutedStartPoint( + llvm::MustBeExecutedIterator &It, const llvm::Instruction *I) { + const Instruction *SuccInst; + DenseSet Visited; + + do { + It.Backward.push_back(I); + SuccInst = I; + Visited.insert(SuccInst); + I = getMustBeExecutedPrevInstruction(It, I); + } while (I && !Visited.count(I)); +} + MustBeExecutedIterator::MustBeExecutedIterator( MustBeExecutedContextExplorer &Explorer, const Instruction *I) : Explorer(Explorer), CurInst(I) { @@ -494,15 +541,20 @@ } void MustBeExecutedIterator::reset(const Instruction *I) { - CurInst = I; + + Backward.clear(); + Explorer.backwardToMustBeExecutedStartPoint(*this, I); + CurInst = Backward.pop_back_val(); Visited.clear(); - Visited.insert(I); + Visited.insert(CurInst); } const Instruction *MustBeExecutedIterator::advance() { assert(CurInst && "Cannot advance an end iterator!"); const Instruction *Next = - Explorer.getMustBeExecutedNextInstruction(*this, CurInst); + Backward.size() + ? Backward.pop_back_val() + : Explorer.getMustBeExecutedNextInstruction(*this, CurInst); if (Next && !Visited.insert(Next).second) Next = nullptr; return Next; Index: llvm/test/Analysis/MustExecute/must_be_executed_context.ll =================================================================== --- llvm/test/Analysis/MustExecute/must_be_executed_context.ll +++ llvm/test/Analysis/MustExecute/must_be_executed_context.ll @@ -40,6 +40,7 @@ call void @B() ; MBEC: -- Explore context of: call void @B() +; MBEC-NEXT: [F: simple_conditional] call void @A() ; MBEC-NEXT: [F: simple_conditional] call void @B() ; MBEC-NEXT: [F: simple_conditional] %tmp = icmp eq i32 %arg, 0 ; MBEC-NEXT: [F: simple_conditional] br i1 %tmp, label %bb2, label %bb1 @@ -52,6 +53,10 @@ bb1: ; preds = %bb call void @C() ; MBEC: -- Explore context of: call void @C() +; MBEC-NEXT: [F: simple_conditional] call void @A() +; MBEC-NEXT: [F: simple_conditional] call void @B() +; MBEC-NEXT: [F: simple_conditional] %tmp = icmp eq i32 %arg, 0 +; MBEC-NEXT: [F: simple_conditional] br i1 %tmp, label %bb2, label %bb1 ; MBEC-NEXT: [F: simple_conditional] call void @C() ; MBEC-NEXT: [F: simple_conditional] call void @D() ; MBEC-NEXT: [F: simple_conditional] br label %bb2 @@ -61,6 +66,11 @@ call void @D() ; MBEC: -- Explore context of: call void @D() +; MBEC-NEXT: [F: simple_conditional] call void @A() +; MBEC-NEXT: [F: simple_conditional] call void @B() +; MBEC-NEXT: [F: simple_conditional] %tmp = icmp eq i32 %arg, 0 +; MBEC-NEXT: [F: simple_conditional] br i1 %tmp, label %bb2, label %bb1 +; MBEC-NEXT: [F: simple_conditional] call void @C() ; MBEC-NEXT: [F: simple_conditional] call void @D() ; MBEC-NEXT: [F: simple_conditional] br label %bb2 ; MBEC-NEXT: [F: simple_conditional] call void @E() @@ -79,6 +89,7 @@ call void @F() ; might not return! ; MBEC: -- Explore context of: call void @F() +; MBEC-NEXT: [F: simple_conditional] call void @E() ; MBEC-NEXT: [F: simple_conditional] call void @F() ; MBEC-NOT: call @@ -149,6 +160,7 @@ call void @B() ; ME: call void @B() ; (mustexec in: bb2) ; MBEC: -- Explore context of: call void @B() +; MBEC-NEXT: [F: complex_loops_and_control] %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ] ; MBEC-NEXT: [F: complex_loops_and_control] call void @B() ; MBEC-NEXT: [F: complex_loops_and_control] %tmp = add nsw i32 %.0, 1 ; MBEC-NEXT: [F: complex_loops_and_control] %tmp3 = icmp eq i32 %tmp, %arg1 @@ -164,8 +176,14 @@ ; ME: call void @C() ; ME-NOT: mustexec ; ME-NEXT: br -; FIXME: Missing A and B (backward) +; FIXME: Missing A (backward) + ; MBEC: -- Explore context of: call void @C() +; MBEC-NEXT: [F: complex_loops_and_control] %.0 = phi i32 [ %arg, %bb ], [ %.0.be, %.backedge ] +; MBEC-NEXT: [F: complex_loops_and_control] call void @B() +; MBEC-NEXT: [F: complex_loops_and_control] %tmp = add nsw i32 %.0, 1 +; MBEC-NEXT: [F: complex_loops_and_control] %tmp3 = icmp eq i32 %tmp, %arg1 +; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp3, label %bb4, label %bb5 ; MBEC-NEXT: [F: complex_loops_and_control] call void @C() ; MBEC-NEXT: [F: complex_loops_and_control] br label %bb5 ; MBEC-NEXT: [F: complex_loops_and_control] %tmp6 = add nsw i32 %.0, 2 @@ -194,6 +212,9 @@ ; ME-NEXT: %tmp10 ; FIXME: Missing A and B (backward) ; MBEC: -- Explore context of: call void @D() +; MBEC-NEXT: [F: complex_loops_and_control] %tmp6 = add nsw i32 %.0, 2 +; MBEC-NEXT: [F: complex_loops_and_control] %tmp7 = icmp eq i32 %tmp6, %arg1 +; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp7, label %bb8, label %bb9 ; MBEC-NEXT: [F: complex_loops_and_control] call void @D() ; MBEC-NEXT: [F: complex_loops_and_control] %tmp10 = add nsw i32 %.0, 3 ; MBEC-NEXT: [F: complex_loops_and_control] %tmp11 = icmp eq i32 %tmp10, %arg1 @@ -226,6 +247,10 @@ ; ME-NEXT: br ; FIXME: Missing A, B, and D (backward), as well as F ; MBEC: -- Explore context of: call void @E() +; MBEC-NEXT: [F: complex_loops_and_control] %.1 = phi i32 [ %tmp10, %bb13 ], [ %tmp20, %bb19 ] +; MBEC-NEXT: [F: complex_loops_and_control] %tmp15 = add nsw i32 %.1, 1 +; MBEC-NEXT: [F: complex_loops_and_control] %tmp16 = icmp eq i32 %tmp15, %arg1 +; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp16, label %bb17, label %bb18 ; MBEC-NEXT: [F: complex_loops_and_control] call void @E() ; MBEC-NEXT: [F: complex_loops_and_control] br label %bb19 ; MBEC-NEXT: [F: complex_loops_and_control] %tmp20 = add nsw i32 %.1, 2 @@ -248,6 +273,10 @@ ; ME-NEXT: br ; FIXME: Missing A, B, and D (backward) ; MBEC: -- Explore context of: call void @F() +; MBEC-NEXT: [F: complex_loops_and_control] %tmp20 = add nsw i32 %.1, 2 +; MBEC-NEXT: [F: complex_loops_and_control] %tmp21 = icmp eq i32 %tmp20, %arg1 +; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp21, label %bb14, label %bb22 +; MBEC-NEXT: [F: complex_loops_and_control] %.lcssa = phi i32 [ %tmp20, %bb19 ] ; MBEC-NEXT: [F: complex_loops_and_control] call void @F() ; MBEC-NOT: call ; MBEC: -- Explore context of: br @@ -258,8 +287,16 @@ ; ME: call void @G() ; ME-NOT: mustexec ; ME-NEXT: ret -; FIXME: Missing A, B, and D (backward) +; FIXME: Missing A and B (backward) ; MBEC: -- Explore context of: call void @G() +; MBEC-NEXT: [F: complex_loops_and_control] %tmp6 = add nsw i32 %.0, 2 +; MBEC-NEXT: [F: complex_loops_and_control] %tmp7 = icmp eq i32 %tmp6, %arg1 +; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp7, label %bb8, label %bb9 +; MBEC-NEXT: [F: complex_loops_and_control] call void @D() +; MBEC-NEXT: [F: complex_loops_and_control] %tmp10 = add nsw i32 %.0, 3 +; MBEC-NEXT: [F: complex_loops_and_control] %tmp11 = icmp eq i32 %tmp10, %arg1 +; MBEC-NEXT: [F: complex_loops_and_control] br i1 %tmp11, label %bb12, label %bb13 +; MBEC-NEXT: [F: complex_loops_and_control] br label %bb23 ; MBEC-NEXT: [F: complex_loops_and_control] call void @G() ; MBEC-NEXT: [F: complex_loops_and_control] ret void ; MBEC-NOT: call