diff --git a/llvm/include/llvm/Analysis/MustExecute.h b/llvm/include/llvm/Analysis/MustExecute.h --- a/llvm/include/llvm/Analysis/MustExecute.h +++ b/llvm/include/llvm/Analysis/MustExecute.h @@ -36,6 +36,7 @@ class Instruction; class DominatorTree; +class PostDominatorTree; class Loop; /// Captures loop safety information. @@ -376,8 +377,11 @@ /// \param ExploreInterBlock Flag to indicate if instructions in blocks /// other than the parent of PP should be /// explored. - MustBeExecutedContextExplorer(bool ExploreInterBlock) - : ExploreInterBlock(ExploreInterBlock), EndIterator(*this, nullptr), + MustBeExecutedContextExplorer(bool ExploreInterBlock, + const LoopInfo *LI = nullptr, + const PostDominatorTree *PDT = nullptr) + : ExploreInterBlock(ExploreInterBlock), LI(LI), PDT(PDT), + EndIterator(*this, nullptr), IsGuaranteedToTransferFn([](const Instruction *I) { return isGuaranteedToTransferExecutionToSuccessor(I); }) {} @@ -435,6 +439,9 @@ getMustBeExecutedNextInstruction(MustBeExecutedIterator &It, const Instruction *PP); + /// Find the next join point from \p InitBB in forward direction. + const BasicBlock *findForwardJoinPoint(const BasicBlock *InitBB); + /// Parameter that limit the performed exploration. See the constructor for /// their meaning. ///{ @@ -449,6 +456,19 @@ } private: + /// CFG analyses + /// + ///{ + const LoopInfo* LI; + const PostDominatorTree* PDT; + ///} + + /// Map to cache isGuaranteedToTransferExecutionToSuccessor results. + DenseMap> BlockTransferMap; + + /// Map to cache containsIrreducibleCFG results. + DenseMap> IrreducibleControlMap; + /// Map from instructions to associated must be executed iterators. DenseMap InstructionIteratorMap; diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp --- a/llvm/lib/Analysis/MustExecute.cpp +++ b/llvm/lib/Analysis/MustExecute.cpp @@ -12,6 +12,7 @@ #include "llvm/Analysis/InstructionSimplify.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/Passes.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/IR/AssemblyAnnotationWriter.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/InstIterator.h" @@ -442,6 +443,159 @@ return false; } +/// Return true if \p L might be an endless loop. +static bool maybeEndlessLoop(const Loop &L) { + if (L.getHeader()->getParent()->hasFnAttribute(Attribute::WillReturn)) + return false; + // TODO: Actually try to prove it is not. + // TODO: If maybeEndlessLoop is going to be expensive, cache it. + return true; +} + +static bool mayContainIrreducibleControl(const Function &F, const LoopInfo *LI) { + if (!LI) + return false; + using RPOTraversal = ReversePostOrderTraversal; + RPOTraversal FuncRPOT(&F); + return !containsIrreducibleCFG(FuncRPOT, *LI); +} + +/// Lookup \p Key in \p Map and return the result, potentially after +/// initializing the optional through \p Fn(\p args). +template +static V getOrCreateCachedOptional(K Key, DenseMap> &Map, + FnTy &&Fn, ArgsTy&&... args) { + Optional &OptVal = Map[Key]; + if (!OptVal.hasValue()) + OptVal = Fn(std::forward(args)...); + return OptVal.getValue(); +} + +const BasicBlock * +MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) { + LLVM_DEBUG(dbgs() << "\tFind forward join point for " << InitBB->getName() + << (LI ? " [LI]" : "") << (PDT ? " [PDT]" : "")); + + const Function &F = *InitBB->getParent(); + const Loop *L = LI ? LI->getLoopFor(InitBB) : nullptr; + const BasicBlock *HeaderBB = L ? L->getHeader() : InitBB; + bool WillReturnAndNoThrow = (F.hasFnAttribute(Attribute::WillReturn) || + (L && !maybeEndlessLoop(*L))) && + F.doesNotThrow(); + LLVM_DEBUG(dbgs() << (L ? " [in loop]" : "") + << (WillReturnAndNoThrow ? " [WillReturn] [NoUnwind]" : "") + << "\n"); + + // Determine the adjacent blocks in the given direction but exclude (self) + // loops under certain circumstances. + SmallVector Worklist; + for (const BasicBlock *SuccBB : successors(InitBB)) { + bool IsLatch = SuccBB == HeaderBB; + // Loop latches are ignored in forward propagation if the loop cannot be + // endless and may not throw: control has to go somewhere. + if (!WillReturnAndNoThrow || !IsLatch) + Worklist.push_back(SuccBB); + } + LLVM_DEBUG(dbgs() << "\t\t#Worklist: " << Worklist.size() << "\n"); + + // If there are no other adjacent blocks, there is no join point. + if (Worklist.empty()) + return nullptr; + + // If there is one adjacent block, it is the join point. + if (Worklist.size() == 1) + return Worklist[0]; + + // Try to determine a join block through the help of the post-dominance + // tree. If no tree was provided, we perform simple pattern matching for one + // block conditionals only. + const BasicBlock *JoinBB = nullptr; + if (PDT) + if (const auto *InitNode = PDT->getNode(InitBB)) + if (const auto *IDomNode = InitNode->getIDom()) + JoinBB = IDomNode->getBlock(); + + if (!JoinBB && Worklist.size() == 2) { + const BasicBlock *Succ0 = Worklist[0]; + const BasicBlock *Succ1 = Worklist[1]; + const BasicBlock *Succ0UniqueSucc = Succ0->getUniqueSuccessor(); + const BasicBlock *Succ1UniqueSucc = Succ1->getUniqueSuccessor(); + if (Succ0 == Succ1UniqueSucc) { + // InitBB -> Succ0 = JoinBB + // InitBB -> Succ1 -> Succ0 = JoinBB + JoinBB = Succ0; + } else if (Succ1 == Succ0UniqueSucc) { + // InitBB -> Succ0 -> Succ1 = JoinBB + // InitBB -> Succ1 = JoinBB + JoinBB = Succ1; + } else if (Succ0UniqueSucc == Succ1UniqueSucc) { + // InitBB -> Succ0 -> JoinBB + // InitBB -> Succ1 -> JoinBB + JoinBB = Succ0UniqueSucc; + } + } + + if (!JoinBB && L) + JoinBB = L->getUniqueExitBlock(); + + if (!JoinBB) + return nullptr; + + LLVM_DEBUG(dbgs() << "\t\tJoin block candidate: " << JoinBB->getName() << "\n"); + + // In forward direction we check if control will for sure reach JoinBB from + // InitBB, thus it can not be "stopped" along the way. Ways to "stop" control + // are: infinite loops and instructions that do not necessarily transfer + // execution to their successor. To check for them we traverse the CFG from + // the adjacent blocks to the JoinBB, looking at all intermediate blocks. + + // If we know the function is "will-return" and "no-throw" there is no need + // for futher checks. + if (!F.hasFnAttribute(Attribute::WillReturn) || !F.doesNotThrow()) { + + auto BlockTransfersExecutionToSuccessor = [](const BasicBlock *BB) { + return isGuaranteedToTransferExecutionToSuccessor(BB); + }; + + SmallPtrSet Visited; + while (!Worklist.empty()) { + const BasicBlock *ToBB = Worklist.pop_back_val(); + if (ToBB == JoinBB) + continue; + + // Make sure all loops in-between are finite. + if (!Visited.insert(ToBB).second) { + if (!F.hasFnAttribute(Attribute::WillReturn)) { + bool MayContainIrreducibleControl = getOrCreateCachedOptional( + &F, IrreducibleControlMap, mayContainIrreducibleControl, F, LI); + if (MayContainIrreducibleControl) + return nullptr; + + const Loop *L = LI->getLoopFor(ToBB); + if (L && maybeEndlessLoop(*L)) + return nullptr; + } + + continue; + } + + // Make sure the block has no instructions that could stop control + // transfer. + bool TransfersExecution = getOrCreateCachedOptional( + ToBB, BlockTransferMap, BlockTransfersExecutionToSuccessor, ToBB); + if (!TransfersExecution) + return nullptr; + + for (const BasicBlock *AdjacentBB : successors(ToBB)) + Worklist.push_back(AdjacentBB); + } + } + + LLVM_DEBUG(dbgs() << "\tJoin block: " << JoinBB->getName() << "\n"); + return JoinBB; +} + const Instruction * MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction( MustBeExecutedIterator &It, const Instruction *PP) { @@ -489,6 +643,12 @@ return &PP->getSuccessor(0)->front(); } + // Multiple successors mean we need to find the join point where control flow + // converges again. We use the findForwardJoinPoint helper function with + // information about the function and helper analyses, if available. + if (const BasicBlock *JoinBB = findForwardJoinPoint(PP->getParent())) + return &JoinBB->front(); + LLVM_DEBUG(dbgs() << "\tNo join point found\n"); return nullptr; } diff --git a/llvm/test/Analysis/MustExecute/must_be_executed_context.ll b/llvm/test/Analysis/MustExecute/must_be_executed_context.ll --- a/llvm/test/Analysis/MustExecute/must_be_executed_context.ll +++ b/llvm/test/Analysis/MustExecute/must_be_executed_context.ll @@ -36,6 +36,8 @@ ; 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 @E() +; MBEC-NEXT: [F: simple_conditional] call void @F() ; MBEC-NOT: call call void @B() @@ -43,6 +45,8 @@ ; 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 @E() +; MBEC-NEXT: [F: simple_conditional] call void @F() ; MBEC-NOT: call ; MBEC: -- Explore context of: %tmp diff --git a/llvm/test/Transforms/FunctionAttrs/nonnull.ll b/llvm/test/Transforms/FunctionAttrs/nonnull.ll --- a/llvm/test/Transforms/FunctionAttrs/nonnull.ll +++ b/llvm/test/Transforms/FunctionAttrs/nonnull.ll @@ -270,8 +270,7 @@ ; fun1(nonnull %a) ; We can say that %a is nonnull define void @f17(i8* %a, i8 %c) { -; FIXME: missing nonnull on %a -; ATTRIBUTOR: define void @f17(i8* %a, i8 %c) +; ATTRIBUTOR: define void @f17(i8* nonnull %a, i8 %c) %cmp = icmp eq i8 %c, 0 br i1 %cmp, label %if.then, label %if.else if.then: @@ -296,8 +295,7 @@ ; fun1(nonnull %a) define void @f18(i8* %a, i8* %b, i8 %c) { -; FIXME: missing nonnull on %a -; ATTRIBUTOR: define void @f18(i8* %a, i8* %b, i8 %c) +; ATTRIBUTOR: define void @f18(i8* nonnull %a, i8* %b, i8 %c) %cmp1 = icmp eq i8 %c, 0 br i1 %cmp1, label %if.then, label %if.else if.then: