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