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