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 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 64 Result(DerivedT &Handle) : Handle(&Handle) {} 65 66 public: 67 // Forward invalidation events to the mock handle. 68 bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA, 69 typename AnalysisManagerT::Invalidator &Inv) { 70 return Handle->invalidate(IR, PA, Inv); 71 } 72 }; 73 74 Result run(IRUnitT &IR, AnalysisManagerT &AM, ExtraArgTs... ExtraArgs) { 75 return Handle->run(IR, AM, ExtraArgs...); 76 } 77 }; 78 79 Analysis getAnalysis() { return Analysis(static_cast<DerivedT &>(*this)); } 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. 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.) 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 137 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 149 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 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: 168 PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, 169 ExtraArgTs... ExtraArgs) { 170 return Handle->run(IR, AM, ExtraArgs...); 171 } 172 }; 173 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.) 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 &)); 193 MockLoopPassHandle() { setDefaults(); } 194 }; 195 196 struct MockFunctionPassHandle 197 : MockPassHandleBase<MockFunctionPassHandle, Function> { 198 MOCK_METHOD2(run, PreservedAnalyses(Function &, FunctionAnalysisManager &)); 199 200 MockFunctionPassHandle() { setDefaults(); } 201 }; 202 203 struct MockModulePassHandle : MockPassHandleBase<MockModulePassHandle, Module> { 204 MOCK_METHOD2(run, PreservedAnalyses(Module &, ModuleAnalysisManager &)); 205 206 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 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 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: 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 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 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 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. 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 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 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 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 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 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