[LoopUtils] Updated deleteDeadLoop() to handle loop nest.

[Whitney]

Summary

Updated deleteDeadLoop() to handle loop nest.

[Whitney]

Removed unnecessary includes.

[bmahjour]

The deleteDeadLoop function when called on the outer loop will effectively remove the subloops from the CFG too (make them unreachable). Maybe we should change deleteDeadLoop to also take the subloops into account when updating the analysis passed to it. Then we shouldn't need a separate function to delete loop nests.

[Whitney]

Didn't notice Bardia already posted something similar.

Actually we can do a small modification in deleteDeadLoop to have it works for loop nest, by changing the last line from LI->erase(L); to erasing all loops in L. Would that way be more preferable?

[Whitney]

What does everyone think? Is deleteDeadLoop() intensionally work for innermost loops? Is adding deleteDeadLoopNest() or modifying deleteDeadLoop() to work for loops with any depth preferred?

[Meinersbur]

I slightly tend towards @bmahjour's suggestion, for convenience of the user.

Since deleteDeadLoop also deletes all its interior already, what is missing to be correct for nested loops as well? Even SCEV->forgetLoop seems to considered nested loops.

[Whitney]

what is missing to be correct for nested loops as well?

The only think I can see missing is LI->erase(L), which relink the subloops of L to the parent of L, or change them to top level loops if L has no parent.

[Meinersbur]

llvm/lib/Transforms/Utils/LoopUtils.cpp

686

[remark] Assigning a lambda to a std::function introduces a lot of overhead. However, auto doesn't work for calling itself recursively. https://laptrinhx.com/recursive-lambdas-713741980/ has a nice technique though.

687

[serious] LoopInfo::erase is designed to modify the parent's subloop list. At least, it will remove Subloop from L's subloop list, hence invalidating the iterator we are currently iterating over.

691

[suggestion] Could you add a comment such as "Recursively remove all subloops. Calling LoopInfo::erase only on the dead loop only moves its subloops to the dead loop's parent".

LoopInfo::erase does a loot of work to move the association of the subloop blocks to the parent. Since we know that the loop is dead, I wonder whether it is worth introducing a variant that just removes the dead loop from its parent's child list.

llvm/unittests/Transforms/Utils/LoopUtilsTest.cpp

29

[style] No almost always auto

[Whitney]

Use removeChildLoop() and removeLoop() instead of erase().

[Whitney]

Change use of auto.

[Meinersbur]

LGTM

[Whitney]

To address memory leak.

[Whitney]

Need to destroy the loop after removing from LI.

llvm/include/llvm/Transforms/Utils/LoopUtils.h

 /// TargetLibraryInfo, Loop, AliasSet information for all instructions of the
 /// loop and loop safety information as arguments. Diagnostics is emitted via \p
 /// ORE. It returns changed status.
 bool hoistRegion(DomTreeNode *, AliasAnalysis *, LoopInfo *, DominatorTree *,
                  TargetLibraryInfo *, Loop *, AliasSetTracker *,
                  MemorySSAUpdater *, ScalarEvolution *, ICFLoopSafetyInfo *,
                  SinkAndHoistLICMFlags &, OptimizationRemarkEmitter *);
 
+/// This function deletes dead loop nest. The requirement for this function is
+/// the same as deleteDeadLoop(), except deleteDeadLoopNest() allow \p L to have
+/// dead inner loops. This also updates the relevant analysis information in
+/// \p DT, \p SE, and \p LI if pointers to those are provided.
+void deleteDeadLoopNest(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
+                        LoopInfo *LI);
+
 /// This function deletes dead loops. The caller of this function needs to
 /// guarantee that the loop is infact dead.
 /// The function requires a bunch or prerequisites to be present:
 ///   - The loop needs to be in LCSSA form
 ///   - The loop needs to have a Preheader
 ///   - A unique dedicated exit block must exist
 ///
 /// This also updates the relevant analysis information in \p DT, \p SE, and \p
 /// LI if pointers to those are provided.
 /// It also updates the loop PM if an updater struct is provided.
