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