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