unittests/Transforms/Scalar/LoopPassManagerTest.cpp

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