diff options
Diffstat (limited to 'include/llvm/Analysis/LoopInfo.h')
| -rw-r--r-- | include/llvm/Analysis/LoopInfo.h | 289 |
1 files changed, 201 insertions, 88 deletions
diff --git a/include/llvm/Analysis/LoopInfo.h b/include/llvm/Analysis/LoopInfo.h index 70ce9a8705175..28afc39727fab 100644 --- a/include/llvm/Analysis/LoopInfo.h +++ b/include/llvm/Analysis/LoopInfo.h @@ -29,7 +29,7 @@ // in the CFG. There can be strongly connected components in the CFG which // this analysis will not recognize and that will not be represented by a Loop // instance. In particular, a Loop might be inside such a non-loop SCC, or a -// non-loop SCC might contain a sub-SCC which is a Loop. +// non-loop SCC might contain a sub-SCC which is a Loop. // //===----------------------------------------------------------------------===// @@ -46,7 +46,9 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/PassManager.h" #include "llvm/Pass.h" +#include "llvm/Support/Allocator.h" #include <algorithm> +#include <utility> namespace llvm { @@ -56,110 +58,145 @@ class Loop; class MDNode; class PHINode; class raw_ostream; -template <class N, bool IsPostDom> -class DominatorTreeBase; -template<class N, class M> class LoopInfoBase; -template<class N, class M> class LoopBase; +template <class N, bool IsPostDom> class DominatorTreeBase; +template <class N, class M> class LoopInfoBase; +template <class N, class M> class LoopBase; //===----------------------------------------------------------------------===// /// Instances of this class are used to represent loops that are detected in the /// flow graph. /// -template<class BlockT, class LoopT> -class LoopBase { +template <class BlockT, class LoopT> class LoopBase { LoopT *ParentLoop; // Loops contained entirely within this one. std::vector<LoopT *> SubLoops; // The list of blocks in this loop. First entry is the header node. - std::vector<BlockT*> Blocks; + std::vector<BlockT *> Blocks; - SmallPtrSet<const BlockT*, 8> DenseBlockSet; + SmallPtrSet<const BlockT *, 8> DenseBlockSet; +#if LLVM_ENABLE_ABI_BREAKING_CHECKS /// Indicator that this loop is no longer a valid loop. bool IsInvalid = false; +#endif LoopBase(const LoopBase<BlockT, LoopT> &) = delete; - const LoopBase<BlockT, LoopT>& - operator=(const LoopBase<BlockT, LoopT> &) = delete; -public: - /// This creates an empty loop. - LoopBase() : ParentLoop(nullptr) {} - ~LoopBase() { - for (size_t i = 0, e = SubLoops.size(); i != e; ++i) - delete SubLoops[i]; - } + const LoopBase<BlockT, LoopT> & + operator=(const LoopBase<BlockT, LoopT> &) = delete; +public: /// Return the nesting level of this loop. An outer-most loop has depth 1, /// for consistency with loop depth values used for basic blocks, where depth /// 0 is used for blocks not inside any loops. unsigned getLoopDepth() const { + assert(!isInvalid() && "Loop not in a valid state!"); unsigned D = 1; for (const LoopT *CurLoop = ParentLoop; CurLoop; CurLoop = CurLoop->ParentLoop) ++D; return D; } - BlockT *getHeader() const { return Blocks.front(); } + BlockT *getHeader() const { return getBlocks().front(); } LoopT *getParentLoop() const { return ParentLoop; } /// This is a raw interface for bypassing addChildLoop. - void setParentLoop(LoopT *L) { ParentLoop = L; } + void setParentLoop(LoopT *L) { + assert(!isInvalid() && "Loop not in a valid state!"); + ParentLoop = L; + } /// Return true if the specified loop is contained within in this loop. bool contains(const LoopT *L) const { - if (L == this) return true; - if (!L) return false; + assert(!isInvalid() && "Loop not in a valid state!"); + if (L == this) + return true; + if (!L) + return false; return contains(L->getParentLoop()); } /// Return true if the specified basic block is in this loop. bool contains(const BlockT *BB) const { + assert(!isInvalid() && "Loop not in a valid state!"); return DenseBlockSet.count(BB); } /// Return true if the specified instruction is in this loop. - template<class InstT> - bool contains(const InstT *Inst) const { + template <class InstT> bool contains(const InstT *Inst) const { return contains(Inst->getParent()); } /// Return the loops contained entirely within this loop. - const std::vector<LoopT *> &getSubLoops() const { return SubLoops; } - std::vector<LoopT *> &getSubLoopsVector() { return SubLoops; } + const std::vector<LoopT *> &getSubLoops() const { + assert(!isInvalid() && "Loop not in a valid state!"); + return SubLoops; + } + std::vector<LoopT *> &getSubLoopsVector() { + assert(!isInvalid() && "Loop not in a valid state!"); + return SubLoops; + } typedef typename std::vector<LoopT *>::const_iterator iterator; - typedef typename std::vector<LoopT *>::const_reverse_iterator - reverse_iterator; - iterator begin() const { return SubLoops.begin(); } - iterator end() const { return SubLoops.end(); } - reverse_iterator rbegin() const { return SubLoops.rbegin(); } - reverse_iterator rend() const { return SubLoops.rend(); } - bool empty() const { return SubLoops.empty(); } + typedef + typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; + iterator begin() const { return getSubLoops().begin(); } + iterator end() const { return getSubLoops().end(); } + reverse_iterator rbegin() const { return getSubLoops().rbegin(); } + reverse_iterator rend() const { return getSubLoops().rend(); } + bool empty() const { return getSubLoops().empty(); } /// Get a list of the basic blocks which make up this loop. - const std::vector<BlockT*> &getBlocks() const { return Blocks; } - typedef typename std::vector<BlockT*>::const_iterator block_iterator; - block_iterator block_begin() const { return Blocks.begin(); } - block_iterator block_end() const { return Blocks.end(); } + ArrayRef<BlockT *> getBlocks() const { + assert(!isInvalid() && "Loop not in a valid state!"); + return Blocks; + } + typedef typename ArrayRef<BlockT *>::const_iterator block_iterator; + block_iterator block_begin() const { return getBlocks().begin(); } + block_iterator block_end() const { return getBlocks().end(); } inline iterator_range<block_iterator> blocks() const { + assert(!isInvalid() && "Loop not in a valid state!"); return make_range(block_begin(), block_end()); } /// Get the number of blocks in this loop in constant time. + /// Invalidate the loop, indicating that it is no longer a loop. unsigned getNumBlocks() const { + assert(!isInvalid() && "Loop not in a valid state!"); return Blocks.size(); } - /// Invalidate the loop, indicating that it is no longer a loop. - void invalidate() { IsInvalid = true; } - - /// Return true if this loop is no longer valid. - bool isInvalid() { return IsInvalid; } + /// Return a direct, mutable handle to the blocks vector so that we can + /// mutate it efficiently with techniques like `std::remove`. + std::vector<BlockT *> &getBlocksVector() { + assert(!isInvalid() && "Loop not in a valid state!"); + return Blocks; + } + /// Return a direct, mutable handle to the blocks set so that we can + /// mutate it efficiently. + SmallPtrSetImpl<const BlockT *> &getBlocksSet() { + assert(!isInvalid() && "Loop not in a valid state!"); + return DenseBlockSet; + } + + /// Return true if this loop is no longer valid. The only valid use of this + /// helper is "assert(L.isInvalid())" or equivalent, since IsInvalid is set to + /// true by the destructor. In other words, if this accessor returns true, + /// the caller has already triggered UB by calling this accessor; and so it + /// can only be called in a context where a return value of true indicates a + /// programmer error. + bool isInvalid() const { +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + return IsInvalid; +#else + return false; +#endif + } /// True if terminator in the block can branch to another block that is /// outside of the current loop. bool isLoopExiting(const BlockT *BB) const { - for (const auto &Succ : children<const BlockT*>(BB)) { + assert(!isInvalid() && "Loop not in a valid state!"); + for (const auto &Succ : children<const BlockT *>(BB)) { if (!contains(Succ)) return true; } @@ -171,20 +208,22 @@ public: /// This function is useful when there are multiple latches in a loop /// because \fn getLoopLatch will return nullptr in that case. bool isLoopLatch(const BlockT *BB) const { + assert(!isInvalid() && "Loop not in a valid state!"); assert(contains(BB) && "block does not belong to the loop"); BlockT *Header = getHeader(); - auto PredBegin = GraphTraits<Inverse<BlockT*> >::child_begin(Header); - auto PredEnd = GraphTraits<Inverse<BlockT*> >::child_end(Header); + auto PredBegin = GraphTraits<Inverse<BlockT *>>::child_begin(Header); + auto PredEnd = GraphTraits<Inverse<BlockT *>>::child_end(Header); return std::find(PredBegin, PredEnd, BB) != PredEnd; } /// Calculate the number of back edges to the loop header. unsigned getNumBackEdges() const { + assert(!isInvalid() && "Loop not in a valid state!"); unsigned NumBackEdges = 0; BlockT *H = getHeader(); - for (const auto Pred : children<Inverse<BlockT*> >(H)) + for (const auto Pred : children<Inverse<BlockT *>>(H)) if (contains(Pred)) ++NumBackEdges; @@ -210,14 +249,14 @@ public: /// Return all of the successor blocks of this loop. These are the blocks /// _outside of the current loop_ which are branched to. - void getExitBlocks(SmallVectorImpl<BlockT*> &ExitBlocks) const; + void getExitBlocks(SmallVectorImpl<BlockT *> &ExitBlocks) const; /// If getExitBlocks would return exactly one block, return that block. /// Otherwise return null. BlockT *getExitBlock() const; /// Edge type. - typedef std::pair<const BlockT*, const BlockT*> Edge; + typedef std::pair<const BlockT *, const BlockT *> Edge; /// Return all pairs of (_inside_block_,_outside_block_). void getExitEdges(SmallVectorImpl<Edge> &ExitEdges) const; @@ -243,8 +282,9 @@ public: /// Return all loop latch blocks of this loop. A latch block is a block that /// contains a branch back to the header. void getLoopLatches(SmallVectorImpl<BlockT *> &LoopLatches) const { + assert(!isInvalid() && "Loop not in a valid state!"); BlockT *H = getHeader(); - for (const auto Pred : children<Inverse<BlockT*>>(H)) + for (const auto Pred : children<Inverse<BlockT *>>(H)) if (contains(Pred)) LoopLatches.push_back(Pred); } @@ -269,6 +309,7 @@ public: /// Add the specified loop to be a child of this loop. /// This updates the loop depth of the new child. void addChildLoop(LoopT *NewChild) { + assert(!isInvalid() && "Loop not in a valid state!"); assert(!NewChild->ParentLoop && "NewChild already has a parent!"); NewChild->ParentLoop = static_cast<LoopT *>(this); SubLoops.push_back(NewChild); @@ -277,37 +318,49 @@ public: /// This removes the specified child from being a subloop of this loop. The /// loop is not deleted, as it will presumably be inserted into another loop. LoopT *removeChildLoop(iterator I) { + assert(!isInvalid() && "Loop not in a valid state!"); assert(I != SubLoops.end() && "Cannot remove end iterator!"); LoopT *Child = *I; assert(Child->ParentLoop == this && "Child is not a child of this loop!"); - SubLoops.erase(SubLoops.begin()+(I-begin())); + SubLoops.erase(SubLoops.begin() + (I - begin())); Child->ParentLoop = nullptr; return Child; } + /// This removes the specified child from being a subloop of this loop. The + /// loop is not deleted, as it will presumably be inserted into another loop. + LoopT *removeChildLoop(LoopT *Child) { + return removeChildLoop(llvm::find(*this, Child)); + } + /// This adds a basic block directly to the basic block list. /// This should only be used by transformations that create new loops. Other /// transformations should use addBasicBlockToLoop. void addBlockEntry(BlockT *BB) { + assert(!isInvalid() && "Loop not in a valid state!"); Blocks.push_back(BB); DenseBlockSet.insert(BB); } /// interface to reverse Blocks[from, end of loop] in this loop void reverseBlock(unsigned from) { + assert(!isInvalid() && "Loop not in a valid state!"); std::reverse(Blocks.begin() + from, Blocks.end()); } /// interface to do reserve() for Blocks void reserveBlocks(unsigned size) { + assert(!isInvalid() && "Loop not in a valid state!"); Blocks.reserve(size); } /// This method is used to move BB (which must be part of this loop) to be the /// loop header of the loop (the block that dominates all others). void moveToHeader(BlockT *BB) { - if (Blocks[0] == BB) return; - for (unsigned i = 0; ; ++i) { + assert(!isInvalid() && "Loop not in a valid state!"); + if (Blocks[0] == BB) + return; + for (unsigned i = 0;; ++i) { assert(i != Blocks.size() && "Loop does not contain BB!"); if (Blocks[i] == BB) { Blocks[i] = Blocks[0]; @@ -321,6 +374,7 @@ public: /// Blocks as appropriate. This does not update the mapping in the LoopInfo /// class. void removeBlockFromLoop(BlockT *BB) { + assert(!isInvalid() && "Loop not in a valid state!"); auto I = find(Blocks, BB); assert(I != Blocks.end() && "N is not in this list!"); Blocks.erase(I); @@ -332,21 +386,47 @@ public: void verifyLoop() const; /// Verify loop structure of this loop and all nested loops. - void verifyLoopNest(DenseSet<const LoopT*> *Loops) const; + void verifyLoopNest(DenseSet<const LoopT *> *Loops) const; /// Print loop with all the BBs inside it. void print(raw_ostream &OS, unsigned Depth = 0, bool Verbose = false) const; protected: friend class LoopInfoBase<BlockT, LoopT>; + + /// This creates an empty loop. + LoopBase() : ParentLoop(nullptr) {} + explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) { Blocks.push_back(BB); DenseBlockSet.insert(BB); } + + // Since loop passes like SCEV are allowed to key analysis results off of + // `Loop` pointers, we cannot re-use pointers within a loop pass manager. + // This means loop passes should not be `delete` ing `Loop` objects directly + // (and risk a later `Loop` allocation re-using the address of a previous one) + // but should be using LoopInfo::markAsRemoved, which keeps around the `Loop` + // pointer till the end of the lifetime of the `LoopInfo` object. + // + // To make it easier to follow this rule, we mark the destructor as + // non-public. + ~LoopBase() { + for (auto *SubLoop : SubLoops) + SubLoop->~LoopT(); + +#if LLVM_ENABLE_ABI_BREAKING_CHECKS + IsInvalid = true; +#endif + SubLoops.clear(); + Blocks.clear(); + DenseBlockSet.clear(); + ParentLoop = nullptr; + } }; -template<class BlockT, class LoopT> -raw_ostream& operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) { +template <class BlockT, class LoopT> +raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) { Loop.print(OS); return OS; } @@ -354,7 +434,6 @@ raw_ostream& operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) { // Implementation in LoopInfoImpl.h extern template class LoopBase<BasicBlock, Loop>; - /// Represents a single loop in the control flow graph. Note that not all SCCs /// in the CFG are necessarily loops. class Loop : public LoopBase<BasicBlock, Loop> { @@ -367,21 +446,17 @@ public: public: LocRange() {} LocRange(DebugLoc Start) : Start(std::move(Start)), End(std::move(Start)) {} - LocRange(DebugLoc Start, DebugLoc End) : Start(std::move(Start)), - End(std::move(End)) {} + LocRange(DebugLoc Start, DebugLoc End) + : Start(std::move(Start)), End(std::move(End)) {} const DebugLoc &getStart() const { return Start; } const DebugLoc &getEnd() const { return End; } /// \brief Check for null. /// - explicit operator bool() const { - return Start && End; - } + explicit operator bool() const { return Start && End; } }; - Loop() {} - /// Return true if the specified value is loop invariant. bool isLoopInvariant(const Value *V) const; @@ -464,6 +539,14 @@ public: /// operand should be the node itself. void setLoopID(MDNode *LoopID) const; + /// Add llvm.loop.unroll.disable to this loop's loop id metadata. + /// + /// Remove existing unroll metadata and add unroll disable metadata to + /// indicate the loop has already been unrolled. This prevents a loop + /// from being unrolled more than is directed by a pragma if the loop + /// unrolling pass is run more than once (which it generally is). + void setLoopAlreadyUnrolled(); + /// Return true if no exit block for the loop has a predecessor that is /// outside the loop. bool hasDedicatedExits() const; @@ -499,8 +582,12 @@ public: } private: + Loop() = default; + friend class LoopInfoBase<BasicBlock, Loop>; + friend class LoopBase<BasicBlock, Loop>; explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {} + ~Loop() = default; }; //===----------------------------------------------------------------------===// @@ -508,25 +595,26 @@ private: /// structures in the specified function. /// -template<class BlockT, class LoopT> -class LoopInfoBase { +template <class BlockT, class LoopT> class LoopInfoBase { // BBMap - Mapping of basic blocks to the inner most loop they occur in DenseMap<const BlockT *, LoopT *> BBMap; std::vector<LoopT *> TopLevelLoops; - std::vector<LoopT *> RemovedLoops; + BumpPtrAllocator LoopAllocator; friend class LoopBase<BlockT, LoopT>; friend class LoopInfo; void operator=(const LoopInfoBase &) = delete; LoopInfoBase(const LoopInfoBase &) = delete; + public: - LoopInfoBase() { } + LoopInfoBase() {} ~LoopInfoBase() { releaseMemory(); } LoopInfoBase(LoopInfoBase &&Arg) : BBMap(std::move(Arg.BBMap)), - TopLevelLoops(std::move(Arg.TopLevelLoops)) { + TopLevelLoops(std::move(Arg.TopLevelLoops)), + LoopAllocator(std::move(Arg.LoopAllocator)) { // We have to clear the arguments top level loops as we've taken ownership. Arg.TopLevelLoops.clear(); } @@ -534,8 +622,10 @@ public: BBMap = std::move(RHS.BBMap); for (auto *L : TopLevelLoops) - delete L; + L->~LoopT(); + TopLevelLoops = std::move(RHS.TopLevelLoops); + LoopAllocator = std::move(RHS.LoopAllocator); RHS.TopLevelLoops.clear(); return *this; } @@ -544,19 +634,22 @@ public: BBMap.clear(); for (auto *L : TopLevelLoops) - delete L; + L->~LoopT(); TopLevelLoops.clear(); - for (auto *L : RemovedLoops) - delete L; - RemovedLoops.clear(); + LoopAllocator.Reset(); + } + + template <typename... ArgsTy> LoopT *AllocateLoop(ArgsTy &&... Args) { + LoopT *Storage = LoopAllocator.Allocate<LoopT>(); + return new (Storage) LoopT(std::forward<ArgsTy>(Args)...); } /// iterator/begin/end - The interface to the top-level loops in the current /// function. /// typedef typename std::vector<LoopT *>::const_iterator iterator; - typedef typename std::vector<LoopT *>::const_reverse_iterator - reverse_iterator; + typedef + typename std::vector<LoopT *>::const_reverse_iterator reverse_iterator; iterator begin() const { return TopLevelLoops.begin(); } iterator end() const { return TopLevelLoops.end(); } reverse_iterator rbegin() const { return TopLevelLoops.rbegin(); } @@ -585,9 +678,7 @@ public: LoopT *getLoopFor(const BlockT *BB) const { return BBMap.lookup(BB); } /// Same as getLoopFor. - const LoopT *operator[](const BlockT *BB) const { - return getLoopFor(BB); - } + const LoopT *operator[](const BlockT *BB) const { return getLoopFor(BB); } /// Return the loop nesting level of the specified block. A depth of 0 means /// the block is not inside any loop. @@ -609,7 +700,7 @@ public: assert(I != end() && "Cannot remove end iterator!"); LoopT *L = *I; assert(!L->getParentLoop() && "Not a top-level loop!"); - TopLevelLoops.erase(TopLevelLoops.begin() + (I-begin())); + TopLevelLoops.erase(TopLevelLoops.begin() + (I - begin())); return L; } @@ -626,8 +717,7 @@ public: /// Replace the specified loop in the top-level loops list with the indicated /// loop. - void changeTopLevelLoop(LoopT *OldLoop, - LoopT *NewLoop) { + void changeTopLevelLoop(LoopT *OldLoop, LoopT *NewLoop) { auto I = find(TopLevelLoops, OldLoop); assert(I != TopLevelLoops.end() && "Old loop not at top level!"); *I = NewLoop; @@ -658,8 +748,10 @@ public: static bool isNotAlreadyContainedIn(const LoopT *SubLoop, const LoopT *ParentLoop) { - if (!SubLoop) return true; - if (SubLoop == ParentLoop) return false; + if (!SubLoop) + return true; + if (SubLoop == ParentLoop) + return false; return isNotAlreadyContainedIn(SubLoop->getParentLoop(), ParentLoop); } @@ -670,6 +762,24 @@ public: void print(raw_ostream &OS) const; void verify(const DominatorTreeBase<BlockT, false> &DomTree) const; + + /// Destroy a loop that has been removed from the `LoopInfo` nest. + /// + /// This runs the destructor of the loop object making it invalid to + /// reference afterward. The memory is retained so that the *pointer* to the + /// loop remains valid. + /// + /// The caller is responsible for removing this loop from the loop nest and + /// otherwise disconnecting it from the broader `LoopInfo` data structures. + /// Callers that don't naturally handle this themselves should probably call + /// `erase' instead. + void destroy(LoopT *L) { + L->~LoopT(); + + // Since LoopAllocator is a BumpPtrAllocator, this Deallocate only poisons + // \c L, but the pointer remains valid for non-dereferencing uses. + LoopAllocator.Deallocate(L); + } }; // Implementation in LoopInfoImpl.h @@ -682,6 +792,7 @@ class LoopInfo : public LoopInfoBase<BasicBlock, Loop> { void operator=(const LoopInfo &) = delete; LoopInfo(const LoopInfo &) = delete; + public: LoopInfo() {} explicit LoopInfo(const DominatorTreeBase<BasicBlock, false> &DomTree); @@ -702,7 +813,7 @@ public: /// the loop forest and parent loops for each block so that \c L is no longer /// referenced, but does not actually delete \c L immediately. The pointer /// will remain valid until this LoopInfo's memory is released. - void markAsRemoved(Loop *L); + void erase(Loop *L); /// Returns true if replacing From with To everywhere is guaranteed to /// preserve LCSSA form. @@ -710,7 +821,8 @@ public: // Preserving LCSSA form is only problematic if the replacing value is an // instruction. Instruction *I = dyn_cast<Instruction>(To); - if (!I) return true; + if (!I) + return true; // If both instructions are defined in the same basic block then replacement // cannot break LCSSA form. if (I->getParent() == From->getParent()) @@ -718,7 +830,8 @@ public: // If the instruction is not defined in a loop then it can safely replace // anything. Loop *ToLoop = getLoopFor(I->getParent()); - if (!ToLoop) return true; + if (!ToLoop) + return true; // If the replacing instruction is defined in the same loop as the original // instruction, or in a loop that contains it as an inner loop, then using // it as a replacement will not break LCSSA form. @@ -798,7 +911,7 @@ public: }; // Allow clients to walk the list of nested loops... -template <> struct GraphTraits<const Loop*> { +template <> struct GraphTraits<const Loop *> { typedef const Loop *NodeRef; typedef LoopInfo::iterator ChildIteratorType; @@ -807,7 +920,7 @@ template <> struct GraphTraits<const Loop*> { static ChildIteratorType child_end(NodeRef N) { return N->end(); } }; -template <> struct GraphTraits<Loop*> { +template <> struct GraphTraits<Loop *> { typedef Loop *NodeRef; typedef LoopInfo::iterator ChildIteratorType; |