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