-
 void deleteDeadLoop(Loop *L, DominatorTree *DT, ScalarEvolution *SE,
                     LoopInfo *LI);
 
 /// Try to promote memory values to scalars by sinking stores out of
 /// the loop and moving loads to before the loop.  We do this by looping over
 /// the stores in the loop, looking for stores to Must pointers which are
 /// loop invariant. It takes a set of must-alias values, Loop exit blocks
 /// vector, loop exit blocks insertion point vector, PredIteratorCache,

llvm/lib/Transforms/Utils/LoopUtils.cpp

llvm::collectChildrenInLoop(DomTreeNode *N, const Loop *CurLoop) {
 
   for (size_t I = 0; I < Worklist.size(); I++)
     for (DomTreeNode *Child : Worklist[I]->getChildren())
       AddRegionToWorklist(Child);
 
   return Worklist;
 }
 
+void llvm::deleteDeadLoopNest(Loop *L, DominatorTree *DT = nullptr,
+                              ScalarEvolution *SE = nullptr,
+                              LoopInfo *LI = nullptr) {
+  for (Loop *SubLoop : *L)
+    deleteDeadLoopNest(SubLoop, DT, SE, LI);
+
+  assert(L->getSubLoops().empty() && "Expecting to be innermost loop");
+  deleteDeadLoop(L, DT, SE, LI);
+}
+
 void llvm::deleteDeadLoop(Loop *L, DominatorTree *DT = nullptr,
                           ScalarEvolution *SE = nullptr,
                           LoopInfo *LI = nullptr) {
   assert((!DT || L->isLCSSAForm(*DT)) && "Expected LCSSA!");
   auto *Preheader = L->getLoopPreheader();
   assert(Preheader && "Preheader should exist!");
 
   // Now that we know the removal is safe, remove the loop by changing the
if (LI) {
     // otherwise our loop iterators won't work.
 
     SmallPtrSet<BasicBlock *, 8> blocks;
     blocks.insert(L->block_begin(), L->block_end());
     for (BasicBlock *BB : blocks)
       LI->removeBlock(BB);
 
     // The last step is to update LoopInfo now that we've eliminated this loop.
     LI->erase(L);
   }
 }
 
 Optional<unsigned> llvm::getLoopEstimatedTripCount(Loop *L) {
   // Support loops with an exiting latch and other existing exists only
   // deoptimize.
 
   // Get the branch weights for the loop's backedge.
   BasicBlock *Latch = L->getLoopLatch();
   if (!Latch)
     return None;
   BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
   if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))

llvm/unittests/Transforms/Utils/CMakeLists.txt

add_llvm_unittest(UtilsTests
   ASanStackFrameLayoutTest.cpp
   BasicBlockUtilsTest.cpp
   CloningTest.cpp
   CodeExtractorTest.cpp
   CodeMoverUtilsTest.cpp
   FunctionComparatorTest.cpp
   IntegerDivisionTest.cpp
   LocalTest.cpp
+  LoopUtilsTest.cpp
   SizeOptsTest.cpp
   SSAUpdaterBulkTest.cpp
   UnrollLoopTest.cpp
   ValueMapperTest.cpp
   VFABIUtils.cpp
   )

llvm/unittests/Transforms/Utils/LoopUtilsTest.cpp

