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