llvm/unittests/Analysis/CGSCCPassManagerTest.cpp

   1 //===- CGSCCPassManagerTest.cpp -------------------------------------------===//
   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/Analysis/CGSCCPassManager.h"
  10 #include "llvm/Analysis/LazyCallGraph.h"
  11 #include "llvm/Analysis/TargetLibraryInfo.h"
  12 #include "llvm/AsmParser/Parser.h"
  13 #include "llvm/IR/Constants.h"
  14 #include "llvm/IR/Function.h"
  15 #include "llvm/IR/InstIterator.h"
  16 #include "llvm/IR/Instructions.h"
  17 #include "llvm/IR/LLVMContext.h"
  18 #include "llvm/IR/Module.h"
  19 #include "llvm/IR/PassManager.h"
  20 #include "llvm/IR/Verifier.h"
  21 #include "llvm/Support/SourceMgr.h"
  22 #include "llvm/Transforms/Utils/CallGraphUpdater.h"
  23 #include "gtest/gtest.h"
  24
  25 using namespace llvm;
  26
  27 namespace {
  28
  29 class TestModuleAnalysis : public AnalysisInfoMixin<TestModuleAnalysis> {
  30 public:
  31   struct Result {
  32     Result(int Count) : FunctionCount(Count) {}
  33     int FunctionCount;
  34     bool invalidate(Module &, const PreservedAnalyses &PA,
  35                     ModuleAnalysisManager::Invalidator &) {
  36       // Check whether the analysis or all analyses on modules have been
  37       // preserved.
  38       auto PAC = PA.getChecker<TestModuleAnalysis>();
  39       return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>());
  40     }
  41   };
  42
  43   TestModuleAnalysis(int &Runs) : Runs(Runs) {}
  44
  45   Result run(Module &M, ModuleAnalysisManager &AM) {
  46     ++Runs;
  47     return Result(M.size());
  48   }
  49
  50 private:
  51   friend AnalysisInfoMixin<TestModuleAnalysis>;
  52   static AnalysisKey Key;
  53
  54   int &Runs;
  55 };
  56
  57 AnalysisKey TestModuleAnalysis::Key;
  58
  59 class TestSCCAnalysis : public AnalysisInfoMixin<TestSCCAnalysis> {
  60 public:
  61   struct Result {
  62     Result(int Count) : FunctionCount(Count) {}
  63     int FunctionCount;
  64     bool invalidate(LazyCallGraph::SCC &, const PreservedAnalyses &PA,
  65                     CGSCCAnalysisManager::Invalidator &) {
  66       // Check whether the analysis or all analyses on SCCs have been
  67       // preserved.
  68       auto PAC = PA.getChecker<TestSCCAnalysis>();
  69       return !(PAC.preserved() ||
  70                PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>());
  71     }
  72   };
  73
  74   TestSCCAnalysis(int &Runs) : Runs(Runs) {}
  75
  76   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &) {
  77     ++Runs;
  78     return Result(C.size());
  79   }
  80
  81 private:
  82   friend AnalysisInfoMixin<TestSCCAnalysis>;
  83   static AnalysisKey Key;
  84
  85   int &Runs;
  86 };
  87
  88 AnalysisKey TestSCCAnalysis::Key;
  89
  90 class TestFunctionAnalysis : public AnalysisInfoMixin<TestFunctionAnalysis> {
  91 public:
  92   struct Result {
  93     Result(int Count) : InstructionCount(Count) {}
  94     int InstructionCount;
  95     bool invalidate(Function &, const PreservedAnalyses &PA,
  96                     FunctionAnalysisManager::Invalidator &) {
  97       // Check whether the analysis or all analyses on functions have been
  98       // preserved.
  99       auto PAC = PA.getChecker<TestFunctionAnalysis>();
 100       return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>());
 101     }
 102   };
 103
 104   TestFunctionAnalysis(int &Runs) : Runs(Runs) {}
 105
 106   Result run(Function &F, FunctionAnalysisManager &AM) {
 107     ++Runs;
 108     int Count = 0;
 109     for (Instruction &I : instructions(F)) {
 110       (void)I;
 111       ++Count;
 112     }
 113     return Result(Count);
 114   }
 115
 116 private:
 117   friend AnalysisInfoMixin<TestFunctionAnalysis>;
 118   static AnalysisKey Key;
 119
 120   int &Runs;
 121 };
 122
 123 AnalysisKey TestFunctionAnalysis::Key;
 124
 125 class TestImmutableFunctionAnalysis
 126     : public AnalysisInfoMixin<TestImmutableFunctionAnalysis> {
 127 public:
 128   struct Result {
 129     bool invalidate(Function &, const PreservedAnalyses &,
 130                     FunctionAnalysisManager::Invalidator &) {
 131       return false;
 132     }
 133   };
 134
 135   TestImmutableFunctionAnalysis(int &Runs) : Runs(Runs) {}
 136
 137   Result run(Function &F, FunctionAnalysisManager &AM) {
 138     ++Runs;
 139     return Result();
 140   }
 141
 142 private:
 143   friend AnalysisInfoMixin<TestImmutableFunctionAnalysis>;
 144   static AnalysisKey Key;
 145
 146   int &Runs;
 147 };
 148
 149 AnalysisKey TestImmutableFunctionAnalysis::Key;
 150
 151 struct LambdaModulePass : public PassInfoMixin<LambdaModulePass> {
 152   template <typename T>
 153   LambdaModulePass(T &&Arg) : Func(std::forward<T>(Arg)) {}
 154
 155   PreservedAnalyses run(Module &F, ModuleAnalysisManager &AM) {
 156     return Func(F, AM);
 157   }
 158
 159   std::function<PreservedAnalyses(Module &, ModuleAnalysisManager &)> Func;
 160 };
 161
 162 struct LambdaSCCPass : public PassInfoMixin<LambdaSCCPass> {
 163   template <typename T> LambdaSCCPass(T &&Arg) : Func(std::forward<T>(Arg)) {}
 164
 165   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 166                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
 167     return Func(C, AM, CG, UR);
 168   }
 169
 170   std::function<PreservedAnalyses(LazyCallGraph::SCC &, CGSCCAnalysisManager &,
 171                                   LazyCallGraph &, CGSCCUpdateResult &)>
 172       Func;
 173 };
 174
 175 struct LambdaFunctionPass : public PassInfoMixin<LambdaFunctionPass> {
 176   template <typename T>
 177   LambdaFunctionPass(T &&Arg) : Func(std::forward<T>(Arg)) {}
 178
 179   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
 180     return Func(F, AM);
 181   }
 182
 183   std::function<PreservedAnalyses(Function &, FunctionAnalysisManager &)> Func;
 184 };
 185
 186 std::unique_ptr<Module> parseIR(const char *IR) {
 187   // We just use a static context here. This is never called from multiple
 188   // threads so it is harmless no matter how it is implemented. We just need
 189   // the context to outlive the module which it does.
 190   static LLVMContext C;
 191   SMDiagnostic Err;
 192   return parseAssemblyString(IR, Err, C);
 193 }
 194
 195 class CGSCCPassManagerTest : public ::testing::Test {
 196 protected:
 197   LLVMContext Context;
 198   FunctionAnalysisManager FAM;
 199   CGSCCAnalysisManager CGAM;
 200   ModuleAnalysisManager MAM;
 201
 202   std::unique_ptr<Module> M;
 203
 204 public:
 205   CGSCCPassManagerTest()
 206       : FAM(), CGAM(), MAM(),
 207         M(parseIR(
 208             // Define a module with the following call graph, where calls go
 209             // out the bottom of nodes and enter the top:
 210             //
 211             // f
 212             // |\   _
 213             // | \ / |
 214             // g  h1 |
 215             // |  |  |
 216             // |  h2 |
 217             // |  |  |
 218             // |  h3 |
 219             // | / \_/
 220             // |/
 221             // x
 222             //
 223             "define void @x() {\n"
 224             "entry:\n"
 225             "  ret void\n"
 226             "}\n"
 227             "define void @h3() {\n"
 228             "entry:\n"
 229             "  call void @h1()\n"
 230             "  ret void\n"
 231             "}\n"
 232             "define void @h2() {\n"
 233             "entry:\n"
 234             "  call void @h3()\n"
 235             "  call void @x()\n"
 236             "  ret void\n"
 237             "}\n"
 238             "define void @h1() {\n"
 239             "entry:\n"
 240             "  call void @h2()\n"
 241             "  ret void\n"
 242             "}\n"
 243             "define void @g() {\n"
 244             "entry:\n"
 245             "  call void @g()\n"
 246             "  call void @x()\n"
 247             "  ret void\n"
 248             "}\n"
 249             "define void @f() {\n"
 250             "entry:\n"
 251             "  call void @g()\n"
 252             "  call void @h1()\n"
 253             "  ret void\n"
 254             "}\n")) {
 255     FAM.registerPass([&] { return TargetLibraryAnalysis(); });
 256     MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
 257     MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
 258
 259     // Register required pass instrumentation analysis.
 260     MAM.registerPass([&] { return PassInstrumentationAnalysis(); });
 261     CGAM.registerPass([&] { return PassInstrumentationAnalysis(); });
 262     FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
 263
 264     // Cross-register proxies.
 265     MAM.registerPass([&] { return CGSCCAnalysisManagerModuleProxy(CGAM); });
 266     CGAM.registerPass([&] { return FunctionAnalysisManagerCGSCCProxy(); });
 267     CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); });
 268     FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); });
 269     FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
 270   }
 271 };
 272
 273 TEST_F(CGSCCPassManagerTest, Basic) {
 274   int FunctionAnalysisRuns = 0;
 275   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 276   int ImmutableFunctionAnalysisRuns = 0;
 277   FAM.registerPass([&] {
 278     return TestImmutableFunctionAnalysis(ImmutableFunctionAnalysisRuns);
 279   });
 280
 281   int SCCAnalysisRuns = 0;
 282   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 283
 284   int ModuleAnalysisRuns = 0;
 285   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
 286
 287   ModulePassManager MPM;
 288   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
 289
 290   CGSCCPassManager CGPM1;
 291   FunctionPassManager FPM1;
 292   int FunctionPassRunCount1 = 0;
 293   FPM1.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
 294     ++FunctionPassRunCount1;
 295     return PreservedAnalyses::none();
 296   }));
 297   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 298
 299   int SCCPassRunCount1 = 0;
 300   int AnalyzedInstrCount1 = 0;
 301   int AnalyzedSCCFunctionCount1 = 0;
 302   int AnalyzedModuleFunctionCount1 = 0;
 303   CGPM1.addPass(
 304       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 305                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
 306         ++SCCPassRunCount1;
 307
 308         // Note: The proper way to get to a module pass from a CGSCC pass is
 309         // through the ModuleAnalysisManagerCGSCCProxy:
 310         // ```
 311         // const auto &MAMProxy =
 312         //    AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
 313         // ```
 314         // However getting a stateful analysis is incorrect usage, and the call
 315         // to getCachedResult below asserts:
 316         // ```
 317         // if (TestModuleAnalysis::Result *TMA =
 318         //        MAMProxy.getCachedResult<TestModuleAnalysis>(
 319         //            *C.begin()->getFunction().getParent()))
 320         //   AnalyzedModuleFunctionCount1 += TMA->FunctionCount;
 321         // ```
 322         // For the purposes of this unittest, use the above MAM directly.
 323         if (TestModuleAnalysis::Result *TMA =
 324                 MAM.getCachedResult<TestModuleAnalysis>(
 325                     *C.begin()->getFunction().getParent()))
 326           AnalyzedModuleFunctionCount1 += TMA->FunctionCount;
 327
 328         FunctionAnalysisManager &FAM =
 329             AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 330         TestSCCAnalysis::Result &AR = AM.getResult<TestSCCAnalysis>(C, CG);
 331         AnalyzedSCCFunctionCount1 += AR.FunctionCount;
 332         for (LazyCallGraph::Node &N : C) {
 333           TestFunctionAnalysis::Result &FAR =
 334               FAM.getResult<TestFunctionAnalysis>(N.getFunction());
 335           AnalyzedInstrCount1 += FAR.InstructionCount;
 336
 337           // Just ensure we get the immutable results.
 338           (void)FAM.getResult<TestImmutableFunctionAnalysis>(N.getFunction());
 339         }
 340
 341         return PreservedAnalyses::all();
 342       }));
 343
 344   FunctionPassManager FPM2;
 345   int FunctionPassRunCount2 = 0;
 346   FPM2.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
 347     ++FunctionPassRunCount2;
 348     return PreservedAnalyses::none();
 349   }));
 350   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 351
 352   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 353
 354   FunctionPassManager FPM3;
 355   int FunctionPassRunCount3 = 0;
 356   FPM3.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
 357     ++FunctionPassRunCount3;
 358     return PreservedAnalyses::none();
 359   }));
 360   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM3)));
 361
 362   MPM.run(*M, MAM);
 363
 364   EXPECT_EQ(4, SCCPassRunCount1);
 365   EXPECT_EQ(6, FunctionPassRunCount1);
 366   EXPECT_EQ(6, FunctionPassRunCount2);
 367   EXPECT_EQ(6, FunctionPassRunCount3);
 368
 369   EXPECT_EQ(1, ModuleAnalysisRuns);
 370   EXPECT_EQ(4, SCCAnalysisRuns);
 371   EXPECT_EQ(6, FunctionAnalysisRuns);
 372   EXPECT_EQ(6, ImmutableFunctionAnalysisRuns);
 373
 374   EXPECT_EQ(14, AnalyzedInstrCount1);
 375   EXPECT_EQ(6, AnalyzedSCCFunctionCount1);
 376   EXPECT_EQ(4 * 6, AnalyzedModuleFunctionCount1);
 377 }
 378
 379 // Test that an SCC pass which fails to preserve a module analysis does in fact
 380 // invalidate that module analysis.
 381 TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesModuleAnalysis) {
 382   int ModuleAnalysisRuns = 0;
 383   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
 384
 385   ModulePassManager MPM;
 386   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
 387
 388   // The first CGSCC run we preserve everything and make sure that works and
 389   // the module analysis is available in the second CGSCC run from the one
 390   // required module pass above.
 391   CGSCCPassManager CGPM1;
 392   int CountFoundModuleAnalysis1 = 0;
 393   CGPM1.addPass(LambdaSCCPass([&](LazyCallGraph::SCC &C,
 394                                   CGSCCAnalysisManager &AM, LazyCallGraph &CG,
 395                                   CGSCCUpdateResult &UR) {
 396     const auto &MAMProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
 397     if (MAMProxy.cachedResultExists<TestModuleAnalysis>(
 398             *C.begin()->getFunction().getParent()))
 399       ++CountFoundModuleAnalysis1;
 400
 401     return PreservedAnalyses::all();
 402   }));
 403   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 404
 405   // The second CGSCC run checks that the module analysis got preserved the
 406   // previous time and in one SCC fails to preserve it.
 407   CGSCCPassManager CGPM2;
 408   int CountFoundModuleAnalysis2 = 0;
 409   CGPM2.addPass(
 410       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 411                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
 412         const auto &MAMProxy =
 413             AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
 414         if (MAMProxy.cachedResultExists<TestModuleAnalysis>(
 415                 *C.begin()->getFunction().getParent()))
 416           ++CountFoundModuleAnalysis2;
 417
 418         // Only fail to preserve analyses on one SCC and make sure that gets
 419         // propagated.
 420         return C.getName() == "(g)" ? PreservedAnalyses::none()
 421                                   : PreservedAnalyses::all();
 422       }));
 423   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 424
 425   // The third CGSCC run should fail to find a cached module analysis as it
 426   // should have been invalidated by the above CGSCC run.
 427   CGSCCPassManager CGPM3;
 428   int CountFoundModuleAnalysis3 = 0;
 429   CGPM3.addPass(LambdaSCCPass([&](LazyCallGraph::SCC &C,
 430                                   CGSCCAnalysisManager &AM, LazyCallGraph &CG,
 431                                   CGSCCUpdateResult &UR) {
 432     const auto &MAMProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
 433     if (MAMProxy.cachedResultExists<TestModuleAnalysis>(
 434             *C.begin()->getFunction().getParent()))
 435       ++CountFoundModuleAnalysis3;
 436
 437     return PreservedAnalyses::none();
 438   }));
 439   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM3)));
 440
 441   MPM.run(*M, MAM);
 442
 443   EXPECT_EQ(1, ModuleAnalysisRuns);
 444   EXPECT_EQ(4, CountFoundModuleAnalysis1);
 445   EXPECT_EQ(4, CountFoundModuleAnalysis2);
 446   EXPECT_EQ(0, CountFoundModuleAnalysis3);
 447 }
 448
 449 // Similar to the above, but test that this works for function passes embedded
 450 // *within* a CGSCC layer.
 451 TEST_F(CGSCCPassManagerTest, TestFunctionPassInsideCGSCCInvalidatesModuleAnalysis) {
 452   int ModuleAnalysisRuns = 0;
 453   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
 454
 455   ModulePassManager MPM;
 456   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
 457
 458   // The first run we preserve everything and make sure that works and the
 459   // module analysis is available in the second run from the one required
 460   // module pass above.
 461   FunctionPassManager FPM1;
 462   // Start true and mark false if we ever failed to find a module analysis
 463   // because we expect this to succeed for each SCC.
 464   bool FoundModuleAnalysis1 = true;
 465   FPM1.addPass(LambdaFunctionPass([&](Function &F,
 466                                       FunctionAnalysisManager &AM) {
 467     const auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
 468     if (!MAMProxy.cachedResultExists<TestModuleAnalysis>(*F.getParent()))
 469       FoundModuleAnalysis1 = false;
 470
 471     return PreservedAnalyses::all();
 472   }));
 473   CGSCCPassManager CGPM1;
 474   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 475   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 476
 477   // The second run checks that the module analysis got preserved the previous
 478   // time and in one function fails to preserve it.
 479   FunctionPassManager FPM2;
 480   // Again, start true and mark false if we ever failed to find a module analysis
 481   // because we expect this to succeed for each SCC.
 482   bool FoundModuleAnalysis2 = true;
 483   FPM2.addPass(LambdaFunctionPass([&](Function &F,
 484                                       FunctionAnalysisManager &AM) {
 485     const auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
 486     if (!MAMProxy.cachedResultExists<TestModuleAnalysis>(*F.getParent()))
 487       FoundModuleAnalysis2 = false;
 488
 489     // Only fail to preserve analyses on one SCC and make sure that gets
 490     // propagated.
 491     return F.getName() == "h2" ? PreservedAnalyses::none()
 492                                : PreservedAnalyses::all();
 493   }));
 494   CGSCCPassManager CGPM2;
 495   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 496   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 497
 498   // The third run should fail to find a cached module analysis as it should
 499   // have been invalidated by the above run.
 500   FunctionPassManager FPM3;
 501   // Start false and mark true if we ever *succeeded* to find a module
 502   // analysis, as we expect this to fail for every function.
 503   bool FoundModuleAnalysis3 = false;
 504   FPM3.addPass(LambdaFunctionPass([&](Function &F,
 505                                       FunctionAnalysisManager &AM) {
 506     const auto &MAMProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
 507     if (MAMProxy.cachedResultExists<TestModuleAnalysis>(*F.getParent()))
 508       FoundModuleAnalysis3 = true;
 509
 510     return PreservedAnalyses::none();
 511   }));
 512   CGSCCPassManager CGPM3;
 513   CGPM3.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM3)));
 514   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM3)));
 515
 516   MPM.run(*M, MAM);
 517
 518   EXPECT_EQ(1, ModuleAnalysisRuns);
 519   EXPECT_TRUE(FoundModuleAnalysis1);
 520   EXPECT_TRUE(FoundModuleAnalysis2);
 521   EXPECT_FALSE(FoundModuleAnalysis3);
 522 }
 523
 524 // Test that a Module pass which fails to preserve an SCC analysis in fact
 525 // invalidates that analysis.
 526 TEST_F(CGSCCPassManagerTest, TestModulePassInvalidatesSCCAnalysis) {
 527   int SCCAnalysisRuns = 0;
 528   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 529
 530   ModulePassManager MPM;
 531
 532   // First force the analysis to be run.
 533   CGSCCPassManager CGPM1;
 534   CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 535                                     CGSCCAnalysisManager, LazyCallGraph &,
 536                                     CGSCCUpdateResult &>());
 537   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 538
 539   // Now run a module pass that preserves the LazyCallGraph and the proxy but
 540   // not the SCC analysis.
 541   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 542     PreservedAnalyses PA;
 543     PA.preserve<LazyCallGraphAnalysis>();
 544     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 545     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 546     return PA;
 547   }));
 548
 549   // And now a second CGSCC run which requires the SCC analysis again. This
 550   // will trigger re-running it.
 551   CGSCCPassManager CGPM2;
 552   CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 553                                     CGSCCAnalysisManager, LazyCallGraph &,
 554                                     CGSCCUpdateResult &>());
 555   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 556
 557   MPM.run(*M, MAM);
 558   // Two runs and four SCCs.
 559   EXPECT_EQ(2 * 4, SCCAnalysisRuns);
 560 }
 561
 562 // Check that marking the SCC analysis preserved is sufficient to avoid
 563 // invaliadtion. This should only run the analysis once for each SCC.
 564 TEST_F(CGSCCPassManagerTest, TestModulePassCanPreserveSCCAnalysis) {
 565   int SCCAnalysisRuns = 0;
 566   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 567
 568   ModulePassManager MPM;
 569
 570   // First force the analysis to be run.
 571   CGSCCPassManager CGPM1;
 572   CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 573                                     CGSCCAnalysisManager, LazyCallGraph &,
 574                                     CGSCCUpdateResult &>());
 575   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 576
 577   // Now run a module pass that preserves each of the necessary components
 578   // (but not everything).
 579   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 580     PreservedAnalyses PA;
 581     PA.preserve<LazyCallGraphAnalysis>();
 582     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 583     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 584     PA.preserve<TestSCCAnalysis>();
 585     return PA;
 586   }));
 587
 588   // And now a second CGSCC run which requires the SCC analysis again but find
 589   // it in the cache.
 590   CGSCCPassManager CGPM2;
 591   CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 592                                     CGSCCAnalysisManager, LazyCallGraph &,
 593                                     CGSCCUpdateResult &>());
 594   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 595
 596   MPM.run(*M, MAM);
 597   // Four SCCs
 598   EXPECT_EQ(4, SCCAnalysisRuns);
 599 }
 600
 601 // Check that even when the analysis is preserved, if the SCC information isn't
 602 // we still nuke things because the SCC keys could change.
 603 TEST_F(CGSCCPassManagerTest, TestModulePassInvalidatesSCCAnalysisOnCGChange) {
 604   int SCCAnalysisRuns = 0;
 605   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 606
 607   ModulePassManager MPM;
 608
 609   // First force the analysis to be run.
 610   CGSCCPassManager CGPM1;
 611   CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 612                                     CGSCCAnalysisManager, LazyCallGraph &,
 613                                     CGSCCUpdateResult &>());
 614   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 615
 616   // Now run a module pass that preserves the analysis but not the call
 617   // graph or proxy.
 618   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 619     PreservedAnalyses PA;
 620     PA.preserve<TestSCCAnalysis>();
 621     return PA;
 622   }));
 623
 624   // And now a second CGSCC run which requires the SCC analysis again.
 625   CGSCCPassManager CGPM2;
 626   CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 627                                     CGSCCAnalysisManager, LazyCallGraph &,
 628                                     CGSCCUpdateResult &>());
 629   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 630
 631   MPM.run(*M, MAM);
 632   // Two runs and four SCCs.
 633   EXPECT_EQ(2 * 4, SCCAnalysisRuns);
 634 }
 635
 636 // Test that an SCC pass which fails to preserve a Function analysis in fact
 637 // invalidates that analysis.
 638 TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesFunctionAnalysis) {
 639   int FunctionAnalysisRuns = 0;
 640   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 641
 642   // Create a very simple module with a single function and SCC to make testing
 643   // these issues much easier.
 644   std::unique_ptr<Module> M = parseIR("declare void @g()\n"
 645                                       "declare void @h()\n"
 646                                       "define void @f() {\n"
 647                                       "entry:\n"
 648                                       "  call void @g()\n"
 649                                       "  call void @h()\n"
 650                                       "  ret void\n"
 651                                       "}\n");
 652
 653   CGSCCPassManager CGPM;
 654
 655   // First force the analysis to be run.
 656   FunctionPassManager FPM1;
 657   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 658   CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 659
 660   // Now run a module pass that preserves the LazyCallGraph and proxy but not
 661   // the SCC analysis.
 662   CGPM.addPass(LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &,
 663                                  LazyCallGraph &, CGSCCUpdateResult &) {
 664     PreservedAnalyses PA;
 665     PA.preserve<LazyCallGraphAnalysis>();
 666     return PA;
 667   }));
 668
 669   // And now a second CGSCC run which requires the SCC analysis again. This
 670   // will trigger re-running it.
 671   FunctionPassManager FPM2;
 672   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 673   CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 674
 675   ModulePassManager MPM;
 676   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
 677   MPM.run(*M, MAM);
 678   EXPECT_EQ(2, FunctionAnalysisRuns);
 679 }
 680
 681 // Check that marking the SCC analysis preserved is sufficient. This should
 682 // only run the analysis once the SCC.
 683 TEST_F(CGSCCPassManagerTest, TestSCCPassCanPreserveFunctionAnalysis) {
 684   int FunctionAnalysisRuns = 0;
 685   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 686
 687   // Create a very simple module with a single function and SCC to make testing
 688   // these issues much easier.
 689   std::unique_ptr<Module> M = parseIR("declare void @g()\n"
 690                                       "declare void @h()\n"
 691                                       "define void @f() {\n"
 692                                       "entry:\n"
 693                                       "  call void @g()\n"
 694                                       "  call void @h()\n"
 695                                       "  ret void\n"
 696                                       "}\n");
 697
 698   CGSCCPassManager CGPM;
 699
 700   // First force the analysis to be run.
 701   FunctionPassManager FPM1;
 702   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 703   CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 704
 705   // Now run a module pass that preserves each of the necessary components
 706   // (but
 707   // not everything).
 708   CGPM.addPass(LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &,
 709                                  LazyCallGraph &, CGSCCUpdateResult &) {
 710     PreservedAnalyses PA;
 711     PA.preserve<LazyCallGraphAnalysis>();
 712     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 713     PA.preserve<TestFunctionAnalysis>();
 714     return PA;
 715   }));
 716
 717   // And now a second CGSCC run which requires the SCC analysis again but find
 718   // it in the cache.
 719   FunctionPassManager FPM2;
 720   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 721   CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 722
 723   ModulePassManager MPM;
 724   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
 725   MPM.run(*M, MAM);
 726   EXPECT_EQ(1, FunctionAnalysisRuns);
 727 }
 728
 729 // Note that there is no test for invalidating the call graph or other
 730 // structure with an SCC pass because there is no mechanism to do that from
 731 // withinsuch a pass. Instead, such a pass has to directly update the call
 732 // graph structure.
 733
 734 // Test that a madule pass invalidates function analyses when the CGSCC proxies
 735 // and pass manager.
 736 TEST_F(CGSCCPassManagerTest,
 737        TestModulePassInvalidatesFunctionAnalysisNestedInCGSCC) {
 738   MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
 739
 740   int FunctionAnalysisRuns = 0;
 741   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 742
 743   ModulePassManager MPM;
 744
 745   // First force the analysis to be run.
 746   FunctionPassManager FPM1;
 747   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 748   CGSCCPassManager CGPM1;
 749   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 750   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 751
 752   // Now run a module pass that preserves the LazyCallGraph and proxies but not
 753   // the Function analysis.
 754   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 755     PreservedAnalyses PA;
 756     PA.preserve<LazyCallGraphAnalysis>();
 757     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 758     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 759     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 760     return PA;
 761   }));
 762
 763   // And now a second CGSCC run which requires the SCC analysis again. This
 764   // will trigger re-running it.
 765   FunctionPassManager FPM2;
 766   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 767   CGSCCPassManager CGPM2;
 768   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 769   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 770
 771   MPM.run(*M, MAM);
 772   // Two runs and 6 functions.
 773   EXPECT_EQ(2 * 6, FunctionAnalysisRuns);
 774 }
 775
 776 // Check that by marking the function pass and proxies as preserved, this
 777 // propagates all the way through.
 778 TEST_F(CGSCCPassManagerTest,
 779        TestModulePassCanPreserveFunctionAnalysisNestedInCGSCC) {
 780   MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
 781
 782   int FunctionAnalysisRuns = 0;
 783   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 784
 785   ModulePassManager MPM;
 786
 787   // First force the analysis to be run.
 788   FunctionPassManager FPM1;
 789   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 790   CGSCCPassManager CGPM1;
 791   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 792   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 793
 794   // Now run a module pass that preserves the LazyCallGraph, the proxy, and
 795   // the Function analysis.
 796   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 797     PreservedAnalyses PA;
 798     PA.preserve<LazyCallGraphAnalysis>();
 799     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 800     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 801     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 802     PA.preserve<TestFunctionAnalysis>();
 803     return PA;
 804   }));
 805
 806   // And now a second CGSCC run which requires the SCC analysis again. This
 807   // will trigger re-running it.
 808   FunctionPassManager FPM2;
 809   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 810   CGSCCPassManager CGPM2;
 811   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 812   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 813
 814   MPM.run(*M, MAM);
 815   // One run and 6 functions.
 816   EXPECT_EQ(6, FunctionAnalysisRuns);
 817 }
 818
 819 // Check that if the lazy call graph itself isn't preserved we still manage to
 820 // invalidate everything.
 821 TEST_F(CGSCCPassManagerTest,
 822        TestModulePassInvalidatesFunctionAnalysisNestedInCGSCCOnCGChange) {
 823   MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
 824
 825   int FunctionAnalysisRuns = 0;
 826   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 827
 828   ModulePassManager MPM;
 829
 830   // First force the analysis to be run.
 831   FunctionPassManager FPM1;
 832   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 833   CGSCCPassManager CGPM1;
 834   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 835   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 836
 837   // Now run a module pass that preserves the LazyCallGraph but not the
 838   // Function analysis.
 839   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 840     PreservedAnalyses PA;
 841     return PA;
 842   }));
 843
 844   // And now a second CGSCC run which requires the SCC analysis again. This
 845   // will trigger re-running it.
 846   FunctionPassManager FPM2;
 847   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 848   CGSCCPassManager CGPM2;
 849   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 850   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 851
 852   MPM.run(*M, MAM);
 853   // Two runs and 6 functions.
 854   EXPECT_EQ(2 * 6, FunctionAnalysisRuns);
 855 }
 856
 857 /// A test CGSCC-level analysis pass which caches in its result another
 858 /// analysis pass and uses it to serve queries. This requires the result to
 859 /// invalidate itself when its dependency is invalidated.
 860 ///
 861 /// FIXME: Currently this doesn't also depend on a function analysis, and if it
 862 /// did we would fail to invalidate it correctly.
 863 struct TestIndirectSCCAnalysis
 864     : public AnalysisInfoMixin<TestIndirectSCCAnalysis> {
 865   struct Result {
 866     Result(TestSCCAnalysis::Result &SCCDep, TestModuleAnalysis::Result &MDep)
 867         : SCCDep(SCCDep), MDep(MDep) {}
 868     TestSCCAnalysis::Result &SCCDep;
 869     TestModuleAnalysis::Result &MDep;
 870
 871     bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
 872                     CGSCCAnalysisManager::Invalidator &Inv) {
 873       auto PAC = PA.getChecker<TestIndirectSCCAnalysis>();
 874       return !(PAC.preserved() ||
 875                PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) ||
 876              Inv.invalidate<TestSCCAnalysis>(C, PA);
 877     }
 878   };
 879
 880   TestIndirectSCCAnalysis(int &Runs, ModuleAnalysisManager &MAM)
 881       : Runs(Runs), MAM(MAM) {}
 882
 883   /// Run the analysis pass over the function and return a result.
 884   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 885              LazyCallGraph &CG) {
 886     ++Runs;
 887     auto &SCCDep = AM.getResult<TestSCCAnalysis>(C, CG);
 888
 889     auto &ModuleProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
 890     // For the test, we insist that the module analysis starts off in the
 891     // cache. Getting a cached result that isn't stateless triggers an assert.
 892     // auto &MDep = *ModuleProxy.getCachedResult<TestModuleAnalysis>(
 893     //  *C.begin()->getFunction().getParent());
 894     // Use MAM, for the purposes of this unittest.
 895     auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(
 896         *C.begin()->getFunction().getParent());
 897     // Register the dependency as module analysis dependencies have to be
 898     // pre-registered on the proxy.
 899     ModuleProxy.registerOuterAnalysisInvalidation<TestModuleAnalysis,
 900                                                   TestIndirectSCCAnalysis>();
 901
 902     return Result(SCCDep, MDep);
 903   }
 904
 905 private:
 906   friend AnalysisInfoMixin<TestIndirectSCCAnalysis>;
 907   static AnalysisKey Key;
 908
 909   int &Runs;
 910   ModuleAnalysisManager &MAM;
 911 };
 912
 913 AnalysisKey TestIndirectSCCAnalysis::Key;
 914
 915 /// A test analysis pass which caches in its result the result from the above
 916 /// indirect analysis pass.
 917 ///
 918 /// This allows us to ensure that whenever an analysis pass is invalidated due
 919 /// to dependencies (especially dependencies across IR units that trigger
 920 /// asynchronous invalidation) we correctly detect that this may in turn cause
 921 /// other analysis to be invalidated.
 922 struct TestDoublyIndirectSCCAnalysis
 923     : public AnalysisInfoMixin<TestDoublyIndirectSCCAnalysis> {
 924   struct Result {
 925     Result(TestIndirectSCCAnalysis::Result &IDep) : IDep(IDep) {}
 926     TestIndirectSCCAnalysis::Result &IDep;
 927
 928     bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
 929                     CGSCCAnalysisManager::Invalidator &Inv) {
 930       auto PAC = PA.getChecker<TestDoublyIndirectSCCAnalysis>();
 931       return !(PAC.preserved() ||
 932                PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) ||
 933              Inv.invalidate<TestIndirectSCCAnalysis>(C, PA);
 934     }
 935   };
 936
 937   TestDoublyIndirectSCCAnalysis(int &Runs) : Runs(Runs) {}
 938
 939   /// Run the analysis pass over the function and return a result.
 940   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 941              LazyCallGraph &CG) {
 942     ++Runs;
 943     auto &IDep = AM.getResult<TestIndirectSCCAnalysis>(C, CG);
 944     return Result(IDep);
 945   }
 946
 947 private:
 948   friend AnalysisInfoMixin<TestDoublyIndirectSCCAnalysis>;
 949   static AnalysisKey Key;
 950
 951   int &Runs;
 952 };
 953
 954 AnalysisKey TestDoublyIndirectSCCAnalysis::Key;
 955
 956 /// A test analysis pass which caches results from three different IR unit
 957 /// layers and requires intermediate layers to correctly propagate the entire
 958 /// distance.
 959 struct TestIndirectFunctionAnalysis
 960     : public AnalysisInfoMixin<TestIndirectFunctionAnalysis> {
 961   struct Result {
 962     Result(TestFunctionAnalysis::Result &FDep, TestModuleAnalysis::Result &MDep,
 963            TestSCCAnalysis::Result &SCCDep)
 964         : FDep(FDep), MDep(MDep), SCCDep(SCCDep) {}
 965     TestFunctionAnalysis::Result &FDep;
 966     TestModuleAnalysis::Result &MDep;
 967     TestSCCAnalysis::Result &SCCDep;
 968
 969     bool invalidate(Function &F, const PreservedAnalyses &PA,
 970                     FunctionAnalysisManager::Invalidator &Inv) {
 971       auto PAC = PA.getChecker<TestIndirectFunctionAnalysis>();
 972       return !(PAC.preserved() ||
 973                PAC.preservedSet<AllAnalysesOn<Function>>()) ||
 974              Inv.invalidate<TestFunctionAnalysis>(F, PA);
 975     }
 976   };
 977
 978   TestIndirectFunctionAnalysis(int &Runs, ModuleAnalysisManager &MAM,
 979                                CGSCCAnalysisManager &CGAM)
 980       : Runs(Runs), MAM(MAM), CGAM(CGAM) {}
 981
 982   /// Run the analysis pass over the function and return a result.
 983   Result run(Function &F, FunctionAnalysisManager &AM) {
 984     ++Runs;
 985     auto &FDep = AM.getResult<TestFunctionAnalysis>(F);
 986
 987     auto &ModuleProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
 988     // For the test, we insist that the module analysis starts off in the
 989     // cache. Getting a cached result that isn't stateless triggers an assert.
 990     // Use MAM, for the purposes of this unittest.
 991     auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(*F.getParent());
 992     // Register the dependency as module analysis dependencies have to be
 993     // pre-registered on the proxy.
 994     ModuleProxy.registerOuterAnalysisInvalidation<
 995         TestModuleAnalysis, TestIndirectFunctionAnalysis>();
 996
 997     // For the test we assume this is run inside a CGSCC pass manager.
 998     // Use MAM, for the purposes of this unittest.
 999     const LazyCallGraph &CG =
1000         *MAM.getCachedResult<LazyCallGraphAnalysis>(*F.getParent());
1001     auto &CGSCCProxy = AM.getResult<CGSCCAnalysisManagerFunctionProxy>(F);
1002     // For the test, we insist that the CGSCC analysis starts off in the cache.
1003     // Getting a cached result that isn't stateless triggers an assert.
1004     // Use CGAM, for the purposes of this unittest.
1005     auto &SCCDep =
1006         *CGAM.getCachedResult<TestSCCAnalysis>(*CG.lookupSCC(*CG.lookup(F)));
1007     // Register the dependency as CGSCC analysis dependencies have to be
1008     // pre-registered on the proxy.
1009     CGSCCProxy.registerOuterAnalysisInvalidation<
1010         TestSCCAnalysis, TestIndirectFunctionAnalysis>();
1011
1012     return Result(FDep, MDep, SCCDep);
1013   }
1014
1015 private:
1016   friend AnalysisInfoMixin<TestIndirectFunctionAnalysis>;
1017   static AnalysisKey Key;
1018
1019   int &Runs;
1020   ModuleAnalysisManager &MAM;
1021   CGSCCAnalysisManager &CGAM;
1022 };
1023
1024 AnalysisKey TestIndirectFunctionAnalysis::Key;
1025
1026 TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
1027   int ModuleAnalysisRuns = 0;
1028   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
1029
1030   int SCCAnalysisRuns = 0, IndirectSCCAnalysisRuns = 0,
1031       DoublyIndirectSCCAnalysisRuns = 0;
1032   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
1033   CGAM.registerPass(
1034       [&] { return TestIndirectSCCAnalysis(IndirectSCCAnalysisRuns, MAM); });
1035   CGAM.registerPass([&] {
1036     return TestDoublyIndirectSCCAnalysis(DoublyIndirectSCCAnalysisRuns);
1037   });
1038
1039   int FunctionAnalysisRuns = 0, IndirectFunctionAnalysisRuns = 0;
1040   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
1041   FAM.registerPass([&] {
1042     return TestIndirectFunctionAnalysis(IndirectFunctionAnalysisRuns, MAM,
1043                                         CGAM);
1044   });
1045
1046   ModulePassManager MPM;
1047
1048   int FunctionCount = 0;
1049   CGSCCPassManager CGPM;
1050   // First just use the analysis to get the function count and preserve
1051   // everything.
1052   CGPM.addPass(
1053       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1054                         LazyCallGraph &CG, CGSCCUpdateResult &) {
1055         auto &DoublyIndirectResult =
1056             AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1057         auto &IndirectResult = DoublyIndirectResult.IDep;
1058         FunctionCount += IndirectResult.SCCDep.FunctionCount;
1059         return PreservedAnalyses::all();
1060       }));
1061   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1062       RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
1063
1064   // Next, invalidate
1065   //   - both analyses for the (f) and (x) SCCs,
1066   //   - just the underlying (indirect) analysis for (g) SCC, and
1067   //   - just the direct analysis for (h1,h2,h3) SCC.
1068   CGPM.addPass(
1069       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1070                         LazyCallGraph &CG, CGSCCUpdateResult &) {
1071         auto &DoublyIndirectResult =
1072             AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1073         auto &IndirectResult = DoublyIndirectResult.IDep;
1074         FunctionCount += IndirectResult.SCCDep.FunctionCount;
1075         auto PA = PreservedAnalyses::none();
1076         PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1077         PA.preserveSet<AllAnalysesOn<Function>>();
1078         if (C.getName() == "(g)")
1079           PA.preserve<TestSCCAnalysis>();
1080         else if (C.getName() == "(h3, h1, h2)")
1081           PA.preserve<TestIndirectSCCAnalysis>();
1082         return PA;
1083       }));
1084   // Finally, use the analysis again on each SCC (and function), forcing
1085   // re-computation for all of them.
1086   CGPM.addPass(
1087       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1088                         LazyCallGraph &CG, CGSCCUpdateResult &) {
1089         auto &DoublyIndirectResult =
1090             AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1091         auto &IndirectResult = DoublyIndirectResult.IDep;
1092         FunctionCount += IndirectResult.SCCDep.FunctionCount;
1093         return PreservedAnalyses::all();
1094       }));
1095   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1096       RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
1097
1098   // Create a second CGSCC pass manager. This will cause the module-level
1099   // invalidation to occur, which will force yet another invalidation of the
1100   // indirect SCC-level analysis as the module analysis it depends on gets
1101   // invalidated.
1102   CGSCCPassManager CGPM2;
1103   CGPM2.addPass(
1104       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1105                         LazyCallGraph &CG, CGSCCUpdateResult &) {
1106         auto &DoublyIndirectResult =
1107             AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1108         auto &IndirectResult = DoublyIndirectResult.IDep;
1109         FunctionCount += IndirectResult.SCCDep.FunctionCount;
1110         return PreservedAnalyses::all();
1111       }));
1112   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(
1113       RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
1114
1115   // Add a requires pass to populate the module analysis and then our CGSCC
1116   // pass pipeline.
1117   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1118   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1119   // Now require the module analysis again (it will have been invalidated once)
1120   // and then use it again from our second CGSCC pipeline..
1121   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1122   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
1123   MPM.run(*M, MAM);
1124
1125   // There are generally two possible runs for each of the four SCCs. But
1126   // for one SCC, we only invalidate the indirect analysis so the base one
1127   // only gets run seven times.
1128   EXPECT_EQ(7, SCCAnalysisRuns);
1129   // The module analysis pass should be run twice here.
1130   EXPECT_EQ(2, ModuleAnalysisRuns);
1131   // The indirect analysis is invalidated (either directly or indirectly) three
1132   // times for each of four SCCs.
1133   EXPECT_EQ(3 * 4, IndirectSCCAnalysisRuns);
1134   EXPECT_EQ(3 * 4, DoublyIndirectSCCAnalysisRuns);
1135
1136   // We run the indirect function analysis once per function the first time.
1137   // Then we re-run it for every SCC but "(g)". Then we re-run it for every
1138   // function again.
1139   EXPECT_EQ(6 + 5 + 6, IndirectFunctionAnalysisRuns);
1140
1141   // Four passes count each of six functions once (via SCCs).
1142   EXPECT_EQ(4 * 6, FunctionCount);
1143 }
1144
1145 TEST_F(CGSCCPassManagerTest, TestAnalysisInvalidationCGSCCUpdate) {
1146   int ModuleAnalysisRuns = 0;
1147   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
1148
1149   int SCCAnalysisRuns = 0, IndirectSCCAnalysisRuns = 0,
1150       DoublyIndirectSCCAnalysisRuns = 0;
1151   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
1152   CGAM.registerPass(
1153       [&] { return TestIndirectSCCAnalysis(IndirectSCCAnalysisRuns, MAM); });
1154   CGAM.registerPass([&] {
1155     return TestDoublyIndirectSCCAnalysis(DoublyIndirectSCCAnalysisRuns);
1156   });
1157
1158   int FunctionAnalysisRuns = 0, IndirectFunctionAnalysisRuns = 0;
1159   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
1160   FAM.registerPass([&] {
1161     return TestIndirectFunctionAnalysis(IndirectFunctionAnalysisRuns, MAM,
1162                                         CGAM);
1163   });
1164
1165   ModulePassManager MPM;
1166
1167   CGSCCPassManager CGPM;
1168   // First just use the analysis to get the function count and preserve
1169   // everything.
1170   using RequireTestIndirectFunctionAnalysisPass =
1171       RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>;
1172   using RequireTestDoublyIndirectSCCAnalysisPass =
1173       RequireAnalysisPass<TestDoublyIndirectSCCAnalysis, LazyCallGraph::SCC,
1174                           CGSCCAnalysisManager, LazyCallGraph &,
1175                           CGSCCUpdateResult &>;
1176   CGPM.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1177   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1178       RequireTestIndirectFunctionAnalysisPass()));
1179
1180   // Next, we inject an SCC pass that invalidates everything for the `(h3, h1,
1181   // h2)` SCC but also deletes the call edge from `h2` to `h3` and updates the
1182   // CG. This should successfully invalidate (and force to be re-run) all the
1183   // analyses for that SCC and for the functions.
1184   CGPM.addPass(
1185       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1186                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
1187         (void)AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1188         if (C.getName() != "(h3, h1, h2)")
1189           return PreservedAnalyses::all();
1190
1191         // Build the preserved set.
1192         auto PA = PreservedAnalyses::none();
1193         PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1194         PA.preserve<TestIndirectSCCAnalysis>();
1195         PA.preserve<TestDoublyIndirectSCCAnalysis>();
1196
1197         // Delete the call from `h2` to `h3`.
1198         auto &H2N = *llvm::find_if(
1199             C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; });
1200         auto &H2F = H2N.getFunction();
1201         auto &H3F = *cast<CallInst>(H2F.begin()->begin())->getCalledFunction();
1202         assert(H3F.getName() == "h3" && "Wrong called function!");
1203         H2F.begin()->begin()->eraseFromParent();
1204         // Insert a bitcast of `h3` so that we retain a ref edge to it.
1205         (void)CastInst::CreatePointerCast(&H3F,
1206                                           Type::getInt8PtrTy(H2F.getContext()),
1207                                           "dummy", &*H2F.begin()->begin());
1208
1209         // Now update the call graph.
1210         auto &NewC =
1211             updateCGAndAnalysisManagerForFunctionPass(CG, C, H2N, AM, UR, FAM);
1212         assert(&NewC != &C && "Should get a new SCC due to update!");
1213         (void)&NewC;
1214
1215         return PA;
1216       }));
1217   // Now use the analysis again on each SCC and function, forcing
1218   // re-computation for all of them.
1219   CGPM.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1220   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1221       RequireTestIndirectFunctionAnalysisPass()));
1222
1223   // Create another CGSCC pipeline that requires all the analyses again.
1224   CGSCCPassManager CGPM2;
1225   CGPM2.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1226   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(
1227       RequireTestIndirectFunctionAnalysisPass()));
1228
1229   // Next we inject an SCC pass that finds the `(h2)` SCC, adds a call to `h3`
1230   // back to `h2`, and then invalidates everything for what will then be the
1231   // `(h3, h1, h2)` SCC again.
1232   CGSCCPassManager CGPM3;
1233   CGPM3.addPass(
1234       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1235                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
1236         (void)AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1237         if (C.getName() != "(h2)")
1238           return PreservedAnalyses::all();
1239
1240         // Build the preserved set.
1241         auto PA = PreservedAnalyses::none();
1242         PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1243         PA.preserve<TestIndirectSCCAnalysis>();
1244         PA.preserve<TestDoublyIndirectSCCAnalysis>();
1245
1246         // Delete the bitcast of `h3` that we added earlier.
1247         auto &H2N = *C.begin();
1248         auto &H2F = H2N.getFunction();
1249         auto &H3F = *cast<Function>(cast<BitCastInst>(H2F.begin()->begin())->getOperand(0));
1250         assert(H3F.getName() == "h3" && "Wrong called function!");
1251         H2F.begin()->begin()->eraseFromParent();
1252         // And insert a call to `h3`.
1253         (void)CallInst::Create(&H3F, {}, "", &*H2F.begin()->begin());
1254
1255         // Now update the call graph.
1256         auto &NewC =
1257             updateCGAndAnalysisManagerForFunctionPass(CG, C, H2N, AM, UR, FAM);
1258         assert(&NewC != &C && "Should get a new SCC due to update!");
1259         (void)&NewC;
1260
1261         return PA;
1262       }));
1263   // Now use the analysis again on each SCC and function, forcing
1264   // re-computation for all of them.
1265   CGPM3.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1266   CGPM3.addPass(createCGSCCToFunctionPassAdaptor(
1267       RequireTestIndirectFunctionAnalysisPass()));
1268
1269   // Create a second CGSCC pass manager. This will cause the module-level
1270   // invalidation to occur, which will force yet another invalidation of the
1271   // indirect SCC-level analysis as the module analysis it depends on gets
1272   // invalidated.
1273   CGSCCPassManager CGPM4;
1274   CGPM4.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1275   CGPM4.addPass(createCGSCCToFunctionPassAdaptor(
1276       RequireTestIndirectFunctionAnalysisPass()));
1277
1278   // Add a requires pass to populate the module analysis and then one of our
1279   // CGSCC pipelines. Repeat for all four CGSCC pipelines.
1280   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1281   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1282   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1283   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
1284   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1285   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM3)));
1286   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1287   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM4)));
1288   MPM.run(*M, MAM);
1289
1290   // We run over four SCCs the first time. But then we split an SCC into three.
1291   // And then we merge those three back into one. However, this also
1292   // invalidates all three SCCs further down in the PO walk.
1293   EXPECT_EQ(4 + 3 + 3, SCCAnalysisRuns);
1294   // The module analysis pass should be run three times.
1295   EXPECT_EQ(3, ModuleAnalysisRuns);
1296   // We run over four SCCs the first time. Then over the two new ones. Then the
1297   // entire module is invalidated causing a full run over all seven. Then we
1298   // fold three SCCs back to one, re-compute for it and the two SCCs above it
1299   // in the graph, and then run over the whole module again.
1300   EXPECT_EQ(4 + 2 + 7 + 3 + 4, IndirectSCCAnalysisRuns);
1301   EXPECT_EQ(4 + 2 + 7 + 3 + 4, DoublyIndirectSCCAnalysisRuns);
1302
1303   // First we run over all six functions. Then we re-run it over three when we
1304   // split their SCCs. Then we re-run over the whole module. Then we re-run
1305   // over three functions merged back into a single SCC, then those three
1306   // functions again, the two functions in SCCs above it in the graph, and then
1307   // over the whole module again.
1308   EXPECT_EQ(6 + 3 + 6 + 3 + 2 + 6, FunctionAnalysisRuns);
1309
1310   // Re run the function analysis over the entire module, and then re-run it
1311   // over the `(h3, h1, h2)` SCC due to invalidation. Then we re-run it over
1312   // the entire module, then the three functions merged back into a single SCC,
1313   // those three functions again, then the two functions in SCCs above it in
1314   // the graph, and then over the whole module.
1315   EXPECT_EQ(6 + 3 + 6 + 3 + 2 + 6, IndirectFunctionAnalysisRuns);
1316 }
1317
1318 // The (negative) tests below check for assertions so we only run them if NDEBUG
1319 // is not defined.
1320 #ifndef NDEBUG
1321
1322 struct LambdaSCCPassNoPreserve : public PassInfoMixin<LambdaSCCPassNoPreserve> {
1323   template <typename T>
1324   LambdaSCCPassNoPreserve(T &&Arg) : Func(std::forward<T>(Arg)) {}
1325
1326   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1327                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
1328     Func(C, AM, CG, UR);
1329     PreservedAnalyses PA;
1330     // We update the core CGSCC data structures and so can preserve the proxy to
1331     // the function analysis manager.
1332     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1333     return PA;
1334   }
1335
1336   std::function<void(LazyCallGraph::SCC &, CGSCCAnalysisManager &,
1337                      LazyCallGraph &, CGSCCUpdateResult &)>
1338       Func;
1339 };
1340
1341 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses0) {
1342   CGSCCPassManager CGPM;
1343   CGPM.addPass(LambdaSCCPassNoPreserve(
1344       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1345           CGSCCUpdateResult &UR) {
1346         if (C.getName() != "(h3, h1, h2)")
1347           return;
1348
1349         auto &FAM =
1350             AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1351         Function *FnX = M->getFunction("x");
1352         Function *FnH1 = M->getFunction("h1");
1353         Function *FnH2 = M->getFunction("h2");
1354         Function *FnH3 = M->getFunction("h3");
1355         ASSERT_NE(FnX, nullptr);
1356         ASSERT_NE(FnH1, nullptr);
1357         ASSERT_NE(FnH2, nullptr);
1358         ASSERT_NE(FnH3, nullptr);
1359
1360         // And insert a call to `h1`, `h2`, and `h3`.
1361         Instruction *IP = &FnH2->getEntryBlock().front();
1362         (void)CallInst::Create(FnH1, {}, "", IP);
1363         (void)CallInst::Create(FnH2, {}, "", IP);
1364         (void)CallInst::Create(FnH3, {}, "", IP);
1365
1366         auto &H2N = *llvm::find_if(
1367             C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; });
1368         ASSERT_NO_FATAL_FAILURE(
1369             updateCGAndAnalysisManagerForCGSCCPass(CG, C, H2N, AM, UR, FAM));
1370       }));
1371
1372   ModulePassManager MPM;
1373   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1374   MPM.run(*M, MAM);
1375 }
1376
1377 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses1) {
1378   CGSCCPassManager CGPM;
1379   CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
1380                                            CGSCCAnalysisManager &AM,
1381                                            LazyCallGraph &CG,
1382                                            CGSCCUpdateResult &UR) {
1383     if (C.getName() != "(h3, h1, h2)")
1384       return;
1385
1386     auto &FAM =
1387         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1388     Function *FnX = M->getFunction("x");
1389     Function *FnH1 = M->getFunction("h1");
1390     Function *FnH2 = M->getFunction("h2");
1391     Function *FnH3 = M->getFunction("h3");
1392     ASSERT_NE(FnX, nullptr);
1393     ASSERT_NE(FnH1, nullptr);
1394     ASSERT_NE(FnH2, nullptr);
1395     ASSERT_NE(FnH3, nullptr);
1396
1397     // And insert a call to `h1`, `h2`, and `h3`.
1398     Instruction *IP = &FnH2->getEntryBlock().front();
1399     (void)CallInst::Create(FnH1, {}, "", IP);
1400     (void)CallInst::Create(FnH2, {}, "", IP);
1401     (void)CallInst::Create(FnH3, {}, "", IP);
1402
1403     auto &H2N = *llvm::find_if(
1404         C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; });
1405     ASSERT_DEATH(
1406         updateCGAndAnalysisManagerForFunctionPass(CG, C, H2N, AM, UR, FAM),
1407         "Any new calls should be modeled as");
1408   }));
1409
1410   ModulePassManager MPM;
1411   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1412   MPM.run(*M, MAM);
1413 }
1414
1415 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses2) {
1416   CGSCCPassManager CGPM;
1417   CGPM.addPass(LambdaSCCPassNoPreserve(
1418       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1419           CGSCCUpdateResult &UR) {
1420         if (C.getName() != "(f)")
1421           return;
1422
1423         auto &FAM =
1424             AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1425         Function *FnF = M->getFunction("f");
1426         Function *FnH2 = M->getFunction("h2");
1427         ASSERT_NE(FnF, nullptr);
1428         ASSERT_NE(FnH2, nullptr);
1429
1430         // And insert a call to `h2`
1431         Instruction *IP = &FnF->getEntryBlock().front();
1432         (void)CallInst::Create(FnH2, {}, "", IP);
1433
1434         auto &FN = *llvm::find_if(
1435             C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
1436         ASSERT_NO_FATAL_FAILURE(
1437             updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR, FAM));
1438       }));
1439
1440   ModulePassManager MPM;
1441   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1442   MPM.run(*M, MAM);
1443 }
1444
1445 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses3) {
1446   CGSCCPassManager CGPM;
1447   CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
1448                                            CGSCCAnalysisManager &AM,
1449                                            LazyCallGraph &CG,
1450                                            CGSCCUpdateResult &UR) {
1451     if (C.getName() != "(f)")
1452       return;
1453
1454     auto &FAM =
1455         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1456     Function *FnF = M->getFunction("f");
1457     Function *FnH2 = M->getFunction("h2");
1458     ASSERT_NE(FnF, nullptr);
1459     ASSERT_NE(FnH2, nullptr);
1460
1461     // And insert a call to `h2`
1462     Instruction *IP = &FnF->getEntryBlock().front();
1463     (void)CallInst::Create(FnH2, {}, "", IP);
1464
1465     auto &FN = *llvm::find_if(
1466         C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
1467     ASSERT_DEATH(
1468         updateCGAndAnalysisManagerForFunctionPass(CG, C, FN, AM, UR, FAM),
1469         "Any new calls should be modeled as");
1470   }));
1471
1472   ModulePassManager MPM;
1473   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1474   MPM.run(*M, MAM);
1475 }
1476
1477 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses4) {
1478   CGSCCPassManager CGPM;
1479   CGPM.addPass(LambdaSCCPassNoPreserve(
1480       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1481           CGSCCUpdateResult &UR) {
1482         if (C.getName() != "(f)")
1483           return;
1484
1485         auto &FAM =
1486             AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1487         Function *FnF = M->getFunction("f");
1488         Function *FnewF = Function::Create(FnF->getFunctionType(),
1489                                            FnF->getLinkage(), "newF", *M);
1490         BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
1491         ReturnInst::Create(FnewF->getContext(), BB);
1492
1493         // And insert a call to `newF`
1494         Instruction *IP = &FnF->getEntryBlock().front();
1495         (void)CallInst::Create(FnewF, {}, "", IP);
1496
1497         // Use the CallGraphUpdater to update the call graph for the new
1498         // function.
1499         CallGraphUpdater CGU;
1500         CGU.initialize(CG, C, AM, UR);
1501         CGU.registerOutlinedFunction(*FnF, *FnewF);
1502
1503         auto &FN = *llvm::find_if(
1504             C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
1505
1506         ASSERT_NO_FATAL_FAILURE(
1507             updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR, FAM));
1508       }));
1509
1510   ModulePassManager MPM;
1511   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1512   MPM.run(*M, MAM);
1513 }
1514
1515 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses5) {
1516   CGSCCPassManager CGPM;
1517   CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
1518                                            CGSCCAnalysisManager &AM,
1519                                            LazyCallGraph &CG,
1520                                            CGSCCUpdateResult &UR) {
1521     if (C.getName() != "(f)")
1522       return;
1523
1524     auto &FAM =
1525         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1526     Function *FnF = M->getFunction("f");
1527     Function *FnewF =
1528         Function::Create(FnF->getFunctionType(), FnF->getLinkage(), "newF", *M);
1529     BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
1530     ReturnInst::Create(FnewF->getContext(), BB);
1531
1532     // Use the CallGraphUpdater to update the call graph for the new
1533     // function.
1534     CallGraphUpdater CGU;
1535     CGU.initialize(CG, C, AM, UR);
1536
1537     // And insert a call to `newF`
1538     Instruction *IP = &FnF->getEntryBlock().front();
1539     (void)CallInst::Create(FnewF, {}, "", IP);
1540
1541     auto &FN = *llvm::find_if(
1542         C, [](LazyCallGraph::Node &N) { return N.getName() == "f"; });
1543
1544     ASSERT_DEATH(updateCGAndAnalysisManagerForCGSCCPass(CG, C, FN, AM, UR, FAM),
1545                  "should already have an associated node");
1546   }));
1547
1548   ModulePassManager MPM;
1549   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1550   MPM.run(*M, MAM);
1551 }
1552
1553 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses6) {
1554   CGSCCPassManager CGPM;
1555   CGPM.addPass(LambdaSCCPassNoPreserve(
1556       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1557           CGSCCUpdateResult &UR) {
1558         if (C.getName() != "(h3, h1, h2)")
1559           return;
1560
1561         Function *FnX = M->getFunction("x");
1562         Function *FnH1 = M->getFunction("h1");
1563         Function *FnH2 = M->getFunction("h2");
1564         Function *FnH3 = M->getFunction("h3");
1565         ASSERT_NE(FnX, nullptr);
1566         ASSERT_NE(FnH1, nullptr);
1567         ASSERT_NE(FnH2, nullptr);
1568         ASSERT_NE(FnH3, nullptr);
1569
1570         // And insert a call to `h1`, `h2`, and `h3`.
1571         Instruction *IP = &FnH2->getEntryBlock().front();
1572         (void)CallInst::Create(FnH1, {}, "", IP);
1573         (void)CallInst::Create(FnH2, {}, "", IP);
1574         (void)CallInst::Create(FnH3, {}, "", IP);
1575
1576         // Use the CallGraphUpdater to update the call graph for the new
1577         // function.
1578         CallGraphUpdater CGU;
1579         CGU.initialize(CG, C, AM, UR);
1580         ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnH2));
1581       }));
1582
1583   ModulePassManager MPM;
1584   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1585   MPM.run(*M, MAM);
1586 }
1587
1588 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses7) {
1589   CGSCCPassManager CGPM;
1590   CGPM.addPass(LambdaSCCPassNoPreserve(
1591       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1592           CGSCCUpdateResult &UR) {
1593         if (C.getName() != "(f)")
1594           return;
1595
1596         Function *FnF = M->getFunction("f");
1597         Function *FnH2 = M->getFunction("h2");
1598         ASSERT_NE(FnF, nullptr);
1599         ASSERT_NE(FnH2, nullptr);
1600
1601         // And insert a call to `h2`
1602         Instruction *IP = &FnF->getEntryBlock().front();
1603         (void)CallInst::Create(FnH2, {}, "", IP);
1604
1605         // Use the CallGraphUpdater to update the call graph for the new
1606         // function.
1607         CallGraphUpdater CGU;
1608         CGU.initialize(CG, C, AM, UR);
1609         ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnF));
1610       }));
1611
1612   ModulePassManager MPM;
1613   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1614   MPM.run(*M, MAM);
1615 }
1616
1617 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses8) {
1618   CGSCCPassManager CGPM;
1619   CGPM.addPass(LambdaSCCPassNoPreserve(
1620       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1621           CGSCCUpdateResult &UR) {
1622         if (C.getName() != "(f)")
1623           return;
1624
1625         Function *FnF = M->getFunction("f");
1626         Function *FnewF = Function::Create(FnF->getFunctionType(),
1627                                            FnF->getLinkage(), "newF", *M);
1628         BasicBlock *BB = BasicBlock::Create(FnewF->getContext(), "", FnewF);
1629         auto *RI = ReturnInst::Create(FnewF->getContext(), BB);
1630         while (FnF->getEntryBlock().size() > 1)
1631           FnF->getEntryBlock().front().moveBefore(RI);
1632         ASSERT_NE(FnF, nullptr);
1633
1634         // Create an unsused constant that is referencing the old (=replaced)
1635         // function.
1636         ConstantExpr::getBitCast(FnF, Type::getInt8PtrTy(FnF->getContext()));
1637
1638         // Use the CallGraphUpdater to update the call graph.
1639         CallGraphUpdater CGU;
1640         CGU.initialize(CG, C, AM, UR);
1641         ASSERT_NO_FATAL_FAILURE(CGU.replaceFunctionWith(*FnF, *FnewF));
1642         ASSERT_TRUE(FnF->isDeclaration());
1643         ASSERT_EQ(FnF->getNumUses(), 0U);
1644       }));
1645
1646   ModulePassManager MPM;
1647   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1648   MPM.run(*M, MAM);
1649 }
1650
1651 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses9) {
1652   CGSCCPassManager CGPM;
1653   CGPM.addPass(LambdaSCCPassNoPreserve(
1654       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1655           CGSCCUpdateResult &UR) {
1656         if (C.getName() != "(f)")
1657           return;
1658
1659         Function *FnF = M->getFunction("f");
1660
1661         // Use the CallGraphUpdater to update the call graph.
1662         {
1663           CallGraphUpdater CGU;
1664           CGU.initialize(CG, C, AM, UR);
1665           ASSERT_NO_FATAL_FAILURE(CGU.removeFunction(*FnF));
1666           ASSERT_EQ(M->getFunctionList().size(), 6U);
1667         }
1668         ASSERT_EQ(M->getFunctionList().size(), 5U);
1669       }));
1670
1671   ModulePassManager MPM;
1672   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1673   MPM.run(*M, MAM);
1674 }
1675
1676 TEST_F(CGSCCPassManagerTest, TestUpdateCGAndAnalysisManagerForPasses10) {
1677   CGSCCPassManager CGPM;
1678   CGPM.addPass(LambdaSCCPassNoPreserve(
1679       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1680           CGSCCUpdateResult &UR) {
1681         if (C.getName() != "(h3, h1, h2)")
1682           return;
1683
1684         Function *FnX = M->getFunction("x");
1685         Function *FnH1 = M->getFunction("h1");
1686         Function *FnH2 = M->getFunction("h2");
1687         Function *FnH3 = M->getFunction("h3");
1688         ASSERT_NE(FnX, nullptr);
1689         ASSERT_NE(FnH1, nullptr);
1690         ASSERT_NE(FnH2, nullptr);
1691         ASSERT_NE(FnH3, nullptr);
1692
1693         // And insert a call to `h1`, and `h3`.
1694         Instruction *IP = &FnH1->getEntryBlock().front();
1695         (void)CallInst::Create(FnH1, {}, "", IP);
1696         (void)CallInst::Create(FnH3, {}, "", IP);
1697
1698         // Remove the `h2` call.
1699         ASSERT_TRUE(isa<CallBase>(IP));
1700         ASSERT_EQ(cast<CallBase>(IP)->getCalledFunction(), FnH2);
1701         IP->eraseFromParent();
1702
1703         // Use the CallGraphUpdater to update the call graph.
1704         CallGraphUpdater CGU;
1705         CGU.initialize(CG, C, AM, UR);
1706         ASSERT_NO_FATAL_FAILURE(CGU.reanalyzeFunction(*FnH1));
1707         ASSERT_NO_FATAL_FAILURE(CGU.removeFunction(*FnH2));
1708       }));
1709
1710   ModulePassManager MPM;
1711   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1712   MPM.run(*M, MAM);
1713 }
1714
1715 // Returns a vector containing the SCC's nodes. Useful for not iterating over an
1716 // SCC while mutating it.
1717 static SmallVector<LazyCallGraph::Node *> SCCNodes(LazyCallGraph::SCC &C) {
1718   SmallVector<LazyCallGraph::Node *> Nodes;
1719   for (auto &N : C)
1720     Nodes.push_back(&N);
1721
1722   return Nodes;
1723 }
1724
1725 // Start with call recursive f, create f -> g and ref recursive f.
1726 TEST_F(CGSCCPassManagerTest, TestInsertionOfNewFunctions1) {
1727   std::unique_ptr<Module> M = parseIR("define void @f() {\n"
1728                                       "entry:\n"
1729                                       "  call void @f()\n"
1730                                       "  ret void\n"
1731                                       "}\n");
1732
1733   bool Ran = false;
1734
1735   CGSCCPassManager CGPM;
1736   CGPM.addPass(LambdaSCCPassNoPreserve(
1737       [&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &CG,
1738           CGSCCUpdateResult &UR) {
1739         if (Ran)
1740           return;
1741
1742         auto &FAM =
1743             AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1744
1745         for (LazyCallGraph::Node *N : SCCNodes(C)) {
1746           Function &F = N->getFunction();
1747           if (F.getName() != "f")
1748             continue;
1749
1750           // Create a new function 'g'.
1751           auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
1752                                      F.getAddressSpace(), "g", F.getParent());
1753           auto *GBB =
1754               BasicBlock::Create(F.getParent()->getContext(), "entry", G);
1755           (void)ReturnInst::Create(G->getContext(), GBB);
1756           // Instruct the LazyCallGraph to create a new node for 'g', as the
1757           // single node in a new SCC, into the call graph. As a result
1758           // the call graph is composed of a single RefSCC with two SCCs:
1759           // [(f), (g)].
1760
1761           // "Demote" the 'f -> f' call edge to a ref edge.
1762           // 1. Erase the call edge from 'f' to 'f'.
1763           F.getEntryBlock().front().eraseFromParent();
1764           // 2. Insert a ref edge from 'f' to 'f'.
1765           (void)CastInst::CreatePointerCast(
1766               &F, Type::getInt8PtrTy(F.getContext()), "f.ref",
1767               &F.getEntryBlock().front());
1768           // 3. Insert a ref edge from 'f' to 'g'.
1769           (void)CastInst::CreatePointerCast(
1770               G, Type::getInt8PtrTy(F.getContext()), "g.ref",
1771               &F.getEntryBlock().front());
1772
1773           CG.addSplitFunction(F, *G);
1774
1775           ASSERT_FALSE(verifyModule(*F.getParent(), &errs()));
1776
1777           ASSERT_NO_FATAL_FAILURE(
1778               updateCGAndAnalysisManagerForCGSCCPass(CG, C, *N, AM, UR, FAM))
1779               << "Updating the call graph with a demoted, self-referential "
1780                  "call edge 'f -> f', and a newly inserted ref edge 'f -> g', "
1781                  "caused a fatal failure";
1782
1783           Ran = true;
1784         }
1785       }));
1786
1787   ModulePassManager MPM;
1788   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1789   MPM.run(*M, MAM);
1790   ASSERT_TRUE(Ran);
1791 }
1792
1793 // Start with f, end with f -> g1, f -> g2, and f -ref-> (h1 <-ref-> h2).
1794 TEST_F(CGSCCPassManagerTest, TestInsertionOfNewFunctions2) {
1795   std::unique_ptr<Module> M = parseIR("define void @f() {\n"
1796                                       "entry:\n"
1797                                       "  ret void\n"
1798                                       "}\n");
1799
1800   bool Ran = false;
1801
1802   CGSCCPassManager CGPM;
1803   CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
1804                                            CGSCCAnalysisManager &AM,
1805                                            LazyCallGraph &CG,
1806                                            CGSCCUpdateResult &UR) {
1807     if (Ran)
1808       return;
1809
1810     auto &FAM =
1811         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1812
1813     for (LazyCallGraph::Node *N : SCCNodes(C)) {
1814       Function &F = N->getFunction();
1815       if (F.getName() != "f")
1816         continue;
1817
1818       // Create g1 and g2.
1819       auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
1820                                   F.getAddressSpace(), "g1", F.getParent());
1821       auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
1822                                   F.getAddressSpace(), "g2", F.getParent());
1823       BasicBlock *G1BB =
1824           BasicBlock::Create(F.getParent()->getContext(), "entry", G1);
1825       BasicBlock *G2BB =
1826           BasicBlock::Create(F.getParent()->getContext(), "entry", G2);
1827       (void)ReturnInst::Create(G1->getContext(), G1BB);
1828       (void)ReturnInst::Create(G2->getContext(), G2BB);
1829
1830       // Add 'f -> g1' call edge.
1831       (void)CallInst::Create(G1, {}, "", &F.getEntryBlock().front());
1832       // Add 'f -> g2' call edge.
1833       (void)CallInst::Create(G2, {}, "", &F.getEntryBlock().front());
1834
1835       CG.addSplitFunction(F, *G1);
1836       CG.addSplitFunction(F, *G2);
1837
1838       // Create mutually recursive functions (ref only) 'h1' and 'h2'.
1839       auto *H1 = Function::Create(F.getFunctionType(), F.getLinkage(),
1840                                   F.getAddressSpace(), "h1", F.getParent());
1841       auto *H2 = Function::Create(F.getFunctionType(), F.getLinkage(),
1842                                   F.getAddressSpace(), "h2", F.getParent());
1843       BasicBlock *H1BB =
1844           BasicBlock::Create(F.getParent()->getContext(), "entry", H1);
1845       BasicBlock *H2BB =
1846           BasicBlock::Create(F.getParent()->getContext(), "entry", H2);
1847       (void)CastInst::CreatePointerCast(H2, Type::getInt8PtrTy(F.getContext()),
1848                                         "h2.ref", H1BB);
1849       (void)ReturnInst::Create(H1->getContext(), H1BB);
1850       (void)CastInst::CreatePointerCast(H1, Type::getInt8PtrTy(F.getContext()),
1851                                         "h1.ref", H2BB);
1852       (void)ReturnInst::Create(H2->getContext(), H2BB);
1853
1854       // Add 'f -> h1' ref edge.
1855       (void)CastInst::CreatePointerCast(H1, Type::getInt8PtrTy(F.getContext()),
1856                                         "h1.ref", &F.getEntryBlock().front());
1857       // Add 'f -> h2' ref edge.
1858       (void)CastInst::CreatePointerCast(H2, Type::getInt8PtrTy(F.getContext()),
1859                                         "h2.ref", &F.getEntryBlock().front());
1860
1861       CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 2>({H1, H2}));
1862
1863       ASSERT_FALSE(verifyModule(*F.getParent(), &errs()));
1864
1865       ASSERT_NO_FATAL_FAILURE(
1866           updateCGAndAnalysisManagerForCGSCCPass(CG, C, *N, AM, UR, FAM))
1867           << "Updating the call graph with mutually recursive g1 <-> g2, h1 "
1868              "<-> h2 caused a fatal failure";
1869
1870       Ran = true;
1871     }
1872   }));
1873
1874   ModulePassManager MPM;
1875   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1876   MPM.run(*M, MAM);
1877   ASSERT_TRUE(Ran);
1878 }
1879
1880 TEST_F(CGSCCPassManagerTest, TestInsertionOfNewNonTrivialCallEdge) {
1881   std::unique_ptr<Module> M = parseIR("define void @f1() {\n"
1882                                       "entry:\n"
1883                                       "  %a = bitcast void ()* @f4 to i8*\n"
1884                                       "  %b = bitcast void ()* @f2 to i8*\n"
1885                                       "  ret void\n"
1886                                       "}\n"
1887                                       "define void @f2() {\n"
1888                                       "entry:\n"
1889                                       "  %a = bitcast void ()* @f1 to i8*\n"
1890                                       "  %b = bitcast void ()* @f3 to i8*\n"
1891                                       "  ret void\n"
1892                                       "}\n"
1893                                       "define void @f3() {\n"
1894                                       "entry:\n"
1895                                       "  %a = bitcast void ()* @f2 to i8*\n"
1896                                       "  %b = bitcast void ()* @f4 to i8*\n"
1897                                       "  ret void\n"
1898                                       "}\n"
1899                                       "define void @f4() {\n"
1900                                       "entry:\n"
1901                                       "  %a = bitcast void ()* @f3 to i8*\n"
1902                                       "  %b = bitcast void ()* @f1 to i8*\n"
1903                                       "  ret void\n"
1904                                       "}\n");
1905
1906   bool Ran = false;
1907   CGSCCPassManager CGPM;
1908   CGPM.addPass(LambdaSCCPassNoPreserve([&](LazyCallGraph::SCC &C,
1909                                            CGSCCAnalysisManager &AM,
1910                                            LazyCallGraph &CG,
1911                                            CGSCCUpdateResult &UR) {
1912     if (Ran)
1913       return;
1914
1915     auto &FAM =
1916         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
1917
1918     for (LazyCallGraph::Node *N : SCCNodes(C)) {
1919       Function &F = N->getFunction();
1920       if (F.getName() != "f1")
1921         continue;
1922
1923       Function *F3 = F.getParent()->getFunction("f3");
1924       ASSERT_TRUE(F3 != nullptr);
1925
1926       // Create call from f1 to f3.
1927       (void)CallInst::Create(F3, {}, "", F.getEntryBlock().getTerminator());
1928
1929       ASSERT_NO_FATAL_FAILURE(
1930           updateCGAndAnalysisManagerForCGSCCPass(CG, C, *N, AM, UR, FAM))
1931           << "Updating the call graph with mutually recursive g1 <-> g2, h1 "
1932              "<-> h2 caused a fatal failure";
1933
1934       Ran = true;
1935     }
1936   }));
1937
1938   ModulePassManager MPM;
1939   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1940   MPM.run(*M, MAM);
1941
1942   ASSERT_TRUE(Ran);
1943 }
1944
1945 TEST_F(CGSCCPassManagerTest, TestFunctionPassesAreQueriedForInvalidation) {
1946   std::unique_ptr<Module> M = parseIR("define void @f() { ret void }");
1947   CGSCCPassManager CGPM;
1948   bool SCCCalled = false;
1949   FunctionPassManager FPM;
1950   int ImmRuns = 0;
1951   FAM.registerPass([&] { return TestImmutableFunctionAnalysis(ImmRuns); });
1952   FPM.addPass(RequireAnalysisPass<TestImmutableFunctionAnalysis, Function>());
1953   CGPM.addPass(
1954       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1955                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
1956         SCCCalled = true;
1957         return PreservedAnalyses::none();
1958       }));
1959   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1960       RequireAnalysisPass<TestImmutableFunctionAnalysis, Function>()));
1961   ModulePassManager MPM;
1962
1963   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM)));
1964   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1965   MPM.run(*M, MAM);
1966   ASSERT_EQ(ImmRuns, 1);
1967   ASSERT_TRUE(SCCCalled);
1968 }
1969
1970 #endif
1971 } // namespace