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

625

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

168

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 {
 
   /// Indicator that this loop is no longer a valid loop.
   bool IsInvalid = false;
 
   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:
   /// 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.
   bool isInvalid() const { return IsInvalid; }
 
   /// 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;
     }
public:
   /// 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(); }
+  static void clearLoop(LoopT &L) { L.~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/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>;
 

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); });
 
   // 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/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/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()};
+        LoopInfo &LI = AR.LI;
+        Loop *NewLoops[] = {LI.AllocateLoop(), LI.AllocateLoop(),
+                            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);