diff options
| -rw-r--r-- | llvm/include/llvm/Analysis/MustExecute.h | 31 | ||||
| -rw-r--r-- | llvm/lib/Analysis/MustExecute.cpp | 188 | ||||
| -rw-r--r-- | llvm/test/Analysis/MustExecute/must_be_executed_context.ll | 121 | ||||
| -rw-r--r-- | llvm/test/Transforms/FunctionAttrs/nonnull.ll | 232 |
4 files changed, 556 insertions, 16 deletions
diff --git a/llvm/include/llvm/Analysis/MustExecute.h b/llvm/include/llvm/Analysis/MustExecute.h index 045171b706f..d88cdf40ed8 100644 --- a/llvm/include/llvm/Analysis/MustExecute.h +++ b/llvm/include/llvm/Analysis/MustExecute.h @@ -33,8 +33,13 @@ namespace llvm { +namespace { +template <typename T> using GetterTy = std::function<T *(const Function &F)>; +} + class Instruction; class DominatorTree; +class PostDominatorTree; class Loop; /// Captures loop safety information. @@ -374,8 +379,14 @@ struct MustBeExecutedContextExplorer { /// \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, + GetterTy<const LoopInfo> LIGetter = + [](const Function &) { return nullptr; }, + GetterTy<const PostDominatorTree> PDTGetter = + [](const Function &) { return nullptr; }) + : ExploreInterBlock(ExploreInterBlock), LIGetter(LIGetter), + PDTGetter(PDTGetter), EndIterator(*this, nullptr) {} /// Clean up the dynamically allocated iterators. ~MustBeExecutedContextExplorer() { @@ -454,6 +465,9 @@ struct MustBeExecutedContextExplorer { 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. ///{ @@ -461,6 +475,19 @@ struct MustBeExecutedContextExplorer { ///} private: + /// Getters for common CFG analyses: LoopInfo, DominatorTree, and + /// PostDominatorTree. + ///{ + GetterTy<const LoopInfo> LIGetter; + GetterTy<const PostDominatorTree> PDTGetter; + ///} + + /// Map to cache isGuaranteedToTransferExecutionToSuccessor results. + DenseMap<const BasicBlock *, Optional<bool>> BlockTransferMap; + + /// Map to cache containsIrreducibleCFG results. + DenseMap<const Function*, Optional<bool>> IrreducibleControlMap; + /// Map from instructions to associated must be executed iterators. DenseMap<const Instruction *, MustBeExecutedIterator *> InstructionIteratorMap; diff --git a/llvm/lib/Analysis/MustExecute.cpp b/llvm/lib/Analysis/MustExecute.cpp index 44527773115..a796cc79ad8 100644 --- a/llvm/lib/Analysis/MustExecute.cpp +++ b/llvm/lib/Analysis/MustExecute.cpp @@ -13,6 +13,7 @@ #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/Passes.h" #include "llvm/Analysis/ValueTracking.h" +#include "llvm/Analysis/PostDominators.h" #include "llvm/IR/AssemblyAnnotationWriter.h" #include "llvm/IR/DataLayout.h" #include "llvm/IR/InstIterator.h" @@ -353,7 +354,19 @@ ModulePass *llvm::createMustBeExecutedContextPrinter() { } bool MustBeExecutedContextPrinter::runOnModule(Module &M) { - MustBeExecutedContextExplorer Explorer(true); + // We provide non-PM analysis here because the old PM doesn't like to query + // function passes from a module pass. Given that this is a printer, we don't + // care much about memory leaks. + GetterTy<LoopInfo> LIGetter = [this](const Function &F) { + DominatorTree *DT = new DominatorTree(const_cast<Function &>(F)); + LoopInfo *LI = new LoopInfo(*DT); + return LI; + }; + GetterTy<PostDominatorTree> PDTGetter = [this](const Function &F) { + PostDominatorTree *PDT = new PostDominatorTree(const_cast<Function &>(F)); + return PDT; + }; + MustBeExecutedContextExplorer Explorer(true, LIGetter, PDTGetter); for (Function &F : M) { for (Instruction &I : instructions(F)) { dbgs() << "-- Explore context of: " << I << "\n"; @@ -443,6 +456,173 @@ bool MustExecutePrinter::runOnFunction(Function &F) { 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<const Function *>; + RPOTraversal FuncRPOT(&F); + return !containsIrreducibleCFG<const BasicBlock *, const RPOTraversal, + const LoopInfo>(FuncRPOT, *LI); +} + +/// Lookup \p Key in \p Map and return the result, potentially after +/// initializing the optional through \p Fn(\p args). +template <typename K, typename V, typename FnTy, typename... ArgsTy> +static V getOrCreateCachedOptional(K Key, DenseMap<K, Optional<V>> &Map, + FnTy &&Fn, ArgsTy&&... args) { + Optional<V> &OptVal = Map[Key]; + if (!OptVal.hasValue()) + OptVal = Fn(std::forward<ArgsTy>(args)...); + return OptVal.getValue(); +} + +const BasicBlock * +MustBeExecutedContextExplorer::findForwardJoinPoint(const BasicBlock *InitBB) { + const LoopInfo *LI = LIGetter(*InitBB->getParent()); + const PostDominatorTree *PDT = PDTGetter(*InitBB->getParent()); + + 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<const BasicBlock *, 8> 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 and one block loops 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 (Succ0UniqueSucc == InitBB) { + // InitBB -> Succ0 -> InitBB + // InitBB -> Succ1 = JoinBB + JoinBB = Succ1; + } else if (Succ1UniqueSucc == InitBB) { + // InitBB -> Succ1 -> InitBB + // InitBB -> Succ0 = JoinBB + JoinBB = Succ0; + } else 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<const BasicBlock *, 16> 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)) { + if (!LI) + return nullptr; + + 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) { @@ -490,6 +670,12 @@ MustBeExecutedContextExplorer::getMustBeExecutedNextInstruction( 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 index da1aa7280b0..fd650872dd9 100644 --- a/llvm/test/Analysis/MustExecute/must_be_executed_context.ll +++ b/llvm/test/Analysis/MustExecute/must_be_executed_context.ll @@ -1,5 +1,6 @@ -; RUN: opt -print-mustexecute -analyze 2>&1 < %s | FileCheck %s --check-prefix=ME -; RUN: opt -print-must-be-executed-contexts -analyze 2>&1 < %s | FileCheck %s --check-prefix=MBEC +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py +; RUN: opt < %s -print-mustexecute -analyze 2>&1 | FileCheck %s --check-prefix=ME +; RUN: opt < %s -print-must-be-executed-contexts -analyze 2>&1 | FileCheck %s --check-prefix=MBEC ; ; void simple_conditional(int c) { ; A(); @@ -36,6 +37,8 @@ bb: ; 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 +46,8 @@ bb: ; 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 @@ -280,3 +285,115 @@ declare void @E() nounwind willreturn declare void @F() nounwind declare void @G() nounwind willreturn + +declare i32 @g(i32*) nounwind willreturn + +declare void @h(i32*) nounwind willreturn + +define i32 @nonnull_exec_ctx_1(i32* %a, i32 %b) { +; MBEC: -- Explore context of: %tmp3 = icmp eq i32 %b, 0 +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp3 = icmp eq i32 %b, 0 +; MBEC-NEXT: [F: nonnull_exec_ctx_1] br i1 %tmp3, label %ex, label %hd +; MBEC-NEXT: -- Explore context of: br i1 %tmp3, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_1] br i1 %tmp3, label %ex, label %hd +; MBEC-NEXT: -- Explore context of: %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_1] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: ret i32 %tmp5 +; MBEC-NEXT: [F: nonnull_exec_ctx_1] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ] +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ] +; MBEC-NEXT: [F: nonnull_exec_ctx_1] tail call void @h(i32* %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp8 = add nuw i32 %tmp7, 1 +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_1] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: -- Explore context of: tail call void @h(i32* %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_1] tail call void @h(i32* %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp8 = add nuw i32 %tmp7, 1 +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_1] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: -- Explore context of: %tmp8 = add nuw i32 %tmp7, 1 +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp8 = add nuw i32 %tmp7, 1 +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_1] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: -- Explore context of: %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_1] %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_1] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: -- Explore context of: br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_1] br i1 %tmp9, label %ex, label %hd +en: + %tmp3 = icmp eq i32 %b, 0 + br i1 %tmp3, label %ex, label %hd + +ex: + %tmp5 = tail call i32 @g(i32* nonnull %a) + ret i32 %tmp5 + +hd: + %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ] + tail call void @h(i32* %a) + %tmp8 = add nuw i32 %tmp7, 1 + %tmp9 = icmp eq i32 %tmp8, %b + br i1 %tmp9, label %ex, label %hd +} + +define i32 @nonnull_exec_ctx_2(i32* %a, i32 %b) nounwind willreturn { +; MBEC: -- Explore context of: %tmp3 = icmp eq i32 %b, 0 +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp3 = icmp eq i32 %b, 0 +; MBEC-NEXT: [F: nonnull_exec_ctx_2] br i1 %tmp3, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: br i1 %tmp3, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] br i1 %tmp3, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: ret i32 %tmp5 +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ] +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ] +; MBEC-NEXT: [F: nonnull_exec_ctx_2] tail call void @h(i32* %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp8 = add nuw i32 %tmp7, 1 +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_2] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: tail call void @h(i32* %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] tail call void @h(i32* %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp8 = add nuw i32 %tmp7, 1 +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_2] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: %tmp8 = add nuw i32 %tmp7, 1 +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp8 = add nuw i32 %tmp7, 1 +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_2] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp9 = icmp eq i32 %tmp8, %b +; MBEC-NEXT: [F: nonnull_exec_ctx_2] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +; MBEC-NEXT: -- Explore context of: br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] br i1 %tmp9, label %ex, label %hd +; MBEC-NEXT: [F: nonnull_exec_ctx_2] %tmp5 = tail call i32 @g(i32* nonnull %a) +; MBEC-NEXT: [F: nonnull_exec_ctx_2] ret i32 %tmp5 +en: + %tmp3 = icmp eq i32 %b, 0 + br i1 %tmp3, label %ex, label %hd + +ex: + %tmp5 = tail call i32 @g(i32* nonnull %a) + ret i32 %tmp5 + +hd: + %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ] + tail call void @h(i32* %a) + %tmp8 = add nuw i32 %tmp7, 1 + %tmp9 = icmp eq i32 %tmp8, %b + br i1 %tmp9, label %ex, label %hd +} diff --git a/llvm/test/Transforms/FunctionAttrs/nonnull.ll b/llvm/test/Transforms/FunctionAttrs/nonnull.ll index 9a7eb114eae..657ef7152eb 100644 --- a/llvm/test/Transforms/FunctionAttrs/nonnull.ll +++ b/llvm/test/Transforms/FunctionAttrs/nonnull.ll @@ -1,3 +1,4 @@ +; NOTE: Assertions have been autogenerated by utils/update_test_checks.py ; RUN: opt -S -functionattrs -enable-nonnull-arg-prop %s | FileCheck %s --check-prefixes=BOTH,FNATTR ; RUN: opt -S -passes=function-attrs -enable-nonnull-arg-prop %s | FileCheck %s --check-prefixes=BOTH,FNATTR ; RUN: opt -attributor --attributor-disable=false -attributor-max-iterations-verify -attributor-max-iterations=8 -S < %s | FileCheck %s --check-prefixes=BOTH,ATTRIBUTOR @@ -159,7 +160,7 @@ define void @test13_helper() { ret void } define internal void @test13(i8* %a, i8* %b, i8* %c) { -; ATTRIBUTOR: define internal void @test13(i8* nocapture nonnull readnone %a, i8* nocapture readnone %b, i8* nocapture readnone %c) +; ATTRIBUTOR: define internal void @test13(i8* nocapture nonnull readnone %a, i8* nocapture readnone %b, i8* nocapture readnone %c) ret void } @@ -172,7 +173,7 @@ declare nonnull i8* @nonnull() ; * Argument ; 1. In f1:bb6, %arg can be marked with nonnull because of the comparison in bb1 ; 2. Because f2 is internal function, f2(i32* %arg) -> @f2(i32* nonnull %arg) -; 3. In f1:bb4 %tmp5 is nonnull and f3 is internal function. +; 3. In f1:bb4 %tmp5 is nonnull and f3 is internal function. ; Then, f3(i32* %arg) -> @f3(i32* nonnull %arg) ; 4. We get nonnull in whole f1 call sites so f1(i32* %arg) -> @f1(i32* nonnull %arg) @@ -208,21 +209,21 @@ bb9: ; preds = %bb4, %bb } define internal i32* @f2(i32* %arg) { -; FIXME: missing nonnull. It should be nonnull @f2(i32* nonnull %arg) +; FIXME: missing nonnull. It should be nonnull @f2(i32* nonnull %arg) ; ATTRIBUTOR: define internal nonnull i32* @f2(i32* readonly %arg) bb: -; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg) +; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg) ; ATTRIBUTOR: %tmp = tail call nonnull i32* @f1(i32* readonly %arg) %tmp = tail call i32* @f1(i32* %arg) ret i32* %tmp } define dso_local noalias i32* @f3(i32* %arg) { -; FIXME: missing nonnull. It should be nonnull @f3(i32* nonnull readonly %arg) +; FIXME: missing nonnull. It should be nonnull @f3(i32* nonnull readonly %arg) ; ATTRIBUTOR: define dso_local noalias i32* @f3(i32* nocapture readonly %arg) bb: -; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg) +; FIXME: missing nonnull. It should be @f1(i32* nonnull readonly %arg) ; ATTRIBUTOR: %tmp = call i32* @f1(i32* readonly %arg) %tmp = call i32* @f1(i32* %arg) ret i32* null @@ -266,8 +267,7 @@ if.else: ; 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: @@ -292,8 +292,7 @@ cont: ; 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: @@ -477,7 +476,7 @@ define i8 @parent7(i8* %a) { declare i32 @esfp(...) define i1 @parent8(i8* %a, i8* %bogus1, i8* %b) personality i8* bitcast (i32 (...)* @esfp to i8*){ -; BOTH-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b) +; BOTH-LABEL: @parent8(i8* nonnull %a, i8* nocapture readnone %bogus1, i8* nonnull %b) ; BOTH-NEXT: entry: ; FNATTR-NEXT: invoke void @use2nonnull(i8* %a, i8* %b) ; ATTRIBUTOR-NEXT: invoke void @use2nonnull(i8* nonnull %a, i8* nonnull %b) @@ -579,5 +578,216 @@ define void @make_live(i32* nonnull dereferenceable(8) %a) { ret void } + +;int f(int *u, int n){ +; for(int i = 0;i<n;i++){ +; h(u); +; } +; return g(nonnull u); +;} +declare void @h(i32*) willreturn nounwind +declare i32 @g(i32*) willreturn nounwind +define i32 @nonnull_exec_ctx_1(i32* %a, i32 %b) { +; FNATTR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_1 +; FNATTR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #3 +; FNATTR-NEXT: en: +; FNATTR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0 +; FNATTR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] +; FNATTR: ex: +; FNATTR-NEXT: [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]]) +; FNATTR-NEXT: ret i32 [[TMP5]] +; FNATTR: hd: +; FNATTR-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ] +; FNATTR-NEXT: tail call void @h(i32* [[A]]) +; FNATTR-NEXT: [[TMP8]] = add nuw i32 [[TMP7]], 1 +; FNATTR-NEXT: [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]] +; FNATTR-NEXT: br i1 [[TMP9]], label [[EX]], label [[HD]] +; +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_1 +; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #5 +; ATTRIBUTOR-NEXT: en: +; ATTRIBUTOR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0 +; ATTRIBUTOR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] +; ATTRIBUTOR: ex: +; ATTRIBUTOR-NEXT: [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]]) +; ATTRIBUTOR-NEXT: ret i32 [[TMP5]] +; ATTRIBUTOR: hd: +; ATTRIBUTOR-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ] +; ATTRIBUTOR-NEXT: tail call void @h(i32* [[A]]) +; ATTRIBUTOR-NEXT: [[TMP8]] = add nuw i32 [[TMP7]], 1 +; ATTRIBUTOR-NEXT: [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]] +; ATTRIBUTOR-NEXT: br i1 [[TMP9]], label [[EX]], label [[HD]] +; +en: + %tmp3 = icmp eq i32 %b, 0 + br i1 %tmp3, label %ex, label %hd + +ex: + %tmp5 = tail call i32 @g(i32* nonnull %a) + ret i32 %tmp5 + +hd: + %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ] + tail call void @h(i32* %a) + %tmp8 = add nuw i32 %tmp7, 1 + %tmp9 = icmp eq i32 %tmp8, %b + br i1 %tmp9, label %ex, label %hd +} + +define i32 @nonnull_exec_ctx_1b(i32* %a, i32 %b) { +; FNATTR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_1b +; FNATTR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #3 +; FNATTR-NEXT: en: +; FNATTR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0 +; FNATTR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] +; FNATTR: ex: +; FNATTR-NEXT: [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]]) +; FNATTR-NEXT: ret i32 [[TMP5]] +; FNATTR: hd: +; FNATTR-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ] +; FNATTR-NEXT: tail call void @h(i32* [[A]]) +; FNATTR-NEXT: br label [[HD2]] +; FNATTR: hd2: +; FNATTR-NEXT: [[TMP8]] = add nuw i32 [[TMP7]], 1 +; FNATTR-NEXT: [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]] +; FNATTR-NEXT: br i1 [[TMP9]], label [[EX]], label [[HD]] +; +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_1b +; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #5 +; ATTRIBUTOR-NEXT: en: +; ATTRIBUTOR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0 +; ATTRIBUTOR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] +; ATTRIBUTOR: ex: +; ATTRIBUTOR-NEXT: [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]]) +; ATTRIBUTOR-NEXT: ret i32 [[TMP5]] +; ATTRIBUTOR: hd: +; ATTRIBUTOR-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ] +; ATTRIBUTOR-NEXT: tail call void @h(i32* [[A]]) +; ATTRIBUTOR-NEXT: br label [[HD2]] +; ATTRIBUTOR: hd2: +; ATTRIBUTOR-NEXT: [[TMP8]] = add nuw i32 [[TMP7]], 1 +; ATTRIBUTOR-NEXT: [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]] +; ATTRIBUTOR-NEXT: br i1 [[TMP9]], label [[EX]], label [[HD]] +; +en: + %tmp3 = icmp eq i32 %b, 0 + br i1 %tmp3, label %ex, label %hd + +ex: + %tmp5 = tail call i32 @g(i32* nonnull %a) + ret i32 %tmp5 + +hd: + %tmp7 = phi i32 [ %tmp8, %hd2 ], [ 0, %en ] + tail call void @h(i32* %a) + br label %hd2 + +hd2: + %tmp8 = add nuw i32 %tmp7, 1 + %tmp9 = icmp eq i32 %tmp8, %b + br i1 %tmp9, label %ex, label %hd +} + +define i32 @nonnull_exec_ctx_2(i32* %a, i32 %b) willreturn nounwind { +; FNATTR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2 +; FNATTR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #2 +; FNATTR-NEXT: en: +; FNATTR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0 +; FNATTR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] +; FNATTR: ex: +; FNATTR-NEXT: [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]]) +; FNATTR-NEXT: ret i32 [[TMP5]] +; FNATTR: hd: +; FNATTR-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ] +; FNATTR-NEXT: tail call void @h(i32* [[A]]) +; FNATTR-NEXT: [[TMP8]] = add nuw i32 [[TMP7]], 1 +; FNATTR-NEXT: [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]] +; FNATTR-NEXT: br i1 [[TMP9]], label [[EX]], label [[HD]] +; +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2 +; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #3 +; ATTRIBUTOR-NEXT: en: +; ATTRIBUTOR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0 +; ATTRIBUTOR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] +; ATTRIBUTOR: ex: +; ATTRIBUTOR-NEXT: [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]]) +; ATTRIBUTOR-NEXT: ret i32 [[TMP5]] +; ATTRIBUTOR: hd: +; ATTRIBUTOR-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD]] ], [ 0, [[EN:%.*]] ] +; ATTRIBUTOR-NEXT: tail call void @h(i32* nonnull [[A]]) +; ATTRIBUTOR-NEXT: [[TMP8]] = add nuw i32 [[TMP7]], 1 +; ATTRIBUTOR-NEXT: [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]] +; ATTRIBUTOR-NEXT: br i1 [[TMP9]], label [[EX]], label [[HD]] +; +en: + %tmp3 = icmp eq i32 %b, 0 + br i1 %tmp3, label %ex, label %hd + +ex: + %tmp5 = tail call i32 @g(i32* nonnull %a) + ret i32 %tmp5 + +hd: + %tmp7 = phi i32 [ %tmp8, %hd ], [ 0, %en ] + tail call void @h(i32* %a) + %tmp8 = add nuw i32 %tmp7, 1 + %tmp9 = icmp eq i32 %tmp8, %b + br i1 %tmp9, label %ex, label %hd +} + +define i32 @nonnull_exec_ctx_2b(i32* %a, i32 %b) willreturn nounwind { +; FNATTR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2b +; FNATTR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #2 +; FNATTR-NEXT: en: +; FNATTR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0 +; FNATTR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] +; FNATTR: ex: +; FNATTR-NEXT: [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]]) +; FNATTR-NEXT: ret i32 [[TMP5]] +; FNATTR: hd: +; FNATTR-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ] +; FNATTR-NEXT: tail call void @h(i32* [[A]]) +; FNATTR-NEXT: br label [[HD2]] +; FNATTR: hd2: +; FNATTR-NEXT: [[TMP8]] = add nuw i32 [[TMP7]], 1 +; FNATTR-NEXT: [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]] +; FNATTR-NEXT: br i1 [[TMP9]], label [[EX]], label [[HD]] +; +; ATTRIBUTOR-LABEL: define {{[^@]+}}@nonnull_exec_ctx_2b +; ATTRIBUTOR-SAME: (i32* [[A:%.*]], i32 [[B:%.*]]) #3 +; ATTRIBUTOR-NEXT: en: +; ATTRIBUTOR-NEXT: [[TMP3:%.*]] = icmp eq i32 [[B:%.*]], 0 +; ATTRIBUTOR-NEXT: br i1 [[TMP3]], label [[EX:%.*]], label [[HD:%.*]] +; ATTRIBUTOR: ex: +; ATTRIBUTOR-NEXT: [[TMP5:%.*]] = tail call i32 @g(i32* nonnull [[A:%.*]]) +; ATTRIBUTOR-NEXT: ret i32 [[TMP5]] +; ATTRIBUTOR: hd: +; ATTRIBUTOR-NEXT: [[TMP7:%.*]] = phi i32 [ [[TMP8:%.*]], [[HD2:%.*]] ], [ 0, [[EN:%.*]] ] +; ATTRIBUTOR-NEXT: tail call void @h(i32* nonnull [[A]]) +; ATTRIBUTOR-NEXT: br label [[HD2]] +; ATTRIBUTOR: hd2: +; ATTRIBUTOR-NEXT: [[TMP8]] = add nuw i32 [[TMP7]], 1 +; ATTRIBUTOR-NEXT: [[TMP9:%.*]] = icmp eq i32 [[TMP8]], [[B]] +; ATTRIBUTOR-NEXT: br i1 [[TMP9]], label [[EX]], label [[HD]] +; +en: + %tmp3 = icmp eq i32 %b, 0 + br i1 %tmp3, label %ex, label %hd + +ex: + %tmp5 = tail call i32 @g(i32* nonnull %a) + ret i32 %tmp5 + +hd: + %tmp7 = phi i32 [ %tmp8, %hd2 ], [ 0, %en ] + tail call void @h(i32* %a) + br label %hd2 + +hd2: + %tmp8 = add nuw i32 %tmp7, 1 + %tmp9 = icmp eq i32 %tmp8, %b + br i1 %tmp9, label %ex, label %hd +} + attributes #0 = { "null-pointer-is-valid"="true" } attributes #1 = { nounwind willreturn} |
