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