From 691addc25f9ad25da4c679e447b325efce613308 Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sun, 18 Jan 2015 01:25:51 +0000 Subject: [PATCH] [PM] Now that LoopInfo isn't in the Pass type hierarchy, it is much cleaner to derive from the generic base. Thise removes a ton of boiler plate code and somewhat strange and pointless indirections. It also remove a bunch of the previously needed friend declarations. To fully remove these, I also lifted the verify logic into the generic LoopInfoBase, which seems good anyways -- it is generic and useful logic even for the machine side. llvm-svn: 226385 --- llvm/include/llvm/Analysis/LoopInfo.h | 81 ++-------------------- llvm/include/llvm/Analysis/LoopInfoImpl.h | 19 +++++ llvm/lib/Analysis/LoopInfo.cpp | 37 +++------- .../Scalar/InductiveRangeCheckElimination.cpp | 3 +- llvm/lib/Transforms/Scalar/LoopUnswitch.cpp | 6 +- llvm/lib/Transforms/Utils/BasicBlockUtils.cpp | 6 +- llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp | 8 +-- llvm/lib/Transforms/Utils/LoopSimplify.cpp | 2 +- llvm/lib/Transforms/Utils/LoopUnroll.cpp | 4 +- llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp | 4 +- llvm/lib/Transforms/Vectorize/LoopVectorize.cpp | 22 +++--- 11 files changed, 63 insertions(+), 129 deletions(-) diff --git a/llvm/include/llvm/Analysis/LoopInfo.h b/llvm/include/llvm/Analysis/LoopInfo.h index 01203c1..2377c80 100644 --- a/llvm/include/llvm/Analysis/LoopInfo.h +++ b/llvm/include/llvm/Analysis/LoopInfo.h @@ -495,7 +495,6 @@ class LoopInfoBase { std::vector TopLevelLoops; friend class LoopBase; friend class LoopInfo; - friend class LoopInfoWrapperPass; void operator=(const LoopInfoBase &) LLVM_DELETED_FUNCTION; LoopInfoBase(const LoopInfo &) LLVM_DELETED_FUNCTION; @@ -618,8 +617,9 @@ public: void Analyze(DominatorTreeBase &DomTree); // Debugging - void print(raw_ostream &OS) const; + + void verify() const; }; // Implementation in LoopInfoImpl.h @@ -627,86 +627,17 @@ public: __extension__ extern template class LoopInfoBase; #endif -class LoopInfo { - LoopInfoBase LI; +class LoopInfo : public LoopInfoBase { + typedef LoopInfoBase BaseT; + friend class LoopBase; - friend class LoopInfoWrapperPass; void operator=(const LoopInfo &) LLVM_DELETED_FUNCTION; LoopInfo(const LoopInfo &) LLVM_DELETED_FUNCTION; public: LoopInfo() {} - LoopInfoBase& getBase() { return LI; } - - /// iterator/begin/end - The interface to the top-level loops in the current - /// function. - /// - typedef LoopInfoBase::iterator iterator; - typedef LoopInfoBase::reverse_iterator reverse_iterator; - inline iterator begin() const { return LI.begin(); } - inline iterator end() const { return LI.end(); } - inline reverse_iterator rbegin() const { return LI.rbegin(); } - inline reverse_iterator rend() const { return LI.rend(); } - bool empty() const { return LI.empty(); } - - /// getLoopFor - Return the inner most loop that BB lives in. If a basic - /// block is in no loop (for example the entry node), null is returned. - /// - inline Loop *getLoopFor(const BasicBlock *BB) const { - return LI.getLoopFor(BB); - } - - /// operator[] - same as getLoopFor... - /// - inline const Loop *operator[](const BasicBlock *BB) const { - return LI.getLoopFor(BB); - } - - /// getLoopDepth - Return the loop nesting level of the specified block. A - /// depth of 0 means the block is not inside any loop. - /// - inline unsigned getLoopDepth(const BasicBlock *BB) const { - return LI.getLoopDepth(BB); - } - - // isLoopHeader - True if the block is a loop header node - inline bool isLoopHeader(BasicBlock *BB) const { - return LI.isLoopHeader(BB); - } - - /// removeLoop - This removes the specified top-level loop from this loop info - /// object. The loop is not deleted, as it will presumably be inserted into - /// another loop. - inline Loop *removeLoop(iterator I) { return LI.removeLoop(I); } - - /// changeLoopFor - Change the top-level loop that contains BB to the - /// specified loop. This should be used by transformations that restructure - /// the loop hierarchy tree. - inline void changeLoopFor(BasicBlock *BB, Loop *L) { - LI.changeLoopFor(BB, L); - } - - /// changeTopLevelLoop - Replace the specified loop in the top-level loops - /// list with the indicated loop. - inline void changeTopLevelLoop(Loop *OldLoop, Loop *NewLoop) { - LI.changeTopLevelLoop(OldLoop, NewLoop); - } - - /// addTopLevelLoop - This adds the specified loop to the collection of - /// top-level loops. - inline void addTopLevelLoop(Loop *New) { - LI.addTopLevelLoop(New); - } - - /// removeBlock - This method completely removes BB from all data structures, - /// including all of the Loop objects it is nested in and our mapping from - /// BasicBlocks to loops. - void removeBlock(BasicBlock *BB) { - LI.removeBlock(BB); - } - - void releaseMemory() { LI.releaseMemory(); } + // Most of the public interface is provided via LoopInfoBase. /// updateUnloop - Update LoopInfo after removing the last backedge from a /// loop--now the "unloop". This updates the loop forest and parent loops for diff --git a/llvm/include/llvm/Analysis/LoopInfoImpl.h b/llvm/include/llvm/Analysis/LoopInfoImpl.h index 948be0f..3321f39 100644 --- a/llvm/include/llvm/Analysis/LoopInfoImpl.h +++ b/llvm/include/llvm/Analysis/LoopInfoImpl.h @@ -545,6 +545,25 @@ void LoopInfoBase::print(raw_ostream &OS) const { #endif } +template +void LoopInfoBase::verify() const { + DenseSet Loops; + for (iterator I = begin(), E = end(); I != E; ++I) { + assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); + (*I)->verifyLoopNest(&Loops); + } + + // Verify that blocks are mapped to valid loops. +#ifndef NDEBUG + for (auto &Entry : BBMap) { + BlockT *BB = Entry.first; + LoopT *L = Entry.second; + assert(Loops.count(L) && "orphaned loop"); + assert(L->contains(BB) && "orphaned block"); + } +#endif +} + } // End llvm namespace #endif diff --git a/llvm/lib/Analysis/LoopInfo.cpp b/llvm/lib/Analysis/LoopInfo.cpp index ec3fed5..5fde485 100644 --- a/llvm/lib/Analysis/LoopInfo.cpp +++ b/llvm/lib/Analysis/LoopInfo.cpp @@ -617,7 +617,8 @@ void LoopInfo::updateUnloop(Loop *Unloop) { if (!Unloop->getParentLoop()) { // Since BBLoop had no parent, Unloop blocks are no longer in a loop. for (Loop::block_iterator I = Unloop->block_begin(), - E = Unloop->block_end(); I != E; ++I) { + E = Unloop->block_end(); + I != E; ++I) { // Don't reparent blocks in subloops. if (getLoopFor(*I) != Unloop) @@ -625,21 +626,21 @@ void LoopInfo::updateUnloop(Loop *Unloop) { // Blocks no longer have a parent but are still referenced by Unloop until // the Unloop object is deleted. - LI.changeLoopFor(*I, nullptr); + changeLoopFor(*I, nullptr); } // Remove the loop from the top-level LoopInfo object. - for (LoopInfo::iterator I = LI.begin();; ++I) { - assert(I != LI.end() && "Couldn't find loop"); + for (iterator I = begin();; ++I) { + assert(I != end() && "Couldn't find loop"); if (*I == Unloop) { - LI.removeLoop(I); + removeLoop(I); break; } } // Move all of the subloops to the top-level. while (!Unloop->empty()) - LI.addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end()))); + addTopLevelLoop(Unloop->removeChildLoop(std::prev(Unloop->end()))); return; } @@ -679,7 +680,7 @@ INITIALIZE_PASS_END(LoopInfoWrapperPass, "loops", "Natural Loop Information", bool LoopInfoWrapperPass::runOnFunction(Function &) { releaseMemory(); - LI.getBase().Analyze(getAnalysis().getDomTree()); + LI.Analyze(getAnalysis().getDomTree()); return false; } @@ -689,24 +690,8 @@ void LoopInfoWrapperPass::verifyAnalysis() const { // -verify-loop-info option can enable this. In order to perform some // checking by default, LoopPass has been taught to call verifyLoop manually // during loop pass sequences. - - if (!VerifyLoopInfo) return; - - DenseSet Loops; - for (LoopInfo::iterator I = LI.begin(), E = LI.end(); I != E; ++I) { - assert(!(*I)->getParentLoop() && "Top-level loop has a parent!"); - (*I)->verifyLoopNest(&Loops); - } - - // Verify that blocks are mapped to valid loops. -#ifndef NDEBUG - for (auto &Entry : LI.LI.BBMap) { - BasicBlock *BB = Entry.first; - Loop *L = Entry.second; - assert(Loops.count(L) && "orphaned loop"); - assert(L->contains(BB) && "orphaned block"); - } -#endif + if (VerifyLoopInfo) + LI.verify(); } void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { @@ -715,7 +700,7 @@ void LoopInfoWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { } void LoopInfoWrapperPass::print(raw_ostream &OS, const Module *) const { - LI.LI.print(OS); + LI.print(OS); } //===----------------------------------------------------------------------===// diff --git a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp index 2918881..53115a9 100644 --- a/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ b/llvm/lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -982,9 +982,8 @@ void LoopConstrainer::addToParentLoopIfNeeded(IteratorTy Begin, if (!ParentLoop) return; - auto &LoopInfoBase = OriginalLoopInfo.getBase(); for (; Begin != End; Begin++) - ParentLoop->addBasicBlockToLoop(*Begin, LoopInfoBase); + ParentLoop->addBasicBlockToLoop(*Begin, OriginalLoopInfo); } bool LoopConstrainer::run() { diff --git a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp index ed1ccdb..eb684d4 100644 --- a/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp +++ b/llvm/lib/Transforms/Scalar/LoopUnswitch.cpp @@ -675,7 +675,7 @@ static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, for (Loop::block_iterator I = L->block_begin(), E = L->block_end(); I != E; ++I) if (LI->getLoopFor(*I) == L) - New->addBasicBlockToLoop(cast(VM[*I]), LI->getBase()); + New->addBasicBlockToLoop(cast(VM[*I]), *LI); // Add all of the subloops to the new loop. for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) @@ -850,14 +850,14 @@ void LoopUnswitch::UnswitchNontrivialCondition(Value *LIC, Constant *Val, if (ParentLoop) { // Make sure to add the cloned preheader and exit blocks to the parent loop // as well. - ParentLoop->addBasicBlockToLoop(NewBlocks[0], LI->getBase()); + ParentLoop->addBasicBlockToLoop(NewBlocks[0], *LI); } for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) { BasicBlock *NewExit = cast(VMap[ExitBlocks[i]]); // The new exit block should be in the same loop as the old one. if (Loop *ExitBBLoop = LI->getLoopFor(ExitBlocks[i])) - ExitBBLoop->addBasicBlockToLoop(NewExit, LI->getBase()); + ExitBBLoop->addBasicBlockToLoop(NewExit, *LI); assert(NewExit->getTerminator()->getNumSuccessors() == 1 && "Exit block should have been split to have one successor!"); diff --git a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp index a6c9d9a..867e433 100644 --- a/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp +++ b/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp @@ -293,7 +293,7 @@ BasicBlock *llvm::SplitBlock(BasicBlock *Old, Instruction *SplitPt, Pass *P) { if (auto *LIWP = P->getAnalysisIfAvailable()) { LoopInfo &LI = LIWP->getLoopInfo(); if (Loop *L = LI.getLoopFor(Old)) - L->addBasicBlockToLoop(New, LI.getBase()); + L->addBasicBlockToLoop(New, LI); } if (DominatorTreeWrapperPass *DTWP = @@ -385,9 +385,9 @@ static void UpdateAnalysisInformation(BasicBlock *OldBB, BasicBlock *NewBB, } if (InnermostPredLoop) - InnermostPredLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + InnermostPredLoop->addBasicBlockToLoop(NewBB, *LI); } else { - L->addBasicBlockToLoop(NewBB, LI->getBase()); + L->addBasicBlockToLoop(NewBB, *LI); if (SplitMakesNewLoopHeader) L->moveToHeader(NewBB); } diff --git a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp index 736a4a8..0e4c704 100644 --- a/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp +++ b/llvm/lib/Transforms/Utils/BreakCriticalEdges.cpp @@ -269,13 +269,13 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, if (Loop *DestLoop = LI->getLoopFor(DestBB)) { if (TIL == DestLoop) { // Both in the same loop, the NewBB joins loop. - DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + DestLoop->addBasicBlockToLoop(NewBB, *LI); } else if (TIL->contains(DestLoop)) { // Edge from an outer loop to an inner loop. Add to the outer loop. - TIL->addBasicBlockToLoop(NewBB, LI->getBase()); + TIL->addBasicBlockToLoop(NewBB, *LI); } else if (DestLoop->contains(TIL)) { // Edge from an inner loop to an outer loop. Add to the outer loop. - DestLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + DestLoop->addBasicBlockToLoop(NewBB, *LI); } else { // Edge from two loops with no containment relation. Because these // are natural loops, we know that the destination block must be the @@ -284,7 +284,7 @@ BasicBlock *llvm::SplitCriticalEdge(TerminatorInst *TI, unsigned SuccNum, assert(DestLoop->getHeader() == DestBB && "Should not create irreducible loops!"); if (Loop *P = DestLoop->getParentLoop()) - P->addBasicBlockToLoop(NewBB, LI->getBase()); + P->addBasicBlockToLoop(NewBB, *LI); } } // If TIBB is in a loop and DestBB is outside of that loop, we may need diff --git a/llvm/lib/Transforms/Utils/LoopSimplify.cpp b/llvm/lib/Transforms/Utils/LoopSimplify.cpp index cb79686..4c7b5c6 100644 --- a/llvm/lib/Transforms/Utils/LoopSimplify.cpp +++ b/llvm/lib/Transforms/Utils/LoopSimplify.cpp @@ -460,7 +460,7 @@ static BasicBlock *insertUniqueBackedgeBlock(Loop *L, BasicBlock *Preheader, // Update Loop Information - we know that this block is now in the current // loop and all parent loops. - L->addBasicBlockToLoop(BEBlock, LI->getBase()); + L->addBasicBlockToLoop(BEBlock, *LI); // Update dominator information DT->splitBlock(BEBlock); diff --git a/llvm/lib/Transforms/Utils/LoopUnroll.cpp b/llvm/lib/Transforms/Utils/LoopUnroll.cpp index 5745920..dbd032e 100644 --- a/llvm/lib/Transforms/Utils/LoopUnroll.cpp +++ b/llvm/lib/Transforms/Utils/LoopUnroll.cpp @@ -311,7 +311,7 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, // Tell LI about New. if (*BB == Header) { assert(LI->getLoopFor(*BB) == L && "Header should not be in a sub-loop"); - L->addBasicBlockToLoop(New, LI->getBase()); + L->addBasicBlockToLoop(New, *LI); } else { // Figure out which loop New is in. const Loop *OldLoop = LI->getLoopFor(*BB); @@ -333,7 +333,7 @@ bool llvm::UnrollLoop(Loop *L, unsigned Count, unsigned TripCount, if (SE) SE->forgetLoop(OldLoop); } - NewLoop->addBasicBlockToLoop(New, LI->getBase()); + NewLoop->addBasicBlockToLoop(New, *LI); } if (*BB == Header) diff --git a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp index f12cd61..c7ea283 100644 --- a/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp +++ b/llvm/lib/Transforms/Utils/LoopUnrollRuntime.cpp @@ -160,9 +160,9 @@ static void CloneLoopBlocks(Loop *L, Value *NewIter, const bool UnrollProlog, NewBlocks.push_back(NewBB); if (NewLoop) - NewLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + NewLoop->addBasicBlockToLoop(NewBB, *LI); else if (ParentLoop) - ParentLoop->addBasicBlockToLoop(NewBB, LI->getBase()); + ParentLoop->addBasicBlockToLoop(NewBB, *LI); VMap[*BB] = NewBB; if (Header == *BB) { diff --git a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp index 9842cdf..13880cb 100644 --- a/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp +++ b/llvm/lib/Transforms/Vectorize/LoopVectorize.cpp @@ -1991,7 +1991,7 @@ void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, bool IfPredic Cmp = Builder.CreateICmp(ICmpInst::ICMP_EQ, Cmp, ConstantInt::get(Cmp->getType(), 1)); CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store"); LoopVectorBody.push_back(CondBlock); - VectorLp->addBasicBlockToLoop(CondBlock, LI->getBase()); + VectorLp->addBasicBlockToLoop(CondBlock, *LI); // Update Builder with newly created basic block. Builder.SetInsertPoint(InsertPt); } @@ -2020,7 +2020,7 @@ void InnerLoopVectorizer::scalarizeInstruction(Instruction *Instr, bool IfPredic if (IfPredicateStore) { BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else"); LoopVectorBody.push_back(NewIfBlock); - VectorLp->addBasicBlockToLoop(NewIfBlock, LI->getBase()); + VectorLp->addBasicBlockToLoop(NewIfBlock, *LI); Builder.SetInsertPoint(InsertPt); Instruction *OldBr = IfBlock->getTerminator(); BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr); @@ -2298,13 +2298,13 @@ void InnerLoopVectorizer::createEmptyLoop() { // before calling any utilities such as SCEV that require valid LoopInfo. if (ParentLoop) { ParentLoop->addChildLoop(Lp); - ParentLoop->addBasicBlockToLoop(ScalarPH, LI->getBase()); - ParentLoop->addBasicBlockToLoop(VectorPH, LI->getBase()); - ParentLoop->addBasicBlockToLoop(MiddleBlock, LI->getBase()); + ParentLoop->addBasicBlockToLoop(ScalarPH, *LI); + ParentLoop->addBasicBlockToLoop(VectorPH, *LI); + ParentLoop->addBasicBlockToLoop(MiddleBlock, *LI); } else { LI->addTopLevelLoop(Lp); } - Lp->addBasicBlockToLoop(VecBody, LI->getBase()); + Lp->addBasicBlockToLoop(VecBody, *LI); // Use this IR builder to create the loop instructions (Phi, Br, Cmp) // inside the loop. @@ -2359,7 +2359,7 @@ void InnerLoopVectorizer::createEmptyLoop() { BasicBlock *CheckBlock = LastBypassBlock->splitBasicBlock(PastOverflowCheck, "overflow.checked"); if (ParentLoop) - ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase()); + ParentLoop->addBasicBlockToLoop(CheckBlock, *LI); LoopBypassBlocks.push_back(CheckBlock); Instruction *OldTerm = LastBypassBlock->getTerminator(); BranchInst::Create(ScalarPH, CheckBlock, CheckBCOverflow, OldTerm); @@ -2379,7 +2379,7 @@ void InnerLoopVectorizer::createEmptyLoop() { BasicBlock *CheckBlock = LastBypassBlock->splitBasicBlock(FirstCheckInst, "vector.stridecheck"); if (ParentLoop) - ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase()); + ParentLoop->addBasicBlockToLoop(CheckBlock, *LI); LoopBypassBlocks.push_back(CheckBlock); // Replace the branch into the memory check block with a conditional branch @@ -2403,7 +2403,7 @@ void InnerLoopVectorizer::createEmptyLoop() { BasicBlock *CheckBlock = LastBypassBlock->splitBasicBlock(MemRuntimeCheck, "vector.memcheck"); if (ParentLoop) - ParentLoop->addBasicBlockToLoop(CheckBlock, LI->getBase()); + ParentLoop->addBasicBlockToLoop(CheckBlock, *LI); LoopBypassBlocks.push_back(CheckBlock); // Replace the branch into the memory check block with a conditional branch @@ -6258,7 +6258,7 @@ void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr, ConstantInt::get(Cond[Part]->getType(), 1)); CondBlock = IfBlock->splitBasicBlock(InsertPt, "cond.store"); LoopVectorBody.push_back(CondBlock); - VectorLp->addBasicBlockToLoop(CondBlock, LI->getBase()); + VectorLp->addBasicBlockToLoop(CondBlock, *LI); // Update Builder with newly created basic block. Builder.SetInsertPoint(InsertPt); } @@ -6284,7 +6284,7 @@ void InnerLoopUnroller::scalarizeInstruction(Instruction *Instr, if (IfPredicateStore) { BasicBlock *NewIfBlock = CondBlock->splitBasicBlock(InsertPt, "else"); LoopVectorBody.push_back(NewIfBlock); - VectorLp->addBasicBlockToLoop(NewIfBlock, LI->getBase()); + VectorLp->addBasicBlockToLoop(NewIfBlock, *LI); Builder.SetInsertPoint(InsertPt); Instruction *OldBr = IfBlock->getTerminator(); BranchInst::Create(CondBlock, NewIfBlock, Cmp, OldBr); -- 2.7.4