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 6.1 bug PR80916. 25 #if defined(__GNUC__) && __GNUC__ > 5 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__ > 5 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 = AR.LI.AllocateLoop(); 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 EXPECT_TRUE(AR.DT.verify()); 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 = AR.LI.AllocateLoop(); 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 EXPECT_TRUE(AR.DT.verify()); 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 = AR.LI.AllocateLoop(); 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 EXPECT_TRUE(AR.DT.verify()); 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[] = {AR.LI.AllocateLoop(), AR.LI.AllocateLoop(), 1185 AR.LI.AllocateLoop()}; 1186 L.getParentLoop()->addChildLoop(NewLoops[0]); 1187 L.getParentLoop()->addChildLoop(NewLoops[1]); 1188 NewLoops[1]->addChildLoop(NewLoops[2]); 1189 auto *NewLoop03PHBB = 1190 BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB); 1191 auto *NewLoop03BB = 1192 BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB); 1193 auto *NewLoop04PHBB = 1194 BasicBlock::Create(Context, "loop.0.4.ph", &F, &Loop0LatchBB); 1195 auto *NewLoop04BB = 1196 BasicBlock::Create(Context, "loop.0.4", &F, &Loop0LatchBB); 1197 auto *NewLoop040PHBB = 1198 BasicBlock::Create(Context, "loop.0.4.0.ph", &F, &Loop0LatchBB); 1199 auto *NewLoop040BB = 1200 BasicBlock::Create(Context, "loop.0.4.0", &F, &Loop0LatchBB); 1201 auto *NewLoop04LatchBB = 1202 BasicBlock::Create(Context, "loop.0.4.latch", &F, &Loop0LatchBB); 1203 Loop02BB.getTerminator()->replaceUsesOfWith(&Loop0LatchBB, NewLoop03PHBB); 1204 BranchInst::Create(NewLoop03BB, NewLoop03PHBB); 1205 CreateCondBr(NewLoop04PHBB, NewLoop03BB, "cond.0.3", NewLoop03BB); 1206 BranchInst::Create(NewLoop04BB, NewLoop04PHBB); 1207 CreateCondBr(&Loop0LatchBB, NewLoop040PHBB, "cond.0.4", NewLoop04BB); 1208 BranchInst::Create(NewLoop040BB, NewLoop040PHBB); 1209 CreateCondBr(NewLoop04LatchBB, NewLoop040BB, "cond.0.4.0", NewLoop040BB); 1210 BranchInst::Create(NewLoop04BB, NewLoop04LatchBB); 1211 AR.DT.addNewBlock(NewLoop03PHBB, &Loop02BB); 1212 AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB); 1213 AR.DT.addNewBlock(NewLoop04PHBB, NewLoop03BB); 1214 auto *NewDTNode = AR.DT.addNewBlock(NewLoop04BB, NewLoop04PHBB); 1215 AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB], NewDTNode); 1216 AR.DT.addNewBlock(NewLoop040PHBB, NewLoop04BB); 1217 AR.DT.addNewBlock(NewLoop040BB, NewLoop040PHBB); 1218 AR.DT.addNewBlock(NewLoop04LatchBB, NewLoop040BB); 1219 EXPECT_TRUE(AR.DT.verify()); 1220 L.getParentLoop()->addBasicBlockToLoop(NewLoop03PHBB, AR.LI); 1221 NewLoops[0]->addBasicBlockToLoop(NewLoop03BB, AR.LI); 1222 L.getParentLoop()->addBasicBlockToLoop(NewLoop04PHBB, AR.LI); 1223 NewLoops[1]->addBasicBlockToLoop(NewLoop04BB, AR.LI); 1224 NewLoops[1]->addBasicBlockToLoop(NewLoop040PHBB, AR.LI); 1225 NewLoops[2]->addBasicBlockToLoop(NewLoop040BB, AR.LI); 1226 NewLoops[1]->addBasicBlockToLoop(NewLoop04LatchBB, AR.LI); 1227 L.getParentLoop()->verifyLoop(); 1228 Updater.addSiblingLoops({NewLoops[0], NewLoops[1]}); 1229 return PreservedAnalyses::all(); 1230 })); 1231 1232 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1233 .WillOnce(Invoke(getLoopAnalysisResult)); 1234 EXPECT_CALL(MLAHandle, run(HasName("loop.0.3"), _, _)); 1235 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1236 .Times(2) 1237 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1238 1239 // Note that we need to visit the inner loop of this added sibling before the 1240 // sibling itself! 1241 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4.0"), _, _, _)) 1242 .WillOnce(Invoke(getLoopAnalysisResult)); 1243 EXPECT_CALL(MLAHandle, run(HasName("loop.0.4.0"), _, _)); 1244 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4.0"), _, _, _)) 1245 .Times(2) 1246 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1247 1248 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4"), _, _, _)) 1249 .WillOnce(Invoke(getLoopAnalysisResult)); 1250 EXPECT_CALL(MLAHandle, run(HasName("loop.0.4"), _, _)); 1251 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4"), _, _, _)) 1252 .Times(2) 1253 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1254 1255 // And only now do we visit the outermost loop of the nest. 1256 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1257 .WillOnce(Invoke(getLoopAnalysisResult)); 1258 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 1259 // On the second pass, we add sibling loops which become new top-level loops. 1260 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1261 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 1262 LoopStandardAnalysisResults &AR, 1263 LPMUpdater &Updater) { 1264 auto *NewLoop = AR.LI.AllocateLoop(); 1265 AR.LI.addTopLevelLoop(NewLoop); 1266 auto *NewLoop1PHBB = BasicBlock::Create(Context, "loop.1.ph", &F, &Loop2BB); 1267 auto *NewLoop1BB = BasicBlock::Create(Context, "loop.1", &F, &Loop2BB); 1268 BranchInst::Create(NewLoop1BB, NewLoop1PHBB); 1269 CreateCondBr(&Loop2PHBB, NewLoop1BB, "cond.1", NewLoop1BB); 1270 Loop0BB.getTerminator()->replaceUsesOfWith(&Loop2PHBB, NewLoop1PHBB); 1271 AR.DT.addNewBlock(NewLoop1PHBB, &Loop0BB); 1272 auto *NewDTNode = AR.DT.addNewBlock(NewLoop1BB, NewLoop1PHBB); 1273 AR.DT.changeImmediateDominator(AR.DT[&Loop2PHBB], NewDTNode); 1274 EXPECT_TRUE(AR.DT.verify()); 1275 NewLoop->addBasicBlockToLoop(NewLoop1BB, AR.LI); 1276 NewLoop->verifyLoop(); 1277 Updater.addSiblingLoops({NewLoop}); 1278 return PreservedAnalyses::all(); 1279 })); 1280 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1281 .WillOnce(Invoke(getLoopAnalysisResult)); 1282 1283 EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _)) 1284 .WillOnce(Invoke(getLoopAnalysisResult)); 1285 EXPECT_CALL(MLAHandle, run(HasName("loop.1"), _, _)); 1286 EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _)) 1287 .Times(2) 1288 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1289 1290 EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _)) 1291 .WillOnce(Invoke(getLoopAnalysisResult)); 1292 EXPECT_CALL(MLAHandle, run(HasName("loop.2"), _, _)); 1293 EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _)) 1294 .Times(2) 1295 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1296 1297 // Now that all the expected actions are registered, run the pipeline over 1298 // our module. All of our expectations are verified when the test finishes. 1299 MPM.run(*M, MAM); 1300 } 1301 1302 TEST_F(LoopPassManagerTest, LoopDeletion) { 1303 // Build a module with a single loop nest that contains one outer loop with 1304 // three subloops, and one of those with its own subloop. We will 1305 // incrementally delete all of these to test different deletion scenarios. 1306 M = parseIR(Context, "define void @f(i1* %ptr) {\n" 1307 "entry:\n" 1308 " br label %loop.0\n" 1309 "loop.0:\n" 1310 " %cond.0 = load volatile i1, i1* %ptr\n" 1311 " br i1 %cond.0, label %loop.0.0.ph, label %end\n" 1312 "loop.0.0.ph:\n" 1313 " br label %loop.0.0\n" 1314 "loop.0.0:\n" 1315 " %cond.0.0 = load volatile i1, i1* %ptr\n" 1316 " br i1 %cond.0.0, label %loop.0.0, label %loop.0.1.ph\n" 1317 "loop.0.1.ph:\n" 1318 " br label %loop.0.1\n" 1319 "loop.0.1:\n" 1320 " %cond.0.1 = load volatile i1, i1* %ptr\n" 1321 " br i1 %cond.0.1, label %loop.0.1, label %loop.0.2.ph\n" 1322 "loop.0.2.ph:\n" 1323 " br label %loop.0.2\n" 1324 "loop.0.2:\n" 1325 " %cond.0.2 = load volatile i1, i1* %ptr\n" 1326 " br i1 %cond.0.2, label %loop.0.2.0.ph, label %loop.0.latch\n" 1327 "loop.0.2.0.ph:\n" 1328 " br label %loop.0.2.0\n" 1329 "loop.0.2.0:\n" 1330 " %cond.0.2.0 = load volatile i1, i1* %ptr\n" 1331 " br i1 %cond.0.2.0, label %loop.0.2.0, label %loop.0.2.latch\n" 1332 "loop.0.2.latch:\n" 1333 " br label %loop.0.2\n" 1334 "loop.0.latch:\n" 1335 " br label %loop.0\n" 1336 "end:\n" 1337 " ret void\n" 1338 "}\n"); 1339 1340 // Build up variables referring into the IR so we can rewrite it below 1341 // easily. 1342 Function &F = *M->begin(); 1343 ASSERT_THAT(F, HasName("f")); 1344 Argument &Ptr = *F.arg_begin(); 1345 auto BBI = F.begin(); 1346 BasicBlock &EntryBB = *BBI++; 1347 ASSERT_THAT(EntryBB, HasName("entry")); 1348 BasicBlock &Loop0BB = *BBI++; 1349 ASSERT_THAT(Loop0BB, HasName("loop.0")); 1350 BasicBlock &Loop00PHBB = *BBI++; 1351 ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph")); 1352 BasicBlock &Loop00BB = *BBI++; 1353 ASSERT_THAT(Loop00BB, HasName("loop.0.0")); 1354 BasicBlock &Loop01PHBB = *BBI++; 1355 ASSERT_THAT(Loop01PHBB, HasName("loop.0.1.ph")); 1356 BasicBlock &Loop01BB = *BBI++; 1357 ASSERT_THAT(Loop01BB, HasName("loop.0.1")); 1358 BasicBlock &Loop02PHBB = *BBI++; 1359 ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph")); 1360 BasicBlock &Loop02BB = *BBI++; 1361 ASSERT_THAT(Loop02BB, HasName("loop.0.2")); 1362 BasicBlock &Loop020PHBB = *BBI++; 1363 ASSERT_THAT(Loop020PHBB, HasName("loop.0.2.0.ph")); 1364 BasicBlock &Loop020BB = *BBI++; 1365 ASSERT_THAT(Loop020BB, HasName("loop.0.2.0")); 1366 BasicBlock &Loop02LatchBB = *BBI++; 1367 ASSERT_THAT(Loop02LatchBB, HasName("loop.0.2.latch")); 1368 BasicBlock &Loop0LatchBB = *BBI++; 1369 ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch")); 1370 BasicBlock &EndBB = *BBI++; 1371 ASSERT_THAT(EndBB, HasName("end")); 1372 ASSERT_THAT(BBI, F.end()); 1373 1374 // Helper to do the actual deletion of a loop. We directly encode this here 1375 // to isolate ourselves from the rest of LLVM and for simplicity. Here we can 1376 // egregiously cheat based on knowledge of the test case. For example, we 1377 // have no PHI nodes and there is always a single i-dom. 1378 auto EraseLoop = [](Loop &L, BasicBlock &IDomBB, 1379 LoopStandardAnalysisResults &AR, 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, L.getName()); 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 AR.LI.erase(&L); 1398 }; 1399 1400 // Build up the pass managers. 1401 ModulePassManager MPM(true); 1402 FunctionPassManager FPM(true); 1403 // We run several loop pass pipelines across the loop nest, but they all take 1404 // the same form of three mock pass runs in a loop pipeline followed by 1405 // domtree and loop verification. We use a lambda to stamp this out each 1406 // time. 1407 auto AddLoopPipelineAndVerificationPasses = [&] { 1408 LoopPassManager LPM(true); 1409 LPM.addPass(MLPHandle.getPass()); 1410 LPM.addPass(MLPHandle.getPass()); 1411 LPM.addPass(MLPHandle.getPass()); 1412 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 1413 FPM.addPass(DominatorTreeVerifierPass()); 1414 FPM.addPass(LoopVerifierPass()); 1415 }; 1416 1417 // All the visit orders are deterministic so we use simple fully order 1418 // expectations. 1419 ::testing::InSequence MakeExpectationsSequenced; 1420 1421 // We run the loop pipeline with three passes over each of the loops. When 1422 // running over the middle loop, the second pass in the pipeline deletes it. 1423 // This should prevent the third pass from visiting it but otherwise leave 1424 // the process unimpacted. 1425 AddLoopPipelineAndVerificationPasses(); 1426 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1427 .WillOnce(Invoke(getLoopAnalysisResult)); 1428 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 1429 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1430 .Times(2) 1431 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1432 1433 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1434 .WillOnce(Invoke(getLoopAnalysisResult)); 1435 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 1436 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1437 .WillOnce( 1438 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1439 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1440 Loop *ParentL = L.getParentLoop(); 1441 AR.SE.forgetLoop(&L); 1442 EraseLoop(L, Loop01PHBB, AR, Updater); 1443 ParentL->verifyLoop(); 1444 return PreservedAnalyses::all(); 1445 })); 1446 1447 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _)) 1448 .WillOnce(Invoke(getLoopAnalysisResult)); 1449 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2.0"), _, _)); 1450 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _)) 1451 .Times(2) 1452 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1453 1454 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1455 .WillOnce(Invoke(getLoopAnalysisResult)); 1456 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _)); 1457 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1458 .Times(2) 1459 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1460 1461 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1462 .WillOnce(Invoke(getLoopAnalysisResult)); 1463 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 1464 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1465 .Times(2) 1466 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1467 1468 // Run the loop pipeline again. This time we delete the last loop, which 1469 // contains a nested loop within it and insert a new loop into the nest. This 1470 // makes sure we can handle nested loop deletion. 1471 AddLoopPipelineAndVerificationPasses(); 1472 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1473 .Times(3) 1474 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1475 1476 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _)) 1477 .Times(3) 1478 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1479 1480 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1481 .WillOnce(Invoke(getLoopAnalysisResult)); 1482 BasicBlock *NewLoop03PHBB; 1483 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1484 .WillOnce( 1485 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1486 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1487 AR.SE.forgetLoop(*L.begin()); 1488 EraseLoop(**L.begin(), Loop020PHBB, AR, Updater); 1489 1490 auto *ParentL = L.getParentLoop(); 1491 AR.SE.forgetLoop(&L); 1492 EraseLoop(L, Loop02PHBB, AR, Updater); 1493 1494 // Now insert a new sibling loop. 1495 auto *NewSibling = AR.LI.AllocateLoop(); 1496 ParentL->addChildLoop(NewSibling); 1497 NewLoop03PHBB = 1498 BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB); 1499 auto *NewLoop03BB = 1500 BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB); 1501 BranchInst::Create(NewLoop03BB, NewLoop03PHBB); 1502 auto *Cond = new LoadInst(&Ptr, "cond.0.3", /*isVolatile*/ true, 1503 NewLoop03BB); 1504 BranchInst::Create(&Loop0LatchBB, NewLoop03BB, Cond, NewLoop03BB); 1505 Loop02PHBB.getTerminator()->replaceUsesOfWith(&Loop0LatchBB, 1506 NewLoop03PHBB); 1507 AR.DT.addNewBlock(NewLoop03PHBB, &Loop02PHBB); 1508 AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB); 1509 AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB], 1510 AR.DT[NewLoop03BB]); 1511 EXPECT_TRUE(AR.DT.verify()); 1512 ParentL->addBasicBlockToLoop(NewLoop03PHBB, AR.LI); 1513 NewSibling->addBasicBlockToLoop(NewLoop03BB, AR.LI); 1514 NewSibling->verifyLoop(); 1515 ParentL->verifyLoop(); 1516 Updater.addSiblingLoops({NewSibling}); 1517 return PreservedAnalyses::all(); 1518 })); 1519 1520 // To respect our inner-to-outer traversal order, we must visit the 1521 // newly-inserted sibling of the loop we just deleted before we visit the 1522 // outer loop. When we do so, this must compute a fresh analysis result, even 1523 // though our new loop has the same pointer value as the loop we deleted. 1524 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1525 .WillOnce(Invoke(getLoopAnalysisResult)); 1526 EXPECT_CALL(MLAHandle, run(HasName("loop.0.3"), _, _)); 1527 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1528 .Times(2) 1529 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1530 1531 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1532 .Times(3) 1533 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1534 1535 // In the final loop pipeline run we delete every loop, including the last 1536 // loop of the nest. We do this again in the second pass in the pipeline, and 1537 // as a consequence we never make it to three runs on any loop. We also cover 1538 // deleting multiple loops in a single pipeline, deleting the first loop and 1539 // deleting the (last) top level loop. 1540 AddLoopPipelineAndVerificationPasses(); 1541 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1542 .WillOnce(Invoke(getLoopAnalysisResult)); 1543 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1544 .WillOnce( 1545 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1546 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1547 AR.SE.forgetLoop(&L); 1548 EraseLoop(L, Loop00PHBB, AR, Updater); 1549 return PreservedAnalyses::all(); 1550 })); 1551 1552 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1553 .WillOnce(Invoke(getLoopAnalysisResult)); 1554 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1555 .WillOnce( 1556 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1557 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1558 AR.SE.forgetLoop(&L); 1559 EraseLoop(L, *NewLoop03PHBB, AR, Updater); 1560 return PreservedAnalyses::all(); 1561 })); 1562 1563 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1564 .WillOnce(Invoke(getLoopAnalysisResult)); 1565 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1566 .WillOnce( 1567 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1568 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1569 AR.SE.forgetLoop(&L); 1570 EraseLoop(L, EntryBB, AR, Updater); 1571 return PreservedAnalyses::all(); 1572 })); 1573 1574 // Add the function pass pipeline now that it is fully built up and run it 1575 // over the module's one function. 1576 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 1577 MPM.run(*M, MAM); 1578 } 1579 } 1580
