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