[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

676

[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.

677

[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.

681

[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

28

[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/lib/Transforms/Utils/LoopUtils.cpp

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.
+    std::function<void(Loop *)> EraseLoopNest = [&](Loop *L) {
+      for (Loop *SubLoop : *L)
+        EraseLoopNest(SubLoop);
+
+      assert(L->getSubLoops().empty() && "Expecting to be innermost loop");
       LI->erase(L);
+    };
+    EraseLoopNest(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.

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/AsmParser/Parser.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");
+
+        deleteDeadLoop(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");
+      });
+}