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