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