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