+//===- LoopUtilsTest.cpp - Unit tests for LoopUtils -----------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/Transforms/Utils/LoopUtils.h"
+#include "llvm/Analysis/AssumptionCache.h"
+#include "llvm/Analysis/DependenceAnalysis.h"
+#include "llvm/Analysis/LoopInfo.h"
+#include "llvm/Analysis/PostDominators.h"
+#include "llvm/Analysis/ScalarEvolutionExpander.h"
+#include "llvm/AsmParser/Parser.h"
+#include "llvm/IR/Dominators.h"
+#include "llvm/IR/LLVMContext.h"
+#include "llvm/Support/SourceMgr.h"
+#include "gtest/gtest.h"
+
+using namespace llvm;
+
+static std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
+  SMDiagnostic Err;
+  std::unique_ptr<Module> Mod = parseAssemblyString(IR, Err, C);
+  if (!Mod)
+    Err.print("LoopUtilsTests", errs());
+  return Mod;
+}
+
+static void run(Module &M, StringRef FuncName,
+                function_ref<void(Function &F, DominatorTree &DT,
+                                  ScalarEvolution &SE, LoopInfo &LI)>
+                    Test) {
+  auto *F = M.getFunction(FuncName);
+  DominatorTree DT(*F);
+  TargetLibraryInfoImpl TLII;
+  TargetLibraryInfo TLI(TLII);
+  AssumptionCache AC(*F);
+  LoopInfo LI(DT);
+  ScalarEvolution SE(*F, TLI, AC, DT, LI);
+  Test(*F, DT, SE, LI);
+}
+
+TEST(LoopUtils, DeleteDeadLoopNest) {
+  LLVMContext C;
+  std::unique_ptr<Module> M =
+      parseIR(C, "define void @foo() {\n"
+                 "entry:\n"
+                 "  br label %for.i\n"
+                 "for.i:\n"
+                 "  %i = phi i64 [ 0, %entry ], [ %inc.i, %for.i.latch ]\n"
+                 "  br label %for.j\n"
+                 "for.j:\n"
+                 "  %j = phi i64 [ 0, %for.i ], [ %inc.j, %for.j ]\n"
+                 "  %inc.j = add nsw i64 %j, 1\n"
+                 "  %cmp.j = icmp slt i64 %inc.j, 100\n"
+                 "  br i1 %cmp.j, label %for.j, label %for.k.preheader\n"
+                 "for.k.preheader:\n"
+                 "  br label %for.k\n"
+                 "for.k:\n"
+                 "  %k = phi i64 [ %inc.k, %for.k ], [ 0, %for.k.preheader ]\n"
+                 "  %inc.k = add nsw i64 %k, 1\n"
+                 "  %cmp.k = icmp slt i64 %inc.k, 100\n"
+                 "  br i1 %cmp.k, label %for.k, label %for.i.latch\n"
+                 "for.i.latch:\n"
+                 "  %inc.i = add nsw i64 %i, 1\n"
+                 "  %cmp.i = icmp slt i64 %inc.i, 100\n"
+                 "  br i1 %cmp.i, label %for.i, label %for.end\n"
+                 "for.end:\n"
+                 "  ret void\n"
+                 "}\n");
+
+  run(*M, "foo",
+      [&](Function &F, DominatorTree &DT, ScalarEvolution &SE, LoopInfo &LI) {
+        assert(LI.begin() != LI.end() && "Expecting loops in function F");
+        Loop *L = *LI.begin();
+        assert(L && L->getName() == "for.i" && "Expecting loop for.i");
+
+        deleteDeadLoopNest(L, &DT, &SE, &LI);
+
+        assert(DT.verify(DominatorTree::VerificationLevel::Fast) &&
+               "Expecting valid dominator tree");
+        LI.verify(DT);
+        assert(LI.begin() == LI.end() &&
+               "Expecting no loops left in function F");
+        SE.verify();
+
+        Function::iterator FI = F.begin();
+        BasicBlock *Entry = &*(FI++);
+        assert(Entry->getName() == "entry" && "Expecting BasicBlock entry");
+        const BranchInst *BI = dyn_cast<BranchInst>(Entry->getTerminator());
+        assert(BI && "Expecting valid branch instruction");
+        EXPECT_EQ(BI->getNumSuccessors(), (unsigned)1);
+        EXPECT_EQ(BI->getSuccessor(0)->getName(), "for.end");
+      });
+}