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