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