Index: include/llvm/Analysis/LoopInfo.h =================================================================== --- include/llvm/Analysis/LoopInfo.h +++ include/llvm/Analysis/LoopInfo.h @@ -46,7 +46,9 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/PassManager.h" #include "llvm/Pass.h" +#include "llvm/Support/Allocator.h" #include +#include namespace llvm { @@ -74,25 +76,16 @@ SmallPtrSet DenseBlockSet; +#if !defined(NDEBUG) || !LLVM_ENABLE_ABI_BREAKING_CHECKS /// Indicator that this loop is no longer a valid loop. bool IsInvalid = false; +#endif LoopBase(const LoopBase &) = delete; const LoopBase & operator=(const LoopBase &) = delete; - void clear() { - IsInvalid = true; - SubLoops.clear(); - Blocks.clear(); - DenseBlockSet.clear(); - ParentLoop = nullptr; - } - public: - /// This creates an empty loop. - LoopBase() : ParentLoop(nullptr) {} - /// 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. @@ -172,8 +165,15 @@ return Blocks.size(); } - /// Return true if this loop is no longer valid. +#ifndef NDEBUG + /// Return true if this loop is no longer valid. The only valid use of this + /// helper is "assert(L.isInvalid())" or equivalent, since IsValid is set to + /// false by the destructor. In other words, if this accessor returns false, + /// 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 false indicates a + /// programmer error. bool isInvalid() const { return IsInvalid; } +#endif /// True if terminator in the block can branch to another block that is /// outside of the current loop. @@ -370,6 +370,10 @@ protected: friend class LoopInfoBase; + + /// This creates an empty loop. + LoopBase() : ParentLoop(nullptr) {} + explicit LoopBase(BlockT *BB) : ParentLoop(nullptr) { Blocks.push_back(BB); DenseBlockSet.insert(BB); @@ -386,7 +390,13 @@ // non-public. ~LoopBase() { for (auto *SubLoop : SubLoops) - delete SubLoop; + SubLoop->~LoopT(); + + IsInvalid = true; + SubLoops.clear(); + Blocks.clear(); + DenseBlockSet.clear(); + ParentLoop = nullptr; } }; @@ -422,8 +432,6 @@ explicit operator bool() const { return Start && End; } }; - Loop() {} - /// Return true if the specified value is loop invariant. bool isLoopInvariant(const Value *V) const; @@ -543,6 +551,8 @@ } private: + Loop() = default; + friend class LoopInfoBase; friend class LoopBase; explicit Loop(BasicBlock *BB) : LoopBase(BB) {} @@ -558,7 +568,7 @@ // BBMap - Mapping of basic blocks to the inner most loop they occur in DenseMap BBMap; std::vector TopLevelLoops; - std::vector RemovedLoops; + BumpPtrAllocator LoopAllocator; friend class LoopBase; friend class LoopInfo; @@ -572,7 +582,8 @@ 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(); } @@ -580,8 +591,10 @@ 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; } @@ -590,11 +603,14 @@ BBMap.clear(); for (auto *L : TopLevelLoops) - delete L; + L->~LoopT(); TopLevelLoops.clear(); - for (auto *L : RemovedLoops) - delete L; - RemovedLoops.clear(); + LoopAllocator.Reset(); + } + + template LoopT *AllocateLoop(ArgsTy &&... Args) { + LoopT *Storage = LoopAllocator.Allocate(); + return new (Storage) LoopT(std::forward(Args)...); } /// iterator/begin/end - The interface to the top-level loops in the current @@ -717,7 +733,15 @@ void verify(const DominatorTreeBase &DomTree) const; protected: - static void clearLoop(LoopT &L) { L.clear(); } + // Calls the destructor for \p L but keeps the memory for \p L around so that + // the pointer value does not get re-used. + 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, sizeof(LoopT)); + } }; // Implementation in LoopInfoImpl.h Index: include/llvm/Analysis/LoopInfoImpl.h =================================================================== --- include/llvm/Analysis/LoopInfoImpl.h +++ include/llvm/Analysis/LoopInfoImpl.h @@ -498,7 +498,7 @@ } // Perform a backward CFG traversal to discover and map blocks in this loop. if (!Backedges.empty()) { - LoopT *L = new LoopT(Header); + LoopT *L = AllocateLoop(Header); discoverAndMapSubloop(L, ArrayRef(Backedges), this, DomTree); } } Index: include/llvm/Analysis/LoopPass.h =================================================================== --- include/llvm/Analysis/LoopPass.h +++ include/llvm/Analysis/LoopPass.h @@ -129,6 +129,9 @@ // Add a new loop into the loop queue. void addLoop(Loop &L); + // Mark \p L as deleted. + void markLoopAsDeleted(Loop &L); + //===--------------------------------------------------------------------===// /// SimpleAnalysis - Provides simple interface to update analysis info /// maintained by various passes. Note, if required this interface can @@ -152,6 +155,7 @@ std::deque LQ; LoopInfo *LI; Loop *CurrentLoop; + bool CurrentLoopDeleted; }; // This pass is required by the LCSSA transformation. It is used inside Index: include/llvm/CodeGen/MachineLoopInfo.h =================================================================== --- include/llvm/CodeGen/MachineLoopInfo.h +++ include/llvm/CodeGen/MachineLoopInfo.h @@ -44,8 +44,6 @@ class MachineLoop : public LoopBase { public: - MachineLoop(); - /// Return the "top" block in the loop, which is the first block in the linear /// layout, ignoring any parts of the loop not contiguous with the part that /// contains the header. @@ -76,6 +74,8 @@ explicit MachineLoop(MachineBasicBlock *MBB) : LoopBase(MBB) {} + + MachineLoop() = default; }; // Implementation in LoopInfoImpl.h Index: include/llvm/Support/Allocator.h =================================================================== --- include/llvm/Support/Allocator.h +++ include/llvm/Support/Allocator.h @@ -269,6 +269,9 @@ // Pull in base class overloads. using AllocatorBase::Allocate; + // Bump pointer allocators are expected to never free their storage; and + // clients expect pointers to remain valid for non-dereferencing uses even + // after deallocation. void Deallocate(const void *Ptr, size_t Size) { __asan_poison_memory_region(Ptr, Size); } Index: lib/Analysis/LoopInfo.cpp =================================================================== --- lib/Analysis/LoopInfo.cpp +++ lib/Analysis/LoopInfo.cpp @@ -620,10 +620,8 @@ void LoopInfo::erase(Loop *Unloop) { assert(!Unloop->isInvalid() && "Loop has already been erased!"); - RemovedLoops.push_back(Unloop); - auto InvalidateOnExit = - make_scope_exit([&]() { BaseT::clearLoop(*Unloop); }); + auto InvalidateOnExit = make_scope_exit([&]() { destroy(Unloop); }); // First handle the special case of no parent loop to simplify the algorithm. if (!Unloop->getParentLoop()) { Index: lib/Analysis/LoopPass.cpp =================================================================== --- lib/Analysis/LoopPass.cpp +++ lib/Analysis/LoopPass.cpp @@ -140,6 +140,13 @@ Info.setPreservesAll(); } +void LPPassManager::markLoopAsDeleted(Loop &L) { + assert((&L == CurrentLoop || CurrentLoop->contains(&L)) && + "Must not delete loop outside the current loop tree!"); + if (&L == CurrentLoop) + CurrentLoopDeleted = true; +} + /// run - Execute all of the passes scheduled for execution. Keep track of /// whether any of the passes modifies the function, and if so, return true. bool LPPassManager::runOnFunction(Function &F) { @@ -176,7 +183,7 @@ // Walk Loops while (!LQ.empty()) { - bool LoopWasDeleted = false; + CurrentLoopDeleted = false; CurrentLoop = LQ.back(); // Run all passes on the current Loop. @@ -195,13 +202,12 @@ Changed |= P->runOnLoop(CurrentLoop, *this); } - LoopWasDeleted = CurrentLoop->isInvalid(); if (Changed) dumpPassInfo(P, MODIFICATION_MSG, ON_LOOP_MSG, CurrentLoop->getName()); dumpPreservedSet(P); - if (LoopWasDeleted) { + if (CurrentLoopDeleted) { // Notify passes that the loop is being deleted. deleteSimpleAnalysisLoop(CurrentLoop); } else { @@ -229,11 +235,12 @@ removeNotPreservedAnalysis(P); recordAvailableAnalysis(P); - removeDeadPasses(P, LoopWasDeleted ? "" - : CurrentLoop->getHeader()->getName(), + removeDeadPasses(P, + CurrentLoopDeleted ? "" + : CurrentLoop->getHeader()->getName(), ON_LOOP_MSG); - if (LoopWasDeleted) + if (CurrentLoopDeleted) // Do not run other passes on this loop. break; } @@ -241,7 +248,7 @@ // If the loop was deleted, release all the loop passes. This frees up // some memory, and avoids trouble with the pass manager trying to call // verifyAnalysis on them. - if (LoopWasDeleted) { + if (CurrentLoopDeleted) { for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { Pass *P = getContainedPass(Index); freePass(P, "", ON_LOOP_MSG); @@ -359,4 +366,3 @@ char LCSSAVerificationPass::ID = 0; INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier", false, false) - Index: lib/Transforms/IPO/LoopExtractor.cpp =================================================================== --- lib/Transforms/IPO/LoopExtractor.cpp +++ lib/Transforms/IPO/LoopExtractor.cpp @@ -80,7 +80,7 @@ // Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); } -bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &) { +bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) { if (skipLoop(L)) return false; @@ -143,6 +143,7 @@ Changed = true; // After extraction, the loop is replaced by a function call, so // we shouldn't try to run any more loop passes on it. + LPM.markLoopAsDeleted(*L); LI.erase(L); } ++NumExtracted; Index: lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp =================================================================== --- lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp +++ lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp @@ -1386,7 +1386,7 @@ Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent, ValueToValueMapTy &VM) { - Loop &New = *new Loop(); + Loop &New = *LI.AllocateLoop(); if (Parent) Parent->addChildLoop(&New); else Index: lib/Transforms/Scalar/LoopDeletion.cpp =================================================================== --- lib/Transforms/Scalar/LoopDeletion.cpp +++ lib/Transforms/Scalar/LoopDeletion.cpp @@ -384,7 +384,7 @@ Pass *llvm::createLoopDeletionPass() { return new LoopDeletionLegacyPass(); } -bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &) { +bool LoopDeletionLegacyPass::runOnLoop(Loop *L, LPPassManager &LPM) { if (skipLoop(L)) return false; DominatorTree &DT = getAnalysis().getDomTree(); @@ -393,5 +393,11 @@ DEBUG(dbgs() << "Analyzing Loop for deletion: "); DEBUG(L->dump()); - return deleteLoopIfDead(L, DT, SE, LI) != LoopDeletionResult::Unmodified; + + LoopDeletionResult Result = deleteLoopIfDead(L, DT, SE, LI); + + if (Result == LoopDeletionResult::Deleted) + LPM.markLoopAsDeleted(*L); + + return Result != LoopDeletionResult::Unmodified; } Index: lib/Transforms/Scalar/LoopUnrollPass.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnrollPass.cpp +++ lib/Transforms/Scalar/LoopUnrollPass.cpp @@ -1087,7 +1087,7 @@ Optional ProvidedUpperBound; Optional ProvidedAllowPeeling; - bool runOnLoop(Loop *L, LPPassManager &) override { + bool runOnLoop(Loop *L, LPPassManager &LPM) override { if (skipLoop(L)) return false; @@ -1105,11 +1105,15 @@ OptimizationRemarkEmitter ORE(&F); bool PreserveLCSSA = mustPreserveAnalysisID(LCSSAID); - return tryToUnrollLoop(L, DT, LI, SE, TTI, AC, ORE, PreserveLCSSA, OptLevel, - ProvidedCount, ProvidedThreshold, - ProvidedAllowPartial, ProvidedRuntime, - ProvidedUpperBound, ProvidedAllowPeeling) != - LoopUnrollResult::Unmodified; + LoopUnrollResult Result = tryToUnrollLoop( + L, DT, LI, SE, TTI, AC, ORE, PreserveLCSSA, OptLevel, ProvidedCount, + ProvidedThreshold, ProvidedAllowPartial, ProvidedRuntime, + ProvidedUpperBound, ProvidedAllowPeeling); + + if (Result == LoopUnrollResult::FullyUnrolled) + LPM.markLoopAsDeleted(*L); + + return Result != LoopUnrollResult::Unmodified; } /// This transformation requires natural loop information & requires that Index: lib/Transforms/Scalar/LoopUnswitch.cpp =================================================================== --- lib/Transforms/Scalar/LoopUnswitch.cpp +++ lib/Transforms/Scalar/LoopUnswitch.cpp @@ -881,7 +881,7 @@ /// mapping the blocks with the specified map. static Loop *CloneLoop(Loop *L, Loop *PL, ValueToValueMapTy &VM, LoopInfo *LI, LPPassManager *LPM) { - Loop &New = *new Loop(); + Loop &New = *LI->AllocateLoop(); if (PL) PL->addChildLoop(&New); else Index: lib/Transforms/Utils/CloneFunction.cpp =================================================================== --- lib/Transforms/Utils/CloneFunction.cpp +++ lib/Transforms/Utils/CloneFunction.cpp @@ -747,7 +747,7 @@ Function *F = OrigLoop->getHeader()->getParent(); Loop *ParentLoop = OrigLoop->getParentLoop(); - Loop *NewLoop = new Loop(); + Loop *NewLoop = LI->AllocateLoop(); if (ParentLoop) ParentLoop->addChildLoop(NewLoop); else Index: lib/Transforms/Utils/LoopSimplify.cpp =================================================================== --- lib/Transforms/Utils/LoopSimplify.cpp +++ lib/Transforms/Utils/LoopSimplify.cpp @@ -258,7 +258,7 @@ placeSplitBlockCarefully(NewBB, OuterLoopPreds, L); // Create the new outer loop. - Loop *NewOuter = new Loop(); + Loop *NewOuter = LI->AllocateLoop(); // Change the parent loop to use the outer loop as its child now. if (Loop *Parent = L->getParentLoop()) Index: lib/Transforms/Utils/LoopUnroll.cpp =================================================================== --- lib/Transforms/Utils/LoopUnroll.cpp +++ lib/Transforms/Utils/LoopUnroll.cpp @@ -200,7 +200,7 @@ assert(OriginalBB == OldLoop->getHeader() && "Header should be first in RPO"); - NewLoop = new Loop(); + NewLoop = LI->AllocateLoop(); Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop()); if (NewLoopParent) Index: lib/Transforms/Vectorize/LoopVectorize.cpp =================================================================== --- lib/Transforms/Vectorize/LoopVectorize.cpp +++ lib/Transforms/Vectorize/LoopVectorize.cpp @@ -3456,7 +3456,7 @@ MiddleBlock->splitBasicBlock(MiddleBlock->getTerminator(), "scalar.ph"); // Create and register the new vector loop. - Loop *Lp = new Loop(); + Loop *Lp = LI->AllocateLoop(); Loop *ParentLoop = OrigLoop->getParentLoop(); // Insert the new loop into the loop nest and register the new basic blocks Index: unittests/Transforms/Scalar/LoopPassManagerTest.cpp =================================================================== --- unittests/Transforms/Scalar/LoopPassManagerTest.cpp +++ unittests/Transforms/Scalar/LoopPassManagerTest.cpp @@ -946,7 +946,7 @@ .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { - auto *NewLoop = new Loop(); + auto *NewLoop = AR.LI.AllocateLoop(); L.addChildLoop(NewLoop); auto *NewLoop010PHBB = BasicBlock::Create(Context, "loop.0.1.0.ph", &F, &Loop02PHBB); @@ -992,7 +992,7 @@ .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { - auto *NewLoop = new Loop(); + auto *NewLoop = AR.LI.AllocateLoop(); L.addChildLoop(NewLoop); auto *NewLoop011PHBB = BasicBlock::Create(Context, "loop.0.1.1.ph", &F, NewLoop01LatchBB); auto *NewLoop011BB = BasicBlock::Create(Context, "loop.0.1.1", &F, NewLoop01LatchBB); @@ -1139,7 +1139,7 @@ .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { - auto *NewLoop = new Loop(); + auto *NewLoop = AR.LI.AllocateLoop(); L.getParentLoop()->addChildLoop(NewLoop); auto *NewLoop01PHBB = BasicBlock::Create(Context, "loop.0.1.ph", &F, &Loop02PHBB); auto *NewLoop01BB = BasicBlock::Create(Context, "loop.0.1", &F, &Loop02PHBB); @@ -1181,7 +1181,8 @@ .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { - Loop *NewLoops[] = {new Loop(), new Loop(), new Loop()}; + Loop *NewLoops[] = {AR.LI.AllocateLoop(), AR.LI.AllocateLoop(), + AR.LI.AllocateLoop()}; L.getParentLoop()->addChildLoop(NewLoops[0]); L.getParentLoop()->addChildLoop(NewLoops[1]); NewLoops[1]->addChildLoop(NewLoops[2]); @@ -1260,7 +1261,7 @@ .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { - auto *NewLoop = new Loop(); + auto *NewLoop = AR.LI.AllocateLoop(); AR.LI.addTopLevelLoop(NewLoop); auto *NewLoop1PHBB = BasicBlock::Create(Context, "loop.1.ph", &F, &Loop2BB); auto *NewLoop1BB = BasicBlock::Create(Context, "loop.1", &F, &Loop2BB); @@ -1491,7 +1492,7 @@ EraseLoop(L, Loop02PHBB, AR, Updater); // Now insert a new sibling loop. - auto *NewSibling = new Loop; + auto *NewSibling = AR.LI.AllocateLoop(); ParentL->addChildLoop(NewSibling); NewLoop03PHBB = BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB);