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