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