Use a BumpPtrAllocator for Loop objects

[sanjoy]

Summary

And now that we no longer have to explicitly free() the Loop instances, we can
(with more ease) use the destructor of LoopBase to do what LoopBase::clear() was
doing.

[sanjoy]

lib/Analysis/LoopInfo.cpp

624

I should also be "freeing" the loop objects here (which for the bump ptr allocator would mean poisoning them).

[sanjoy]

• Update: Use Deallocate

[sanjoy]

There is a problem with this patch -- the legacy pass manager checks if a loop is valid or not by querying isInvalid, which is incorrect; since we call the destructor for loop objects to mark them as "invalid" calling isInvalid for possibly invalid loop objects has UB. We already have this UB in User::operator delete though, and so given that and that the legacy pass manager is going away at some point, perhaps this is okay? Alternatively, I could add a mechanism on the legacy loop pass manager that lets passes denote loop objects to have been deleted (by remembering the pointers in a set) and use that to decide if a Loop object is valid or not (and with that, I can guard isInvalid with #ifndef NDEBUG).

The asserts are using isInvalid correctly, as far as I can tell; they should never have UB in an execution that uses the loop objects correctly.

[chandlerc]

In D38201#880392, @sanjoy wrote:

There is a problem with this patch -- the legacy pass manager checks if a loop is valid or not by querying isInvalid, which is incorrect; since we call the destructor for loop objects to mark them as "invalid" calling isInvalid for possibly invalid loop objects has UB. We already have this UB in User::operator delete though, and so given that and that the legacy pass manager is going away at some point, perhaps this is okay? Alternatively, I could add a mechanism on the legacy loop pass manager that lets passes denote loop objects to have been deleted (by remembering the pointers in a set) and use that to decide if a Loop object is valid or not (and with that, I can guard isInvalid with #ifndef NDEBUG).

Sadly, I think this would be problematic. I think it'll trip ASan's use-after-scope or use-after-lifetime checks.... =/ But maybe there is a way around that. Or maybe just implement the solution you suggest. Dunno, but definitely worth checking.

The asserts are using isInvalid correctly, as far as I can tell; they should never have UB in an execution that uses the loop objects correctly.

Cool.

[sanjoy]

In D38201#880864, @chandlerc wrote:

In D38201#880392, @sanjoy wrote:

There is a problem with this patch -- the legacy pass manager checks if a loop is valid or not by querying isInvalid, which is incorrect; since we call the destructor for loop objects to mark them as "invalid" calling isInvalid for possibly invalid loop objects has UB. We already have this UB in User::operator delete though, and so given that and that the legacy pass manager is going away at some point, perhaps this is okay? Alternatively, I could add a mechanism on the legacy loop pass manager that lets passes denote loop objects to have been deleted (by remembering the pointers in a set) and use that to decide if a Loop object is valid or not (and with that, I can guard isInvalid with #ifndef NDEBUG).

Sadly, I think this would be problematic. I think it'll trip ASan's use-after-scope or use-after-lifetime checks.... =/ But maybe there is a way around that. Or maybe just implement the solution you suggest. Dunno, but definitely worth checking.

We already do this for User instances -- we read from fields in the User object to be destroyed in its operator delete, after the destructors have run. However, two wrongs don't make a right so I'll first try to see if I can fix this in the old pass manager.

The asserts are using isInvalid correctly, as far as I can tell; they should never have UB in an execution that uses the loop objects correctly.

Cool.

[chandlerc]

In D38201#881716, @sanjoy wrote:

In D38201#880864, @chandlerc wrote:

In D38201#880392, @sanjoy wrote:

There is a problem with this patch -- the legacy pass manager checks if a loop is valid or not by querying isInvalid, which is incorrect; since we call the destructor for loop objects to mark them as "invalid" calling isInvalid for possibly invalid loop objects has UB. We already have this UB in User::operator delete though, and so given that and that the legacy pass manager is going away at some point, perhaps this is okay? Alternatively, I could add a mechanism on the legacy loop pass manager that lets passes denote loop objects to have been deleted (by remembering the pointers in a set) and use that to decide if a Loop object is valid or not (and with that, I can guard isInvalid with #ifndef NDEBUG).

Sadly, I think this would be problematic. I think it'll trip ASan's use-after-scope or use-after-lifetime checks.... =/ But maybe there is a way around that. Or maybe just implement the solution you suggest. Dunno, but definitely worth checking.

We already do this for User instances -- we read from fields in the User object to be destroyed in its operator delete, after the destructors have run. However, two wrongs don't make a right so I'll first try to see if I can fix this in the old pass manager.

Cool...

However, to be clear, I'm not trying to argue any theorectical purity here. Mostly, I'm worried that the operator delete may be somewhat less problematic *in practice*. If you have carefully verified that this causes no problems in practice with lifetime-markers and sanitizers as they are currently implemented.

[sanjoy]

With this update, we no longer have the UB in the legacy PM

[sanjoy]

Remove the last remaining use of isInvalid() (I had missed this one but it
showed up when building in release mode).

[chandlerc]

LGTM!

include/llvm/Analysis/LoopInfo.h

170

The comment says IsValid, but the code uses IsInvalid...

include/llvm/Analysis/LoopInfo.h

 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/IR/Instruction.h"
 #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 {
 
 class DominatorTree;
 class LoopInfo;
 class Loop;
 class MDNode;
 class PHINode;
template <class BlockT, class LoopT> class LoopBase {
   // 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;
 
   SmallPtrSet<const BlockT *, 8> 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<BlockT, LoopT> &) = delete;
   const LoopBase<BlockT, LoopT> &
   operator=(const LoopBase<BlockT, LoopT> &) = 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.
   unsigned getLoopDepth() const {
     assert(!isInvalid() && "Loop not in a valid state!");
     unsigned D = 1;
     for (const LoopT *CurLoop = ParentLoop; CurLoop;
          CurLoop = CurLoop->ParentLoop)
public:
 
   /// 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();
   }
 
-  /// 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.
   bool isLoopExiting(const BlockT *BB) const {
     assert(!isInvalid() && "Loop not in a valid state!");
     for (const auto &Succ : children<const BlockT *>(BB)) {
       if (!contains(Succ))
         return true;
#endif
   /// Verify loop structure of this loop and all nested loops.
   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)
-      delete SubLoop;
+      SubLoop->~LoopT();
+
+    IsInvalid = true;
+    SubLoops.clear();
+    Blocks.clear();
+    DenseBlockSet.clear();
+    ParentLoop = nullptr;
   }
 };
 
 template <class BlockT, class LoopT>
 raw_ostream &operator<<(raw_ostream &OS, const LoopBase<BlockT, LoopT> &Loop) {
   Loop.print(OS);
   return OS;
 }
public:
     const DebugLoc &getStart() const { return Start; }
     const DebugLoc &getEnd() const { return End; }
 
     /// \brief Check for null.
     ///
     explicit operator bool() const { return Start && End; }
   };
 
-  Loop() {}
-
   /// Return true if the specified value is loop invariant.
   bool isLoopInvariant(const Value *V) const;
 
   /// Return true if all the operands of the specified instruction are loop
   /// invariant.
   bool hasLoopInvariantOperands(const Instruction *I) const;
 
   /// If the given value is an instruction inside of the loop and it can be
if (isInvalid())
       return "<invalidated loop>";
     if (BasicBlock *Header = getHeader())
       if (Header->hasName())
         return Header->getName();
     return "<unnamed loop>";
   }
 
 private:
+  Loop() = default;
+
   friend class LoopInfoBase<BasicBlock, Loop>;
   friend class LoopBase<BasicBlock, Loop>;
   explicit Loop(BasicBlock *BB) : LoopBase<BasicBlock, Loop>(BB) {}
   ~Loop() = default;
 };
 
 //===----------------------------------------------------------------------===//
 /// This class builds and contains all of the top-level loop
 /// structures in the specified function.
 ///
 
 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() { 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();
   }
   LoopInfoBase &operator=(LoopInfoBase &&RHS) {
     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;
   }
 
   void releaseMemory() {
     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;
public:
   void analyze(const DominatorTreeBase<BlockT, false> &DomTree);
 
   // Debugging
   void print(raw_ostream &OS) const;
 
   void verify(const DominatorTreeBase<BlockT, false> &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
 extern template class LoopInfoBase<BasicBlock, Loop>;
 
 class LoopInfo : public LoopInfoBase<BasicBlock, Loop> {
   typedef LoopInfoBase<BasicBlock, Loop> BaseT;
 

include/llvm/Analysis/LoopInfoImpl.h

for (const auto Backedge : children<Inverse<BlockT *>>(Header)) {
       // If Header dominates predBB, this is a new loop. Collect the backedges.
       if (DomTree.dominates(Header, Backedge) &&
           DomTree.isReachableFromEntry(Backedge)) {
         Backedges.push_back(Backedge);
       }
     }
     // 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<BlockT *>(Backedges), this, DomTree);
     }
   }
   // Perform a single forward CFG traversal to populate block and subloop
   // vectors for all loops.
   PopulateLoopsDFS<BlockT, LoopT> DFS(this);
   DFS.traverse(DomRoot->getBlock());
 }

