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 // Register required pass instrumentation analysis. 312 LAM.registerPass([&] { return PassInstrumentationAnalysis(); }); 313 FAM.registerPass([&] { return PassInstrumentationAnalysis(); }); 314 MAM.registerPass([&] { return PassInstrumentationAnalysis(); }); 315 316 // Cross-register proxies. 317 LAM.registerPass([&] { return FunctionAnalysisManagerLoopProxy(FAM); }); 318 FAM.registerPass([&] { return LoopAnalysisManagerFunctionProxy(LAM); }); 319 FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); }); 320 MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); }); 321 } 322 }; 323 324 TEST_F(LoopPassManagerTest, Basic) { 325 ModulePassManager MPM(true); 326 ::testing::InSequence MakeExpectationsSequenced; 327 328 // First we just visit all the loops in all the functions and get their 329 // analysis results. This will run the analysis a total of four times, 330 // once for each loop. 331 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 332 .WillOnce(Invoke(getLoopAnalysisResult)); 333 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 334 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 335 .WillOnce(Invoke(getLoopAnalysisResult)); 336 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 337 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 338 .WillOnce(Invoke(getLoopAnalysisResult)); 339 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 340 EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _)) 341 .WillOnce(Invoke(getLoopAnalysisResult)); 342 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); 343 // Wire the loop pass through pass managers into the module pipeline. 344 { 345 LoopPassManager LPM(true); 346 LPM.addPass(MLPHandle.getPass()); 347 FunctionPassManager FPM(true); 348 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 349 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 350 } 351 352 // Next we run two passes over the loops. The first one invalidates the 353 // analyses for one loop, the second ones try to get the analysis results. 354 // This should force only one analysis to re-run within the loop PM, but will 355 // also invalidate everything after the loop pass manager finishes. 356 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 357 .WillOnce(DoDefault()) 358 .WillOnce(Invoke(getLoopAnalysisResult)); 359 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 360 .WillOnce(InvokeWithoutArgs([] { return PreservedAnalyses::none(); })) 361 .WillOnce(Invoke(getLoopAnalysisResult)); 362 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 363 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 364 .WillOnce(DoDefault()) 365 .WillOnce(Invoke(getLoopAnalysisResult)); 366 EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _)) 367 .WillOnce(DoDefault()) 368 .WillOnce(Invoke(getLoopAnalysisResult)); 369 // Wire two loop pass runs into the module pipeline. 370 { 371 LoopPassManager LPM(true); 372 LPM.addPass(MLPHandle.getPass()); 373 LPM.addPass(MLPHandle.getPass()); 374 FunctionPassManager FPM(true); 375 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 376 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 377 } 378 379 // And now run the pipeline across the module. 380 MPM.run(*M, MAM); 381 } 382 383 TEST_F(LoopPassManagerTest, FunctionPassInvalidationOfLoopAnalyses) { 384 ModulePassManager MPM(true); 385 FunctionPassManager FPM(true); 386 // We process each function completely in sequence. 387 ::testing::Sequence FSequence, GSequence; 388 389 // First, force the analysis result to be computed for each loop. 390 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)) 391 .InSequence(FSequence) 392 .WillOnce(DoDefault()); 393 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)) 394 .InSequence(FSequence) 395 .WillOnce(DoDefault()); 396 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)) 397 .InSequence(FSequence) 398 .WillOnce(DoDefault()); 399 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)) 400 .InSequence(GSequence) 401 .WillOnce(DoDefault()); 402 FPM.addPass(createFunctionToLoopPassAdaptor( 403 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 404 405 // No need to re-run if we require again from a fresh loop pass manager. 406 FPM.addPass(createFunctionToLoopPassAdaptor( 407 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 408 409 // For 'f', preserve most things but not the specific loop analyses. 410 EXPECT_CALL(MFPHandle, run(HasName("f"), _)) 411 .InSequence(FSequence) 412 .WillOnce(Return(getLoopPassPreservedAnalyses())); 413 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.0"), _, _)) 414 .InSequence(FSequence) 415 .WillOnce(DoDefault()); 416 // On one loop, skip the invalidation (as though we did an internal update). 417 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.1"), _, _)) 418 .InSequence(FSequence) 419 .WillOnce(Return(false)); 420 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0"), _, _)) 421 .InSequence(FSequence) 422 .WillOnce(DoDefault()); 423 // Now two loops still have to be recomputed. 424 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)) 425 .InSequence(FSequence) 426 .WillOnce(DoDefault()); 427 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)) 428 .InSequence(FSequence) 429 .WillOnce(DoDefault()); 430 // Preserve things in the second function to ensure invalidation remains 431 // isolated to one function. 432 EXPECT_CALL(MFPHandle, run(HasName("g"), _)) 433 .InSequence(GSequence) 434 .WillOnce(DoDefault()); 435 FPM.addPass(MFPHandle.getPass()); 436 FPM.addPass(createFunctionToLoopPassAdaptor( 437 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 438 439 EXPECT_CALL(MFPHandle, run(HasName("f"), _)) 440 .InSequence(FSequence) 441 .WillOnce(DoDefault()); 442 // For 'g', fail to preserve anything, causing the loops themselves to be 443 // cleared. We don't get an invalidation event here as the loop is gone, but 444 // we should still have to recompute the analysis. 445 EXPECT_CALL(MFPHandle, run(HasName("g"), _)) 446 .InSequence(GSequence) 447 .WillOnce(Return(PreservedAnalyses::none())); 448 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)) 449 .InSequence(GSequence) 450 .WillOnce(DoDefault()); 451 FPM.addPass(MFPHandle.getPass()); 452 FPM.addPass(createFunctionToLoopPassAdaptor( 453 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 454 455 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 456 457 // Verify with a separate function pass run that we didn't mess up 'f's 458 // cache. No analysis runs should be necessary here. 459 MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( 460 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()))); 461 462 MPM.run(*M, MAM); 463 } 464 465 TEST_F(LoopPassManagerTest, ModulePassInvalidationOfLoopAnalyses) { 466 ModulePassManager MPM(true); 467 ::testing::InSequence MakeExpectationsSequenced; 468 469 // First, force the analysis result to be computed for each loop. 470 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 471 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 472 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 473 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); 474 MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( 475 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()))); 476 477 // Walking all the way out and all the way back in doesn't re-run the 478 // analysis. 479 MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( 480 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()))); 481 482 // But a module pass that doesn't preserve the actual mock loop analysis 483 // invalidates all the way down and forces recomputing. 484 EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] { 485 auto PA = getLoopPassPreservedAnalyses(); 486 PA.preserve<FunctionAnalysisManagerModuleProxy>(); 487 return PA; 488 })); 489 // All the loop analyses from both functions get invalidated before we 490 // recompute anything. 491 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.0"), _, _)); 492 // On one loop, again skip the invalidation (as though we did an internal 493 // update). 494 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.1"), _, _)) 495 .WillOnce(Return(false)); 496 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0"), _, _)); 497 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.g.0"), _, _)); 498 // Now all but one of the loops gets re-analyzed. 499 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 500 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 501 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); 502 MPM.addPass(MMPHandle.getPass()); 503 MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( 504 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()))); 505 506 // Verify that the cached values persist. 507 MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( 508 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()))); 509 510 // Now we fail to preserve the loop analysis and observe that the loop 511 // analyses are cleared (so no invalidation event) as the loops themselves 512 // are no longer valid. 513 EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] { 514 auto PA = PreservedAnalyses::none(); 515 PA.preserve<FunctionAnalysisManagerModuleProxy>(); 516 return PA; 517 })); 518 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 519 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 520 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 521 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); 522 MPM.addPass(MMPHandle.getPass()); 523 MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( 524 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()))); 525 526 // Verify that the cached values persist. 527 MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( 528 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()))); 529 530 // Next, check that even if we preserve everything within the function itelf, 531 // if the function's module pass proxy isn't preserved and the potential set 532 // of functions changes, the clear reaches the loop analyses as well. This 533 // will again trigger re-runs but not invalidation events. 534 EXPECT_CALL(MMPHandle, run(_, _)).WillOnce(InvokeWithoutArgs([] { 535 auto PA = PreservedAnalyses::none(); 536 PA.preserveSet<AllAnalysesOn<Function>>(); 537 PA.preserveSet<AllAnalysesOn<Loop>>(); 538 return PA; 539 })); 540 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 541 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 542 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 543 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); 544 MPM.addPass(MMPHandle.getPass()); 545 MPM.addPass(createModuleToFunctionPassAdaptor(createFunctionToLoopPassAdaptor( 546 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>()))); 547 548 MPM.run(*M, MAM); 549 } 550 551 // Test that if any of the bundled analyses provided in the LPM's signature 552 // become invalid, the analysis proxy itself becomes invalid and we clear all 553 // loop analysis results. 554 TEST_F(LoopPassManagerTest, InvalidationOfBundledAnalyses) { 555 ModulePassManager MPM(true); 556 FunctionPassManager FPM(true); 557 ::testing::InSequence MakeExpectationsSequenced; 558 559 // First, force the analysis result to be computed for each loop. 560 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 561 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 562 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 563 FPM.addPass(createFunctionToLoopPassAdaptor( 564 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 565 566 // No need to re-run if we require again from a fresh loop pass manager. 567 FPM.addPass(createFunctionToLoopPassAdaptor( 568 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 569 570 // Preserving everything but the loop analyses themselves results in 571 // invalidation and running. 572 EXPECT_CALL(MFPHandle, run(HasName("f"), _)) 573 .WillOnce(Return(getLoopPassPreservedAnalyses())); 574 EXPECT_CALL(MLAHandle, invalidate(_, _, _)).Times(3); 575 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 576 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 577 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 578 FPM.addPass(MFPHandle.getPass()); 579 FPM.addPass(createFunctionToLoopPassAdaptor( 580 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 581 582 // The rest don't invalidate analyses, they only trigger re-runs because we 583 // clear the cache completely. 584 EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { 585 auto PA = PreservedAnalyses::none(); 586 // Not preserving `AAManager`. 587 PA.preserve<DominatorTreeAnalysis>(); 588 PA.preserve<LoopAnalysis>(); 589 PA.preserve<LoopAnalysisManagerFunctionProxy>(); 590 PA.preserve<ScalarEvolutionAnalysis>(); 591 return PA; 592 })); 593 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 594 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 595 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 596 FPM.addPass(MFPHandle.getPass()); 597 FPM.addPass(createFunctionToLoopPassAdaptor( 598 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 599 600 EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { 601 auto PA = PreservedAnalyses::none(); 602 PA.preserve<AAManager>(); 603 // Not preserving `DominatorTreeAnalysis`. 604 PA.preserve<LoopAnalysis>(); 605 PA.preserve<LoopAnalysisManagerFunctionProxy>(); 606 PA.preserve<ScalarEvolutionAnalysis>(); 607 return PA; 608 })); 609 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 610 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 611 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 612 FPM.addPass(MFPHandle.getPass()); 613 FPM.addPass(createFunctionToLoopPassAdaptor( 614 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 615 616 EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { 617 auto PA = PreservedAnalyses::none(); 618 PA.preserve<AAManager>(); 619 PA.preserve<DominatorTreeAnalysis>(); 620 // Not preserving the `LoopAnalysis`. 621 PA.preserve<LoopAnalysisManagerFunctionProxy>(); 622 PA.preserve<ScalarEvolutionAnalysis>(); 623 return PA; 624 })); 625 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 626 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 627 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 628 FPM.addPass(MFPHandle.getPass()); 629 FPM.addPass(createFunctionToLoopPassAdaptor( 630 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 631 632 EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { 633 auto PA = PreservedAnalyses::none(); 634 PA.preserve<AAManager>(); 635 PA.preserve<DominatorTreeAnalysis>(); 636 PA.preserve<LoopAnalysis>(); 637 // Not preserving the `LoopAnalysisManagerFunctionProxy`. 638 PA.preserve<ScalarEvolutionAnalysis>(); 639 return PA; 640 })); 641 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 642 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 643 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 644 FPM.addPass(MFPHandle.getPass()); 645 FPM.addPass(createFunctionToLoopPassAdaptor( 646 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 647 648 EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { 649 auto PA = PreservedAnalyses::none(); 650 PA.preserve<AAManager>(); 651 PA.preserve<DominatorTreeAnalysis>(); 652 PA.preserve<LoopAnalysis>(); 653 PA.preserve<LoopAnalysisManagerFunctionProxy>(); 654 // Not preserving `ScalarEvolutionAnalysis`. 655 return PA; 656 })); 657 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 658 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 659 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 660 FPM.addPass(MFPHandle.getPass()); 661 FPM.addPass(createFunctionToLoopPassAdaptor( 662 RequireAnalysisLoopPass<MockLoopAnalysisHandle::Analysis>())); 663 664 // After all the churn on 'f', we'll compute the loop analysis results for 665 // 'g' once with a requires pass and then run our mock pass over g a bunch 666 // but just get cached results each time. 667 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); 668 EXPECT_CALL(MFPHandle, run(HasName("g"), _)).Times(6); 669 670 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 671 MPM.run(*M, MAM); 672 } 673 674 TEST_F(LoopPassManagerTest, IndirectInvalidation) { 675 // We need two distinct analysis types and handles. 676 enum { A, B }; 677 MockLoopAnalysisHandleTemplate<A> MLAHandleA; 678 MockLoopAnalysisHandleTemplate<B> MLAHandleB; 679 LAM.registerPass([&] { return MLAHandleA.getAnalysis(); }); 680 LAM.registerPass([&] { return MLAHandleB.getAnalysis(); }); 681 typedef decltype(MLAHandleA)::Analysis AnalysisA; 682 typedef decltype(MLAHandleB)::Analysis AnalysisB; 683 684 // Set up AnalysisA to depend on our AnalysisB. For testing purposes we just 685 // need to get the AnalysisB results in AnalysisA's run method and check if 686 // AnalysisB gets invalidated in AnalysisA's invalidate method. 687 ON_CALL(MLAHandleA, run(_, _, _)) 688 .WillByDefault(Invoke([&](Loop &L, LoopAnalysisManager &AM, 689 LoopStandardAnalysisResults &AR) { 690 (void)AM.getResult<AnalysisB>(L, AR); 691 return MLAHandleA.getResult(); 692 })); 693 ON_CALL(MLAHandleA, invalidate(_, _, _)) 694 .WillByDefault(Invoke([](Loop &L, const PreservedAnalyses &PA, 695 LoopAnalysisManager::Invalidator &Inv) { 696 auto PAC = PA.getChecker<AnalysisA>(); 697 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Loop>>()) || 698 Inv.invalidate<AnalysisB>(L, PA); 699 })); 700 701 ::testing::InSequence MakeExpectationsSequenced; 702 703 // Compute the analyses across all of 'f' first. 704 EXPECT_CALL(MLAHandleA, run(HasName("loop.0.0"), _, _)); 705 EXPECT_CALL(MLAHandleB, run(HasName("loop.0.0"), _, _)); 706 EXPECT_CALL(MLAHandleA, run(HasName("loop.0.1"), _, _)); 707 EXPECT_CALL(MLAHandleB, run(HasName("loop.0.1"), _, _)); 708 EXPECT_CALL(MLAHandleA, run(HasName("loop.0"), _, _)); 709 EXPECT_CALL(MLAHandleB, run(HasName("loop.0"), _, _)); 710 711 // Now we invalidate AnalysisB (but not AnalysisA) for one of the loops and 712 // preserve everything for the rest. This in turn triggers that one loop to 713 // recompute both AnalysisB *and* AnalysisA if indirect invalidation is 714 // working. 715 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 716 .WillOnce(InvokeWithoutArgs([] { 717 auto PA = getLoopPassPreservedAnalyses(); 718 // Specifically preserve AnalysisA so that it would survive if it 719 // didn't depend on AnalysisB. 720 PA.preserve<AnalysisA>(); 721 return PA; 722 })); 723 // It happens that AnalysisB is invalidated first. That shouldn't matter 724 // though, and we should still call AnalysisA's invalidation. 725 EXPECT_CALL(MLAHandleB, invalidate(HasName("loop.0.0"), _, _)); 726 EXPECT_CALL(MLAHandleA, invalidate(HasName("loop.0.0"), _, _)); 727 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 728 .WillOnce(Invoke([](Loop &L, LoopAnalysisManager &AM, 729 LoopStandardAnalysisResults &AR, LPMUpdater &) { 730 (void)AM.getResult<AnalysisA>(L, AR); 731 return PreservedAnalyses::all(); 732 })); 733 EXPECT_CALL(MLAHandleA, run(HasName("loop.0.0"), _, _)); 734 EXPECT_CALL(MLAHandleB, run(HasName("loop.0.0"), _, _)); 735 // The rest of the loops should run and get cached results. 736 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 737 .Times(2) 738 .WillRepeatedly(Invoke([](Loop &L, LoopAnalysisManager &AM, 739 LoopStandardAnalysisResults &AR, LPMUpdater &) { 740 (void)AM.getResult<AnalysisA>(L, AR); 741 return PreservedAnalyses::all(); 742 })); 743 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 744 .Times(2) 745 .WillRepeatedly(Invoke([](Loop &L, LoopAnalysisManager &AM, 746 LoopStandardAnalysisResults &AR, LPMUpdater &) { 747 (void)AM.getResult<AnalysisA>(L, AR); 748 return PreservedAnalyses::all(); 749 })); 750 751 // The run over 'g' should be boring, with us just computing the analyses once 752 // up front and then running loop passes and getting cached results. 753 EXPECT_CALL(MLAHandleA, run(HasName("loop.g.0"), _, _)); 754 EXPECT_CALL(MLAHandleB, run(HasName("loop.g.0"), _, _)); 755 EXPECT_CALL(MLPHandle, run(HasName("loop.g.0"), _, _, _)) 756 .Times(2) 757 .WillRepeatedly(Invoke([](Loop &L, LoopAnalysisManager &AM, 758 LoopStandardAnalysisResults &AR, LPMUpdater &) { 759 (void)AM.getResult<AnalysisA>(L, AR); 760 return PreservedAnalyses::all(); 761 })); 762 763 // Build the pipeline and run it. 764 ModulePassManager MPM(true); 765 FunctionPassManager FPM(true); 766 FPM.addPass( 767 createFunctionToLoopPassAdaptor(RequireAnalysisLoopPass<AnalysisA>())); 768 LoopPassManager LPM(true); 769 LPM.addPass(MLPHandle.getPass()); 770 LPM.addPass(MLPHandle.getPass()); 771 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 772 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 773 MPM.run(*M, MAM); 774 } 775 776 TEST_F(LoopPassManagerTest, IndirectOuterPassInvalidation) { 777 typedef decltype(MLAHandle)::Analysis LoopAnalysis; 778 779 MockFunctionAnalysisHandle MFAHandle; 780 FAM.registerPass([&] { return MFAHandle.getAnalysis(); }); 781 typedef decltype(MFAHandle)::Analysis FunctionAnalysis; 782 783 // Set up the loop analysis to depend on both the function and module 784 // analysis. 785 ON_CALL(MLAHandle, run(_, _, _)) 786 .WillByDefault(Invoke([&](Loop &L, LoopAnalysisManager &AM, 787 LoopStandardAnalysisResults &AR) { 788 auto &FAMP = AM.getResult<FunctionAnalysisManagerLoopProxy>(L, AR); 789 auto &FAM = FAMP.getManager(); 790 Function &F = *L.getHeader()->getParent(); 791 if (FAM.getCachedResult<FunctionAnalysis>(F)) 792 FAMP.registerOuterAnalysisInvalidation<FunctionAnalysis, 793 LoopAnalysis>(); 794 return MLAHandle.getResult(); 795 })); 796 797 ::testing::InSequence MakeExpectationsSequenced; 798 799 // Compute the analyses across all of 'f' first. 800 EXPECT_CALL(MFPHandle, run(HasName("f"), _)) 801 .WillOnce(Invoke([](Function &F, FunctionAnalysisManager &AM) { 802 // Force the computing of the function analysis so it is available in 803 // this function. 804 (void)AM.getResult<FunctionAnalysis>(F); 805 return PreservedAnalyses::all(); 806 })); 807 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 808 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 809 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 810 811 // Now invalidate the function analysis but preserve the loop analyses. 812 // This should trigger immediate invalidation of the loop analyses, despite 813 // the fact that they were preserved. 814 EXPECT_CALL(MFPHandle, run(HasName("f"), _)).WillOnce(InvokeWithoutArgs([] { 815 auto PA = getLoopPassPreservedAnalyses(); 816 PA.preserveSet<AllAnalysesOn<Loop>>(); 817 return PA; 818 })); 819 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.0"), _, _)); 820 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0.1"), _, _)); 821 EXPECT_CALL(MLAHandle, invalidate(HasName("loop.0"), _, _)); 822 823 // And re-running a requires pass recomputes them. 824 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 825 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 826 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 827 828 // When we run over 'g' we don't populate the cache with the function 829 // analysis. 830 EXPECT_CALL(MFPHandle, run(HasName("g"), _)) 831 .WillOnce(Return(PreservedAnalyses::all())); 832 EXPECT_CALL(MLAHandle, run(HasName("loop.g.0"), _, _)); 833 834 // Which means that no extra invalidation occurs and cached values are used. 835 EXPECT_CALL(MFPHandle, run(HasName("g"), _)).WillOnce(InvokeWithoutArgs([] { 836 auto PA = getLoopPassPreservedAnalyses(); 837 PA.preserveSet<AllAnalysesOn<Loop>>(); 838 return PA; 839 })); 840 841 // Build the pipeline and run it. 842 ModulePassManager MPM(true); 843 FunctionPassManager FPM(true); 844 FPM.addPass(MFPHandle.getPass()); 845 FPM.addPass( 846 createFunctionToLoopPassAdaptor(RequireAnalysisLoopPass<LoopAnalysis>())); 847 FPM.addPass(MFPHandle.getPass()); 848 FPM.addPass( 849 createFunctionToLoopPassAdaptor(RequireAnalysisLoopPass<LoopAnalysis>())); 850 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 851 MPM.run(*M, MAM); 852 } 853 854 TEST_F(LoopPassManagerTest, LoopChildInsertion) { 855 // Super boring module with three loops in a single loop nest. 856 M = parseIR(Context, "define void @f(i1* %ptr) {\n" 857 "entry:\n" 858 " br label %loop.0\n" 859 "loop.0:\n" 860 " %cond.0 = load volatile i1, i1* %ptr\n" 861 " br i1 %cond.0, label %loop.0.0.ph, label %end\n" 862 "loop.0.0.ph:\n" 863 " br label %loop.0.0\n" 864 "loop.0.0:\n" 865 " %cond.0.0 = load volatile i1, i1* %ptr\n" 866 " br i1 %cond.0.0, label %loop.0.0, label %loop.0.1.ph\n" 867 "loop.0.1.ph:\n" 868 " br label %loop.0.1\n" 869 "loop.0.1:\n" 870 " %cond.0.1 = load volatile i1, i1* %ptr\n" 871 " br i1 %cond.0.1, label %loop.0.1, label %loop.0.2.ph\n" 872 "loop.0.2.ph:\n" 873 " br label %loop.0.2\n" 874 "loop.0.2:\n" 875 " %cond.0.2 = load volatile i1, i1* %ptr\n" 876 " br i1 %cond.0.2, label %loop.0.2, label %loop.0.latch\n" 877 "loop.0.latch:\n" 878 " br label %loop.0\n" 879 "end:\n" 880 " ret void\n" 881 "}\n"); 882 883 // Build up variables referring into the IR so we can rewrite it below 884 // easily. 885 Function &F = *M->begin(); 886 ASSERT_THAT(F, HasName("f")); 887 Argument &Ptr = *F.arg_begin(); 888 auto BBI = F.begin(); 889 BasicBlock &EntryBB = *BBI++; 890 ASSERT_THAT(EntryBB, HasName("entry")); 891 BasicBlock &Loop0BB = *BBI++; 892 ASSERT_THAT(Loop0BB, HasName("loop.0")); 893 BasicBlock &Loop00PHBB = *BBI++; 894 ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph")); 895 BasicBlock &Loop00BB = *BBI++; 896 ASSERT_THAT(Loop00BB, HasName("loop.0.0")); 897 BasicBlock &Loop01PHBB = *BBI++; 898 ASSERT_THAT(Loop01PHBB, HasName("loop.0.1.ph")); 899 BasicBlock &Loop01BB = *BBI++; 900 ASSERT_THAT(Loop01BB, HasName("loop.0.1")); 901 BasicBlock &Loop02PHBB = *BBI++; 902 ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph")); 903 BasicBlock &Loop02BB = *BBI++; 904 ASSERT_THAT(Loop02BB, HasName("loop.0.2")); 905 BasicBlock &Loop0LatchBB = *BBI++; 906 ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch")); 907 BasicBlock &EndBB = *BBI++; 908 ASSERT_THAT(EndBB, HasName("end")); 909 ASSERT_THAT(BBI, F.end()); 910 auto CreateCondBr = [&](BasicBlock *TrueBB, BasicBlock *FalseBB, 911 const char *Name, BasicBlock *BB) { 912 auto *Cond = new LoadInst(&Ptr, Name, /*isVolatile*/ true, BB); 913 BranchInst::Create(TrueBB, FalseBB, Cond, BB); 914 }; 915 916 // Build the pass managers and register our pipeline. We build a single loop 917 // pass pipeline consisting of three mock pass runs over each loop. After 918 // this we run both domtree and loop verification passes to make sure that 919 // the IR remained valid during our mutations. 920 ModulePassManager MPM(true); 921 FunctionPassManager FPM(true); 922 LoopPassManager LPM(true); 923 LPM.addPass(MLPHandle.getPass()); 924 LPM.addPass(MLPHandle.getPass()); 925 LPM.addPass(MLPHandle.getPass()); 926 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 927 FPM.addPass(DominatorTreeVerifierPass()); 928 FPM.addPass(LoopVerifierPass()); 929 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 930 931 // All the visit orders are deterministic, so we use simple fully order 932 // expectations. 933 ::testing::InSequence MakeExpectationsSequenced; 934 935 // We run loop passes three times over each of the loops. 936 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 937 .WillOnce(Invoke(getLoopAnalysisResult)); 938 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 939 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 940 .Times(2) 941 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 942 943 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 944 .WillOnce(Invoke(getLoopAnalysisResult)); 945 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 946 947 // When running over the middle loop, the second run inserts two new child 948 // loops, inserting them and itself into the worklist. 949 BasicBlock *NewLoop010BB, *NewLoop01LatchBB; 950 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 951 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 952 LoopStandardAnalysisResults &AR, 953 LPMUpdater &Updater) { 954 auto *NewLoop = AR.LI.AllocateLoop(); 955 L.addChildLoop(NewLoop); 956 auto *NewLoop010PHBB = 957 BasicBlock::Create(Context, "loop.0.1.0.ph", &F, &Loop02PHBB); 958 NewLoop010BB = 959 BasicBlock::Create(Context, "loop.0.1.0", &F, &Loop02PHBB); 960 NewLoop01LatchBB = 961 BasicBlock::Create(Context, "loop.0.1.latch", &F, &Loop02PHBB); 962 Loop01BB.getTerminator()->replaceUsesOfWith(&Loop01BB, NewLoop010PHBB); 963 BranchInst::Create(NewLoop010BB, NewLoop010PHBB); 964 CreateCondBr(NewLoop01LatchBB, NewLoop010BB, "cond.0.1.0", 965 NewLoop010BB); 966 BranchInst::Create(&Loop01BB, NewLoop01LatchBB); 967 AR.DT.addNewBlock(NewLoop010PHBB, &Loop01BB); 968 AR.DT.addNewBlock(NewLoop010BB, NewLoop010PHBB); 969 AR.DT.addNewBlock(NewLoop01LatchBB, NewLoop010BB); 970 EXPECT_TRUE(AR.DT.verify()); 971 L.addBasicBlockToLoop(NewLoop010PHBB, AR.LI); 972 NewLoop->addBasicBlockToLoop(NewLoop010BB, AR.LI); 973 L.addBasicBlockToLoop(NewLoop01LatchBB, AR.LI); 974 NewLoop->verifyLoop(); 975 L.verifyLoop(); 976 Updater.addChildLoops({NewLoop}); 977 return PreservedAnalyses::all(); 978 })); 979 980 // We should immediately drop down to fully visit the new inner loop. 981 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.0"), _, _, _)) 982 .WillOnce(Invoke(getLoopAnalysisResult)); 983 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1.0"), _, _)); 984 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.0"), _, _, _)) 985 .Times(2) 986 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 987 988 // After visiting the inner loop, we should re-visit the second loop 989 // reflecting its new loop nest structure. 990 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 991 .WillOnce(Invoke(getLoopAnalysisResult)); 992 993 // In the second run over the middle loop after we've visited the new child, 994 // we add another child to check that we can repeatedly add children, and add 995 // children to a loop that already has children. 996 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 997 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 998 LoopStandardAnalysisResults &AR, 999 LPMUpdater &Updater) { 1000 auto *NewLoop = AR.LI.AllocateLoop(); 1001 L.addChildLoop(NewLoop); 1002 auto *NewLoop011PHBB = BasicBlock::Create(Context, "loop.0.1.1.ph", &F, NewLoop01LatchBB); 1003 auto *NewLoop011BB = BasicBlock::Create(Context, "loop.0.1.1", &F, NewLoop01LatchBB); 1004 NewLoop010BB->getTerminator()->replaceUsesOfWith(NewLoop01LatchBB, 1005 NewLoop011PHBB); 1006 BranchInst::Create(NewLoop011BB, NewLoop011PHBB); 1007 CreateCondBr(NewLoop01LatchBB, NewLoop011BB, "cond.0.1.1", 1008 NewLoop011BB); 1009 AR.DT.addNewBlock(NewLoop011PHBB, NewLoop010BB); 1010 auto *NewDTNode = AR.DT.addNewBlock(NewLoop011BB, NewLoop011PHBB); 1011 AR.DT.changeImmediateDominator(AR.DT[NewLoop01LatchBB], NewDTNode); 1012 EXPECT_TRUE(AR.DT.verify()); 1013 L.addBasicBlockToLoop(NewLoop011PHBB, AR.LI); 1014 NewLoop->addBasicBlockToLoop(NewLoop011BB, AR.LI); 1015 NewLoop->verifyLoop(); 1016 L.verifyLoop(); 1017 Updater.addChildLoops({NewLoop}); 1018 return PreservedAnalyses::all(); 1019 })); 1020 1021 // Again, we should immediately drop down to visit the new, unvisited child 1022 // loop. We don't need to revisit the other child though. 1023 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.1"), _, _, _)) 1024 .WillOnce(Invoke(getLoopAnalysisResult)); 1025 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1.1"), _, _)); 1026 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.1"), _, _, _)) 1027 .Times(2) 1028 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1029 1030 // And now we should pop back up to the second loop and do a full pipeline of 1031 // three passes on its current form. 1032 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1033 .Times(3) 1034 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1035 1036 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1037 .WillOnce(Invoke(getLoopAnalysisResult)); 1038 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _)); 1039 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1040 .Times(2) 1041 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1042 1043 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1044 .WillOnce(Invoke(getLoopAnalysisResult)); 1045 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 1046 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1047 .Times(2) 1048 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1049 1050 // Now that all the expected actions are registered, run the pipeline over 1051 // our module. All of our expectations are verified when the test finishes. 1052 MPM.run(*M, MAM); 1053 } 1054 1055 TEST_F(LoopPassManagerTest, LoopPeerInsertion) { 1056 // Super boring module with two loop nests and loop nest with two child 1057 // loops. 1058 M = parseIR(Context, "define void @f(i1* %ptr) {\n" 1059 "entry:\n" 1060 " br label %loop.0\n" 1061 "loop.0:\n" 1062 " %cond.0 = load volatile i1, i1* %ptr\n" 1063 " br i1 %cond.0, label %loop.0.0.ph, label %loop.2.ph\n" 1064 "loop.0.0.ph:\n" 1065 " br label %loop.0.0\n" 1066 "loop.0.0:\n" 1067 " %cond.0.0 = load volatile i1, i1* %ptr\n" 1068 " br i1 %cond.0.0, label %loop.0.0, label %loop.0.2.ph\n" 1069 "loop.0.2.ph:\n" 1070 " br label %loop.0.2\n" 1071 "loop.0.2:\n" 1072 " %cond.0.2 = load volatile i1, i1* %ptr\n" 1073 " br i1 %cond.0.2, label %loop.0.2, label %loop.0.latch\n" 1074 "loop.0.latch:\n" 1075 " br label %loop.0\n" 1076 "loop.2.ph:\n" 1077 " br label %loop.2\n" 1078 "loop.2:\n" 1079 " %cond.2 = load volatile i1, i1* %ptr\n" 1080 " br i1 %cond.2, label %loop.2, label %end\n" 1081 "end:\n" 1082 " ret void\n" 1083 "}\n"); 1084 1085 // Build up variables referring into the IR so we can rewrite it below 1086 // easily. 1087 Function &F = *M->begin(); 1088 ASSERT_THAT(F, HasName("f")); 1089 Argument &Ptr = *F.arg_begin(); 1090 auto BBI = F.begin(); 1091 BasicBlock &EntryBB = *BBI++; 1092 ASSERT_THAT(EntryBB, HasName("entry")); 1093 BasicBlock &Loop0BB = *BBI++; 1094 ASSERT_THAT(Loop0BB, HasName("loop.0")); 1095 BasicBlock &Loop00PHBB = *BBI++; 1096 ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph")); 1097 BasicBlock &Loop00BB = *BBI++; 1098 ASSERT_THAT(Loop00BB, HasName("loop.0.0")); 1099 BasicBlock &Loop02PHBB = *BBI++; 1100 ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph")); 1101 BasicBlock &Loop02BB = *BBI++; 1102 ASSERT_THAT(Loop02BB, HasName("loop.0.2")); 1103 BasicBlock &Loop0LatchBB = *BBI++; 1104 ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch")); 1105 BasicBlock &Loop2PHBB = *BBI++; 1106 ASSERT_THAT(Loop2PHBB, HasName("loop.2.ph")); 1107 BasicBlock &Loop2BB = *BBI++; 1108 ASSERT_THAT(Loop2BB, HasName("loop.2")); 1109 BasicBlock &EndBB = *BBI++; 1110 ASSERT_THAT(EndBB, HasName("end")); 1111 ASSERT_THAT(BBI, F.end()); 1112 auto CreateCondBr = [&](BasicBlock *TrueBB, BasicBlock *FalseBB, 1113 const char *Name, BasicBlock *BB) { 1114 auto *Cond = new LoadInst(&Ptr, Name, /*isVolatile*/ true, BB); 1115 BranchInst::Create(TrueBB, FalseBB, Cond, BB); 1116 }; 1117 1118 // Build the pass managers and register our pipeline. We build a single loop 1119 // pass pipeline consisting of three mock pass runs over each loop. After 1120 // this we run both domtree and loop verification passes to make sure that 1121 // the IR remained valid during our mutations. 1122 ModulePassManager MPM(true); 1123 FunctionPassManager FPM(true); 1124 LoopPassManager LPM(true); 1125 LPM.addPass(MLPHandle.getPass()); 1126 LPM.addPass(MLPHandle.getPass()); 1127 LPM.addPass(MLPHandle.getPass()); 1128 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 1129 FPM.addPass(DominatorTreeVerifierPass()); 1130 FPM.addPass(LoopVerifierPass()); 1131 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 1132 1133 // All the visit orders are deterministic, so we use simple fully order 1134 // expectations. 1135 ::testing::InSequence MakeExpectationsSequenced; 1136 1137 // We run loop passes three times over each of the loops. 1138 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1139 .WillOnce(Invoke(getLoopAnalysisResult)); 1140 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 1141 1142 // On the second run, we insert a sibling loop. 1143 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1144 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 1145 LoopStandardAnalysisResults &AR, 1146 LPMUpdater &Updater) { 1147 auto *NewLoop = AR.LI.AllocateLoop(); 1148 L.getParentLoop()->addChildLoop(NewLoop); 1149 auto *NewLoop01PHBB = BasicBlock::Create(Context, "loop.0.1.ph", &F, &Loop02PHBB); 1150 auto *NewLoop01BB = BasicBlock::Create(Context, "loop.0.1", &F, &Loop02PHBB); 1151 BranchInst::Create(NewLoop01BB, NewLoop01PHBB); 1152 CreateCondBr(&Loop02PHBB, NewLoop01BB, "cond.0.1", NewLoop01BB); 1153 Loop00BB.getTerminator()->replaceUsesOfWith(&Loop02PHBB, NewLoop01PHBB); 1154 AR.DT.addNewBlock(NewLoop01PHBB, &Loop00BB); 1155 auto *NewDTNode = AR.DT.addNewBlock(NewLoop01BB, NewLoop01PHBB); 1156 AR.DT.changeImmediateDominator(AR.DT[&Loop02PHBB], NewDTNode); 1157 EXPECT_TRUE(AR.DT.verify()); 1158 L.getParentLoop()->addBasicBlockToLoop(NewLoop01PHBB, AR.LI); 1159 NewLoop->addBasicBlockToLoop(NewLoop01BB, AR.LI); 1160 L.getParentLoop()->verifyLoop(); 1161 Updater.addSiblingLoops({NewLoop}); 1162 return PreservedAnalyses::all(); 1163 })); 1164 // We finish processing this loop as sibling loops don't perturb the 1165 // postorder walk. 1166 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1167 .WillOnce(Invoke(getLoopAnalysisResult)); 1168 1169 // We visit the inserted sibling next. 1170 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1171 .WillOnce(Invoke(getLoopAnalysisResult)); 1172 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 1173 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1174 .Times(2) 1175 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1176 1177 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1178 .WillOnce(Invoke(getLoopAnalysisResult)); 1179 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _)); 1180 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1181 .WillOnce(Invoke(getLoopAnalysisResult)); 1182 // Next, on the third pass run on the last inner loop we add more new 1183 // siblings, more than one, and one with nested child loops. By doing this at 1184 // the end we make sure that edge case works well. 1185 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1186 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 1187 LoopStandardAnalysisResults &AR, 1188 LPMUpdater &Updater) { 1189 Loop *NewLoops[] = {AR.LI.AllocateLoop(), AR.LI.AllocateLoop(), 1190 AR.LI.AllocateLoop()}; 1191 L.getParentLoop()->addChildLoop(NewLoops[0]); 1192 L.getParentLoop()->addChildLoop(NewLoops[1]); 1193 NewLoops[1]->addChildLoop(NewLoops[2]); 1194 auto *NewLoop03PHBB = 1195 BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB); 1196 auto *NewLoop03BB = 1197 BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB); 1198 auto *NewLoop04PHBB = 1199 BasicBlock::Create(Context, "loop.0.4.ph", &F, &Loop0LatchBB); 1200 auto *NewLoop04BB = 1201 BasicBlock::Create(Context, "loop.0.4", &F, &Loop0LatchBB); 1202 auto *NewLoop040PHBB = 1203 BasicBlock::Create(Context, "loop.0.4.0.ph", &F, &Loop0LatchBB); 1204 auto *NewLoop040BB = 1205 BasicBlock::Create(Context, "loop.0.4.0", &F, &Loop0LatchBB); 1206 auto *NewLoop04LatchBB = 1207 BasicBlock::Create(Context, "loop.0.4.latch", &F, &Loop0LatchBB); 1208 Loop02BB.getTerminator()->replaceUsesOfWith(&Loop0LatchBB, NewLoop03PHBB); 1209 BranchInst::Create(NewLoop03BB, NewLoop03PHBB); 1210 CreateCondBr(NewLoop04PHBB, NewLoop03BB, "cond.0.3", NewLoop03BB); 1211 BranchInst::Create(NewLoop04BB, NewLoop04PHBB); 1212 CreateCondBr(&Loop0LatchBB, NewLoop040PHBB, "cond.0.4", NewLoop04BB); 1213 BranchInst::Create(NewLoop040BB, NewLoop040PHBB); 1214 CreateCondBr(NewLoop04LatchBB, NewLoop040BB, "cond.0.4.0", NewLoop040BB); 1215 BranchInst::Create(NewLoop04BB, NewLoop04LatchBB); 1216 AR.DT.addNewBlock(NewLoop03PHBB, &Loop02BB); 1217 AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB); 1218 AR.DT.addNewBlock(NewLoop04PHBB, NewLoop03BB); 1219 auto *NewDTNode = AR.DT.addNewBlock(NewLoop04BB, NewLoop04PHBB); 1220 AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB], NewDTNode); 1221 AR.DT.addNewBlock(NewLoop040PHBB, NewLoop04BB); 1222 AR.DT.addNewBlock(NewLoop040BB, NewLoop040PHBB); 1223 AR.DT.addNewBlock(NewLoop04LatchBB, NewLoop040BB); 1224 EXPECT_TRUE(AR.DT.verify()); 1225 L.getParentLoop()->addBasicBlockToLoop(NewLoop03PHBB, AR.LI); 1226 NewLoops[0]->addBasicBlockToLoop(NewLoop03BB, AR.LI); 1227 L.getParentLoop()->addBasicBlockToLoop(NewLoop04PHBB, AR.LI); 1228 NewLoops[1]->addBasicBlockToLoop(NewLoop04BB, AR.LI); 1229 NewLoops[1]->addBasicBlockToLoop(NewLoop040PHBB, AR.LI); 1230 NewLoops[2]->addBasicBlockToLoop(NewLoop040BB, AR.LI); 1231 NewLoops[1]->addBasicBlockToLoop(NewLoop04LatchBB, AR.LI); 1232 L.getParentLoop()->verifyLoop(); 1233 Updater.addSiblingLoops({NewLoops[0], NewLoops[1]}); 1234 return PreservedAnalyses::all(); 1235 })); 1236 1237 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1238 .WillOnce(Invoke(getLoopAnalysisResult)); 1239 EXPECT_CALL(MLAHandle, run(HasName("loop.0.3"), _, _)); 1240 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1241 .Times(2) 1242 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1243 1244 // Note that we need to visit the inner loop of this added sibling before the 1245 // sibling itself! 1246 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4.0"), _, _, _)) 1247 .WillOnce(Invoke(getLoopAnalysisResult)); 1248 EXPECT_CALL(MLAHandle, run(HasName("loop.0.4.0"), _, _)); 1249 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4.0"), _, _, _)) 1250 .Times(2) 1251 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1252 1253 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4"), _, _, _)) 1254 .WillOnce(Invoke(getLoopAnalysisResult)); 1255 EXPECT_CALL(MLAHandle, run(HasName("loop.0.4"), _, _)); 1256 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4"), _, _, _)) 1257 .Times(2) 1258 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1259 1260 // And only now do we visit the outermost loop of the nest. 1261 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1262 .WillOnce(Invoke(getLoopAnalysisResult)); 1263 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 1264 // On the second pass, we add sibling loops which become new top-level loops. 1265 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1266 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 1267 LoopStandardAnalysisResults &AR, 1268 LPMUpdater &Updater) { 1269 auto *NewLoop = AR.LI.AllocateLoop(); 1270 AR.LI.addTopLevelLoop(NewLoop); 1271 auto *NewLoop1PHBB = BasicBlock::Create(Context, "loop.1.ph", &F, &Loop2BB); 1272 auto *NewLoop1BB = BasicBlock::Create(Context, "loop.1", &F, &Loop2BB); 1273 BranchInst::Create(NewLoop1BB, NewLoop1PHBB); 1274 CreateCondBr(&Loop2PHBB, NewLoop1BB, "cond.1", NewLoop1BB); 1275 Loop0BB.getTerminator()->replaceUsesOfWith(&Loop2PHBB, NewLoop1PHBB); 1276 AR.DT.addNewBlock(NewLoop1PHBB, &Loop0BB); 1277 auto *NewDTNode = AR.DT.addNewBlock(NewLoop1BB, NewLoop1PHBB); 1278 AR.DT.changeImmediateDominator(AR.DT[&Loop2PHBB], NewDTNode); 1279 EXPECT_TRUE(AR.DT.verify()); 1280 NewLoop->addBasicBlockToLoop(NewLoop1BB, AR.LI); 1281 NewLoop->verifyLoop(); 1282 Updater.addSiblingLoops({NewLoop}); 1283 return PreservedAnalyses::all(); 1284 })); 1285 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1286 .WillOnce(Invoke(getLoopAnalysisResult)); 1287 1288 EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _)) 1289 .WillOnce(Invoke(getLoopAnalysisResult)); 1290 EXPECT_CALL(MLAHandle, run(HasName("loop.1"), _, _)); 1291 EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _)) 1292 .Times(2) 1293 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1294 1295 EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _)) 1296 .WillOnce(Invoke(getLoopAnalysisResult)); 1297 EXPECT_CALL(MLAHandle, run(HasName("loop.2"), _, _)); 1298 EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _)) 1299 .Times(2) 1300 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1301 1302 // Now that all the expected actions are registered, run the pipeline over 1303 // our module. All of our expectations are verified when the test finishes. 1304 MPM.run(*M, MAM); 1305 } 1306 1307 TEST_F(LoopPassManagerTest, LoopDeletion) { 1308 // Build a module with a single loop nest that contains one outer loop with 1309 // three subloops, and one of those with its own subloop. We will 1310 // incrementally delete all of these to test different deletion scenarios. 1311 M = parseIR(Context, "define void @f(i1* %ptr) {\n" 1312 "entry:\n" 1313 " br label %loop.0\n" 1314 "loop.0:\n" 1315 " %cond.0 = load volatile i1, i1* %ptr\n" 1316 " br i1 %cond.0, label %loop.0.0.ph, label %end\n" 1317 "loop.0.0.ph:\n" 1318 " br label %loop.0.0\n" 1319 "loop.0.0:\n" 1320 " %cond.0.0 = load volatile i1, i1* %ptr\n" 1321 " br i1 %cond.0.0, label %loop.0.0, label %loop.0.1.ph\n" 1322 "loop.0.1.ph:\n" 1323 " br label %loop.0.1\n" 1324 "loop.0.1:\n" 1325 " %cond.0.1 = load volatile i1, i1* %ptr\n" 1326 " br i1 %cond.0.1, label %loop.0.1, label %loop.0.2.ph\n" 1327 "loop.0.2.ph:\n" 1328 " br label %loop.0.2\n" 1329 "loop.0.2:\n" 1330 " %cond.0.2 = load volatile i1, i1* %ptr\n" 1331 " br i1 %cond.0.2, label %loop.0.2.0.ph, label %loop.0.latch\n" 1332 "loop.0.2.0.ph:\n" 1333 " br label %loop.0.2.0\n" 1334 "loop.0.2.0:\n" 1335 " %cond.0.2.0 = load volatile i1, i1* %ptr\n" 1336 " br i1 %cond.0.2.0, label %loop.0.2.0, label %loop.0.2.latch\n" 1337 "loop.0.2.latch:\n" 1338 " br label %loop.0.2\n" 1339 "loop.0.latch:\n" 1340 " br label %loop.0\n" 1341 "end:\n" 1342 " ret void\n" 1343 "}\n"); 1344 1345 // Build up variables referring into the IR so we can rewrite it below 1346 // easily. 1347 Function &F = *M->begin(); 1348 ASSERT_THAT(F, HasName("f")); 1349 Argument &Ptr = *F.arg_begin(); 1350 auto BBI = F.begin(); 1351 BasicBlock &EntryBB = *BBI++; 1352 ASSERT_THAT(EntryBB, HasName("entry")); 1353 BasicBlock &Loop0BB = *BBI++; 1354 ASSERT_THAT(Loop0BB, HasName("loop.0")); 1355 BasicBlock &Loop00PHBB = *BBI++; 1356 ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph")); 1357 BasicBlock &Loop00BB = *BBI++; 1358 ASSERT_THAT(Loop00BB, HasName("loop.0.0")); 1359 BasicBlock &Loop01PHBB = *BBI++; 1360 ASSERT_THAT(Loop01PHBB, HasName("loop.0.1.ph")); 1361 BasicBlock &Loop01BB = *BBI++; 1362 ASSERT_THAT(Loop01BB, HasName("loop.0.1")); 1363 BasicBlock &Loop02PHBB = *BBI++; 1364 ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph")); 1365 BasicBlock &Loop02BB = *BBI++; 1366 ASSERT_THAT(Loop02BB, HasName("loop.0.2")); 1367 BasicBlock &Loop020PHBB = *BBI++; 1368 ASSERT_THAT(Loop020PHBB, HasName("loop.0.2.0.ph")); 1369 BasicBlock &Loop020BB = *BBI++; 1370 ASSERT_THAT(Loop020BB, HasName("loop.0.2.0")); 1371 BasicBlock &Loop02LatchBB = *BBI++; 1372 ASSERT_THAT(Loop02LatchBB, HasName("loop.0.2.latch")); 1373 BasicBlock &Loop0LatchBB = *BBI++; 1374 ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch")); 1375 BasicBlock &EndBB = *BBI++; 1376 ASSERT_THAT(EndBB, HasName("end")); 1377 ASSERT_THAT(BBI, F.end()); 1378 1379 // Helper to do the actual deletion of a loop. We directly encode this here 1380 // to isolate ourselves from the rest of LLVM and for simplicity. Here we can 1381 // egregiously cheat based on knowledge of the test case. For example, we 1382 // have no PHI nodes and there is always a single i-dom. 1383 auto EraseLoop = [](Loop &L, BasicBlock &IDomBB, 1384 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1385 assert(L.empty() && "Can only delete leaf loops with this routine!"); 1386 SmallVector<BasicBlock *, 4> LoopBBs(L.block_begin(), L.block_end()); 1387 Updater.markLoopAsDeleted(L, L.getName()); 1388 IDomBB.getTerminator()->replaceUsesOfWith(L.getHeader(), 1389 L.getUniqueExitBlock()); 1390 for (BasicBlock *LoopBB : LoopBBs) { 1391 SmallVector<DomTreeNode *, 4> ChildNodes(AR.DT[LoopBB]->begin(), 1392 AR.DT[LoopBB]->end()); 1393 for (DomTreeNode *ChildNode : ChildNodes) 1394 AR.DT.changeImmediateDominator(ChildNode, AR.DT[&IDomBB]); 1395 AR.DT.eraseNode(LoopBB); 1396 AR.LI.removeBlock(LoopBB); 1397 LoopBB->dropAllReferences(); 1398 } 1399 for (BasicBlock *LoopBB : LoopBBs) 1400 LoopBB->eraseFromParent(); 1401 1402 AR.LI.erase(&L); 1403 }; 1404 1405 // Build up the pass managers. 1406 ModulePassManager MPM(true); 1407 FunctionPassManager FPM(true); 1408 // We run several loop pass pipelines across the loop nest, but they all take 1409 // the same form of three mock pass runs in a loop pipeline followed by 1410 // domtree and loop verification. We use a lambda to stamp this out each 1411 // time. 1412 auto AddLoopPipelineAndVerificationPasses = [&] { 1413 LoopPassManager LPM(true); 1414 LPM.addPass(MLPHandle.getPass()); 1415 LPM.addPass(MLPHandle.getPass()); 1416 LPM.addPass(MLPHandle.getPass()); 1417 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 1418 FPM.addPass(DominatorTreeVerifierPass()); 1419 FPM.addPass(LoopVerifierPass()); 1420 }; 1421 1422 // All the visit orders are deterministic so we use simple fully order 1423 // expectations. 1424 ::testing::InSequence MakeExpectationsSequenced; 1425 1426 // We run the loop pipeline with three passes over each of the loops. When 1427 // running over the middle loop, the second pass in the pipeline deletes it. 1428 // This should prevent the third pass from visiting it but otherwise leave 1429 // the process unimpacted. 1430 AddLoopPipelineAndVerificationPasses(); 1431 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1432 .WillOnce(Invoke(getLoopAnalysisResult)); 1433 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 1434 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1435 .Times(2) 1436 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1437 1438 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1439 .WillOnce(Invoke(getLoopAnalysisResult)); 1440 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 1441 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1442 .WillOnce( 1443 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1444 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1445 Loop *ParentL = L.getParentLoop(); 1446 AR.SE.forgetLoop(&L); 1447 EraseLoop(L, Loop01PHBB, AR, Updater); 1448 ParentL->verifyLoop(); 1449 return PreservedAnalyses::all(); 1450 })); 1451 1452 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _)) 1453 .WillOnce(Invoke(getLoopAnalysisResult)); 1454 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2.0"), _, _)); 1455 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _)) 1456 .Times(2) 1457 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1458 1459 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1460 .WillOnce(Invoke(getLoopAnalysisResult)); 1461 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _)); 1462 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1463 .Times(2) 1464 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1465 1466 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1467 .WillOnce(Invoke(getLoopAnalysisResult)); 1468 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 1469 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1470 .Times(2) 1471 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1472 1473 // Run the loop pipeline again. This time we delete the last loop, which 1474 // contains a nested loop within it and insert a new loop into the nest. This 1475 // makes sure 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 AR.SE.forgetLoop(*L.begin()); 1493 EraseLoop(**L.begin(), Loop020PHBB, AR, Updater); 1494 1495 auto *ParentL = L.getParentLoop(); 1496 AR.SE.forgetLoop(&L); 1497 EraseLoop(L, Loop02PHBB, AR, Updater); 1498 1499 // Now insert a new sibling loop. 1500 auto *NewSibling = AR.LI.AllocateLoop(); 1501 ParentL->addChildLoop(NewSibling); 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 EXPECT_TRUE(AR.DT.verify()); 1517 ParentL->addBasicBlockToLoop(NewLoop03PHBB, AR.LI); 1518 NewSibling->addBasicBlockToLoop(NewLoop03BB, AR.LI); 1519 NewSibling->verifyLoop(); 1520 ParentL->verifyLoop(); 1521 Updater.addSiblingLoops({NewSibling}); 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 EraseLoop(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 EraseLoop(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 EraseLoop(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