[PM] Teach LoopUnroll to update the LPM infrastructure as it unrolls loops.

[chandlerc]

Summary

We do this by reconstructing the newly added loops after the unroll
completes to avoid threading pass manager details through all the mess
of the unrolling infrastructure.

I've enabled some extra assertions in the LPM to try and catch issues
here and enabled a bunch of unroller tests to try and make sure this is
sane.

Currently, I'm manually running loop-simplify when needed. That should
go away once it is folded into the LPM infrastructure.

[chandlerc]

Add some detailed comments about what is happening here. After a long
discussion with Mikhail Zolotukhin on IRC, we're both pretty sure this is in
fact the correct logic, but it is sufficiently non-obvious to be worth walking
the reader through with some precision.

Also, I've added a test case that *specifically* triggers the interesting cases
here and checks that we visit the expected loops after both full and partial
unrolling.

I tried to add a test case for loop peeling but currently we don't have any
support for peeling an outer loop.

[chandlerc]

Rebase and ping.

[chandlerc]

Adapt to not run loop-simplify unnecessarily now that it is run automatically.

[chandlerc]

::sigh:: *Actually* remove the unnecessary loop-simplify runs.

[davide]

lib/Transforms/Scalar/LoopUnrollPass.cpp

116–117

This is a little verbose (maybe part of this can be moved to a comment? (up to you, I don't feel strong about it).

1147–1149

#ifdef NDEBUG, maybe ?

[chandlerc]

Thanks, both addressed!

lib/Transforms/Scalar/LoopUnrollPass.cpp

116–117

Nah, it was wordy. Thanks for the suggestion. I both tightened it up and moved part of it to a comment.

[chandlerc]

Update the patch based on review feedback.

[mzolotukhin]

LGTM with one question inline.

Michael

lib/Transforms/Scalar/LoopPassManager.cpp

47–49

AFAIR, we have lcssa-verification pass now (see rL285394). Aren't we redoing it here?

I don't know if we want to keep that pass with the new pass manager, but still we probably want to have one or the other.

[chandlerc]

Thanks, landing!

lib/Transforms/Scalar/LoopPassManager.cpp

47–49

I feel like a non-pass solution is more clean with the new PM, but I'm completely open to alternatives. The reason why is because the loop PM is now *directly* forming and maintaining LCSSA rather than relying on cross-pass dependencies. That (IMO) makes it much more reasonable to have the PM itself *enforce* LCSSA.

But maybe there are reasons to prefer the pass approach I don't see, so I'm happy to revisit as necessary.

lib/Transforms/Scalar/LoopPassManager.cpp

for (auto &Pass : Passes) {
     PreservedAnalyses PassPA = Pass->run(L, AM, AR, U);
 
     // If the loop was deleted, abort the run and return to the outer walk.
     if (U.skipCurrentLoop()) {
       PA.intersect(std::move(PassPA));
       break;
     }
 
+#ifndef NDEBUG
+    // Verify the loop structure and LCSSA form before visiting the loop.
+    L.verifyLoop();
+    assert(L.isRecursivelyLCSSAForm(AR.DT, AR.LI) &&
+           "Loops must remain in LCSSA form!");
+#endif
+
     // Update the analysis manager as each pass runs and potentially
     // invalidates analyses.
     AM.invalidate(L, PassPA);
 
     // Finally, we intersect the final preserved analyses to compute the
     // aggregate preserved set for this pass manager.
     PA.intersect(std::move(PassPA));
 

lib/Transforms/Scalar/LoopUnrollPass.cpp

static cl::opt<unsigned> FlatLoopTripCountThreshold(
     cl::desc("If the runtime tripcount for the loop is lower than the "
              "threshold, the loop is considered as flat and will be less "
              "aggressively unrolled."));
 
 static cl::opt<bool>
     UnrollAllowPeeling("unroll-allow-peeling", cl::Hidden,
                        cl::desc("Allows loops to be peeled when the dynamic "
                                 "trip count is known to be low."));
 
 /// A magic value for use with the Threshold parameter to indicate
 /// that the loop unroll should be performed regardless of how much
 /// code expansion would result.
 static const unsigned NoThreshold = UINT_MAX;
 
 /// Gather the various unrolling parameters based on the defaults, compiler
 /// flags, TTI overrides and user specified parameters.
 static TargetTransformInfo::UnrollingPreferences gatherUnrollingPreferences(
     Loop *L, const TargetTransformInfo &TTI, Optional<unsigned> UserThreshold,

 }
 
 Pass *llvm::createSimpleLoopUnrollPass() {
   return llvm::createLoopUnrollPass(-1, -1, 0, 0, 0);
 }
 
 PreservedAnalyses LoopUnrollPass::run(Loop &L, LoopAnalysisManager &AM,
                                       LoopStandardAnalysisResults &AR,
-                                      LPMUpdater &) {
+                                      LPMUpdater &Updater) {
   const auto &FAM =
       AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR).getManager();
   Function *F = L.getHeader()->getParent();
 
   auto *ORE = FAM.getCachedResult<OptimizationRemarkEmitterAnalysis>(*F);
   // FIXME: This should probably be optional rather than required.
   if (!ORE)
     report_fatal_error("LoopUnrollPass: OptimizationRemarkEmitterAnalysis not "
                        "cached at a higher level");
 
+  // Keep track of the previous loop structure so we can identify new loops
+  // created by unrolling.
+  Loop *ParentL = L.getParentLoop();
+  SmallPtrSet<Loop *, 4> OldLoops;
+  if (ParentL)
+    OldLoops.insert(ParentL->begin(), ParentL->end());
+  else
+    OldLoops.insert(AR.LI.begin(), AR.LI.end());
+
   bool Changed = tryToUnrollLoop(&L, AR.DT, &AR.LI, &AR.SE, AR.TTI, AR.AC, *ORE,
                                  /*PreserveLCSSA*/ true, ProvidedCount,
                                  ProvidedThreshold, ProvidedAllowPartial,
                                  ProvidedRuntime, ProvidedUpperBound);
   if (!Changed)
     return PreservedAnalyses::all();
 
+  // The parent must not be damaged by unrolling!
+  if (ParentL)
+    ParentL->verifyLoop();
+
+  // We need to update the loop pass manager, so we look to see if our loop
+  // still exists and enque any new loops into the worklist.
+  bool IsCurrentLoopValid = false;
+  SmallVector<Loop *, 4> SibLoops;
+  if (ParentL)
+    SibLoops.append(ParentL->begin(), ParentL->end());
+  else
+    SibLoops.append(AR.LI.begin(), AR.LI.end());
+  erase_if(SibLoops, [&](Loop *SibLoop) {
+    if (SibLoop == &L) {
+      IsCurrentLoopValid = true;
+      return true;
+    }
+
+    // Otherwise erase the loop from the list if it was in the old loops.
+    return OldLoops.count(SibLoop) != 0;
+  });
+  Updater.addSiblingLoops(SibLoops);
+  if (!IsCurrentLoopValid)
+    Updater.markLoopAsDeleted(L);
+
   return getLoopPassPreservedAnalyses();
 }

test/Transforms/LoopUnroll/basic.ll

 ; RUN: opt < %s -loop-unroll -S | FileCheck %s
+; RUN: opt < %s -passes='require<opt-remark-emit>,loop(unroll)' -S | FileCheck %s
 
 
 ; This should not unroll since the address of the loop header is taken.
 
 ; CHECK-LABEL: @test1(
 ; CHECK: store i8* blockaddress(@test1, %l1), i8** %P
 ; CHECK: l1:
 ; CHECK-NEXT: phi i32

test/Transforms/LoopUnroll/full-unroll-bad-cost.ll

 ; RUN: opt -S -loop-unroll < %s | FileCheck %s
+; RUN: opt < %s -passes='require<opt-remark-emit>,loop(unroll)' -S | FileCheck %s
 
 ; LLVM should not try to fully unroll this loop.
 
 declare void @f()
 declare void @g()
 declare void @h()
 
 define void @trivial_loop() {

test/Transforms/LoopUnroll/full-unroll-crashers.ll

 ; Check that we don't crash on corner cases.
 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=1 -unroll-max-percent-threshold-boost=200 -o /dev/null
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=1 -unroll-max-percent-threshold-boost=200 -o /dev/null
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @known_constant = internal unnamed_addr constant [10 x i32] [i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1], align 16
 
 define void @foo1() {
 entry:
   br label %for.body
 

test/Transforms/LoopUnroll/full-unroll-heuristics-2.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=1000 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @unknown_global = internal unnamed_addr global [9 x i32] [i32 0, i32 -1, i32 0, i32 -1, i32 5, i32 -1, i32 0, i32 -1, i32 0], align 16
 @weak_constant = weak unnamed_addr constant [9 x i32] [i32 0, i32 -1, i32 0, i32 -1, i32 5, i32 -1, i32 0, i32 -1, i32 0], align 16
 
 ; Though @unknown_global is initialized with constant values, we can't consider
 ; it as a constant, so we shouldn't unroll the loop.
 ; CHECK-LABEL: @foo

test/Transforms/LoopUnroll/full-unroll-heuristics-cmp.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @known_constant = internal unnamed_addr constant [10 x i32] [i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1], align 16
 
 ; If we can figure out result of comparison on each iteration, we can resolve
 ; the depending branch. That means, that the unrolled version of the loop would
 ; have less code, because we don't need not-taken basic blocks there.
 ; This test checks that this is taken into consideration.

test/Transforms/LoopUnroll/full-unroll-heuristics-dce.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=12 -unroll-max-percent-threshold-boost=400 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=12 -unroll-max-percent-threshold-boost=400 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 @known_constant = internal unnamed_addr constant [10 x i32] [i32 0, i32 0, i32 0, i32 0, i32 1, i32 0, i32 0, i32 0, i32 0, i32 0], align 16
 
 ; If a load becomes a constant after loop unrolling, we sometimes can simplify
 ; CFG. This test verifies that we handle such cases.
 ; After one operand in an instruction is constant-folded and the
 ; instruction is simplified, the other operand might become dead.

test/Transforms/LoopUnroll/full-unroll-heuristics-geps.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 ; When examining gep-instructions we shouldn't consider them simplified if the
 ; corresponding memory access isn't simplified. Doing the opposite might bias
 ; our estimate, so that we might decide to unroll even a simple memcpy loop.
 ;
 ; Thus, the following loop shouldn't be unrolled:
 ; CHECK-LABEL: @not_simplified_geps

test/Transforms/LoopUnroll/full-unroll-heuristics-phi-prop.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll)' -unroll-max-iteration-count-to-analyze=100 -unroll-threshold=10 -unroll-max-percent-threshold-boost=200 | FileCheck %s
 target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
 
 define i64 @propagate_loop_phis() {
 ; CHECK-LABEL: @propagate_loop_phis(
 ; CHECK-NOT: br i1
 ; CHECK: ret i64 3
 entry:
   br label %loop

test/Transforms/LoopUnroll/full-unroll-keep-first-exit.ll

 ; RUN: opt -S -loop-unroll < %s | FileCheck %s
+; RUN: opt -S -passes='require<opt-remark-emit>,loop(unroll)' < %s | FileCheck %s
 
 ; Unroll twice, with first loop exit kept
 ; CHECK-LABEL: @s32_max1
 ; CHECK: do.body:
 ; CHECK:  store
 ; CHECK:  br i1 %cmp, label %do.body.1, label %do.end
 ; CHECK: do.end:
 ; CHECK:  ret void

test/Transforms/LoopUnroll/runtime-loop.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=true  | FileCheck %s -check-prefix=EPILOG
 ; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
+; RUN: opt < %s -S -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-runtime=true -unroll-runtime-epilog=true  | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-runtime=true -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
+
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 
 ; Tests for unrolling loops with run-time trip counts
 
 ; EPILOG: %xtraiter = and i32 %n
 ; EPILOG:  %lcmp.mod = icmp ne i32 %xtraiter, 0
 ; EPILOG:  br i1 %lcmp.mod, label %for.body.epil.preheader, label %for.end.loopexit
 

test/Transforms/LoopUnroll/runtime-loop1.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-runtime -unroll-count=2 -unroll-runtime-epilog=true | FileCheck %s -check-prefix=EPILOG
 ; RUN: opt < %s -S -loop-unroll -unroll-runtime -unroll-count=2 -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
+; RUN: opt < %s -S -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-runtime -unroll-count=2 -unroll-runtime-epilog=true | FileCheck %s -check-prefix=EPILOG
+; RUN: opt < %s -S -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-runtime -unroll-count=2 -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
+
 ; This tests that setting the unroll count works
 
 
 ; EPILOG: for.body.preheader:
 ; EPILOG:   br i1 %1, label %for.end.loopexit.unr-lcssa, label %for.body.preheader.new, !dbg [[PH_LOC:![0-9]+]]
 ; EPILOG: for.body:
 ; EPILOG:   br i1 %niter.ncmp.1, label %for.end.loopexit.unr-lcssa.loopexit, label %for.body, !dbg [[BODY_LOC:![0-9]+]]
 ; EPILOG-NOT: br i1 %niter.ncmp.2, label %for.end.loopexit{{.*}}, label %for.body

test/Transforms/LoopUnroll/runtime-loop2.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-threshold=25 -unroll-partial-threshold=25 -unroll-runtime -unroll-runtime-epilog=true  -unroll-count=8 | FileCheck %s  -check-prefix=EPILOG
 ; RUN: opt < %s -S -loop-unroll -unroll-threshold=25 -unroll-partial-threshold=25 -unroll-runtime -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
 
+; RUN: opt < %s -S -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-threshold=25 -unroll-partial-threshold=25 -unroll-runtime -unroll-runtime-epilog=true  -unroll-count=8 | FileCheck %s  -check-prefix=EPILOG
+; RUN: opt < %s -S -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-threshold=25 -unroll-partial-threshold=25 -unroll-runtime -unroll-runtime-epilog=false | FileCheck %s -check-prefix=PROLOG
+
 ; Choose a smaller, power-of-two, unroll count if the loop is too large.
 ; This test makes sure we're not unrolling 'odd' counts
 
 ; EPILOG: for.body:
 ; EPILOG: br i1 %niter.ncmp.3, label %for.end.loopexit.unr-lcssa.loopexit{{.*}}, label %for.body
 ; EPILOG-NOT: br i1 %niter.ncmp.4, label %for.end.loopexit.unr-lcssa.loopexit{{.*}}, label %for.body
 ; EPILOG: for.body.epil:
 

test/Transforms/LoopUnroll/runtime-loop3.ll

 ; REQUIRES: asserts
 ; RUN: opt < %s -disable-output -stats -loop-unroll -unroll-runtime -unroll-threshold=400 -info-output-file - | FileCheck %s --check-prefix=STATS
+; RUN: opt < %s -disable-output -stats -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-runtime -unroll-threshold=400 -info-output-file - | FileCheck %s --check-prefix=STATS
 
 ; Test that nested loops can be unrolled.  We need to increase threshold to do it
 
 ; STATS: 2 loop-unroll - Number of loops unrolled (completely or otherwise)
 
 define i32 @nested(i32* nocapture %a, i32 %n, i32 %m) nounwind uwtable readonly {
 entry:
   %cmp11 = icmp sgt i32 %n, 0

test/Transforms/LoopUnroll/runtime-loop5.ll

 ; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-count=16 | FileCheck --check-prefix=UNROLL-16 %s
 ; RUN: opt < %s -S -loop-unroll -unroll-runtime=true -unroll-count=4 | FileCheck --check-prefix=UNROLL-4 %s
 
+; RUN: opt < %s -S -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-runtime=true -unroll-count=16 | FileCheck --check-prefix=UNROLL-16 %s
+; RUN: opt < %s -S -passes='loop-simplify,require<opt-remark-emit>,loop(unroll)' -unroll-runtime=true -unroll-count=4 | FileCheck --check-prefix=UNROLL-4 %s
+
 ; Given that the trip-count of this loop is a 3-bit value, we cannot
 ; safely unroll it with a count of anything more than 8.
 
 define i3 @test(i3* %a, i3 %n) {
 ; UNROLL-16-LABEL: @test(
 ; UNROLL-4-LABEL: @test(
 entry:
   %cmp1 = icmp eq i3 %n, 0

test/Transforms/LoopUnroll/unloop.ll

 ; RUN: opt < %s -S -loop-unroll -verify-loop-info | FileCheck %s
-; RUN: opt < %s -S -passes='function(require<scalar-evolution>,require<targetir>,require<opt-remark-emit>,loop(unroll),verify<loops>)' | FileCheck %s
+; RUN: opt < %s -S -passes='require<opt-remark-emit>,loop(unroll),verify<loops>' | FileCheck %s
 ;
 ; Unit tests for LoopInfo::markAsRemoved.
 
 declare i1 @check() nounwind
 
 ; Ensure that tail->inner is removed and rely on verify-loopinfo to
 ; check soundness.
 ;

test/Transforms/LoopUnroll/update-loop-info-in-subloops.ll

 ; RUN: opt -S < %s -loop-unroll -block-freq | FileCheck %s
+; RUN: opt -S < %s -passes='require<opt-remark-emit>,loop(unroll),require<block-freq>' | FileCheck %s
 ; Crasher from PR20987.
 
 ; CHECK: define void @update_loop_info_in_subloops
 ; CHECK: entry:
 ; CHECK: L:
 ; CHECK: L.inner:
 ; CHECK: L.inner.latch:
 ; CHECK: L.latch: