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