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