?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[clang][ExtractAPI] Refactor ExtractAPIVisitor to make it more extensible
[llvm-project.git] / llvm / unittests / Analysis / LazyCallGraphTest.cpp
blob7eb6932ffb1f1994f657041bd36f275bc30f8622
1 //===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//
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/LazyCallGraph.h"
10 #include "llvm/AsmParser/Parser.h"
11 #include "llvm/IR/Function.h"
12 #include "llvm/IR/Instructions.h"
13 #include "llvm/IR/LLVMContext.h"
14 #include "llvm/IR/Module.h"
15 #include "llvm/IR/Verifier.h"
16 #include "llvm/Support/ErrorHandling.h"
17 #include "llvm/Support/SourceMgr.h"
18 #include "llvm/TargetParser/Triple.h"
19 #include "gtest/gtest.h"
20 #include <memory>
21
22 using namespace llvm;
23
24 namespace {
25
26 std::unique_ptr<Module> parseAssembly(LLVMContext &Context,
27 const char *Assembly) {
28 SMDiagnostic Error;
29 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
30
31 std::string ErrMsg;
32 raw_string_ostream OS(ErrMsg);
33 Error.print("", OS);
34
35 // A failure here means that the test itself is buggy.
36 if (!M)
37 report_fatal_error(OS.str().c_str());
38
39 return M;
40 }
41
42 /*
43 IR forming a call graph with a diamond of triangle-shaped SCCs:
44
45 d1
46 / \
47 d3--d2
48 / \
49 b1 c1
50 / \ / \
51 b3--b2 c3--c2
52 \ /
53 a1
54 / \
55 a3--a2
56
57 All call edges go up between SCCs, and clockwise around the SCC.
58 */
59 static const char DiamondOfTriangles[] =
60 "define void @a1() {\n"
61 "entry:\n"
62 " call void @a2()\n"
63 " call void @b2()\n"
64 " call void @c3()\n"
65 " ret void\n"
66 "}\n"
67 "define void @a2() {\n"
68 "entry:\n"
69 " call void @a3()\n"
70 " ret void\n"
71 "}\n"
72 "define void @a3() {\n"
73 "entry:\n"
74 " call void @a1()\n"
75 " ret void\n"
76 "}\n"
77 "define void @b1() {\n"
78 "entry:\n"
79 " call void @b2()\n"
80 " call void @d3()\n"
81 " ret void\n"
82 "}\n"
83 "define void @b2() {\n"
84 "entry:\n"
85 " call void @b3()\n"
86 " ret void\n"
87 "}\n"
88 "define void @b3() {\n"
89 "entry:\n"
90 " call void @b1()\n"
91 " ret void\n"
92 "}\n"
93 "define void @c1() {\n"
94 "entry:\n"
95 " call void @c2()\n"
96 " call void @d2()\n"
97 " ret void\n"
98 "}\n"
99 "define void @c2() {\n"
100 "entry:\n"
101 " call void @c3()\n"
102 " ret void\n"
103 "}\n"
104 "define void @c3() {\n"
105 "entry:\n"
106 " call void @c1()\n"
107 " ret void\n"
108 "}\n"
109 "define void @d1() {\n"
110 "entry:\n"
111 " call void @d2()\n"
112 " ret void\n"
113 "}\n"
114 "define void @d2() {\n"
115 "entry:\n"
116 " call void @d3()\n"
117 " ret void\n"
118 "}\n"
119 "define void @d3() {\n"
120 "entry:\n"
121 " call void @d1()\n"
122 " ret void\n"
123 "}\n";
124
125 /*
126 IR forming a reference graph with a diamond of triangle-shaped RefSCCs
127
128 d1
129 / \
130 d3--d2
131 / \
132 b1 c1
133 / \ / \
134 b3--b2 c3--c2
135 \ /
136 a1
137 / \
138 a3--a2
139
140 All call edges go up between RefSCCs, and clockwise around the RefSCC.
141 */
142 static const char DiamondOfTrianglesRefGraph[] =
143 "define void @a1() {\n"
144 "entry:\n"
145 " %a = alloca void ()*\n"
146 " store void ()* @a2, void ()** %a\n"
147 " store void ()* @b2, void ()** %a\n"
148 " store void ()* @c3, void ()** %a\n"
149 " ret void\n"
150 "}\n"
151 "define void @a2() {\n"
152 "entry:\n"
153 " %a = alloca void ()*\n"
154 " store void ()* @a3, void ()** %a\n"
155 " ret void\n"
156 "}\n"
157 "define void @a3() {\n"
158 "entry:\n"
159 " %a = alloca void ()*\n"
160 " store void ()* @a1, void ()** %a\n"
161 " ret void\n"
162 "}\n"
163 "define void @b1() {\n"
164 "entry:\n"
165 " %a = alloca void ()*\n"
166 " store void ()* @b2, void ()** %a\n"
167 " store void ()* @d3, void ()** %a\n"
168 " ret void\n"
169 "}\n"
170 "define void @b2() {\n"
171 "entry:\n"
172 " %a = alloca void ()*\n"
173 " store void ()* @b3, void ()** %a\n"
174 " ret void\n"
175 "}\n"
176 "define void @b3() {\n"
177 "entry:\n"
178 " %a = alloca void ()*\n"
179 " store void ()* @b1, void ()** %a\n"
180 " ret void\n"
181 "}\n"
182 "define void @c1() {\n"
183 "entry:\n"
184 " %a = alloca void ()*\n"
185 " store void ()* @c2, void ()** %a\n"
186 " store void ()* @d2, void ()** %a\n"
187 " ret void\n"
188 "}\n"
189 "define void @c2() {\n"
190 "entry:\n"
191 " %a = alloca void ()*\n"
192 " store void ()* @c3, void ()** %a\n"
193 " ret void\n"
194 "}\n"
195 "define void @c3() {\n"
196 "entry:\n"
197 " %a = alloca void ()*\n"
198 " store void ()* @c1, void ()** %a\n"
199 " ret void\n"
200 "}\n"
201 "define void @d1() {\n"
202 "entry:\n"
203 " %a = alloca void ()*\n"
204 " store void ()* @d2, void ()** %a\n"
205 " ret void\n"
206 "}\n"
207 "define void @d2() {\n"
208 "entry:\n"
209 " %a = alloca void ()*\n"
210 " store void ()* @d3, void ()** %a\n"
211 " ret void\n"
212 "}\n"
213 "define void @d3() {\n"
214 "entry:\n"
215 " %a = alloca void ()*\n"
216 " store void ()* @d1, void ()** %a\n"
217 " ret void\n"
218 "}\n";
219
220 static LazyCallGraph buildCG(Module &M) {
221 TargetLibraryInfoImpl TLII(Triple(M.getTargetTriple()));
222 TargetLibraryInfo TLI(TLII);
223 auto GetTLI = [&TLI](Function &F) -> TargetLibraryInfo & { return TLI; };
224
225 LazyCallGraph CG(M, GetTLI);
226 return CG;
227 }
228
229 TEST(LazyCallGraphTest, BasicGraphFormation) {
230 LLVMContext Context;
231 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
232 LazyCallGraph CG = buildCG(*M);
233
234 // The order of the entry nodes should be stable w.r.t. the source order of
235 // the IR, and everything in our module is an entry node, so just directly
236 // build variables for each node.
237 auto I = CG.begin();
238 LazyCallGraph::Node &A1 = (I++)->getNode();
239 EXPECT_EQ("a1", A1.getFunction().getName());
240 LazyCallGraph::Node &A2 = (I++)->getNode();
241 EXPECT_EQ("a2", A2.getFunction().getName());
242 LazyCallGraph::Node &A3 = (I++)->getNode();
243 EXPECT_EQ("a3", A3.getFunction().getName());
244 LazyCallGraph::Node &B1 = (I++)->getNode();
245 EXPECT_EQ("b1", B1.getFunction().getName());
246 LazyCallGraph::Node &B2 = (I++)->getNode();
247 EXPECT_EQ("b2", B2.getFunction().getName());
248 LazyCallGraph::Node &B3 = (I++)->getNode();
249 EXPECT_EQ("b3", B3.getFunction().getName());
250 LazyCallGraph::Node &C1 = (I++)->getNode();
251 EXPECT_EQ("c1", C1.getFunction().getName());
252 LazyCallGraph::Node &C2 = (I++)->getNode();
253 EXPECT_EQ("c2", C2.getFunction().getName());
254 LazyCallGraph::Node &C3 = (I++)->getNode();
255 EXPECT_EQ("c3", C3.getFunction().getName());
256 LazyCallGraph::Node &D1 = (I++)->getNode();
257 EXPECT_EQ("d1", D1.getFunction().getName());
258 LazyCallGraph::Node &D2 = (I++)->getNode();
259 EXPECT_EQ("d2", D2.getFunction().getName());
260 LazyCallGraph::Node &D3 = (I++)->getNode();
261 EXPECT_EQ("d3", D3.getFunction().getName());
262 EXPECT_EQ(CG.end(), I);
263
264 // Build vectors and sort them for the rest of the assertions to make them
265 // independent of order.
266 std::vector<std::string> Nodes;
267
268 for (LazyCallGraph::Edge &E : A1.populate())
269 Nodes.push_back(std::string(E.getFunction().getName()));
270 llvm::sort(Nodes);
271 EXPECT_EQ("a2", Nodes[0]);
272 EXPECT_EQ("b2", Nodes[1]);
273 EXPECT_EQ("c3", Nodes[2]);
274 Nodes.clear();
275
276 A2.populate();
277 EXPECT_EQ(A2->end(), std::next(A2->begin()));
278 EXPECT_EQ("a3", A2->begin()->getFunction().getName());
279 A3.populate();
280 EXPECT_EQ(A3->end(), std::next(A3->begin()));
281 EXPECT_EQ("a1", A3->begin()->getFunction().getName());
282
283 for (LazyCallGraph::Edge &E : B1.populate())
284 Nodes.push_back(std::string(E.getFunction().getName()));
285 llvm::sort(Nodes);
286 EXPECT_EQ("b2", Nodes[0]);
287 EXPECT_EQ("d3", Nodes[1]);
288 Nodes.clear();
289
290 B2.populate();
291 EXPECT_EQ(B2->end(), std::next(B2->begin()));
292 EXPECT_EQ("b3", B2->begin()->getFunction().getName());
293 B3.populate();
294 EXPECT_EQ(B3->end(), std::next(B3->begin()));
295 EXPECT_EQ("b1", B3->begin()->getFunction().getName());
296
297 for (LazyCallGraph::Edge &E : C1.populate())
298 Nodes.push_back(std::string(E.getFunction().getName()));
299 llvm::sort(Nodes);
300 EXPECT_EQ("c2", Nodes[0]);
301 EXPECT_EQ("d2", Nodes[1]);
302 Nodes.clear();
303
304 C2.populate();
305 EXPECT_EQ(C2->end(), std::next(C2->begin()));
306 EXPECT_EQ("c3", C2->begin()->getFunction().getName());
307 C3.populate();
308 EXPECT_EQ(C3->end(), std::next(C3->begin()));
309 EXPECT_EQ("c1", C3->begin()->getFunction().getName());
310
311 D1.populate();
312 EXPECT_EQ(D1->end(), std::next(D1->begin()));
313 EXPECT_EQ("d2", D1->begin()->getFunction().getName());
314 D2.populate();
315 EXPECT_EQ(D2->end(), std::next(D2->begin()));
316 EXPECT_EQ("d3", D2->begin()->getFunction().getName());
317 D3.populate();
318 EXPECT_EQ(D3->end(), std::next(D3->begin()));
319 EXPECT_EQ("d1", D3->begin()->getFunction().getName());
320
321 // Now lets look at the RefSCCs and SCCs.
322 CG.buildRefSCCs();
323 auto J = CG.postorder_ref_scc_begin();
324
325 LazyCallGraph::RefSCC &D = *J++;
326 ASSERT_EQ(1, D.size());
327 for (LazyCallGraph::Node &N : *D.begin())
328 Nodes.push_back(std::string(N.getFunction().getName()));
329 llvm::sort(Nodes);
330 EXPECT_EQ(3u, Nodes.size());
331 EXPECT_EQ("d1", Nodes[0]);
332 EXPECT_EQ("d2", Nodes[1]);
333 EXPECT_EQ("d3", Nodes[2]);
334 Nodes.clear();
335 EXPECT_FALSE(D.isParentOf(D));
336 EXPECT_FALSE(D.isChildOf(D));
337 EXPECT_FALSE(D.isAncestorOf(D));
338 EXPECT_FALSE(D.isDescendantOf(D));
339 EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin());
340
341 LazyCallGraph::RefSCC &B = *J++;
342 ASSERT_EQ(1, B.size());
343 for (LazyCallGraph::Node &N : *B.begin())
344 Nodes.push_back(std::string(N.getFunction().getName()));
345 llvm::sort(Nodes);
346 EXPECT_EQ(3u, Nodes.size());
347 EXPECT_EQ("b1", Nodes[0]);
348 EXPECT_EQ("b2", Nodes[1]);
349 EXPECT_EQ("b3", Nodes[2]);
350 Nodes.clear();
351 EXPECT_TRUE(B.isParentOf(D));
352 EXPECT_FALSE(B.isChildOf(D));
353 EXPECT_TRUE(B.isAncestorOf(D));
354 EXPECT_FALSE(B.isDescendantOf(D));
355 EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin()));
356
357 LazyCallGraph::RefSCC &C = *J++;
358 ASSERT_EQ(1, C.size());
359 for (LazyCallGraph::Node &N : *C.begin())
360 Nodes.push_back(std::string(N.getFunction().getName()));
361 llvm::sort(Nodes);
362 EXPECT_EQ(3u, Nodes.size());
363 EXPECT_EQ("c1", Nodes[0]);
364 EXPECT_EQ("c2", Nodes[1]);
365 EXPECT_EQ("c3", Nodes[2]);
366 Nodes.clear();
367 EXPECT_FALSE(B.isAncestorOf(C));
368 EXPECT_FALSE(C.isAncestorOf(B));
369 EXPECT_TRUE(C.isParentOf(D));
370 EXPECT_FALSE(C.isChildOf(D));
371 EXPECT_TRUE(C.isAncestorOf(D));
372 EXPECT_FALSE(C.isDescendantOf(D));
373 EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin(), 2));
374
375 LazyCallGraph::RefSCC &A = *J++;
376 ASSERT_EQ(1, A.size());
377 for (LazyCallGraph::Node &N : *A.begin())
378 Nodes.push_back(std::string(N.getFunction().getName()));
379 llvm::sort(Nodes);
380 EXPECT_EQ(3u, Nodes.size());
381 EXPECT_EQ("a1", Nodes[0]);
382 EXPECT_EQ("a2", Nodes[1]);
383 EXPECT_EQ("a3", Nodes[2]);
384 Nodes.clear();
385 EXPECT_TRUE(A.isParentOf(B));
386 EXPECT_TRUE(A.isParentOf(C));
387 EXPECT_FALSE(A.isParentOf(D));
388 EXPECT_TRUE(A.isAncestorOf(B));
389 EXPECT_TRUE(A.isAncestorOf(C));
390 EXPECT_TRUE(A.isAncestorOf(D));
391 EXPECT_EQ(&A, &*std::next(CG.postorder_ref_scc_begin(), 3));
392
393 EXPECT_EQ(CG.postorder_ref_scc_end(), J);
394 EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4));
395 }
396
397 static Function &lookupFunction(Module &M, StringRef Name) {
398 for (Function &F : M)
399 if (F.getName() == Name)
400 return F;
401 report_fatal_error("Couldn't find function!");
402 }
403
404 TEST(LazyCallGraphTest, BasicGraphMutation) {
405 LLVMContext Context;
406 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
407 "entry:\n"
408 " call void @b()\n"
409 " call void @c()\n"
410 " ret void\n"
411 "}\n"
412 "define void @b() {\n"
413 "entry:\n"
414 " ret void\n"
415 "}\n"
416 "define void @c() {\n"
417 "entry:\n"
418 " ret void\n"
419 "}\n");
420 LazyCallGraph CG = buildCG(*M);
421
422 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
423 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
424 A.populate();
425 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
426 B.populate();
427 EXPECT_EQ(0, std::distance(B->begin(), B->end()));
428
429 LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c"));
430 C.populate();
431 CG.insertEdge(B, C, LazyCallGraph::Edge::Call);
432 EXPECT_EQ(1, std::distance(B->begin(), B->end()));
433 EXPECT_EQ(0, std::distance(C->begin(), C->end()));
434
435 CG.insertEdge(C, B, LazyCallGraph::Edge::Call);
436 EXPECT_EQ(1, std::distance(C->begin(), C->end()));
437 EXPECT_EQ(&B, &C->begin()->getNode());
438
439 CG.insertEdge(C, C, LazyCallGraph::Edge::Call);
440 EXPECT_EQ(2, std::distance(C->begin(), C->end()));
441 EXPECT_EQ(&B, &C->begin()->getNode());
442 EXPECT_EQ(&C, &std::next(C->begin())->getNode());
443
444 CG.removeEdge(C, B);
445 EXPECT_EQ(1, std::distance(C->begin(), C->end()));
446 EXPECT_EQ(&C, &C->begin()->getNode());
447
448 CG.removeEdge(C, C);
449 EXPECT_EQ(0, std::distance(C->begin(), C->end()));
450
451 CG.removeEdge(B, C);
452 EXPECT_EQ(0, std::distance(B->begin(), B->end()));
453 }
454
455 TEST(LazyCallGraphTest, InnerSCCFormation) {
456 LLVMContext Context;
457 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
458 LazyCallGraph CG = buildCG(*M);
459
460 // Now mutate the graph to connect every node into a single RefSCC to ensure
461 // that our inner SCC formation handles the rest.
462 LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1"));
463 LazyCallGraph::Node &A1 = CG.get(lookupFunction(*M, "a1"));
464 A1.populate();
465 D1.populate();
466 CG.insertEdge(D1, A1, LazyCallGraph::Edge::Ref);
467
468 // Build vectors and sort them for the rest of the assertions to make them
469 // independent of order.
470 std::vector<std::string> Nodes;
471
472 // We should build a single RefSCC for the entire graph.
473 CG.buildRefSCCs();
474 auto I = CG.postorder_ref_scc_begin();
475 LazyCallGraph::RefSCC &RC = *I++;
476 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
477
478 // Now walk the four SCCs which should be in post-order.
479 auto J = RC.begin();
480 LazyCallGraph::SCC &D = *J++;
481 for (LazyCallGraph::Node &N : D)
482 Nodes.push_back(std::string(N.getFunction().getName()));
483 llvm::sort(Nodes);
484 EXPECT_EQ(3u, Nodes.size());
485 EXPECT_EQ("d1", Nodes[0]);
486 EXPECT_EQ("d2", Nodes[1]);
487 EXPECT_EQ("d3", Nodes[2]);
488 Nodes.clear();
489
490 LazyCallGraph::SCC &B = *J++;
491 for (LazyCallGraph::Node &N : B)
492 Nodes.push_back(std::string(N.getFunction().getName()));
493 llvm::sort(Nodes);
494 EXPECT_EQ(3u, Nodes.size());
495 EXPECT_EQ("b1", Nodes[0]);
496 EXPECT_EQ("b2", Nodes[1]);
497 EXPECT_EQ("b3", Nodes[2]);
498 Nodes.clear();
499
500 LazyCallGraph::SCC &C = *J++;
501 for (LazyCallGraph::Node &N : C)
502 Nodes.push_back(std::string(N.getFunction().getName()));
503 llvm::sort(Nodes);
504 EXPECT_EQ(3u, Nodes.size());
505 EXPECT_EQ("c1", Nodes[0]);
506 EXPECT_EQ("c2", Nodes[1]);
507 EXPECT_EQ("c3", Nodes[2]);
508 Nodes.clear();
509
510 LazyCallGraph::SCC &A = *J++;
511 for (LazyCallGraph::Node &N : A)
512 Nodes.push_back(std::string(N.getFunction().getName()));
513 llvm::sort(Nodes);
514 EXPECT_EQ(3u, Nodes.size());
515 EXPECT_EQ("a1", Nodes[0]);
516 EXPECT_EQ("a2", Nodes[1]);
517 EXPECT_EQ("a3", Nodes[2]);
518 Nodes.clear();
519
520 EXPECT_EQ(RC.end(), J);
521 }
522
523 TEST(LazyCallGraphTest, MultiArmSCC) {
524 LLVMContext Context;
525 // Two interlocking cycles. The really useful thing about this SCC is that it
526 // will require Tarjan's DFS to backtrack and finish processing all of the
527 // children of each node in the SCC. Since this involves call edges, both
528 // Tarjan implementations will have to successfully navigate the structure.
529 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f1() {\n"
530 "entry:\n"
531 " call void @f2()\n"
532 " call void @f4()\n"
533 " ret void\n"
534 "}\n"
535 "define void @f2() {\n"
536 "entry:\n"
537 " call void @f3()\n"
538 " ret void\n"
539 "}\n"
540 "define void @f3() {\n"
541 "entry:\n"
542 " call void @f1()\n"
543 " ret void\n"
544 "}\n"
545 "define void @f4() {\n"
546 "entry:\n"
547 " call void @f5()\n"
548 " ret void\n"
549 "}\n"
550 "define void @f5() {\n"
551 "entry:\n"
552 " call void @f1()\n"
553 " ret void\n"
554 "}\n");
555 LazyCallGraph CG = buildCG(*M);
556
557 // Force the graph to be fully expanded.
558 CG.buildRefSCCs();
559 auto I = CG.postorder_ref_scc_begin();
560 LazyCallGraph::RefSCC &RC = *I++;
561 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
562
563 LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1"));
564 LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2"));
565 LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3"));
566 LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4"));
567 LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4"));
568 EXPECT_EQ(&RC, CG.lookupRefSCC(N1));
569 EXPECT_EQ(&RC, CG.lookupRefSCC(N2));
570 EXPECT_EQ(&RC, CG.lookupRefSCC(N3));
571 EXPECT_EQ(&RC, CG.lookupRefSCC(N4));
572 EXPECT_EQ(&RC, CG.lookupRefSCC(N5));
573
574 ASSERT_EQ(1, RC.size());
575
576 LazyCallGraph::SCC &C = *RC.begin();
577 EXPECT_EQ(&C, CG.lookupSCC(N1));
578 EXPECT_EQ(&C, CG.lookupSCC(N2));
579 EXPECT_EQ(&C, CG.lookupSCC(N3));
580 EXPECT_EQ(&C, CG.lookupSCC(N4));
581 EXPECT_EQ(&C, CG.lookupSCC(N5));
582 }
583
584 TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
585 LLVMContext Context;
586 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
587 "entry:\n"
588 " call void @b()\n"
589 " call void @c()\n"
590 " ret void\n"
591 "}\n"
592 "define void @b() {\n"
593 "entry:\n"
594 " call void @d()\n"
595 " ret void\n"
596 "}\n"
597 "define void @c() {\n"
598 "entry:\n"
599 " call void @d()\n"
600 " ret void\n"
601 "}\n"
602 "define void @d() {\n"
603 "entry:\n"
604 " ret void\n"
605 "}\n");
606 LazyCallGraph CG = buildCG(*M);
607
608 // Force the graph to be fully expanded.
609 CG.buildRefSCCs();
610 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
611 dbgs() << "Formed RefSCC: " << RC << "\n";
612
613 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
614 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
615 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
616 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
617 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
618 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
619 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
620 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
621 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
622 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
623 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
624 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
625 EXPECT_TRUE(ARC.isParentOf(BRC));
626 EXPECT_TRUE(AC.isParentOf(BC));
627 EXPECT_TRUE(ARC.isParentOf(CRC));
628 EXPECT_TRUE(AC.isParentOf(CC));
629 EXPECT_FALSE(ARC.isParentOf(DRC));
630 EXPECT_FALSE(AC.isParentOf(DC));
631 EXPECT_TRUE(ARC.isAncestorOf(DRC));
632 EXPECT_TRUE(AC.isAncestorOf(DC));
633 EXPECT_FALSE(DRC.isChildOf(ARC));
634 EXPECT_FALSE(DC.isChildOf(AC));
635 EXPECT_TRUE(DRC.isDescendantOf(ARC));
636 EXPECT_TRUE(DC.isDescendantOf(AC));
637 EXPECT_TRUE(DRC.isChildOf(BRC));
638 EXPECT_TRUE(DC.isChildOf(BC));
639 EXPECT_TRUE(DRC.isChildOf(CRC));
640 EXPECT_TRUE(DC.isChildOf(CC));
641
642 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
643 ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call);
644 EXPECT_EQ(3, std::distance(A->begin(), A->end()));
645 const LazyCallGraph::Edge &NewE = (*A)[D];
646 EXPECT_TRUE(NewE);
647 EXPECT_TRUE(NewE.isCall());
648 EXPECT_EQ(&D, &NewE.getNode());
649
650 // Only the parent and child tests sholud have changed. The rest of the graph
651 // remains the same.
652 EXPECT_TRUE(ARC.isParentOf(DRC));
653 EXPECT_TRUE(AC.isParentOf(DC));
654 EXPECT_TRUE(ARC.isAncestorOf(DRC));
655 EXPECT_TRUE(AC.isAncestorOf(DC));
656 EXPECT_TRUE(DRC.isChildOf(ARC));
657 EXPECT_TRUE(DC.isChildOf(AC));
658 EXPECT_TRUE(DRC.isDescendantOf(ARC));
659 EXPECT_TRUE(DC.isDescendantOf(AC));
660 EXPECT_EQ(&AC, CG.lookupSCC(A));
661 EXPECT_EQ(&BC, CG.lookupSCC(B));
662 EXPECT_EQ(&CC, CG.lookupSCC(C));
663 EXPECT_EQ(&DC, CG.lookupSCC(D));
664 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
665 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
666 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
667 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
668
669 ARC.switchOutgoingEdgeToRef(A, D);
670 EXPECT_FALSE(NewE.isCall());
671
672 // Verify the reference graph remains the same but the SCC graph is updated.
673 EXPECT_TRUE(ARC.isParentOf(DRC));
674 EXPECT_FALSE(AC.isParentOf(DC));
675 EXPECT_TRUE(ARC.isAncestorOf(DRC));
676 EXPECT_TRUE(AC.isAncestorOf(DC));
677 EXPECT_TRUE(DRC.isChildOf(ARC));
678 EXPECT_FALSE(DC.isChildOf(AC));
679 EXPECT_TRUE(DRC.isDescendantOf(ARC));
680 EXPECT_TRUE(DC.isDescendantOf(AC));
681 EXPECT_EQ(&AC, CG.lookupSCC(A));
682 EXPECT_EQ(&BC, CG.lookupSCC(B));
683 EXPECT_EQ(&CC, CG.lookupSCC(C));
684 EXPECT_EQ(&DC, CG.lookupSCC(D));
685 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
686 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
687 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
688 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
689
690 ARC.switchOutgoingEdgeToCall(A, D);
691 EXPECT_TRUE(NewE.isCall());
692
693 // Verify the reference graph remains the same but the SCC graph is updated.
694 EXPECT_TRUE(ARC.isParentOf(DRC));
695 EXPECT_TRUE(AC.isParentOf(DC));
696 EXPECT_TRUE(ARC.isAncestorOf(DRC));
697 EXPECT_TRUE(AC.isAncestorOf(DC));
698 EXPECT_TRUE(DRC.isChildOf(ARC));
699 EXPECT_TRUE(DC.isChildOf(AC));
700 EXPECT_TRUE(DRC.isDescendantOf(ARC));
701 EXPECT_TRUE(DC.isDescendantOf(AC));
702 EXPECT_EQ(&AC, CG.lookupSCC(A));
703 EXPECT_EQ(&BC, CG.lookupSCC(B));
704 EXPECT_EQ(&CC, CG.lookupSCC(C));
705 EXPECT_EQ(&DC, CG.lookupSCC(D));
706 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
707 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
708 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
709 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
710
711 ARC.removeOutgoingEdge(A, D);
712 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
713
714 // Now the parent and child tests fail again but the rest remains the same.
715 EXPECT_FALSE(ARC.isParentOf(DRC));
716 EXPECT_FALSE(AC.isParentOf(DC));
717 EXPECT_TRUE(ARC.isAncestorOf(DRC));
718 EXPECT_TRUE(AC.isAncestorOf(DC));
719 EXPECT_FALSE(DRC.isChildOf(ARC));
720 EXPECT_FALSE(DC.isChildOf(AC));
721 EXPECT_TRUE(DRC.isDescendantOf(ARC));
722 EXPECT_TRUE(DC.isDescendantOf(AC));
723 EXPECT_EQ(&AC, CG.lookupSCC(A));
724 EXPECT_EQ(&BC, CG.lookupSCC(B));
725 EXPECT_EQ(&CC, CG.lookupSCC(C));
726 EXPECT_EQ(&DC, CG.lookupSCC(D));
727 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
728 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
729 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
730 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
731 }
732
733 TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
734 LLVMContext Context;
735 // We want to ensure we can add edges even across complex diamond graphs, so
736 // we use the diamond of triangles graph defined above. The ascii diagram is
737 // repeated here for easy reference.
738 //
739 // d1 |
740 // / \ |
741 // d3--d2 |
742 // / \ |
743 // b1 c1 |
744 // / \ / \ |
745 // b3--b2 c3--c2 |
746 // \ / |
747 // a1 |
748 // / \ |
749 // a3--a2 |
750 //
751 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
752 LazyCallGraph CG = buildCG(*M);
753
754 // Force the graph to be fully expanded.
755 CG.buildRefSCCs();
756 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
757 dbgs() << "Formed RefSCC: " << RC << "\n";
758
759 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
760 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
761 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
762 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
763 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
764 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
765 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
766 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
767 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
768 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
769 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
770 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
771 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
772 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
773 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
774 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
775 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
776 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
777 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
778 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
779 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
780 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
781 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
782 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
783 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
784
785 // Add an edge to make the graph:
786 //
787 // d1 |
788 // / \ |
789 // d3--d2---. |
790 // / \ | |
791 // b1 c1 | |
792 // / \ / \ / |
793 // b3--b2 c3--c2 |
794 // \ / |
795 // a1 |
796 // / \ |
797 // a3--a2 |
798 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
799 // Make sure we connected the nodes.
800 for (LazyCallGraph::Edge E : *D2) {
801 if (&E.getNode() == &D3)
802 continue;
803 EXPECT_EQ(&C2, &E.getNode());
804 }
805 // And marked the D ref-SCC as no longer valid.
806 EXPECT_EQ(1u, MergedRCs.size());
807 EXPECT_EQ(&DRC, MergedRCs[0]);
808
809 // Make sure we have the correct nodes in the SCC sets.
810 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
811 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
812 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
813 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
814 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
815 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
816 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
817 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
818 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
819 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
820 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
821 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
822
823 // And that ancestry tests have been updated.
824 EXPECT_TRUE(ARC.isParentOf(CRC));
825 EXPECT_TRUE(BRC.isParentOf(CRC));
826
827 // And verify the post-order walk reflects the updated structure.
828 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
829 ASSERT_NE(I, E);
830 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
831 ASSERT_NE(++I, E);
832 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
833 ASSERT_NE(++I, E);
834 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
835 EXPECT_EQ(++I, E);
836 }
837
838 TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) {
839 LLVMContext Context;
840 // Another variation of the above test but with all the edges switched to
841 // references rather than calls.
842 std::unique_ptr<Module> M =
843 parseAssembly(Context, DiamondOfTrianglesRefGraph);
844 LazyCallGraph CG = buildCG(*M);
845
846 // Force the graph to be fully expanded.
847 CG.buildRefSCCs();
848 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
849 dbgs() << "Formed RefSCC: " << RC << "\n";
850
851 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
852 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
853 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
854 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
855 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
856 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
857 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
858 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
859 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
860 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
861 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
862 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
863 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
864 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
865 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
866 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
867 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
868 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
869 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
870 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
871 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
872 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
873 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
874 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
875 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
876
877 // Add an edge to make the graph:
878 //
879 // d1 |
880 // / \ |
881 // d3--d2---. |
882 // / \ | |
883 // b1 c1 | |
884 // / \ / \ / |
885 // b3--b2 c3--c2 |
886 // \ / |
887 // a1 |
888 // / \ |
889 // a3--a2 |
890 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
891 // Make sure we connected the nodes.
892 for (LazyCallGraph::Edge E : *D2) {
893 if (&E.getNode() == &D3)
894 continue;
895 EXPECT_EQ(&C2, &E.getNode());
896 }
897 // And marked the D ref-SCC as no longer valid.
898 EXPECT_EQ(1u, MergedRCs.size());
899 EXPECT_EQ(&DRC, MergedRCs[0]);
900
901 // Make sure we have the correct nodes in the SCC sets.
902 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
903 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
904 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
905 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
906 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
907 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
908 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
909 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
910 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
911 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
912 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
913 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
914
915 // And that ancestry tests have been updated.
916 EXPECT_TRUE(ARC.isParentOf(CRC));
917 EXPECT_TRUE(BRC.isParentOf(CRC));
918
919 // And verify the post-order walk reflects the updated structure.
920 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
921 ASSERT_NE(I, E);
922 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
923 ASSERT_NE(++I, E);
924 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
925 ASSERT_NE(++I, E);
926 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
927 EXPECT_EQ(++I, E);
928 }
929
930 TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) {
931 LLVMContext Context;
932 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
933 "entry:\n"
934 " call void @b()\n"
935 " ret void\n"
936 "}\n"
937 "define void @b() {\n"
938 "entry:\n"
939 " call void @c()\n"
940 " ret void\n"
941 "}\n"
942 "define void @c() {\n"
943 "entry:\n"
944 " call void @d()\n"
945 " ret void\n"
946 "}\n"
947 "define void @d() {\n"
948 "entry:\n"
949 " ret void\n"
950 "}\n");
951 LazyCallGraph CG = buildCG(*M);
952
953 // Force the graph to be fully expanded.
954 CG.buildRefSCCs();
955 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
956 dbgs() << "Formed RefSCC: " << RC << "\n";
957
958 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
959 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
960 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
961 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
962 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
963 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
964 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
965 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
966 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
967 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
968 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
969 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
970
971 // Connect the top to the bottom forming a large RefSCC made up mostly of calls.
972 auto MergedRCs = ARC.insertIncomingRefEdge(D, A);
973 // Make sure we connected the nodes.
974 EXPECT_NE(D->begin(), D->end());
975 EXPECT_EQ(&A, &D->begin()->getNode());
976
977 // Check that we have the dead RCs, but ignore the order.
978 EXPECT_EQ(3u, MergedRCs.size());
979 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());
980 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());
981 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());
982
983 // Make sure the nodes point to the right place now.
984 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
985 EXPECT_EQ(&ARC, CG.lookupRefSCC(B));
986 EXPECT_EQ(&ARC, CG.lookupRefSCC(C));
987 EXPECT_EQ(&ARC, CG.lookupRefSCC(D));
988
989 // Check that the SCCs are in postorder.
990 EXPECT_EQ(4, ARC.size());
991 EXPECT_EQ(&DC, &ARC[0]);
992 EXPECT_EQ(&CC, &ARC[1]);
993 EXPECT_EQ(&BC, &ARC[2]);
994 EXPECT_EQ(&AC, &ARC[3]);
995
996 // And verify the post-order walk reflects the updated structure.
997 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
998 ASSERT_NE(I, E);
999 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1000 EXPECT_EQ(++I, E);
1001 }
1002
1003 TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
1004 LLVMContext Context;
1005 std::unique_ptr<Module> M =
1006 parseAssembly(Context, "define void @a() {\n"
1007 "entry:\n"
1008 " %p = alloca void ()*\n"
1009 " store void ()* @b, void ()** %p\n"
1010 " ret void\n"
1011 "}\n"
1012 "define void @b() {\n"
1013 "entry:\n"
1014 " %p = alloca void ()*\n"
1015 " store void ()* @c, void ()** %p\n"
1016 " ret void\n"
1017 "}\n"
1018 "define void @c() {\n"
1019 "entry:\n"
1020 " %p = alloca void ()*\n"
1021 " store void ()* @d, void ()** %p\n"
1022 " ret void\n"
1023 "}\n"
1024 "define void @d() {\n"
1025 "entry:\n"
1026 " ret void\n"
1027 "}\n");
1028 LazyCallGraph CG = buildCG(*M);
1029
1030 // Force the graph to be fully expanded.
1031 CG.buildRefSCCs();
1032 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
1033 dbgs() << "Formed RefSCC: " << RC << "\n";
1034
1035 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1036 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1037 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1038 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1039 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
1040 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
1041 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
1042 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
1043
1044 // Connect the top to the bottom forming a large RefSCC made up just of
1045 // references.
1046 auto MergedRCs = ARC.insertIncomingRefEdge(D, A);
1047 // Make sure we connected the nodes.
1048 EXPECT_NE(D->begin(), D->end());
1049 EXPECT_EQ(&A, &D->begin()->getNode());
1050
1051 // Check that we have the dead RCs, but ignore the order.
1052 EXPECT_EQ(3u, MergedRCs.size());
1053 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());
1054 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());
1055 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());
1056
1057 // Make sure the nodes point to the right place now.
1058 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
1059 EXPECT_EQ(&ARC, CG.lookupRefSCC(B));
1060 EXPECT_EQ(&ARC, CG.lookupRefSCC(C));
1061 EXPECT_EQ(&ARC, CG.lookupRefSCC(D));
1062
1063 // And verify the post-order walk reflects the updated structure.
1064 auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end();
1065 ASSERT_NE(I, End);
1066 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1067 EXPECT_EQ(++I, End);
1068 }
1069
1070 TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
1071 LLVMContext Context;
1072 // We want to ensure we can delete nodes from relatively complex graphs and
1073 // so use the diamond of triangles graph defined above.
1074 //
1075 // The ascii diagram is repeated here for easy reference.
1076 //
1077 // d1 |
1078 // / \ |
1079 // d3--d2 |
1080 // / \ |
1081 // b1 c1 |
1082 // / \ / \ |
1083 // b3--b2 c3--c2 |
1084 // \ / |
1085 // a1 |
1086 // / \ |
1087 // a3--a2 |
1088 //
1089 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
1090 LazyCallGraph CG = buildCG(*M);
1091
1092 // Force the graph to be fully expanded.
1093 CG.buildRefSCCs();
1094 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
1095 dbgs() << "Formed RefSCC: " << RC << "\n";
1096
1097 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
1098 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
1099 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
1100 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
1101 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
1102 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
1103 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
1104 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
1105 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
1106 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
1107 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
1108 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
1109 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
1110 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
1111 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
1112 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
1113 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
1114 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
1115 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
1116 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
1117 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
1118 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
1119 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
1120 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
1121 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
1122
1123 // Delete d2 from the graph, as if it had been inlined.
1124 //
1125 // d1 |
1126 // / / |
1127 // d3--. |
1128 // / \ |
1129 // b1 c1 |
1130 // / \ / \ |
1131 // b3--b2 c3--c2 |
1132 // \ / |
1133 // a1 |
1134 // / \ |
1135 // a3--a2 |
1136
1137 Function &D2F = D2.getFunction();
1138 CallInst *C1Call = nullptr, *D1Call = nullptr;
1139 for (User *U : D2F.users()) {
1140 CallInst *CI = dyn_cast<CallInst>(U);
1141 ASSERT_TRUE(CI) << "Expected a call: " << *U;
1142 if (CI->getParent()->getParent() == &C1.getFunction()) {
1143 ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;
1144 C1Call = CI;
1145 } else if (CI->getParent()->getParent() == &D1.getFunction()) {
1146 ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;
1147 D1Call = CI;
1148 } else {
1149 FAIL() << "Found an unexpected call instruction: " << *CI;
1150 }
1151 }
1152 ASSERT_NE(C1Call, nullptr);
1153 ASSERT_NE(D1Call, nullptr);
1154 ASSERT_EQ(&D2F, C1Call->getCalledFunction());
1155 ASSERT_EQ(&D2F, D1Call->getCalledFunction());
1156 C1Call->setCalledFunction(&D3.getFunction());
1157 D1Call->setCalledFunction(&D3.getFunction());
1158 ASSERT_EQ(0u, D2F.getNumUses());
1159
1160 // Insert new edges first.
1161 CRC.insertTrivialCallEdge(C1, D3);
1162 DRC.insertTrivialCallEdge(D1, D3);
1163
1164 // Then remove the old ones.
1165 LazyCallGraph::SCC &DC = *CG.lookupSCC(D2);
1166 auto NewCs = DRC.switchInternalEdgeToRef(D1, D2);
1167 EXPECT_EQ(&DC, CG.lookupSCC(D2));
1168 EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));
1169 LazyCallGraph::SCC &NewDC = *NewCs.begin();
1170 EXPECT_EQ(&NewDC, CG.lookupSCC(D1));
1171 EXPECT_EQ(&NewDC, CG.lookupSCC(D3));
1172 auto NewRCs = DRC.removeInternalRefEdge(D1, {&D2});
1173 ASSERT_EQ(2u, NewRCs.size());
1174 LazyCallGraph::RefSCC &NewDRC = *NewRCs[0];
1175 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
1176 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
1177 LazyCallGraph::RefSCC &D2RC = *NewRCs[1];
1178 EXPECT_EQ(&D2RC, CG.lookupRefSCC(D2));
1179 EXPECT_FALSE(NewDRC.isParentOf(D2RC));
1180 EXPECT_TRUE(CRC.isParentOf(D2RC));
1181 EXPECT_TRUE(CRC.isParentOf(NewDRC));
1182 EXPECT_TRUE(D2RC.isParentOf(NewDRC));
1183 CRC.removeOutgoingEdge(C1, D2);
1184 EXPECT_FALSE(CRC.isParentOf(D2RC));
1185 EXPECT_TRUE(CRC.isParentOf(NewDRC));
1186 EXPECT_TRUE(D2RC.isParentOf(NewDRC));
1187
1188 // Now that we've updated the call graph, D2 is dead, so remove it.
1189 CG.removeDeadFunction(D2F);
1190
1191 // Check that the graph still looks the same.
1192 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
1193 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
1194 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
1195 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
1196 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
1197 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
1198 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
1199 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
1200 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
1201 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
1202 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
1203 EXPECT_TRUE(CRC.isParentOf(NewDRC));
1204
1205 // Verify the post-order walk hasn't changed.
1206 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1207 ASSERT_NE(I, E);
1208 EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;
1209 ASSERT_NE(++I, E);
1210 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
1211 ASSERT_NE(++I, E);
1212 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
1213 ASSERT_NE(++I, E);
1214 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1215 EXPECT_EQ(++I, E);
1216 }
1217
1218 TEST(LazyCallGraphTest, InternalEdgeMutation) {
1219 LLVMContext Context;
1220 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
1221 "entry:\n"
1222 " call void @b()\n"
1223 " ret void\n"
1224 "}\n"
1225 "define void @b() {\n"
1226 "entry:\n"
1227 " call void @c()\n"
1228 " ret void\n"
1229 "}\n"
1230 "define void @c() {\n"
1231 "entry:\n"
1232 " call void @a()\n"
1233 " ret void\n"
1234 "}\n");
1235 LazyCallGraph CG = buildCG(*M);
1236
1237 // Force the graph to be fully expanded.
1238 CG.buildRefSCCs();
1239 auto I = CG.postorder_ref_scc_begin();
1240 LazyCallGraph::RefSCC &RC = *I++;
1241 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1242
1243 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1244 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1245 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1246 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1247 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1248 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1249 EXPECT_EQ(1, RC.size());
1250 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
1251 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
1252 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
1253
1254 // Insert an edge from 'a' to 'c'. Nothing changes about the graph.
1255 RC.insertInternalRefEdge(A, C);
1256 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
1257 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1258 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1259 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1260 EXPECT_EQ(1, RC.size());
1261 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
1262 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
1263 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
1264
1265 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the
1266 // call cycle and cause us to form more SCCs. The RefSCC will remain the same
1267 // though.
1268 auto NewCs = RC.switchInternalEdgeToRef(B, C);
1269 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1270 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1271 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1272 auto J = RC.begin();
1273 // The SCCs must be in *post-order* which means successors before
1274 // predecessors. At this point we have call edges from C to A and from A to
1275 // B. The only valid postorder is B, A, C.
1276 EXPECT_EQ(&*J++, CG.lookupSCC(B));
1277 EXPECT_EQ(&*J++, CG.lookupSCC(A));
1278 EXPECT_EQ(&*J++, CG.lookupSCC(C));
1279 EXPECT_EQ(RC.end(), J);
1280 // And the returned range must be the slice of this sequence containing new
1281 // SCCs.
1282 EXPECT_EQ(RC.begin(), NewCs.begin());
1283 EXPECT_EQ(std::prev(RC.end()), NewCs.end());
1284
1285 // Test turning the ref edge from A to C into a call edge. This will form an
1286 // SCC out of A and C. Since we previously had a call edge from C to A, the
1287 // C SCC should be preserved and have A merged into it while the A SCC should
1288 // be invalidated.
1289 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1290 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1291 EXPECT_TRUE(RC.switchInternalEdgeToCall(A, C, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1292 ASSERT_EQ(1u, MergedCs.size());
1293 EXPECT_EQ(&AC, MergedCs[0]);
1294 }));
1295 EXPECT_EQ(2, CC.size());
1296 EXPECT_EQ(&CC, CG.lookupSCC(A));
1297 EXPECT_EQ(&CC, CG.lookupSCC(C));
1298 J = RC.begin();
1299 EXPECT_EQ(&*J++, CG.lookupSCC(B));
1300 EXPECT_EQ(&*J++, CG.lookupSCC(C));
1301 EXPECT_EQ(RC.end(), J);
1302 }
1303
1304 TEST(LazyCallGraphTest, InternalEdgeRemoval) {
1305 LLVMContext Context;
1306 // A nice fully connected (including self-edges) RefSCC.
1307 std::unique_ptr<Module> M = parseAssembly(
1308 Context, "define void @a(i8** %ptr) {\n"
1309 "entry:\n"
1310 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1311 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1312 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1313 " ret void\n"
1314 "}\n"
1315 "define void @b(i8** %ptr) {\n"
1316 "entry:\n"
1317 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1318 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1319 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1320 " ret void\n"
1321 "}\n"
1322 "define void @c(i8** %ptr) {\n"
1323 "entry:\n"
1324 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1325 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1326 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1327 " ret void\n"
1328 "}\n");
1329 LazyCallGraph CG = buildCG(*M);
1330
1331 // Force the graph to be fully expanded.
1332 CG.buildRefSCCs();
1333 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1334 LazyCallGraph::RefSCC &RC = *I;
1335 EXPECT_EQ(E, std::next(I));
1336
1337 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1338 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1339 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1340 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1341 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1342 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1343
1344 // Remove the edge from b -> a, which should leave the 3 functions still in
1345 // a single connected component because of a -> b -> c -> a.
1346 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1347 RC.removeInternalRefEdge(B, {&A});
1348 EXPECT_EQ(0u, NewRCs.size());
1349 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1350 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1351 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1352 auto J = CG.postorder_ref_scc_begin();
1353 EXPECT_EQ(I, J);
1354 EXPECT_EQ(&RC, &*J);
1355 EXPECT_EQ(E, std::next(J));
1356
1357 // Increment I before we actually mutate the structure so that it remains
1358 // a valid iterator.
1359 ++I;
1360
1361 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC
1362 // and form a new RefSCC for 'b' and 'c'.
1363 NewRCs = RC.removeInternalRefEdge(C, {&A});
1364 ASSERT_EQ(2u, NewRCs.size());
1365 LazyCallGraph::RefSCC &BCRC = *NewRCs[0];
1366 LazyCallGraph::RefSCC &ARC = *NewRCs[1];
1367 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
1368 EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end()));
1369 EXPECT_EQ(&BCRC, CG.lookupRefSCC(B));
1370 EXPECT_EQ(&BCRC, CG.lookupRefSCC(C));
1371 J = CG.postorder_ref_scc_begin();
1372 EXPECT_NE(I, J);
1373 EXPECT_EQ(&BCRC, &*J);
1374 ++J;
1375 EXPECT_NE(I, J);
1376 EXPECT_EQ(&ARC, &*J);
1377 ++J;
1378 EXPECT_EQ(I, J);
1379 EXPECT_EQ(E, J);
1380 }
1381
1382 TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) {
1383 LLVMContext Context;
1384 // A nice fully connected (including self-edges) RefSCC.
1385 std::unique_ptr<Module> M = parseAssembly(
1386 Context, "define void @a(i8** %ptr) {\n"
1387 "entry:\n"
1388 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1389 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1390 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1391 " ret void\n"
1392 "}\n"
1393 "define void @b(i8** %ptr) {\n"
1394 "entry:\n"
1395 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1396 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1397 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1398 " ret void\n"
1399 "}\n"
1400 "define void @c(i8** %ptr) {\n"
1401 "entry:\n"
1402 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1403 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1404 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1405 " ret void\n"
1406 "}\n");
1407 LazyCallGraph CG = buildCG(*M);
1408
1409 // Force the graph to be fully expanded.
1410 CG.buildRefSCCs();
1411 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1412 LazyCallGraph::RefSCC &RC = *I;
1413 EXPECT_EQ(E, std::next(I));
1414
1415 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1416 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1417 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1418 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1419 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1420 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1421
1422 // Increment I before we actually mutate the structure so that it remains
1423 // a valid iterator.
1424 ++I;
1425
1426 // Remove the edges from b -> a and b -> c, leaving b in its own RefSCC.
1427 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1428 RC.removeInternalRefEdge(B, {&A, &C});
1429
1430 ASSERT_EQ(2u, NewRCs.size());
1431 LazyCallGraph::RefSCC &BRC = *NewRCs[0];
1432 LazyCallGraph::RefSCC &ACRC = *NewRCs[1];
1433 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
1434 EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end()));
1435 EXPECT_EQ(&ACRC, CG.lookupRefSCC(A));
1436 EXPECT_EQ(&ACRC, CG.lookupRefSCC(C));
1437 auto J = CG.postorder_ref_scc_begin();
1438 EXPECT_NE(I, J);
1439 EXPECT_EQ(&BRC, &*J);
1440 ++J;
1441 EXPECT_NE(I, J);
1442 EXPECT_EQ(&ACRC, &*J);
1443 ++J;
1444 EXPECT_EQ(I, J);
1445 EXPECT_EQ(E, J);
1446 }
1447
1448 TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) {
1449 LLVMContext Context;
1450 // A graph with a single cycle formed both from call and reference edges
1451 // which makes the reference edges trivial to delete. The graph looks like:
1452 //
1453 // Reference edges: a -> b -> c -> a
1454 // Call edges: a -> c -> b -> a
1455 std::unique_ptr<Module> M = parseAssembly(
1456 Context, "define void @a(i8** %ptr) {\n"
1457 "entry:\n"
1458 " call void @b(i8** %ptr)\n"
1459 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1460 " ret void\n"
1461 "}\n"
1462 "define void @b(i8** %ptr) {\n"
1463 "entry:\n"
1464 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1465 " call void @c(i8** %ptr)\n"
1466 " ret void\n"
1467 "}\n"
1468 "define void @c(i8** %ptr) {\n"
1469 "entry:\n"
1470 " call void @a(i8** %ptr)\n"
1471 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1472 " ret void\n"
1473 "}\n");
1474 LazyCallGraph CG = buildCG(*M);
1475
1476 // Force the graph to be fully expanded.
1477 CG.buildRefSCCs();
1478 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1479 LazyCallGraph::RefSCC &RC = *I;
1480 EXPECT_EQ(E, std::next(I));
1481
1482 LazyCallGraph::SCC &C = *RC.begin();
1483 EXPECT_EQ(RC.end(), std::next(RC.begin()));
1484
1485 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
1486 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
1487 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
1488 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1489 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1490 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1491 EXPECT_EQ(&C, CG.lookupSCC(AN));
1492 EXPECT_EQ(&C, CG.lookupSCC(BN));
1493 EXPECT_EQ(&C, CG.lookupSCC(CN));
1494
1495 // Remove the edge from a -> c which doesn't change anything.
1496 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1497 RC.removeInternalRefEdge(AN, {&CN});
1498 EXPECT_EQ(0u, NewRCs.size());
1499 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1500 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1501 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1502 EXPECT_EQ(&C, CG.lookupSCC(AN));
1503 EXPECT_EQ(&C, CG.lookupSCC(BN));
1504 EXPECT_EQ(&C, CG.lookupSCC(CN));
1505 auto J = CG.postorder_ref_scc_begin();
1506 EXPECT_EQ(I, J);
1507 EXPECT_EQ(&RC, &*J);
1508 EXPECT_EQ(E, std::next(J));
1509
1510 // Remove the edge from b -> a and c -> b; again this doesn't change
1511 // anything.
1512 NewRCs = RC.removeInternalRefEdge(BN, {&AN});
1513 NewRCs = RC.removeInternalRefEdge(CN, {&BN});
1514 EXPECT_EQ(0u, NewRCs.size());
1515 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1516 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1517 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1518 EXPECT_EQ(&C, CG.lookupSCC(AN));
1519 EXPECT_EQ(&C, CG.lookupSCC(BN));
1520 EXPECT_EQ(&C, CG.lookupSCC(CN));
1521 J = CG.postorder_ref_scc_begin();
1522 EXPECT_EQ(I, J);
1523 EXPECT_EQ(&RC, &*J);
1524 EXPECT_EQ(E, std::next(J));
1525 }
1526
1527 TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
1528 LLVMContext Context;
1529 // A nice fully connected (including self-edges) SCC (and RefSCC)
1530 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
1531 "entry:\n"
1532 " call void @a()\n"
1533 " call void @b()\n"
1534 " call void @c()\n"
1535 " ret void\n"
1536 "}\n"
1537 "define void @b() {\n"
1538 "entry:\n"
1539 " call void @a()\n"
1540 " call void @b()\n"
1541 " call void @c()\n"
1542 " ret void\n"
1543 "}\n"
1544 "define void @c() {\n"
1545 "entry:\n"
1546 " call void @a()\n"
1547 " call void @b()\n"
1548 " call void @c()\n"
1549 " ret void\n"
1550 "}\n");
1551 LazyCallGraph CG = buildCG(*M);
1552
1553 // Force the graph to be fully expanded.
1554 CG.buildRefSCCs();
1555 auto I = CG.postorder_ref_scc_begin();
1556 LazyCallGraph::RefSCC &RC = *I++;
1557 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1558
1559 EXPECT_EQ(1, RC.size());
1560 LazyCallGraph::SCC &AC = *RC.begin();
1561
1562 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
1563 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
1564 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
1565 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1566 EXPECT_EQ(&AC, CG.lookupSCC(BN));
1567 EXPECT_EQ(&AC, CG.lookupSCC(CN));
1568
1569 // Remove the call edge from b -> a to a ref edge, which should leave the
1570 // 3 functions still in a single connected component because of a -> b ->
1571 // c -> a.
1572 auto NewCs = RC.switchInternalEdgeToRef(BN, AN);
1573 EXPECT_EQ(NewCs.begin(), NewCs.end());
1574 EXPECT_EQ(1, RC.size());
1575 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1576 EXPECT_EQ(&AC, CG.lookupSCC(BN));
1577 EXPECT_EQ(&AC, CG.lookupSCC(CN));
1578
1579 // Remove the edge from c -> a, which should leave 'a' in the original SCC
1580 // and form a new SCC for 'b' and 'c'.
1581 NewCs = RC.switchInternalEdgeToRef(CN, AN);
1582 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
1583 EXPECT_EQ(2, RC.size());
1584 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1585 LazyCallGraph::SCC &BC = *CG.lookupSCC(BN);
1586 EXPECT_NE(&BC, &AC);
1587 EXPECT_EQ(&BC, CG.lookupSCC(CN));
1588 auto J = RC.find(AC);
1589 EXPECT_EQ(&AC, &*J);
1590 --J;
1591 EXPECT_EQ(&BC, &*J);
1592 EXPECT_EQ(RC.begin(), J);
1593 EXPECT_EQ(J, NewCs.begin());
1594
1595 // Remove the edge from c -> b, which should leave 'b' in the original SCC
1596 // and form a new SCC for 'c'. It shouldn't change 'a's SCC.
1597 NewCs = RC.switchInternalEdgeToRef(CN, BN);
1598 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
1599 EXPECT_EQ(3, RC.size());
1600 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1601 EXPECT_EQ(&BC, CG.lookupSCC(BN));
1602 LazyCallGraph::SCC &CC = *CG.lookupSCC(CN);
1603 EXPECT_NE(&CC, &AC);
1604 EXPECT_NE(&CC, &BC);
1605 J = RC.find(AC);
1606 EXPECT_EQ(&AC, &*J);
1607 --J;
1608 EXPECT_EQ(&BC, &*J);
1609 --J;
1610 EXPECT_EQ(&CC, &*J);
1611 EXPECT_EQ(RC.begin(), J);
1612 EXPECT_EQ(J, NewCs.begin());
1613 }
1614
1615 TEST(LazyCallGraphTest, InternalRefEdgeToCall) {
1616 LLVMContext Context;
1617 // Basic tests for making a ref edge a call. This hits the basics of the
1618 // process only.
1619 std::unique_ptr<Module> M =
1620 parseAssembly(Context, "define void @a() {\n"
1621 "entry:\n"
1622 " call void @b()\n"
1623 " call void @c()\n"
1624 " store void()* @d, void()** undef\n"
1625 " ret void\n"
1626 "}\n"
1627 "define void @b() {\n"
1628 "entry:\n"
1629 " store void()* @c, void()** undef\n"
1630 " call void @d()\n"
1631 " ret void\n"
1632 "}\n"
1633 "define void @c() {\n"
1634 "entry:\n"
1635 " store void()* @b, void()** undef\n"
1636 " call void @d()\n"
1637 " ret void\n"
1638 "}\n"
1639 "define void @d() {\n"
1640 "entry:\n"
1641 " store void()* @a, void()** undef\n"
1642 " ret void\n"
1643 "}\n");
1644 LazyCallGraph CG = buildCG(*M);
1645
1646 // Force the graph to be fully expanded.
1647 CG.buildRefSCCs();
1648 auto I = CG.postorder_ref_scc_begin();
1649 LazyCallGraph::RefSCC &RC = *I++;
1650 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1651
1652 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1653 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1654 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1655 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1656 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1657 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
1658 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1659 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1660
1661 // Check the initial post-order. Note that B and C could be flipped here (and
1662 // in our mutation) without changing the nature of this test.
1663 ASSERT_EQ(4, RC.size());
1664 EXPECT_EQ(&DC, &RC[0]);
1665 EXPECT_EQ(&BC, &RC[1]);
1666 EXPECT_EQ(&CC, &RC[2]);
1667 EXPECT_EQ(&AC, &RC[3]);
1668
1669 // Switch the ref edge from A -> D to a call edge. This should have no
1670 // effect as it is already in postorder and no new cycles are formed.
1671 EXPECT_FALSE(RC.switchInternalEdgeToCall(A, D));
1672 ASSERT_EQ(4, RC.size());
1673 EXPECT_EQ(&DC, &RC[0]);
1674 EXPECT_EQ(&BC, &RC[1]);
1675 EXPECT_EQ(&CC, &RC[2]);
1676 EXPECT_EQ(&AC, &RC[3]);
1677
1678 // Switch B -> C to a call edge. This doesn't form any new cycles but does
1679 // require reordering the SCCs.
1680 EXPECT_FALSE(RC.switchInternalEdgeToCall(B, C));
1681 ASSERT_EQ(4, RC.size());
1682 EXPECT_EQ(&DC, &RC[0]);
1683 EXPECT_EQ(&CC, &RC[1]);
1684 EXPECT_EQ(&BC, &RC[2]);
1685 EXPECT_EQ(&AC, &RC[3]);
1686
1687 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs.
1688 EXPECT_TRUE(RC.switchInternalEdgeToCall(C, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1689 ASSERT_EQ(1u, MergedCs.size());
1690 EXPECT_EQ(&CC, MergedCs[0]);
1691 }));
1692 ASSERT_EQ(3, RC.size());
1693 EXPECT_EQ(&DC, &RC[0]);
1694 EXPECT_EQ(&BC, &RC[1]);
1695 EXPECT_EQ(&AC, &RC[2]);
1696 EXPECT_EQ(2, BC.size());
1697 EXPECT_EQ(&BC, CG.lookupSCC(B));
1698 EXPECT_EQ(&BC, CG.lookupSCC(C));
1699 }
1700
1701 TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) {
1702 LLVMContext Context;
1703 // Test for having a post-order prior to changing a ref edge to a call edge
1704 // with SCCs connecting to the source and connecting to the target, but not
1705 // connecting to both, interleaved between the source and target. This
1706 // ensures we correctly partition the range rather than simply moving one or
1707 // the other.
1708 std::unique_ptr<Module> M =
1709 parseAssembly(Context, "define void @a() {\n"
1710 "entry:\n"
1711 " call void @b1()\n"
1712 " call void @c1()\n"
1713 " ret void\n"
1714 "}\n"
1715 "define void @b1() {\n"
1716 "entry:\n"
1717 " call void @c1()\n"
1718 " call void @b2()\n"
1719 " ret void\n"
1720 "}\n"
1721 "define void @c1() {\n"
1722 "entry:\n"
1723 " call void @b2()\n"
1724 " call void @c2()\n"
1725 " ret void\n"
1726 "}\n"
1727 "define void @b2() {\n"
1728 "entry:\n"
1729 " call void @c2()\n"
1730 " call void @b3()\n"
1731 " ret void\n"
1732 "}\n"
1733 "define void @c2() {\n"
1734 "entry:\n"
1735 " call void @b3()\n"
1736 " call void @c3()\n"
1737 " ret void\n"
1738 "}\n"
1739 "define void @b3() {\n"
1740 "entry:\n"
1741 " call void @c3()\n"
1742 " call void @d()\n"
1743 " ret void\n"
1744 "}\n"
1745 "define void @c3() {\n"
1746 "entry:\n"
1747 " store void()* @b1, void()** undef\n"
1748 " call void @d()\n"
1749 " ret void\n"
1750 "}\n"
1751 "define void @d() {\n"
1752 "entry:\n"
1753 " store void()* @a, void()** undef\n"
1754 " ret void\n"
1755 "}\n");
1756 LazyCallGraph CG = buildCG(*M);
1757
1758 // Force the graph to be fully expanded.
1759 CG.buildRefSCCs();
1760 auto I = CG.postorder_ref_scc_begin();
1761 LazyCallGraph::RefSCC &RC = *I++;
1762 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1763
1764 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1765 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
1766 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
1767 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
1768 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
1769 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
1770 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
1771 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1772 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1773 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1);
1774 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2);
1775 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3);
1776 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1);
1777 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2);
1778 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3);
1779 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1780
1781 // Several call edges are initially present to force a particual post-order.
1782 // Remove them now, leaving an interleaved post-order pattern.
1783 RC.switchTrivialInternalEdgeToRef(B3, C3);
1784 RC.switchTrivialInternalEdgeToRef(C2, B3);
1785 RC.switchTrivialInternalEdgeToRef(B2, C2);
1786 RC.switchTrivialInternalEdgeToRef(C1, B2);
1787 RC.switchTrivialInternalEdgeToRef(B1, C1);
1788
1789 // Check the initial post-order. We ensure this order with the extra edges
1790 // that are nuked above.
1791 ASSERT_EQ(8, RC.size());
1792 EXPECT_EQ(&DC, &RC[0]);
1793 EXPECT_EQ(&C3C, &RC[1]);
1794 EXPECT_EQ(&B3C, &RC[2]);
1795 EXPECT_EQ(&C2C, &RC[3]);
1796 EXPECT_EQ(&B2C, &RC[4]);
1797 EXPECT_EQ(&C1C, &RC[5]);
1798 EXPECT_EQ(&B1C, &RC[6]);
1799 EXPECT_EQ(&AC, &RC[7]);
1800
1801 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does
1802 // require reordering the SCCs in the face of tricky internal node
1803 // structures.
1804 EXPECT_FALSE(RC.switchInternalEdgeToCall(C3, B1));
1805 ASSERT_EQ(8, RC.size());
1806 EXPECT_EQ(&DC, &RC[0]);
1807 EXPECT_EQ(&B3C, &RC[1]);
1808 EXPECT_EQ(&B2C, &RC[2]);
1809 EXPECT_EQ(&B1C, &RC[3]);
1810 EXPECT_EQ(&C3C, &RC[4]);
1811 EXPECT_EQ(&C2C, &RC[5]);
1812 EXPECT_EQ(&C1C, &RC[6]);
1813 EXPECT_EQ(&AC, &RC[7]);
1814 }
1815
1816 TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {
1817 LLVMContext Context;
1818 // Test for having a postorder where between the source and target are all
1819 // three kinds of other SCCs:
1820 // 1) One connected to the target only that have to be shifted below the
1821 // source.
1822 // 2) One connected to the source only that have to be shifted below the
1823 // target.
1824 // 3) One connected to both source and target that has to remain and get
1825 // merged away.
1826 //
1827 // To achieve this we construct a heavily connected graph to force
1828 // a particular post-order. Then we remove the forcing edges and connect
1829 // a cycle.
1830 //
1831 // Diagram for the graph we want on the left and the graph we use to force
1832 // the ordering on the right. Edges ponit down or right.
1833 //
1834 // A | A |
1835 // / \ | / \ |
1836 // B E | B \ |
1837 // |\ | | |\ | |
1838 // | D | | C-D-E |
1839 // | \| | | \| |
1840 // C F | \ F |
1841 // \ / | \ / |
1842 // G | G |
1843 //
1844 // And we form a cycle by connecting F to B.
1845 std::unique_ptr<Module> M =
1846 parseAssembly(Context, "define void @a() {\n"
1847 "entry:\n"
1848 " call void @b()\n"
1849 " call void @e()\n"
1850 " ret void\n"
1851 "}\n"
1852 "define void @b() {\n"
1853 "entry:\n"
1854 " call void @c()\n"
1855 " call void @d()\n"
1856 " ret void\n"
1857 "}\n"
1858 "define void @c() {\n"
1859 "entry:\n"
1860 " call void @d()\n"
1861 " call void @g()\n"
1862 " ret void\n"
1863 "}\n"
1864 "define void @d() {\n"
1865 "entry:\n"
1866 " call void @e()\n"
1867 " call void @f()\n"
1868 " ret void\n"
1869 "}\n"
1870 "define void @e() {\n"
1871 "entry:\n"
1872 " call void @f()\n"
1873 " ret void\n"
1874 "}\n"
1875 "define void @f() {\n"
1876 "entry:\n"
1877 " store void()* @b, void()** undef\n"
1878 " call void @g()\n"
1879 " ret void\n"
1880 "}\n"
1881 "define void @g() {\n"
1882 "entry:\n"
1883 " store void()* @a, void()** undef\n"
1884 " ret void\n"
1885 "}\n");
1886 LazyCallGraph CG = buildCG(*M);
1887
1888 // Force the graph to be fully expanded.
1889 CG.buildRefSCCs();
1890 auto I = CG.postorder_ref_scc_begin();
1891 LazyCallGraph::RefSCC &RC = *I++;
1892 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1893
1894 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1895 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1896 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1897 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1898 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));
1899 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
1900 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
1901 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1902 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
1903 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1904 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1905 LazyCallGraph::SCC &EC = *CG.lookupSCC(E);
1906 LazyCallGraph::SCC &FC = *CG.lookupSCC(F);
1907 LazyCallGraph::SCC &GC = *CG.lookupSCC(G);
1908
1909 // Remove the extra edges that were used to force a particular post-order.
1910 RC.switchTrivialInternalEdgeToRef(C, D);
1911 RC.switchTrivialInternalEdgeToRef(D, E);
1912
1913 // Check the initial post-order. We ensure this order with the extra edges
1914 // that are nuked above.
1915 ASSERT_EQ(7, RC.size());
1916 EXPECT_EQ(&GC, &RC[0]);
1917 EXPECT_EQ(&FC, &RC[1]);
1918 EXPECT_EQ(&EC, &RC[2]);
1919 EXPECT_EQ(&DC, &RC[3]);
1920 EXPECT_EQ(&CC, &RC[4]);
1921 EXPECT_EQ(&BC, &RC[5]);
1922 EXPECT_EQ(&AC, &RC[6]);
1923
1924 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC,
1925 // and has to place the C and E SCCs on either side of it:
1926 // A A |
1927 // / \ / \ |
1928 // B E | E |
1929 // |\ | \ / |
1930 // | D | -> B |
1931 // | \| / \ |
1932 // C F C | |
1933 // \ / \ / |
1934 // G G |
1935 EXPECT_TRUE(RC.switchInternalEdgeToCall(
1936 F, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1937 ASSERT_EQ(2u, MergedCs.size());
1938 EXPECT_EQ(&FC, MergedCs[0]);
1939 EXPECT_EQ(&DC, MergedCs[1]);
1940 }));
1941 EXPECT_EQ(3, BC.size());
1942
1943 // And make sure the postorder was updated.
1944 ASSERT_EQ(5, RC.size());
1945 EXPECT_EQ(&GC, &RC[0]);
1946 EXPECT_EQ(&CC, &RC[1]);
1947 EXPECT_EQ(&BC, &RC[2]);
1948 EXPECT_EQ(&EC, &RC[3]);
1949 EXPECT_EQ(&AC, &RC[4]);
1950 }
1951
1952 // Test for IR containing constants using blockaddress constant expressions.
1953 // These are truly unique constructs: constant expressions with non-constant
1954 // operands.
1955 TEST(LazyCallGraphTest, HandleBlockAddress) {
1956 LLVMContext Context;
1957 std::unique_ptr<Module> M =
1958 parseAssembly(Context, "define void @f() {\n"
1959 "entry:\n"
1960 " ret void\n"
1961 "bb:\n"
1962 " unreachable\n"
1963 "}\n"
1964 "define void @g(i8** %ptr) {\n"
1965 "entry:\n"
1966 " store i8* blockaddress(@f, %bb), i8** %ptr\n"
1967 " ret void\n"
1968 "}\n");
1969 LazyCallGraph CG = buildCG(*M);
1970
1971 CG.buildRefSCCs();
1972 auto I = CG.postorder_ref_scc_begin();
1973 LazyCallGraph::RefSCC &FRC = *I++;
1974 LazyCallGraph::RefSCC &GRC = *I++;
1975 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1976
1977 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
1978 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
1979 EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
1980 EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
1981 EXPECT_FALSE(GRC.isParentOf(FRC));
1982 EXPECT_FALSE(FRC.isParentOf(GRC));
1983 }
1984
1985 // Test that a blockaddress that refers to itself creates no new RefSCC
1986 // connections. https://bugs.llvm.org/show_bug.cgi?id=40722
1987 TEST(LazyCallGraphTest, HandleBlockAddress2) {
1988 LLVMContext Context;
1989 std::unique_ptr<Module> M =
1990 parseAssembly(Context, "define void @f() {\n"
1991 " ret void\n"
1992 "}\n"
1993 "define void @g(i8** %ptr) {\n"
1994 "bb:\n"
1995 " store i8* blockaddress(@g, %bb), i8** %ptr\n"
1996 " ret void\n"
1997 "}\n");
1998 LazyCallGraph CG = buildCG(*M);
1999
2000 CG.buildRefSCCs();
2001 auto I = CG.postorder_ref_scc_begin();
2002 LazyCallGraph::RefSCC &FRC = *I++;
2003 LazyCallGraph::RefSCC &GRC = *I++;
2004 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2005
2006 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
2007 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
2008 EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
2009 EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
2010 EXPECT_FALSE(GRC.isParentOf(FRC));
2011 EXPECT_FALSE(FRC.isParentOf(GRC));
2012 }
2013
2014 TEST(LazyCallGraphTest, ReplaceNodeFunction) {
2015 LLVMContext Context;
2016 // A graph with several different kinds of edges pointing at a particular
2017 // function.
2018 std::unique_ptr<Module> M =
2019 parseAssembly(Context,
2020 "define void @a(i8** %ptr) {\n"
2021 "entry:\n"
2022 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2023 " ret void\n"
2024 "}\n"
2025 "define void @b(i8** %ptr) {\n"
2026 "entry:\n"
2027 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2028 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2029 " call void @d(i8** %ptr)"
2030 " ret void\n"
2031 "}\n"
2032 "define void @c(i8** %ptr) {\n"
2033 "entry:\n"
2034 " call void @d(i8** %ptr)"
2035 " call void @d(i8** %ptr)"
2036 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2037 " ret void\n"
2038 "}\n"
2039 "define void @d(i8** %ptr) {\n"
2040 "entry:\n"
2041 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
2042 " call void @c(i8** %ptr)"
2043 " call void @d(i8** %ptr)"
2044 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2045 " ret void\n"
2046 "}\n");
2047 LazyCallGraph CG = buildCG(*M);
2048
2049 // Force the graph to be fully expanded.
2050 CG.buildRefSCCs();
2051 auto I = CG.postorder_ref_scc_begin();
2052 LazyCallGraph::RefSCC &RC1 = *I++;
2053 LazyCallGraph::RefSCC &RC2 = *I++;
2054 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2055
2056 ASSERT_EQ(2, RC1.size());
2057 LazyCallGraph::SCC &C1 = RC1[0];
2058 LazyCallGraph::SCC &C2 = RC1[1];
2059
2060 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
2061 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
2062 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
2063 LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d"));
2064 EXPECT_EQ(&C1, CG.lookupSCC(DN));
2065 EXPECT_EQ(&C1, CG.lookupSCC(CN));
2066 EXPECT_EQ(&C2, CG.lookupSCC(BN));
2067 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
2068 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
2069 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
2070 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
2071
2072 // Now we need to build a new function 'e' with the same signature as 'd'.
2073 Function &D = DN.getFunction();
2074 Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e");
2075 D.getParent()->getFunctionList().insert(D.getIterator(), &E);
2076
2077 // Change each use of 'd' to use 'e'. This is particularly easy as they have
2078 // the same type.
2079 D.replaceAllUsesWith(&E);
2080
2081 // Splice the body of the old function into the new one.
2082 E.splice(E.begin(), &D);
2083 // And fix up the one argument.
2084 D.arg_begin()->replaceAllUsesWith(&*E.arg_begin());
2085 E.arg_begin()->takeName(&*D.arg_begin());
2086
2087 // Now replace the function in the graph.
2088 RC1.replaceNodeFunction(DN, E);
2089
2090 EXPECT_EQ(&E, &DN.getFunction());
2091 EXPECT_EQ(&DN, &(*CN)[DN].getNode());
2092 EXPECT_EQ(&DN, &(*BN)[DN].getNode());
2093 }
2094
2095 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRef) {
2096 LLVMContext Context;
2097 // A graph with a couple of RefSCCs.
2098 std::unique_ptr<Module> M =
2099 parseAssembly(Context,
2100 "define void @a(i8** %ptr) {\n"
2101 "entry:\n"
2102 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2103 " ret void\n"
2104 "}\n"
2105 "define void @b(i8** %ptr) {\n"
2106 "entry:\n"
2107 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
2108 " ret void\n"
2109 "}\n"
2110 "define void @c(i8** %ptr) {\n"
2111 "entry:\n"
2112 " call void @d(i8** %ptr)"
2113 " ret void\n"
2114 "}\n"
2115 "define void @d(i8** %ptr) {\n"
2116 "entry:\n"
2117 " call void @c(i8** %ptr)"
2118 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
2119 " ret void\n"
2120 "}\n"
2121 "define void @dead() {\n"
2122 "entry:\n"
2123 " ret void\n"
2124 "}\n");
2125 LazyCallGraph CG = buildCG(*M);
2126
2127 // Insert spurious ref edges.
2128 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2129 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2130 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2131 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));
2132 LazyCallGraph::Node &DeadN = CG.get(lookupFunction(*M, "dead"));
2133 AN.populate();
2134 BN.populate();
2135 CN.populate();
2136 DN.populate();
2137 DeadN.populate();
2138 CG.insertEdge(AN, DeadN, LazyCallGraph::Edge::Ref);
2139 CG.insertEdge(BN, DeadN, LazyCallGraph::Edge::Ref);
2140 CG.insertEdge(CN, DeadN, LazyCallGraph::Edge::Ref);
2141 CG.insertEdge(DN, DeadN, LazyCallGraph::Edge::Ref);
2142
2143 // Force the graph to be fully expanded.
2144 CG.buildRefSCCs();
2145 auto I = CG.postorder_ref_scc_begin();
2146 LazyCallGraph::RefSCC &DeadRC = *I++;
2147 LazyCallGraph::RefSCC &RC1 = *I++;
2148 LazyCallGraph::RefSCC &RC2 = *I++;
2149 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2150
2151 ASSERT_EQ(2, RC1.size());
2152 LazyCallGraph::SCC &C1 = RC1[0];
2153 LazyCallGraph::SCC &C2 = RC1[1];
2154
2155 EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN));
2156 EXPECT_EQ(&C1, CG.lookupSCC(DN));
2157 EXPECT_EQ(&C1, CG.lookupSCC(CN));
2158 EXPECT_EQ(&C2, CG.lookupSCC(BN));
2159 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
2160 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
2161 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
2162 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
2163
2164 // Now delete 'dead'. There are no uses of this function but there are
2165 // spurious references.
2166 CG.removeDeadFunction(DeadN.getFunction());
2167
2168 // The only observable change should be that the RefSCC is gone from the
2169 // postorder sequence.
2170 I = CG.postorder_ref_scc_begin();
2171 EXPECT_EQ(&RC1, &*I++);
2172 EXPECT_EQ(&RC2, &*I++);
2173 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2174 }
2175
2176 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive) {
2177 LLVMContext Context;
2178 std::unique_ptr<Module> M =
2179 parseAssembly(Context, "define void @a(ptr %p) {\n"
2180 " store ptr @b, ptr %p\n"
2181 " ret void\n"
2182 "}\n"
2183 "define void @b(ptr %p) {\n"
2184 " store ptr @c, ptr %p\n"
2185 " ret void\n"
2186 "}\n"
2187 "define void @c(ptr %p) {\n"
2188 " ret void\n"
2189 "}\n");
2190 LazyCallGraph CG = buildCG(*M);
2191
2192 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2193 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2194 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2195 AN.populate();
2196 BN.populate();
2197 CN.populate();
2198 // Insert spurious ref edge.
2199 CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref);
2200
2201 // Force the graph to be fully expanded.
2202 CG.buildRefSCCs();
2203 auto I = CG.postorder_ref_scc_begin();
2204 LazyCallGraph::RefSCC &RC = *I++;
2205 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2206
2207 ASSERT_EQ(RC.size(), 3);
2208
2209 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2210 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2211 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2212
2213 // Now delete 'a'. There are no uses of this function but there are
2214 // spurious references.
2215 CG.removeDeadFunction(AN.getFunction());
2216
2217 // The only observable change should be that the RefSCC is gone from the
2218 // postorder sequence.
2219 I = CG.postorder_ref_scc_begin();
2220 EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);
2221 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2222 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2223 }
2224
2225 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive2) {
2226 LLVMContext Context;
2227 std::unique_ptr<Module> M =
2228 parseAssembly(Context, "define void @a(ptr %p) {\n"
2229 " store ptr @b, ptr %p\n"
2230 " ret void\n"
2231 "}\n"
2232 "define void @b(ptr %p) {\n"
2233 " store ptr @c, ptr %p\n"
2234 " ret void\n"
2235 "}\n"
2236 "define void @c(ptr %p) {\n"
2237 " store ptr @b, ptr %p\n"
2238 " store ptr @d, ptr %p\n"
2239 " ret void\n"
2240 "}\n"
2241 "define void @d(ptr %p) {\n"
2242 " ret void\n"
2243 "}\n");
2244 LazyCallGraph CG = buildCG(*M);
2245
2246 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2247 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2248 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2249 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));
2250 AN.populate();
2251 BN.populate();
2252 CN.populate();
2253 DN.populate();
2254 // Insert spurious ref edge.
2255 CG.insertEdge(DN, AN, LazyCallGraph::Edge::Ref);
2256
2257 // Force the graph to be fully expanded.
2258 CG.buildRefSCCs();
2259 auto I = CG.postorder_ref_scc_begin();
2260 LazyCallGraph::RefSCC &RC = *I++;
2261 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2262
2263 ASSERT_EQ(4, RC.size());
2264
2265 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2266 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2267 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2268 EXPECT_EQ(&RC, CG.lookupRefSCC(DN));
2269
2270 // Now delete 'a'. There are no uses of this function but there are
2271 // spurious references.
2272 CG.removeDeadFunction(AN.getFunction());
2273
2274 // The only observable change should be that the RefSCC is gone from the
2275 // postorder sequence.
2276 I = CG.postorder_ref_scc_begin();
2277 EXPECT_EQ(CG.lookupRefSCC(DN), &*I++);
2278 EXPECT_EQ(CG.lookupRefSCC(CN), &*I);
2279 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2280 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2281 }
2282
2283 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive3) {
2284 LLVMContext Context;
2285 std::unique_ptr<Module> M =
2286 parseAssembly(Context, "define void @a(ptr %p) {\n"
2287 " store ptr @b, ptr %p\n"
2288 " ret void\n"
2289 "}\n"
2290 "define void @b(ptr %p) {\n"
2291 " store ptr @c, ptr %p\n"
2292 " ret void\n"
2293 "}\n"
2294 "define void @c(ptr %p) {\n"
2295 " ret void\n"
2296 "}\n");
2297 LazyCallGraph CG = buildCG(*M);
2298
2299 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2300 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2301 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2302 AN.populate();
2303 BN.populate();
2304 CN.populate();
2305 // Insert spurious ref edges.
2306 CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref);
2307 CG.insertEdge(BN, AN, LazyCallGraph::Edge::Ref);
2308
2309 // Force the graph to be fully expanded.
2310 CG.buildRefSCCs();
2311 auto I = CG.postorder_ref_scc_begin();
2312 LazyCallGraph::RefSCC &RC = *I++;
2313 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2314
2315 ASSERT_EQ(RC.size(), 3);
2316
2317 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2318 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2319 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2320
2321 // Now delete 'a'. There are no uses of this function but there are
2322 // spurious references.
2323 CG.removeDeadFunction(AN.getFunction());
2324
2325 // The only observable change should be that the RefSCC is gone from the
2326 // postorder sequence.
2327 I = CG.postorder_ref_scc_begin();
2328 EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);
2329 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2330 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2331 }
2332
2333 TEST(LazyCallGraphTest, AddSplitFunction1) {
2334 LLVMContext Context;
2335 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2336 " ret void\n"
2337 "}\n");
2338 LazyCallGraph CG = buildCG(*M);
2339
2340 Function &F = lookupFunction(*M, "f");
2341 LazyCallGraph::Node &FN = CG.get(F);
2342
2343 // Force the graph to be fully expanded.
2344 CG.buildRefSCCs();
2345 auto I = CG.postorder_ref_scc_begin();
2346 LazyCallGraph::RefSCC *ORC = &*I++;
2347 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2348
2349 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2350 F.getAddressSpace(), "g", F.getParent());
2351 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2352 (void)ReturnInst::Create(Context, GBB);
2353
2354 // Create f -call-> g.
2355 (void)CallInst::Create(G, {}, "", &*F.getEntryBlock().begin());
2356
2357 EXPECT_FALSE(verifyModule(*M, &errs()));
2358
2359 CG.addSplitFunction(F, *G);
2360
2361 LazyCallGraph::Node *GN = CG.lookup(*G);
2362 EXPECT_TRUE(GN);
2363
2364 I = CG.postorder_ref_scc_begin();
2365 LazyCallGraph::RefSCC *RC1 = &*I++;
2366 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2367 LazyCallGraph::RefSCC *RC2 = &*I++;
2368 EXPECT_EQ(RC2, ORC);
2369 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2370 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2371 }
2372
2373 TEST(LazyCallGraphTest, AddSplitFunction2) {
2374 LLVMContext Context;
2375 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2376 " ret void\n"
2377 "}\n");
2378 LazyCallGraph CG = buildCG(*M);
2379
2380 Function &F = lookupFunction(*M, "f");
2381 LazyCallGraph::Node &FN = CG.get(F);
2382
2383 // Force the graph to be fully expanded.
2384 CG.buildRefSCCs();
2385 auto I = CG.postorder_ref_scc_begin();
2386 LazyCallGraph::RefSCC *ORC = &*I++;
2387 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2388
2389 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2390 F.getAddressSpace(), "g", F.getParent());
2391 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2392 (void)ReturnInst::Create(Context, GBB);
2393
2394 // Create f -ref-> g.
2395 (void)CastInst::CreatePointerCast(G, Type::getInt8PtrTy(Context), "",
2396 &*F.getEntryBlock().begin());
2397
2398 EXPECT_FALSE(verifyModule(*M, &errs()));
2399
2400 CG.addSplitFunction(F, *G);
2401
2402 LazyCallGraph::Node *GN = CG.lookup(*G);
2403 EXPECT_TRUE(GN);
2404
2405 I = CG.postorder_ref_scc_begin();
2406 LazyCallGraph::RefSCC *RC1 = &*I++;
2407 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2408 LazyCallGraph::RefSCC *RC2 = &*I++;
2409 EXPECT_EQ(RC2, ORC);
2410 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2411 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2412 }
2413
2414 TEST(LazyCallGraphTest, AddSplitFunction3) {
2415 LLVMContext Context;
2416 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2417 " ret void\n"
2418 "}\n");
2419 LazyCallGraph CG = buildCG(*M);
2420
2421 Function &F = lookupFunction(*M, "f");
2422 LazyCallGraph::Node &FN = CG.get(F);
2423
2424 // Force the graph to be fully expanded.
2425 CG.buildRefSCCs();
2426 auto I = CG.postorder_ref_scc_begin();
2427 LazyCallGraph::RefSCC *ORC = &*I++;
2428 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2429
2430 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2431 F.getAddressSpace(), "g", F.getParent());
2432 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2433 // Create g -ref-> f.
2434 (void)CastInst::CreatePointerCast(&F, Type::getInt8PtrTy(Context), "", GBB);
2435 (void)ReturnInst::Create(Context, GBB);
2436
2437 // Create f -call-> g.
2438 (void)CallInst::Create(G, {}, "", &*F.getEntryBlock().begin());
2439
2440 EXPECT_FALSE(verifyModule(*M, &errs()));
2441
2442 CG.addSplitFunction(F, *G);
2443
2444 LazyCallGraph::Node *GN = CG.lookup(*G);
2445 EXPECT_TRUE(GN);
2446
2447 I = CG.postorder_ref_scc_begin();
2448 LazyCallGraph::RefSCC *RC = &*I++;
2449 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2450 EXPECT_EQ(RC, ORC);
2451 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2452
2453 EXPECT_EQ(2, RC->size());
2454 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2455 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]);
2456 }
2457
2458 TEST(LazyCallGraphTest, AddSplitFunction4) {
2459 LLVMContext Context;
2460 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2461 " ret void\n"
2462 "}\n");
2463 LazyCallGraph CG = buildCG(*M);
2464
2465 Function &F = lookupFunction(*M, "f");
2466 LazyCallGraph::Node &FN = CG.get(F);
2467
2468 // Force the graph to be fully expanded.
2469 CG.buildRefSCCs();
2470 auto I = CG.postorder_ref_scc_begin();
2471 LazyCallGraph::RefSCC *ORC = &*I++;
2472 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2473
2474 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2475 F.getAddressSpace(), "g", F.getParent());
2476 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2477 // Create g -ref-> f.
2478 (void)CastInst::CreatePointerCast(&F, Type::getInt8PtrTy(Context), "", GBB);
2479 (void)ReturnInst::Create(Context, GBB);
2480
2481 // Create f -ref-> g.
2482 (void)CastInst::CreatePointerCast(G, Type::getInt8PtrTy(Context), "",
2483 &*F.getEntryBlock().begin());
2484
2485 EXPECT_FALSE(verifyModule(*M, &errs()));
2486
2487 CG.addSplitFunction(F, *G);
2488
2489 LazyCallGraph::Node *GN = CG.lookup(*G);
2490 EXPECT_TRUE(GN);
2491
2492 I = CG.postorder_ref_scc_begin();
2493 LazyCallGraph::RefSCC *RC = &*I++;
2494 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2495 EXPECT_EQ(RC, ORC);
2496 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2497
2498 // Order doesn't matter for sibling SCCs.
2499 EXPECT_EQ(2, RC->size());
2500 EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC);
2501 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2502 }
2503
2504 TEST(LazyCallGraphTest, AddSplitFunction5) {
2505 LLVMContext Context;
2506 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2507 " ret void\n"
2508 "}\n");
2509 LazyCallGraph CG = buildCG(*M);
2510
2511 Function &F = lookupFunction(*M, "f");
2512 LazyCallGraph::Node &FN = CG.get(F);
2513
2514 // Force the graph to be fully expanded.
2515 CG.buildRefSCCs();
2516 auto I = CG.postorder_ref_scc_begin();
2517 LazyCallGraph::RefSCC *ORC = &*I++;
2518 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2519
2520 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2521 F.getAddressSpace(), "g", F.getParent());
2522 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2523 // Create g -call-> f.
2524 (void)CallInst::Create(&F, {}, "", GBB);
2525 (void)ReturnInst::Create(Context, GBB);
2526
2527 // Create f -ref-> g.
2528 (void)CastInst::CreatePointerCast(G, Type::getInt8PtrTy(Context), "",
2529 &*F.getEntryBlock().begin());
2530
2531 EXPECT_FALSE(verifyModule(*M, &errs()));
2532
2533 CG.addSplitFunction(F, *G);
2534
2535 LazyCallGraph::Node *GN = CG.lookup(*G);
2536 EXPECT_TRUE(GN);
2537
2538 I = CG.postorder_ref_scc_begin();
2539 LazyCallGraph::RefSCC *RC = &*I++;
2540 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2541 EXPECT_EQ(RC, ORC);
2542 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2543
2544 EXPECT_EQ(2, RC->size());
2545 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2546 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]);
2547 }
2548
2549 TEST(LazyCallGraphTest, AddSplitFunction6) {
2550 LLVMContext Context;
2551 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2552 " ret void\n"
2553 "}\n");
2554 LazyCallGraph CG = buildCG(*M);
2555
2556 Function &F = lookupFunction(*M, "f");
2557 LazyCallGraph::Node &FN = CG.get(F);
2558
2559 // Force the graph to be fully expanded.
2560 CG.buildRefSCCs();
2561 auto I = CG.postorder_ref_scc_begin();
2562 LazyCallGraph::RefSCC *ORC = &*I++;
2563 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2564
2565 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2566 F.getAddressSpace(), "g", F.getParent());
2567 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2568 // Create g -call-> f.
2569 (void)CallInst::Create(&F, {}, "", GBB);
2570 (void)ReturnInst::Create(Context, GBB);
2571
2572 // Create f -call-> g.
2573 (void)CallInst::Create(G, {}, "", &*F.getEntryBlock().begin());
2574
2575 EXPECT_FALSE(verifyModule(*M, &errs()));
2576
2577 CG.addSplitFunction(F, *G);
2578
2579 LazyCallGraph::Node *GN = CG.lookup(*G);
2580 EXPECT_TRUE(GN);
2581
2582 I = CG.postorder_ref_scc_begin();
2583 LazyCallGraph::RefSCC *RC = &*I++;
2584 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2585 EXPECT_EQ(RC, ORC);
2586 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2587
2588 EXPECT_EQ(1, RC->size());
2589 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2590 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2591 }
2592
2593 TEST(LazyCallGraphTest, AddSplitFunction7) {
2594 LLVMContext Context;
2595 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2596 " call void @f2()\n"
2597 " ret void\n"
2598 "}\n"
2599 "define void @f2() {\n"
2600 " call void @f()\n"
2601 " ret void\n"
2602 "}\n");
2603 LazyCallGraph CG = buildCG(*M);
2604
2605 Function &F = lookupFunction(*M, "f");
2606 LazyCallGraph::Node &FN = CG.get(F);
2607 Function &F2 = lookupFunction(*M, "f2");
2608 LazyCallGraph::Node &F2N = CG.get(F2);
2609
2610 // Force the graph to be fully expanded.
2611 CG.buildRefSCCs();
2612 auto I = CG.postorder_ref_scc_begin();
2613 LazyCallGraph::RefSCC *ORC = &*I++;
2614 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2615
2616 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2617 F.getAddressSpace(), "g", F.getParent());
2618 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2619 // Create g -call-> f2.
2620 (void)CallInst::Create(&F2, {}, "", GBB);
2621 (void)ReturnInst::Create(Context, GBB);
2622
2623 // Create f -call-> g.
2624 (void)CallInst::Create(G, {}, "", &*F.getEntryBlock().begin());
2625
2626 EXPECT_FALSE(verifyModule(*M, &errs()));
2627
2628 CG.addSplitFunction(F, *G);
2629
2630 LazyCallGraph::Node *GN = CG.lookup(*G);
2631 EXPECT_TRUE(GN);
2632
2633 I = CG.postorder_ref_scc_begin();
2634 LazyCallGraph::RefSCC *RC = &*I++;
2635 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2636 EXPECT_EQ(RC, ORC);
2637 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2638
2639 EXPECT_EQ(1, RC->size());
2640 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2641 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]);
2642 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2643 }
2644
2645 TEST(LazyCallGraphTest, AddSplitFunction8) {
2646 LLVMContext Context;
2647 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2648 " call void @f2()\n"
2649 " ret void\n"
2650 "}\n"
2651 "define void @f2() {\n"
2652 " call void @f()\n"
2653 " ret void\n"
2654 "}\n");
2655 LazyCallGraph CG = buildCG(*M);
2656
2657 Function &F = lookupFunction(*M, "f");
2658 LazyCallGraph::Node &FN = CG.get(F);
2659 Function &F2 = lookupFunction(*M, "f2");
2660 LazyCallGraph::Node &F2N = CG.get(F2);
2661
2662 // Force the graph to be fully expanded.
2663 CG.buildRefSCCs();
2664 auto I = CG.postorder_ref_scc_begin();
2665 LazyCallGraph::RefSCC *ORC = &*I++;
2666 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2667
2668 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2669 F.getAddressSpace(), "g", F.getParent());
2670 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2671 // Create g -call-> f2.
2672 (void)CallInst::Create(&F2, {}, "", GBB);
2673 (void)ReturnInst::Create(Context, GBB);
2674
2675 // Create f -ref-> g.
2676 (void)CastInst::CreatePointerCast(G, Type::getInt8PtrTy(Context), "",
2677 &*F.getEntryBlock().begin());
2678
2679 EXPECT_FALSE(verifyModule(*M, &errs()));
2680
2681 CG.addSplitFunction(F, *G);
2682
2683 LazyCallGraph::Node *GN = CG.lookup(*G);
2684 EXPECT_TRUE(GN);
2685
2686 I = CG.postorder_ref_scc_begin();
2687 LazyCallGraph::RefSCC *RC = &*I++;
2688 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2689 EXPECT_EQ(RC, ORC);
2690 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2691
2692 EXPECT_EQ(2, RC->size());
2693 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2694 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]);
2695 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]);
2696 }
2697
2698 TEST(LazyCallGraphTest, AddSplitFunction9) {
2699 LLVMContext Context;
2700 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2701 " call void @f2()\n"
2702 " ret void\n"
2703 "}\n"
2704 "define void @f2() {\n"
2705 " call void @f()\n"
2706 " ret void\n"
2707 "}\n");
2708 LazyCallGraph CG = buildCG(*M);
2709
2710 Function &F = lookupFunction(*M, "f");
2711 LazyCallGraph::Node &FN = CG.get(F);
2712 Function &F2 = lookupFunction(*M, "f2");
2713 LazyCallGraph::Node &F2N = CG.get(F2);
2714
2715 // Force the graph to be fully expanded.
2716 CG.buildRefSCCs();
2717 auto I = CG.postorder_ref_scc_begin();
2718 LazyCallGraph::RefSCC *ORC = &*I++;
2719 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2720
2721 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2722 F.getAddressSpace(), "g", F.getParent());
2723 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2724 // Create g -ref-> f2.
2725 (void)CastInst::CreatePointerCast(&F2, Type::getInt8PtrTy(Context), "", GBB);
2726 (void)ReturnInst::Create(Context, GBB);
2727
2728 // Create f -call-> g.
2729 (void)CallInst::Create(G, {}, "", &*F.getEntryBlock().begin());
2730
2731 EXPECT_FALSE(verifyModule(*M, &errs()));
2732
2733 CG.addSplitFunction(F, *G);
2734
2735 LazyCallGraph::Node *GN = CG.lookup(*G);
2736 EXPECT_TRUE(GN);
2737
2738 I = CG.postorder_ref_scc_begin();
2739 LazyCallGraph::RefSCC *RC = &*I++;
2740 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2741 EXPECT_EQ(RC, ORC);
2742 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2743
2744 EXPECT_EQ(2, RC->size());
2745 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2746 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]);
2747 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[1]);
2748 }
2749
2750 TEST(LazyCallGraphTest, AddSplitFunctions1) {
2751 LLVMContext Context;
2752 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2753 " ret void\n"
2754 "}\n");
2755 LazyCallGraph CG = buildCG(*M);
2756
2757 Function &F = lookupFunction(*M, "f");
2758 LazyCallGraph::Node &FN = CG.get(F);
2759
2760 // Force the graph to be fully expanded.
2761 CG.buildRefSCCs();
2762 auto I = CG.postorder_ref_scc_begin();
2763 LazyCallGraph::RefSCC *ORC = &*I++;
2764 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2765
2766 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2767 F.getAddressSpace(), "g", F.getParent());
2768 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2769 (void)ReturnInst::Create(Context, GBB);
2770
2771 // Create f -ref-> g.
2772 (void)CastInst::CreatePointerCast(G, Type::getInt8PtrTy(Context), "",
2773 &*F.getEntryBlock().begin());
2774
2775 EXPECT_FALSE(verifyModule(*M, &errs()));
2776
2777 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G}));
2778
2779 LazyCallGraph::Node *GN = CG.lookup(*G);
2780 EXPECT_TRUE(GN);
2781
2782 I = CG.postorder_ref_scc_begin();
2783 LazyCallGraph::RefSCC *RC1 = &*I++;
2784 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2785 LazyCallGraph::RefSCC *RC2 = &*I++;
2786 EXPECT_EQ(RC2, ORC);
2787 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2788 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2789 }
2790
2791 TEST(LazyCallGraphTest, AddSplitFunctions2) {
2792 LLVMContext Context;
2793 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2794 " ret void\n"
2795 "}\n");
2796 LazyCallGraph CG = buildCG(*M);
2797
2798 Function &F = lookupFunction(*M, "f");
2799 LazyCallGraph::Node &FN = CG.get(F);
2800
2801 // Force the graph to be fully expanded.
2802 CG.buildRefSCCs();
2803 auto I = CG.postorder_ref_scc_begin();
2804 LazyCallGraph::RefSCC *ORC = &*I++;
2805 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2806
2807 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2808 F.getAddressSpace(), "g", F.getParent());
2809 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2810 // Create g -ref-> f.
2811 (void)CastInst::CreatePointerCast(&F, Type::getInt8PtrTy(Context), "", GBB);
2812 (void)ReturnInst::Create(Context, GBB);
2813
2814 // Create f -ref-> g.
2815 (void)CastInst::CreatePointerCast(G, Type::getInt8PtrTy(Context), "",
2816 &*F.getEntryBlock().begin());
2817
2818 EXPECT_FALSE(verifyModule(*M, &errs()));
2819
2820 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G}));
2821
2822 LazyCallGraph::Node *GN = CG.lookup(*G);
2823 EXPECT_TRUE(GN);
2824
2825 I = CG.postorder_ref_scc_begin();
2826 LazyCallGraph::RefSCC *RC = &*I++;
2827 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2828 EXPECT_EQ(RC, ORC);
2829 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2830
2831 // Order doesn't matter for sibling SCCs.
2832 EXPECT_EQ(2, RC->size());
2833 EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC);
2834 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2835 }
2836
2837 TEST(LazyCallGraphTest, AddSplitFunctions3) {
2838 LLVMContext Context;
2839 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2840 " ret void\n"
2841 "}\n");
2842 LazyCallGraph CG = buildCG(*M);
2843
2844 Function &F = lookupFunction(*M, "f");
2845 LazyCallGraph::Node &FN = CG.get(F);
2846
2847 // Force the graph to be fully expanded.
2848 CG.buildRefSCCs();
2849 auto I = CG.postorder_ref_scc_begin();
2850 LazyCallGraph::RefSCC *ORC = &*I++;
2851 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2852
2853 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
2854 F.getAddressSpace(), "g1", F.getParent());
2855 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
2856 F.getAddressSpace(), "g2", F.getParent());
2857 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);
2858 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);
2859 // Create g1 -ref-> g2 and g2 -ref-> g1.
2860 (void)CastInst::CreatePointerCast(G2, Type::getInt8PtrTy(Context), "", G1BB);
2861 (void)CastInst::CreatePointerCast(G1, Type::getInt8PtrTy(Context), "", G2BB);
2862 (void)ReturnInst::Create(Context, G1BB);
2863 (void)ReturnInst::Create(Context, G2BB);
2864
2865 // Create f -ref-> g1 and f -ref-> g2.
2866 (void)CastInst::CreatePointerCast(G1, Type::getInt8PtrTy(Context), "",
2867 &*F.getEntryBlock().begin());
2868 (void)CastInst::CreatePointerCast(G2, Type::getInt8PtrTy(Context), "",
2869 &*F.getEntryBlock().begin());
2870
2871 EXPECT_FALSE(verifyModule(*M, &errs()));
2872
2873 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));
2874
2875 LazyCallGraph::Node *G1N = CG.lookup(*G1);
2876 EXPECT_TRUE(G1N);
2877 LazyCallGraph::Node *G2N = CG.lookup(*G2);
2878 EXPECT_TRUE(G2N);
2879
2880 I = CG.postorder_ref_scc_begin();
2881 LazyCallGraph::RefSCC *RC1 = &*I++;
2882 EXPECT_EQ(2, RC1->size());
2883 EXPECT_EQ(RC1, CG.lookupRefSCC(*G1N));
2884 EXPECT_EQ(RC1, CG.lookupRefSCC(*G2N));
2885 LazyCallGraph::RefSCC *RC2 = &*I++;
2886 EXPECT_EQ(RC2, ORC);
2887 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2888 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2889 }
2890
2891 TEST(LazyCallGraphTest, AddSplitFunctions4) {
2892 LLVMContext Context;
2893 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2894 " ret void\n"
2895 "}\n");
2896 LazyCallGraph CG = buildCG(*M);
2897
2898 Function &F = lookupFunction(*M, "f");
2899 LazyCallGraph::Node &FN = CG.get(F);
2900
2901 // Force the graph to be fully expanded.
2902 CG.buildRefSCCs();
2903 auto I = CG.postorder_ref_scc_begin();
2904 LazyCallGraph::RefSCC *ORC = &*I++;
2905 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2906
2907 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
2908 F.getAddressSpace(), "g1", F.getParent());
2909 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
2910 F.getAddressSpace(), "g2", F.getParent());
2911 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);
2912 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);
2913 // Create g1 -ref-> g2 and g2 -ref-> g1.
2914 (void)CastInst::CreatePointerCast(G2, Type::getInt8PtrTy(Context), "", G1BB);
2915 (void)CastInst::CreatePointerCast(G1, Type::getInt8PtrTy(Context), "", G2BB);
2916 // Create g2 -ref-> f.
2917 (void)CastInst::CreatePointerCast(&F, Type::getInt8PtrTy(Context), "", G2BB);
2918 (void)ReturnInst::Create(Context, G1BB);
2919 (void)ReturnInst::Create(Context, G2BB);
2920
2921 // Create f -ref-> g1 and f -ref-> g2.
2922 (void)CastInst::CreatePointerCast(G1, Type::getInt8PtrTy(Context), "",
2923 &*F.getEntryBlock().begin());
2924 (void)CastInst::CreatePointerCast(G2, Type::getInt8PtrTy(Context), "",
2925 &*F.getEntryBlock().begin());
2926
2927 EXPECT_FALSE(verifyModule(*M, &errs()));
2928
2929 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));
2930
2931 LazyCallGraph::Node *G1N = CG.lookup(*G1);
2932 EXPECT_TRUE(G1N);
2933 LazyCallGraph::Node *G2N = CG.lookup(*G2);
2934 EXPECT_TRUE(G2N);
2935
2936 I = CG.postorder_ref_scc_begin();
2937 LazyCallGraph::RefSCC *RC = &*I++;
2938 EXPECT_EQ(RC, ORC);
2939 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2940
2941 // Order doesn't matter for sibling SCCs.
2942 EXPECT_EQ(3, RC->size());
2943 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2944 EXPECT_EQ(&CG.lookupSCC(*G1N)->getOuterRefSCC(), RC);
2945 EXPECT_EQ(&CG.lookupSCC(*G2N)->getOuterRefSCC(), RC);
2946 EXPECT_EQ(RC, CG.lookupRefSCC(*G1N));
2947 EXPECT_EQ(RC, CG.lookupRefSCC(*G2N));
2948 }
2949
2950 TEST(LazyCallGraphTest, AddSplitFunctions5) {
2951 LLVMContext Context;
2952 std::unique_ptr<Module> M =
2953 parseAssembly(Context, "define void @f() {\n"
2954 " %1 = bitcast void ()* @f2 to i8*\n"
2955 " ret void\n"
2956 "}\n"
2957 "define void @f2() {\n"
2958 " call void @f()\n"
2959 " ret void\n"
2960 "}\n");
2961 LazyCallGraph CG = buildCG(*M);
2962
2963 Function &F = lookupFunction(*M, "f");
2964 LazyCallGraph::Node &FN = CG.get(F);
2965 Function &F2 = lookupFunction(*M, "f2");
2966 LazyCallGraph::Node &F2N = CG.get(F);
2967
2968 // Force the graph to be fully expanded.
2969 CG.buildRefSCCs();
2970 auto I = CG.postorder_ref_scc_begin();
2971 LazyCallGraph::RefSCC *ORC = &*I++;
2972 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2973
2974 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
2975 F.getAddressSpace(), "g1", F.getParent());
2976 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
2977 F.getAddressSpace(), "g2", F.getParent());
2978 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);
2979 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);
2980 // Create g1 -ref-> g2 and g2 -ref-> g1.
2981 (void)CastInst::CreatePointerCast(G2, Type::getInt8PtrTy(Context), "", G1BB);
2982 (void)CastInst::CreatePointerCast(G1, Type::getInt8PtrTy(Context), "", G2BB);
2983 // Create g2 -ref-> f2.
2984 (void)CastInst::CreatePointerCast(&F2, Type::getInt8PtrTy(Context), "", G2BB);
2985 (void)ReturnInst::Create(Context, G1BB);
2986 (void)ReturnInst::Create(Context, G2BB);
2987
2988 // Create f -ref-> g1 and f -ref-> g2.
2989 (void)CastInst::CreatePointerCast(G1, Type::getInt8PtrTy(Context), "",
2990 &*F.getEntryBlock().begin());
2991 (void)CastInst::CreatePointerCast(G2, Type::getInt8PtrTy(Context), "",
2992 &*F.getEntryBlock().begin());
2993
2994 EXPECT_FALSE(verifyModule(*M, &errs()));
2995
2996 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));
2997
2998 LazyCallGraph::Node *G1N = CG.lookup(*G1);
2999 EXPECT_TRUE(G1N);
3000 LazyCallGraph::Node *G2N = CG.lookup(*G2);
3001 EXPECT_TRUE(G2N);
3002
3003 I = CG.postorder_ref_scc_begin();
3004 LazyCallGraph::RefSCC *RC = &*I++;
3005 EXPECT_EQ(4, RC->size());
3006 EXPECT_EQ(RC, ORC);
3007 EXPECT_EQ(RC, CG.lookupRefSCC(*G1N));
3008 EXPECT_EQ(RC, CG.lookupRefSCC(*G2N));
3009 EXPECT_EQ(RC, CG.lookupRefSCC(FN));
3010 EXPECT_EQ(RC, CG.lookupRefSCC(F2N));
3011 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
3012 }
3013 }
LLVM monorepo