include/llvm/Analysis/LoopPass.h

public:
   PassManagerType getPassManagerType() const override {
     return PMT_LoopPassManager;
   }
 
 public:
   // 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
   /// be extracted into a separate abstract class but it would require
   /// additional use of multiple inheritance in Pass class hierarchy, something
   /// we are trying to avoid.
 
   /// cloneBasicBlockSimpleAnalysis - Invoke cloneBasicBlockAnalysis hook for
   /// all passes that implement simple analysis interface.
   void cloneBasicBlockSimpleAnalysis(BasicBlock *From, BasicBlock *To, Loop *L);
 
   /// deleteSimpleAnalysisValue - Invoke deleteAnalysisValue hook for all passes
   /// that implement simple analysis interface.
   void deleteSimpleAnalysisValue(Value *V, Loop *L);
 
   /// Invoke deleteAnalysisLoop hook for all passes that implement simple
   /// analysis interface.
   void deleteSimpleAnalysisLoop(Loop *L);
 
 private:
   std::deque<Loop *> LQ;
   LoopInfo *LI;
   Loop *CurrentLoop;
+  bool CurrentLoopDeleted;
 };
 
 // This pass is required by the LCSSA transformation. It is used inside
 // LPPassManager to check if current pass preserves LCSSA form, and if it does
 // pass manager calls lcssa verification for the current loop.
 struct LCSSAVerificationPass : public FunctionPass {
   static char ID;
   LCSSAVerificationPass() : FunctionPass(ID) {

include/llvm/CodeGen/MachineLoopInfo.h

 namespace llvm {
 
 // Implementation in LoopInfoImpl.h
 class MachineLoop;
 extern template class LoopBase<MachineBasicBlock, MachineLoop>;
 
 class MachineLoop : public LoopBase<MachineBasicBlock, MachineLoop> {
 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.
   MachineBasicBlock *getTopBlock();
 
   /// Return the "bottom" block in the loop, which is the last block in the
   /// linear layout, ignoring any parts of the loop not contiguous with the part
   /// that contains the header.
public:
 
   void dump() const;
 
 private:
   friend class LoopInfoBase<MachineBasicBlock, MachineLoop>;
 
   explicit MachineLoop(MachineBasicBlock *MBB)
     : LoopBase<MachineBasicBlock, MachineLoop>(MBB) {}
+
+  MachineLoop() = default;
 };
 
 // Implementation in LoopInfoImpl.h
 extern template class LoopInfoBase<MachineBasicBlock, MachineLoop>;
 
 class MachineLoopInfo : public MachineFunctionPass {
   friend class LoopBase<MachineBasicBlock, MachineLoop>;
 

include/llvm/Support/Allocator.h

#endif
     __msan_allocated_memory(AlignedPtr, Size);
     __asan_unpoison_memory_region(AlignedPtr, Size);
     return AlignedPtr;
   }
 
   // Pull in base class overloads.
   using AllocatorBase<BumpPtrAllocatorImpl>::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);
   }
 
   // Pull in base class overloads.
   using AllocatorBase<BumpPtrAllocatorImpl>::Deallocate;
 
   size_t GetNumSlabs() const { return Slabs.size() + CustomSizedSlabs.size(); }

lib/Analysis/LoopInfo.cpp

bool LoopInfo::invalidate(Function &F, const PreservedAnalyses &PA,
   // CFG have been preserved.
   auto PAC = PA.getChecker<LoopAnalysis>();
   return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>() ||
            PAC.preservedSet<CFGAnalyses>());
 }
 
 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()) {
     // 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) {
 

lib/Analysis/LoopPass.cpp

 void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const {
   // LPPassManager needs LoopInfo. In the long term LoopInfo class will
   // become part of LPPassManager.
   Info.addRequired<LoopInfoWrapperPass>();
   Info.addRequired<DominatorTreeWrapperPass>();
   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) {
   auto &LIWP = getAnalysis<LoopInfoWrapperPass>();
   LI = &LIWP.getLoopInfo();
   DominatorTree *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   bool Changed = false;
 
for (Loop *L : LQ) {
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       LoopPass *P = getContainedPass(Index);
       Changed |= P->doInitialization(L, *this);
     }
   }
 
   // Walk Loops
   while (!LQ.empty()) {
-    bool LoopWasDeleted = false;
+    CurrentLoopDeleted = false;
     CurrentLoop = LQ.back();
 
     // Run all passes on the current Loop.
     for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
       LoopPass *P = getContainedPass(Index);
 
       dumpPassInfo(P, EXECUTION_MSG, ON_LOOP_MSG,
                    CurrentLoop->getHeader()->getName());
       dumpRequiredSet(P);
 
       initializeAnalysisImpl(P);
 
       {
         PassManagerPrettyStackEntry X(P, *CurrentLoop->getHeader());
         TimeRegion PassTimer(getPassTimer(P));
 
         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 {
         // Manually check that this loop is still healthy. This is done
         // instead of relying on LoopInfo::verifyLoop since LoopInfo
         // is a function pass and it's really expensive to verify every
         // loop in the function every time. That level of checking can be
         // enabled with the -verify-loop-info option.
for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
         // Then call the regular verifyAnalysis functions.
         verifyPreservedAnalysis(P);
 
         F.getContext().yield();
       }
 
       removeNotPreservedAnalysis(P);
       recordAvailableAnalysis(P);
-      removeDeadPasses(P, LoopWasDeleted ? "<deleted>"
+      removeDeadPasses(P,
+                       CurrentLoopDeleted ? "<deleted>"
                                           : CurrentLoop->getHeader()->getName(),
                        ON_LOOP_MSG);
 
-      if (LoopWasDeleted)
+      if (CurrentLoopDeleted)
         // Do not run other passes on this loop.
         break;
     }
 
     // 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, "<deleted>", ON_LOOP_MSG);
       }
     }
 
     // Pop the loop from queue after running all passes.
     LQ.pop_back();
if (F->hasFnAttribute(Attribute::OptimizeNone)) {
     return true;
   }
   return false;
 }
 
 char LCSSAVerificationPass::ID = 0;
 INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier",
                 false, false)
