• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- llvm/unittest/Analysis/LoopPassManagerTest.cpp - LPM tests ---------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/Transforms/Scalar/LoopPassManager.h"
10 #include "llvm/Analysis/AliasAnalysis.h"
11 #include "llvm/Analysis/AssumptionCache.h"
12 #include "llvm/Analysis/BlockFrequencyInfo.h"
13 #include "llvm/Analysis/BranchProbabilityInfo.h"
14 #include "llvm/Analysis/MemorySSA.h"
15 #include "llvm/Analysis/PostDominators.h"
16 #include "llvm/Analysis/ScalarEvolution.h"
17 #include "llvm/Analysis/TargetLibraryInfo.h"
18 #include "llvm/Analysis/TargetTransformInfo.h"
19 #include "llvm/AsmParser/Parser.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/IR/Function.h"
22 #include "llvm/IR/LLVMContext.h"
23 #include "llvm/IR/Module.h"
24 #include "llvm/IR/PassManager.h"
25 #include "llvm/Support/SourceMgr.h"
26 
27 #include "gmock/gmock.h"
28 #include "gtest/gtest.h"
29 
30 using namespace llvm;
31 
32 namespace {
33 
34 using testing::DoDefault;
35 using testing::Return;
36 using testing::Expectation;
37 using testing::Invoke;
38 using testing::InvokeWithoutArgs;
39 using testing::_;
40 
41 template <typename DerivedT, typename IRUnitT,
42           typename AnalysisManagerT = AnalysisManager<IRUnitT>,
43           typename... ExtraArgTs>
44 class MockAnalysisHandleBase {
45 public:
46   class Analysis : public AnalysisInfoMixin<Analysis> {
47     friend AnalysisInfoMixin<Analysis>;
48     friend MockAnalysisHandleBase;
49     static AnalysisKey Key;
50 
51     DerivedT *Handle;
52 
Analysis(DerivedT & Handle)53     Analysis(DerivedT &Handle) : Handle(&Handle) {
54       static_assert(std::is_base_of<MockAnalysisHandleBase, DerivedT>::value,
55                     "Must pass the derived type to this template!");
56     }
57 
58   public:
59     class Result {
60       friend MockAnalysisHandleBase;
61 
62       DerivedT *Handle;
63 
Result(DerivedT & Handle)64       Result(DerivedT &Handle) : Handle(&Handle) {}
65 
66     public:
67       // Forward invalidation events to the mock handle.
invalidate(IRUnitT & IR,const PreservedAnalyses & PA,typename AnalysisManagerT::Invalidator & Inv)68       bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA,
69                       typename AnalysisManagerT::Invalidator &Inv) {
70         return Handle->invalidate(IR, PA, Inv);
71       }
72     };
73 
run(IRUnitT & IR,AnalysisManagerT & AM,ExtraArgTs...ExtraArgs)74     Result run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs) {
75       return Handle->run(IR, AM, ExtraArgs...);
76     }
77   };
78 
getAnalysis()79   Analysis getAnalysis() { return Analysis(static_cast<DerivedT &>(*this)); }
getResult()80   typename Analysis::Result getResult() {
81     return typename Analysis::Result(static_cast<DerivedT &>(*this));
82   }
83 
84 protected:
85   // FIXME: MSVC seems unable to handle a lambda argument to Invoke from within
86   // the template, so we use a boring static function.
invalidateCallback(IRUnitT & IR,const PreservedAnalyses & PA,typename AnalysisManagerT::Invalidator & Inv)87   static bool invalidateCallback(IRUnitT &IR, const PreservedAnalyses &PA,
88                                  typename AnalysisManagerT::Invalidator &Inv) {
89     auto PAC = PA.template getChecker<Analysis>();
90     return !PAC.preserved() &&
91            !PAC.template preservedSet<AllAnalysesOn<IRUnitT>>();
92   }
93 
94   /// Derived classes should call this in their constructor to set up default
95   /// mock actions. (We can't do this in our constructor because this has to
96   /// run after the DerivedT is constructed.)
setDefaults()97   void setDefaults() {
98     ON_CALL(static_cast<DerivedT &>(*this),
99             run(_, _, testing::Matcher<ExtraArgTs>(_)...))
100         .WillByDefault(Return(this->getResult()));
101     ON_CALL(static_cast<DerivedT &>(*this), invalidate(_, _, _))
102         .WillByDefault(Invoke(&invalidateCallback));
103   }
104 };
105 
106 template <typename DerivedT, typename IRUnitT, typename AnalysisManagerT,
107           typename... ExtraArgTs>
108 AnalysisKey MockAnalysisHandleBase<DerivedT, IRUnitT, AnalysisManagerT,
109                                    ExtraArgTs...>::Analysis::Key;
110 
111 /// Mock handle for loop analyses.
112 ///
113 /// This is provided as a template accepting an (optional) integer. Because
114 /// analyses are identified and queried by type, this allows constructing
115 /// multiple handles with distinctly typed nested 'Analysis' types that can be
116 /// registered and queried. If you want to register multiple loop analysis
117 /// passes, you'll need to instantiate this type with different values for I.
118 /// For example:
119 ///
120 ///   MockLoopAnalysisHandleTemplate<0> h0;
121 ///   MockLoopAnalysisHandleTemplate<1> h1;
122 ///   typedef decltype(h0)::Analysis Analysis0;
123 ///   typedef decltype(h1)::Analysis Analysis1;
124 template <size_t I = static_cast<size_t>(-1)>
125 struct MockLoopAnalysisHandleTemplate
126     : MockAnalysisHandleBase<MockLoopAnalysisHandleTemplate<I>, Loop,
127                              LoopAnalysisManager,
128                              LoopStandardAnalysisResults &> {
129   typedef typename MockLoopAnalysisHandleTemplate::Analysis Analysis;
130 
131   MOCK_METHOD3_T(run, typename Analysis::Result(Loop &, LoopAnalysisManager &,
132                                                 LoopStandardAnalysisResults &));
133 
134   MOCK_METHOD3_T(invalidate, bool(Loop &, const PreservedAnalyses &,
135                                   LoopAnalysisManager::Invalidator &));
136 
MockLoopAnalysisHandleTemplate__anona238d0920111::MockLoopAnalysisHandleTemplate137   MockLoopAnalysisHandleTemplate() { this->setDefaults(); }
138 };
139 
140 typedef MockLoopAnalysisHandleTemplate<> MockLoopAnalysisHandle;
141 
142 struct MockFunctionAnalysisHandle
143     : MockAnalysisHandleBase<MockFunctionAnalysisHandle, Function> {
144   MOCK_METHOD2(run, Analysis::Result(Function &, FunctionAnalysisManager &));
145 
146   MOCK_METHOD3(invalidate, bool(Function &, const PreservedAnalyses &,
147                                 FunctionAnalysisManager::Invalidator &));
148 
MockFunctionAnalysisHandle__anona238d0920111::MockFunctionAnalysisHandle149   MockFunctionAnalysisHandle() { setDefaults(); }
150 };
151 
152 template <typename DerivedT, typename IRUnitT,
153           typename AnalysisManagerT = AnalysisManager<IRUnitT>,
154           typename... ExtraArgTs>
155 class MockPassHandleBase {
156 public:
157   class Pass : public PassInfoMixin<Pass> {
158     friend MockPassHandleBase;
159 
160     DerivedT *Handle;
161 
Pass(DerivedT & Handle)162     Pass(DerivedT &Handle) : Handle(&Handle) {
163       static_assert(std::is_base_of<MockPassHandleBase, DerivedT>::value,
164                     "Must pass the derived type to this template!");
165     }
166 
167   public:
run(IRUnitT & IR,AnalysisManagerT & AM,ExtraArgTs...ExtraArgs)168     PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM,
169                           ExtraArgTs... ExtraArgs) {
170       return Handle->run(IR, AM, ExtraArgs...);
171     }
172   };
173 
getPass()174   Pass getPass() { return Pass(static_cast<DerivedT &>(*this)); }
175 
176 protected:
177   /// Derived classes should call this in their constructor to set up default
178   /// mock actions. (We can't do this in our constructor because this has to
179   /// run after the DerivedT is constructed.)
setDefaults()180   void setDefaults() {
181     ON_CALL(static_cast<DerivedT &>(*this),
182             run(_, _, testing::Matcher<ExtraArgTs>(_)...))
183         .WillByDefault(Return(PreservedAnalyses::all()));
184   }
185 };
186 
187 struct MockLoopPassHandle
188     : MockPassHandleBase<MockLoopPassHandle, Loop, LoopAnalysisManager,
189                          LoopStandardAnalysisResults &, LPMUpdater &> {
190   MOCK_METHOD4(run,
191                PreservedAnalyses(Loop &, LoopAnalysisManager &,
192                                  LoopStandardAnalysisResults &, LPMUpdater &));
MockLoopPassHandle__anona238d0920111::MockLoopPassHandle193   MockLoopPassHandle() { setDefaults(); }
194 };
195 
196 struct MockFunctionPassHandle
197     : MockPassHandleBase<MockFunctionPassHandle, Function> {
198   MOCK_METHOD2(run, PreservedAnalyses(Function &, FunctionAnalysisManager &));
199 
MockFunctionPassHandle__anona238d0920111::MockFunctionPassHandle200   MockFunctionPassHandle() { setDefaults(); }
201 };
202 
203 struct MockModulePassHandle : MockPassHandleBase<MockModulePassHandle, Module> {
204   MOCK_METHOD2(run, PreservedAnalyses(Module &, ModuleAnalysisManager &));
205 
MockModulePassHandle__anona238d0920111::MockModulePassHandle206   MockModulePassHandle() { setDefaults(); }
207 };
208 
209 /// Define a custom matcher for objects which support a 'getName' method
210 /// returning a StringRef.
211 ///
212 /// LLVM often has IR objects or analysis objects which expose a StringRef name
213 /// and in tests it is convenient to match these by name for readability. This
214 /// matcher supports any type exposing a getName() method of this form.
215 ///
216 /// It should be used as:
217 ///
218 ///   HasName("my_function")
219 ///
220 /// No namespace or other qualification is required.
221 MATCHER_P(HasName, Name, "") {
222   // The matcher's name and argument are printed in the case of failure, but we
223   // also want to print out the name of the argument. This uses an implicitly
224   // avaiable std::ostream, so we have to construct a std::string.
225   *result_listener << "has name '" << arg.getName().str() << "'";
226   return Name == arg.getName();
227 }
228 
parseIR(LLVMContext & C,const char * IR)229 std::unique_ptr<Module> parseIR(LLVMContext &C, const char *IR) {
230   SMDiagnostic Err;
231   return parseAssemblyString(IR, Err, C);
232 }
233 
234 class LoopPassManagerTest : public ::testing::Test {
235 protected:
236   LLVMContext Context;
237   std::unique_ptr<Module> M;
238 
239   LoopAnalysisManager LAM;
240   FunctionAnalysisManager FAM;
241   ModuleAnalysisManager MAM;
242 
243   MockLoopAnalysisHandle MLAHandle;
244   MockLoopPassHandle MLPHandle;
245   MockFunctionPassHandle MFPHandle;
246   MockModulePassHandle MMPHandle;
247 
248   static PreservedAnalyses
getLoopAnalysisResult(Loop & L,LoopAnalysisManager & AM,LoopStandardAnalysisResults & AR,LPMUpdater &)249   getLoopAnalysisResult(Loop &L, LoopAnalysisManager &AM,
250                         LoopStandardAnalysisResults &AR, LPMUpdater &) {
251     (void)AM.getResult<MockLoopAnalysisHandle::Analysis>(L, AR);
252     return PreservedAnalyses::all();
253   };
254 
255 public:
LoopPassManagerTest()256   LoopPassManagerTest()
257       : M(parseIR(Context,
258                   "define void @f(i1* %ptr) {\n"
259                   "entry:\n"
260                   "  br label %loop.0\n"
261                   "loop.0:\n"
262                   "  %cond.0 = load volatile i1, i1* %ptr\n"
263                   "  br i1 %cond.0, label %loop.0.0.ph, label %end\n"
264                   "loop.0.0.ph:\n"
265                   "  br label %loop.0.0\n"
266                   "loop.0.0:\n"
267                   "  %cond.0.0 = load volatile i1, i1* %ptr\n"
268                   "  br i1 %cond.0.0, label %loop.0.0, label %loop.0.1.ph\n"
269                   "loop.0.1.ph:\n"
270                   "  br label %loop.0.1\n"
271                   "loop.0.1:\n"
272                   "  %cond.0.1 = load volatile i1, i1* %ptr\n"
273                   "  br i1 %cond.0.1, label %loop.0.1, label %loop.0.latch\n"
274                   "loop.0.latch:\n"
275                   "  br label %loop.0\n"
276                   "end:\n"
277                   "  ret void\n"
278                   "}\n"
279                   "\n"
280                   "define void @g(i1* %ptr) {\n"
281                   "entry:\n"
282                   "  br label %loop.g.0\n"
283                   "loop.g.0:\n"
284                   "  %cond.0 = load volatile i1, i1* %ptr\n"
285                   "  br i1 %cond.0, label %loop.g.0, label %end\n"
286                   "end:\n"
287                   "  ret void\n"
288                   "}\n")),
289         LAM(true), FAM(true), MAM(true) {
290     // Register our mock analysis.
291     LAM.registerPass([&] { return MLAHandle.getAnalysis(); });
292 
293     // We need DominatorTreeAnalysis for LoopAnalysis.
294     FAM.registerPass([&] { return DominatorTreeAnalysis(); });
295     FAM.registerPass([&] { return LoopAnalysis(); });
296     // We also allow loop passes to assume a set of other analyses and so need
297     // those.
298     FAM.registerPass([&] { return AAManager(); });
299     FAM.registerPass([&] { return AssumptionAnalysis(); });
300     FAM.registerPass([&] { return BlockFrequencyAnalysis(); });
301     FAM.registerPass([&] { return BranchProbabilityAnalysis(); });
302     FAM.registerPass([&] { return PostDominatorTreeAnalysis(); });
303     FAM.registerPass([&] { return MemorySSAAnalysis(); });
304     FAM.registerPass([&] { return ScalarEvolutionAnalysis(); });
305     FAM.registerPass([&] { return TargetLibraryAnalysis(); });
306     FAM.registerPass([&] { return TargetIRAnalysis(); });
307 
308     // Register required pass instrumentation analysis.
309     LAM.registerPass([&] { return PassInstrumentationAnalysis(); });
310     FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
311     MAM.registerPass([&] { return PassInstrumentationAnalysis(); });
312 
313     // Cross-register proxies.
314     LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); });
315     FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); });
316     FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
317     MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
318   }
319 };
320 
TEST_F(LoopPassManagerTest,Basic)321 TEST_F(LoopPassManagerTest, Basic) {
322   ModulePassManager MPM(true);
323   ::testing::InSequence MakeExpectationsSequenced;
324 
325   // First we just visit all the loops in all the functions and get their
326   // analysis results. This will run the analysis a total of four times,
327   // once for each loop.
328   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
329       .WillOnce(Invoke(getLoopAnalysisResult));
330   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
331   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
332       .WillOnce(Invoke(getLoopAnalysisResult));
333   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
334   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
335       .WillOnce(Invoke(getLoopAnalysisResult));
336   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
337   EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _))
338       .WillOnce(Invoke(getLoopAnalysisResult));
339   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
340   // Wire the loop pass through pass managers into the module pipeline.
341   {
342     LoopPassManager LPM(true);
343     LPM.addPass(MLPHandle.getPass());
344     FunctionPassManager FPM(true);
345     FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
346     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
347   }
348 
349   // Next we run two passes over the loops. The first one invalidates the
350   // analyses for one loop, the second ones try to get the analysis results.
351   // This should force only one analysis to re-run within the loop PM, but will
352   // also invalidate everything after the loop pass manager finishes.
353   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
354       .WillOnce(DoDefault())
355       .WillOnce(Invoke(getLoopAnalysisResult));
356   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
357       .WillOnce(InvokeWithoutArgs([] { return PreservedAnalyses::none(); }))
358       .WillOnce(Invoke(getLoopAnalysisResult));
359   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
360   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
361       .WillOnce(DoDefault())
362       .WillOnce(Invoke(getLoopAnalysisResult));
363   EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _))
364       .WillOnce(DoDefault())
365       .WillOnce(Invoke(getLoopAnalysisResult));
366   // Wire two loop pass runs into the module pipeline.
367   {
368     LoopPassManager LPM(true);
369     LPM.addPass(MLPHandle.getPass());
370     LPM.addPass(MLPHandle.getPass());
371     FunctionPassManager FPM(true);
372     FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
373     MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
374   }
375 
376   // And now run the pipeline across the module.
377   MPM.run(*M, MAM);
378 }
379 
TEST_F(LoopPassManagerTest,FunctionPassInvalidationOfLoopAnalyses)380 TEST_F(LoopPassManagerTest, FunctionPassInvalidationOfLoopAnalyses) {
381   ModulePassManager MPM(true);
382   FunctionPassManager FPM(true);
383   // We process each function completely in sequence.
384   ::testing::Sequence FSequence, GSequence;
385 
386   // First, force the analysis result to be computed for each loop.
387   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _))
388       .InSequence(FSequence)
389       .WillOnce(DoDefault());
390   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _))
391       .InSequence(FSequence)
392       .WillOnce(DoDefault());
393   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _))
394       .InSequence(FSequence)
395       .WillOnce(DoDefault());
396   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _))
397       .InSequence(GSequence)
398       .WillOnce(DoDefault());
399   FPM.addPass(createFunctionToLoopPassAdaptor(
400       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
401 
402   // No need to re-run if we require again from a fresh loop pass manager.
403   FPM.addPass(createFunctionToLoopPassAdaptor(
404       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
405   // For 'f', preserve most things but not the specific loop analyses.
406   auto PA = getLoopPassPreservedAnalyses();
407   if (EnableMSSALoopDependency)
408     PA.preserve<MemorySSAAnalysis>();
409   EXPECT_CALL(MFPHandle, run(HasName("f"), _))
410       .InSequence(FSequence)
411       .WillOnce(Return(PA));
412   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.0"), _, _))
413       .InSequence(FSequence)
414       .WillOnce(DoDefault());
415   // On one loop, skip the invalidation (as though we did an internal update).
416   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.1"), _, _))
417       .InSequence(FSequence)
418       .WillOnce(Return(false));
419   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0"), _, _))
420       .InSequence(FSequence)
421       .WillOnce(DoDefault());
422   // Now two loops still have to be recomputed.
423   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _))
424       .InSequence(FSequence)
425       .WillOnce(DoDefault());
426   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _))
427       .InSequence(FSequence)
428       .WillOnce(DoDefault());
429   // Preserve things in the second function to ensure invalidation remains
430   // isolated to one function.
431   EXPECT_CALL(MFPHandle, run(HasName("g"), _))
432       .InSequence(GSequence)
433       .WillOnce(DoDefault());
434   FPM.addPass(MFPHandle.getPass());
435   FPM.addPass(createFunctionToLoopPassAdaptor(
436       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
437 
438   EXPECT_CALL(MFPHandle, run(HasName("f"), _))
439       .InSequence(FSequence)
440       .WillOnce(DoDefault());
441   // For 'g', fail to preserve anything, causing the loops themselves to be
442   // cleared. We don't get an invalidation event here as the loop is gone, but
443   // we should still have to recompute the analysis.
444   EXPECT_CALL(MFPHandle, run(HasName("g"), _))
445       .InSequence(GSequence)
446       .WillOnce(Return(PreservedAnalyses::none()));
447   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _))
448       .InSequence(GSequence)
449       .WillOnce(DoDefault());
450   FPM.addPass(MFPHandle.getPass());
451   FPM.addPass(createFunctionToLoopPassAdaptor(
452       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
453 
454   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
455 
456   // Verify with a separate function pass run that we didn't mess up 'f's
457   // cache. No analysis runs should be necessary here.
458   MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
459       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
460 
461   MPM.run(*M, MAM);
462 }
463 
TEST_F(LoopPassManagerTest,ModulePassInvalidationOfLoopAnalyses)464 TEST_F(LoopPassManagerTest, ModulePassInvalidationOfLoopAnalyses) {
465   ModulePassManager MPM(true);
466   ::testing::InSequence MakeExpectationsSequenced;
467 
468   // First, force the analysis result to be computed for each loop.
469   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
470   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
471   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
472   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
473   MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
474       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
475 
476   // Walking all the way out and all the way back in doesn't re-run the
477   // analysis.
478   MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
479       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
480 
481   // But a module pass that doesn't preserve the actual mock loop analysis
482   // invalidates all the way down and forces recomputing.
483   EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] {
484     auto PA = getLoopPassPreservedAnalyses();
485     PA.preserve<FunctionAnalysisManagerModuleProxy>();
486     if (EnableMSSALoopDependency)
487       PA.preserve<MemorySSAAnalysis>();
488     return PA;
489   }));
490   // All the loop analyses from both functions get invalidated before we
491   // recompute anything.
492   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.0"), _, _));
493   // On one loop, again skip the invalidation (as though we did an internal
494   // update).
495   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.1"), _, _))
496       .WillOnce(Return(false));
497   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0"), _, _));
498   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.g.0"), _, _));
499   // Now all but one of the loops gets re-analyzed.
500   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
501   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
502   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
503   MPM.addPass(MMPHandle.getPass());
504   MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
505       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
506 
507   // Verify that the cached values persist.
508   MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
509       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
510 
511   // Now we fail to preserve the loop analysis and observe that the loop
512   // analyses are cleared (so no invalidation event) as the loops themselves
513   // are no longer valid.
514   EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] {
515     auto PA = PreservedAnalyses::none();
516     PA.preserve<FunctionAnalysisManagerModuleProxy>();
517     return PA;
518   }));
519   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
520   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
521   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
522   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
523   MPM.addPass(MMPHandle.getPass());
524   MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
525       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
526 
527   // Verify that the cached values persist.
528   MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
529       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
530 
531   // Next, check that even if we preserve everything within the function itelf,
532   // if the function's module pass proxy isn't preserved and the potential set
533   // of functions changes, the clear reaches the loop analyses as well. This
534   // will again trigger re-runs but not invalidation events.
535   EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] {
536     auto PA = PreservedAnalyses::none();
537     PA.preserveSet<AllAnalysesOn<Function>>();
538     PA.preserveSet<AllAnalysesOn<Loop>>();
539     return PA;
540   }));
541   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
542   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
543   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
544   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
545   MPM.addPass(MMPHandle.getPass());
546   MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor(
547       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())));
548 
549   MPM.run(*M, MAM);
550 }
551 
552 // Test that if any of the bundled analyses provided in the LPM's signature
553 // become invalid, the analysis proxy itself becomes invalid and we clear all
554 // loop analysis results.
TEST_F(LoopPassManagerTest,InvalidationOfBundledAnalyses)555 TEST_F(LoopPassManagerTest, InvalidationOfBundledAnalyses) {
556   ModulePassManager MPM(true);
557   FunctionPassManager FPM(true);
558   ::testing::InSequence MakeExpectationsSequenced;
559 
560   // First, force the analysis result to be computed for each loop.
561   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
562   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
563   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
564   FPM.addPass(createFunctionToLoopPassAdaptor(
565       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
566 
567   // No need to re-run if we require again from a fresh loop pass manager.
568   FPM.addPass(createFunctionToLoopPassAdaptor(
569       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
570 
571   // Preserving everything but the loop analyses themselves results in
572   // invalidation and running.
573   EXPECT_CALL(MFPHandle, run(HasName("f"), _))
574       .WillOnce(Return(getLoopPassPreservedAnalyses()));
575   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
576   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
577   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
578   FPM.addPass(MFPHandle.getPass());
579   FPM.addPass(createFunctionToLoopPassAdaptor(
580       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
581 
582   // The rest don't invalidate analyses, they only trigger re-runs because we
583   // clear the cache completely.
584   EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
585     auto PA = PreservedAnalyses::none();
586     // Not preserving `AAManager`.
587     PA.preserve<DominatorTreeAnalysis>();
588     PA.preserve<LoopAnalysis>();
589     PA.preserve<LoopAnalysisManagerFunctionProxy>();
590     PA.preserve<ScalarEvolutionAnalysis>();
591     return PA;
592   }));
593   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
594   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
595   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
596   FPM.addPass(MFPHandle.getPass());
597   FPM.addPass(createFunctionToLoopPassAdaptor(
598       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
599 
600   EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
601     auto PA = PreservedAnalyses::none();
602     PA.preserve<AAManager>();
603     // Not preserving `DominatorTreeAnalysis`.
604     PA.preserve<LoopAnalysis>();
605     PA.preserve<LoopAnalysisManagerFunctionProxy>();
606     PA.preserve<ScalarEvolutionAnalysis>();
607     return PA;
608   }));
609   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
610   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
611   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
612   FPM.addPass(MFPHandle.getPass());
613   FPM.addPass(createFunctionToLoopPassAdaptor(
614       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
615 
616   EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
617     auto PA = PreservedAnalyses::none();
618     PA.preserve<AAManager>();
619     PA.preserve<DominatorTreeAnalysis>();
620     // Not preserving the `LoopAnalysis`.
621     PA.preserve<LoopAnalysisManagerFunctionProxy>();
622     PA.preserve<ScalarEvolutionAnalysis>();
623     return PA;
624   }));
625   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
626   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
627   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
628   FPM.addPass(MFPHandle.getPass());
629   FPM.addPass(createFunctionToLoopPassAdaptor(
630       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
631 
632   EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
633     auto PA = PreservedAnalyses::none();
634     PA.preserve<AAManager>();
635     PA.preserve<DominatorTreeAnalysis>();
636     PA.preserve<LoopAnalysis>();
637     // Not preserving the `LoopAnalysisManagerFunctionProxy`.
638     PA.preserve<ScalarEvolutionAnalysis>();
639     return PA;
640   }));
641   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
642   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
643   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
644   FPM.addPass(MFPHandle.getPass());
645   FPM.addPass(createFunctionToLoopPassAdaptor(
646       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
647 
648   EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
649     auto PA = PreservedAnalyses::none();
650     PA.preserve<AAManager>();
651     PA.preserve<DominatorTreeAnalysis>();
652     PA.preserve<LoopAnalysis>();
653     PA.preserve<LoopAnalysisManagerFunctionProxy>();
654     // Not preserving `ScalarEvolutionAnalysis`.
655     return PA;
656   }));
657   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
658   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
659   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
660   FPM.addPass(MFPHandle.getPass());
661   FPM.addPass(createFunctionToLoopPassAdaptor(
662       RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()));
663 
664   // After all the churn on 'f', we'll compute the loop analysis results for
665   // 'g' once with a requires pass and then run our mock pass over g a bunch
666   // but just get cached results each time.
667   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
668   EXPECT_CALL(MFPHandle, run(HasName("g"), _)).Times(6);
669 
670   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
671   MPM.run(*M, MAM);
672 }
673 
TEST_F(LoopPassManagerTest,IndirectInvalidation)674 TEST_F(LoopPassManagerTest, IndirectInvalidation) {
675   // We need two distinct analysis types and handles.
676   enum { A, B };
677   MockLoopAnalysisHandleTemplate<A> MLAHandleA;
678   MockLoopAnalysisHandleTemplate<B> MLAHandleB;
679   LAM.registerPass([&] { return MLAHandleA.getAnalysis(); });
680   LAM.registerPass([&] { return MLAHandleB.getAnalysis(); });
681   typedef decltype(MLAHandleA)::Analysis AnalysisA;
682   typedef decltype(MLAHandleB)::Analysis AnalysisB;
683 
684   // Set up AnalysisA to depend on our AnalysisB. For testing purposes we just
685   // need to get the AnalysisB results in AnalysisA's run method and check if
686   // AnalysisB gets invalidated in AnalysisA's invalidate method.
687   ON_CALL(MLAHandleA, run(_, _, _))
688       .WillByDefault(Invoke([&](Loop &L, LoopAnalysisManager &AM,
689                                 LoopStandardAnalysisResults &AR) {
690         (void)AM.getResult<AnalysisB>(L, AR);
691         return MLAHandleA.getResult();
692       }));
693   ON_CALL(MLAHandleA, invalidate(_, _, _))
694       .WillByDefault(Invoke([](Loop &L, const PreservedAnalyses &PA,
695                                LoopAnalysisManager::Invalidator &Inv) {
696         auto PAC = PA.getChecker<AnalysisA>();
697         return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Loop>>()) ||
698                Inv.invalidate<AnalysisB>(L, PA);
699       }));
700 
701   ::testing::InSequence MakeExpectationsSequenced;
702 
703   // Compute the analyses across all of 'f' first.
704   EXPECT_CALL(MLAHandleA, run(HasName("loop.0.0"), _, _));
705   EXPECT_CALL(MLAHandleB, run(HasName("loop.0.0"), _, _));
706   EXPECT_CALL(MLAHandleA, run(HasName("loop.0.1"), _, _));
707   EXPECT_CALL(MLAHandleB, run(HasName("loop.0.1"), _, _));
708   EXPECT_CALL(MLAHandleA, run(HasName("loop.0"), _, _));
709   EXPECT_CALL(MLAHandleB, run(HasName("loop.0"), _, _));
710 
711   // Now we invalidate AnalysisB (but not AnalysisA) for one of the loops and
712   // preserve everything for the rest. This in turn triggers that one loop to
713   // recompute both AnalysisB *and* AnalysisA if indirect invalidation is
714   // working.
715   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
716       .WillOnce(InvokeWithoutArgs([] {
717         auto PA = getLoopPassPreservedAnalyses();
718         // Specifically preserve AnalysisA so that it would survive if it
719         // didn't depend on AnalysisB.
720         PA.preserve<AnalysisA>();
721         return PA;
722       }));
723   // It happens that AnalysisB is invalidated first. That shouldn't matter
724   // though, and we should still call AnalysisA's invalidation.
725   EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.0.0"), _, _));
726   EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.0.0"), _, _));
727   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
728       .WillOnce(Invoke([](Loop &L, LoopAnalysisManager &AM,
729                           LoopStandardAnalysisResults &AR, LPMUpdater &) {
730         (void)AM.getResult<AnalysisA>(L, AR);
731         return PreservedAnalyses::all();
732       }));
733   EXPECT_CALL(MLAHandleA, run(HasName("loop.0.0"), _, _));
734   EXPECT_CALL(MLAHandleB, run(HasName("loop.0.0"), _, _));
735   // The rest of the loops should run and get cached results.
736   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
737       .Times(2)
738       .WillRepeatedly(Invoke([](Loop &L, LoopAnalysisManager &AM,
739                                 LoopStandardAnalysisResults &AR, LPMUpdater &) {
740         (void)AM.getResult<AnalysisA>(L, AR);
741         return PreservedAnalyses::all();
742       }));
743   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
744       .Times(2)
745       .WillRepeatedly(Invoke([](Loop &L, LoopAnalysisManager &AM,
746                                 LoopStandardAnalysisResults &AR, LPMUpdater &) {
747         (void)AM.getResult<AnalysisA>(L, AR);
748         return PreservedAnalyses::all();
749       }));
750 
751   // The run over 'g' should be boring, with us just computing the analyses once
752   // up front and then running loop passes and getting cached results.
753   EXPECT_CALL(MLAHandleA, run(HasName("loop.g.0"), _, _));
754   EXPECT_CALL(MLAHandleB, run(HasName("loop.g.0"), _, _));
755   EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _))
756       .Times(2)
757       .WillRepeatedly(Invoke([](Loop &L, LoopAnalysisManager &AM,
758                                 LoopStandardAnalysisResults &AR, LPMUpdater &) {
759         (void)AM.getResult<AnalysisA>(L, AR);
760         return PreservedAnalyses::all();
761       }));
762 
763   // Build the pipeline and run it.
764   ModulePassManager MPM(true);
765   FunctionPassManager FPM(true);
766   FPM.addPass(
767       createFunctionToLoopPassAdaptor(RequireAnalysisLoopPass<AnalysisA>()));
768   LoopPassManager LPM(true);
769   LPM.addPass(MLPHandle.getPass());
770   LPM.addPass(MLPHandle.getPass());
771   FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
772   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
773   MPM.run(*M, MAM);
774 }
775 
TEST_F(LoopPassManagerTest,IndirectOuterPassInvalidation)776 TEST_F(LoopPassManagerTest, IndirectOuterPassInvalidation) {
777   typedef decltype(MLAHandle)::Analysis LoopAnalysis;
778 
779   MockFunctionAnalysisHandle MFAHandle;
780   FAM.registerPass([&] { return MFAHandle.getAnalysis(); });
781   typedef decltype(MFAHandle)::Analysis FunctionAnalysis;
782 
783   // Set up the loop analysis to depend on both the function and module
784   // analysis.
785   ON_CALL(MLAHandle, run(_, _, _))
786       .WillByDefault(Invoke([&](Loop &L, LoopAnalysisManager &AM,
787                                 LoopStandardAnalysisResults &AR) {
788         auto &FAMP = AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR);
789         Function &F = *L.getHeader()->getParent();
790         // This call will assert when trying to get the actual analysis if the
791         // FunctionAnalysis can be invalidated. Only check its existence.
792         // Alternatively, use FAM above, for the purposes of this unittest.
793         if (FAMP.cachedResultExists<FunctionAnalysis>(F))
794           FAMP.registerOuterAnalysisInvalidation<FunctionAnalysis,
795                                                  LoopAnalysis>();
796         return MLAHandle.getResult();
797       }));
798 
799   ::testing::InSequence MakeExpectationsSequenced;
800 
801   // Compute the analyses across all of 'f' first.
802   EXPECT_CALL(MFPHandle, run(HasName("f"), _))
803       .WillOnce(Invoke([](Function &F, FunctionAnalysisManager &AM) {
804         // Force the computing of the function analysis so it is available in
805         // this function.
806         (void)AM.getResult<FunctionAnalysis>(F);
807         return PreservedAnalyses::all();
808       }));
809   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
810   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
811   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
812 
813   // Now invalidate the function analysis but preserve the loop analyses.
814   // This should trigger immediate invalidation of the loop analyses, despite
815   // the fact that they were preserved.
816   EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] {
817     auto PA = getLoopPassPreservedAnalyses();
818     if (EnableMSSALoopDependency)
819       PA.preserve<MemorySSAAnalysis>();
820     PA.preserveSet<AllAnalysesOn<Loop>>();
821     return PA;
822   }));
823   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.0"), _, _));
824   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.1"), _, _));
825   EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0"), _, _));
826 
827   // And re-running a requires pass recomputes them.
828   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
829   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
830   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
831 
832   // When we run over 'g' we don't populate the cache with the function
833   // analysis.
834   EXPECT_CALL(MFPHandle, run(HasName("g"), _))
835       .WillOnce(Return(PreservedAnalyses::all()));
836   EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _));
837 
838   // Which means that no extra invalidation occurs and cached values are used.
839   EXPECT_CALL(MFPHandle, run(HasName("g"), _)).WillOnce(InvokeWithoutArgs([] {
840     auto PA = getLoopPassPreservedAnalyses();
841     if (EnableMSSALoopDependency)
842       PA.preserve<MemorySSAAnalysis>();
843     PA.preserveSet<AllAnalysesOn<Loop>>();
844     return PA;
845   }));
846 
847   // Build the pipeline and run it.
848   ModulePassManager MPM(true);
849   FunctionPassManager FPM(true);
850   FPM.addPass(MFPHandle.getPass());
851   FPM.addPass(
852       createFunctionToLoopPassAdaptor(RequireAnalysisLoopPass<LoopAnalysis>()));
853   FPM.addPass(MFPHandle.getPass());
854   FPM.addPass(
855       createFunctionToLoopPassAdaptor(RequireAnalysisLoopPass<LoopAnalysis>()));
856   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
857   MPM.run(*M, MAM);
858 }
859 
TEST_F(LoopPassManagerTest,LoopChildInsertion)860 TEST_F(LoopPassManagerTest, LoopChildInsertion) {
861   // Super boring module with three loops in a single loop nest.
862   M = parseIR(Context, "define void @f(i1* %ptr) {\n"
863                        "entry:\n"
864                        "  br label %loop.0\n"
865                        "loop.0:\n"
866                        "  %cond.0 = load volatile i1, i1* %ptr\n"
867                        "  br i1 %cond.0, label %loop.0.0.ph, label %end\n"
868                        "loop.0.0.ph:\n"
869                        "  br label %loop.0.0\n"
870                        "loop.0.0:\n"
871                        "  %cond.0.0 = load volatile i1, i1* %ptr\n"
872                        "  br i1 %cond.0.0, label %loop.0.0, label %loop.0.1.ph\n"
873                        "loop.0.1.ph:\n"
874                        "  br label %loop.0.1\n"
875                        "loop.0.1:\n"
876                        "  %cond.0.1 = load volatile i1, i1* %ptr\n"
877                        "  br i1 %cond.0.1, label %loop.0.1, label %loop.0.2.ph\n"
878                        "loop.0.2.ph:\n"
879                        "  br label %loop.0.2\n"
880                        "loop.0.2:\n"
881                        "  %cond.0.2 = load volatile i1, i1* %ptr\n"
882                        "  br i1 %cond.0.2, label %loop.0.2, label %loop.0.latch\n"
883                        "loop.0.latch:\n"
884                        "  br label %loop.0\n"
885                        "end:\n"
886                        "  ret void\n"
887                        "}\n");
888 
889   // Build up variables referring into the IR so we can rewrite it below
890   // easily.
891   Function &F = *M->begin();
892   ASSERT_THAT(F, HasName("f"));
893   Argument &Ptr = *F.arg_begin();
894   auto BBI = F.begin();
895   BasicBlock &EntryBB = *BBI++;
896   ASSERT_THAT(EntryBB, HasName("entry"));
897   BasicBlock &Loop0BB = *BBI++;
898   ASSERT_THAT(Loop0BB, HasName("loop.0"));
899   BasicBlock &Loop00PHBB = *BBI++;
900   ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph"));
901   BasicBlock &Loop00BB = *BBI++;
902   ASSERT_THAT(Loop00BB, HasName("loop.0.0"));
903   BasicBlock &Loop01PHBB = *BBI++;
904   ASSERT_THAT(Loop01PHBB, HasName("loop.0.1.ph"));
905   BasicBlock &Loop01BB = *BBI++;
906   ASSERT_THAT(Loop01BB, HasName("loop.0.1"));
907   BasicBlock &Loop02PHBB = *BBI++;
908   ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph"));
909   BasicBlock &Loop02BB = *BBI++;
910   ASSERT_THAT(Loop02BB, HasName("loop.0.2"));
911   BasicBlock &Loop0LatchBB = *BBI++;
912   ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch"));
913   BasicBlock &EndBB = *BBI++;
914   ASSERT_THAT(EndBB, HasName("end"));
915   ASSERT_THAT(BBI, F.end());
916   auto CreateCondBr = [&](BasicBlock *TrueBB, BasicBlock *FalseBB,
917                           const char *Name, BasicBlock *BB) {
918     auto *Cond = new LoadInst(Type::getInt1Ty(Context), &Ptr, Name,
919                               /*isVolatile*/ true, BB);
920     BranchInst::Create(TrueBB, FalseBB, Cond, BB);
921   };
922 
923   // Build the pass managers and register our pipeline. We build a single loop
924   // pass pipeline consisting of three mock pass runs over each loop. After
925   // this we run both domtree and loop verification passes to make sure that
926   // the IR remained valid during our mutations.
927   ModulePassManager MPM(true);
928   FunctionPassManager FPM(true);
929   LoopPassManager LPM(true);
930   LPM.addPass(MLPHandle.getPass());
931   LPM.addPass(MLPHandle.getPass());
932   LPM.addPass(MLPHandle.getPass());
933   FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
934   FPM.addPass(DominatorTreeVerifierPass());
935   FPM.addPass(LoopVerifierPass());
936   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
937 
938   // All the visit orders are deterministic, so we use simple fully order
939   // expectations.
940   ::testing::InSequence MakeExpectationsSequenced;
941 
942   // We run loop passes three times over each of the loops.
943   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
944       .WillOnce(Invoke(getLoopAnalysisResult));
945   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
946   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
947       .Times(2)
948       .WillRepeatedly(Invoke(getLoopAnalysisResult));
949 
950   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
951       .WillOnce(Invoke(getLoopAnalysisResult));
952   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
953 
954   // When running over the middle loop, the second run inserts two new child
955   // loops, inserting them and itself into the worklist.
956   BasicBlock *NewLoop010BB, *NewLoop01LatchBB;
957   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
958       .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM,
959                            LoopStandardAnalysisResults &AR,
960                            LPMUpdater &Updater) {
961         auto *NewLoop = AR.LI.AllocateLoop();
962         L.addChildLoop(NewLoop);
963         auto *NewLoop010PHBB =
964             BasicBlock::Create(Context, "loop.0.1.0.ph", &F, &Loop02PHBB);
965         NewLoop010BB =
966             BasicBlock::Create(Context, "loop.0.1.0", &F, &Loop02PHBB);
967         NewLoop01LatchBB =
968             BasicBlock::Create(Context, "loop.0.1.latch", &F, &Loop02PHBB);
969         Loop01BB.getTerminator()->replaceUsesOfWith(&Loop01BB, NewLoop010PHBB);
970         BranchInst::Create(NewLoop010BB, NewLoop010PHBB);
971         CreateCondBr(NewLoop01LatchBB, NewLoop010BB, "cond.0.1.0",
972                      NewLoop010BB);
973         BranchInst::Create(&Loop01BB, NewLoop01LatchBB);
974         AR.DT.addNewBlock(NewLoop010PHBB, &Loop01BB);
975         AR.DT.addNewBlock(NewLoop010BB, NewLoop010PHBB);
976         AR.DT.addNewBlock(NewLoop01LatchBB, NewLoop010BB);
977         EXPECT_TRUE(AR.DT.verify());
978         L.addBasicBlockToLoop(NewLoop010PHBB, AR.LI);
979         NewLoop->addBasicBlockToLoop(NewLoop010BB, AR.LI);
980         L.addBasicBlockToLoop(NewLoop01LatchBB, AR.LI);
981         NewLoop->verifyLoop();
982         L.verifyLoop();
983         Updater.addChildLoops({NewLoop});
984         return PreservedAnalyses::all();
985       }));
986 
987   // We should immediately drop down to fully visit the new inner loop.
988   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.0"), _, _, _))
989       .WillOnce(Invoke(getLoopAnalysisResult));
990   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1.0"), _, _));
991   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.0"), _, _, _))
992       .Times(2)
993       .WillRepeatedly(Invoke(getLoopAnalysisResult));
994 
995   // After visiting the inner loop, we should re-visit the second loop
996   // reflecting its new loop nest structure.
997   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
998       .WillOnce(Invoke(getLoopAnalysisResult));
999 
1000   // In the second run over the middle loop after we've visited the new child,
1001   // we add another child to check that we can repeatedly add children, and add
1002   // children to a loop that already has children.
1003   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
1004       .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM,
1005                            LoopStandardAnalysisResults &AR,
1006                            LPMUpdater &Updater) {
1007         auto *NewLoop = AR.LI.AllocateLoop();
1008         L.addChildLoop(NewLoop);
1009         auto *NewLoop011PHBB = BasicBlock::Create(Context, "loop.0.1.1.ph", &F, NewLoop01LatchBB);
1010         auto *NewLoop011BB = BasicBlock::Create(Context, "loop.0.1.1", &F, NewLoop01LatchBB);
1011         NewLoop010BB->getTerminator()->replaceUsesOfWith(NewLoop01LatchBB,
1012                                                          NewLoop011PHBB);
1013         BranchInst::Create(NewLoop011BB, NewLoop011PHBB);
1014         CreateCondBr(NewLoop01LatchBB, NewLoop011BB, "cond.0.1.1",
1015                      NewLoop011BB);
1016         AR.DT.addNewBlock(NewLoop011PHBB, NewLoop010BB);
1017         auto *NewDTNode = AR.DT.addNewBlock(NewLoop011BB, NewLoop011PHBB);
1018         AR.DT.changeImmediateDominator(AR.DT[NewLoop01LatchBB], NewDTNode);
1019         EXPECT_TRUE(AR.DT.verify());
1020         L.addBasicBlockToLoop(NewLoop011PHBB, AR.LI);
1021         NewLoop->addBasicBlockToLoop(NewLoop011BB, AR.LI);
1022         NewLoop->verifyLoop();
1023         L.verifyLoop();
1024         Updater.addChildLoops({NewLoop});
1025         return PreservedAnalyses::all();
1026       }));
1027 
1028   // Again, we should immediately drop down to visit the new, unvisited child
1029   // loop. We don't need to revisit the other child though.
1030   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.1"), _, _, _))
1031       .WillOnce(Invoke(getLoopAnalysisResult));
1032   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1.1"), _, _));
1033   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.1"), _, _, _))
1034       .Times(2)
1035       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1036 
1037   // And now we should pop back up to the second loop and do a full pipeline of
1038   // three passes on its current form.
1039   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
1040       .Times(3)
1041       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1042 
1043   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1044       .WillOnce(Invoke(getLoopAnalysisResult));
1045   EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _));
1046   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1047       .Times(2)
1048       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1049 
1050   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1051       .WillOnce(Invoke(getLoopAnalysisResult));
1052   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
1053   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1054       .Times(2)
1055       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1056 
1057   // Now that all the expected actions are registered, run the pipeline over
1058   // our module. All of our expectations are verified when the test finishes.
1059   MPM.run(*M, MAM);
1060 }
1061 
TEST_F(LoopPassManagerTest,LoopPeerInsertion)1062 TEST_F(LoopPassManagerTest, LoopPeerInsertion) {
1063   // Super boring module with two loop nests and loop nest with two child
1064   // loops.
1065   M = parseIR(Context, "define void @f(i1* %ptr) {\n"
1066                        "entry:\n"
1067                        "  br label %loop.0\n"
1068                        "loop.0:\n"
1069                        "  %cond.0 = load volatile i1, i1* %ptr\n"
1070                        "  br i1 %cond.0, label %loop.0.0.ph, label %loop.2.ph\n"
1071                        "loop.0.0.ph:\n"
1072                        "  br label %loop.0.0\n"
1073                        "loop.0.0:\n"
1074                        "  %cond.0.0 = load volatile i1, i1* %ptr\n"
1075                        "  br i1 %cond.0.0, label %loop.0.0, label %loop.0.2.ph\n"
1076                        "loop.0.2.ph:\n"
1077                        "  br label %loop.0.2\n"
1078                        "loop.0.2:\n"
1079                        "  %cond.0.2 = load volatile i1, i1* %ptr\n"
1080                        "  br i1 %cond.0.2, label %loop.0.2, label %loop.0.latch\n"
1081                        "loop.0.latch:\n"
1082                        "  br label %loop.0\n"
1083                        "loop.2.ph:\n"
1084                        "  br label %loop.2\n"
1085                        "loop.2:\n"
1086                        "  %cond.2 = load volatile i1, i1* %ptr\n"
1087                        "  br i1 %cond.2, label %loop.2, label %end\n"
1088                        "end:\n"
1089                        "  ret void\n"
1090                        "}\n");
1091 
1092   // Build up variables referring into the IR so we can rewrite it below
1093   // easily.
1094   Function &F = *M->begin();
1095   ASSERT_THAT(F, HasName("f"));
1096   Argument &Ptr = *F.arg_begin();
1097   auto BBI = F.begin();
1098   BasicBlock &EntryBB = *BBI++;
1099   ASSERT_THAT(EntryBB, HasName("entry"));
1100   BasicBlock &Loop0BB = *BBI++;
1101   ASSERT_THAT(Loop0BB, HasName("loop.0"));
1102   BasicBlock &Loop00PHBB = *BBI++;
1103   ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph"));
1104   BasicBlock &Loop00BB = *BBI++;
1105   ASSERT_THAT(Loop00BB, HasName("loop.0.0"));
1106   BasicBlock &Loop02PHBB = *BBI++;
1107   ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph"));
1108   BasicBlock &Loop02BB = *BBI++;
1109   ASSERT_THAT(Loop02BB, HasName("loop.0.2"));
1110   BasicBlock &Loop0LatchBB = *BBI++;
1111   ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch"));
1112   BasicBlock &Loop2PHBB = *BBI++;
1113   ASSERT_THAT(Loop2PHBB, HasName("loop.2.ph"));
1114   BasicBlock &Loop2BB = *BBI++;
1115   ASSERT_THAT(Loop2BB, HasName("loop.2"));
1116   BasicBlock &EndBB = *BBI++;
1117   ASSERT_THAT(EndBB, HasName("end"));
1118   ASSERT_THAT(BBI, F.end());
1119   auto CreateCondBr = [&](BasicBlock *TrueBB, BasicBlock *FalseBB,
1120                           const char *Name, BasicBlock *BB) {
1121     auto *Cond = new LoadInst(Type::getInt1Ty(Context), &Ptr, Name,
1122                               /*isVolatile*/ true, BB);
1123     BranchInst::Create(TrueBB, FalseBB, Cond, BB);
1124   };
1125 
1126   // Build the pass managers and register our pipeline. We build a single loop
1127   // pass pipeline consisting of three mock pass runs over each loop. After
1128   // this we run both domtree and loop verification passes to make sure that
1129   // the IR remained valid during our mutations.
1130   ModulePassManager MPM(true);
1131   FunctionPassManager FPM(true);
1132   LoopPassManager LPM(true);
1133   LPM.addPass(MLPHandle.getPass());
1134   LPM.addPass(MLPHandle.getPass());
1135   LPM.addPass(MLPHandle.getPass());
1136   FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
1137   FPM.addPass(DominatorTreeVerifierPass());
1138   FPM.addPass(LoopVerifierPass());
1139   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
1140 
1141   // All the visit orders are deterministic, so we use simple fully order
1142   // expectations.
1143   ::testing::InSequence MakeExpectationsSequenced;
1144 
1145   // We run loop passes three times over each of the loops.
1146   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
1147       .WillOnce(Invoke(getLoopAnalysisResult));
1148   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
1149 
1150   // On the second run, we insert a sibling loop.
1151   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
1152       .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM,
1153                            LoopStandardAnalysisResults &AR,
1154                            LPMUpdater &Updater) {
1155         auto *NewLoop = AR.LI.AllocateLoop();
1156         L.getParentLoop()->addChildLoop(NewLoop);
1157         auto *NewLoop01PHBB = BasicBlock::Create(Context, "loop.0.1.ph", &F, &Loop02PHBB);
1158         auto *NewLoop01BB = BasicBlock::Create(Context, "loop.0.1", &F, &Loop02PHBB);
1159         BranchInst::Create(NewLoop01BB, NewLoop01PHBB);
1160         CreateCondBr(&Loop02PHBB, NewLoop01BB, "cond.0.1", NewLoop01BB);
1161         Loop00BB.getTerminator()->replaceUsesOfWith(&Loop02PHBB, NewLoop01PHBB);
1162         AR.DT.addNewBlock(NewLoop01PHBB, &Loop00BB);
1163         auto *NewDTNode = AR.DT.addNewBlock(NewLoop01BB, NewLoop01PHBB);
1164         AR.DT.changeImmediateDominator(AR.DT[&Loop02PHBB], NewDTNode);
1165         EXPECT_TRUE(AR.DT.verify());
1166         L.getParentLoop()->addBasicBlockToLoop(NewLoop01PHBB, AR.LI);
1167         NewLoop->addBasicBlockToLoop(NewLoop01BB, AR.LI);
1168         L.getParentLoop()->verifyLoop();
1169         Updater.addSiblingLoops({NewLoop});
1170         return PreservedAnalyses::all();
1171       }));
1172   // We finish processing this loop as sibling loops don't perturb the
1173   // postorder walk.
1174   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
1175       .WillOnce(Invoke(getLoopAnalysisResult));
1176 
1177   // We visit the inserted sibling next.
1178   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
1179       .WillOnce(Invoke(getLoopAnalysisResult));
1180   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
1181   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
1182       .Times(2)
1183       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1184 
1185   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1186       .WillOnce(Invoke(getLoopAnalysisResult));
1187   EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _));
1188   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1189       .WillOnce(Invoke(getLoopAnalysisResult));
1190   // Next, on the third pass run on the last inner loop we add more new
1191   // siblings, more than one, and one with nested child loops. By doing this at
1192   // the end we make sure that edge case works well.
1193   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1194       .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM,
1195                            LoopStandardAnalysisResults &AR,
1196                            LPMUpdater &Updater) {
1197         Loop *NewLoops[] = {AR.LI.AllocateLoop(), AR.LI.AllocateLoop(),
1198                             AR.LI.AllocateLoop()};
1199         L.getParentLoop()->addChildLoop(NewLoops[0]);
1200         L.getParentLoop()->addChildLoop(NewLoops[1]);
1201         NewLoops[1]->addChildLoop(NewLoops[2]);
1202         auto *NewLoop03PHBB =
1203             BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB);
1204         auto *NewLoop03BB =
1205             BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB);
1206         auto *NewLoop04PHBB =
1207             BasicBlock::Create(Context, "loop.0.4.ph", &F, &Loop0LatchBB);
1208         auto *NewLoop04BB =
1209             BasicBlock::Create(Context, "loop.0.4", &F, &Loop0LatchBB);
1210         auto *NewLoop040PHBB =
1211             BasicBlock::Create(Context, "loop.0.4.0.ph", &F, &Loop0LatchBB);
1212         auto *NewLoop040BB =
1213             BasicBlock::Create(Context, "loop.0.4.0", &F, &Loop0LatchBB);
1214         auto *NewLoop04LatchBB =
1215             BasicBlock::Create(Context, "loop.0.4.latch", &F, &Loop0LatchBB);
1216         Loop02BB.getTerminator()->replaceUsesOfWith(&Loop0LatchBB, NewLoop03PHBB);
1217         BranchInst::Create(NewLoop03BB, NewLoop03PHBB);
1218         CreateCondBr(NewLoop04PHBB, NewLoop03BB, "cond.0.3", NewLoop03BB);
1219         BranchInst::Create(NewLoop04BB, NewLoop04PHBB);
1220         CreateCondBr(&Loop0LatchBB, NewLoop040PHBB, "cond.0.4", NewLoop04BB);
1221         BranchInst::Create(NewLoop040BB, NewLoop040PHBB);
1222         CreateCondBr(NewLoop04LatchBB, NewLoop040BB, "cond.0.4.0", NewLoop040BB);
1223         BranchInst::Create(NewLoop04BB, NewLoop04LatchBB);
1224         AR.DT.addNewBlock(NewLoop03PHBB, &Loop02BB);
1225         AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB);
1226         AR.DT.addNewBlock(NewLoop04PHBB, NewLoop03BB);
1227         auto *NewDTNode = AR.DT.addNewBlock(NewLoop04BB, NewLoop04PHBB);
1228         AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB], NewDTNode);
1229         AR.DT.addNewBlock(NewLoop040PHBB, NewLoop04BB);
1230         AR.DT.addNewBlock(NewLoop040BB, NewLoop040PHBB);
1231         AR.DT.addNewBlock(NewLoop04LatchBB, NewLoop040BB);
1232         EXPECT_TRUE(AR.DT.verify());
1233         L.getParentLoop()->addBasicBlockToLoop(NewLoop03PHBB, AR.LI);
1234         NewLoops[0]->addBasicBlockToLoop(NewLoop03BB, AR.LI);
1235         L.getParentLoop()->addBasicBlockToLoop(NewLoop04PHBB, AR.LI);
1236         NewLoops[1]->addBasicBlockToLoop(NewLoop04BB, AR.LI);
1237         NewLoops[1]->addBasicBlockToLoop(NewLoop040PHBB, AR.LI);
1238         NewLoops[2]->addBasicBlockToLoop(NewLoop040BB, AR.LI);
1239         NewLoops[1]->addBasicBlockToLoop(NewLoop04LatchBB, AR.LI);
1240         L.getParentLoop()->verifyLoop();
1241         Updater.addSiblingLoops({NewLoops[0], NewLoops[1]});
1242         return PreservedAnalyses::all();
1243       }));
1244 
1245   EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _))
1246       .WillOnce(Invoke(getLoopAnalysisResult));
1247   EXPECT_CALL(MLAHandle, run(HasName("loop.0.3"), _, _));
1248   EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _))
1249       .Times(2)
1250       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1251 
1252   // Note that we need to visit the inner loop of this added sibling before the
1253   // sibling itself!
1254   EXPECT_CALL(MLPHandle, run(HasName("loop.0.4.0"), _, _, _))
1255       .WillOnce(Invoke(getLoopAnalysisResult));
1256   EXPECT_CALL(MLAHandle, run(HasName("loop.0.4.0"), _, _));
1257   EXPECT_CALL(MLPHandle, run(HasName("loop.0.4.0"), _, _, _))
1258       .Times(2)
1259       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1260 
1261   EXPECT_CALL(MLPHandle, run(HasName("loop.0.4"), _, _, _))
1262       .WillOnce(Invoke(getLoopAnalysisResult));
1263   EXPECT_CALL(MLAHandle, run(HasName("loop.0.4"), _, _));
1264   EXPECT_CALL(MLPHandle, run(HasName("loop.0.4"), _, _, _))
1265       .Times(2)
1266       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1267 
1268   // And only now do we visit the outermost loop of the nest.
1269   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1270       .WillOnce(Invoke(getLoopAnalysisResult));
1271   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
1272   // On the second pass, we add sibling loops which become new top-level loops.
1273   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1274       .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM,
1275                            LoopStandardAnalysisResults &AR,
1276                            LPMUpdater &Updater) {
1277         auto *NewLoop = AR.LI.AllocateLoop();
1278         AR.LI.addTopLevelLoop(NewLoop);
1279         auto *NewLoop1PHBB = BasicBlock::Create(Context, "loop.1.ph", &F, &Loop2BB);
1280         auto *NewLoop1BB = BasicBlock::Create(Context, "loop.1", &F, &Loop2BB);
1281         BranchInst::Create(NewLoop1BB, NewLoop1PHBB);
1282         CreateCondBr(&Loop2PHBB, NewLoop1BB, "cond.1", NewLoop1BB);
1283         Loop0BB.getTerminator()->replaceUsesOfWith(&Loop2PHBB, NewLoop1PHBB);
1284         AR.DT.addNewBlock(NewLoop1PHBB, &Loop0BB);
1285         auto *NewDTNode = AR.DT.addNewBlock(NewLoop1BB, NewLoop1PHBB);
1286         AR.DT.changeImmediateDominator(AR.DT[&Loop2PHBB], NewDTNode);
1287         EXPECT_TRUE(AR.DT.verify());
1288         NewLoop->addBasicBlockToLoop(NewLoop1BB, AR.LI);
1289         NewLoop->verifyLoop();
1290         Updater.addSiblingLoops({NewLoop});
1291         return PreservedAnalyses::all();
1292       }));
1293   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1294       .WillOnce(Invoke(getLoopAnalysisResult));
1295 
1296   EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _))
1297       .WillOnce(Invoke(getLoopAnalysisResult));
1298   EXPECT_CALL(MLAHandle, run(HasName("loop.1"), _, _));
1299   EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _))
1300       .Times(2)
1301       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1302 
1303   EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _))
1304       .WillOnce(Invoke(getLoopAnalysisResult));
1305   EXPECT_CALL(MLAHandle, run(HasName("loop.2"), _, _));
1306   EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _))
1307       .Times(2)
1308       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1309 
1310   // Now that all the expected actions are registered, run the pipeline over
1311   // our module. All of our expectations are verified when the test finishes.
1312   MPM.run(*M, MAM);
1313 }
1314 
TEST_F(LoopPassManagerTest,LoopDeletion)1315 TEST_F(LoopPassManagerTest, LoopDeletion) {
1316   // Build a module with a single loop nest that contains one outer loop with
1317   // three subloops, and one of those with its own subloop. We will
1318   // incrementally delete all of these to test different deletion scenarios.
1319   M = parseIR(Context, "define void @f(i1* %ptr) {\n"
1320                        "entry:\n"
1321                        "  br label %loop.0\n"
1322                        "loop.0:\n"
1323                        "  %cond.0 = load volatile i1, i1* %ptr\n"
1324                        "  br i1 %cond.0, label %loop.0.0.ph, label %end\n"
1325                        "loop.0.0.ph:\n"
1326                        "  br label %loop.0.0\n"
1327                        "loop.0.0:\n"
1328                        "  %cond.0.0 = load volatile i1, i1* %ptr\n"
1329                        "  br i1 %cond.0.0, label %loop.0.0, label %loop.0.1.ph\n"
1330                        "loop.0.1.ph:\n"
1331                        "  br label %loop.0.1\n"
1332                        "loop.0.1:\n"
1333                        "  %cond.0.1 = load volatile i1, i1* %ptr\n"
1334                        "  br i1 %cond.0.1, label %loop.0.1, label %loop.0.2.ph\n"
1335                        "loop.0.2.ph:\n"
1336                        "  br label %loop.0.2\n"
1337                        "loop.0.2:\n"
1338                        "  %cond.0.2 = load volatile i1, i1* %ptr\n"
1339                        "  br i1 %cond.0.2, label %loop.0.2.0.ph, label %loop.0.latch\n"
1340                        "loop.0.2.0.ph:\n"
1341                        "  br label %loop.0.2.0\n"
1342                        "loop.0.2.0:\n"
1343                        "  %cond.0.2.0 = load volatile i1, i1* %ptr\n"
1344                        "  br i1 %cond.0.2.0, label %loop.0.2.0, label %loop.0.2.latch\n"
1345                        "loop.0.2.latch:\n"
1346                        "  br label %loop.0.2\n"
1347                        "loop.0.latch:\n"
1348                        "  br label %loop.0\n"
1349                        "end:\n"
1350                        "  ret void\n"
1351                        "}\n");
1352 
1353   // Build up variables referring into the IR so we can rewrite it below
1354   // easily.
1355   Function &F = *M->begin();
1356   ASSERT_THAT(F, HasName("f"));
1357   Argument &Ptr = *F.arg_begin();
1358   auto BBI = F.begin();
1359   BasicBlock &EntryBB = *BBI++;
1360   ASSERT_THAT(EntryBB, HasName("entry"));
1361   BasicBlock &Loop0BB = *BBI++;
1362   ASSERT_THAT(Loop0BB, HasName("loop.0"));
1363   BasicBlock &Loop00PHBB = *BBI++;
1364   ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph"));
1365   BasicBlock &Loop00BB = *BBI++;
1366   ASSERT_THAT(Loop00BB, HasName("loop.0.0"));
1367   BasicBlock &Loop01PHBB = *BBI++;
1368   ASSERT_THAT(Loop01PHBB, HasName("loop.0.1.ph"));
1369   BasicBlock &Loop01BB = *BBI++;
1370   ASSERT_THAT(Loop01BB, HasName("loop.0.1"));
1371   BasicBlock &Loop02PHBB = *BBI++;
1372   ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph"));
1373   BasicBlock &Loop02BB = *BBI++;
1374   ASSERT_THAT(Loop02BB, HasName("loop.0.2"));
1375   BasicBlock &Loop020PHBB = *BBI++;
1376   ASSERT_THAT(Loop020PHBB, HasName("loop.0.2.0.ph"));
1377   BasicBlock &Loop020BB = *BBI++;
1378   ASSERT_THAT(Loop020BB, HasName("loop.0.2.0"));
1379   BasicBlock &Loop02LatchBB = *BBI++;
1380   ASSERT_THAT(Loop02LatchBB, HasName("loop.0.2.latch"));
1381   BasicBlock &Loop0LatchBB = *BBI++;
1382   ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch"));
1383   BasicBlock &EndBB = *BBI++;
1384   ASSERT_THAT(EndBB, HasName("end"));
1385   ASSERT_THAT(BBI, F.end());
1386 
1387   // Helper to do the actual deletion of a loop. We directly encode this here
1388   // to isolate ourselves from the rest of LLVM and for simplicity. Here we can
1389   // egregiously cheat based on knowledge of the test case. For example, we
1390   // have no PHI nodes and there is always a single i-dom.
1391   auto EraseLoop = [](Loop &L, BasicBlock &IDomBB,
1392                       LoopStandardAnalysisResults &AR, LPMUpdater &Updater) {
1393     assert(L.isInnermost() && "Can only delete leaf loops with this routine!");
1394     SmallVector<BasicBlock *, 4> LoopBBs(L.block_begin(), L.block_end());
1395     Updater.markLoopAsDeleted(L, L.getName());
1396     IDomBB.getTerminator()->replaceUsesOfWith(L.getHeader(),
1397                                               L.getUniqueExitBlock());
1398     for (BasicBlock *LoopBB : LoopBBs) {
1399       SmallVector<DomTreeNode *, 4> ChildNodes(AR.DT[LoopBB]->begin(),
1400                                                AR.DT[LoopBB]->end());
1401       for (DomTreeNode *ChildNode : ChildNodes)
1402         AR.DT.changeImmediateDominator(ChildNode, AR.DT[&IDomBB]);
1403       AR.DT.eraseNode(LoopBB);
1404       AR.LI.removeBlock(LoopBB);
1405       LoopBB->dropAllReferences();
1406     }
1407     for (BasicBlock *LoopBB : LoopBBs)
1408       LoopBB->eraseFromParent();
1409 
1410     AR.LI.erase(&L);
1411   };
1412 
1413   // Build up the pass managers.
1414   ModulePassManager MPM(true);
1415   FunctionPassManager FPM(true);
1416   // We run several loop pass pipelines across the loop nest, but they all take
1417   // the same form of three mock pass runs in a loop pipeline followed by
1418   // domtree and loop verification. We use a lambda to stamp this out each
1419   // time.
1420   auto AddLoopPipelineAndVerificationPasses = [&] {
1421     LoopPassManager LPM(true);
1422     LPM.addPass(MLPHandle.getPass());
1423     LPM.addPass(MLPHandle.getPass());
1424     LPM.addPass(MLPHandle.getPass());
1425     FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM)));
1426     FPM.addPass(DominatorTreeVerifierPass());
1427     FPM.addPass(LoopVerifierPass());
1428   };
1429 
1430   // All the visit orders are deterministic so we use simple fully order
1431   // expectations.
1432   ::testing::InSequence MakeExpectationsSequenced;
1433 
1434   // We run the loop pipeline with three passes over each of the loops. When
1435   // running over the middle loop, the second pass in the pipeline deletes it.
1436   // This should prevent the third pass from visiting it but otherwise leave
1437   // the process unimpacted.
1438   AddLoopPipelineAndVerificationPasses();
1439   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
1440       .WillOnce(Invoke(getLoopAnalysisResult));
1441   EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _));
1442   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
1443       .Times(2)
1444       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1445 
1446   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
1447       .WillOnce(Invoke(getLoopAnalysisResult));
1448   EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _));
1449   EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _))
1450       .WillOnce(
1451           Invoke([&](Loop &L, LoopAnalysisManager &AM,
1452                      LoopStandardAnalysisResults &AR, LPMUpdater &Updater) {
1453             Loop *ParentL = L.getParentLoop();
1454             AR.SE.forgetLoop(&L);
1455             EraseLoop(L, Loop01PHBB, AR, Updater);
1456             ParentL->verifyLoop();
1457             return PreservedAnalyses::all();
1458           }));
1459 
1460   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _))
1461       .WillOnce(Invoke(getLoopAnalysisResult));
1462   EXPECT_CALL(MLAHandle, run(HasName("loop.0.2.0"), _, _));
1463   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _))
1464       .Times(2)
1465       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1466 
1467   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1468       .WillOnce(Invoke(getLoopAnalysisResult));
1469   EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _));
1470   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1471       .Times(2)
1472       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1473 
1474   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1475       .WillOnce(Invoke(getLoopAnalysisResult));
1476   EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _));
1477   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1478       .Times(2)
1479       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1480 
1481   // Run the loop pipeline again. This time we delete the last loop, which
1482   // contains a nested loop within it and insert a new loop into the nest. This
1483   // makes sure we can handle nested loop deletion.
1484   AddLoopPipelineAndVerificationPasses();
1485   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
1486       .Times(3)
1487       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1488 
1489   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _))
1490       .Times(3)
1491       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1492 
1493   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1494       .WillOnce(Invoke(getLoopAnalysisResult));
1495   BasicBlock *NewLoop03PHBB;
1496   EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _))
1497       .WillOnce(
1498           Invoke([&](Loop &L, LoopAnalysisManager &AM,
1499                      LoopStandardAnalysisResults &AR, LPMUpdater &Updater) {
1500             AR.SE.forgetLoop(*L.begin());
1501             EraseLoop(**L.begin(), Loop020PHBB, AR, Updater);
1502 
1503             auto *ParentL = L.getParentLoop();
1504             AR.SE.forgetLoop(&L);
1505             EraseLoop(L, Loop02PHBB, AR, Updater);
1506 
1507             // Now insert a new sibling loop.
1508             auto *NewSibling = AR.LI.AllocateLoop();
1509             ParentL->addChildLoop(NewSibling);
1510             NewLoop03PHBB =
1511                 BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB);
1512             auto *NewLoop03BB =
1513                 BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB);
1514             BranchInst::Create(NewLoop03BB, NewLoop03PHBB);
1515             auto *Cond =
1516                 new LoadInst(Type::getInt1Ty(Context), &Ptr, "cond.0.3",
1517                              /*isVolatile*/ true, NewLoop03BB);
1518             BranchInst::Create(&Loop0LatchBB, NewLoop03BB, Cond, NewLoop03BB);
1519             Loop02PHBB.getTerminator()->replaceUsesOfWith(&Loop0LatchBB,
1520                                                           NewLoop03PHBB);
1521             AR.DT.addNewBlock(NewLoop03PHBB, &Loop02PHBB);
1522             AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB);
1523             AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB],
1524                                            AR.DT[NewLoop03BB]);
1525             EXPECT_TRUE(AR.DT.verify());
1526             ParentL->addBasicBlockToLoop(NewLoop03PHBB, AR.LI);
1527             NewSibling->addBasicBlockToLoop(NewLoop03BB, AR.LI);
1528             NewSibling->verifyLoop();
1529             ParentL->verifyLoop();
1530             Updater.addSiblingLoops({NewSibling});
1531             return PreservedAnalyses::all();
1532           }));
1533 
1534   // To respect our inner-to-outer traversal order, we must visit the
1535   // newly-inserted sibling of the loop we just deleted before we visit the
1536   // outer loop. When we do so, this must compute a fresh analysis result, even
1537   // though our new loop has the same pointer value as the loop we deleted.
1538   EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _))
1539       .WillOnce(Invoke(getLoopAnalysisResult));
1540   EXPECT_CALL(MLAHandle, run(HasName("loop.0.3"), _, _));
1541   EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _))
1542       .Times(2)
1543       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1544 
1545   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1546       .Times(3)
1547       .WillRepeatedly(Invoke(getLoopAnalysisResult));
1548 
1549   // In the final loop pipeline run we delete every loop, including the last
1550   // loop of the nest. We do this again in the second pass in the pipeline, and
1551   // as a consequence we never make it to three runs on any loop. We also cover
1552   // deleting multiple loops in a single pipeline, deleting the first loop and
1553   // deleting the (last) top level loop.
1554   AddLoopPipelineAndVerificationPasses();
1555   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
1556       .WillOnce(Invoke(getLoopAnalysisResult));
1557   EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _))
1558       .WillOnce(
1559           Invoke([&](Loop &L, LoopAnalysisManager &AM,
1560                      LoopStandardAnalysisResults &AR, LPMUpdater &Updater) {
1561             AR.SE.forgetLoop(&L);
1562             EraseLoop(L, Loop00PHBB, AR, Updater);
1563             return PreservedAnalyses::all();
1564           }));
1565 
1566   EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _))
1567       .WillOnce(Invoke(getLoopAnalysisResult));
1568   EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _))
1569       .WillOnce(
1570           Invoke([&](Loop &L, LoopAnalysisManager &AM,
1571                      LoopStandardAnalysisResults &AR, LPMUpdater &Updater) {
1572             AR.SE.forgetLoop(&L);
1573             EraseLoop(L, *NewLoop03PHBB, AR, Updater);
1574             return PreservedAnalyses::all();
1575           }));
1576 
1577   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1578       .WillOnce(Invoke(getLoopAnalysisResult));
1579   EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _))
1580       .WillOnce(
1581           Invoke([&](Loop &L, LoopAnalysisManager &AM,
1582                      LoopStandardAnalysisResults &AR, LPMUpdater &Updater) {
1583             AR.SE.forgetLoop(&L);
1584             EraseLoop(L, EntryBB, AR, Updater);
1585             return PreservedAnalyses::all();
1586           }));
1587 
1588   // Add the function pass pipeline now that it is fully built up and run it
1589   // over the module's one function.
1590   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
1591   MPM.run(*M, MAM);
1592 }
1593 }
1594