?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Fix test failures introduced by PR #113697 (#116941)
[llvm-project.git] / llvm / unittests / Analysis / LazyCallGraphTest.cpp
blob6ca233a50f31fb9eab59f52572022c5fe2e9adf4
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(ErrMsg.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.removeInternalRefEdges({{&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.markDeadFunction(D2F);
1190 CG.removeDeadFunctions({&D2F});
1191
1192 // Check that the graph still looks the same.
1193 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
1194 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
1195 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
1196 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
1197 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
1198 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
1199 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
1200 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
1201 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
1202 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
1203 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
1204 EXPECT_TRUE(CRC.isParentOf(NewDRC));
1205
1206 // Verify the post-order walk hasn't changed.
1207 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1208 ASSERT_NE(I, E);
1209 EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;
1210 ASSERT_NE(++I, E);
1211 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
1212 ASSERT_NE(++I, E);
1213 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
1214 ASSERT_NE(++I, E);
1215 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1216 EXPECT_EQ(++I, E);
1217 }
1218
1219 TEST(LazyCallGraphTest, InternalEdgeMutation) {
1220 LLVMContext Context;
1221 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
1222 "entry:\n"
1223 " call void @b()\n"
1224 " ret void\n"
1225 "}\n"
1226 "define void @b() {\n"
1227 "entry:\n"
1228 " call void @c()\n"
1229 " ret void\n"
1230 "}\n"
1231 "define void @c() {\n"
1232 "entry:\n"
1233 " call void @a()\n"
1234 " ret void\n"
1235 "}\n");
1236 LazyCallGraph CG = buildCG(*M);
1237
1238 // Force the graph to be fully expanded.
1239 CG.buildRefSCCs();
1240 auto I = CG.postorder_ref_scc_begin();
1241 LazyCallGraph::RefSCC &RC = *I++;
1242 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1243
1244 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1245 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1246 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1247 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1248 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1249 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1250 EXPECT_EQ(1, RC.size());
1251 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
1252 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
1253 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
1254
1255 // Insert an edge from 'a' to 'c'. Nothing changes about the graph.
1256 RC.insertInternalRefEdge(A, C);
1257 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
1258 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1259 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1260 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1261 EXPECT_EQ(1, RC.size());
1262 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
1263 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
1264 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
1265
1266 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the
1267 // call cycle and cause us to form more SCCs. The RefSCC will remain the same
1268 // though.
1269 auto NewCs = RC.switchInternalEdgeToRef(B, C);
1270 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1271 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1272 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1273 auto J = RC.begin();
1274 // The SCCs must be in *post-order* which means successors before
1275 // predecessors. At this point we have call edges from C to A and from A to
1276 // B. The only valid postorder is B, A, C.
1277 EXPECT_EQ(&*J++, CG.lookupSCC(B));
1278 EXPECT_EQ(&*J++, CG.lookupSCC(A));
1279 EXPECT_EQ(&*J++, CG.lookupSCC(C));
1280 EXPECT_EQ(RC.end(), J);
1281 // And the returned range must be the slice of this sequence containing new
1282 // SCCs.
1283 EXPECT_EQ(RC.begin(), NewCs.begin());
1284 EXPECT_EQ(std::prev(RC.end()), NewCs.end());
1285
1286 // Test turning the ref edge from A to C into a call edge. This will form an
1287 // SCC out of A and C. Since we previously had a call edge from C to A, the
1288 // C SCC should be preserved and have A merged into it while the A SCC should
1289 // be invalidated.
1290 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1291 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1292 EXPECT_TRUE(RC.switchInternalEdgeToCall(A, C, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1293 ASSERT_EQ(1u, MergedCs.size());
1294 EXPECT_EQ(&AC, MergedCs[0]);
1295 }));
1296 EXPECT_EQ(2, CC.size());
1297 EXPECT_EQ(&CC, CG.lookupSCC(A));
1298 EXPECT_EQ(&CC, CG.lookupSCC(C));
1299 J = RC.begin();
1300 EXPECT_EQ(&*J++, CG.lookupSCC(B));
1301 EXPECT_EQ(&*J++, CG.lookupSCC(C));
1302 EXPECT_EQ(RC.end(), J);
1303 }
1304
1305 TEST(LazyCallGraphTest, InternalEdgeRemoval) {
1306 LLVMContext Context;
1307 // A nice fully connected (including self-edges) RefSCC.
1308 std::unique_ptr<Module> M = parseAssembly(
1309 Context, "define void @a(i8** %ptr) {\n"
1310 "entry:\n"
1311 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1312 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1313 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1314 " ret void\n"
1315 "}\n"
1316 "define void @b(i8** %ptr) {\n"
1317 "entry:\n"
1318 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1319 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1320 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1321 " ret void\n"
1322 "}\n"
1323 "define void @c(i8** %ptr) {\n"
1324 "entry:\n"
1325 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1326 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1327 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1328 " ret void\n"
1329 "}\n");
1330 LazyCallGraph CG = buildCG(*M);
1331
1332 // Force the graph to be fully expanded.
1333 CG.buildRefSCCs();
1334 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1335 LazyCallGraph::RefSCC &RC = *I;
1336 EXPECT_EQ(E, std::next(I));
1337
1338 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1339 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1340 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1341 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1342 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1343 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1344
1345 // Remove the edge from b -> a, which should leave the 3 functions still in
1346 // a single connected component because of a -> b -> c -> a.
1347 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1348 RC.removeInternalRefEdges({{&B, &A}});
1349 EXPECT_EQ(0u, NewRCs.size());
1350 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1351 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1352 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1353 auto J = CG.postorder_ref_scc_begin();
1354 EXPECT_EQ(I, J);
1355 EXPECT_EQ(&RC, &*J);
1356 EXPECT_EQ(E, std::next(J));
1357
1358 // Increment I before we actually mutate the structure so that it remains
1359 // a valid iterator.
1360 ++I;
1361
1362 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC
1363 // and form a new RefSCC for 'b' and 'c'.
1364 NewRCs = RC.removeInternalRefEdges({{&C, &A}});
1365 ASSERT_EQ(2u, NewRCs.size());
1366 LazyCallGraph::RefSCC &BCRC = *NewRCs[0];
1367 LazyCallGraph::RefSCC &ARC = *NewRCs[1];
1368 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
1369 EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end()));
1370 EXPECT_EQ(&BCRC, CG.lookupRefSCC(B));
1371 EXPECT_EQ(&BCRC, CG.lookupRefSCC(C));
1372 J = CG.postorder_ref_scc_begin();
1373 EXPECT_NE(I, J);
1374 EXPECT_EQ(&BCRC, &*J);
1375 ++J;
1376 EXPECT_NE(I, J);
1377 EXPECT_EQ(&ARC, &*J);
1378 ++J;
1379 EXPECT_EQ(I, J);
1380 EXPECT_EQ(E, J);
1381 }
1382
1383 TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) {
1384 LLVMContext Context;
1385 // A nice fully connected (including self-edges) RefSCC.
1386 std::unique_ptr<Module> M = parseAssembly(
1387 Context, "define void @a(i8** %ptr) {\n"
1388 "entry:\n"
1389 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1390 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1391 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1392 " ret void\n"
1393 "}\n"
1394 "define void @b(i8** %ptr) {\n"
1395 "entry:\n"
1396 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1397 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1398 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1399 " ret void\n"
1400 "}\n"
1401 "define void @c(i8** %ptr) {\n"
1402 "entry:\n"
1403 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1404 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1405 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1406 " ret void\n"
1407 "}\n");
1408 LazyCallGraph CG = buildCG(*M);
1409
1410 // Force the graph to be fully expanded.
1411 CG.buildRefSCCs();
1412 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1413 LazyCallGraph::RefSCC &RC = *I;
1414 EXPECT_EQ(E, std::next(I));
1415
1416 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1417 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1418 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1419 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1420 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1421 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1422
1423 // Increment I before we actually mutate the structure so that it remains
1424 // a valid iterator.
1425 ++I;
1426
1427 // Remove the edges from b -> a and b -> c, leaving b in its own RefSCC.
1428 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1429 RC.removeInternalRefEdges({{&B, &A}, {&B, &C}});
1430
1431 ASSERT_EQ(2u, NewRCs.size());
1432 LazyCallGraph::RefSCC &BRC = *NewRCs[0];
1433 LazyCallGraph::RefSCC &ACRC = *NewRCs[1];
1434 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
1435 EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end()));
1436 EXPECT_EQ(&ACRC, CG.lookupRefSCC(A));
1437 EXPECT_EQ(&ACRC, CG.lookupRefSCC(C));
1438 auto J = CG.postorder_ref_scc_begin();
1439 EXPECT_NE(I, J);
1440 EXPECT_EQ(&BRC, &*J);
1441 ++J;
1442 EXPECT_NE(I, J);
1443 EXPECT_EQ(&ACRC, &*J);
1444 ++J;
1445 EXPECT_EQ(I, J);
1446 EXPECT_EQ(E, J);
1447 }
1448
1449 TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) {
1450 LLVMContext Context;
1451 // A graph with a single cycle formed both from call and reference edges
1452 // which makes the reference edges trivial to delete. The graph looks like:
1453 //
1454 // Reference edges: a -> b -> c -> a
1455 // Call edges: a -> c -> b -> a
1456 std::unique_ptr<Module> M = parseAssembly(
1457 Context, "define void @a(i8** %ptr) {\n"
1458 "entry:\n"
1459 " call void @b(i8** %ptr)\n"
1460 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1461 " ret void\n"
1462 "}\n"
1463 "define void @b(i8** %ptr) {\n"
1464 "entry:\n"
1465 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1466 " call void @c(i8** %ptr)\n"
1467 " ret void\n"
1468 "}\n"
1469 "define void @c(i8** %ptr) {\n"
1470 "entry:\n"
1471 " call void @a(i8** %ptr)\n"
1472 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1473 " ret void\n"
1474 "}\n");
1475 LazyCallGraph CG = buildCG(*M);
1476
1477 // Force the graph to be fully expanded.
1478 CG.buildRefSCCs();
1479 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1480 LazyCallGraph::RefSCC &RC = *I;
1481 EXPECT_EQ(E, std::next(I));
1482
1483 LazyCallGraph::SCC &C = *RC.begin();
1484 EXPECT_EQ(RC.end(), std::next(RC.begin()));
1485
1486 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
1487 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
1488 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
1489 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1490 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1491 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1492 EXPECT_EQ(&C, CG.lookupSCC(AN));
1493 EXPECT_EQ(&C, CG.lookupSCC(BN));
1494 EXPECT_EQ(&C, CG.lookupSCC(CN));
1495
1496 // Remove the edge from a -> c which doesn't change anything.
1497 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1498 RC.removeInternalRefEdges({{&AN, &CN}});
1499 EXPECT_EQ(0u, NewRCs.size());
1500 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1501 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1502 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1503 EXPECT_EQ(&C, CG.lookupSCC(AN));
1504 EXPECT_EQ(&C, CG.lookupSCC(BN));
1505 EXPECT_EQ(&C, CG.lookupSCC(CN));
1506 auto J = CG.postorder_ref_scc_begin();
1507 EXPECT_EQ(I, J);
1508 EXPECT_EQ(&RC, &*J);
1509 EXPECT_EQ(E, std::next(J));
1510
1511 // Remove the edge from b -> a and c -> b; again this doesn't change
1512 // anything.
1513 NewRCs = RC.removeInternalRefEdges({{&BN, &AN}});
1514 NewRCs = RC.removeInternalRefEdges({{&CN, &BN}});
1515 EXPECT_EQ(0u, NewRCs.size());
1516 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1517 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1518 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1519 EXPECT_EQ(&C, CG.lookupSCC(AN));
1520 EXPECT_EQ(&C, CG.lookupSCC(BN));
1521 EXPECT_EQ(&C, CG.lookupSCC(CN));
1522 J = CG.postorder_ref_scc_begin();
1523 EXPECT_EQ(I, J);
1524 EXPECT_EQ(&RC, &*J);
1525 EXPECT_EQ(E, std::next(J));
1526 }
1527
1528 TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
1529 LLVMContext Context;
1530 // A nice fully connected (including self-edges) SCC (and RefSCC)
1531 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
1532 "entry:\n"
1533 " call void @a()\n"
1534 " call void @b()\n"
1535 " call void @c()\n"
1536 " ret void\n"
1537 "}\n"
1538 "define void @b() {\n"
1539 "entry:\n"
1540 " call void @a()\n"
1541 " call void @b()\n"
1542 " call void @c()\n"
1543 " ret void\n"
1544 "}\n"
1545 "define void @c() {\n"
1546 "entry:\n"
1547 " call void @a()\n"
1548 " call void @b()\n"
1549 " call void @c()\n"
1550 " ret void\n"
1551 "}\n");
1552 LazyCallGraph CG = buildCG(*M);
1553
1554 // Force the graph to be fully expanded.
1555 CG.buildRefSCCs();
1556 auto I = CG.postorder_ref_scc_begin();
1557 LazyCallGraph::RefSCC &RC = *I++;
1558 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1559
1560 EXPECT_EQ(1, RC.size());
1561 LazyCallGraph::SCC &AC = *RC.begin();
1562
1563 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
1564 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
1565 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
1566 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1567 EXPECT_EQ(&AC, CG.lookupSCC(BN));
1568 EXPECT_EQ(&AC, CG.lookupSCC(CN));
1569
1570 // Remove the call edge from b -> a to a ref edge, which should leave the
1571 // 3 functions still in a single connected component because of a -> b ->
1572 // c -> a.
1573 auto NewCs = RC.switchInternalEdgeToRef(BN, AN);
1574 EXPECT_EQ(NewCs.begin(), NewCs.end());
1575 EXPECT_EQ(1, RC.size());
1576 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1577 EXPECT_EQ(&AC, CG.lookupSCC(BN));
1578 EXPECT_EQ(&AC, CG.lookupSCC(CN));
1579
1580 // Remove the edge from c -> a, which should leave 'a' in the original SCC
1581 // and form a new SCC for 'b' and 'c'.
1582 NewCs = RC.switchInternalEdgeToRef(CN, AN);
1583 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
1584 EXPECT_EQ(2, RC.size());
1585 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1586 LazyCallGraph::SCC &BC = *CG.lookupSCC(BN);
1587 EXPECT_NE(&BC, &AC);
1588 EXPECT_EQ(&BC, CG.lookupSCC(CN));
1589 auto J = RC.find(AC);
1590 EXPECT_EQ(&AC, &*J);
1591 --J;
1592 EXPECT_EQ(&BC, &*J);
1593 EXPECT_EQ(RC.begin(), J);
1594 EXPECT_EQ(J, NewCs.begin());
1595
1596 // Remove the edge from c -> b, which should leave 'b' in the original SCC
1597 // and form a new SCC for 'c'. It shouldn't change 'a's SCC.
1598 NewCs = RC.switchInternalEdgeToRef(CN, BN);
1599 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
1600 EXPECT_EQ(3, RC.size());
1601 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1602 EXPECT_EQ(&BC, CG.lookupSCC(BN));
1603 LazyCallGraph::SCC &CC = *CG.lookupSCC(CN);
1604 EXPECT_NE(&CC, &AC);
1605 EXPECT_NE(&CC, &BC);
1606 J = RC.find(AC);
1607 EXPECT_EQ(&AC, &*J);
1608 --J;
1609 EXPECT_EQ(&BC, &*J);
1610 --J;
1611 EXPECT_EQ(&CC, &*J);
1612 EXPECT_EQ(RC.begin(), J);
1613 EXPECT_EQ(J, NewCs.begin());
1614 }
1615
1616 TEST(LazyCallGraphTest, InternalRefEdgeToCall) {
1617 LLVMContext Context;
1618 // Basic tests for making a ref edge a call. This hits the basics of the
1619 // process only.
1620 std::unique_ptr<Module> M =
1621 parseAssembly(Context, "define void @a() {\n"
1622 "entry:\n"
1623 " call void @b()\n"
1624 " call void @c()\n"
1625 " store void()* @d, void()** undef\n"
1626 " ret void\n"
1627 "}\n"
1628 "define void @b() {\n"
1629 "entry:\n"
1630 " store void()* @c, void()** undef\n"
1631 " call void @d()\n"
1632 " ret void\n"
1633 "}\n"
1634 "define void @c() {\n"
1635 "entry:\n"
1636 " store void()* @b, void()** undef\n"
1637 " call void @d()\n"
1638 " ret void\n"
1639 "}\n"
1640 "define void @d() {\n"
1641 "entry:\n"
1642 " store void()* @a, void()** undef\n"
1643 " ret void\n"
1644 "}\n");
1645 LazyCallGraph CG = buildCG(*M);
1646
1647 // Force the graph to be fully expanded.
1648 CG.buildRefSCCs();
1649 auto I = CG.postorder_ref_scc_begin();
1650 LazyCallGraph::RefSCC &RC = *I++;
1651 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1652
1653 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1654 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1655 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1656 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1657 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1658 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
1659 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1660 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1661
1662 // Check the initial post-order. Note that B and C could be flipped here (and
1663 // in our mutation) without changing the nature of this test.
1664 ASSERT_EQ(4, RC.size());
1665 EXPECT_EQ(&DC, &RC[0]);
1666 EXPECT_EQ(&BC, &RC[1]);
1667 EXPECT_EQ(&CC, &RC[2]);
1668 EXPECT_EQ(&AC, &RC[3]);
1669
1670 // Switch the ref edge from A -> D to a call edge. This should have no
1671 // effect as it is already in postorder and no new cycles are formed.
1672 EXPECT_FALSE(RC.switchInternalEdgeToCall(A, D));
1673 ASSERT_EQ(4, RC.size());
1674 EXPECT_EQ(&DC, &RC[0]);
1675 EXPECT_EQ(&BC, &RC[1]);
1676 EXPECT_EQ(&CC, &RC[2]);
1677 EXPECT_EQ(&AC, &RC[3]);
1678
1679 // Switch B -> C to a call edge. This doesn't form any new cycles but does
1680 // require reordering the SCCs.
1681 EXPECT_FALSE(RC.switchInternalEdgeToCall(B, C));
1682 ASSERT_EQ(4, RC.size());
1683 EXPECT_EQ(&DC, &RC[0]);
1684 EXPECT_EQ(&CC, &RC[1]);
1685 EXPECT_EQ(&BC, &RC[2]);
1686 EXPECT_EQ(&AC, &RC[3]);
1687
1688 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs.
1689 EXPECT_TRUE(RC.switchInternalEdgeToCall(C, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1690 ASSERT_EQ(1u, MergedCs.size());
1691 EXPECT_EQ(&CC, MergedCs[0]);
1692 }));
1693 ASSERT_EQ(3, RC.size());
1694 EXPECT_EQ(&DC, &RC[0]);
1695 EXPECT_EQ(&BC, &RC[1]);
1696 EXPECT_EQ(&AC, &RC[2]);
1697 EXPECT_EQ(2, BC.size());
1698 EXPECT_EQ(&BC, CG.lookupSCC(B));
1699 EXPECT_EQ(&BC, CG.lookupSCC(C));
1700 }
1701
1702 TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) {
1703 LLVMContext Context;
1704 // Test for having a post-order prior to changing a ref edge to a call edge
1705 // with SCCs connecting to the source and connecting to the target, but not
1706 // connecting to both, interleaved between the source and target. This
1707 // ensures we correctly partition the range rather than simply moving one or
1708 // the other.
1709 std::unique_ptr<Module> M =
1710 parseAssembly(Context, "define void @a() {\n"
1711 "entry:\n"
1712 " call void @b1()\n"
1713 " call void @c1()\n"
1714 " ret void\n"
1715 "}\n"
1716 "define void @b1() {\n"
1717 "entry:\n"
1718 " call void @c1()\n"
1719 " call void @b2()\n"
1720 " ret void\n"
1721 "}\n"
1722 "define void @c1() {\n"
1723 "entry:\n"
1724 " call void @b2()\n"
1725 " call void @c2()\n"
1726 " ret void\n"
1727 "}\n"
1728 "define void @b2() {\n"
1729 "entry:\n"
1730 " call void @c2()\n"
1731 " call void @b3()\n"
1732 " ret void\n"
1733 "}\n"
1734 "define void @c2() {\n"
1735 "entry:\n"
1736 " call void @b3()\n"
1737 " call void @c3()\n"
1738 " ret void\n"
1739 "}\n"
1740 "define void @b3() {\n"
1741 "entry:\n"
1742 " call void @c3()\n"
1743 " call void @d()\n"
1744 " ret void\n"
1745 "}\n"
1746 "define void @c3() {\n"
1747 "entry:\n"
1748 " store void()* @b1, void()** undef\n"
1749 " call void @d()\n"
1750 " ret void\n"
1751 "}\n"
1752 "define void @d() {\n"
1753 "entry:\n"
1754 " store void()* @a, void()** undef\n"
1755 " ret void\n"
1756 "}\n");
1757 LazyCallGraph CG = buildCG(*M);
1758
1759 // Force the graph to be fully expanded.
1760 CG.buildRefSCCs();
1761 auto I = CG.postorder_ref_scc_begin();
1762 LazyCallGraph::RefSCC &RC = *I++;
1763 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1764
1765 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1766 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
1767 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
1768 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
1769 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
1770 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
1771 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
1772 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1773 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1774 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1);
1775 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2);
1776 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3);
1777 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1);
1778 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2);
1779 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3);
1780 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1781
1782 // Several call edges are initially present to force a particual post-order.
1783 // Remove them now, leaving an interleaved post-order pattern.
1784 RC.switchTrivialInternalEdgeToRef(B3, C3);
1785 RC.switchTrivialInternalEdgeToRef(C2, B3);
1786 RC.switchTrivialInternalEdgeToRef(B2, C2);
1787 RC.switchTrivialInternalEdgeToRef(C1, B2);
1788 RC.switchTrivialInternalEdgeToRef(B1, C1);
1789
1790 // Check the initial post-order. We ensure this order with the extra edges
1791 // that are nuked above.
1792 ASSERT_EQ(8, RC.size());
1793 EXPECT_EQ(&DC, &RC[0]);
1794 EXPECT_EQ(&C3C, &RC[1]);
1795 EXPECT_EQ(&B3C, &RC[2]);
1796 EXPECT_EQ(&C2C, &RC[3]);
1797 EXPECT_EQ(&B2C, &RC[4]);
1798 EXPECT_EQ(&C1C, &RC[5]);
1799 EXPECT_EQ(&B1C, &RC[6]);
1800 EXPECT_EQ(&AC, &RC[7]);
1801
1802 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does
1803 // require reordering the SCCs in the face of tricky internal node
1804 // structures.
1805 EXPECT_FALSE(RC.switchInternalEdgeToCall(C3, B1));
1806 ASSERT_EQ(8, RC.size());
1807 EXPECT_EQ(&DC, &RC[0]);
1808 EXPECT_EQ(&B3C, &RC[1]);
1809 EXPECT_EQ(&B2C, &RC[2]);
1810 EXPECT_EQ(&B1C, &RC[3]);
1811 EXPECT_EQ(&C3C, &RC[4]);
1812 EXPECT_EQ(&C2C, &RC[5]);
1813 EXPECT_EQ(&C1C, &RC[6]);
1814 EXPECT_EQ(&AC, &RC[7]);
1815 }
1816
1817 TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {
1818 LLVMContext Context;
1819 // Test for having a postorder where between the source and target are all
1820 // three kinds of other SCCs:
1821 // 1) One connected to the target only that have to be shifted below the
1822 // source.
1823 // 2) One connected to the source only that have to be shifted below the
1824 // target.
1825 // 3) One connected to both source and target that has to remain and get
1826 // merged away.
1827 //
1828 // To achieve this we construct a heavily connected graph to force
1829 // a particular post-order. Then we remove the forcing edges and connect
1830 // a cycle.
1831 //
1832 // Diagram for the graph we want on the left and the graph we use to force
1833 // the ordering on the right. Edges point down or right.
1834 //
1835 // A | A |
1836 // / \ | / \ |
1837 // B E | B \ |
1838 // |\ | | |\ | |
1839 // | D | | C-D-E |
1840 // | \| | | \| |
1841 // C F | \ F |
1842 // \ / | \ / |
1843 // G | G |
1844 //
1845 // And we form a cycle by connecting F to B.
1846 std::unique_ptr<Module> M =
1847 parseAssembly(Context, "define void @a() {\n"
1848 "entry:\n"
1849 " call void @b()\n"
1850 " call void @e()\n"
1851 " ret void\n"
1852 "}\n"
1853 "define void @b() {\n"
1854 "entry:\n"
1855 " call void @c()\n"
1856 " call void @d()\n"
1857 " ret void\n"
1858 "}\n"
1859 "define void @c() {\n"
1860 "entry:\n"
1861 " call void @d()\n"
1862 " call void @g()\n"
1863 " ret void\n"
1864 "}\n"
1865 "define void @d() {\n"
1866 "entry:\n"
1867 " call void @e()\n"
1868 " call void @f()\n"
1869 " ret void\n"
1870 "}\n"
1871 "define void @e() {\n"
1872 "entry:\n"
1873 " call void @f()\n"
1874 " ret void\n"
1875 "}\n"
1876 "define void @f() {\n"
1877 "entry:\n"
1878 " store void()* @b, void()** undef\n"
1879 " call void @g()\n"
1880 " ret void\n"
1881 "}\n"
1882 "define void @g() {\n"
1883 "entry:\n"
1884 " store void()* @a, void()** undef\n"
1885 " ret void\n"
1886 "}\n");
1887 LazyCallGraph CG = buildCG(*M);
1888
1889 // Force the graph to be fully expanded.
1890 CG.buildRefSCCs();
1891 auto I = CG.postorder_ref_scc_begin();
1892 LazyCallGraph::RefSCC &RC = *I++;
1893 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1894
1895 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1896 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1897 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1898 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1899 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));
1900 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
1901 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
1902 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1903 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
1904 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1905 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1906 LazyCallGraph::SCC &EC = *CG.lookupSCC(E);
1907 LazyCallGraph::SCC &FC = *CG.lookupSCC(F);
1908 LazyCallGraph::SCC &GC = *CG.lookupSCC(G);
1909
1910 // Remove the extra edges that were used to force a particular post-order.
1911 RC.switchTrivialInternalEdgeToRef(C, D);
1912 RC.switchTrivialInternalEdgeToRef(D, E);
1913
1914 // Check the initial post-order. We ensure this order with the extra edges
1915 // that are nuked above.
1916 ASSERT_EQ(7, RC.size());
1917 EXPECT_EQ(&GC, &RC[0]);
1918 EXPECT_EQ(&FC, &RC[1]);
1919 EXPECT_EQ(&EC, &RC[2]);
1920 EXPECT_EQ(&DC, &RC[3]);
1921 EXPECT_EQ(&CC, &RC[4]);
1922 EXPECT_EQ(&BC, &RC[5]);
1923 EXPECT_EQ(&AC, &RC[6]);
1924
1925 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC,
1926 // and has to place the C and E SCCs on either side of it:
1927 // A A |
1928 // / \ / \ |
1929 // B E | E |
1930 // |\ | \ / |
1931 // | D | -> B |
1932 // | \| / \ |
1933 // C F C | |
1934 // \ / \ / |
1935 // G G |
1936 EXPECT_TRUE(RC.switchInternalEdgeToCall(
1937 F, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1938 ASSERT_EQ(2u, MergedCs.size());
1939 EXPECT_EQ(&FC, MergedCs[0]);
1940 EXPECT_EQ(&DC, MergedCs[1]);
1941 }));
1942 EXPECT_EQ(3, BC.size());
1943
1944 // And make sure the postorder was updated.
1945 ASSERT_EQ(5, RC.size());
1946 EXPECT_EQ(&GC, &RC[0]);
1947 EXPECT_EQ(&CC, &RC[1]);
1948 EXPECT_EQ(&BC, &RC[2]);
1949 EXPECT_EQ(&EC, &RC[3]);
1950 EXPECT_EQ(&AC, &RC[4]);
1951 }
1952
1953 // Test for IR containing constants using blockaddress constant expressions.
1954 // These are truly unique constructs: constant expressions with non-constant
1955 // operands.
1956 TEST(LazyCallGraphTest, HandleBlockAddress) {
1957 LLVMContext Context;
1958 std::unique_ptr<Module> M =
1959 parseAssembly(Context, "define void @f() {\n"
1960 "entry:\n"
1961 " ret void\n"
1962 "bb:\n"
1963 " unreachable\n"
1964 "}\n"
1965 "define void @g(i8** %ptr) {\n"
1966 "entry:\n"
1967 " store i8* blockaddress(@f, %bb), i8** %ptr\n"
1968 " ret void\n"
1969 "}\n");
1970 LazyCallGraph CG = buildCG(*M);
1971
1972 CG.buildRefSCCs();
1973 auto I = CG.postorder_ref_scc_begin();
1974 LazyCallGraph::RefSCC &FRC = *I++;
1975 LazyCallGraph::RefSCC &GRC = *I++;
1976 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1977
1978 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
1979 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
1980 EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
1981 EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
1982 EXPECT_FALSE(GRC.isParentOf(FRC));
1983 EXPECT_FALSE(FRC.isParentOf(GRC));
1984 }
1985
1986 // Test that a blockaddress that refers to itself creates no new RefSCC
1987 // connections. https://bugs.llvm.org/show_bug.cgi?id=40722
1988 TEST(LazyCallGraphTest, HandleBlockAddress2) {
1989 LLVMContext Context;
1990 std::unique_ptr<Module> M =
1991 parseAssembly(Context, "define void @f() {\n"
1992 " ret void\n"
1993 "}\n"
1994 "define void @g(i8** %ptr) {\n"
1995 "bb:\n"
1996 " store i8* blockaddress(@g, %bb), i8** %ptr\n"
1997 " ret void\n"
1998 "}\n");
1999 LazyCallGraph CG = buildCG(*M);
2000
2001 CG.buildRefSCCs();
2002 auto I = CG.postorder_ref_scc_begin();
2003 LazyCallGraph::RefSCC &FRC = *I++;
2004 LazyCallGraph::RefSCC &GRC = *I++;
2005 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2006
2007 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
2008 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
2009 EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
2010 EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
2011 EXPECT_FALSE(GRC.isParentOf(FRC));
2012 EXPECT_FALSE(FRC.isParentOf(GRC));
2013 }
2014
2015 TEST(LazyCallGraphTest, ReplaceNodeFunction) {
2016 LLVMContext Context;
2017 // A graph with several different kinds of edges pointing at a particular
2018 // function.
2019 std::unique_ptr<Module> M =
2020 parseAssembly(Context,
2021 "define void @a(i8** %ptr) {\n"
2022 "entry:\n"
2023 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2024 " ret void\n"
2025 "}\n"
2026 "define void @b(i8** %ptr) {\n"
2027 "entry:\n"
2028 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2029 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2030 " call void @d(i8** %ptr)"
2031 " ret void\n"
2032 "}\n"
2033 "define void @c(i8** %ptr) {\n"
2034 "entry:\n"
2035 " call void @d(i8** %ptr)"
2036 " call void @d(i8** %ptr)"
2037 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2038 " ret void\n"
2039 "}\n"
2040 "define void @d(i8** %ptr) {\n"
2041 "entry:\n"
2042 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
2043 " call void @c(i8** %ptr)"
2044 " call void @d(i8** %ptr)"
2045 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2046 " ret void\n"
2047 "}\n");
2048 LazyCallGraph CG = buildCG(*M);
2049
2050 // Force the graph to be fully expanded.
2051 CG.buildRefSCCs();
2052 auto I = CG.postorder_ref_scc_begin();
2053 LazyCallGraph::RefSCC &RC1 = *I++;
2054 LazyCallGraph::RefSCC &RC2 = *I++;
2055 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2056
2057 ASSERT_EQ(2, RC1.size());
2058 LazyCallGraph::SCC &C1 = RC1[0];
2059 LazyCallGraph::SCC &C2 = RC1[1];
2060
2061 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
2062 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
2063 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
2064 LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d"));
2065 EXPECT_EQ(&C1, CG.lookupSCC(DN));
2066 EXPECT_EQ(&C1, CG.lookupSCC(CN));
2067 EXPECT_EQ(&C2, CG.lookupSCC(BN));
2068 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
2069 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
2070 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
2071 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
2072
2073 // Now we need to build a new function 'e' with the same signature as 'd'.
2074 Function &D = DN.getFunction();
2075 Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e");
2076 D.getParent()->getFunctionList().insert(D.getIterator(), &E);
2077
2078 // Change each use of 'd' to use 'e'. This is particularly easy as they have
2079 // the same type.
2080 D.replaceAllUsesWith(&E);
2081
2082 // Splice the body of the old function into the new one.
2083 E.splice(E.begin(), &D);
2084 // And fix up the one argument.
2085 D.arg_begin()->replaceAllUsesWith(&*E.arg_begin());
2086 E.arg_begin()->takeName(&*D.arg_begin());
2087
2088 // Now replace the function in the graph.
2089 RC1.replaceNodeFunction(DN, E);
2090
2091 EXPECT_EQ(&E, &DN.getFunction());
2092 EXPECT_EQ(&DN, &(*CN)[DN].getNode());
2093 EXPECT_EQ(&DN, &(*BN)[DN].getNode());
2094 }
2095
2096 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRef) {
2097 LLVMContext Context;
2098 // A graph with a couple of RefSCCs.
2099 std::unique_ptr<Module> M =
2100 parseAssembly(Context,
2101 "define void @a(i8** %ptr) {\n"
2102 "entry:\n"
2103 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2104 " ret void\n"
2105 "}\n"
2106 "define void @b(i8** %ptr) {\n"
2107 "entry:\n"
2108 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
2109 " ret void\n"
2110 "}\n"
2111 "define void @c(i8** %ptr) {\n"
2112 "entry:\n"
2113 " call void @d(i8** %ptr)"
2114 " ret void\n"
2115 "}\n"
2116 "define void @d(i8** %ptr) {\n"
2117 "entry:\n"
2118 " call void @c(i8** %ptr)"
2119 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
2120 " ret void\n"
2121 "}\n"
2122 "define void @dead() {\n"
2123 "entry:\n"
2124 " ret void\n"
2125 "}\n");
2126 LazyCallGraph CG = buildCG(*M);
2127
2128 // Insert spurious ref edges.
2129 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2130 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2131 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2132 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));
2133 LazyCallGraph::Node &DeadN = CG.get(lookupFunction(*M, "dead"));
2134 AN.populate();
2135 BN.populate();
2136 CN.populate();
2137 DN.populate();
2138 DeadN.populate();
2139 CG.insertEdge(AN, DeadN, LazyCallGraph::Edge::Ref);
2140 CG.insertEdge(BN, DeadN, LazyCallGraph::Edge::Ref);
2141 CG.insertEdge(CN, DeadN, LazyCallGraph::Edge::Ref);
2142 CG.insertEdge(DN, DeadN, LazyCallGraph::Edge::Ref);
2143
2144 // Force the graph to be fully expanded.
2145 CG.buildRefSCCs();
2146 auto I = CG.postorder_ref_scc_begin();
2147 LazyCallGraph::RefSCC &DeadRC = *I++;
2148 LazyCallGraph::RefSCC &RC1 = *I++;
2149 LazyCallGraph::RefSCC &RC2 = *I++;
2150 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2151
2152 ASSERT_EQ(2, RC1.size());
2153 LazyCallGraph::SCC &C1 = RC1[0];
2154 LazyCallGraph::SCC &C2 = RC1[1];
2155
2156 EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN));
2157 EXPECT_EQ(&C1, CG.lookupSCC(DN));
2158 EXPECT_EQ(&C1, CG.lookupSCC(CN));
2159 EXPECT_EQ(&C2, CG.lookupSCC(BN));
2160 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
2161 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
2162 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
2163 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
2164
2165 // Now delete 'dead'. There are no uses of this function but there are
2166 // spurious references.
2167 CG.markDeadFunction(DeadN.getFunction());
2168 CG.removeDeadFunctions({&DeadN.getFunction()});
2169
2170 // The only observable change should be that the RefSCC is gone from the
2171 // postorder sequence.
2172 I = CG.postorder_ref_scc_begin();
2173 EXPECT_EQ(&RC1, &*I++);
2174 EXPECT_EQ(&RC2, &*I++);
2175 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2176 }
2177
2178 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive) {
2179 LLVMContext Context;
2180 std::unique_ptr<Module> M =
2181 parseAssembly(Context, "define void @a(ptr %p) {\n"
2182 " store ptr @b, ptr %p\n"
2183 " ret void\n"
2184 "}\n"
2185 "define void @b(ptr %p) {\n"
2186 " store ptr @c, ptr %p\n"
2187 " ret void\n"
2188 "}\n"
2189 "define void @c(ptr %p) {\n"
2190 " ret void\n"
2191 "}\n");
2192 LazyCallGraph CG = buildCG(*M);
2193
2194 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2195 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2196 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2197 AN.populate();
2198 BN.populate();
2199 CN.populate();
2200 // Insert spurious ref edge.
2201 CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref);
2202
2203 // Force the graph to be fully expanded.
2204 CG.buildRefSCCs();
2205 auto I = CG.postorder_ref_scc_begin();
2206 LazyCallGraph::RefSCC &RC = *I++;
2207 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2208
2209 ASSERT_EQ(RC.size(), 3);
2210
2211 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2212 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2213 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2214
2215 // Now delete 'a'. There are no uses of this function but there are
2216 // spurious references.
2217 CG.markDeadFunction(AN.getFunction());
2218 CG.removeDeadFunctions({&AN.getFunction()});
2219
2220 // The only observable change should be that the RefSCC is gone from the
2221 // postorder sequence.
2222 I = CG.postorder_ref_scc_begin();
2223 EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);
2224 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2225 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2226 }
2227
2228 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive2) {
2229 LLVMContext Context;
2230 std::unique_ptr<Module> M =
2231 parseAssembly(Context, "define void @a(ptr %p) {\n"
2232 " store ptr @b, ptr %p\n"
2233 " ret void\n"
2234 "}\n"
2235 "define void @b(ptr %p) {\n"
2236 " store ptr @c, ptr %p\n"
2237 " ret void\n"
2238 "}\n"
2239 "define void @c(ptr %p) {\n"
2240 " store ptr @b, ptr %p\n"
2241 " store ptr @d, ptr %p\n"
2242 " ret void\n"
2243 "}\n"
2244 "define void @d(ptr %p) {\n"
2245 " ret void\n"
2246 "}\n");
2247 LazyCallGraph CG = buildCG(*M);
2248
2249 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2250 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2251 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2252 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));
2253 AN.populate();
2254 BN.populate();
2255 CN.populate();
2256 DN.populate();
2257 // Insert spurious ref edge.
2258 CG.insertEdge(DN, AN, LazyCallGraph::Edge::Ref);
2259
2260 // Force the graph to be fully expanded.
2261 CG.buildRefSCCs();
2262 auto I = CG.postorder_ref_scc_begin();
2263 LazyCallGraph::RefSCC &RC = *I++;
2264 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2265
2266 ASSERT_EQ(4, RC.size());
2267
2268 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2269 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2270 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2271 EXPECT_EQ(&RC, CG.lookupRefSCC(DN));
2272
2273 // Now delete 'a'. There are no uses of this function but there are
2274 // spurious references.
2275 CG.markDeadFunction(AN.getFunction());
2276 CG.removeDeadFunctions({&AN.getFunction()});
2277
2278 // The only observable change should be that the RefSCC is gone from the
2279 // postorder sequence.
2280 I = CG.postorder_ref_scc_begin();
2281 EXPECT_EQ(CG.lookupRefSCC(DN), &*I++);
2282 EXPECT_EQ(CG.lookupRefSCC(CN), &*I);
2283 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2284 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2285 }
2286
2287 TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive3) {
2288 LLVMContext Context;
2289 std::unique_ptr<Module> M =
2290 parseAssembly(Context, "define void @a(ptr %p) {\n"
2291 " store ptr @b, ptr %p\n"
2292 " ret void\n"
2293 "}\n"
2294 "define void @b(ptr %p) {\n"
2295 " store ptr @c, ptr %p\n"
2296 " ret void\n"
2297 "}\n"
2298 "define void @c(ptr %p) {\n"
2299 " ret void\n"
2300 "}\n");
2301 LazyCallGraph CG = buildCG(*M);
2302
2303 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2304 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2305 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2306 AN.populate();
2307 BN.populate();
2308 CN.populate();
2309 // Insert spurious ref edges.
2310 CG.insertEdge(CN, AN, LazyCallGraph::Edge::Ref);
2311 CG.insertEdge(BN, AN, LazyCallGraph::Edge::Ref);
2312
2313 // Force the graph to be fully expanded.
2314 CG.buildRefSCCs();
2315 auto I = CG.postorder_ref_scc_begin();
2316 LazyCallGraph::RefSCC &RC = *I++;
2317 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2318
2319 ASSERT_EQ(RC.size(), 3);
2320
2321 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2322 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2323 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2324
2325 // Now delete 'a'. There are no uses of this function but there are
2326 // spurious references.
2327 CG.markDeadFunction(AN.getFunction());
2328 CG.removeDeadFunctions({&AN.getFunction()});
2329
2330 // The only observable change should be that the RefSCC is gone from the
2331 // postorder sequence.
2332 I = CG.postorder_ref_scc_begin();
2333 EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);
2334 EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2335 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2336 }
2337
2338 TEST(LazyCallGraphTest, AddSplitFunction1) {
2339 LLVMContext Context;
2340 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2341 " ret void\n"
2342 "}\n");
2343 LazyCallGraph CG = buildCG(*M);
2344
2345 Function &F = lookupFunction(*M, "f");
2346 LazyCallGraph::Node &FN = CG.get(F);
2347
2348 // Force the graph to be fully expanded.
2349 CG.buildRefSCCs();
2350 auto I = CG.postorder_ref_scc_begin();
2351 LazyCallGraph::RefSCC *ORC = &*I++;
2352 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2353
2354 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2355 F.getAddressSpace(), "g", F.getParent());
2356 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2357 (void)ReturnInst::Create(Context, GBB);
2358
2359 // Create f -call-> g.
2360 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());
2361
2362 EXPECT_FALSE(verifyModule(*M, &errs()));
2363
2364 CG.addSplitFunction(F, *G);
2365
2366 LazyCallGraph::Node *GN = CG.lookup(*G);
2367 EXPECT_TRUE(GN);
2368
2369 I = CG.postorder_ref_scc_begin();
2370 LazyCallGraph::RefSCC *RC1 = &*I++;
2371 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2372 LazyCallGraph::RefSCC *RC2 = &*I++;
2373 EXPECT_EQ(RC2, ORC);
2374 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2375 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2376 }
2377
2378 TEST(LazyCallGraphTest, AddSplitFunction2) {
2379 LLVMContext Context;
2380 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2381 " ret void\n"
2382 "}\n");
2383 LazyCallGraph CG = buildCG(*M);
2384
2385 Function &F = lookupFunction(*M, "f");
2386 LazyCallGraph::Node &FN = CG.get(F);
2387
2388 // Force the graph to be fully expanded.
2389 CG.buildRefSCCs();
2390 auto I = CG.postorder_ref_scc_begin();
2391 LazyCallGraph::RefSCC *ORC = &*I++;
2392 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2393
2394 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2395 F.getAddressSpace(), "g", F.getParent());
2396 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2397 (void)ReturnInst::Create(Context, GBB);
2398
2399 // Create f -ref-> g.
2400 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",
2401 F.getEntryBlock().begin());
2402
2403 EXPECT_FALSE(verifyModule(*M, &errs()));
2404
2405 CG.addSplitFunction(F, *G);
2406
2407 LazyCallGraph::Node *GN = CG.lookup(*G);
2408 EXPECT_TRUE(GN);
2409
2410 I = CG.postorder_ref_scc_begin();
2411 LazyCallGraph::RefSCC *RC1 = &*I++;
2412 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2413 LazyCallGraph::RefSCC *RC2 = &*I++;
2414 EXPECT_EQ(RC2, ORC);
2415 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2416 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2417 }
2418
2419 TEST(LazyCallGraphTest, AddSplitFunction3) {
2420 LLVMContext Context;
2421 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2422 " ret void\n"
2423 "}\n");
2424 LazyCallGraph CG = buildCG(*M);
2425
2426 Function &F = lookupFunction(*M, "f");
2427 LazyCallGraph::Node &FN = CG.get(F);
2428
2429 // Force the graph to be fully expanded.
2430 CG.buildRefSCCs();
2431 auto I = CG.postorder_ref_scc_begin();
2432 LazyCallGraph::RefSCC *ORC = &*I++;
2433 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2434
2435 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2436 F.getAddressSpace(), "g", F.getParent());
2437 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2438 // Create g -ref-> f.
2439 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "",
2440 GBB);
2441 (void)ReturnInst::Create(Context, GBB);
2442
2443 // Create f -call-> g.
2444 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());
2445
2446 EXPECT_FALSE(verifyModule(*M, &errs()));
2447
2448 CG.addSplitFunction(F, *G);
2449
2450 LazyCallGraph::Node *GN = CG.lookup(*G);
2451 EXPECT_TRUE(GN);
2452
2453 I = CG.postorder_ref_scc_begin();
2454 LazyCallGraph::RefSCC *RC = &*I++;
2455 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2456 EXPECT_EQ(RC, ORC);
2457 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2458
2459 EXPECT_EQ(2, RC->size());
2460 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2461 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]);
2462 }
2463
2464 TEST(LazyCallGraphTest, AddSplitFunction4) {
2465 LLVMContext Context;
2466 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2467 " ret void\n"
2468 "}\n");
2469 LazyCallGraph CG = buildCG(*M);
2470
2471 Function &F = lookupFunction(*M, "f");
2472 LazyCallGraph::Node &FN = CG.get(F);
2473
2474 // Force the graph to be fully expanded.
2475 CG.buildRefSCCs();
2476 auto I = CG.postorder_ref_scc_begin();
2477 LazyCallGraph::RefSCC *ORC = &*I++;
2478 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2479
2480 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2481 F.getAddressSpace(), "g", F.getParent());
2482 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2483 // Create g -ref-> f.
2484 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "",
2485 GBB);
2486 (void)ReturnInst::Create(Context, GBB);
2487
2488 // Create f -ref-> g.
2489 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",
2490 F.getEntryBlock().begin());
2491
2492 EXPECT_FALSE(verifyModule(*M, &errs()));
2493
2494 CG.addSplitFunction(F, *G);
2495
2496 LazyCallGraph::Node *GN = CG.lookup(*G);
2497 EXPECT_TRUE(GN);
2498
2499 I = CG.postorder_ref_scc_begin();
2500 LazyCallGraph::RefSCC *RC = &*I++;
2501 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2502 EXPECT_EQ(RC, ORC);
2503 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2504
2505 // Order doesn't matter for sibling SCCs.
2506 EXPECT_EQ(2, RC->size());
2507 EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC);
2508 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2509 }
2510
2511 TEST(LazyCallGraphTest, AddSplitFunction5) {
2512 LLVMContext Context;
2513 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2514 " ret void\n"
2515 "}\n");
2516 LazyCallGraph CG = buildCG(*M);
2517
2518 Function &F = lookupFunction(*M, "f");
2519 LazyCallGraph::Node &FN = CG.get(F);
2520
2521 // Force the graph to be fully expanded.
2522 CG.buildRefSCCs();
2523 auto I = CG.postorder_ref_scc_begin();
2524 LazyCallGraph::RefSCC *ORC = &*I++;
2525 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2526
2527 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2528 F.getAddressSpace(), "g", F.getParent());
2529 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2530 // Create g -call-> f.
2531 (void)CallInst::Create(&F, {}, "", GBB);
2532 (void)ReturnInst::Create(Context, GBB);
2533
2534 // Create f -ref-> g.
2535 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",
2536 F.getEntryBlock().begin());
2537
2538 EXPECT_FALSE(verifyModule(*M, &errs()));
2539
2540 CG.addSplitFunction(F, *G);
2541
2542 LazyCallGraph::Node *GN = CG.lookup(*G);
2543 EXPECT_TRUE(GN);
2544
2545 I = CG.postorder_ref_scc_begin();
2546 LazyCallGraph::RefSCC *RC = &*I++;
2547 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2548 EXPECT_EQ(RC, ORC);
2549 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2550
2551 EXPECT_EQ(2, RC->size());
2552 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2553 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]);
2554 }
2555
2556 TEST(LazyCallGraphTest, AddSplitFunction6) {
2557 LLVMContext Context;
2558 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2559 " ret void\n"
2560 "}\n");
2561 LazyCallGraph CG = buildCG(*M);
2562
2563 Function &F = lookupFunction(*M, "f");
2564 LazyCallGraph::Node &FN = CG.get(F);
2565
2566 // Force the graph to be fully expanded.
2567 CG.buildRefSCCs();
2568 auto I = CG.postorder_ref_scc_begin();
2569 LazyCallGraph::RefSCC *ORC = &*I++;
2570 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2571
2572 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2573 F.getAddressSpace(), "g", F.getParent());
2574 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2575 // Create g -call-> f.
2576 (void)CallInst::Create(&F, {}, "", GBB);
2577 (void)ReturnInst::Create(Context, GBB);
2578
2579 // Create f -call-> g.
2580 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());
2581
2582 EXPECT_FALSE(verifyModule(*M, &errs()));
2583
2584 CG.addSplitFunction(F, *G);
2585
2586 LazyCallGraph::Node *GN = CG.lookup(*G);
2587 EXPECT_TRUE(GN);
2588
2589 I = CG.postorder_ref_scc_begin();
2590 LazyCallGraph::RefSCC *RC = &*I++;
2591 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2592 EXPECT_EQ(RC, ORC);
2593 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2594
2595 EXPECT_EQ(1, RC->size());
2596 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2597 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2598 }
2599
2600 TEST(LazyCallGraphTest, AddSplitFunction7) {
2601 LLVMContext Context;
2602 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2603 " call void @f2()\n"
2604 " ret void\n"
2605 "}\n"
2606 "define void @f2() {\n"
2607 " call void @f()\n"
2608 " ret void\n"
2609 "}\n");
2610 LazyCallGraph CG = buildCG(*M);
2611
2612 Function &F = lookupFunction(*M, "f");
2613 LazyCallGraph::Node &FN = CG.get(F);
2614 Function &F2 = lookupFunction(*M, "f2");
2615 LazyCallGraph::Node &F2N = CG.get(F2);
2616
2617 // Force the graph to be fully expanded.
2618 CG.buildRefSCCs();
2619 auto I = CG.postorder_ref_scc_begin();
2620 LazyCallGraph::RefSCC *ORC = &*I++;
2621 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2622
2623 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2624 F.getAddressSpace(), "g", F.getParent());
2625 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2626 // Create g -call-> f2.
2627 (void)CallInst::Create(&F2, {}, "", GBB);
2628 (void)ReturnInst::Create(Context, GBB);
2629
2630 // Create f -call-> g.
2631 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());
2632
2633 EXPECT_FALSE(verifyModule(*M, &errs()));
2634
2635 CG.addSplitFunction(F, *G);
2636
2637 LazyCallGraph::Node *GN = CG.lookup(*G);
2638 EXPECT_TRUE(GN);
2639
2640 I = CG.postorder_ref_scc_begin();
2641 LazyCallGraph::RefSCC *RC = &*I++;
2642 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2643 EXPECT_EQ(RC, ORC);
2644 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2645
2646 EXPECT_EQ(1, RC->size());
2647 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2648 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]);
2649 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2650 }
2651
2652 TEST(LazyCallGraphTest, AddSplitFunction8) {
2653 LLVMContext Context;
2654 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2655 " call void @f2()\n"
2656 " ret void\n"
2657 "}\n"
2658 "define void @f2() {\n"
2659 " call void @f()\n"
2660 " ret void\n"
2661 "}\n");
2662 LazyCallGraph CG = buildCG(*M);
2663
2664 Function &F = lookupFunction(*M, "f");
2665 LazyCallGraph::Node &FN = CG.get(F);
2666 Function &F2 = lookupFunction(*M, "f2");
2667 LazyCallGraph::Node &F2N = CG.get(F2);
2668
2669 // Force the graph to be fully expanded.
2670 CG.buildRefSCCs();
2671 auto I = CG.postorder_ref_scc_begin();
2672 LazyCallGraph::RefSCC *ORC = &*I++;
2673 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2674
2675 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2676 F.getAddressSpace(), "g", F.getParent());
2677 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2678 // Create g -call-> f2.
2679 (void)CallInst::Create(&F2, {}, "", GBB);
2680 (void)ReturnInst::Create(Context, GBB);
2681
2682 // Create f -ref-> g.
2683 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",
2684 F.getEntryBlock().begin());
2685
2686 EXPECT_FALSE(verifyModule(*M, &errs()));
2687
2688 CG.addSplitFunction(F, *G);
2689
2690 LazyCallGraph::Node *GN = CG.lookup(*G);
2691 EXPECT_TRUE(GN);
2692
2693 I = CG.postorder_ref_scc_begin();
2694 LazyCallGraph::RefSCC *RC = &*I++;
2695 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2696 EXPECT_EQ(RC, ORC);
2697 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2698
2699 EXPECT_EQ(2, RC->size());
2700 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2701 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]);
2702 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]);
2703 }
2704
2705 TEST(LazyCallGraphTest, AddSplitFunction9) {
2706 LLVMContext Context;
2707 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2708 " call void @f2()\n"
2709 " ret void\n"
2710 "}\n"
2711 "define void @f2() {\n"
2712 " call void @f()\n"
2713 " ret void\n"
2714 "}\n");
2715 LazyCallGraph CG = buildCG(*M);
2716
2717 Function &F = lookupFunction(*M, "f");
2718 LazyCallGraph::Node &FN = CG.get(F);
2719 Function &F2 = lookupFunction(*M, "f2");
2720 LazyCallGraph::Node &F2N = CG.get(F2);
2721
2722 // Force the graph to be fully expanded.
2723 CG.buildRefSCCs();
2724 auto I = CG.postorder_ref_scc_begin();
2725 LazyCallGraph::RefSCC *ORC = &*I++;
2726 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2727
2728 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2729 F.getAddressSpace(), "g", F.getParent());
2730 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2731 // Create g -ref-> f2.
2732 (void)CastInst::CreatePointerCast(&F2, PointerType::getUnqual(Context), "",
2733 GBB);
2734 (void)ReturnInst::Create(Context, GBB);
2735
2736 // Create f -call-> g.
2737 (void)CallInst::Create(G, {}, "", F.getEntryBlock().begin());
2738
2739 EXPECT_FALSE(verifyModule(*M, &errs()));
2740
2741 CG.addSplitFunction(F, *G);
2742
2743 LazyCallGraph::Node *GN = CG.lookup(*G);
2744 EXPECT_TRUE(GN);
2745
2746 I = CG.postorder_ref_scc_begin();
2747 LazyCallGraph::RefSCC *RC = &*I++;
2748 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2749 EXPECT_EQ(RC, ORC);
2750 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2751
2752 EXPECT_EQ(2, RC->size());
2753 EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2754 EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]);
2755 EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[1]);
2756 }
2757
2758 TEST(LazyCallGraphTest, AddSplitFunctions1) {
2759 LLVMContext Context;
2760 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2761 " ret void\n"
2762 "}\n");
2763 LazyCallGraph CG = buildCG(*M);
2764
2765 Function &F = lookupFunction(*M, "f");
2766 LazyCallGraph::Node &FN = CG.get(F);
2767
2768 // Force the graph to be fully expanded.
2769 CG.buildRefSCCs();
2770 auto I = CG.postorder_ref_scc_begin();
2771 LazyCallGraph::RefSCC *ORC = &*I++;
2772 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2773
2774 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2775 F.getAddressSpace(), "g", F.getParent());
2776 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2777 (void)ReturnInst::Create(Context, GBB);
2778
2779 // Create f -ref-> g.
2780 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",
2781 F.getEntryBlock().begin());
2782
2783 EXPECT_FALSE(verifyModule(*M, &errs()));
2784
2785 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G}));
2786
2787 LazyCallGraph::Node *GN = CG.lookup(*G);
2788 EXPECT_TRUE(GN);
2789
2790 I = CG.postorder_ref_scc_begin();
2791 LazyCallGraph::RefSCC *RC1 = &*I++;
2792 EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2793 LazyCallGraph::RefSCC *RC2 = &*I++;
2794 EXPECT_EQ(RC2, ORC);
2795 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2796 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2797 }
2798
2799 TEST(LazyCallGraphTest, AddSplitFunctions2) {
2800 LLVMContext Context;
2801 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2802 " ret void\n"
2803 "}\n");
2804 LazyCallGraph CG = buildCG(*M);
2805
2806 Function &F = lookupFunction(*M, "f");
2807 LazyCallGraph::Node &FN = CG.get(F);
2808
2809 // Force the graph to be fully expanded.
2810 CG.buildRefSCCs();
2811 auto I = CG.postorder_ref_scc_begin();
2812 LazyCallGraph::RefSCC *ORC = &*I++;
2813 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2814
2815 auto *G = Function::Create(F.getFunctionType(), F.getLinkage(),
2816 F.getAddressSpace(), "g", F.getParent());
2817 BasicBlock *GBB = BasicBlock::Create(Context, "", G);
2818 // Create g -ref-> f.
2819 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "",
2820 GBB);
2821 (void)ReturnInst::Create(Context, GBB);
2822
2823 // Create f -ref-> g.
2824 (void)CastInst::CreatePointerCast(G, PointerType::getUnqual(Context), "",
2825 F.getEntryBlock().begin());
2826
2827 EXPECT_FALSE(verifyModule(*M, &errs()));
2828
2829 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G}));
2830
2831 LazyCallGraph::Node *GN = CG.lookup(*G);
2832 EXPECT_TRUE(GN);
2833
2834 I = CG.postorder_ref_scc_begin();
2835 LazyCallGraph::RefSCC *RC = &*I++;
2836 EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2837 EXPECT_EQ(RC, ORC);
2838 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2839
2840 // Order doesn't matter for sibling SCCs.
2841 EXPECT_EQ(2, RC->size());
2842 EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC);
2843 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2844 }
2845
2846 TEST(LazyCallGraphTest, AddSplitFunctions3) {
2847 LLVMContext Context;
2848 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2849 " ret void\n"
2850 "}\n");
2851 LazyCallGraph CG = buildCG(*M);
2852
2853 Function &F = lookupFunction(*M, "f");
2854 LazyCallGraph::Node &FN = CG.get(F);
2855
2856 // Force the graph to be fully expanded.
2857 CG.buildRefSCCs();
2858 auto I = CG.postorder_ref_scc_begin();
2859 LazyCallGraph::RefSCC *ORC = &*I++;
2860 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2861
2862 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
2863 F.getAddressSpace(), "g1", F.getParent());
2864 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
2865 F.getAddressSpace(), "g2", F.getParent());
2866 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);
2867 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);
2868 // Create g1 -ref-> g2 and g2 -ref-> g1.
2869 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",
2870 G1BB);
2871 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",
2872 G2BB);
2873 (void)ReturnInst::Create(Context, G1BB);
2874 (void)ReturnInst::Create(Context, G2BB);
2875
2876 // Create f -ref-> g1 and f -ref-> g2.
2877 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",
2878 F.getEntryBlock().begin());
2879 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",
2880 F.getEntryBlock().begin());
2881
2882 EXPECT_FALSE(verifyModule(*M, &errs()));
2883
2884 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));
2885
2886 LazyCallGraph::Node *G1N = CG.lookup(*G1);
2887 EXPECT_TRUE(G1N);
2888 LazyCallGraph::Node *G2N = CG.lookup(*G2);
2889 EXPECT_TRUE(G2N);
2890
2891 I = CG.postorder_ref_scc_begin();
2892 LazyCallGraph::RefSCC *RC1 = &*I++;
2893 EXPECT_EQ(2, RC1->size());
2894 EXPECT_EQ(RC1, CG.lookupRefSCC(*G1N));
2895 EXPECT_EQ(RC1, CG.lookupRefSCC(*G2N));
2896 LazyCallGraph::RefSCC *RC2 = &*I++;
2897 EXPECT_EQ(RC2, ORC);
2898 EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2899 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2900 }
2901
2902 TEST(LazyCallGraphTest, AddSplitFunctions4) {
2903 LLVMContext Context;
2904 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f() {\n"
2905 " ret void\n"
2906 "}\n");
2907 LazyCallGraph CG = buildCG(*M);
2908
2909 Function &F = lookupFunction(*M, "f");
2910 LazyCallGraph::Node &FN = CG.get(F);
2911
2912 // Force the graph to be fully expanded.
2913 CG.buildRefSCCs();
2914 auto I = CG.postorder_ref_scc_begin();
2915 LazyCallGraph::RefSCC *ORC = &*I++;
2916 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2917
2918 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
2919 F.getAddressSpace(), "g1", F.getParent());
2920 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
2921 F.getAddressSpace(), "g2", F.getParent());
2922 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);
2923 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);
2924 // Create g1 -ref-> g2 and g2 -ref-> g1.
2925 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",
2926 G1BB);
2927 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",
2928 G2BB);
2929 // Create g2 -ref-> f.
2930 (void)CastInst::CreatePointerCast(&F, PointerType::getUnqual(Context), "",
2931 G2BB);
2932 (void)ReturnInst::Create(Context, G1BB);
2933 (void)ReturnInst::Create(Context, G2BB);
2934
2935 // Create f -ref-> g1 and f -ref-> g2.
2936 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",
2937 F.getEntryBlock().begin());
2938 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",
2939 F.getEntryBlock().begin());
2940
2941 EXPECT_FALSE(verifyModule(*M, &errs()));
2942
2943 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));
2944
2945 LazyCallGraph::Node *G1N = CG.lookup(*G1);
2946 EXPECT_TRUE(G1N);
2947 LazyCallGraph::Node *G2N = CG.lookup(*G2);
2948 EXPECT_TRUE(G2N);
2949
2950 I = CG.postorder_ref_scc_begin();
2951 LazyCallGraph::RefSCC *RC = &*I++;
2952 EXPECT_EQ(RC, ORC);
2953 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2954
2955 // Order doesn't matter for sibling SCCs.
2956 EXPECT_EQ(3, RC->size());
2957 EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2958 EXPECT_EQ(&CG.lookupSCC(*G1N)->getOuterRefSCC(), RC);
2959 EXPECT_EQ(&CG.lookupSCC(*G2N)->getOuterRefSCC(), RC);
2960 EXPECT_EQ(RC, CG.lookupRefSCC(*G1N));
2961 EXPECT_EQ(RC, CG.lookupRefSCC(*G2N));
2962 }
2963
2964 TEST(LazyCallGraphTest, AddSplitFunctions5) {
2965 LLVMContext Context;
2966 std::unique_ptr<Module> M =
2967 parseAssembly(Context, "define void @f() {\n"
2968 " %1 = bitcast void ()* @f2 to i8*\n"
2969 " ret void\n"
2970 "}\n"
2971 "define void @f2() {\n"
2972 " call void @f()\n"
2973 " ret void\n"
2974 "}\n");
2975 LazyCallGraph CG = buildCG(*M);
2976
2977 Function &F = lookupFunction(*M, "f");
2978 LazyCallGraph::Node &FN = CG.get(F);
2979 Function &F2 = lookupFunction(*M, "f2");
2980 LazyCallGraph::Node &F2N = CG.get(F);
2981
2982 // Force the graph to be fully expanded.
2983 CG.buildRefSCCs();
2984 auto I = CG.postorder_ref_scc_begin();
2985 LazyCallGraph::RefSCC *ORC = &*I++;
2986 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2987
2988 auto *G1 = Function::Create(F.getFunctionType(), F.getLinkage(),
2989 F.getAddressSpace(), "g1", F.getParent());
2990 auto *G2 = Function::Create(F.getFunctionType(), F.getLinkage(),
2991 F.getAddressSpace(), "g2", F.getParent());
2992 BasicBlock *G1BB = BasicBlock::Create(Context, "", G1);
2993 BasicBlock *G2BB = BasicBlock::Create(Context, "", G2);
2994 // Create g1 -ref-> g2 and g2 -ref-> g1.
2995 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",
2996 G1BB);
2997 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",
2998 G2BB);
2999 // Create g2 -ref-> f2.
3000 (void)CastInst::CreatePointerCast(&F2, PointerType::getUnqual(Context), "",
3001 G2BB);
3002 (void)ReturnInst::Create(Context, G1BB);
3003 (void)ReturnInst::Create(Context, G2BB);
3004
3005 // Create f -ref-> g1 and f -ref-> g2.
3006 (void)CastInst::CreatePointerCast(G1, PointerType::getUnqual(Context), "",
3007 F.getEntryBlock().begin());
3008 (void)CastInst::CreatePointerCast(G2, PointerType::getUnqual(Context), "",
3009 F.getEntryBlock().begin());
3010
3011 EXPECT_FALSE(verifyModule(*M, &errs()));
3012
3013 CG.addSplitRefRecursiveFunctions(F, SmallVector<Function *, 1>({G1, G2}));
3014
3015 LazyCallGraph::Node *G1N = CG.lookup(*G1);
3016 EXPECT_TRUE(G1N);
3017 LazyCallGraph::Node *G2N = CG.lookup(*G2);
3018 EXPECT_TRUE(G2N);
3019
3020 I = CG.postorder_ref_scc_begin();
3021 LazyCallGraph::RefSCC *RC = &*I++;
3022 EXPECT_EQ(4, RC->size());
3023 EXPECT_EQ(RC, ORC);
3024 EXPECT_EQ(RC, CG.lookupRefSCC(*G1N));
3025 EXPECT_EQ(RC, CG.lookupRefSCC(*G2N));
3026 EXPECT_EQ(RC, CG.lookupRefSCC(FN));
3027 EXPECT_EQ(RC, CG.lookupRefSCC(F2N));
3028 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
3029 }
3030 }
LLVM monorepo