llvm/unittests/Transforms/Scalar/LoopPassManagerTest.cpp

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