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