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