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