-

lib/Transforms/IPO/LoopExtractor.cpp

 INITIALIZE_PASS(SingleLoopExtractor, "loop-extract-single",
                 "Extract at most one loop into a new function", false, false)
 
 // createLoopExtractorPass - This pass extracts all natural loops from the
 // program into a function if it can.
 //
 Pass *llvm::createLoopExtractorPass() { return new LoopExtractor(); }
 
-bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &) {
+bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (skipLoop(L))
     return false;
 
   // Only visit top-level loops.
   if (L->getParentLoop())
     return false;
 
   // If LoopSimplify form is not available, stay out of trouble.
bool LoopExtractor::runOnLoop(Loop *L, LPPassManager &LPM) {
   if (ShouldExtractLoop) {
     if (NumLoops == 0) return Changed;
     --NumLoops;
     CodeExtractor Extractor(DT, *L);
     if (Extractor.extractCodeRegion() != nullptr) {
       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;
   }
 
   return Changed;
 }
 

lib/Transforms/Scalar/InductiveRangeCheckElimination.cpp

if (!ParentLoop)
     return;
 
   for (BasicBlock *BB : BBs)
     ParentLoop->addBasicBlockToLoop(BB, LI);
 }
 
 Loop *LoopConstrainer::createClonedLoopStructure(Loop *Original, Loop *Parent,
                                                  ValueToValueMapTy &VM) {
-  Loop &New = *new Loop();
+  Loop &New = *LI.AllocateLoop();
   if (Parent)
     Parent->addChildLoop(&New);
   else
     LI.addTopLevelLoop(&New);
   LPM.addLoop(New);
 
   // Add all of the blocks in Original to the new loop.
   for (auto *BB : Original->blocks())

lib/Transforms/Scalar/LoopDeletion.cpp

 INITIALIZE_PASS_BEGIN(LoopDeletionLegacyPass, "loop-deletion",
                       "Delete dead loops", false, false)
 INITIALIZE_PASS_DEPENDENCY(LoopPass)
 INITIALIZE_PASS_END(LoopDeletionLegacyPass, "loop-deletion",
                     "Delete dead loops", false, false)
 
 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<DominatorTreeWrapperPass>().getDomTree();
   ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
   LoopInfo &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
   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;
 }

lib/Transforms/Scalar/LoopUnrollPass.cpp

public:
   int OptLevel;
   Optional<unsigned> ProvidedCount;
   Optional<unsigned> ProvidedThreshold;
   Optional<bool> ProvidedAllowPartial;
   Optional<bool> ProvidedRuntime;
   Optional<bool> ProvidedUpperBound;
   Optional<bool> ProvidedAllowPeeling;
 
-  bool runOnLoop(Loop *L, LPPassManager &) override {
+  bool runOnLoop(Loop *L, LPPassManager &LPM) override {
     if (skipLoop(L))
       return false;
 
     Function &F = *L->getHeader()->getParent();
 
     auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     LoopInfo *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     ScalarEvolution &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
     const TargetTransformInfo &TTI =
         getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
     auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
     // For the old PM, we can't use OptimizationRemarkEmitter as an analysis
     // pass.  Function analyses need to be preserved across loop transformations
     // but ORE cannot be preserved (see comment before the pass definition).
     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
   /// loop preheaders be inserted into the CFG...
   ///
   void getAnalysisUsage(AnalysisUsage &AU) const override {
     AU.addRequired<AssumptionCacheTracker>();
     AU.addRequired<TargetTransformInfoWrapperPass>();

lib/Transforms/Scalar/LoopUnswitch.cpp

bool LoopUnswitch::UnswitchIfProfitable(Value *LoopCond, Constant *Val,
   UnswitchNontrivialCondition(LoopCond, Val, currentLoop, TI);
   return true;
 }
 
 /// Recursively clone the specified loop and all of its children,
 /// 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
     LI->addTopLevelLoop(&New);
   LPM->addLoop(New);
 
   // Add all of the blocks in L to the new loop.
   for (Loop::block_iterator I = L->block_begin(), E = L->block_end();

lib/Transforms/Utils/CloneFunction.cpp

Loop *llvm::cloneLoopWithPreheader(BasicBlock *Before, BasicBlock *LoopDomBB,
                                    const Twine &NameSuffix, LoopInfo *LI,
                                    DominatorTree *DT,
                                    SmallVectorImpl<BasicBlock *> &Blocks) {
   assert(OrigLoop->getSubLoops().empty() && 
          "Loop to be cloned cannot have inner loop");
   Function *F = OrigLoop->getHeader()->getParent();
   Loop *ParentLoop = OrigLoop->getParentLoop();
 
-  Loop *NewLoop = new Loop();
+  Loop *NewLoop = LI->AllocateLoop();
   if (ParentLoop)
     ParentLoop->addChildLoop(NewLoop);
   else
     LI->addTopLevelLoop(NewLoop);
 
   BasicBlock *OrigPH = OrigLoop->getLoopPreheader();
   assert(OrigPH && "No preheader");
   BasicBlock *NewPH = CloneBasicBlock(OrigPH, VMap, NameSuffix, F);

lib/Transforms/Utils/LoopSimplify.cpp

static Loop *separateNestedLoop(Loop *L, BasicBlock *Preheader,
   BasicBlock *NewBB = SplitBlockPredecessors(Header, OuterLoopPreds, ".outer",
                                              DT, LI, PreserveLCSSA);
 
   // Make sure that NewBB is put someplace intelligent, which doesn't mess up
   // code layout too horribly.
   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())
     Parent->replaceChildLoopWith(L, NewOuter);
   else
     LI->changeTopLevelLoop(L, NewOuter);
 
   // L is now a subloop of our outer loop.

lib/Transforms/Utils/LoopUnroll.cpp

const Loop* llvm::addClonedBlockToLoopInfo(BasicBlock *OriginalBB,
   assert(OldLoop && "Should (at least) be in the loop being unrolled!");
 
   Loop *&NewLoop = NewLoops[OldLoop];
   if (!NewLoop) {
     // Found a new sub-loop.
     assert(OriginalBB == OldLoop->getHeader() &&
            "Header should be first in RPO");
 
-    NewLoop = new Loop();
+    NewLoop = LI->AllocateLoop();
     Loop *NewLoopParent = NewLoops.lookup(OldLoop->getParentLoop());
 
     if (NewLoopParent)
       NewLoopParent->addChildLoop(NewLoop);
     else
       LI->addTopLevelLoop(NewLoop);
 
     NewLoop->addBasicBlockToLoop(ClonedBB, *LI);

lib/Transforms/Vectorize/LoopVectorize.cpp

BasicBlock *InnerLoopVectorizer::createVectorizedLoopSkeleton() {
   BasicBlock *VecBody =
       VectorPH->splitBasicBlock(VectorPH->getTerminator(), "vector.body");
   BasicBlock *MiddleBlock =
       VecBody->splitBasicBlock(VecBody->getTerminator(), "middle.block");
   BasicBlock *ScalarPH =
       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
   // before calling any utilities such as SCEV that require valid LoopInfo.
   if (ParentLoop) {
     ParentLoop->addChildLoop(Lp);
     ParentLoop->addBasicBlockToLoop(ScalarPH, *LI);
     ParentLoop->addBasicBlockToLoop(MiddleBlock, *LI);

unittests/Transforms/Scalar/LoopPassManagerTest.cpp

TEST_F(LoopPassManagerTest, LoopChildInsertion) {
 
   // When running over the middle loop, the second run inserts two new child
   // loops, inserting them and itself into the worklist.
   BasicBlock *NewLoop010BB, *NewLoop01LatchBB;
   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
       .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);
         NewLoop010BB =
             BasicBlock::Create(Context, "loop.0.1.0", &F, &Loop02PHBB);
         NewLoop01LatchBB =
             BasicBlock::Create(Context, "loop.0.1.latch", &F, &Loop02PHBB);
         Loop01BB.getTerminator()->replaceUsesOfWith(&Loop01BB, NewLoop010PHBB);
TEST_F(LoopPassManagerTest, LoopChildInsertion) {
 
   // In the second run over the middle loop after we've visited the new child,
   // we add another child to check that we can repeatedly add children, and add
   // children to a loop that already has children.
   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
       .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);
         NewLoop010BB->getTerminator()->replaceUsesOfWith(NewLoop01LatchBB,
                                                          NewLoop011PHBB);
         BranchInst::Create(NewLoop011BB, NewLoop011PHBB);
         CreateCondBr(NewLoop01LatchBB, NewLoop011BB, "cond.0.1.1",
                      NewLoop011BB);
EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
       .WillOnce(Invoke(getLoopAnalysisResult));
   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
 
   // On the second run, we insert a sibling loop.
   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
       .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);
         BranchInst::Create(NewLoop01BB, NewLoop01PHBB);
         CreateCondBr(&Loop02PHBB, NewLoop01BB, "cond.0.1", NewLoop01BB);
         Loop00BB.getTerminator()->replaceUsesOfWith(&Loop02PHBB, NewLoop01PHBB);
         AR.DT.addNewBlock(NewLoop01PHBB, &Loop00BB);
         auto *NewDTNode = AR.DT.addNewBlock(NewLoop01BB, NewLoop01PHBB);
EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
       .WillOnce(Invoke(getLoopAnalysisResult));
   // Next, on the third pass run on the last inner loop we add more new
   // siblings, more than one, and one with nested child loops. By doing this at
   // the end we make sure that edge case works well.
   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
       .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]);
         auto *NewLoop03PHBB =
             BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB);
         auto *NewLoop03BB =
             BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB);
         auto *NewLoop04PHBB =
TEST_F(LoopPassManagerTest, LoopPeerInsertion) {
   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
       .WillOnce(Invoke(getLoopAnalysisResult));
   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
   // On the second pass, we add sibling loops which become new top-level loops.
   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
       .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);
         BranchInst::Create(NewLoop1BB, NewLoop1PHBB);
         CreateCondBr(&Loop2PHBB, NewLoop1BB, "cond.1", NewLoop1BB);
         Loop0BB.getTerminator()->replaceUsesOfWith(&Loop2PHBB, NewLoop1PHBB);
         AR.DT.addNewBlock(NewLoop1PHBB, &Loop0BB);
         auto *NewDTNode = AR.DT.addNewBlock(NewLoop1BB, NewLoop1PHBB);
EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
             AR.SE.forgetLoop(*L.begin());
             EraseLoop(**L.begin(), Loop020PHBB, AR, Updater);
 
             auto *ParentL = L.getParentLoop();
             AR.SE.forgetLoop(&L);
             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);
             auto *NewLoop03BB =
                 BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB);
             BranchInst::Create(NewLoop03BB, NewLoop03PHBB);
             auto *Cond = new LoadInst(&Ptr, "cond.0.3", /*isVolatile*/ true,
                                       NewLoop03BB);