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