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, 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(Type::getInt1Ty(Context), &Ptr, Name, 913 /*isVolatile*/ true, BB); 914 BranchInst::Create(TrueBB, FalseBB, Cond, BB); 915 }; 916 917 // Build the pass managers and register our pipeline. We build a single loop 918 // pass pipeline consisting of three mock pass runs over each loop. After 919 // this we run both domtree and loop verification passes to make sure that 920 // the IR remained valid during our mutations. 921 ModulePassManager MPM(true); 922 FunctionPassManager FPM(true); 923 LoopPassManager LPM(true); 924 LPM.addPass(MLPHandle.getPass()); 925 LPM.addPass(MLPHandle.getPass()); 926 LPM.addPass(MLPHandle.getPass()); 927 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 928 FPM.addPass(DominatorTreeVerifierPass()); 929 FPM.addPass(LoopVerifierPass()); 930 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 931 932 // All the visit orders are deterministic, so we use simple fully order 933 // expectations. 934 ::testing::InSequence MakeExpectationsSequenced; 935 936 // We run loop passes three times over each of the loops. 937 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 938 .WillOnce(Invoke(getLoopAnalysisResult)); 939 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 940 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 941 .Times(2) 942 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 943 944 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 945 .WillOnce(Invoke(getLoopAnalysisResult)); 946 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 947 948 // When running over the middle loop, the second run inserts two new child 949 // loops, inserting them and itself into the worklist. 950 BasicBlock *NewLoop010BB, *NewLoop01LatchBB; 951 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 952 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 953 LoopStandardAnalysisResults &AR, 954 LPMUpdater &Updater) { 955 auto *NewLoop = AR.LI.AllocateLoop(); 956 L.addChildLoop(NewLoop); 957 auto *NewLoop010PHBB = 958 BasicBlock::Create(Context, "loop.0.1.0.ph", &F, &Loop02PHBB); 959 NewLoop010BB = 960 BasicBlock::Create(Context, "loop.0.1.0", &F, &Loop02PHBB); 961 NewLoop01LatchBB = 962 BasicBlock::Create(Context, "loop.0.1.latch", &F, &Loop02PHBB); 963 Loop01BB.getTerminator()->replaceUsesOfWith(&Loop01BB, NewLoop010PHBB); 964 BranchInst::Create(NewLoop010BB, NewLoop010PHBB); 965 CreateCondBr(NewLoop01LatchBB, NewLoop010BB, "cond.0.1.0", 966 NewLoop010BB); 967 BranchInst::Create(&Loop01BB, NewLoop01LatchBB); 968 AR.DT.addNewBlock(NewLoop010PHBB, &Loop01BB); 969 AR.DT.addNewBlock(NewLoop010BB, NewLoop010PHBB); 970 AR.DT.addNewBlock(NewLoop01LatchBB, NewLoop010BB); 971 EXPECT_TRUE(AR.DT.verify()); 972 L.addBasicBlockToLoop(NewLoop010PHBB, AR.LI); 973 NewLoop->addBasicBlockToLoop(NewLoop010BB, AR.LI); 974 L.addBasicBlockToLoop(NewLoop01LatchBB, AR.LI); 975 NewLoop->verifyLoop(); 976 L.verifyLoop(); 977 Updater.addChildLoops({NewLoop}); 978 return PreservedAnalyses::all(); 979 })); 980 981 // We should immediately drop down to fully visit the new inner loop. 982 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.0"), _, _, _)) 983 .WillOnce(Invoke(getLoopAnalysisResult)); 984 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1.0"), _, _)); 985 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.0"), _, _, _)) 986 .Times(2) 987 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 988 989 // After visiting the inner loop, we should re-visit the second loop 990 // reflecting its new loop nest structure. 991 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 992 .WillOnce(Invoke(getLoopAnalysisResult)); 993 994 // In the second run over the middle loop after we've visited the new child, 995 // we add another child to check that we can repeatedly add children, and add 996 // children to a loop that already has children. 997 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 998 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 999 LoopStandardAnalysisResults &AR, 1000 LPMUpdater &Updater) { 1001 auto *NewLoop = AR.LI.AllocateLoop(); 1002 L.addChildLoop(NewLoop); 1003 auto *NewLoop011PHBB = BasicBlock::Create(Context, "loop.0.1.1.ph", &F, NewLoop01LatchBB); 1004 auto *NewLoop011BB = BasicBlock::Create(Context, "loop.0.1.1", &F, NewLoop01LatchBB); 1005 NewLoop010BB->getTerminator()->replaceUsesOfWith(NewLoop01LatchBB, 1006 NewLoop011PHBB); 1007 BranchInst::Create(NewLoop011BB, NewLoop011PHBB); 1008 CreateCondBr(NewLoop01LatchBB, NewLoop011BB, "cond.0.1.1", 1009 NewLoop011BB); 1010 AR.DT.addNewBlock(NewLoop011PHBB, NewLoop010BB); 1011 auto *NewDTNode = AR.DT.addNewBlock(NewLoop011BB, NewLoop011PHBB); 1012 AR.DT.changeImmediateDominator(AR.DT[NewLoop01LatchBB], NewDTNode); 1013 EXPECT_TRUE(AR.DT.verify()); 1014 L.addBasicBlockToLoop(NewLoop011PHBB, AR.LI); 1015 NewLoop->addBasicBlockToLoop(NewLoop011BB, AR.LI); 1016 NewLoop->verifyLoop(); 1017 L.verifyLoop(); 1018 Updater.addChildLoops({NewLoop}); 1019 return PreservedAnalyses::all(); 1020 })); 1021 1022 // Again, we should immediately drop down to visit the new, unvisited child 1023 // loop. We don't need to revisit the other child though. 1024 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.1"), _, _, _)) 1025 .WillOnce(Invoke(getLoopAnalysisResult)); 1026 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1.1"), _, _)); 1027 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1.1"), _, _, _)) 1028 .Times(2) 1029 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1030 1031 // And now we should pop back up to the second loop and do a full pipeline of 1032 // three passes on its current form. 1033 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1034 .Times(3) 1035 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1036 1037 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1038 .WillOnce(Invoke(getLoopAnalysisResult)); 1039 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _)); 1040 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1041 .Times(2) 1042 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1043 1044 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1045 .WillOnce(Invoke(getLoopAnalysisResult)); 1046 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 1047 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1048 .Times(2) 1049 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1050 1051 // Now that all the expected actions are registered, run the pipeline over 1052 // our module. All of our expectations are verified when the test finishes. 1053 MPM.run(*M, MAM); 1054 } 1055 1056 TEST_F(LoopPassManagerTest, LoopPeerInsertion) { 1057 // Super boring module with two loop nests and loop nest with two child 1058 // loops. 1059 M = parseIR(Context, "define void @f(i1* %ptr) {\n" 1060 "entry:\n" 1061 " br label %loop.0\n" 1062 "loop.0:\n" 1063 " %cond.0 = load volatile i1, i1* %ptr\n" 1064 " br i1 %cond.0, label %loop.0.0.ph, label %loop.2.ph\n" 1065 "loop.0.0.ph:\n" 1066 " br label %loop.0.0\n" 1067 "loop.0.0:\n" 1068 " %cond.0.0 = load volatile i1, i1* %ptr\n" 1069 " br i1 %cond.0.0, label %loop.0.0, label %loop.0.2.ph\n" 1070 "loop.0.2.ph:\n" 1071 " br label %loop.0.2\n" 1072 "loop.0.2:\n" 1073 " %cond.0.2 = load volatile i1, i1* %ptr\n" 1074 " br i1 %cond.0.2, label %loop.0.2, label %loop.0.latch\n" 1075 "loop.0.latch:\n" 1076 " br label %loop.0\n" 1077 "loop.2.ph:\n" 1078 " br label %loop.2\n" 1079 "loop.2:\n" 1080 " %cond.2 = load volatile i1, i1* %ptr\n" 1081 " br i1 %cond.2, label %loop.2, label %end\n" 1082 "end:\n" 1083 " ret void\n" 1084 "}\n"); 1085 1086 // Build up variables referring into the IR so we can rewrite it below 1087 // easily. 1088 Function &F = *M->begin(); 1089 ASSERT_THAT(F, HasName("f")); 1090 Argument &Ptr = *F.arg_begin(); 1091 auto BBI = F.begin(); 1092 BasicBlock &EntryBB = *BBI++; 1093 ASSERT_THAT(EntryBB, HasName("entry")); 1094 BasicBlock &Loop0BB = *BBI++; 1095 ASSERT_THAT(Loop0BB, HasName("loop.0")); 1096 BasicBlock &Loop00PHBB = *BBI++; 1097 ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph")); 1098 BasicBlock &Loop00BB = *BBI++; 1099 ASSERT_THAT(Loop00BB, HasName("loop.0.0")); 1100 BasicBlock &Loop02PHBB = *BBI++; 1101 ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph")); 1102 BasicBlock &Loop02BB = *BBI++; 1103 ASSERT_THAT(Loop02BB, HasName("loop.0.2")); 1104 BasicBlock &Loop0LatchBB = *BBI++; 1105 ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch")); 1106 BasicBlock &Loop2PHBB = *BBI++; 1107 ASSERT_THAT(Loop2PHBB, HasName("loop.2.ph")); 1108 BasicBlock &Loop2BB = *BBI++; 1109 ASSERT_THAT(Loop2BB, HasName("loop.2")); 1110 BasicBlock &EndBB = *BBI++; 1111 ASSERT_THAT(EndBB, HasName("end")); 1112 ASSERT_THAT(BBI, F.end()); 1113 auto CreateCondBr = [&](BasicBlock *TrueBB, BasicBlock *FalseBB, 1114 const char *Name, BasicBlock *BB) { 1115 auto *Cond = new LoadInst(Type::getInt1Ty(Context), &Ptr, Name, 1116 /*isVolatile*/ true, BB); 1117 BranchInst::Create(TrueBB, FalseBB, Cond, BB); 1118 }; 1119 1120 // Build the pass managers and register our pipeline. We build a single loop 1121 // pass pipeline consisting of three mock pass runs over each loop. After 1122 // this we run both domtree and loop verification passes to make sure that 1123 // the IR remained valid during our mutations. 1124 ModulePassManager MPM(true); 1125 FunctionPassManager FPM(true); 1126 LoopPassManager LPM(true); 1127 LPM.addPass(MLPHandle.getPass()); 1128 LPM.addPass(MLPHandle.getPass()); 1129 LPM.addPass(MLPHandle.getPass()); 1130 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 1131 FPM.addPass(DominatorTreeVerifierPass()); 1132 FPM.addPass(LoopVerifierPass()); 1133 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 1134 1135 // All the visit orders are deterministic, so we use simple fully order 1136 // expectations. 1137 ::testing::InSequence MakeExpectationsSequenced; 1138 1139 // We run loop passes three times over each of the loops. 1140 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1141 .WillOnce(Invoke(getLoopAnalysisResult)); 1142 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 1143 1144 // On the second run, we insert a sibling loop. 1145 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1146 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 1147 LoopStandardAnalysisResults &AR, 1148 LPMUpdater &Updater) { 1149 auto *NewLoop = AR.LI.AllocateLoop(); 1150 L.getParentLoop()->addChildLoop(NewLoop); 1151 auto *NewLoop01PHBB = BasicBlock::Create(Context, "loop.0.1.ph", &F, &Loop02PHBB); 1152 auto *NewLoop01BB = BasicBlock::Create(Context, "loop.0.1", &F, &Loop02PHBB); 1153 BranchInst::Create(NewLoop01BB, NewLoop01PHBB); 1154 CreateCondBr(&Loop02PHBB, NewLoop01BB, "cond.0.1", NewLoop01BB); 1155 Loop00BB.getTerminator()->replaceUsesOfWith(&Loop02PHBB, NewLoop01PHBB); 1156 AR.DT.addNewBlock(NewLoop01PHBB, &Loop00BB); 1157 auto *NewDTNode = AR.DT.addNewBlock(NewLoop01BB, NewLoop01PHBB); 1158 AR.DT.changeImmediateDominator(AR.DT[&Loop02PHBB], NewDTNode); 1159 EXPECT_TRUE(AR.DT.verify()); 1160 L.getParentLoop()->addBasicBlockToLoop(NewLoop01PHBB, AR.LI); 1161 NewLoop->addBasicBlockToLoop(NewLoop01BB, AR.LI); 1162 L.getParentLoop()->verifyLoop(); 1163 Updater.addSiblingLoops({NewLoop}); 1164 return PreservedAnalyses::all(); 1165 })); 1166 // We finish processing this loop as sibling loops don't perturb the 1167 // postorder walk. 1168 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1169 .WillOnce(Invoke(getLoopAnalysisResult)); 1170 1171 // We visit the inserted sibling next. 1172 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1173 .WillOnce(Invoke(getLoopAnalysisResult)); 1174 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 1175 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1176 .Times(2) 1177 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1178 1179 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1180 .WillOnce(Invoke(getLoopAnalysisResult)); 1181 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _)); 1182 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1183 .WillOnce(Invoke(getLoopAnalysisResult)); 1184 // Next, on the third pass run on the last inner loop we add more new 1185 // siblings, more than one, and one with nested child loops. By doing this at 1186 // the end we make sure that edge case works well. 1187 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1188 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 1189 LoopStandardAnalysisResults &AR, 1190 LPMUpdater &Updater) { 1191 Loop *NewLoops[] = {AR.LI.AllocateLoop(), AR.LI.AllocateLoop(), 1192 AR.LI.AllocateLoop()}; 1193 L.getParentLoop()->addChildLoop(NewLoops[0]); 1194 L.getParentLoop()->addChildLoop(NewLoops[1]); 1195 NewLoops[1]->addChildLoop(NewLoops[2]); 1196 auto *NewLoop03PHBB = 1197 BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB); 1198 auto *NewLoop03BB = 1199 BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB); 1200 auto *NewLoop04PHBB = 1201 BasicBlock::Create(Context, "loop.0.4.ph", &F, &Loop0LatchBB); 1202 auto *NewLoop04BB = 1203 BasicBlock::Create(Context, "loop.0.4", &F, &Loop0LatchBB); 1204 auto *NewLoop040PHBB = 1205 BasicBlock::Create(Context, "loop.0.4.0.ph", &F, &Loop0LatchBB); 1206 auto *NewLoop040BB = 1207 BasicBlock::Create(Context, "loop.0.4.0", &F, &Loop0LatchBB); 1208 auto *NewLoop04LatchBB = 1209 BasicBlock::Create(Context, "loop.0.4.latch", &F, &Loop0LatchBB); 1210 Loop02BB.getTerminator()->replaceUsesOfWith(&Loop0LatchBB, NewLoop03PHBB); 1211 BranchInst::Create(NewLoop03BB, NewLoop03PHBB); 1212 CreateCondBr(NewLoop04PHBB, NewLoop03BB, "cond.0.3", NewLoop03BB); 1213 BranchInst::Create(NewLoop04BB, NewLoop04PHBB); 1214 CreateCondBr(&Loop0LatchBB, NewLoop040PHBB, "cond.0.4", NewLoop04BB); 1215 BranchInst::Create(NewLoop040BB, NewLoop040PHBB); 1216 CreateCondBr(NewLoop04LatchBB, NewLoop040BB, "cond.0.4.0", NewLoop040BB); 1217 BranchInst::Create(NewLoop04BB, NewLoop04LatchBB); 1218 AR.DT.addNewBlock(NewLoop03PHBB, &Loop02BB); 1219 AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB); 1220 AR.DT.addNewBlock(NewLoop04PHBB, NewLoop03BB); 1221 auto *NewDTNode = AR.DT.addNewBlock(NewLoop04BB, NewLoop04PHBB); 1222 AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB], NewDTNode); 1223 AR.DT.addNewBlock(NewLoop040PHBB, NewLoop04BB); 1224 AR.DT.addNewBlock(NewLoop040BB, NewLoop040PHBB); 1225 AR.DT.addNewBlock(NewLoop04LatchBB, NewLoop040BB); 1226 EXPECT_TRUE(AR.DT.verify()); 1227 L.getParentLoop()->addBasicBlockToLoop(NewLoop03PHBB, AR.LI); 1228 NewLoops[0]->addBasicBlockToLoop(NewLoop03BB, AR.LI); 1229 L.getParentLoop()->addBasicBlockToLoop(NewLoop04PHBB, AR.LI); 1230 NewLoops[1]->addBasicBlockToLoop(NewLoop04BB, AR.LI); 1231 NewLoops[1]->addBasicBlockToLoop(NewLoop040PHBB, AR.LI); 1232 NewLoops[2]->addBasicBlockToLoop(NewLoop040BB, AR.LI); 1233 NewLoops[1]->addBasicBlockToLoop(NewLoop04LatchBB, AR.LI); 1234 L.getParentLoop()->verifyLoop(); 1235 Updater.addSiblingLoops({NewLoops[0], NewLoops[1]}); 1236 return PreservedAnalyses::all(); 1237 })); 1238 1239 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1240 .WillOnce(Invoke(getLoopAnalysisResult)); 1241 EXPECT_CALL(MLAHandle, run(HasName("loop.0.3"), _, _)); 1242 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1243 .Times(2) 1244 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1245 1246 // Note that we need to visit the inner loop of this added sibling before the 1247 // sibling itself! 1248 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4.0"), _, _, _)) 1249 .WillOnce(Invoke(getLoopAnalysisResult)); 1250 EXPECT_CALL(MLAHandle, run(HasName("loop.0.4.0"), _, _)); 1251 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4.0"), _, _, _)) 1252 .Times(2) 1253 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1254 1255 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4"), _, _, _)) 1256 .WillOnce(Invoke(getLoopAnalysisResult)); 1257 EXPECT_CALL(MLAHandle, run(HasName("loop.0.4"), _, _)); 1258 EXPECT_CALL(MLPHandle, run(HasName("loop.0.4"), _, _, _)) 1259 .Times(2) 1260 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1261 1262 // And only now do we visit the outermost loop of the nest. 1263 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1264 .WillOnce(Invoke(getLoopAnalysisResult)); 1265 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 1266 // On the second pass, we add sibling loops which become new top-level loops. 1267 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1268 .WillOnce(Invoke([&](Loop &L, LoopAnalysisManager &AM, 1269 LoopStandardAnalysisResults &AR, 1270 LPMUpdater &Updater) { 1271 auto *NewLoop = AR.LI.AllocateLoop(); 1272 AR.LI.addTopLevelLoop(NewLoop); 1273 auto *NewLoop1PHBB = BasicBlock::Create(Context, "loop.1.ph", &F, &Loop2BB); 1274 auto *NewLoop1BB = BasicBlock::Create(Context, "loop.1", &F, &Loop2BB); 1275 BranchInst::Create(NewLoop1BB, NewLoop1PHBB); 1276 CreateCondBr(&Loop2PHBB, NewLoop1BB, "cond.1", NewLoop1BB); 1277 Loop0BB.getTerminator()->replaceUsesOfWith(&Loop2PHBB, NewLoop1PHBB); 1278 AR.DT.addNewBlock(NewLoop1PHBB, &Loop0BB); 1279 auto *NewDTNode = AR.DT.addNewBlock(NewLoop1BB, NewLoop1PHBB); 1280 AR.DT.changeImmediateDominator(AR.DT[&Loop2PHBB], NewDTNode); 1281 EXPECT_TRUE(AR.DT.verify()); 1282 NewLoop->addBasicBlockToLoop(NewLoop1BB, AR.LI); 1283 NewLoop->verifyLoop(); 1284 Updater.addSiblingLoops({NewLoop}); 1285 return PreservedAnalyses::all(); 1286 })); 1287 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1288 .WillOnce(Invoke(getLoopAnalysisResult)); 1289 1290 EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _)) 1291 .WillOnce(Invoke(getLoopAnalysisResult)); 1292 EXPECT_CALL(MLAHandle, run(HasName("loop.1"), _, _)); 1293 EXPECT_CALL(MLPHandle, run(HasName("loop.1"), _, _, _)) 1294 .Times(2) 1295 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1296 1297 EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _)) 1298 .WillOnce(Invoke(getLoopAnalysisResult)); 1299 EXPECT_CALL(MLAHandle, run(HasName("loop.2"), _, _)); 1300 EXPECT_CALL(MLPHandle, run(HasName("loop.2"), _, _, _)) 1301 .Times(2) 1302 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1303 1304 // Now that all the expected actions are registered, run the pipeline over 1305 // our module. All of our expectations are verified when the test finishes. 1306 MPM.run(*M, MAM); 1307 } 1308 1309 TEST_F(LoopPassManagerTest, LoopDeletion) { 1310 // Build a module with a single loop nest that contains one outer loop with 1311 // three subloops, and one of those with its own subloop. We will 1312 // incrementally delete all of these to test different deletion scenarios. 1313 M = parseIR(Context, "define void @f(i1* %ptr) {\n" 1314 "entry:\n" 1315 " br label %loop.0\n" 1316 "loop.0:\n" 1317 " %cond.0 = load volatile i1, i1* %ptr\n" 1318 " br i1 %cond.0, label %loop.0.0.ph, label %end\n" 1319 "loop.0.0.ph:\n" 1320 " br label %loop.0.0\n" 1321 "loop.0.0:\n" 1322 " %cond.0.0 = load volatile i1, i1* %ptr\n" 1323 " br i1 %cond.0.0, label %loop.0.0, label %loop.0.1.ph\n" 1324 "loop.0.1.ph:\n" 1325 " br label %loop.0.1\n" 1326 "loop.0.1:\n" 1327 " %cond.0.1 = load volatile i1, i1* %ptr\n" 1328 " br i1 %cond.0.1, label %loop.0.1, label %loop.0.2.ph\n" 1329 "loop.0.2.ph:\n" 1330 " br label %loop.0.2\n" 1331 "loop.0.2:\n" 1332 " %cond.0.2 = load volatile i1, i1* %ptr\n" 1333 " br i1 %cond.0.2, label %loop.0.2.0.ph, label %loop.0.latch\n" 1334 "loop.0.2.0.ph:\n" 1335 " br label %loop.0.2.0\n" 1336 "loop.0.2.0:\n" 1337 " %cond.0.2.0 = load volatile i1, i1* %ptr\n" 1338 " br i1 %cond.0.2.0, label %loop.0.2.0, label %loop.0.2.latch\n" 1339 "loop.0.2.latch:\n" 1340 " br label %loop.0.2\n" 1341 "loop.0.latch:\n" 1342 " br label %loop.0\n" 1343 "end:\n" 1344 " ret void\n" 1345 "}\n"); 1346 1347 // Build up variables referring into the IR so we can rewrite it below 1348 // easily. 1349 Function &F = *M->begin(); 1350 ASSERT_THAT(F, HasName("f")); 1351 Argument &Ptr = *F.arg_begin(); 1352 auto BBI = F.begin(); 1353 BasicBlock &EntryBB = *BBI++; 1354 ASSERT_THAT(EntryBB, HasName("entry")); 1355 BasicBlock &Loop0BB = *BBI++; 1356 ASSERT_THAT(Loop0BB, HasName("loop.0")); 1357 BasicBlock &Loop00PHBB = *BBI++; 1358 ASSERT_THAT(Loop00PHBB, HasName("loop.0.0.ph")); 1359 BasicBlock &Loop00BB = *BBI++; 1360 ASSERT_THAT(Loop00BB, HasName("loop.0.0")); 1361 BasicBlock &Loop01PHBB = *BBI++; 1362 ASSERT_THAT(Loop01PHBB, HasName("loop.0.1.ph")); 1363 BasicBlock &Loop01BB = *BBI++; 1364 ASSERT_THAT(Loop01BB, HasName("loop.0.1")); 1365 BasicBlock &Loop02PHBB = *BBI++; 1366 ASSERT_THAT(Loop02PHBB, HasName("loop.0.2.ph")); 1367 BasicBlock &Loop02BB = *BBI++; 1368 ASSERT_THAT(Loop02BB, HasName("loop.0.2")); 1369 BasicBlock &Loop020PHBB = *BBI++; 1370 ASSERT_THAT(Loop020PHBB, HasName("loop.0.2.0.ph")); 1371 BasicBlock &Loop020BB = *BBI++; 1372 ASSERT_THAT(Loop020BB, HasName("loop.0.2.0")); 1373 BasicBlock &Loop02LatchBB = *BBI++; 1374 ASSERT_THAT(Loop02LatchBB, HasName("loop.0.2.latch")); 1375 BasicBlock &Loop0LatchBB = *BBI++; 1376 ASSERT_THAT(Loop0LatchBB, HasName("loop.0.latch")); 1377 BasicBlock &EndBB = *BBI++; 1378 ASSERT_THAT(EndBB, HasName("end")); 1379 ASSERT_THAT(BBI, F.end()); 1380 1381 // Helper to do the actual deletion of a loop. We directly encode this here 1382 // to isolate ourselves from the rest of LLVM and for simplicity. Here we can 1383 // egregiously cheat based on knowledge of the test case. For example, we 1384 // have no PHI nodes and there is always a single i-dom. 1385 auto EraseLoop = [](Loop &L, BasicBlock &IDomBB, 1386 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1387 assert(L.empty() && "Can only delete leaf loops with this routine!"); 1388 SmallVector<BasicBlock *, 4> LoopBBs(L.block_begin(), L.block_end()); 1389 Updater.markLoopAsDeleted(L, L.getName()); 1390 IDomBB.getTerminator()->replaceUsesOfWith(L.getHeader(), 1391 L.getUniqueExitBlock()); 1392 for (BasicBlock *LoopBB : LoopBBs) { 1393 SmallVector<DomTreeNode *, 4> ChildNodes(AR.DT[LoopBB]->begin(), 1394 AR.DT[LoopBB]->end()); 1395 for (DomTreeNode *ChildNode : ChildNodes) 1396 AR.DT.changeImmediateDominator(ChildNode, AR.DT[&IDomBB]); 1397 AR.DT.eraseNode(LoopBB); 1398 AR.LI.removeBlock(LoopBB); 1399 LoopBB->dropAllReferences(); 1400 } 1401 for (BasicBlock *LoopBB : LoopBBs) 1402 LoopBB->eraseFromParent(); 1403 1404 AR.LI.erase(&L); 1405 }; 1406 1407 // Build up the pass managers. 1408 ModulePassManager MPM(true); 1409 FunctionPassManager FPM(true); 1410 // We run several loop pass pipelines across the loop nest, but they all take 1411 // the same form of three mock pass runs in a loop pipeline followed by 1412 // domtree and loop verification. We use a lambda to stamp this out each 1413 // time. 1414 auto AddLoopPipelineAndVerificationPasses = [&] { 1415 LoopPassManager LPM(true); 1416 LPM.addPass(MLPHandle.getPass()); 1417 LPM.addPass(MLPHandle.getPass()); 1418 LPM.addPass(MLPHandle.getPass()); 1419 FPM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM))); 1420 FPM.addPass(DominatorTreeVerifierPass()); 1421 FPM.addPass(LoopVerifierPass()); 1422 }; 1423 1424 // All the visit orders are deterministic so we use simple fully order 1425 // expectations. 1426 ::testing::InSequence MakeExpectationsSequenced; 1427 1428 // We run the loop pipeline with three passes over each of the loops. When 1429 // running over the middle loop, the second pass in the pipeline deletes it. 1430 // This should prevent the third pass from visiting it but otherwise leave 1431 // the process unimpacted. 1432 AddLoopPipelineAndVerificationPasses(); 1433 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1434 .WillOnce(Invoke(getLoopAnalysisResult)); 1435 EXPECT_CALL(MLAHandle, run(HasName("loop.0.0"), _, _)); 1436 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1437 .Times(2) 1438 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1439 1440 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1441 .WillOnce(Invoke(getLoopAnalysisResult)); 1442 EXPECT_CALL(MLAHandle, run(HasName("loop.0.1"), _, _)); 1443 EXPECT_CALL(MLPHandle, run(HasName("loop.0.1"), _, _, _)) 1444 .WillOnce( 1445 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1446 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1447 Loop *ParentL = L.getParentLoop(); 1448 AR.SE.forgetLoop(&L); 1449 EraseLoop(L, Loop01PHBB, AR, Updater); 1450 ParentL->verifyLoop(); 1451 return PreservedAnalyses::all(); 1452 })); 1453 1454 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _)) 1455 .WillOnce(Invoke(getLoopAnalysisResult)); 1456 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2.0"), _, _)); 1457 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _)) 1458 .Times(2) 1459 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1460 1461 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1462 .WillOnce(Invoke(getLoopAnalysisResult)); 1463 EXPECT_CALL(MLAHandle, run(HasName("loop.0.2"), _, _)); 1464 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1465 .Times(2) 1466 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1467 1468 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1469 .WillOnce(Invoke(getLoopAnalysisResult)); 1470 EXPECT_CALL(MLAHandle, run(HasName("loop.0"), _, _)); 1471 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1472 .Times(2) 1473 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1474 1475 // Run the loop pipeline again. This time we delete the last loop, which 1476 // contains a nested loop within it and insert a new loop into the nest. This 1477 // makes sure we can handle nested loop deletion. 1478 AddLoopPipelineAndVerificationPasses(); 1479 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1480 .Times(3) 1481 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1482 1483 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2.0"), _, _, _)) 1484 .Times(3) 1485 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1486 1487 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1488 .WillOnce(Invoke(getLoopAnalysisResult)); 1489 BasicBlock *NewLoop03PHBB; 1490 EXPECT_CALL(MLPHandle, run(HasName("loop.0.2"), _, _, _)) 1491 .WillOnce( 1492 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1493 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1494 AR.SE.forgetLoop(*L.begin()); 1495 EraseLoop(**L.begin(), Loop020PHBB, AR, Updater); 1496 1497 auto *ParentL = L.getParentLoop(); 1498 AR.SE.forgetLoop(&L); 1499 EraseLoop(L, Loop02PHBB, AR, Updater); 1500 1501 // Now insert a new sibling loop. 1502 auto *NewSibling = AR.LI.AllocateLoop(); 1503 ParentL->addChildLoop(NewSibling); 1504 NewLoop03PHBB = 1505 BasicBlock::Create(Context, "loop.0.3.ph", &F, &Loop0LatchBB); 1506 auto *NewLoop03BB = 1507 BasicBlock::Create(Context, "loop.0.3", &F, &Loop0LatchBB); 1508 BranchInst::Create(NewLoop03BB, NewLoop03PHBB); 1509 auto *Cond = 1510 new LoadInst(Type::getInt1Ty(Context), &Ptr, "cond.0.3", 1511 /*isVolatile*/ true, NewLoop03BB); 1512 BranchInst::Create(&Loop0LatchBB, NewLoop03BB, Cond, NewLoop03BB); 1513 Loop02PHBB.getTerminator()->replaceUsesOfWith(&Loop0LatchBB, 1514 NewLoop03PHBB); 1515 AR.DT.addNewBlock(NewLoop03PHBB, &Loop02PHBB); 1516 AR.DT.addNewBlock(NewLoop03BB, NewLoop03PHBB); 1517 AR.DT.changeImmediateDominator(AR.DT[&Loop0LatchBB], 1518 AR.DT[NewLoop03BB]); 1519 EXPECT_TRUE(AR.DT.verify()); 1520 ParentL->addBasicBlockToLoop(NewLoop03PHBB, AR.LI); 1521 NewSibling->addBasicBlockToLoop(NewLoop03BB, AR.LI); 1522 NewSibling->verifyLoop(); 1523 ParentL->verifyLoop(); 1524 Updater.addSiblingLoops({NewSibling}); 1525 return PreservedAnalyses::all(); 1526 })); 1527 1528 // To respect our inner-to-outer traversal order, we must visit the 1529 // newly-inserted sibling of the loop we just deleted before we visit the 1530 // outer loop. When we do so, this must compute a fresh analysis result, even 1531 // though our new loop has the same pointer value as the loop we deleted. 1532 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1533 .WillOnce(Invoke(getLoopAnalysisResult)); 1534 EXPECT_CALL(MLAHandle, run(HasName("loop.0.3"), _, _)); 1535 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1536 .Times(2) 1537 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1538 1539 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1540 .Times(3) 1541 .WillRepeatedly(Invoke(getLoopAnalysisResult)); 1542 1543 // In the final loop pipeline run we delete every loop, including the last 1544 // loop of the nest. We do this again in the second pass in the pipeline, and 1545 // as a consequence we never make it to three runs on any loop. We also cover 1546 // deleting multiple loops in a single pipeline, deleting the first loop and 1547 // deleting the (last) top level loop. 1548 AddLoopPipelineAndVerificationPasses(); 1549 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1550 .WillOnce(Invoke(getLoopAnalysisResult)); 1551 EXPECT_CALL(MLPHandle, run(HasName("loop.0.0"), _, _, _)) 1552 .WillOnce( 1553 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1554 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1555 AR.SE.forgetLoop(&L); 1556 EraseLoop(L, Loop00PHBB, AR, Updater); 1557 return PreservedAnalyses::all(); 1558 })); 1559 1560 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1561 .WillOnce(Invoke(getLoopAnalysisResult)); 1562 EXPECT_CALL(MLPHandle, run(HasName("loop.0.3"), _, _, _)) 1563 .WillOnce( 1564 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1565 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1566 AR.SE.forgetLoop(&L); 1567 EraseLoop(L, *NewLoop03PHBB, AR, Updater); 1568 return PreservedAnalyses::all(); 1569 })); 1570 1571 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1572 .WillOnce(Invoke(getLoopAnalysisResult)); 1573 EXPECT_CALL(MLPHandle, run(HasName("loop.0"), _, _, _)) 1574 .WillOnce( 1575 Invoke([&](Loop &L, LoopAnalysisManager &AM, 1576 LoopStandardAnalysisResults &AR, LPMUpdater &Updater) { 1577 AR.SE.forgetLoop(&L); 1578 EraseLoop(L, EntryBB, AR, Updater); 1579 return PreservedAnalyses::all(); 1580 })); 1581 1582 // Add the function pass pipeline now that it is fully built up and run it 1583 // over the module's one function. 1584 MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM))); 1585 MPM.run(*M, MAM); 1586 } 1587 } 1588