diff --git a/llvm/include/llvm/Analysis/CFG.h b/llvm/include/llvm/Analysis/CFG.h --- a/llvm/include/llvm/Analysis/CFG.h +++ b/llvm/include/llvm/Analysis/CFG.h @@ -47,8 +47,8 @@ bool isCriticalEdge(const Instruction *TI, unsigned SuccNum, bool AllowIdenticalEdges = false); -/// Determine whether instruction 'To' is reachable from 'From', -/// returning true if uncertain. +/// Determine whether instruction 'To' is reachable from 'From', without passing +/// through any blocks in ExclusionSet, returning true if uncertain. /// /// Determine whether there is a path from From to To within a single function. /// Returns false only if we can prove that once 'From' has been executed then @@ -62,9 +62,10 @@ /// we find a block that dominates the block containing 'To'. DT is most useful /// on branchy code but not loops, and LI is most useful on code with loops but /// does not help on branchy code outside loops. -bool isPotentiallyReachable(const Instruction *From, const Instruction *To, - const DominatorTree *DT = nullptr, - const LoopInfo *LI = nullptr); +bool isPotentiallyReachable( + const Instruction *From, const Instruction *To, + const SmallPtrSetImpl *ExclusionSet = nullptr, + const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); /// Determine whether block 'To' is reachable from 'From', returning /// true if uncertain. @@ -88,6 +89,20 @@ const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); +/// Determine whether there is at least one path from a block in +/// 'Worklist' to 'StopBB' without passing through any blocks in +/// 'ExclusionSet', returning true if uncertain. +/// +/// Determine whether there is a path from at least one block in Worklist to +/// StopBB within a single function without passing through any of the blocks +/// in 'ExclusionSet'. Returns false only if we can prove that once any block +/// in 'Worklist' has been reached then 'StopBB' can not be executed. +/// Conservatively returns true. +bool isPotentiallyReachableFromMany( + SmallVectorImpl &Worklist, BasicBlock *StopBB, + const SmallPtrSetImpl *ExclusionSet, + const DominatorTree *DT = nullptr, const LoopInfo *LI = nullptr); + /// Return true if the control flow in \p RPOTraversal is irreducible. /// /// This is a generic implementation to detect CFG irreducibility based on loop diff --git a/llvm/include/llvm/Analysis/LoopAllocationInfo.h b/llvm/include/llvm/Analysis/LoopAllocationInfo.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/Analysis/LoopAllocationInfo.h @@ -0,0 +1,102 @@ +//===- LoopAllocationInfo.h - memory allocations inside loops ---*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_ANALYSIS_LOOPALLOCATIONINFO_H +#define LLVM_ANALYSIS_LOOPALLOCATIONINFO_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/SmallVector.h" + +namespace llvm { + +class BasicBlock; +class CallInst; +class DominatorTree; +class Loop; +class LoopInfo; +class TargetLibraryInfo; + +/// Track ptr = allocfn to one or more freefn(ptr) relationships within the +/// loop. +/// +/// This analysis stores information about allocation and deallocation calls +/// where the pointer is only live within the loop. +/// +/// An allocation must be both hoisted and sunk, or neither. LICM performs +/// sinking first, then hoisting. As sinking and hoisting is performed, more +/// instructions will appear to be loop invariant, making more opportunities. +/// For this reason we split the analysis into two pieces: +/// 1. for a given pointer that is only live in the loop, retain a list its +/// matching deallocating instructions. +/// 2. during sinking, if we would sink the deallocation, don't, but inform +/// the LoopAllocationInfo. If all deallocations would have been sunk, and +/// hoistSink would hoist the allocation, perform both the hoist and sink +/// the various deallocation instructions. +/// +/// We don't need guaranteed execution of any deallocation function during +/// unwinding. Before this transformation, an unwind mid-loop would leak one +/// pointer that was allocated at the start of the loop. After this +/// transformation, it would leak the one pointer allocated before the loop +/// began. There is no difference visible to the caller. +/// +/// We do have to ensure that the maximum amount of allocated memory is not +/// raised by this transformation. To ensure this, we stop looking for +/// allocations after seeing an opaque function call. For example: +/// loop_top: +/// %ptr1 = call i8* @malloc(i32 %loop_invariant1) ;; candidate +/// %ptr2 = call i8* @malloc(i32 %loop_variant2) ;; not candidate +/// %ptr3 = call i8* @malloc(i32 %loop_invariant3) ;; candidate +/// call void @opaque() ;; stop scanning +/// %ptr5 = call i8* @malloc(i32 %loop_invariant5) ;; not candidate +/// +/// The same idea applies in reverse order to @free calls at the loop exits: +/// loop_exiting: +/// call void @free(%ptr1) ;; not candidate +/// call void @opaque() ;; stop scanning +/// call void @free(%ptr2) ;; %ptr2 is candidate +/// ;; start here and scan upwards +class LoopAllocationInfo { +public: + void analyzeLoop(LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, + Loop *CurLoop); + + // sinkRegion has determined that this deallocation call may be sunk. + void addSafeToSink(const CallInst *CI); + + // hoistRegion would like to know whether the given allocation call may be + // hoisted. + bool mayHoist(const CallInst *CI) const; + + // Retrieve the list of free calls that should be removed from the loop. + const SmallVector &toSink(const CallInst *CI); + + // Retrieve the list of loop exit blocks which must have a free inserted. + // This is a subset or equal to the loops exit blocks. + const SmallVector &addDeallocations(const CallInst *CI); + + // Returns whether the loop has any potentially-hoistable allocations. + bool empty() const { return Allocations.empty(); } + +private: + // The n-th index into these vectors finds the matching allocation and + // deallocations. + SmallVector Allocations; + SmallVector, 4> Deallocations; + SmallVector, 4> ExitBlocksToAddDeallocationsTo; + + // Look up the index into the above vector given a call. + DenseMap AllocationLookup; + DenseMap DeallocationLookup; + + DenseSet SafeToSink; +}; + +} // namespace llvm + +#endif diff --git a/llvm/include/llvm/IR/Instruction.h b/llvm/include/llvm/IR/Instruction.h --- a/llvm/include/llvm/IR/Instruction.h +++ b/llvm/include/llvm/IR/Instruction.h @@ -536,6 +536,12 @@ return mayReadFromMemory() || mayWriteToMemory(); } + /// Return true if this instruction may allocate heap memory. + bool mayAllocateMemory() const; + + /// Return true if this instruction may deallocate heap memory. + bool mayDeallocateMemory() const; + /// Return true if this instruction has an AtomicOrdering of unordered or /// higher. bool isAtomic() const; diff --git a/llvm/include/llvm/Transforms/Utils/LoopUtils.h b/llvm/include/llvm/Transforms/Utils/LoopUtils.h --- a/llvm/include/llvm/Transforms/Utils/LoopUtils.h +++ b/llvm/include/llvm/Transforms/Utils/LoopUtils.h @@ -39,6 +39,7 @@ class BasicBlock; class DataLayout; class Loop; +class LoopAllocationInfo; class LoopInfo; class MemoryAccess; class MemorySSAUpdater; @@ -112,7 +113,7 @@ bool sinkRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, TargetTransformInfo *, Loop *, AliasSetTracker *, MemorySSAUpdater *, ICFLoopSafetyInfo *, - bool, int &, OptimizationRemarkEmitter *); + LoopAllocationInfo *, bool, int &, OptimizationRemarkEmitter *); /// Walk the specified region of the CFG (defined by all blocks /// dominated by the specified block, and that are in the current loop) in depth @@ -124,8 +125,8 @@ /// ORE. It returns changed status. bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *, TargetLibraryInfo *, Loop *, AliasSetTracker *, - MemorySSAUpdater *, ICFLoopSafetyInfo *, bool, int &, - OptimizationRemarkEmitter *); + MemorySSAUpdater *, ICFLoopSafetyInfo *, LoopAllocationInfo *, + bool, int &, OptimizationRemarkEmitter *); /// This function deletes dead loops. The caller of this function needs to /// guarantee that the loop is infact dead. diff --git a/llvm/lib/Analysis/BasicAliasAnalysis.cpp b/llvm/lib/Analysis/BasicAliasAnalysis.cpp --- a/llvm/lib/Analysis/BasicAliasAnalysis.cpp +++ b/llvm/lib/Analysis/BasicAliasAnalysis.cpp @@ -1906,7 +1906,7 @@ // the Values cannot come from different iterations of a potential cycle the // phi nodes could be involved in. for (auto *P : VisitedPhiBBs) - if (isPotentiallyReachable(&P->front(), Inst, DT, LI)) + if (isPotentiallyReachable(&P->front(), Inst, nullptr, DT, LI)) return false; return true; diff --git a/llvm/lib/Analysis/CFG.cpp b/llvm/lib/Analysis/CFG.cpp --- a/llvm/lib/Analysis/CFG.cpp +++ b/llvm/lib/Analysis/CFG.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CFG.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallSet.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/IR/Dominators.h" @@ -119,22 +120,33 @@ return L; } -// True if there is a loop which contains both BB1 and BB2. -static bool loopContainsBoth(const LoopInfo *LI, - const BasicBlock *BB1, const BasicBlock *BB2) { - const Loop *L1 = getOutermostLoop(LI, BB1); - const Loop *L2 = getOutermostLoop(LI, BB2); - return L1 != nullptr && L1 == L2; -} - bool llvm::isPotentiallyReachableFromMany( SmallVectorImpl &Worklist, BasicBlock *StopBB, - const DominatorTree *DT, const LoopInfo *LI) { + const SmallPtrSetImpl *ExclusionSet, const DominatorTree *DT, + const LoopInfo *LI) { // When the stop block is unreachable, it's dominated from everywhere, // regardless of whether there's a path between the two blocks. if (DT && !DT->isReachableFromEntry(StopBB)) DT = nullptr; + // We can't skip directly from a block that dominates the stop block if the + // exclusion block is potentially in between. + if (ExclusionSet && !ExclusionSet->empty()) + DT = nullptr; + + // Normally any block in a loop is reachable from any other block in a loop, + // however excluded blocks might partition the body of a loop to make that + // untrue. + SmallPtrSet LoopsWithHoles; + if (LI && ExclusionSet) { + for (auto BB : *ExclusionSet) { + if (const Loop *L = getOutermostLoop(LI, BB)) + LoopsWithHoles.insert(L); + } + } + + const Loop *StopLoop = LI ? getOutermostLoop(LI, StopBB) : nullptr; + // Limit the number of blocks we visit. The goal is to avoid run-away compile // times on large CFGs without hampering sensible code. Arbitrarily chosen. unsigned Limit = 32; @@ -145,10 +157,19 @@ continue; if (BB == StopBB) return true; + if (ExclusionSet && ExclusionSet->count(BB)) + continue; if (DT && DT->dominates(BB, StopBB)) return true; - if (LI && loopContainsBoth(LI, BB, StopBB)) - return true; + + const Loop *Outer = nullptr; + if (LI) { + Outer = getOutermostLoop(LI, BB); + if (LoopsWithHoles.count(Outer)) + Outer = nullptr; + if (StopLoop && Outer == StopLoop) + return true; + } if (!--Limit) { // We haven't been able to prove it one way or the other. Conservatively @@ -156,7 +177,7 @@ return true; } - if (const Loop *Outer = LI ? getOutermostLoop(LI, BB) : nullptr) { + if (Outer) { // All blocks in a single loop are reachable from all other blocks. From // any of these blocks, we can skip directly to the exits of the loop, // ignoring any other blocks inside the loop body. @@ -180,11 +201,13 @@ Worklist.push_back(const_cast(A)); return isPotentiallyReachableFromMany(Worklist, const_cast(B), - DT, LI); + nullptr, DT, LI); } -bool llvm::isPotentiallyReachable(const Instruction *A, const Instruction *B, - const DominatorTree *DT, const LoopInfo *LI) { +bool llvm::isPotentiallyReachable( + const Instruction *A, const Instruction *B, + const SmallPtrSetImpl *ExclusionSet, const DominatorTree *DT, + const LoopInfo *LI) { assert(A->getParent()->getParent() == B->getParent()->getParent() && "This analysis is function-local!"); @@ -226,11 +249,20 @@ Worklist.push_back(const_cast(A->getParent())); } - if (A->getParent() == &A->getParent()->getParent()->getEntryBlock()) - return true; - if (B->getParent() == &A->getParent()->getParent()->getEntryBlock()) - return false; + if (DT) { + if (DT->isReachableFromEntry(A->getParent()) != + DT->isReachableFromEntry(B->getParent())) + return false; + if (!ExclusionSet || ExclusionSet->empty()) { + if (A->getParent() == &A->getParent()->getParent()->getEntryBlock() && + DT->isReachableFromEntry(B->getParent())) + return true; + if (B->getParent() == &A->getParent()->getParent()->getEntryBlock() && + DT->isReachableFromEntry(A->getParent())) + return false; + } + } return isPotentiallyReachableFromMany( - Worklist, const_cast(B->getParent()), DT, LI); + Worklist, const_cast(B->getParent()), ExclusionSet, DT, LI); } diff --git a/llvm/lib/Analysis/CMakeLists.txt b/llvm/lib/Analysis/CMakeLists.txt --- a/llvm/lib/Analysis/CMakeLists.txt +++ b/llvm/lib/Analysis/CMakeLists.txt @@ -50,6 +50,7 @@ Lint.cpp Loads.cpp LoopAccessAnalysis.cpp + LoopAllocationInfo.cpp LoopAnalysisManager.cpp LoopUnrollAnalyzer.cpp LoopInfo.cpp diff --git a/llvm/lib/Analysis/CaptureTracking.cpp b/llvm/lib/Analysis/CaptureTracking.cpp --- a/llvm/lib/Analysis/CaptureTracking.cpp +++ b/llvm/lib/Analysis/CaptureTracking.cpp @@ -101,14 +101,14 @@ SmallVector Worklist; Worklist.append(succ_begin(BB), succ_end(BB)); - return !isPotentiallyReachableFromMany(Worklist, BB, DT); + return !isPotentiallyReachableFromMany(Worklist, BB, nullptr, DT); } // If the value is defined in the same basic block as use and BeforeHere, // there is no need to explore the use if BeforeHere dominates use. // Check whether there is a path from I to BeforeHere. if (BeforeHere != I && DT->dominates(BeforeHere, I) && - !isPotentiallyReachable(I, BeforeHere, DT)) + !isPotentiallyReachable(I, BeforeHere, nullptr, DT)) return true; return false; diff --git a/llvm/lib/Analysis/LoopAllocationInfo.cpp b/llvm/lib/Analysis/LoopAllocationInfo.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/Analysis/LoopAllocationInfo.cpp @@ -0,0 +1,235 @@ +//===- LoopAllocationInfo.cpp - memory allocations inside loops -----------===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "llvm/Analysis/LoopAllocationInfo.h" + +#include "llvm/ADT/BitVector.h" +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/DenseSet.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/Analysis/CFG.h" +#include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/MemoryBuiltins.h" +#include "llvm/IR/BasicBlock.h" +#include "llvm/IR/CFG.h" +#include "llvm/IR/Dominators.h" +#include "llvm/IR/Instruction.h" +#include "llvm/IR/Instructions.h" +#include "llvm/Support/Casting.h" + +namespace llvm { + +/// Track ptr = allocfn to one or more freefn(ptr) relationships within the +/// loop. +/// +/// This analysis stores information about allocation and deallocation calls +/// where the pointer is only live within the loop. +/// +/// An allocation must be both hoisted and sunk, or neither. LICM performs +/// sinking first, then hoisting. As sinking and hoisting is performed, more +/// instructions will appear to be loop invariant, making more opportunities. +/// For this reason we split the analysis into two pieces: +/// 1. for a given pointer that is only live in the loop, retain a list its +/// matching deallocating instructions. +/// 2. during sinking, if we would sink the deallocation, don't, but inform +/// the LoopAllocationInfo. If all deallocations would have been sunk, and +/// hoistSink would hoist the allocation, perform both the hoist and sink +/// the various deallocation instructions. +/// +/// We don't need guaranteed execution of any deallocation function during +/// unwinding. Before this transformation, an unwind mid-loop would leak one +/// pointer that was allocated at the start of the loop. After this +/// transformation, it would leak the one pointer allocated before the loop +/// began. There is no difference visible to the caller. +/// +/// We do have to ensure that the maximum amount of allocated memory is not +/// raised by this transformation. To ensure this, we stop looking for +/// allocations after seeing an opaque function call. For example: +/// loop_top: +/// %ptr1 = call i8* @malloc(i32 %loop_invariant1) ;; candidate +/// %ptr2 = call i8* @malloc(i32 %loop_variant2) ;; not candidate +/// %ptr3 = call i8* @malloc(i32 %loop_invariant3) ;; candidate +/// call void @opaque() ;; stop scanning +/// %ptr5 = call i8* @malloc(i32 %loop_invariant5) ;; not candidate +/// +/// The same idea applies in reverse order to @free calls at the loop exits: +/// loop_exiting: +/// call void @free(%ptr1) ;; not candidate +/// call void @opaque() ;; stop scanning +/// call void @free(%ptr2) ;; %ptr2 is candidate +/// ;; start here and scan upwards +void LoopAllocationInfo::analyzeLoop(LoopInfo *LI, DominatorTree *DT, + TargetLibraryInfo *TLI, Loop *CurLoop) { + assert(LI != nullptr && DT != nullptr && CurLoop != nullptr && + "Unexpected input to LoopAllocationInfo::analyzeLoop."); + if (!TLI) + return; + + SmallVector LatchBlocks; + CurLoop->getLoopLatches(LatchBlocks); + if (LatchBlocks.empty()) + return; + + SmallVector ExitBlocks; + CurLoop->getExitBlocks(ExitBlocks); + if (ExitBlocks.empty()) + return; + + // Unlike hoistRegion, we only scan the header block. If the allocation is in + // a later block, it must be behind some sort of branch which implies that + // it's conditional on something or else another optimization would've removed + // the unconditional branch earlier). + BasicBlock *HeaderBB = CurLoop->getHeader(); + SmallPtrSet HeaderBlock; + HeaderBlock.insert(HeaderBB); + for (BasicBlock::iterator II = HeaderBB->begin(), E = HeaderBB->end(); + II != E; ++II) { + if (!II->mayDeallocateMemory() && !II->mayAllocateMemory()) + continue; + if (!llvm::isAllocationFn(&*II, TLI)) + break; + auto CI = cast(II); + + // Find places in the loop where the pointer is certainly freed. The places + // we identify must free this allocation, but there may be any number of + // other places that could free our pointer which we miss. + // + // We use this to ensure that the allocation is freed before we go around + // any loop latch. + SmallVector FreeCalls; + constexpr size_t UseVisitThreshold = 20; + SmallVector Worklist; + SmallPtrSet Visited; + auto Enqueue = [&](const Instruction *I) { + for (const Use &U : I->uses()) { + Instruction *User = cast(U.getUser()); + if (!CurLoop->contains(User)) + continue; + if (!Visited.insert(User).second) + continue; + if (Visited.size() == UseVisitThreshold) + return; + Worklist.push_back(User); + } + }; + Enqueue(CI); + do { + Instruction *I = Worklist.pop_back_val(); + if (isa(I)) { + Enqueue(I); + } else if (auto *GEP = dyn_cast(I)) { + if (GEP->hasAllZeroIndices()) + Enqueue(GEP); + } else if (auto *PN = dyn_cast(I)) { + if (PN->hasConstantOrUndefValue()) + Enqueue(I); + } else if (llvm::isFreeCall(I, TLI)) { + FreeCalls.push_back(cast(I)); + } + } while (!Worklist.empty() && Visited.size() < UseVisitThreshold); + + if (FreeCalls.empty() || Visited.size() >= UseVisitThreshold) + continue; + + SmallPtrSet FreeCallBBs; + for (auto FreeCall : FreeCalls) + FreeCallBBs.insert(FreeCall->getParent()); + + bool DoNotTransform = false; + + // Check that the frees we found cover all the latches. + for (BasicBlock *LatchBB : LatchBlocks) { + if (FreeCallBBs.count(LatchBB)) + continue; + SmallVector HeaderWorklist; + HeaderWorklist.push_back(HeaderBB); + if (llvm::isPotentiallyReachableFromMany(HeaderWorklist, LatchBB, + &FreeCallBBs, DT, LI)) { + DoNotTransform = true; + break; + } + } + if (DoNotTransform) + continue; + + // Examine each exit block and determine whether was a free which is + // unconditionally executed on the way to the exit block. + // + // We use two queries, is there a path from any free to this exit without + // going back to the header (if not, do not insert a free), and is there a + // path from the path from the header to this exit without going through any + // frees (if not, we must insert a free). Both of these queries can return + // true, in which case the deallocation is conditional or there are other + // deallocations we can not see, and we do not perform the transform. + SmallVector InsertDeallocation; + for (auto ExitBB : ExitBlocks) { + SmallVector HeaderWorklist, FreeCallWorklist; + HeaderWorklist.push_back(HeaderBB); + FreeCallWorklist.insert(FreeCallWorklist.end(), FreeCallBBs.begin(), + FreeCallBBs.end()); + bool A = llvm::isPotentiallyReachableFromMany(HeaderWorklist, ExitBB, + &FreeCallBBs, DT, LI); + bool B = FreeCallBBs.count(HeaderBB) || + llvm::isPotentiallyReachableFromMany(FreeCallWorklist, ExitBB, + &HeaderBlock, DT, LI); + assert((A || B) && "loop exit blocks not reachable from loop"); + if (A && B) { + // We can't tell whether we pass through a free on the way to this exit + // block. + DoNotTransform = true; + break; + } + if (B) + InsertDeallocation.push_back(ExitBB); + } + if (DoNotTransform) + continue; + + AllocationLookup[CI] = Allocations.size(); + for (const CallInst *FreeCall : FreeCalls) + DeallocationLookup[FreeCall] = Allocations.size(); + Allocations.push_back(CI); + Deallocations.emplace_back(std::move(FreeCalls)); + ExitBlocksToAddDeallocationsTo.emplace_back(std::move(InsertDeallocation)); + } +} + +// sinkRegion has determined that this deallocation call may be sunk. +void LoopAllocationInfo::addSafeToSink(const CallInst *CI) { + if (DeallocationLookup.count(CI)) + SafeToSink.insert(CI); +} + +// hoistRegion would like to know whether the given allocation call may be +// hoisted. +bool LoopAllocationInfo::mayHoist(const CallInst *CI) const { + auto it = AllocationLookup.find(CI); + if (it == AllocationLookup.end()) + return false; + size_t index = it->second; + assert(index < Deallocations.size()); + for (const CallInst *FreeCall : Deallocations[index]) { + if (!SafeToSink.count(FreeCall)) + return false; + } + return true; +} + +const SmallVector & +LoopAllocationInfo::toSink(const CallInst *CI) { + assert(AllocationLookup.find(CI) != AllocationLookup.end()); + return Deallocations[AllocationLookup[CI]]; +} + +const SmallVector & +LoopAllocationInfo::addDeallocations(const CallInst *CI) { + assert(AllocationLookup.find(CI) != AllocationLookup.end()); + return ExitBlocksToAddDeallocationsTo[AllocationLookup[CI]]; +} + +} // namespace llvm diff --git a/llvm/lib/CodeGen/DwarfEHPrepare.cpp b/llvm/lib/CodeGen/DwarfEHPrepare.cpp --- a/llvm/lib/CodeGen/DwarfEHPrepare.cpp +++ b/llvm/lib/CodeGen/DwarfEHPrepare.cpp @@ -145,7 +145,7 @@ size_t ResumeIndex = 0; for (auto *RI : Resumes) { for (auto *LP : CleanupLPads) { - if (isPotentiallyReachable(LP, RI, DT)) { + if (isPotentiallyReachable(LP, RI, nullptr, DT)) { ResumeReachable.set(ResumeIndex); break; } diff --git a/llvm/lib/IR/Instruction.cpp b/llvm/lib/IR/Instruction.cpp --- a/llvm/lib/IR/Instruction.cpp +++ b/llvm/lib/IR/Instruction.cpp @@ -548,6 +548,46 @@ } } +bool Instruction::mayAllocateMemory() const { + switch (getOpcode()) { + default: + return false; + case Instruction::CallBr: + return true; + case Instruction::Call: { + auto II = dyn_cast(this); + if (!II) + return true; + switch (II->getIntrinsicID()) { + default: + return false; + case Intrinsic::objc_autoreleasePoolPush: + return true; + } + } + } +} + +bool Instruction::mayDeallocateMemory() const { + switch (getOpcode()) { + default: + return false; + case Instruction::CallBr: + return true; + case Instruction::Call: { + auto II = dyn_cast(this); + if (!II) + return true; + switch (II->getIntrinsicID()) { + default: + return false; + case Intrinsic::objc_autoreleasePoolPop: + return true; + } + } + } +} + bool Instruction::isAtomic() const { switch (getOpcode()) { default: diff --git a/llvm/lib/Transforms/Scalar/LICM.cpp b/llvm/lib/Transforms/Scalar/LICM.cpp --- a/llvm/lib/Transforms/Scalar/LICM.cpp +++ b/llvm/lib/Transforms/Scalar/LICM.cpp @@ -40,6 +40,7 @@ #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/GuardUtils.h" #include "llvm/Analysis/Loads.h" +#include "llvm/Analysis/LoopAllocationInfo.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/Analysis/LoopIterator.h" #include "llvm/Analysis/LoopPass.h" @@ -56,6 +57,7 @@ #include "llvm/IR/DataLayout.h" #include "llvm/IR/DerivedTypes.h" #include "llvm/IR/Dominators.h" +#include "llvm/IR/IRBuilder.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/LLVMContext.h" @@ -139,8 +141,7 @@ MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE); static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, - MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE, - bool FreeInLoop); + MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE); static bool isSafeToExecuteUnconditionally(Instruction &Inst, const DominatorTree *DT, const Loop *CurLoop, @@ -343,6 +344,11 @@ ICFLoopSafetyInfo SafetyInfo(DT); SafetyInfo.computeLoopSafetyInfo(L); + // Scan for matching malloc/free pairs. + LoopAllocationInfo LAI; + if (L->hasDedicatedExits() && Preheader) + LAI.analyzeLoop(LI, DT, TLI, L); + // We want to visit all of the instructions in this loop... that are not parts // of our subloops (they have already had their invariants hoisted out of // their loop, into this loop, so there is no need to process the BODIES of @@ -355,11 +361,11 @@ // if (L->hasDedicatedExits()) Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, TTI, L, - CurAST.get(), MSSAU.get(), &SafetyInfo, + CurAST.get(), MSSAU.get(), &SafetyInfo, &LAI, NoOfMemAccTooLarge, LicmMssaOptCounter, ORE); if (Preheader) Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L, - CurAST.get(), MSSAU.get(), &SafetyInfo, + CurAST.get(), MSSAU.get(), &SafetyInfo, &LAI, NoOfMemAccTooLarge, LicmMssaOptCounter, ORE); // Now that all loop invariants have been removed from the loop, promote any @@ -464,12 +470,13 @@ DominatorTree *DT, TargetLibraryInfo *TLI, TargetTransformInfo *TTI, Loop *CurLoop, AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU, - ICFLoopSafetyInfo *SafetyInfo, bool NoOfMemAccTooLarge, - int &LicmMssaOptCounter, OptimizationRemarkEmitter *ORE) { + ICFLoopSafetyInfo *SafetyInfo, LoopAllocationInfo *LAI, + bool NoOfMemAccTooLarge, int &LicmMssaOptCounter, + OptimizationRemarkEmitter *ORE) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && - CurLoop != nullptr && SafetyInfo != nullptr && + CurLoop != nullptr && SafetyInfo != nullptr && LAI != nullptr && "Unexpected input to sinkRegion."); assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."); @@ -487,6 +494,7 @@ if (inSubLoop(BB, CurLoop, LI)) continue; + bool PassedOpaqueFunction = LAI->empty(); for (BasicBlock::iterator II = BB->end(); II != BB->begin();) { Instruction &I = *--II; @@ -511,7 +519,7 @@ canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, MSSAU, true, NoOfMemAccTooLarge, &LicmMssaOptCounter, ORE) && !I.mayHaveSideEffects()) { - if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE, FreeInLoop)) { + if (sink(I, LI, DT, CurLoop, SafetyInfo, MSSAU, ORE)) { if (!FreeInLoop) { ++II; eraseInstruction(I, *SafetyInfo, CurAST, MSSAU); @@ -519,6 +527,14 @@ Changed = true; } } + + if (!PassedOpaqueFunction) { + if (llvm::isFreeCall(&I, TLI)) { + LAI->addSafeToSink(cast(&I)); + } else if (I.mayAllocateMemory()) { + PassedOpaqueFunction = true; + } + } } } if (MSSAU && VerifyMemorySSA) @@ -763,12 +779,12 @@ bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop, AliasSetTracker *CurAST, MemorySSAUpdater *MSSAU, - ICFLoopSafetyInfo *SafetyInfo, bool NoOfMemAccTooLarge, - int &LicmMssaOptCounter, + ICFLoopSafetyInfo *SafetyInfo, LoopAllocationInfo *LAI, + bool NoOfMemAccTooLarge, int &LicmMssaOptCounter, OptimizationRemarkEmitter *ORE) { // Verify inputs. assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr && - CurLoop != nullptr && SafetyInfo != nullptr && + CurLoop != nullptr && SafetyInfo != nullptr && LAI != nullptr && "Unexpected input to hoistRegion."); assert(((CurAST != nullptr) ^ (MSSAU != nullptr)) && "Either AliasSetTracker or MemorySSA should be initialized."); @@ -829,6 +845,32 @@ continue; } + // If it's a malloc/free pair, try hoisting it out to the preheader. We + // don't need to worry about intervening unwinding function calls in this + // case, so we can be more aggressive than for generic instructions. + if (CurLoop->hasLoopInvariantOperands(&I) && + llvm::isAllocationFn(&I, TLI) && LAI->mayHoist(cast(&I))) { + IRBuilder<>(&I).CreateLifetimeStart(&I); + hoist(I, DT, CurLoop, CFH.getOrCreateHoistedBlock(BB), SafetyInfo, + MSSAU, ORE); + HoistedInstructions.push_back(&I); + Instruction *Pattern = LAI->toSink(cast(&I))[0]; + for (auto ExitBlock : LAI->addDeallocations(cast(&I))) { + Instruction *Clone = Pattern->clone(); + Clone->dropUnknownNonDebugMetadata(); + ExitBlock->getInstList().insert(ExitBlock->getFirstInsertionPt(), + Clone); + } + + for (auto FreeCall : LAI->toSink(cast(&I))) { + IRBuilder<>(FreeCall).CreateLifetimeEnd(&I); + eraseInstruction(*FreeCall, *SafetyInfo, CurAST, MSSAU); + } + + Changed = true; + continue; + } + // Attempt to remove floating point division out of the loop by // converting it to a reciprocal multiplication. if (I.getOpcode() == Instruction::FDiv && @@ -998,16 +1040,15 @@ namespace { /// Return true if-and-only-if we know how to (mechanically) both hoist and /// sink a given instruction out of a loop. Does not address legality -/// concerns such as aliasing or speculation safety. +/// concerns such as aliasing or speculation safety. bool isHoistableAndSinkableInst(Instruction &I) { // Only these instructions are hoistable/sinkable. - return (isa(I) || isa(I) || - isa(I) || isa(I) || - isa(I) || isa(I) || - isa(I) || isa(I) || - isa(I) || isa(I) || - isa(I) || isa(I) || - isa(I) || isa(I)); + return (isa(I) || isa(I) || isa(I) || + isa(I) || isa(I) || isa(I) || + isa(I) || isa(I) || isa(I) || + isa(I) || isa(I) || + isa(I) || isa(I) || + isa(I)); } /// Return true if all of the alias sets within this AST are known not to /// contain a Mod, or if MSSA knows thare are no MemoryDefs in the loop. @@ -1317,7 +1358,7 @@ // Sinking call-sites need to be handled differently from other // instructions. The cloned call-site needs a funclet bundle operand - // appropriate for it's location in the CFG. + // appropriate for its location in the CFG. SmallVector OpBundles; for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles(); BundleIdx != BundleEnd; ++BundleIdx) { @@ -1515,8 +1556,7 @@ /// static bool sink(Instruction &I, LoopInfo *LI, DominatorTree *DT, const Loop *CurLoop, ICFLoopSafetyInfo *SafetyInfo, - MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE, - bool FreeInLoop) { + MemorySSAUpdater *MSSAU, OptimizationRemarkEmitter *ORE) { LLVM_DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n"); ORE->emit([&]() { return OptimizationRemark(DEBUG_TYPE, "InstSunk", &I) @@ -1530,7 +1570,7 @@ ++NumSunk; // Iterate over users to be ready for actual sinking. Replace users via - // unrechable blocks with undef and make all user PHIs trivially replcable. + // unreachable blocks with undef and make all user PHIs trivially replaceable. SmallPtrSet VisitedUsers; for (Value::user_iterator UI = I.user_begin(), UE = I.user_end(); UI != UE;) { auto *User = cast(*UI); diff --git a/llvm/test/Transforms/LICM/allocs.ll b/llvm/test/Transforms/LICM/allocs.ll new file mode 100644 --- /dev/null +++ b/llvm/test/Transforms/LICM/allocs.ll @@ -0,0 +1,300 @@ +; RUN: opt -S -licm < %s | FileCheck %s + +declare i8* @malloc(i32) +declare void @free(i8* nocapture) + +declare void @use(i8*) +declare i1 @expr() + +define void @test1(i32 %loop_invariant) { +; CHECK-LABEL: @test1 +header: +; CHECK-LABEL: header: +; CHECK: @malloc +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-NOT: @malloc +; CHECK: @llvm.lifetime.start +; CHECK-NOT: @malloc +; CHECK: @use +; CHECK-NOT: @free +; CHECK: @llvm.lifetime.end +; CHECK-NOT: @free + %ptr = call i8* @malloc(i32 %loop_invariant) + call void @use(i8* %ptr) + call void @free(i8* %ptr) + br i1 undef, label %loop, label %loopexit + +loopexit: +; CHECK-LABEL: loopexit: +; CHECK: @free + ret void +} + +declare void @mightmalloc() + +define void @test2(i32 %loop_invariant) { +; CHECK-LABEL: @test2 +header: +; CHECK-LABEL: header: +; CHECK-NOT: @malloc +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: @malloc +; CHECK: @use +; CHECK: @free +; CHECK: @mightmalloc + %ptr = call i8* @malloc(i32 %loop_invariant) + call void @use(i8* %ptr) + call void @free(i8* %ptr) + call void @mightmalloc() + br i1 undef, label %loop, label %loopexit + +loopexit: +; CHECK-LABEL: loopexit: +; CHECK-NOT: @free + ret void +} + +define void @test3(i32 %loop_invariant) { +; CHECK-LABEL: @test3 +header: +; CHECK-LABEL: header: +; CHECK-NOT: @malloc +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: @mightmalloc +; CHECK: @malloc +; CHECK: @use +; CHECK: @free + call void @mightmalloc() + %ptr = call i8* @malloc(i32 %loop_invariant) + call void @use(i8* %ptr) + call void @free(i8* %ptr) + br i1 undef, label %loop, label %loopexit + +loopexit: +; CHECK-LABEL: loopexit: +; CHECK-NOT: @free + ret void +} + +define void @test4(i32 %loop_invariant) { +; CHECK-LABEL: @test4 +header: +; CHECK-LABEL: header: +; CHECK: @malloc +; CHECK: @malloc +; CHECK: @malloc +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-NOT: @malloc +; CHECK: @llvm.lifetime.start +; CHECK: @llvm.lifetime.start +; CHECK: @llvm.lifetime.start +; CHECK: @use +; CHECK: @use +; CHECK: @use +; CHECK: @llvm.lifetime.end +; CHECK: @llvm.lifetime.end +; CHECK: @llvm.lifetime.end +; CHECK-NOT: @free + %ptr1 = call i8* @malloc(i32 %loop_invariant) + %ptr2 = call i8* @malloc(i32 %loop_invariant) + %ptr3 = call i8* @malloc(i32 %loop_invariant) + call void @use(i8* %ptr1) + call void @use(i8* %ptr2) + call void @use(i8* %ptr3) + call void @free(i8* %ptr1) + call void @free(i8* %ptr2) + call void @free(i8* %ptr3) + br i1 undef, label %loop, label %loopexit + +loopexit: +; CHECK-LABEL: loopexit: +; CHECK: @free +; CHECK: @free +; CHECK: @free + ret void +} + +define void @test5(i32 %loop_invariant) { +; CHECK-LABEL: @test5 +header: +; CHECK-LABEL: header: +; CHECK: @malloc +; CHECK: @malloc +; CHECK: @malloc +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-NOT: @malloc +; CHECK: @llvm.lifetime.start +; CHECK: @llvm.lifetime.start +; CHECK: @llvm.lifetime.start +; CHECK: @use +; CHECK: @use +; CHECK: @use +; CHECK: @llvm.lifetime.end +; CHECK: @llvm.lifetime.end +; CHECK: @llvm.lifetime.end +; CHECK-NOT: @free + %ptr3 = call i8* @malloc(i32 %loop_invariant) + %ptr2 = call i8* @malloc(i32 %loop_invariant) + %ptr1 = call i8* @malloc(i32 %loop_invariant) + call void @use(i8* %ptr1) + call void @use(i8* %ptr2) + call void @use(i8* %ptr3) + call void @free(i8* %ptr1) + call void @free(i8* %ptr2) + call void @free(i8* %ptr3) + br i1 undef, label %loop, label %loopexit + +loopexit: +; CHECK-LABEL: loopexit: +; CHECK: @free +; CHECK: @free +; CHECK: @free + ret void +} + +define void @test6(i32 %loop_invariant) { +; CHECK-LABEL: @test6 +header: +; CHECK-LABEL: header: +; CHECK: @malloc +; CHECK: @malloc +; CHECK-NOT: @malloc +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK: @llvm.lifetime.start +; CHECK: @malloc +; CHECK: @llvm.lifetime.start +; CHECK: @use +; CHECK: @use +; CHECK: @use +; CHECK: @llvm.lifetime.end +; CHECK: @free +; CHECK: @llvm.lifetime.end + %i = phi i32 [%loop_invariant, %header], [%i.1, %loop] + %ptr1 = call i8* @malloc(i32 %loop_invariant) + %ptr2 = call i8* @malloc(i32 %i) + %ptr3 = call i8* @malloc(i32 %loop_invariant) + call void @use(i8* %ptr1) + call void @use(i8* %ptr2) + call void @use(i8* %ptr3) + call void @free(i8* %ptr1) + call void @free(i8* %ptr2) + call void @free(i8* %ptr3) + %i.1 = add i32 %i, 1 + br i1 undef, label %loop, label %loopexit + +loopexit: +; CHECK-LABEL: loopexit: +; CHECK: @free +; CHECK: @free +; CHECK-NOT: @free +; CHECK: ret void + ret void +} + +define void @test7(i32 %loop_invariant) { +; CHECK-LABEL: @test7 +header: +; CHECK-LABEL: header: +; CHECK: @malloc +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-NOT: @malloc +; CHECK: @llvm.lifetime.start +; CHECK-NOT: @malloc +; CHECK: @use +; CHECK-NOT: @free +; CHECK-NOT: @llvm.lifetime.end + %i = phi i32 [%loop_invariant, %header], [%i.1, %loop.2], [%i.1, %loop.3] + %ptr = call i8* @malloc(i32 %loop_invariant) + call void @use(i8* %ptr) + %i.1 = add i32 %i, 1 + %cmp = icmp eq i32 %i.1, 123 + br i1 %cmp, label %loop.2, label %loop.3 + +loop.2: +; CHECK-LABEL: loop.2: +; CHECK-NOT: @free +; CHECK: @llvm.lifetime.end +; CHECK-NOT: @free + %continue.1 = call i1 @expr() + call void @free(i8* %ptr) + br i1 %continue.1, label %loop, label %loopexit + +loop.3: +; CHECK-LABEL: loop.3: +; CHECK-NOT: @free +; CHECK: @llvm.lifetime.end +; CHECK-NOT: @free + %continue.2 = call i1 @expr() + call void @free(i8* %ptr) + br i1 %continue.2, label %loop, label %loopexit + +loopexit: +; CHECK-LABEL: loopexit: +; CHECK: @free + ret void +} + +declare void @assert_fail() + +define void @test8(i32 %loop_invariant) { +; CHECK-LABEL: @test8 +header: +; CHECK-LABEL: header: +; CHECK: @malloc +; CHECK: br label %loop + br label %loop + +loop: +; CHECK-LABEL: loop: +; CHECK-NOT: @malloc +; CHECK: @llvm.lifetime.start +; CHECK-NOT: @malloc + %ptr = call i8* @malloc(i32 %loop_invariant) + %fail = call i1 @expr() + br i1 %fail, label %assert_fail, label %assert_pass + +assert_fail: + call void @assert_fail() + unreachable + +assert_pass: +; CHECK-LABEL: assert_pass: +; CHECK-NOT: @free +; CHECK: @llvm.lifetime.end +; CHECK-NOT: @free + call void @free(i8* %ptr) + br i1 undef, label %loop, label %loopexit + +loopexit: +; CHECK-LABEL: loopexit: +; CHECK: @free + ret void +} diff --git a/llvm/unittests/Analysis/CFGTest.cpp b/llvm/unittests/Analysis/CFGTest.cpp --- a/llvm/unittests/Analysis/CFGTest.cpp +++ b/llvm/unittests/Analysis/CFGTest.cpp @@ -7,6 +7,7 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/CFG.h" +#include "llvm/ADT/SmallPtrSet.h" #include "llvm/Analysis/LoopInfo.h" #include "llvm/AsmParser/Parser.h" #include "llvm/IR/Dominators.h" @@ -57,24 +58,32 @@ report_fatal_error("@test must have an instruction %A"); if (B == nullptr) report_fatal_error("@test must have an instruction %B"); + + assert(ExclusionSet.empty()); + for (auto I = F->begin(), E = F->end(); I != E; ++I) { + if (I->hasName() && I->getName().startswith("excluded")) + ExclusionSet.insert(&*I); + } } void ExpectPath(bool ExpectedResult) { static char ID; class IsPotentiallyReachableTestPass : public FunctionPass { public: - IsPotentiallyReachableTestPass(bool ExpectedResult, - Instruction *A, Instruction *B) - : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B) {} - - static int initialize() { - PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", - "", &ID, nullptr, true, true); - PassRegistry::getPassRegistry()->registerPass(*PI, false); - initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); - initializeDominatorTreeWrapperPassPass( - *PassRegistry::getPassRegistry()); - return 0; + IsPotentiallyReachableTestPass(bool ExpectedResult, Instruction *A, + Instruction *B, + SmallPtrSet ExclusionSet) + : FunctionPass(ID), ExpectedResult(ExpectedResult), A(A), B(B), + ExclusionSet(ExclusionSet) {} + + static int initialize() { + PassInfo *PI = new PassInfo("isPotentiallyReachable testing pass", "", + &ID, nullptr, true, true); + PassRegistry::getPassRegistry()->registerPass(*PI, false); + initializeLoopInfoWrapperPassPass(*PassRegistry::getPassRegistry()); + initializeDominatorTreeWrapperPassPass( + *PassRegistry::getPassRegistry()); + return 0; } void getAnalysisUsage(AnalysisUsage &AU) const override { @@ -90,22 +99,26 @@ LoopInfo *LI = &getAnalysis().getLoopInfo(); DominatorTree *DT = &getAnalysis().getDomTree(); - EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, nullptr), + EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, nullptr), + ExpectedResult); + EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, nullptr), + ExpectedResult); + EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, nullptr, LI), + ExpectedResult); + EXPECT_EQ(isPotentiallyReachable(A, B, &ExclusionSet, DT, LI), ExpectedResult); - EXPECT_EQ(isPotentiallyReachable(A, B, DT, nullptr), ExpectedResult); - EXPECT_EQ(isPotentiallyReachable(A, B, nullptr, LI), ExpectedResult); - EXPECT_EQ(isPotentiallyReachable(A, B, DT, LI), ExpectedResult); return false; } bool ExpectedResult; Instruction *A, *B; + SmallPtrSet ExclusionSet; }; static int initialize = IsPotentiallyReachableTestPass::initialize(); (void)initialize; IsPotentiallyReachableTestPass *P = - new IsPotentiallyReachableTestPass(ExpectedResult, A, B); + new IsPotentiallyReachableTestPass(ExpectedResult, A, B, ExclusionSet); legacy::PassManager PM; PM.add(P); PM.run(*M); @@ -114,6 +127,7 @@ LLVMContext Context; std::unique_ptr M; Instruction *A, *B; + SmallPtrSet ExclusionSet; }; } @@ -385,3 +399,95 @@ S[0] = OldBB; ExpectPath(true); } + +TEST_F(IsPotentiallyReachableTest, UnreachableFromEntryTest) { + ParseAssembly("define void @test() {\n" + "entry:\n" + " %A = bitcast i8 undef to i8\n" + " ret void\n" + "not.reachable:\n" + " %B = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(false); +} + +TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest1) { + ParseAssembly("define void @test() {\n" + "entry:\n" + " ret void\n" + "not.reachable.1:\n" + " %A = bitcast i8 undef to i8\n" + " br label %not.reachable.2\n" + "not.reachable.2:\n" + " %B = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(true); +} + +TEST_F(IsPotentiallyReachableTest, UnreachableBlocksTest2) { + ParseAssembly("define void @test() {\n" + "entry:\n" + " ret void\n" + "not.reachable.1:\n" + " %B = bitcast i8 undef to i8\n" + " br label %not.reachable.2\n" + "not.reachable.2:\n" + " %A = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(false); +} + +TEST_F(IsPotentiallyReachableTest, SimpleExclusionTest) { + ParseAssembly("define void @test() {\n" + "entry:\n" + " %A = bitcast i8 undef to i8\n" + " br label %excluded\n" + "excluded:\n" + " br label %exit\n" + "exit:\n" + " %B = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(false); +} + +TEST_F(IsPotentiallyReachableTest, DiamondExcludedTest) { + ParseAssembly("declare i1 @switch()\n" + "\n" + "define void @test() {\n" + "entry:\n" + " %x = call i1 @switch()\n" + " %A = bitcast i8 undef to i8\n" + " br i1 %x, label %excluded.1, label %excluded.2\n" + "excluded.1:\n" + " br label %exit\n" + "excluded.2:\n" + " br label %exit\n" + "exit:\n" + " %B = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(false); +} + +TEST_F(IsPotentiallyReachableTest, DiamondOneSideExcludedTest) { + ParseAssembly("declare i1 @switch()\n" + "\n" + "define void @test() {\n" + "entry:\n" + " %x = call i1 @switch()\n" + " %A = bitcast i8 undef to i8\n" + " br i1 %x, label %excluded, label %diamond\n" + "excluded:\n" + " br label %exit\n" + "diamond:\n" + " br label %exit\n" + "exit:\n" + " %B = bitcast i8 undef to i8\n" + " ret void\n" + "}"); + ExpectPath(true); +}