unittests/Analysis/CGSCCPassManagerTest.cpp

   1 //===- CGSCCPassManagerTest.cpp -------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/CGSCCPassManager.h"
  11 #include "llvm/Analysis/LazyCallGraph.h"
  12 #include "llvm/Analysis/TargetLibraryInfo.h"
  13 #include "llvm/AsmParser/Parser.h"
  14 #include "llvm/IR/Function.h"
  15 #include "llvm/IR/InstIterator.h"
  16 #include "llvm/IR/LLVMContext.h"
  17 #include "llvm/IR/Module.h"
  18 #include "llvm/IR/PassManager.h"
  19 #include "llvm/Support/SourceMgr.h"
  20 #include "gtest/gtest.h"
  21
  22 using namespace llvm;
  23
  24 namespace {
  25
  26 class TestModuleAnalysis : public AnalysisInfoMixin<TestModuleAnalysis> {
  27 public:
  28   struct Result {
  29     Result(int Count) : FunctionCount(Count) {}
  30     int FunctionCount;
  31   };
  32
  33   TestModuleAnalysis(int &Runs) : Runs(Runs) {}
  34
  35   Result run(Module &M, ModuleAnalysisManager &AM) {
  36     ++Runs;
  37     return Result(M.size());
  38   }
  39
  40 private:
  41   friend AnalysisInfoMixin<TestModuleAnalysis>;
  42   static AnalysisKey Key;
  43
  44   int &Runs;
  45 };
  46
  47 AnalysisKey TestModuleAnalysis::Key;
  48
  49 class TestSCCAnalysis : public AnalysisInfoMixin<TestSCCAnalysis> {
  50 public:
  51   struct Result {
  52     Result(int Count) : FunctionCount(Count) {}
  53     int FunctionCount;
  54   };
  55
  56   TestSCCAnalysis(int &Runs) : Runs(Runs) {}
  57
  58   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &) {
  59     ++Runs;
  60     return Result(C.size());
  61   }
  62
  63 private:
  64   friend AnalysisInfoMixin<TestSCCAnalysis>;
  65   static AnalysisKey Key;
  66
  67   int &Runs;
  68 };
  69
  70 AnalysisKey TestSCCAnalysis::Key;
  71
  72 class TestFunctionAnalysis : public AnalysisInfoMixin<TestFunctionAnalysis> {
  73 public:
  74   struct Result {
  75     Result(int Count) : InstructionCount(Count) {}
  76     int InstructionCount;
  77   };
  78
  79   TestFunctionAnalysis(int &Runs) : Runs(Runs) {}
  80
  81   Result run(Function &F, FunctionAnalysisManager &AM) {
  82     ++Runs;
  83     int Count = 0;
  84     for (Instruction &I : instructions(F)) {
  85       (void)I;
  86       ++Count;
  87     }
  88     return Result(Count);
  89   }
  90
  91 private:
  92   friend AnalysisInfoMixin<TestFunctionAnalysis>;
  93   static AnalysisKey Key;
  94
  95   int &Runs;
  96 };
  97
  98 AnalysisKey TestFunctionAnalysis::Key;
  99
 100 class TestImmutableFunctionAnalysis
 101     : public AnalysisInfoMixin<TestImmutableFunctionAnalysis> {
 102 public:
 103   struct Result {
 104     bool invalidate(Function &, const PreservedAnalyses &,
 105                     FunctionAnalysisManager::Invalidator &) {
 106       return false;
 107     }
 108   };
 109
 110   TestImmutableFunctionAnalysis(int &Runs) : Runs(Runs) {}
 111
 112   Result run(Function &F, FunctionAnalysisManager &AM) {
 113     ++Runs;
 114     return Result();
 115   }
 116
 117 private:
 118   friend AnalysisInfoMixin<TestImmutableFunctionAnalysis>;
 119   static AnalysisKey Key;
 120
 121   int &Runs;
 122 };
 123
 124 AnalysisKey TestImmutableFunctionAnalysis::Key;
 125
 126 struct LambdaModulePass : public PassInfoMixin<LambdaModulePass> {
 127   template <typename T>
 128   LambdaModulePass(T &&Arg) : Func(std::forward<T>(Arg)) {}
 129
 130   PreservedAnalyses run(Module &F, ModuleAnalysisManager &AM) {
 131     return Func(F, AM);
 132   }
 133
 134   std::function<PreservedAnalyses(Module &, ModuleAnalysisManager &)> Func;
 135 };
 136
 137 struct LambdaSCCPass : public PassInfoMixin<LambdaSCCPass> {
 138   template <typename T> LambdaSCCPass(T &&Arg) : Func(std::forward<T>(Arg)) {}
 139
 140   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 141                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
 142     return Func(C, AM, CG, UR);
 143   }
 144
 145   std::function<PreservedAnalyses(LazyCallGraph::SCC &, CGSCCAnalysisManager &,
 146                                   LazyCallGraph &, CGSCCUpdateResult &)>
 147       Func;
 148 };
 149
 150 struct LambdaFunctionPass : public PassInfoMixin<LambdaFunctionPass> {
 151   template <typename T>
 152   LambdaFunctionPass(T &&Arg) : Func(std::forward<T>(Arg)) {}
 153
 154   PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM) {
 155     return Func(F, AM);
 156   }
 157
 158   std::function<PreservedAnalyses(Function &, FunctionAnalysisManager &)> Func;
 159 };
 160
 161 std::unique_ptr<Module> parseIR(const char *IR) {
 162   // We just use a static context here. This is never called from multiple
 163   // threads so it is harmless no matter how it is implemented. We just need
 164   // the context to outlive the module which it does.
 165   static LLVMContext C;
 166   SMDiagnostic Err;
 167   return parseAssemblyString(IR, Err, C);
 168 }
 169
 170 class CGSCCPassManagerTest : public ::testing::Test {
 171 protected:
 172   LLVMContext Context;
 173   FunctionAnalysisManager FAM;
 174   CGSCCAnalysisManager CGAM;
 175   ModuleAnalysisManager MAM;
 176
 177   std::unique_ptr<Module> M;
 178
 179 public:
 180   CGSCCPassManagerTest()
 181       : FAM(/*DebugLogging*/ true), CGAM(/*DebugLogging*/ true),
 182         MAM(/*DebugLogging*/ true),
 183         M(parseIR(
 184             // Define a module with the following call graph, where calls go
 185             // out the bottom of nodes and enter the top:
 186             //
 187             // f
 188             // |\   _
 189             // | \ / |
 190             // g  h1 |
 191             // |  |  |
 192             // |  h2 |
 193             // |  |  |
 194             // |  h3 |
 195             // | / \_/
 196             // |/
 197             // x
 198             //
 199             "define void @f() {\n"
 200             "entry:\n"
 201             "  call void @g()\n"
 202             "  call void @h1()\n"
 203             "  ret void\n"
 204             "}\n"
 205             "define void @g() {\n"
 206             "entry:\n"
 207             "  call void @g()\n"
 208             "  call void @x()\n"
 209             "  ret void\n"
 210             "}\n"
 211             "define void @h1() {\n"
 212             "entry:\n"
 213             "  call void @h2()\n"
 214             "  ret void\n"
 215             "}\n"
 216             "define void @h2() {\n"
 217             "entry:\n"
 218             "  call void @h3()\n"
 219             "  call void @x()\n"
 220             "  ret void\n"
 221             "}\n"
 222             "define void @h3() {\n"
 223             "entry:\n"
 224             "  call void @h1()\n"
 225             "  ret void\n"
 226             "}\n"
 227             "define void @x() {\n"
 228             "entry:\n"
 229             "  ret void\n"
 230             "}\n")) {
 231     MAM.registerPass([&] { return TargetLibraryAnalysis(); });
 232     MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
 233     MAM.registerPass([&] { return FunctionAnalysisManagerModuleProxy(FAM); });
 234
 235     // Register required pass instrumentation analysis.
 236     MAM.registerPass([&] { return PassInstrumentationAnalysis(); });
 237     CGAM.registerPass([&] { return PassInstrumentationAnalysis(); });
 238     FAM.registerPass([&] { return PassInstrumentationAnalysis(); });
 239
 240     // Cross-register proxies.
 241     MAM.registerPass([&] { return CGSCCAnalysisManagerModuleProxy(CGAM); });
 242     CGAM.registerPass([&] { return FunctionAnalysisManagerCGSCCProxy(); });
 243     CGAM.registerPass([&] { return ModuleAnalysisManagerCGSCCProxy(MAM); });
 244     FAM.registerPass([&] { return CGSCCAnalysisManagerFunctionProxy(CGAM); });
 245     FAM.registerPass([&] { return ModuleAnalysisManagerFunctionProxy(MAM); });
 246   }
 247 };
 248
 249 TEST_F(CGSCCPassManagerTest, Basic) {
 250   int FunctionAnalysisRuns = 0;
 251   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 252   int ImmutableFunctionAnalysisRuns = 0;
 253   FAM.registerPass([&] {
 254     return TestImmutableFunctionAnalysis(ImmutableFunctionAnalysisRuns);
 255   });
 256
 257   int SCCAnalysisRuns = 0;
 258   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 259
 260   int ModuleAnalysisRuns = 0;
 261   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
 262
 263   ModulePassManager MPM(/*DebugLogging*/ true);
 264   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
 265
 266   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 267   FunctionPassManager FPM1(/*DebugLogging*/ true);
 268   int FunctionPassRunCount1 = 0;
 269   FPM1.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
 270     ++FunctionPassRunCount1;
 271     return PreservedAnalyses::none();
 272   }));
 273   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 274
 275   int SCCPassRunCount1 = 0;
 276   int AnalyzedInstrCount1 = 0;
 277   int AnalyzedSCCFunctionCount1 = 0;
 278   int AnalyzedModuleFunctionCount1 = 0;
 279   CGPM1.addPass(
 280       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 281                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
 282         ++SCCPassRunCount1;
 283
 284         const ModuleAnalysisManager &MAM =
 285             AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager();
 286         FunctionAnalysisManager &FAM =
 287             AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
 288         if (TestModuleAnalysis::Result *TMA =
 289                 MAM.getCachedResult<TestModuleAnalysis>(
 290                     *C.begin()->getFunction().getParent()))
 291           AnalyzedModuleFunctionCount1 += TMA->FunctionCount;
 292
 293         TestSCCAnalysis::Result &AR = AM.getResult<TestSCCAnalysis>(C, CG);
 294         AnalyzedSCCFunctionCount1 += AR.FunctionCount;
 295         for (LazyCallGraph::Node &N : C) {
 296           TestFunctionAnalysis::Result &FAR =
 297               FAM.getResult<TestFunctionAnalysis>(N.getFunction());
 298           AnalyzedInstrCount1 += FAR.InstructionCount;
 299
 300           // Just ensure we get the immutable results.
 301           (void)FAM.getResult<TestImmutableFunctionAnalysis>(N.getFunction());
 302         }
 303
 304         return PreservedAnalyses::all();
 305       }));
 306
 307   FunctionPassManager FPM2(/*DebugLogging*/ true);
 308   int FunctionPassRunCount2 = 0;
 309   FPM2.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
 310     ++FunctionPassRunCount2;
 311     return PreservedAnalyses::none();
 312   }));
 313   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 314
 315   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 316
 317   FunctionPassManager FPM3(/*DebugLogging*/ true);
 318   int FunctionPassRunCount3 = 0;
 319   FPM3.addPass(LambdaFunctionPass([&](Function &, FunctionAnalysisManager &) {
 320     ++FunctionPassRunCount3;
 321     return PreservedAnalyses::none();
 322   }));
 323   MPM.addPass(createModuleToFunctionPassAdaptor(std::move(FPM3)));
 324
 325   MPM.run(*M, MAM);
 326
 327   EXPECT_EQ(4, SCCPassRunCount1);
 328   EXPECT_EQ(6, FunctionPassRunCount1);
 329   EXPECT_EQ(6, FunctionPassRunCount2);
 330   EXPECT_EQ(6, FunctionPassRunCount3);
 331
 332   EXPECT_EQ(1, ModuleAnalysisRuns);
 333   EXPECT_EQ(4, SCCAnalysisRuns);
 334   EXPECT_EQ(6, FunctionAnalysisRuns);
 335   EXPECT_EQ(6, ImmutableFunctionAnalysisRuns);
 336
 337   EXPECT_EQ(14, AnalyzedInstrCount1);
 338   EXPECT_EQ(6, AnalyzedSCCFunctionCount1);
 339   EXPECT_EQ(4 * 6, AnalyzedModuleFunctionCount1);
 340 }
 341
 342 // Test that an SCC pass which fails to preserve a module analysis does in fact
 343 // invalidate that module analysis.
 344 TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesModuleAnalysis) {
 345   int ModuleAnalysisRuns = 0;
 346   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
 347
 348   ModulePassManager MPM(/*DebugLogging*/ true);
 349   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
 350
 351   // The first CGSCC run we preserve everything and make sure that works and
 352   // the module analysis is available in the second CGSCC run from the one
 353   // required module pass above.
 354   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 355   int CountFoundModuleAnalysis1 = 0;
 356   CGPM1.addPass(
 357       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 358                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
 359         const auto &MAM =
 360             AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager();
 361         auto *TMA = MAM.getCachedResult<TestModuleAnalysis>(
 362             *C.begin()->getFunction().getParent());
 363
 364         if (TMA)
 365           ++CountFoundModuleAnalysis1;
 366
 367         return PreservedAnalyses::all();
 368       }));
 369   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 370
 371   // The second CGSCC run checks that the module analysis got preserved the
 372   // previous time and in one SCC fails to preserve it.
 373   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
 374   int CountFoundModuleAnalysis2 = 0;
 375   CGPM2.addPass(
 376       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 377                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
 378         const auto &MAM =
 379             AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager();
 380         auto *TMA = MAM.getCachedResult<TestModuleAnalysis>(
 381             *C.begin()->getFunction().getParent());
 382
 383         if (TMA)
 384           ++CountFoundModuleAnalysis2;
 385
 386         // Only fail to preserve analyses on one SCC and make sure that gets
 387         // propagated.
 388         return C.getName() == "(g)" ? PreservedAnalyses::none()
 389                                   : PreservedAnalyses::all();
 390       }));
 391   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 392
 393   // The third CGSCC run should fail to find a cached module analysis as it
 394   // should have been invalidated by the above CGSCC run.
 395   CGSCCPassManager CGPM3(/*DebugLogging*/ true);
 396   int CountFoundModuleAnalysis3 = 0;
 397   CGPM3.addPass(
 398       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 399                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
 400         const auto &MAM =
 401             AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager();
 402         auto *TMA = MAM.getCachedResult<TestModuleAnalysis>(
 403             *C.begin()->getFunction().getParent());
 404
 405         if (TMA)
 406           ++CountFoundModuleAnalysis3;
 407
 408         return PreservedAnalyses::none();
 409       }));
 410   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM3)));
 411
 412   MPM.run(*M, MAM);
 413
 414   EXPECT_EQ(1, ModuleAnalysisRuns);
 415   EXPECT_EQ(4, CountFoundModuleAnalysis1);
 416   EXPECT_EQ(4, CountFoundModuleAnalysis2);
 417   EXPECT_EQ(0, CountFoundModuleAnalysis3);
 418 }
 419
 420 // Similar to the above, but test that this works for function passes embedded
 421 // *within* a CGSCC layer.
 422 TEST_F(CGSCCPassManagerTest, TestFunctionPassInsideCGSCCInvalidatesModuleAnalysis) {
 423   int ModuleAnalysisRuns = 0;
 424   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
 425
 426   ModulePassManager MPM(/*DebugLogging*/ true);
 427   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
 428
 429   // The first run we preserve everything and make sure that works and the
 430   // module analysis is available in the second run from the one required
 431   // module pass above.
 432   FunctionPassManager FPM1(/*DebugLogging*/ true);
 433   // Start true and mark false if we ever failed to find a module analysis
 434   // because we expect this to succeed for each SCC.
 435   bool FoundModuleAnalysis1 = true;
 436   FPM1.addPass(
 437       LambdaFunctionPass([&](Function &F, FunctionAnalysisManager &AM) {
 438         const auto &MAM =
 439             AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
 440         auto *TMA = MAM.getCachedResult<TestModuleAnalysis>(*F.getParent());
 441
 442         if (!TMA)
 443           FoundModuleAnalysis1 = false;
 444
 445         return PreservedAnalyses::all();
 446       }));
 447   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 448   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 449   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 450
 451   // The second run checks that the module analysis got preserved the previous
 452   // time and in one function fails to preserve it.
 453   FunctionPassManager FPM2(/*DebugLogging*/ true);
 454   // Again, start true and mark false if we ever failed to find a module analysis
 455   // because we expect this to succeed for each SCC.
 456   bool FoundModuleAnalysis2 = true;
 457   FPM2.addPass(
 458       LambdaFunctionPass([&](Function &F, FunctionAnalysisManager &AM) {
 459         const auto &MAM =
 460             AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
 461         auto *TMA = MAM.getCachedResult<TestModuleAnalysis>(*F.getParent());
 462
 463         if (!TMA)
 464           FoundModuleAnalysis2 = false;
 465
 466         // Only fail to preserve analyses on one SCC and make sure that gets
 467         // propagated.
 468         return F.getName() == "h2" ? PreservedAnalyses::none()
 469                                    : PreservedAnalyses::all();
 470       }));
 471   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
 472   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 473   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 474
 475   // The third run should fail to find a cached module analysis as it should
 476   // have been invalidated by the above run.
 477   FunctionPassManager FPM3(/*DebugLogging*/ true);
 478   // Start false and mark true if we ever *succeeded* to find a module
 479   // analysis, as we expect this to fail for every function.
 480   bool FoundModuleAnalysis3 = false;
 481   FPM3.addPass(
 482       LambdaFunctionPass([&](Function &F, FunctionAnalysisManager &AM) {
 483         const auto &MAM =
 484             AM.getResult<ModuleAnalysisManagerFunctionProxy>(F).getManager();
 485         auto *TMA = MAM.getCachedResult<TestModuleAnalysis>(*F.getParent());
 486
 487         if (TMA)
 488           FoundModuleAnalysis3 = true;
 489
 490         return PreservedAnalyses::none();
 491       }));
 492   CGSCCPassManager CGPM3(/*DebugLogging*/ true);
 493   CGPM3.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM3)));
 494   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM3)));
 495
 496   MPM.run(*M, MAM);
 497
 498   EXPECT_EQ(1, ModuleAnalysisRuns);
 499   EXPECT_TRUE(FoundModuleAnalysis1);
 500   EXPECT_TRUE(FoundModuleAnalysis2);
 501   EXPECT_FALSE(FoundModuleAnalysis3);
 502 }
 503
 504 // Test that a Module pass which fails to preserve an SCC analysis in fact
 505 // invalidates that analysis.
 506 TEST_F(CGSCCPassManagerTest, TestModulePassInvalidatesSCCAnalysis) {
 507   int SCCAnalysisRuns = 0;
 508   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 509
 510   ModulePassManager MPM(/*DebugLogging*/ true);
 511
 512   // First force the analysis to be run.
 513   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 514   CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 515                                     CGSCCAnalysisManager, LazyCallGraph &,
 516                                     CGSCCUpdateResult &>());
 517   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 518
 519   // Now run a module pass that preserves the LazyCallGraph and the proxy but
 520   // not the SCC analysis.
 521   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 522     PreservedAnalyses PA;
 523     PA.preserve<LazyCallGraphAnalysis>();
 524     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 525     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 526     return PA;
 527   }));
 528
 529   // And now a second CGSCC run which requires the SCC analysis again. This
 530   // will trigger re-running it.
 531   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
 532   CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 533                                     CGSCCAnalysisManager, LazyCallGraph &,
 534                                     CGSCCUpdateResult &>());
 535   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 536
 537   MPM.run(*M, MAM);
 538   // Two runs and four SCCs.
 539   EXPECT_EQ(2 * 4, SCCAnalysisRuns);
 540 }
 541
 542 // Check that marking the SCC analysis preserved is sufficient to avoid
 543 // invaliadtion. This should only run the analysis once for each SCC.
 544 TEST_F(CGSCCPassManagerTest, TestModulePassCanPreserveSCCAnalysis) {
 545   int SCCAnalysisRuns = 0;
 546   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 547
 548   ModulePassManager MPM(/*DebugLogging*/ true);
 549
 550   // First force the analysis to be run.
 551   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 552   CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 553                                     CGSCCAnalysisManager, LazyCallGraph &,
 554                                     CGSCCUpdateResult &>());
 555   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 556
 557   // Now run a module pass that preserves each of the necessary components
 558   // (but not everything).
 559   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 560     PreservedAnalyses PA;
 561     PA.preserve<LazyCallGraphAnalysis>();
 562     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 563     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 564     PA.preserve<TestSCCAnalysis>();
 565     return PA;
 566   }));
 567
 568   // And now a second CGSCC run which requires the SCC analysis again but find
 569   // it in the cache.
 570   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
 571   CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 572                                     CGSCCAnalysisManager, LazyCallGraph &,
 573                                     CGSCCUpdateResult &>());
 574   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 575
 576   MPM.run(*M, MAM);
 577   // Four SCCs
 578   EXPECT_EQ(4, SCCAnalysisRuns);
 579 }
 580
 581 // Check that even when the analysis is preserved, if the SCC information isn't
 582 // we still nuke things because the SCC keys could change.
 583 TEST_F(CGSCCPassManagerTest, TestModulePassInvalidatesSCCAnalysisOnCGChange) {
 584   int SCCAnalysisRuns = 0;
 585   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
 586
 587   ModulePassManager MPM(/*DebugLogging*/ true);
 588
 589   // First force the analysis to be run.
 590   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 591   CGPM1.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 592                                     CGSCCAnalysisManager, LazyCallGraph &,
 593                                     CGSCCUpdateResult &>());
 594   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 595
 596   // Now run a module pass that preserves the analysis but not the call
 597   // graph or proxy.
 598   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 599     PreservedAnalyses PA;
 600     PA.preserve<TestSCCAnalysis>();
 601     return PA;
 602   }));
 603
 604   // And now a second CGSCC run which requires the SCC analysis again.
 605   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
 606   CGPM2.addPass(RequireAnalysisPass<TestSCCAnalysis, LazyCallGraph::SCC,
 607                                     CGSCCAnalysisManager, LazyCallGraph &,
 608                                     CGSCCUpdateResult &>());
 609   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 610
 611   MPM.run(*M, MAM);
 612   // Two runs and four SCCs.
 613   EXPECT_EQ(2 * 4, SCCAnalysisRuns);
 614 }
 615
 616 // Test that an SCC pass which fails to preserve a Function analysis in fact
 617 // invalidates that analysis.
 618 TEST_F(CGSCCPassManagerTest, TestSCCPassInvalidatesFunctionAnalysis) {
 619   int FunctionAnalysisRuns = 0;
 620   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 621
 622   // Create a very simple module with a single function and SCC to make testing
 623   // these issues much easier.
 624   std::unique_ptr<Module> M = parseIR("declare void @g()\n"
 625                                       "declare void @h()\n"
 626                                       "define void @f() {\n"
 627                                       "entry:\n"
 628                                       "  call void @g()\n"
 629                                       "  call void @h()\n"
 630                                       "  ret void\n"
 631                                       "}\n");
 632
 633   CGSCCPassManager CGPM(/*DebugLogging*/ true);
 634
 635   // First force the analysis to be run.
 636   FunctionPassManager FPM1(/*DebugLogging*/ true);
 637   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 638   CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 639
 640   // Now run a module pass that preserves the LazyCallGraph and proxy but not
 641   // the SCC analysis.
 642   CGPM.addPass(LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &,
 643                                  LazyCallGraph &, CGSCCUpdateResult &) {
 644     PreservedAnalyses PA;
 645     PA.preserve<LazyCallGraphAnalysis>();
 646     return PA;
 647   }));
 648
 649   // And now a second CGSCC run which requires the SCC analysis again. This
 650   // will trigger re-running it.
 651   FunctionPassManager FPM2(/*DebugLogging*/ true);
 652   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 653   CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 654
 655   ModulePassManager MPM(/*DebugLogging*/ true);
 656   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
 657   MPM.run(*M, MAM);
 658   EXPECT_EQ(2, FunctionAnalysisRuns);
 659 }
 660
 661 // Check that marking the SCC analysis preserved is sufficient. This should
 662 // only run the analysis once the SCC.
 663 TEST_F(CGSCCPassManagerTest, TestSCCPassCanPreserveFunctionAnalysis) {
 664   int FunctionAnalysisRuns = 0;
 665   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 666
 667   // Create a very simple module with a single function and SCC to make testing
 668   // these issues much easier.
 669   std::unique_ptr<Module> M = parseIR("declare void @g()\n"
 670                                       "declare void @h()\n"
 671                                       "define void @f() {\n"
 672                                       "entry:\n"
 673                                       "  call void @g()\n"
 674                                       "  call void @h()\n"
 675                                       "  ret void\n"
 676                                       "}\n");
 677
 678   CGSCCPassManager CGPM(/*DebugLogging*/ true);
 679
 680   // First force the analysis to be run.
 681   FunctionPassManager FPM1(/*DebugLogging*/ true);
 682   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 683   CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 684
 685   // Now run a module pass that preserves each of the necessary components
 686   // (but
 687   // not everything).
 688   CGPM.addPass(LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &,
 689                                  LazyCallGraph &, CGSCCUpdateResult &) {
 690     PreservedAnalyses PA;
 691     PA.preserve<LazyCallGraphAnalysis>();
 692     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 693     PA.preserve<TestFunctionAnalysis>();
 694     return PA;
 695   }));
 696
 697   // And now a second CGSCC run which requires the SCC analysis again but find
 698   // it in the cache.
 699   FunctionPassManager FPM2(/*DebugLogging*/ true);
 700   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 701   CGPM.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 702
 703   ModulePassManager MPM(/*DebugLogging*/ true);
 704   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
 705   MPM.run(*M, MAM);
 706   EXPECT_EQ(1, FunctionAnalysisRuns);
 707 }
 708
 709 // Note that there is no test for invalidating the call graph or other
 710 // structure with an SCC pass because there is no mechanism to do that from
 711 // withinsuch a pass. Instead, such a pass has to directly update the call
 712 // graph structure.
 713
 714 // Test that a madule pass invalidates function analyses when the CGSCC proxies
 715 // and pass manager.
 716 TEST_F(CGSCCPassManagerTest,
 717        TestModulePassInvalidatesFunctionAnalysisNestedInCGSCC) {
 718   MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
 719
 720   int FunctionAnalysisRuns = 0;
 721   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 722
 723   ModulePassManager MPM(/*DebugLogging*/ true);
 724
 725   // First force the analysis to be run.
 726   FunctionPassManager FPM1(/*DebugLogging*/ true);
 727   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 728   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 729   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 730   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 731
 732   // Now run a module pass that preserves the LazyCallGraph and proxies but not
 733   // the Function analysis.
 734   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 735     PreservedAnalyses PA;
 736     PA.preserve<LazyCallGraphAnalysis>();
 737     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 738     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 739     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 740     return PA;
 741   }));
 742
 743   // And now a second CGSCC run which requires the SCC analysis again. This
 744   // will trigger re-running it.
 745   FunctionPassManager FPM2(/*DebugLogging*/ true);
 746   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 747   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
 748   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 749   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 750
 751   MPM.run(*M, MAM);
 752   // Two runs and 6 functions.
 753   EXPECT_EQ(2 * 6, FunctionAnalysisRuns);
 754 }
 755
 756 // Check that by marking the function pass and proxies as preserved, this
 757 // propagates all the way through.
 758 TEST_F(CGSCCPassManagerTest,
 759        TestModulePassCanPreserveFunctionAnalysisNestedInCGSCC) {
 760   MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
 761
 762   int FunctionAnalysisRuns = 0;
 763   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 764
 765   ModulePassManager MPM(/*DebugLogging*/ true);
 766
 767   // First force the analysis to be run.
 768   FunctionPassManager FPM1(/*DebugLogging*/ true);
 769   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 770   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 771   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 772   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 773
 774   // Now run a module pass that preserves the LazyCallGraph, the proxy, and
 775   // the Function analysis.
 776   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 777     PreservedAnalyses PA;
 778     PA.preserve<LazyCallGraphAnalysis>();
 779     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 780     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 781     PA.preserve<FunctionAnalysisManagerModuleProxy>();
 782     PA.preserve<TestFunctionAnalysis>();
 783     return PA;
 784   }));
 785
 786   // And now a second CGSCC run which requires the SCC analysis again. This
 787   // will trigger re-running it.
 788   FunctionPassManager FPM2(/*DebugLogging*/ true);
 789   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 790   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
 791   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 792   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 793
 794   MPM.run(*M, MAM);
 795   // One run and 6 functions.
 796   EXPECT_EQ(6, FunctionAnalysisRuns);
 797 }
 798
 799 // Check that if the lazy call graph itself isn't preserved we still manage to
 800 // invalidate everything.
 801 TEST_F(CGSCCPassManagerTest,
 802        TestModulePassInvalidatesFunctionAnalysisNestedInCGSCCOnCGChange) {
 803   MAM.registerPass([&] { return LazyCallGraphAnalysis(); });
 804
 805   int FunctionAnalysisRuns = 0;
 806   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
 807
 808   ModulePassManager MPM(/*DebugLogging*/ true);
 809
 810   // First force the analysis to be run.
 811   FunctionPassManager FPM1(/*DebugLogging*/ true);
 812   FPM1.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 813   CGSCCPassManager CGPM1(/*DebugLogging*/ true);
 814   CGPM1.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM1)));
 815   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM1)));
 816
 817   // Now run a module pass that preserves the LazyCallGraph but not the
 818   // Function analysis.
 819   MPM.addPass(LambdaModulePass([&](Module &M, ModuleAnalysisManager &) {
 820     PreservedAnalyses PA;
 821     return PA;
 822   }));
 823
 824   // And now a second CGSCC run which requires the SCC analysis again. This
 825   // will trigger re-running it.
 826   FunctionPassManager FPM2(/*DebugLogging*/ true);
 827   FPM2.addPass(RequireAnalysisPass<TestFunctionAnalysis, Function>());
 828   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
 829   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(std::move(FPM2)));
 830   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
 831
 832   MPM.run(*M, MAM);
 833   // Two runs and 6 functions.
 834   EXPECT_EQ(2 * 6, FunctionAnalysisRuns);
 835 }
 836
 837 /// A test CGSCC-level analysis pass which caches in its result another
 838 /// analysis pass and uses it to serve queries. This requires the result to
 839 /// invalidate itself when its dependency is invalidated.
 840 ///
 841 /// FIXME: Currently this doesn't also depend on a function analysis, and if it
 842 /// did we would fail to invalidate it correctly.
 843 struct TestIndirectSCCAnalysis
 844     : public AnalysisInfoMixin<TestIndirectSCCAnalysis> {
 845   struct Result {
 846     Result(TestSCCAnalysis::Result &SCCDep, TestModuleAnalysis::Result &MDep)
 847         : SCCDep(SCCDep), MDep(MDep) {}
 848     TestSCCAnalysis::Result &SCCDep;
 849     TestModuleAnalysis::Result &MDep;
 850
 851     bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
 852                     CGSCCAnalysisManager::Invalidator &Inv) {
 853       auto PAC = PA.getChecker<TestIndirectSCCAnalysis>();
 854       return !(PAC.preserved() ||
 855                PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) ||
 856              Inv.invalidate<TestSCCAnalysis>(C, PA);
 857     }
 858   };
 859
 860   TestIndirectSCCAnalysis(int &Runs) : Runs(Runs) {}
 861
 862   /// Run the analysis pass over the function and return a result.
 863   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 864              LazyCallGraph &CG) {
 865     ++Runs;
 866     auto &SCCDep = AM.getResult<TestSCCAnalysis>(C, CG);
 867
 868     auto &ModuleProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
 869     const ModuleAnalysisManager &MAM = ModuleProxy.getManager();
 870     // For the test, we insist that the module analysis starts off in the
 871     // cache.
 872     auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(
 873         *C.begin()->getFunction().getParent());
 874     // Register the dependency as module analysis dependencies have to be
 875     // pre-registered on the proxy.
 876     ModuleProxy.registerOuterAnalysisInvalidation<TestModuleAnalysis,
 877                                                   TestIndirectSCCAnalysis>();
 878
 879     return Result(SCCDep, MDep);
 880   }
 881
 882 private:
 883   friend AnalysisInfoMixin<TestIndirectSCCAnalysis>;
 884   static AnalysisKey Key;
 885
 886   int &Runs;
 887 };
 888
 889 AnalysisKey TestIndirectSCCAnalysis::Key;
 890
 891 /// A test analysis pass which caches in its result the result from the above
 892 /// indirect analysis pass.
 893 ///
 894 /// This allows us to ensure that whenever an analysis pass is invalidated due
 895 /// to dependencies (especially dependencies across IR units that trigger
 896 /// asynchronous invalidation) we correctly detect that this may in turn cause
 897 /// other analysis to be invalidated.
 898 struct TestDoublyIndirectSCCAnalysis
 899     : public AnalysisInfoMixin<TestDoublyIndirectSCCAnalysis> {
 900   struct Result {
 901     Result(TestIndirectSCCAnalysis::Result &IDep) : IDep(IDep) {}
 902     TestIndirectSCCAnalysis::Result &IDep;
 903
 904     bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
 905                     CGSCCAnalysisManager::Invalidator &Inv) {
 906       auto PAC = PA.getChecker<TestDoublyIndirectSCCAnalysis>();
 907       return !(PAC.preserved() ||
 908                PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) ||
 909              Inv.invalidate<TestIndirectSCCAnalysis>(C, PA);
 910     }
 911   };
 912
 913   TestDoublyIndirectSCCAnalysis(int &Runs) : Runs(Runs) {}
 914
 915   /// Run the analysis pass over the function and return a result.
 916   Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
 917              LazyCallGraph &CG) {
 918     ++Runs;
 919     auto &IDep = AM.getResult<TestIndirectSCCAnalysis>(C, CG);
 920     return Result(IDep);
 921   }
 922
 923 private:
 924   friend AnalysisInfoMixin<TestDoublyIndirectSCCAnalysis>;
 925   static AnalysisKey Key;
 926
 927   int &Runs;
 928 };
 929
 930 AnalysisKey TestDoublyIndirectSCCAnalysis::Key;
 931
 932 /// A test analysis pass which caches results from three different IR unit
 933 /// layers and requires intermediate layers to correctly propagate the entire
 934 /// distance.
 935 struct TestIndirectFunctionAnalysis
 936     : public AnalysisInfoMixin<TestIndirectFunctionAnalysis> {
 937   struct Result {
 938     Result(TestFunctionAnalysis::Result &FDep, TestModuleAnalysis::Result &MDep,
 939            TestSCCAnalysis::Result &SCCDep)
 940         : FDep(FDep), MDep(MDep), SCCDep(SCCDep) {}
 941     TestFunctionAnalysis::Result &FDep;
 942     TestModuleAnalysis::Result &MDep;
 943     TestSCCAnalysis::Result &SCCDep;
 944
 945     bool invalidate(Function &F, const PreservedAnalyses &PA,
 946                     FunctionAnalysisManager::Invalidator &Inv) {
 947       auto PAC = PA.getChecker<TestIndirectFunctionAnalysis>();
 948       return !(PAC.preserved() ||
 949                PAC.preservedSet<AllAnalysesOn<Function>>()) ||
 950              Inv.invalidate<TestFunctionAnalysis>(F, PA);
 951     }
 952   };
 953
 954   TestIndirectFunctionAnalysis(int &Runs) : Runs(Runs) {}
 955
 956   /// Run the analysis pass over the function and return a result.
 957   Result run(Function &F, FunctionAnalysisManager &AM) {
 958     ++Runs;
 959     auto &FDep = AM.getResult<TestFunctionAnalysis>(F);
 960
 961     auto &ModuleProxy = AM.getResult<ModuleAnalysisManagerFunctionProxy>(F);
 962     const ModuleAnalysisManager &MAM = ModuleProxy.getManager();
 963     // For the test, we insist that the module analysis starts off in the
 964     // cache.
 965     auto &MDep = *MAM.getCachedResult<TestModuleAnalysis>(*F.getParent());
 966     // Register the dependency as module analysis dependencies have to be
 967     // pre-registered on the proxy.
 968     ModuleProxy.registerOuterAnalysisInvalidation<
 969         TestModuleAnalysis, TestIndirectFunctionAnalysis>();
 970
 971     // For thet test we assume this is run inside a CGSCC pass manager.
 972     const LazyCallGraph &CG =
 973         *MAM.getCachedResult<LazyCallGraphAnalysis>(*F.getParent());
 974     auto &CGSCCProxy = AM.getResult<CGSCCAnalysisManagerFunctionProxy>(F);
 975     const CGSCCAnalysisManager &CGAM = CGSCCProxy.getManager();
 976     // For the test, we insist that the CGSCC analysis starts off in the cache.
 977     auto &SCCDep =
 978         *CGAM.getCachedResult<TestSCCAnalysis>(*CG.lookupSCC(*CG.lookup(F)));
 979     // Register the dependency as CGSCC analysis dependencies have to be
 980     // pre-registered on the proxy.
 981     CGSCCProxy.registerOuterAnalysisInvalidation<
 982         TestSCCAnalysis, TestIndirectFunctionAnalysis>();
 983
 984     return Result(FDep, MDep, SCCDep);
 985   }
 986
 987 private:
 988   friend AnalysisInfoMixin<TestIndirectFunctionAnalysis>;
 989   static AnalysisKey Key;
 990
 991   int &Runs;
 992 };
 993
 994 AnalysisKey TestIndirectFunctionAnalysis::Key;
 995
 996 TEST_F(CGSCCPassManagerTest, TestIndirectAnalysisInvalidation) {
 997   int ModuleAnalysisRuns = 0;
 998   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
 999
1000   int SCCAnalysisRuns = 0, IndirectSCCAnalysisRuns = 0,
1001       DoublyIndirectSCCAnalysisRuns = 0;
1002   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
1003   CGAM.registerPass(
1004       [&] { return TestIndirectSCCAnalysis(IndirectSCCAnalysisRuns); });
1005   CGAM.registerPass([&] {
1006     return TestDoublyIndirectSCCAnalysis(DoublyIndirectSCCAnalysisRuns);
1007   });
1008
1009   int FunctionAnalysisRuns = 0, IndirectFunctionAnalysisRuns = 0;
1010   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
1011   FAM.registerPass([&] {
1012     return TestIndirectFunctionAnalysis(IndirectFunctionAnalysisRuns);
1013   });
1014
1015   ModulePassManager MPM(/*DebugLogging*/ true);
1016
1017   int FunctionCount = 0;
1018   CGSCCPassManager CGPM(/*DebugLogging*/ true);
1019   // First just use the analysis to get the function count and preserve
1020   // everything.
1021   CGPM.addPass(
1022       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1023                         LazyCallGraph &CG, CGSCCUpdateResult &) {
1024         auto &DoublyIndirectResult =
1025             AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1026         auto &IndirectResult = DoublyIndirectResult.IDep;
1027         FunctionCount += IndirectResult.SCCDep.FunctionCount;
1028         return PreservedAnalyses::all();
1029       }));
1030   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1031       RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
1032
1033   // Next, invalidate
1034   //   - both analyses for the (f) and (x) SCCs,
1035   //   - just the underlying (indirect) analysis for (g) SCC, and
1036   //   - just the direct analysis for (h1,h2,h3) SCC.
1037   CGPM.addPass(
1038       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1039                         LazyCallGraph &CG, CGSCCUpdateResult &) {
1040         auto &DoublyIndirectResult =
1041             AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1042         auto &IndirectResult = DoublyIndirectResult.IDep;
1043         FunctionCount += IndirectResult.SCCDep.FunctionCount;
1044         auto PA = PreservedAnalyses::none();
1045         PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1046         PA.preserveSet<AllAnalysesOn<Function>>();
1047         if (C.getName() == "(g)")
1048           PA.preserve<TestSCCAnalysis>();
1049         else if (C.getName() == "(h3, h1, h2)")
1050           PA.preserve<TestIndirectSCCAnalysis>();
1051         return PA;
1052       }));
1053   // Finally, use the analysis again on each SCC (and function), forcing
1054   // re-computation for all of them.
1055   CGPM.addPass(
1056       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1057                         LazyCallGraph &CG, CGSCCUpdateResult &) {
1058         auto &DoublyIndirectResult =
1059             AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1060         auto &IndirectResult = DoublyIndirectResult.IDep;
1061         FunctionCount += IndirectResult.SCCDep.FunctionCount;
1062         return PreservedAnalyses::all();
1063       }));
1064   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1065       RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
1066
1067   // Create a second CGSCC pass manager. This will cause the module-level
1068   // invalidation to occur, which will force yet another invalidation of the
1069   // indirect SCC-level analysis as the module analysis it depends on gets
1070   // invalidated.
1071   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
1072   CGPM2.addPass(
1073       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1074                         LazyCallGraph &CG, CGSCCUpdateResult &) {
1075         auto &DoublyIndirectResult =
1076             AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1077         auto &IndirectResult = DoublyIndirectResult.IDep;
1078         FunctionCount += IndirectResult.SCCDep.FunctionCount;
1079         return PreservedAnalyses::all();
1080       }));
1081   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(
1082       RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>()));
1083
1084   // Add a requires pass to populate the module analysis and then our CGSCC
1085   // pass pipeline.
1086   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1087   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1088   // Now require the module analysis again (it will have been invalidated once)
1089   // and then use it again from our second CGSCC pipeline..
1090   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1091   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
1092   MPM.run(*M, MAM);
1093
1094   // There are generally two possible runs for each of the four SCCs. But
1095   // for one SCC, we only invalidate the indirect analysis so the base one
1096   // only gets run seven times.
1097   EXPECT_EQ(7, SCCAnalysisRuns);
1098   // The module analysis pass should be run twice here.
1099   EXPECT_EQ(2, ModuleAnalysisRuns);
1100   // The indirect analysis is invalidated (either directly or indirectly) three
1101   // times for each of four SCCs.
1102   EXPECT_EQ(3 * 4, IndirectSCCAnalysisRuns);
1103   EXPECT_EQ(3 * 4, DoublyIndirectSCCAnalysisRuns);
1104
1105   // We run the indirect function analysis once per function the first time.
1106   // Then we re-run it for every SCC but "(g)". Then we re-run it for every
1107   // function again.
1108   EXPECT_EQ(6 + 5 + 6, IndirectFunctionAnalysisRuns);
1109
1110   // Four passes count each of six functions once (via SCCs).
1111   EXPECT_EQ(4 * 6, FunctionCount);
1112 }
1113
1114 TEST_F(CGSCCPassManagerTest, TestAnalysisInvalidationCGSCCUpdate) {
1115   int ModuleAnalysisRuns = 0;
1116   MAM.registerPass([&] { return TestModuleAnalysis(ModuleAnalysisRuns); });
1117
1118   int SCCAnalysisRuns = 0, IndirectSCCAnalysisRuns = 0,
1119       DoublyIndirectSCCAnalysisRuns = 0;
1120   CGAM.registerPass([&] { return TestSCCAnalysis(SCCAnalysisRuns); });
1121   CGAM.registerPass(
1122       [&] { return TestIndirectSCCAnalysis(IndirectSCCAnalysisRuns); });
1123   CGAM.registerPass([&] {
1124     return TestDoublyIndirectSCCAnalysis(DoublyIndirectSCCAnalysisRuns);
1125   });
1126
1127   int FunctionAnalysisRuns = 0, IndirectFunctionAnalysisRuns = 0;
1128   FAM.registerPass([&] { return TestFunctionAnalysis(FunctionAnalysisRuns); });
1129   FAM.registerPass([&] {
1130     return TestIndirectFunctionAnalysis(IndirectFunctionAnalysisRuns);
1131   });
1132
1133   ModulePassManager MPM(/*DebugLogging*/ true);
1134
1135   CGSCCPassManager CGPM(/*DebugLogging*/ true);
1136   // First just use the analysis to get the function count and preserve
1137   // everything.
1138   using RequireTestIndirectFunctionAnalysisPass =
1139       RequireAnalysisPass<TestIndirectFunctionAnalysis, Function>;
1140   using RequireTestDoublyIndirectSCCAnalysisPass =
1141       RequireAnalysisPass<TestDoublyIndirectSCCAnalysis, LazyCallGraph::SCC,
1142                           CGSCCAnalysisManager, LazyCallGraph &,
1143                           CGSCCUpdateResult &>;
1144   CGPM.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1145   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1146       RequireTestIndirectFunctionAnalysisPass()));
1147
1148   // Next, we inject an SCC pass that invalidates everything for the `(h3, h1,
1149   // h2)` SCC but also deletes the call edge from `h2` to `h3` and updates the
1150   // CG. This should successfully invalidate (and force to be re-run) all the
1151   // analyses for that SCC and for the functions.
1152   CGPM.addPass(
1153       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1154                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
1155         (void)AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1156         if (C.getName() != "(h3, h1, h2)")
1157           return PreservedAnalyses::all();
1158
1159         // Build the preserved set.
1160         auto PA = PreservedAnalyses::none();
1161         PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1162         PA.preserve<TestIndirectSCCAnalysis>();
1163         PA.preserve<TestDoublyIndirectSCCAnalysis>();
1164
1165         // Delete the call from `h2` to `h3`.
1166         auto &H2N = *llvm::find_if(
1167             C, [](LazyCallGraph::Node &N) { return N.getName() == "h2"; });
1168         auto &H2F = H2N.getFunction();
1169         auto &H3F = *cast<CallInst>(H2F.begin()->begin())->getCalledFunction();
1170         assert(H3F.getName() == "h3" && "Wrong called function!");
1171         H2F.begin()->begin()->eraseFromParent();
1172         // Insert a bitcast of `h3` so that we retain a ref edge to it.
1173         (void)CastInst::CreatePointerCast(&H3F,
1174                                           Type::getInt8PtrTy(H2F.getContext()),
1175                                           "dummy", &*H2F.begin()->begin());
1176
1177         // Now update the call graph.
1178         auto &NewC =
1179             updateCGAndAnalysisManagerForFunctionPass(CG, C, H2N, AM, UR);
1180         assert(&NewC != &C && "Should get a new SCC due to update!");
1181         (void)&NewC;
1182
1183         return PA;
1184       }));
1185   // Now use the analysis again on each SCC and function, forcing
1186   // re-computation for all of them.
1187   CGPM.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1188   CGPM.addPass(createCGSCCToFunctionPassAdaptor(
1189       RequireTestIndirectFunctionAnalysisPass()));
1190
1191   // Create another CGSCC pipeline that requires all the analyses again.
1192   CGSCCPassManager CGPM2(/*DebugLogging*/ true);
1193   CGPM2.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1194   CGPM2.addPass(createCGSCCToFunctionPassAdaptor(
1195       RequireTestIndirectFunctionAnalysisPass()));
1196
1197   // Next we inject an SCC pass that finds the `(h2)` SCC, adds a call to `h3`
1198   // back to `h2`, and then invalidates everything for what will then be the
1199   // `(h3, h1, h2)` SCC again.
1200   CGSCCPassManager CGPM3(/*DebugLogging*/ true);
1201   CGPM3.addPass(
1202       LambdaSCCPass([&](LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM,
1203                         LazyCallGraph &CG, CGSCCUpdateResult &UR) {
1204         (void)AM.getResult<TestDoublyIndirectSCCAnalysis>(C, CG);
1205         if (C.getName() != "(h2)")
1206           return PreservedAnalyses::all();
1207
1208         // Build the preserved set.
1209         auto PA = PreservedAnalyses::none();
1210         PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1211         PA.preserve<TestIndirectSCCAnalysis>();
1212         PA.preserve<TestDoublyIndirectSCCAnalysis>();
1213
1214         // Delete the bitcast of `h3` that we added earlier.
1215         auto &H2N = *C.begin();
1216         auto &H2F = H2N.getFunction();
1217         auto &H3F = *cast<Function>(cast<BitCastInst>(H2F.begin()->begin())->getOperand(0));
1218         assert(H3F.getName() == "h3" && "Wrong called function!");
1219         H2F.begin()->begin()->eraseFromParent();
1220         // And insert a call to `h3`.
1221         (void)CallInst::Create(&H3F, {}, "", &*H2F.begin()->begin());
1222
1223         // Now update the call graph.
1224         auto &NewC =
1225             updateCGAndAnalysisManagerForFunctionPass(CG, C, H2N, AM, UR);
1226         assert(&NewC != &C && "Should get a new SCC due to update!");
1227         (void)&NewC;
1228
1229         return PA;
1230       }));
1231   // Now use the analysis again on each SCC and function, forcing
1232   // re-computation for all of them.
1233   CGPM3.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1234   CGPM3.addPass(createCGSCCToFunctionPassAdaptor(
1235       RequireTestIndirectFunctionAnalysisPass()));
1236
1237   // Create a second CGSCC pass manager. This will cause the module-level
1238   // invalidation to occur, which will force yet another invalidation of the
1239   // indirect SCC-level analysis as the module analysis it depends on gets
1240   // invalidated.
1241   CGSCCPassManager CGPM4(/*DebugLogging*/ true);
1242   CGPM4.addPass(RequireTestDoublyIndirectSCCAnalysisPass());
1243   CGPM4.addPass(createCGSCCToFunctionPassAdaptor(
1244       RequireTestIndirectFunctionAnalysisPass()));
1245
1246   // Add a requires pass to populate the module analysis and then one of our
1247   // CGSCC pipelines. Repeat for all four CGSCC pipelines.
1248   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1249   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM)));
1250   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1251   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM2)));
1252   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1253   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM3)));
1254   MPM.addPass(RequireAnalysisPass<TestModuleAnalysis, Module>());
1255   MPM.addPass(createModuleToPostOrderCGSCCPassAdaptor(std::move(CGPM4)));
1256   MPM.run(*M, MAM);
1257
1258   // We run over four SCCs the first time. But then we split an SCC into three.
1259   // And then we merge those three back into one.
1260   EXPECT_EQ(4 + 3 + 1, SCCAnalysisRuns);
1261   // The module analysis pass should be run three times.
1262   EXPECT_EQ(3, ModuleAnalysisRuns);
1263   // We run over four SCCs the first time. Then over the two new ones. Then the
1264   // entire module is invalidated causing a full run over all seven. Then we
1265   // fold three SCCs back to one, and then run over the whole module again.
1266   EXPECT_EQ(4 + 2 + 7 + 1 + 4, IndirectSCCAnalysisRuns);
1267   EXPECT_EQ(4 + 2 + 7 + 1 + 4, DoublyIndirectSCCAnalysisRuns);
1268
1269   // First we run over all six functions. Then we re-run it over three when we
1270   // split their SCCs. Then we re-run over the whole module. Then we re-run
1271   // over three functions merged back into a single SCC, and then over the
1272   // whole module again.
1273   EXPECT_EQ(6 + 3 + 6 + 3 + 6, FunctionAnalysisRuns);
1274
1275   // Re run the function analysis over the entire module, and then re-run it
1276   // over the `(h3, h1, h2)` SCC due to invalidation. Then we re-run it over
1277   // the entire module, then the three functions merged back into a single SCC,
1278   // and then over the whole module.
1279   EXPECT_EQ(6 + 3 + 6 + 3 + 6, IndirectFunctionAnalysisRuns);
1280 }
1281 }