?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
[MIParser] Set RegClassOrRegBank during instruction parsing
[llvm-complete.git] / unittests / Analysis / LazyCallGraphTest.cpp
blob42bdcfb8b7c0b84a645fb21e7df520d2010c0f76
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/Support/ErrorHandling.h"
16 #include "llvm/Support/SourceMgr.h"
17 #include "gtest/gtest.h"
18 #include <memory>
19
20 using namespace llvm;
21
22 namespace {
23
24 std::unique_ptr<Module> parseAssembly(LLVMContext &Context,
25 const char *Assembly) {
26 SMDiagnostic Error;
27 std::unique_ptr<Module> M = parseAssemblyString(Assembly, Error, Context);
28
29 std::string ErrMsg;
30 raw_string_ostream OS(ErrMsg);
31 Error.print("", OS);
32
33 // A failure here means that the test itself is buggy.
34 if (!M)
35 report_fatal_error(OS.str().c_str());
36
37 return M;
38 }
39
40 /*
41 IR forming a call graph with a diamond of triangle-shaped SCCs:
42
43 d1
44 / \
45 d3--d2
46 / \
47 b1 c1
48 / \ / \
49 b3--b2 c3--c2
50 \ /
51 a1
52 / \
53 a3--a2
54
55 All call edges go up between SCCs, and clockwise around the SCC.
56 */
57 static const char DiamondOfTriangles[] =
58 "define void @a1() {\n"
59 "entry:\n"
60 " call void @a2()\n"
61 " call void @b2()\n"
62 " call void @c3()\n"
63 " ret void\n"
64 "}\n"
65 "define void @a2() {\n"
66 "entry:\n"
67 " call void @a3()\n"
68 " ret void\n"
69 "}\n"
70 "define void @a3() {\n"
71 "entry:\n"
72 " call void @a1()\n"
73 " ret void\n"
74 "}\n"
75 "define void @b1() {\n"
76 "entry:\n"
77 " call void @b2()\n"
78 " call void @d3()\n"
79 " ret void\n"
80 "}\n"
81 "define void @b2() {\n"
82 "entry:\n"
83 " call void @b3()\n"
84 " ret void\n"
85 "}\n"
86 "define void @b3() {\n"
87 "entry:\n"
88 " call void @b1()\n"
89 " ret void\n"
90 "}\n"
91 "define void @c1() {\n"
92 "entry:\n"
93 " call void @c2()\n"
94 " call void @d2()\n"
95 " ret void\n"
96 "}\n"
97 "define void @c2() {\n"
98 "entry:\n"
99 " call void @c3()\n"
100 " ret void\n"
101 "}\n"
102 "define void @c3() {\n"
103 "entry:\n"
104 " call void @c1()\n"
105 " ret void\n"
106 "}\n"
107 "define void @d1() {\n"
108 "entry:\n"
109 " call void @d2()\n"
110 " ret void\n"
111 "}\n"
112 "define void @d2() {\n"
113 "entry:\n"
114 " call void @d3()\n"
115 " ret void\n"
116 "}\n"
117 "define void @d3() {\n"
118 "entry:\n"
119 " call void @d1()\n"
120 " ret void\n"
121 "}\n";
122
123 /*
124 IR forming a reference graph with a diamond of triangle-shaped RefSCCs
125
126 d1
127 / \
128 d3--d2
129 / \
130 b1 c1
131 / \ / \
132 b3--b2 c3--c2
133 \ /
134 a1
135 / \
136 a3--a2
137
138 All call edges go up between RefSCCs, and clockwise around the RefSCC.
139 */
140 static const char DiamondOfTrianglesRefGraph[] =
141 "define void @a1() {\n"
142 "entry:\n"
143 " %a = alloca void ()*\n"
144 " store void ()* @a2, void ()** %a\n"
145 " store void ()* @b2, void ()** %a\n"
146 " store void ()* @c3, void ()** %a\n"
147 " ret void\n"
148 "}\n"
149 "define void @a2() {\n"
150 "entry:\n"
151 " %a = alloca void ()*\n"
152 " store void ()* @a3, void ()** %a\n"
153 " ret void\n"
154 "}\n"
155 "define void @a3() {\n"
156 "entry:\n"
157 " %a = alloca void ()*\n"
158 " store void ()* @a1, void ()** %a\n"
159 " ret void\n"
160 "}\n"
161 "define void @b1() {\n"
162 "entry:\n"
163 " %a = alloca void ()*\n"
164 " store void ()* @b2, void ()** %a\n"
165 " store void ()* @d3, void ()** %a\n"
166 " ret void\n"
167 "}\n"
168 "define void @b2() {\n"
169 "entry:\n"
170 " %a = alloca void ()*\n"
171 " store void ()* @b3, void ()** %a\n"
172 " ret void\n"
173 "}\n"
174 "define void @b3() {\n"
175 "entry:\n"
176 " %a = alloca void ()*\n"
177 " store void ()* @b1, void ()** %a\n"
178 " ret void\n"
179 "}\n"
180 "define void @c1() {\n"
181 "entry:\n"
182 " %a = alloca void ()*\n"
183 " store void ()* @c2, void ()** %a\n"
184 " store void ()* @d2, void ()** %a\n"
185 " ret void\n"
186 "}\n"
187 "define void @c2() {\n"
188 "entry:\n"
189 " %a = alloca void ()*\n"
190 " store void ()* @c3, void ()** %a\n"
191 " ret void\n"
192 "}\n"
193 "define void @c3() {\n"
194 "entry:\n"
195 " %a = alloca void ()*\n"
196 " store void ()* @c1, void ()** %a\n"
197 " ret void\n"
198 "}\n"
199 "define void @d1() {\n"
200 "entry:\n"
201 " %a = alloca void ()*\n"
202 " store void ()* @d2, void ()** %a\n"
203 " ret void\n"
204 "}\n"
205 "define void @d2() {\n"
206 "entry:\n"
207 " %a = alloca void ()*\n"
208 " store void ()* @d3, void ()** %a\n"
209 " ret void\n"
210 "}\n"
211 "define void @d3() {\n"
212 "entry:\n"
213 " %a = alloca void ()*\n"
214 " store void ()* @d1, void ()** %a\n"
215 " ret void\n"
216 "}\n";
217
218 static LazyCallGraph buildCG(Module &M) {
219 TargetLibraryInfoImpl TLII(Triple(M.getTargetTriple()));
220 TargetLibraryInfo TLI(TLII);
221 auto GetTLI = [&TLI](Function &F) -> TargetLibraryInfo & { return TLI; };
222
223 LazyCallGraph CG(M, GetTLI);
224 return CG;
225 }
226
227 TEST(LazyCallGraphTest, BasicGraphFormation) {
228 LLVMContext Context;
229 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
230 LazyCallGraph CG = buildCG(*M);
231
232 // The order of the entry nodes should be stable w.r.t. the source order of
233 // the IR, and everything in our module is an entry node, so just directly
234 // build variables for each node.
235 auto I = CG.begin();
236 LazyCallGraph::Node &A1 = (I++)->getNode();
237 EXPECT_EQ("a1", A1.getFunction().getName());
238 LazyCallGraph::Node &A2 = (I++)->getNode();
239 EXPECT_EQ("a2", A2.getFunction().getName());
240 LazyCallGraph::Node &A3 = (I++)->getNode();
241 EXPECT_EQ("a3", A3.getFunction().getName());
242 LazyCallGraph::Node &B1 = (I++)->getNode();
243 EXPECT_EQ("b1", B1.getFunction().getName());
244 LazyCallGraph::Node &B2 = (I++)->getNode();
245 EXPECT_EQ("b2", B2.getFunction().getName());
246 LazyCallGraph::Node &B3 = (I++)->getNode();
247 EXPECT_EQ("b3", B3.getFunction().getName());
248 LazyCallGraph::Node &C1 = (I++)->getNode();
249 EXPECT_EQ("c1", C1.getFunction().getName());
250 LazyCallGraph::Node &C2 = (I++)->getNode();
251 EXPECT_EQ("c2", C2.getFunction().getName());
252 LazyCallGraph::Node &C3 = (I++)->getNode();
253 EXPECT_EQ("c3", C3.getFunction().getName());
254 LazyCallGraph::Node &D1 = (I++)->getNode();
255 EXPECT_EQ("d1", D1.getFunction().getName());
256 LazyCallGraph::Node &D2 = (I++)->getNode();
257 EXPECT_EQ("d2", D2.getFunction().getName());
258 LazyCallGraph::Node &D3 = (I++)->getNode();
259 EXPECT_EQ("d3", D3.getFunction().getName());
260 EXPECT_EQ(CG.end(), I);
261
262 // Build vectors and sort them for the rest of the assertions to make them
263 // independent of order.
264 std::vector<std::string> Nodes;
265
266 for (LazyCallGraph::Edge &E : A1.populate())
267 Nodes.push_back(E.getFunction().getName());
268 llvm::sort(Nodes);
269 EXPECT_EQ("a2", Nodes[0]);
270 EXPECT_EQ("b2", Nodes[1]);
271 EXPECT_EQ("c3", Nodes[2]);
272 Nodes.clear();
273
274 A2.populate();
275 EXPECT_EQ(A2->end(), std::next(A2->begin()));
276 EXPECT_EQ("a3", A2->begin()->getFunction().getName());
277 A3.populate();
278 EXPECT_EQ(A3->end(), std::next(A3->begin()));
279 EXPECT_EQ("a1", A3->begin()->getFunction().getName());
280
281 for (LazyCallGraph::Edge &E : B1.populate())
282 Nodes.push_back(E.getFunction().getName());
283 llvm::sort(Nodes);
284 EXPECT_EQ("b2", Nodes[0]);
285 EXPECT_EQ("d3", Nodes[1]);
286 Nodes.clear();
287
288 B2.populate();
289 EXPECT_EQ(B2->end(), std::next(B2->begin()));
290 EXPECT_EQ("b3", B2->begin()->getFunction().getName());
291 B3.populate();
292 EXPECT_EQ(B3->end(), std::next(B3->begin()));
293 EXPECT_EQ("b1", B3->begin()->getFunction().getName());
294
295 for (LazyCallGraph::Edge &E : C1.populate())
296 Nodes.push_back(E.getFunction().getName());
297 llvm::sort(Nodes);
298 EXPECT_EQ("c2", Nodes[0]);
299 EXPECT_EQ("d2", Nodes[1]);
300 Nodes.clear();
301
302 C2.populate();
303 EXPECT_EQ(C2->end(), std::next(C2->begin()));
304 EXPECT_EQ("c3", C2->begin()->getFunction().getName());
305 C3.populate();
306 EXPECT_EQ(C3->end(), std::next(C3->begin()));
307 EXPECT_EQ("c1", C3->begin()->getFunction().getName());
308
309 D1.populate();
310 EXPECT_EQ(D1->end(), std::next(D1->begin()));
311 EXPECT_EQ("d2", D1->begin()->getFunction().getName());
312 D2.populate();
313 EXPECT_EQ(D2->end(), std::next(D2->begin()));
314 EXPECT_EQ("d3", D2->begin()->getFunction().getName());
315 D3.populate();
316 EXPECT_EQ(D3->end(), std::next(D3->begin()));
317 EXPECT_EQ("d1", D3->begin()->getFunction().getName());
318
319 // Now lets look at the RefSCCs and SCCs.
320 CG.buildRefSCCs();
321 auto J = CG.postorder_ref_scc_begin();
322
323 LazyCallGraph::RefSCC &D = *J++;
324 ASSERT_EQ(1, D.size());
325 for (LazyCallGraph::Node &N : *D.begin())
326 Nodes.push_back(N.getFunction().getName());
327 llvm::sort(Nodes);
328 EXPECT_EQ(3u, Nodes.size());
329 EXPECT_EQ("d1", Nodes[0]);
330 EXPECT_EQ("d2", Nodes[1]);
331 EXPECT_EQ("d3", Nodes[2]);
332 Nodes.clear();
333 EXPECT_FALSE(D.isParentOf(D));
334 EXPECT_FALSE(D.isChildOf(D));
335 EXPECT_FALSE(D.isAncestorOf(D));
336 EXPECT_FALSE(D.isDescendantOf(D));
337 EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin());
338
339 LazyCallGraph::RefSCC &C = *J++;
340 ASSERT_EQ(1, C.size());
341 for (LazyCallGraph::Node &N : *C.begin())
342 Nodes.push_back(N.getFunction().getName());
343 llvm::sort(Nodes);
344 EXPECT_EQ(3u, Nodes.size());
345 EXPECT_EQ("c1", Nodes[0]);
346 EXPECT_EQ("c2", Nodes[1]);
347 EXPECT_EQ("c3", Nodes[2]);
348 Nodes.clear();
349 EXPECT_TRUE(C.isParentOf(D));
350 EXPECT_FALSE(C.isChildOf(D));
351 EXPECT_TRUE(C.isAncestorOf(D));
352 EXPECT_FALSE(C.isDescendantOf(D));
353 EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin()));
354
355 LazyCallGraph::RefSCC &B = *J++;
356 ASSERT_EQ(1, B.size());
357 for (LazyCallGraph::Node &N : *B.begin())
358 Nodes.push_back(N.getFunction().getName());
359 llvm::sort(Nodes);
360 EXPECT_EQ(3u, Nodes.size());
361 EXPECT_EQ("b1", Nodes[0]);
362 EXPECT_EQ("b2", Nodes[1]);
363 EXPECT_EQ("b3", Nodes[2]);
364 Nodes.clear();
365 EXPECT_TRUE(B.isParentOf(D));
366 EXPECT_FALSE(B.isChildOf(D));
367 EXPECT_TRUE(B.isAncestorOf(D));
368 EXPECT_FALSE(B.isDescendantOf(D));
369 EXPECT_FALSE(B.isAncestorOf(C));
370 EXPECT_FALSE(C.isAncestorOf(B));
371 EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin(), 2));
372
373 LazyCallGraph::RefSCC &A = *J++;
374 ASSERT_EQ(1, A.size());
375 for (LazyCallGraph::Node &N : *A.begin())
376 Nodes.push_back(N.getFunction().getName());
377 llvm::sort(Nodes);
378 EXPECT_EQ(3u, Nodes.size());
379 EXPECT_EQ("a1", Nodes[0]);
380 EXPECT_EQ("a2", Nodes[1]);
381 EXPECT_EQ("a3", Nodes[2]);
382 Nodes.clear();
383 EXPECT_TRUE(A.isParentOf(B));
384 EXPECT_TRUE(A.isParentOf(C));
385 EXPECT_FALSE(A.isParentOf(D));
386 EXPECT_TRUE(A.isAncestorOf(B));
387 EXPECT_TRUE(A.isAncestorOf(C));
388 EXPECT_TRUE(A.isAncestorOf(D));
389 EXPECT_EQ(&A, &*std::next(CG.postorder_ref_scc_begin(), 3));
390
391 EXPECT_EQ(CG.postorder_ref_scc_end(), J);
392 EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4));
393 }
394
395 static Function &lookupFunction(Module &M, StringRef Name) {
396 for (Function &F : M)
397 if (F.getName() == Name)
398 return F;
399 report_fatal_error("Couldn't find function!");
400 }
401
402 TEST(LazyCallGraphTest, BasicGraphMutation) {
403 LLVMContext Context;
404 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
405 "entry:\n"
406 " call void @b()\n"
407 " call void @c()\n"
408 " ret void\n"
409 "}\n"
410 "define void @b() {\n"
411 "entry:\n"
412 " ret void\n"
413 "}\n"
414 "define void @c() {\n"
415 "entry:\n"
416 " ret void\n"
417 "}\n");
418 LazyCallGraph CG = buildCG(*M);
419
420 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
421 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
422 A.populate();
423 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
424 B.populate();
425 EXPECT_EQ(0, std::distance(B->begin(), B->end()));
426
427 LazyCallGraph::Node &C = CG.get(lookupFunction(*M, "c"));
428 C.populate();
429 CG.insertEdge(B, C, LazyCallGraph::Edge::Call);
430 EXPECT_EQ(1, std::distance(B->begin(), B->end()));
431 EXPECT_EQ(0, std::distance(C->begin(), C->end()));
432
433 CG.insertEdge(C, B, LazyCallGraph::Edge::Call);
434 EXPECT_EQ(1, std::distance(C->begin(), C->end()));
435 EXPECT_EQ(&B, &C->begin()->getNode());
436
437 CG.insertEdge(C, C, LazyCallGraph::Edge::Call);
438 EXPECT_EQ(2, std::distance(C->begin(), C->end()));
439 EXPECT_EQ(&B, &C->begin()->getNode());
440 EXPECT_EQ(&C, &std::next(C->begin())->getNode());
441
442 CG.removeEdge(C, B);
443 EXPECT_EQ(1, std::distance(C->begin(), C->end()));
444 EXPECT_EQ(&C, &C->begin()->getNode());
445
446 CG.removeEdge(C, C);
447 EXPECT_EQ(0, std::distance(C->begin(), C->end()));
448
449 CG.removeEdge(B, C);
450 EXPECT_EQ(0, std::distance(B->begin(), B->end()));
451 }
452
453 TEST(LazyCallGraphTest, InnerSCCFormation) {
454 LLVMContext Context;
455 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
456 LazyCallGraph CG = buildCG(*M);
457
458 // Now mutate the graph to connect every node into a single RefSCC to ensure
459 // that our inner SCC formation handles the rest.
460 LazyCallGraph::Node &D1 = CG.get(lookupFunction(*M, "d1"));
461 LazyCallGraph::Node &A1 = CG.get(lookupFunction(*M, "a1"));
462 A1.populate();
463 D1.populate();
464 CG.insertEdge(D1, A1, LazyCallGraph::Edge::Ref);
465
466 // Build vectors and sort them for the rest of the assertions to make them
467 // independent of order.
468 std::vector<std::string> Nodes;
469
470 // We should build a single RefSCC for the entire graph.
471 CG.buildRefSCCs();
472 auto I = CG.postorder_ref_scc_begin();
473 LazyCallGraph::RefSCC &RC = *I++;
474 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
475
476 // Now walk the four SCCs which should be in post-order.
477 auto J = RC.begin();
478 LazyCallGraph::SCC &D = *J++;
479 for (LazyCallGraph::Node &N : D)
480 Nodes.push_back(N.getFunction().getName());
481 llvm::sort(Nodes);
482 EXPECT_EQ(3u, Nodes.size());
483 EXPECT_EQ("d1", Nodes[0]);
484 EXPECT_EQ("d2", Nodes[1]);
485 EXPECT_EQ("d3", Nodes[2]);
486 Nodes.clear();
487
488 LazyCallGraph::SCC &B = *J++;
489 for (LazyCallGraph::Node &N : B)
490 Nodes.push_back(N.getFunction().getName());
491 llvm::sort(Nodes);
492 EXPECT_EQ(3u, Nodes.size());
493 EXPECT_EQ("b1", Nodes[0]);
494 EXPECT_EQ("b2", Nodes[1]);
495 EXPECT_EQ("b3", Nodes[2]);
496 Nodes.clear();
497
498 LazyCallGraph::SCC &C = *J++;
499 for (LazyCallGraph::Node &N : C)
500 Nodes.push_back(N.getFunction().getName());
501 llvm::sort(Nodes);
502 EXPECT_EQ(3u, Nodes.size());
503 EXPECT_EQ("c1", Nodes[0]);
504 EXPECT_EQ("c2", Nodes[1]);
505 EXPECT_EQ("c3", Nodes[2]);
506 Nodes.clear();
507
508 LazyCallGraph::SCC &A = *J++;
509 for (LazyCallGraph::Node &N : A)
510 Nodes.push_back(N.getFunction().getName());
511 llvm::sort(Nodes);
512 EXPECT_EQ(3u, Nodes.size());
513 EXPECT_EQ("a1", Nodes[0]);
514 EXPECT_EQ("a2", Nodes[1]);
515 EXPECT_EQ("a3", Nodes[2]);
516 Nodes.clear();
517
518 EXPECT_EQ(RC.end(), J);
519 }
520
521 TEST(LazyCallGraphTest, MultiArmSCC) {
522 LLVMContext Context;
523 // Two interlocking cycles. The really useful thing about this SCC is that it
524 // will require Tarjan's DFS to backtrack and finish processing all of the
525 // children of each node in the SCC. Since this involves call edges, both
526 // Tarjan implementations will have to successfully navigate the structure.
527 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f1() {\n"
528 "entry:\n"
529 " call void @f2()\n"
530 " call void @f4()\n"
531 " ret void\n"
532 "}\n"
533 "define void @f2() {\n"
534 "entry:\n"
535 " call void @f3()\n"
536 " ret void\n"
537 "}\n"
538 "define void @f3() {\n"
539 "entry:\n"
540 " call void @f1()\n"
541 " ret void\n"
542 "}\n"
543 "define void @f4() {\n"
544 "entry:\n"
545 " call void @f5()\n"
546 " ret void\n"
547 "}\n"
548 "define void @f5() {\n"
549 "entry:\n"
550 " call void @f1()\n"
551 " ret void\n"
552 "}\n");
553 LazyCallGraph CG = buildCG(*M);
554
555 // Force the graph to be fully expanded.
556 CG.buildRefSCCs();
557 auto I = CG.postorder_ref_scc_begin();
558 LazyCallGraph::RefSCC &RC = *I++;
559 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
560
561 LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1"));
562 LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2"));
563 LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3"));
564 LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4"));
565 LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4"));
566 EXPECT_EQ(&RC, CG.lookupRefSCC(N1));
567 EXPECT_EQ(&RC, CG.lookupRefSCC(N2));
568 EXPECT_EQ(&RC, CG.lookupRefSCC(N3));
569 EXPECT_EQ(&RC, CG.lookupRefSCC(N4));
570 EXPECT_EQ(&RC, CG.lookupRefSCC(N5));
571
572 ASSERT_EQ(1, RC.size());
573
574 LazyCallGraph::SCC &C = *RC.begin();
575 EXPECT_EQ(&C, CG.lookupSCC(N1));
576 EXPECT_EQ(&C, CG.lookupSCC(N2));
577 EXPECT_EQ(&C, CG.lookupSCC(N3));
578 EXPECT_EQ(&C, CG.lookupSCC(N4));
579 EXPECT_EQ(&C, CG.lookupSCC(N5));
580 }
581
582 TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
583 LLVMContext Context;
584 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
585 "entry:\n"
586 " call void @b()\n"
587 " call void @c()\n"
588 " ret void\n"
589 "}\n"
590 "define void @b() {\n"
591 "entry:\n"
592 " call void @d()\n"
593 " ret void\n"
594 "}\n"
595 "define void @c() {\n"
596 "entry:\n"
597 " call void @d()\n"
598 " ret void\n"
599 "}\n"
600 "define void @d() {\n"
601 "entry:\n"
602 " ret void\n"
603 "}\n");
604 LazyCallGraph CG = buildCG(*M);
605
606 // Force the graph to be fully expanded.
607 CG.buildRefSCCs();
608 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
609 dbgs() << "Formed RefSCC: " << RC << "\n";
610
611 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
612 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
613 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
614 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
615 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
616 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
617 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
618 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
619 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
620 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
621 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
622 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
623 EXPECT_TRUE(ARC.isParentOf(BRC));
624 EXPECT_TRUE(AC.isParentOf(BC));
625 EXPECT_TRUE(ARC.isParentOf(CRC));
626 EXPECT_TRUE(AC.isParentOf(CC));
627 EXPECT_FALSE(ARC.isParentOf(DRC));
628 EXPECT_FALSE(AC.isParentOf(DC));
629 EXPECT_TRUE(ARC.isAncestorOf(DRC));
630 EXPECT_TRUE(AC.isAncestorOf(DC));
631 EXPECT_FALSE(DRC.isChildOf(ARC));
632 EXPECT_FALSE(DC.isChildOf(AC));
633 EXPECT_TRUE(DRC.isDescendantOf(ARC));
634 EXPECT_TRUE(DC.isDescendantOf(AC));
635 EXPECT_TRUE(DRC.isChildOf(BRC));
636 EXPECT_TRUE(DC.isChildOf(BC));
637 EXPECT_TRUE(DRC.isChildOf(CRC));
638 EXPECT_TRUE(DC.isChildOf(CC));
639
640 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
641 ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call);
642 EXPECT_EQ(3, std::distance(A->begin(), A->end()));
643 const LazyCallGraph::Edge &NewE = (*A)[D];
644 EXPECT_TRUE(NewE);
645 EXPECT_TRUE(NewE.isCall());
646 EXPECT_EQ(&D, &NewE.getNode());
647
648 // Only the parent and child tests sholud have changed. The rest of the graph
649 // remains the same.
650 EXPECT_TRUE(ARC.isParentOf(DRC));
651 EXPECT_TRUE(AC.isParentOf(DC));
652 EXPECT_TRUE(ARC.isAncestorOf(DRC));
653 EXPECT_TRUE(AC.isAncestorOf(DC));
654 EXPECT_TRUE(DRC.isChildOf(ARC));
655 EXPECT_TRUE(DC.isChildOf(AC));
656 EXPECT_TRUE(DRC.isDescendantOf(ARC));
657 EXPECT_TRUE(DC.isDescendantOf(AC));
658 EXPECT_EQ(&AC, CG.lookupSCC(A));
659 EXPECT_EQ(&BC, CG.lookupSCC(B));
660 EXPECT_EQ(&CC, CG.lookupSCC(C));
661 EXPECT_EQ(&DC, CG.lookupSCC(D));
662 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
663 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
664 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
665 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
666
667 ARC.switchOutgoingEdgeToRef(A, D);
668 EXPECT_FALSE(NewE.isCall());
669
670 // Verify the reference graph remains the same but the SCC graph is updated.
671 EXPECT_TRUE(ARC.isParentOf(DRC));
672 EXPECT_FALSE(AC.isParentOf(DC));
673 EXPECT_TRUE(ARC.isAncestorOf(DRC));
674 EXPECT_TRUE(AC.isAncestorOf(DC));
675 EXPECT_TRUE(DRC.isChildOf(ARC));
676 EXPECT_FALSE(DC.isChildOf(AC));
677 EXPECT_TRUE(DRC.isDescendantOf(ARC));
678 EXPECT_TRUE(DC.isDescendantOf(AC));
679 EXPECT_EQ(&AC, CG.lookupSCC(A));
680 EXPECT_EQ(&BC, CG.lookupSCC(B));
681 EXPECT_EQ(&CC, CG.lookupSCC(C));
682 EXPECT_EQ(&DC, CG.lookupSCC(D));
683 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
684 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
685 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
686 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
687
688 ARC.switchOutgoingEdgeToCall(A, D);
689 EXPECT_TRUE(NewE.isCall());
690
691 // Verify the reference graph remains the same but the SCC graph is updated.
692 EXPECT_TRUE(ARC.isParentOf(DRC));
693 EXPECT_TRUE(AC.isParentOf(DC));
694 EXPECT_TRUE(ARC.isAncestorOf(DRC));
695 EXPECT_TRUE(AC.isAncestorOf(DC));
696 EXPECT_TRUE(DRC.isChildOf(ARC));
697 EXPECT_TRUE(DC.isChildOf(AC));
698 EXPECT_TRUE(DRC.isDescendantOf(ARC));
699 EXPECT_TRUE(DC.isDescendantOf(AC));
700 EXPECT_EQ(&AC, CG.lookupSCC(A));
701 EXPECT_EQ(&BC, CG.lookupSCC(B));
702 EXPECT_EQ(&CC, CG.lookupSCC(C));
703 EXPECT_EQ(&DC, CG.lookupSCC(D));
704 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
705 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
706 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
707 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
708
709 ARC.removeOutgoingEdge(A, D);
710 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
711
712 // Now the parent and child tests fail again but the rest remains the same.
713 EXPECT_FALSE(ARC.isParentOf(DRC));
714 EXPECT_FALSE(AC.isParentOf(DC));
715 EXPECT_TRUE(ARC.isAncestorOf(DRC));
716 EXPECT_TRUE(AC.isAncestorOf(DC));
717 EXPECT_FALSE(DRC.isChildOf(ARC));
718 EXPECT_FALSE(DC.isChildOf(AC));
719 EXPECT_TRUE(DRC.isDescendantOf(ARC));
720 EXPECT_TRUE(DC.isDescendantOf(AC));
721 EXPECT_EQ(&AC, CG.lookupSCC(A));
722 EXPECT_EQ(&BC, CG.lookupSCC(B));
723 EXPECT_EQ(&CC, CG.lookupSCC(C));
724 EXPECT_EQ(&DC, CG.lookupSCC(D));
725 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
726 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
727 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
728 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
729 }
730
731 TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
732 LLVMContext Context;
733 // We want to ensure we can add edges even across complex diamond graphs, so
734 // we use the diamond of triangles graph defined above. The ascii diagram is
735 // repeated here for easy reference.
736 //
737 // d1 |
738 // / \ |
739 // d3--d2 |
740 // / \ |
741 // b1 c1 |
742 // / \ / \ |
743 // b3--b2 c3--c2 |
744 // \ / |
745 // a1 |
746 // / \ |
747 // a3--a2 |
748 //
749 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
750 LazyCallGraph CG = buildCG(*M);
751
752 // Force the graph to be fully expanded.
753 CG.buildRefSCCs();
754 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
755 dbgs() << "Formed RefSCC: " << RC << "\n";
756
757 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
758 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
759 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
760 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
761 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
762 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
763 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
764 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
765 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
766 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
767 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
768 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
769 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
770 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
771 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
772 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
773 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
774 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
775 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
776 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
777 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
778 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
779 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
780 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
781 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
782
783 // Add an edge to make the graph:
784 //
785 // d1 |
786 // / \ |
787 // d3--d2---. |
788 // / \ | |
789 // b1 c1 | |
790 // / \ / \ / |
791 // b3--b2 c3--c2 |
792 // \ / |
793 // a1 |
794 // / \ |
795 // a3--a2 |
796 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
797 // Make sure we connected the nodes.
798 for (LazyCallGraph::Edge E : *D2) {
799 if (&E.getNode() == &D3)
800 continue;
801 EXPECT_EQ(&C2, &E.getNode());
802 }
803 // And marked the D ref-SCC as no longer valid.
804 EXPECT_EQ(1u, MergedRCs.size());
805 EXPECT_EQ(&DRC, MergedRCs[0]);
806
807 // Make sure we have the correct nodes in the SCC sets.
808 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
809 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
810 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
811 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
812 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
813 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
814 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
815 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
816 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
817 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
818 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
819 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
820
821 // And that ancestry tests have been updated.
822 EXPECT_TRUE(ARC.isParentOf(CRC));
823 EXPECT_TRUE(BRC.isParentOf(CRC));
824
825 // And verify the post-order walk reflects the updated structure.
826 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
827 ASSERT_NE(I, E);
828 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
829 ASSERT_NE(++I, E);
830 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
831 ASSERT_NE(++I, E);
832 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
833 EXPECT_EQ(++I, E);
834 }
835
836 TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) {
837 LLVMContext Context;
838 // Another variation of the above test but with all the edges switched to
839 // references rather than calls.
840 std::unique_ptr<Module> M =
841 parseAssembly(Context, DiamondOfTrianglesRefGraph);
842 LazyCallGraph CG = buildCG(*M);
843
844 // Force the graph to be fully expanded.
845 CG.buildRefSCCs();
846 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
847 dbgs() << "Formed RefSCC: " << RC << "\n";
848
849 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
850 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
851 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
852 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
853 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
854 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
855 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
856 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
857 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
858 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
859 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
860 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
861 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
862 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
863 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
864 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
865 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
866 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
867 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
868 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
869 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
870 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
871 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
872 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
873 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
874
875 // Add an edge to make the graph:
876 //
877 // d1 |
878 // / \ |
879 // d3--d2---. |
880 // / \ | |
881 // b1 c1 | |
882 // / \ / \ / |
883 // b3--b2 c3--c2 |
884 // \ / |
885 // a1 |
886 // / \ |
887 // a3--a2 |
888 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
889 // Make sure we connected the nodes.
890 for (LazyCallGraph::Edge E : *D2) {
891 if (&E.getNode() == &D3)
892 continue;
893 EXPECT_EQ(&C2, &E.getNode());
894 }
895 // And marked the D ref-SCC as no longer valid.
896 EXPECT_EQ(1u, MergedRCs.size());
897 EXPECT_EQ(&DRC, MergedRCs[0]);
898
899 // Make sure we have the correct nodes in the SCC sets.
900 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
901 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
902 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
903 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
904 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
905 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
906 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
907 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
908 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
909 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
910 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
911 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
912
913 // And that ancestry tests have been updated.
914 EXPECT_TRUE(ARC.isParentOf(CRC));
915 EXPECT_TRUE(BRC.isParentOf(CRC));
916
917 // And verify the post-order walk reflects the updated structure.
918 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
919 ASSERT_NE(I, E);
920 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
921 ASSERT_NE(++I, E);
922 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
923 ASSERT_NE(++I, E);
924 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
925 EXPECT_EQ(++I, E);
926 }
927
928 TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) {
929 LLVMContext Context;
930 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
931 "entry:\n"
932 " call void @b()\n"
933 " ret void\n"
934 "}\n"
935 "define void @b() {\n"
936 "entry:\n"
937 " call void @c()\n"
938 " ret void\n"
939 "}\n"
940 "define void @c() {\n"
941 "entry:\n"
942 " call void @d()\n"
943 " ret void\n"
944 "}\n"
945 "define void @d() {\n"
946 "entry:\n"
947 " ret void\n"
948 "}\n");
949 LazyCallGraph CG = buildCG(*M);
950
951 // Force the graph to be fully expanded.
952 CG.buildRefSCCs();
953 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
954 dbgs() << "Formed RefSCC: " << RC << "\n";
955
956 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
957 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
958 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
959 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
960 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
961 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
962 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
963 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
964 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
965 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
966 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
967 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
968
969 // Connect the top to the bottom forming a large RefSCC made up mostly of calls.
970 auto MergedRCs = ARC.insertIncomingRefEdge(D, A);
971 // Make sure we connected the nodes.
972 EXPECT_NE(D->begin(), D->end());
973 EXPECT_EQ(&A, &D->begin()->getNode());
974
975 // Check that we have the dead RCs, but ignore the order.
976 EXPECT_EQ(3u, MergedRCs.size());
977 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());
978 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());
979 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());
980
981 // Make sure the nodes point to the right place now.
982 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
983 EXPECT_EQ(&ARC, CG.lookupRefSCC(B));
984 EXPECT_EQ(&ARC, CG.lookupRefSCC(C));
985 EXPECT_EQ(&ARC, CG.lookupRefSCC(D));
986
987 // Check that the SCCs are in postorder.
988 EXPECT_EQ(4, ARC.size());
989 EXPECT_EQ(&DC, &ARC[0]);
990 EXPECT_EQ(&CC, &ARC[1]);
991 EXPECT_EQ(&BC, &ARC[2]);
992 EXPECT_EQ(&AC, &ARC[3]);
993
994 // And verify the post-order walk reflects the updated structure.
995 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
996 ASSERT_NE(I, E);
997 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
998 EXPECT_EQ(++I, E);
999 }
1000
1001 TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
1002 LLVMContext Context;
1003 std::unique_ptr<Module> M =
1004 parseAssembly(Context, "define void @a() {\n"
1005 "entry:\n"
1006 " %p = alloca void ()*\n"
1007 " store void ()* @b, void ()** %p\n"
1008 " ret void\n"
1009 "}\n"
1010 "define void @b() {\n"
1011 "entry:\n"
1012 " %p = alloca void ()*\n"
1013 " store void ()* @c, void ()** %p\n"
1014 " ret void\n"
1015 "}\n"
1016 "define void @c() {\n"
1017 "entry:\n"
1018 " %p = alloca void ()*\n"
1019 " store void ()* @d, void ()** %p\n"
1020 " ret void\n"
1021 "}\n"
1022 "define void @d() {\n"
1023 "entry:\n"
1024 " ret void\n"
1025 "}\n");
1026 LazyCallGraph CG = buildCG(*M);
1027
1028 // Force the graph to be fully expanded.
1029 CG.buildRefSCCs();
1030 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
1031 dbgs() << "Formed RefSCC: " << RC << "\n";
1032
1033 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1034 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1035 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1036 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1037 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
1038 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
1039 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
1040 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
1041
1042 // Connect the top to the bottom forming a large RefSCC made up just of
1043 // references.
1044 auto MergedRCs = ARC.insertIncomingRefEdge(D, A);
1045 // Make sure we connected the nodes.
1046 EXPECT_NE(D->begin(), D->end());
1047 EXPECT_EQ(&A, &D->begin()->getNode());
1048
1049 // Check that we have the dead RCs, but ignore the order.
1050 EXPECT_EQ(3u, MergedRCs.size());
1051 EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());
1052 EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());
1053 EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());
1054
1055 // Make sure the nodes point to the right place now.
1056 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
1057 EXPECT_EQ(&ARC, CG.lookupRefSCC(B));
1058 EXPECT_EQ(&ARC, CG.lookupRefSCC(C));
1059 EXPECT_EQ(&ARC, CG.lookupRefSCC(D));
1060
1061 // And verify the post-order walk reflects the updated structure.
1062 auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end();
1063 ASSERT_NE(I, End);
1064 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1065 EXPECT_EQ(++I, End);
1066 }
1067
1068 TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
1069 LLVMContext Context;
1070 // We want to ensure we can delete nodes from relatively complex graphs and
1071 // so use the diamond of triangles graph defined above.
1072 //
1073 // The ascii diagram is repeated here for easy reference.
1074 //
1075 // d1 |
1076 // / \ |
1077 // d3--d2 |
1078 // / \ |
1079 // b1 c1 |
1080 // / \ / \ |
1081 // b3--b2 c3--c2 |
1082 // \ / |
1083 // a1 |
1084 // / \ |
1085 // a3--a2 |
1086 //
1087 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
1088 LazyCallGraph CG = buildCG(*M);
1089
1090 // Force the graph to be fully expanded.
1091 CG.buildRefSCCs();
1092 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
1093 dbgs() << "Formed RefSCC: " << RC << "\n";
1094
1095 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
1096 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
1097 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
1098 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
1099 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
1100 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
1101 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
1102 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
1103 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
1104 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
1105 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
1106 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
1107 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
1108 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
1109 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
1110 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
1111 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
1112 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
1113 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
1114 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
1115 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
1116 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
1117 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
1118 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
1119 ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
1120
1121 // Delete d2 from the graph, as if it had been inlined.
1122 //
1123 // d1 |
1124 // / / |
1125 // d3--. |
1126 // / \ |
1127 // b1 c1 |
1128 // / \ / \ |
1129 // b3--b2 c3--c2 |
1130 // \ / |
1131 // a1 |
1132 // / \ |
1133 // a3--a2 |
1134
1135 Function &D2F = D2.getFunction();
1136 CallInst *C1Call = nullptr, *D1Call = nullptr;
1137 for (User *U : D2F.users()) {
1138 CallInst *CI = dyn_cast<CallInst>(U);
1139 ASSERT_TRUE(CI) << "Expected a call: " << *U;
1140 if (CI->getParent()->getParent() == &C1.getFunction()) {
1141 ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;
1142 C1Call = CI;
1143 } else if (CI->getParent()->getParent() == &D1.getFunction()) {
1144 ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;
1145 D1Call = CI;
1146 } else {
1147 FAIL() << "Found an unexpected call instruction: " << *CI;
1148 }
1149 }
1150 ASSERT_NE(C1Call, nullptr);
1151 ASSERT_NE(D1Call, nullptr);
1152 ASSERT_EQ(&D2F, C1Call->getCalledFunction());
1153 ASSERT_EQ(&D2F, D1Call->getCalledFunction());
1154 C1Call->setCalledFunction(&D3.getFunction());
1155 D1Call->setCalledFunction(&D3.getFunction());
1156 ASSERT_EQ(0u, D2F.getNumUses());
1157
1158 // Insert new edges first.
1159 CRC.insertTrivialCallEdge(C1, D3);
1160 DRC.insertTrivialCallEdge(D1, D3);
1161
1162 // Then remove the old ones.
1163 LazyCallGraph::SCC &DC = *CG.lookupSCC(D2);
1164 auto NewCs = DRC.switchInternalEdgeToRef(D1, D2);
1165 EXPECT_EQ(&DC, CG.lookupSCC(D2));
1166 EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));
1167 LazyCallGraph::SCC &NewDC = *NewCs.begin();
1168 EXPECT_EQ(&NewDC, CG.lookupSCC(D1));
1169 EXPECT_EQ(&NewDC, CG.lookupSCC(D3));
1170 auto NewRCs = DRC.removeInternalRefEdge(D1, {&D2});
1171 ASSERT_EQ(2u, NewRCs.size());
1172 LazyCallGraph::RefSCC &NewDRC = *NewRCs[0];
1173 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
1174 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
1175 LazyCallGraph::RefSCC &D2RC = *NewRCs[1];
1176 EXPECT_EQ(&D2RC, CG.lookupRefSCC(D2));
1177 EXPECT_FALSE(NewDRC.isParentOf(D2RC));
1178 EXPECT_TRUE(CRC.isParentOf(D2RC));
1179 EXPECT_TRUE(CRC.isParentOf(NewDRC));
1180 EXPECT_TRUE(D2RC.isParentOf(NewDRC));
1181 CRC.removeOutgoingEdge(C1, D2);
1182 EXPECT_FALSE(CRC.isParentOf(D2RC));
1183 EXPECT_TRUE(CRC.isParentOf(NewDRC));
1184 EXPECT_TRUE(D2RC.isParentOf(NewDRC));
1185
1186 // Now that we've updated the call graph, D2 is dead, so remove it.
1187 CG.removeDeadFunction(D2F);
1188
1189 // Check that the graph still looks the same.
1190 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
1191 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
1192 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
1193 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
1194 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
1195 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
1196 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
1197 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
1198 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
1199 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
1200 EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
1201 EXPECT_TRUE(CRC.isParentOf(NewDRC));
1202
1203 // Verify the post-order walk hasn't changed.
1204 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1205 ASSERT_NE(I, E);
1206 EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;
1207 ASSERT_NE(++I, E);
1208 EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
1209 ASSERT_NE(++I, E);
1210 EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
1211 ASSERT_NE(++I, E);
1212 EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1213 EXPECT_EQ(++I, E);
1214 }
1215
1216 TEST(LazyCallGraphTest, InternalEdgeMutation) {
1217 LLVMContext Context;
1218 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
1219 "entry:\n"
1220 " call void @b()\n"
1221 " ret void\n"
1222 "}\n"
1223 "define void @b() {\n"
1224 "entry:\n"
1225 " call void @c()\n"
1226 " ret void\n"
1227 "}\n"
1228 "define void @c() {\n"
1229 "entry:\n"
1230 " call void @a()\n"
1231 " ret void\n"
1232 "}\n");
1233 LazyCallGraph CG = buildCG(*M);
1234
1235 // Force the graph to be fully expanded.
1236 CG.buildRefSCCs();
1237 auto I = CG.postorder_ref_scc_begin();
1238 LazyCallGraph::RefSCC &RC = *I++;
1239 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1240
1241 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1242 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1243 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1244 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1245 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1246 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1247 EXPECT_EQ(1, RC.size());
1248 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
1249 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
1250 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
1251
1252 // Insert an edge from 'a' to 'c'. Nothing changes about the graph.
1253 RC.insertInternalRefEdge(A, C);
1254 EXPECT_EQ(2, std::distance(A->begin(), A->end()));
1255 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1256 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1257 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1258 EXPECT_EQ(1, RC.size());
1259 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
1260 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
1261 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
1262
1263 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the
1264 // call cycle and cause us to form more SCCs. The RefSCC will remain the same
1265 // though.
1266 auto NewCs = RC.switchInternalEdgeToRef(B, C);
1267 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1268 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1269 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1270 auto J = RC.begin();
1271 // The SCCs must be in *post-order* which means successors before
1272 // predecessors. At this point we have call edges from C to A and from A to
1273 // B. The only valid postorder is B, A, C.
1274 EXPECT_EQ(&*J++, CG.lookupSCC(B));
1275 EXPECT_EQ(&*J++, CG.lookupSCC(A));
1276 EXPECT_EQ(&*J++, CG.lookupSCC(C));
1277 EXPECT_EQ(RC.end(), J);
1278 // And the returned range must be the slice of this sequence containing new
1279 // SCCs.
1280 EXPECT_EQ(RC.begin(), NewCs.begin());
1281 EXPECT_EQ(std::prev(RC.end()), NewCs.end());
1282
1283 // Test turning the ref edge from A to C into a call edge. This will form an
1284 // SCC out of A and C. Since we previously had a call edge from C to A, the
1285 // C SCC should be preserved and have A merged into it while the A SCC should
1286 // be invalidated.
1287 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1288 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1289 EXPECT_TRUE(RC.switchInternalEdgeToCall(A, C, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1290 ASSERT_EQ(1u, MergedCs.size());
1291 EXPECT_EQ(&AC, MergedCs[0]);
1292 }));
1293 EXPECT_EQ(2, CC.size());
1294 EXPECT_EQ(&CC, CG.lookupSCC(A));
1295 EXPECT_EQ(&CC, CG.lookupSCC(C));
1296 J = RC.begin();
1297 EXPECT_EQ(&*J++, CG.lookupSCC(B));
1298 EXPECT_EQ(&*J++, CG.lookupSCC(C));
1299 EXPECT_EQ(RC.end(), J);
1300 }
1301
1302 TEST(LazyCallGraphTest, InternalEdgeRemoval) {
1303 LLVMContext Context;
1304 // A nice fully connected (including self-edges) RefSCC.
1305 std::unique_ptr<Module> M = parseAssembly(
1306 Context, "define void @a(i8** %ptr) {\n"
1307 "entry:\n"
1308 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1309 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1310 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1311 " ret void\n"
1312 "}\n"
1313 "define void @b(i8** %ptr) {\n"
1314 "entry:\n"
1315 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1316 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1317 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1318 " ret void\n"
1319 "}\n"
1320 "define void @c(i8** %ptr) {\n"
1321 "entry:\n"
1322 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1323 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1324 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1325 " ret void\n"
1326 "}\n");
1327 LazyCallGraph CG = buildCG(*M);
1328
1329 // Force the graph to be fully expanded.
1330 CG.buildRefSCCs();
1331 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1332 LazyCallGraph::RefSCC &RC = *I;
1333 EXPECT_EQ(E, std::next(I));
1334
1335 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1336 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1337 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1338 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1339 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1340 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1341
1342 // Remove the edge from b -> a, which should leave the 3 functions still in
1343 // a single connected component because of a -> b -> c -> a.
1344 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1345 RC.removeInternalRefEdge(B, {&A});
1346 EXPECT_EQ(0u, NewRCs.size());
1347 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1348 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1349 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1350 auto J = CG.postorder_ref_scc_begin();
1351 EXPECT_EQ(I, J);
1352 EXPECT_EQ(&RC, &*J);
1353 EXPECT_EQ(E, std::next(J));
1354
1355 // Increment I before we actually mutate the structure so that it remains
1356 // a valid iterator.
1357 ++I;
1358
1359 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC
1360 // and form a new RefSCC for 'b' and 'c'.
1361 NewRCs = RC.removeInternalRefEdge(C, {&A});
1362 ASSERT_EQ(2u, NewRCs.size());
1363 LazyCallGraph::RefSCC &BCRC = *NewRCs[0];
1364 LazyCallGraph::RefSCC &ARC = *NewRCs[1];
1365 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
1366 EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end()));
1367 EXPECT_EQ(&BCRC, CG.lookupRefSCC(B));
1368 EXPECT_EQ(&BCRC, CG.lookupRefSCC(C));
1369 J = CG.postorder_ref_scc_begin();
1370 EXPECT_NE(I, J);
1371 EXPECT_EQ(&BCRC, &*J);
1372 ++J;
1373 EXPECT_NE(I, J);
1374 EXPECT_EQ(&ARC, &*J);
1375 ++J;
1376 EXPECT_EQ(I, J);
1377 EXPECT_EQ(E, J);
1378 }
1379
1380 TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) {
1381 LLVMContext Context;
1382 // A nice fully connected (including self-edges) RefSCC.
1383 std::unique_ptr<Module> M = parseAssembly(
1384 Context, "define void @a(i8** %ptr) {\n"
1385 "entry:\n"
1386 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1387 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1388 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1389 " ret void\n"
1390 "}\n"
1391 "define void @b(i8** %ptr) {\n"
1392 "entry:\n"
1393 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1394 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1395 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1396 " ret void\n"
1397 "}\n"
1398 "define void @c(i8** %ptr) {\n"
1399 "entry:\n"
1400 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1401 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1402 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1403 " ret void\n"
1404 "}\n");
1405 LazyCallGraph CG = buildCG(*M);
1406
1407 // Force the graph to be fully expanded.
1408 CG.buildRefSCCs();
1409 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1410 LazyCallGraph::RefSCC &RC = *I;
1411 EXPECT_EQ(E, std::next(I));
1412
1413 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1414 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1415 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1416 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1417 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1418 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1419
1420 // Increment I before we actually mutate the structure so that it remains
1421 // a valid iterator.
1422 ++I;
1423
1424 // Remove the edges from b -> a and b -> c, leaving b in its own RefSCC.
1425 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1426 RC.removeInternalRefEdge(B, {&A, &C});
1427
1428 ASSERT_EQ(2u, NewRCs.size());
1429 LazyCallGraph::RefSCC &BRC = *NewRCs[0];
1430 LazyCallGraph::RefSCC &ACRC = *NewRCs[1];
1431 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
1432 EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end()));
1433 EXPECT_EQ(&ACRC, CG.lookupRefSCC(A));
1434 EXPECT_EQ(&ACRC, CG.lookupRefSCC(C));
1435 auto J = CG.postorder_ref_scc_begin();
1436 EXPECT_NE(I, J);
1437 EXPECT_EQ(&BRC, &*J);
1438 ++J;
1439 EXPECT_NE(I, J);
1440 EXPECT_EQ(&ACRC, &*J);
1441 ++J;
1442 EXPECT_EQ(I, J);
1443 EXPECT_EQ(E, J);
1444 }
1445
1446 TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) {
1447 LLVMContext Context;
1448 // A graph with a single cycle formed both from call and reference edges
1449 // which makes the reference edges trivial to delete. The graph looks like:
1450 //
1451 // Reference edges: a -> b -> c -> a
1452 // Call edges: a -> c -> b -> a
1453 std::unique_ptr<Module> M = parseAssembly(
1454 Context, "define void @a(i8** %ptr) {\n"
1455 "entry:\n"
1456 " call void @b(i8** %ptr)\n"
1457 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1458 " ret void\n"
1459 "}\n"
1460 "define void @b(i8** %ptr) {\n"
1461 "entry:\n"
1462 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1463 " call void @c(i8** %ptr)\n"
1464 " ret void\n"
1465 "}\n"
1466 "define void @c(i8** %ptr) {\n"
1467 "entry:\n"
1468 " call void @a(i8** %ptr)\n"
1469 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1470 " ret void\n"
1471 "}\n");
1472 LazyCallGraph CG = buildCG(*M);
1473
1474 // Force the graph to be fully expanded.
1475 CG.buildRefSCCs();
1476 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1477 LazyCallGraph::RefSCC &RC = *I;
1478 EXPECT_EQ(E, std::next(I));
1479
1480 LazyCallGraph::SCC &C = *RC.begin();
1481 EXPECT_EQ(RC.end(), std::next(RC.begin()));
1482
1483 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
1484 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
1485 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
1486 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1487 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1488 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1489 EXPECT_EQ(&C, CG.lookupSCC(AN));
1490 EXPECT_EQ(&C, CG.lookupSCC(BN));
1491 EXPECT_EQ(&C, CG.lookupSCC(CN));
1492
1493 // Remove the edge from a -> c which doesn't change anything.
1494 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1495 RC.removeInternalRefEdge(AN, {&CN});
1496 EXPECT_EQ(0u, NewRCs.size());
1497 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1498 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1499 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1500 EXPECT_EQ(&C, CG.lookupSCC(AN));
1501 EXPECT_EQ(&C, CG.lookupSCC(BN));
1502 EXPECT_EQ(&C, CG.lookupSCC(CN));
1503 auto J = CG.postorder_ref_scc_begin();
1504 EXPECT_EQ(I, J);
1505 EXPECT_EQ(&RC, &*J);
1506 EXPECT_EQ(E, std::next(J));
1507
1508 // Remove the edge from b -> a and c -> b; again this doesn't change
1509 // anything.
1510 NewRCs = RC.removeInternalRefEdge(BN, {&AN});
1511 NewRCs = RC.removeInternalRefEdge(CN, {&BN});
1512 EXPECT_EQ(0u, NewRCs.size());
1513 EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1514 EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1515 EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1516 EXPECT_EQ(&C, CG.lookupSCC(AN));
1517 EXPECT_EQ(&C, CG.lookupSCC(BN));
1518 EXPECT_EQ(&C, CG.lookupSCC(CN));
1519 J = CG.postorder_ref_scc_begin();
1520 EXPECT_EQ(I, J);
1521 EXPECT_EQ(&RC, &*J);
1522 EXPECT_EQ(E, std::next(J));
1523 }
1524
1525 TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
1526 LLVMContext Context;
1527 // A nice fully connected (including self-edges) SCC (and RefSCC)
1528 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
1529 "entry:\n"
1530 " call void @a()\n"
1531 " call void @b()\n"
1532 " call void @c()\n"
1533 " ret void\n"
1534 "}\n"
1535 "define void @b() {\n"
1536 "entry:\n"
1537 " call void @a()\n"
1538 " call void @b()\n"
1539 " call void @c()\n"
1540 " ret void\n"
1541 "}\n"
1542 "define void @c() {\n"
1543 "entry:\n"
1544 " call void @a()\n"
1545 " call void @b()\n"
1546 " call void @c()\n"
1547 " ret void\n"
1548 "}\n");
1549 LazyCallGraph CG = buildCG(*M);
1550
1551 // Force the graph to be fully expanded.
1552 CG.buildRefSCCs();
1553 auto I = CG.postorder_ref_scc_begin();
1554 LazyCallGraph::RefSCC &RC = *I++;
1555 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1556
1557 EXPECT_EQ(1, RC.size());
1558 LazyCallGraph::SCC &AC = *RC.begin();
1559
1560 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
1561 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
1562 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
1563 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1564 EXPECT_EQ(&AC, CG.lookupSCC(BN));
1565 EXPECT_EQ(&AC, CG.lookupSCC(CN));
1566
1567 // Remove the call edge from b -> a to a ref edge, which should leave the
1568 // 3 functions still in a single connected component because of a -> b ->
1569 // c -> a.
1570 auto NewCs = RC.switchInternalEdgeToRef(BN, AN);
1571 EXPECT_EQ(NewCs.begin(), NewCs.end());
1572 EXPECT_EQ(1, RC.size());
1573 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1574 EXPECT_EQ(&AC, CG.lookupSCC(BN));
1575 EXPECT_EQ(&AC, CG.lookupSCC(CN));
1576
1577 // Remove the edge from c -> a, which should leave 'a' in the original SCC
1578 // and form a new SCC for 'b' and 'c'.
1579 NewCs = RC.switchInternalEdgeToRef(CN, AN);
1580 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
1581 EXPECT_EQ(2, RC.size());
1582 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1583 LazyCallGraph::SCC &BC = *CG.lookupSCC(BN);
1584 EXPECT_NE(&BC, &AC);
1585 EXPECT_EQ(&BC, CG.lookupSCC(CN));
1586 auto J = RC.find(AC);
1587 EXPECT_EQ(&AC, &*J);
1588 --J;
1589 EXPECT_EQ(&BC, &*J);
1590 EXPECT_EQ(RC.begin(), J);
1591 EXPECT_EQ(J, NewCs.begin());
1592
1593 // Remove the edge from c -> b, which should leave 'b' in the original SCC
1594 // and form a new SCC for 'c'. It shouldn't change 'a's SCC.
1595 NewCs = RC.switchInternalEdgeToRef(CN, BN);
1596 EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
1597 EXPECT_EQ(3, RC.size());
1598 EXPECT_EQ(&AC, CG.lookupSCC(AN));
1599 EXPECT_EQ(&BC, CG.lookupSCC(BN));
1600 LazyCallGraph::SCC &CC = *CG.lookupSCC(CN);
1601 EXPECT_NE(&CC, &AC);
1602 EXPECT_NE(&CC, &BC);
1603 J = RC.find(AC);
1604 EXPECT_EQ(&AC, &*J);
1605 --J;
1606 EXPECT_EQ(&BC, &*J);
1607 --J;
1608 EXPECT_EQ(&CC, &*J);
1609 EXPECT_EQ(RC.begin(), J);
1610 EXPECT_EQ(J, NewCs.begin());
1611 }
1612
1613 TEST(LazyCallGraphTest, InternalRefEdgeToCall) {
1614 LLVMContext Context;
1615 // Basic tests for making a ref edge a call. This hits the basics of the
1616 // process only.
1617 std::unique_ptr<Module> M =
1618 parseAssembly(Context, "define void @a() {\n"
1619 "entry:\n"
1620 " call void @b()\n"
1621 " call void @c()\n"
1622 " store void()* @d, void()** undef\n"
1623 " ret void\n"
1624 "}\n"
1625 "define void @b() {\n"
1626 "entry:\n"
1627 " store void()* @c, void()** undef\n"
1628 " call void @d()\n"
1629 " ret void\n"
1630 "}\n"
1631 "define void @c() {\n"
1632 "entry:\n"
1633 " store void()* @b, void()** undef\n"
1634 " call void @d()\n"
1635 " ret void\n"
1636 "}\n"
1637 "define void @d() {\n"
1638 "entry:\n"
1639 " store void()* @a, void()** undef\n"
1640 " ret void\n"
1641 "}\n");
1642 LazyCallGraph CG = buildCG(*M);
1643
1644 // Force the graph to be fully expanded.
1645 CG.buildRefSCCs();
1646 auto I = CG.postorder_ref_scc_begin();
1647 LazyCallGraph::RefSCC &RC = *I++;
1648 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1649
1650 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1651 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1652 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1653 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1654 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1655 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
1656 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1657 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1658
1659 // Check the initial post-order. Note that B and C could be flipped here (and
1660 // in our mutation) without changing the nature of this test.
1661 ASSERT_EQ(4, RC.size());
1662 EXPECT_EQ(&DC, &RC[0]);
1663 EXPECT_EQ(&BC, &RC[1]);
1664 EXPECT_EQ(&CC, &RC[2]);
1665 EXPECT_EQ(&AC, &RC[3]);
1666
1667 // Switch the ref edge from A -> D to a call edge. This should have no
1668 // effect as it is already in postorder and no new cycles are formed.
1669 EXPECT_FALSE(RC.switchInternalEdgeToCall(A, D));
1670 ASSERT_EQ(4, RC.size());
1671 EXPECT_EQ(&DC, &RC[0]);
1672 EXPECT_EQ(&BC, &RC[1]);
1673 EXPECT_EQ(&CC, &RC[2]);
1674 EXPECT_EQ(&AC, &RC[3]);
1675
1676 // Switch B -> C to a call edge. This doesn't form any new cycles but does
1677 // require reordering the SCCs.
1678 EXPECT_FALSE(RC.switchInternalEdgeToCall(B, C));
1679 ASSERT_EQ(4, RC.size());
1680 EXPECT_EQ(&DC, &RC[0]);
1681 EXPECT_EQ(&CC, &RC[1]);
1682 EXPECT_EQ(&BC, &RC[2]);
1683 EXPECT_EQ(&AC, &RC[3]);
1684
1685 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs.
1686 EXPECT_TRUE(RC.switchInternalEdgeToCall(C, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1687 ASSERT_EQ(1u, MergedCs.size());
1688 EXPECT_EQ(&CC, MergedCs[0]);
1689 }));
1690 ASSERT_EQ(3, RC.size());
1691 EXPECT_EQ(&DC, &RC[0]);
1692 EXPECT_EQ(&BC, &RC[1]);
1693 EXPECT_EQ(&AC, &RC[2]);
1694 EXPECT_EQ(2, BC.size());
1695 EXPECT_EQ(&BC, CG.lookupSCC(B));
1696 EXPECT_EQ(&BC, CG.lookupSCC(C));
1697 }
1698
1699 TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) {
1700 LLVMContext Context;
1701 // Test for having a post-order prior to changing a ref edge to a call edge
1702 // with SCCs connecting to the source and connecting to the target, but not
1703 // connecting to both, interleaved between the source and target. This
1704 // ensures we correctly partition the range rather than simply moving one or
1705 // the other.
1706 std::unique_ptr<Module> M =
1707 parseAssembly(Context, "define void @a() {\n"
1708 "entry:\n"
1709 " call void @b1()\n"
1710 " call void @c1()\n"
1711 " ret void\n"
1712 "}\n"
1713 "define void @b1() {\n"
1714 "entry:\n"
1715 " call void @c1()\n"
1716 " call void @b2()\n"
1717 " ret void\n"
1718 "}\n"
1719 "define void @c1() {\n"
1720 "entry:\n"
1721 " call void @b2()\n"
1722 " call void @c2()\n"
1723 " ret void\n"
1724 "}\n"
1725 "define void @b2() {\n"
1726 "entry:\n"
1727 " call void @c2()\n"
1728 " call void @b3()\n"
1729 " ret void\n"
1730 "}\n"
1731 "define void @c2() {\n"
1732 "entry:\n"
1733 " call void @b3()\n"
1734 " call void @c3()\n"
1735 " ret void\n"
1736 "}\n"
1737 "define void @b3() {\n"
1738 "entry:\n"
1739 " call void @c3()\n"
1740 " call void @d()\n"
1741 " ret void\n"
1742 "}\n"
1743 "define void @c3() {\n"
1744 "entry:\n"
1745 " store void()* @b1, void()** undef\n"
1746 " call void @d()\n"
1747 " ret void\n"
1748 "}\n"
1749 "define void @d() {\n"
1750 "entry:\n"
1751 " store void()* @a, void()** undef\n"
1752 " ret void\n"
1753 "}\n");
1754 LazyCallGraph CG = buildCG(*M);
1755
1756 // Force the graph to be fully expanded.
1757 CG.buildRefSCCs();
1758 auto I = CG.postorder_ref_scc_begin();
1759 LazyCallGraph::RefSCC &RC = *I++;
1760 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1761
1762 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1763 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
1764 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
1765 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
1766 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
1767 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
1768 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
1769 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1770 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1771 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1);
1772 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2);
1773 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3);
1774 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1);
1775 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2);
1776 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3);
1777 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1778
1779 // Several call edges are initially present to force a particual post-order.
1780 // Remove them now, leaving an interleaved post-order pattern.
1781 RC.switchTrivialInternalEdgeToRef(B3, C3);
1782 RC.switchTrivialInternalEdgeToRef(C2, B3);
1783 RC.switchTrivialInternalEdgeToRef(B2, C2);
1784 RC.switchTrivialInternalEdgeToRef(C1, B2);
1785 RC.switchTrivialInternalEdgeToRef(B1, C1);
1786
1787 // Check the initial post-order. We ensure this order with the extra edges
1788 // that are nuked above.
1789 ASSERT_EQ(8, RC.size());
1790 EXPECT_EQ(&DC, &RC[0]);
1791 EXPECT_EQ(&C3C, &RC[1]);
1792 EXPECT_EQ(&B3C, &RC[2]);
1793 EXPECT_EQ(&C2C, &RC[3]);
1794 EXPECT_EQ(&B2C, &RC[4]);
1795 EXPECT_EQ(&C1C, &RC[5]);
1796 EXPECT_EQ(&B1C, &RC[6]);
1797 EXPECT_EQ(&AC, &RC[7]);
1798
1799 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does
1800 // require reordering the SCCs in the face of tricky internal node
1801 // structures.
1802 EXPECT_FALSE(RC.switchInternalEdgeToCall(C3, B1));
1803 ASSERT_EQ(8, RC.size());
1804 EXPECT_EQ(&DC, &RC[0]);
1805 EXPECT_EQ(&B3C, &RC[1]);
1806 EXPECT_EQ(&B2C, &RC[2]);
1807 EXPECT_EQ(&B1C, &RC[3]);
1808 EXPECT_EQ(&C3C, &RC[4]);
1809 EXPECT_EQ(&C2C, &RC[5]);
1810 EXPECT_EQ(&C1C, &RC[6]);
1811 EXPECT_EQ(&AC, &RC[7]);
1812 }
1813
1814 TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {
1815 LLVMContext Context;
1816 // Test for having a postorder where between the source and target are all
1817 // three kinds of other SCCs:
1818 // 1) One connected to the target only that have to be shifted below the
1819 // source.
1820 // 2) One connected to the source only that have to be shifted below the
1821 // target.
1822 // 3) One connected to both source and target that has to remain and get
1823 // merged away.
1824 //
1825 // To achieve this we construct a heavily connected graph to force
1826 // a particular post-order. Then we remove the forcing edges and connect
1827 // a cycle.
1828 //
1829 // Diagram for the graph we want on the left and the graph we use to force
1830 // the ordering on the right. Edges ponit down or right.
1831 //
1832 // A | A |
1833 // / \ | / \ |
1834 // B E | B \ |
1835 // |\ | | |\ | |
1836 // | D | | C-D-E |
1837 // | \| | | \| |
1838 // C F | \ F |
1839 // \ / | \ / |
1840 // G | G |
1841 //
1842 // And we form a cycle by connecting F to B.
1843 std::unique_ptr<Module> M =
1844 parseAssembly(Context, "define void @a() {\n"
1845 "entry:\n"
1846 " call void @b()\n"
1847 " call void @e()\n"
1848 " ret void\n"
1849 "}\n"
1850 "define void @b() {\n"
1851 "entry:\n"
1852 " call void @c()\n"
1853 " call void @d()\n"
1854 " ret void\n"
1855 "}\n"
1856 "define void @c() {\n"
1857 "entry:\n"
1858 " call void @d()\n"
1859 " call void @g()\n"
1860 " ret void\n"
1861 "}\n"
1862 "define void @d() {\n"
1863 "entry:\n"
1864 " call void @e()\n"
1865 " call void @f()\n"
1866 " ret void\n"
1867 "}\n"
1868 "define void @e() {\n"
1869 "entry:\n"
1870 " call void @f()\n"
1871 " ret void\n"
1872 "}\n"
1873 "define void @f() {\n"
1874 "entry:\n"
1875 " store void()* @b, void()** undef\n"
1876 " call void @g()\n"
1877 " ret void\n"
1878 "}\n"
1879 "define void @g() {\n"
1880 "entry:\n"
1881 " store void()* @a, void()** undef\n"
1882 " ret void\n"
1883 "}\n");
1884 LazyCallGraph CG = buildCG(*M);
1885
1886 // Force the graph to be fully expanded.
1887 CG.buildRefSCCs();
1888 auto I = CG.postorder_ref_scc_begin();
1889 LazyCallGraph::RefSCC &RC = *I++;
1890 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1891
1892 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1893 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1894 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1895 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1896 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));
1897 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
1898 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
1899 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1900 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
1901 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1902 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1903 LazyCallGraph::SCC &EC = *CG.lookupSCC(E);
1904 LazyCallGraph::SCC &FC = *CG.lookupSCC(F);
1905 LazyCallGraph::SCC &GC = *CG.lookupSCC(G);
1906
1907 // Remove the extra edges that were used to force a particular post-order.
1908 RC.switchTrivialInternalEdgeToRef(C, D);
1909 RC.switchTrivialInternalEdgeToRef(D, E);
1910
1911 // Check the initial post-order. We ensure this order with the extra edges
1912 // that are nuked above.
1913 ASSERT_EQ(7, RC.size());
1914 EXPECT_EQ(&GC, &RC[0]);
1915 EXPECT_EQ(&FC, &RC[1]);
1916 EXPECT_EQ(&EC, &RC[2]);
1917 EXPECT_EQ(&DC, &RC[3]);
1918 EXPECT_EQ(&CC, &RC[4]);
1919 EXPECT_EQ(&BC, &RC[5]);
1920 EXPECT_EQ(&AC, &RC[6]);
1921
1922 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC,
1923 // and has to place the C and E SCCs on either side of it:
1924 // A A |
1925 // / \ / \ |
1926 // B E | E |
1927 // |\ | \ / |
1928 // | D | -> B |
1929 // | \| / \ |
1930 // C F C | |
1931 // \ / \ / |
1932 // G G |
1933 EXPECT_TRUE(RC.switchInternalEdgeToCall(
1934 F, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1935 ASSERT_EQ(2u, MergedCs.size());
1936 EXPECT_EQ(&FC, MergedCs[0]);
1937 EXPECT_EQ(&DC, MergedCs[1]);
1938 }));
1939 EXPECT_EQ(3, BC.size());
1940
1941 // And make sure the postorder was updated.
1942 ASSERT_EQ(5, RC.size());
1943 EXPECT_EQ(&GC, &RC[0]);
1944 EXPECT_EQ(&CC, &RC[1]);
1945 EXPECT_EQ(&BC, &RC[2]);
1946 EXPECT_EQ(&EC, &RC[3]);
1947 EXPECT_EQ(&AC, &RC[4]);
1948 }
1949
1950 // Test for IR containing constants using blockaddress constant expressions.
1951 // These are truly unique constructs: constant expressions with non-constant
1952 // operands.
1953 TEST(LazyCallGraphTest, HandleBlockAddress) {
1954 LLVMContext Context;
1955 std::unique_ptr<Module> M =
1956 parseAssembly(Context, "define void @f() {\n"
1957 "entry:\n"
1958 " ret void\n"
1959 "bb:\n"
1960 " unreachable\n"
1961 "}\n"
1962 "define void @g(i8** %ptr) {\n"
1963 "entry:\n"
1964 " store i8* blockaddress(@f, %bb), i8** %ptr\n"
1965 " ret void\n"
1966 "}\n");
1967 LazyCallGraph CG = buildCG(*M);
1968
1969 CG.buildRefSCCs();
1970 auto I = CG.postorder_ref_scc_begin();
1971 LazyCallGraph::RefSCC &FRC = *I++;
1972 LazyCallGraph::RefSCC &GRC = *I++;
1973 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1974
1975 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
1976 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
1977 EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
1978 EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
1979 EXPECT_TRUE(GRC.isParentOf(FRC));
1980 }
1981
1982 // Test that a blockaddress that refers to itself creates no new RefSCC
1983 // connections. https://bugs.llvm.org/show_bug.cgi?id=40722
1984 TEST(LazyCallGraphTest, HandleBlockAddress2) {
1985 LLVMContext Context;
1986 std::unique_ptr<Module> M =
1987 parseAssembly(Context, "define void @f() {\n"
1988 " ret void\n"
1989 "}\n"
1990 "define void @g(i8** %ptr) {\n"
1991 "bb:\n"
1992 " store i8* blockaddress(@g, %bb), i8** %ptr\n"
1993 " ret void\n"
1994 "}\n");
1995 LazyCallGraph CG = buildCG(*M);
1996
1997 CG.buildRefSCCs();
1998 auto I = CG.postorder_ref_scc_begin();
1999 LazyCallGraph::RefSCC &GRC = *I++;
2000 LazyCallGraph::RefSCC &FRC = *I++;
2001 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2002
2003 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
2004 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
2005 EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
2006 EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
2007 EXPECT_FALSE(GRC.isParentOf(FRC));
2008 EXPECT_FALSE(FRC.isParentOf(GRC));
2009 }
2010
2011 TEST(LazyCallGraphTest, ReplaceNodeFunction) {
2012 LLVMContext Context;
2013 // A graph with several different kinds of edges pointing at a particular
2014 // function.
2015 std::unique_ptr<Module> M =
2016 parseAssembly(Context,
2017 "define void @a(i8** %ptr) {\n"
2018 "entry:\n"
2019 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2020 " ret void\n"
2021 "}\n"
2022 "define void @b(i8** %ptr) {\n"
2023 "entry:\n"
2024 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2025 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2026 " call void @d(i8** %ptr)"
2027 " ret void\n"
2028 "}\n"
2029 "define void @c(i8** %ptr) {\n"
2030 "entry:\n"
2031 " call void @d(i8** %ptr)"
2032 " call void @d(i8** %ptr)"
2033 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2034 " ret void\n"
2035 "}\n"
2036 "define void @d(i8** %ptr) {\n"
2037 "entry:\n"
2038 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
2039 " call void @c(i8** %ptr)"
2040 " call void @d(i8** %ptr)"
2041 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2042 " ret void\n"
2043 "}\n");
2044 LazyCallGraph CG = buildCG(*M);
2045
2046 // Force the graph to be fully expanded.
2047 CG.buildRefSCCs();
2048 auto I = CG.postorder_ref_scc_begin();
2049 LazyCallGraph::RefSCC &RC1 = *I++;
2050 LazyCallGraph::RefSCC &RC2 = *I++;
2051 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2052
2053 ASSERT_EQ(2, RC1.size());
2054 LazyCallGraph::SCC &C1 = RC1[0];
2055 LazyCallGraph::SCC &C2 = RC1[1];
2056
2057 LazyCallGraph::Node &AN = *CG.lookup(lookupFunction(*M, "a"));
2058 LazyCallGraph::Node &BN = *CG.lookup(lookupFunction(*M, "b"));
2059 LazyCallGraph::Node &CN = *CG.lookup(lookupFunction(*M, "c"));
2060 LazyCallGraph::Node &DN = *CG.lookup(lookupFunction(*M, "d"));
2061 EXPECT_EQ(&C1, CG.lookupSCC(DN));
2062 EXPECT_EQ(&C1, CG.lookupSCC(CN));
2063 EXPECT_EQ(&C2, CG.lookupSCC(BN));
2064 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
2065 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
2066 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
2067 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
2068
2069 // Now we need to build a new function 'e' with the same signature as 'd'.
2070 Function &D = DN.getFunction();
2071 Function &E = *Function::Create(D.getFunctionType(), D.getLinkage(), "e");
2072 D.getParent()->getFunctionList().insert(D.getIterator(), &E);
2073
2074 // Change each use of 'd' to use 'e'. This is particularly easy as they have
2075 // the same type.
2076 D.replaceAllUsesWith(&E);
2077
2078 // Splice the body of the old function into the new one.
2079 E.getBasicBlockList().splice(E.begin(), D.getBasicBlockList());
2080 // And fix up the one argument.
2081 D.arg_begin()->replaceAllUsesWith(&*E.arg_begin());
2082 E.arg_begin()->takeName(&*D.arg_begin());
2083
2084 // Now replace the function in the graph.
2085 RC1.replaceNodeFunction(DN, E);
2086
2087 EXPECT_EQ(&E, &DN.getFunction());
2088 EXPECT_EQ(&DN, &(*CN)[DN].getNode());
2089 EXPECT_EQ(&DN, &(*BN)[DN].getNode());
2090 }
2091
2092 TEST(LazyCallGraphTest, RemoveFunctionWithSpurriousRef) {
2093 LLVMContext Context;
2094 // A graph with a couple of RefSCCs.
2095 std::unique_ptr<Module> M =
2096 parseAssembly(Context,
2097 "define void @a(i8** %ptr) {\n"
2098 "entry:\n"
2099 " store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2100 " ret void\n"
2101 "}\n"
2102 "define void @b(i8** %ptr) {\n"
2103 "entry:\n"
2104 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
2105 " ret void\n"
2106 "}\n"
2107 "define void @c(i8** %ptr) {\n"
2108 "entry:\n"
2109 " call void @d(i8** %ptr)"
2110 " ret void\n"
2111 "}\n"
2112 "define void @d(i8** %ptr) {\n"
2113 "entry:\n"
2114 " call void @c(i8** %ptr)"
2115 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
2116 " ret void\n"
2117 "}\n"
2118 "define void @dead() {\n"
2119 "entry:\n"
2120 " ret void\n"
2121 "}\n");
2122 LazyCallGraph CG = buildCG(*M);
2123
2124 // Insert spurious ref edges.
2125 LazyCallGraph::Node &AN = CG.get(lookupFunction(*M, "a"));
2126 LazyCallGraph::Node &BN = CG.get(lookupFunction(*M, "b"));
2127 LazyCallGraph::Node &CN = CG.get(lookupFunction(*M, "c"));
2128 LazyCallGraph::Node &DN = CG.get(lookupFunction(*M, "d"));
2129 LazyCallGraph::Node &DeadN = CG.get(lookupFunction(*M, "dead"));
2130 AN.populate();
2131 BN.populate();
2132 CN.populate();
2133 DN.populate();
2134 DeadN.populate();
2135 CG.insertEdge(AN, DeadN, LazyCallGraph::Edge::Ref);
2136 CG.insertEdge(BN, DeadN, LazyCallGraph::Edge::Ref);
2137 CG.insertEdge(CN, DeadN, LazyCallGraph::Edge::Ref);
2138 CG.insertEdge(DN, DeadN, LazyCallGraph::Edge::Ref);
2139
2140 // Force the graph to be fully expanded.
2141 CG.buildRefSCCs();
2142 auto I = CG.postorder_ref_scc_begin();
2143 LazyCallGraph::RefSCC &DeadRC = *I++;
2144 LazyCallGraph::RefSCC &RC1 = *I++;
2145 LazyCallGraph::RefSCC &RC2 = *I++;
2146 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2147
2148 ASSERT_EQ(2, RC1.size());
2149 LazyCallGraph::SCC &C1 = RC1[0];
2150 LazyCallGraph::SCC &C2 = RC1[1];
2151
2152 EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN));
2153 EXPECT_EQ(&C1, CG.lookupSCC(DN));
2154 EXPECT_EQ(&C1, CG.lookupSCC(CN));
2155 EXPECT_EQ(&C2, CG.lookupSCC(BN));
2156 EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
2157 EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
2158 EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
2159 EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
2160
2161 // Now delete 'dead'. There are no uses of this function but there are
2162 // spurious references.
2163 CG.removeDeadFunction(DeadN.getFunction());
2164
2165 // The only observable change should be that the RefSCC is gone from the
2166 // postorder sequence.
2167 I = CG.postorder_ref_scc_begin();
2168 EXPECT_EQ(&RC1, &*I++);
2169 EXPECT_EQ(&RC2, &*I++);
2170 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2171 }
2172 }
The low level virtual machine