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