1 //===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #include "llvm/Analysis/LazyCallGraph.h"
11 #include "llvm/AsmParser/Parser.h"
12 #include "llvm/IR/Function.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
parseAssembly(LLVMContext & Context,const char * Assembly)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
TEST(LazyCallGraphTest,BasicGraphFormation)123 TEST(LazyCallGraphTest, BasicGraphFormation) {
124 LLVMContext Context;
125 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
126 LazyCallGraph CG(*M);
127
128 // The order of the entry nodes should be stable w.r.t. the source order of
129 // the IR, and everything in our module is an entry node, so just directly
130 // build variables for each node.
131 auto I = CG.begin();
132 LazyCallGraph::Node &A1 = (I++)->getNode(CG);
133 EXPECT_EQ("a1", A1.getFunction().getName());
134 LazyCallGraph::Node &A2 = (I++)->getNode(CG);
135 EXPECT_EQ("a2", A2.getFunction().getName());
136 LazyCallGraph::Node &A3 = (I++)->getNode(CG);
137 EXPECT_EQ("a3", A3.getFunction().getName());
138 LazyCallGraph::Node &B1 = (I++)->getNode(CG);
139 EXPECT_EQ("b1", B1.getFunction().getName());
140 LazyCallGraph::Node &B2 = (I++)->getNode(CG);
141 EXPECT_EQ("b2", B2.getFunction().getName());
142 LazyCallGraph::Node &B3 = (I++)->getNode(CG);
143 EXPECT_EQ("b3", B3.getFunction().getName());
144 LazyCallGraph::Node &C1 = (I++)->getNode(CG);
145 EXPECT_EQ("c1", C1.getFunction().getName());
146 LazyCallGraph::Node &C2 = (I++)->getNode(CG);
147 EXPECT_EQ("c2", C2.getFunction().getName());
148 LazyCallGraph::Node &C3 = (I++)->getNode(CG);
149 EXPECT_EQ("c3", C3.getFunction().getName());
150 LazyCallGraph::Node &D1 = (I++)->getNode(CG);
151 EXPECT_EQ("d1", D1.getFunction().getName());
152 LazyCallGraph::Node &D2 = (I++)->getNode(CG);
153 EXPECT_EQ("d2", D2.getFunction().getName());
154 LazyCallGraph::Node &D3 = (I++)->getNode(CG);
155 EXPECT_EQ("d3", D3.getFunction().getName());
156 EXPECT_EQ(CG.end(), I);
157
158 // Build vectors and sort them for the rest of the assertions to make them
159 // independent of order.
160 std::vector<std::string> Nodes;
161
162 for (LazyCallGraph::Edge &E : A1)
163 Nodes.push_back(E.getFunction().getName());
164 std::sort(Nodes.begin(), Nodes.end());
165 EXPECT_EQ("a2", Nodes[0]);
166 EXPECT_EQ("b2", Nodes[1]);
167 EXPECT_EQ("c3", Nodes[2]);
168 Nodes.clear();
169
170 EXPECT_EQ(A2.end(), std::next(A2.begin()));
171 EXPECT_EQ("a3", A2.begin()->getFunction().getName());
172 EXPECT_EQ(A3.end(), std::next(A3.begin()));
173 EXPECT_EQ("a1", A3.begin()->getFunction().getName());
174
175 for (LazyCallGraph::Edge &E : B1)
176 Nodes.push_back(E.getFunction().getName());
177 std::sort(Nodes.begin(), Nodes.end());
178 EXPECT_EQ("b2", Nodes[0]);
179 EXPECT_EQ("d3", Nodes[1]);
180 Nodes.clear();
181
182 EXPECT_EQ(B2.end(), std::next(B2.begin()));
183 EXPECT_EQ("b3", B2.begin()->getFunction().getName());
184 EXPECT_EQ(B3.end(), std::next(B3.begin()));
185 EXPECT_EQ("b1", B3.begin()->getFunction().getName());
186
187 for (LazyCallGraph::Edge &E : C1)
188 Nodes.push_back(E.getFunction().getName());
189 std::sort(Nodes.begin(), Nodes.end());
190 EXPECT_EQ("c2", Nodes[0]);
191 EXPECT_EQ("d2", Nodes[1]);
192 Nodes.clear();
193
194 EXPECT_EQ(C2.end(), std::next(C2.begin()));
195 EXPECT_EQ("c3", C2.begin()->getFunction().getName());
196 EXPECT_EQ(C3.end(), std::next(C3.begin()));
197 EXPECT_EQ("c1", C3.begin()->getFunction().getName());
198
199 EXPECT_EQ(D1.end(), std::next(D1.begin()));
200 EXPECT_EQ("d2", D1.begin()->getFunction().getName());
201 EXPECT_EQ(D2.end(), std::next(D2.begin()));
202 EXPECT_EQ("d3", D2.begin()->getFunction().getName());
203 EXPECT_EQ(D3.end(), std::next(D3.begin()));
204 EXPECT_EQ("d1", D3.begin()->getFunction().getName());
205
206 // Now lets look at the RefSCCs and SCCs.
207 auto J = CG.postorder_ref_scc_begin();
208
209 LazyCallGraph::RefSCC &D = *J++;
210 ASSERT_EQ(1, D.size());
211 for (LazyCallGraph::Node &N : *D.begin())
212 Nodes.push_back(N.getFunction().getName());
213 std::sort(Nodes.begin(), Nodes.end());
214 EXPECT_EQ(3u, Nodes.size());
215 EXPECT_EQ("d1", Nodes[0]);
216 EXPECT_EQ("d2", Nodes[1]);
217 EXPECT_EQ("d3", Nodes[2]);
218 Nodes.clear();
219 EXPECT_FALSE(D.isParentOf(D));
220 EXPECT_FALSE(D.isChildOf(D));
221 EXPECT_FALSE(D.isAncestorOf(D));
222 EXPECT_FALSE(D.isDescendantOf(D));
223
224 LazyCallGraph::RefSCC &C = *J++;
225 ASSERT_EQ(1, C.size());
226 for (LazyCallGraph::Node &N : *C.begin())
227 Nodes.push_back(N.getFunction().getName());
228 std::sort(Nodes.begin(), Nodes.end());
229 EXPECT_EQ(3u, Nodes.size());
230 EXPECT_EQ("c1", Nodes[0]);
231 EXPECT_EQ("c2", Nodes[1]);
232 EXPECT_EQ("c3", Nodes[2]);
233 Nodes.clear();
234 EXPECT_TRUE(C.isParentOf(D));
235 EXPECT_FALSE(C.isChildOf(D));
236 EXPECT_TRUE(C.isAncestorOf(D));
237 EXPECT_FALSE(C.isDescendantOf(D));
238
239 LazyCallGraph::RefSCC &B = *J++;
240 ASSERT_EQ(1, B.size());
241 for (LazyCallGraph::Node &N : *B.begin())
242 Nodes.push_back(N.getFunction().getName());
243 std::sort(Nodes.begin(), Nodes.end());
244 EXPECT_EQ(3u, Nodes.size());
245 EXPECT_EQ("b1", Nodes[0]);
246 EXPECT_EQ("b2", Nodes[1]);
247 EXPECT_EQ("b3", Nodes[2]);
248 Nodes.clear();
249 EXPECT_TRUE(B.isParentOf(D));
250 EXPECT_FALSE(B.isChildOf(D));
251 EXPECT_TRUE(B.isAncestorOf(D));
252 EXPECT_FALSE(B.isDescendantOf(D));
253 EXPECT_FALSE(B.isAncestorOf(C));
254 EXPECT_FALSE(C.isAncestorOf(B));
255
256 LazyCallGraph::RefSCC &A = *J++;
257 ASSERT_EQ(1, A.size());
258 for (LazyCallGraph::Node &N : *A.begin())
259 Nodes.push_back(N.getFunction().getName());
260 std::sort(Nodes.begin(), Nodes.end());
261 EXPECT_EQ(3u, Nodes.size());
262 EXPECT_EQ("a1", Nodes[0]);
263 EXPECT_EQ("a2", Nodes[1]);
264 EXPECT_EQ("a3", Nodes[2]);
265 Nodes.clear();
266 EXPECT_TRUE(A.isParentOf(B));
267 EXPECT_TRUE(A.isParentOf(C));
268 EXPECT_FALSE(A.isParentOf(D));
269 EXPECT_TRUE(A.isAncestorOf(B));
270 EXPECT_TRUE(A.isAncestorOf(C));
271 EXPECT_TRUE(A.isAncestorOf(D));
272
273 EXPECT_EQ(CG.postorder_ref_scc_end(), J);
274 }
275
lookupFunction(Module & M,StringRef Name)276 static Function &lookupFunction(Module &M, StringRef Name) {
277 for (Function &F : M)
278 if (F.getName() == Name)
279 return F;
280 report_fatal_error("Couldn't find function!");
281 }
282
TEST(LazyCallGraphTest,BasicGraphMutation)283 TEST(LazyCallGraphTest, BasicGraphMutation) {
284 LLVMContext Context;
285 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
286 "entry:\n"
287 " call void @b()\n"
288 " call void @c()\n"
289 " ret void\n"
290 "}\n"
291 "define void @b() {\n"
292 "entry:\n"
293 " ret void\n"
294 "}\n"
295 "define void @c() {\n"
296 "entry:\n"
297 " ret void\n"
298 "}\n");
299 LazyCallGraph CG(*M);
300
301 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
302 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
303 EXPECT_EQ(2, std::distance(A.begin(), A.end()));
304 EXPECT_EQ(0, std::distance(B.begin(), B.end()));
305
306 CG.insertEdge(B, lookupFunction(*M, "c"), LazyCallGraph::Edge::Call);
307 EXPECT_EQ(1, std::distance(B.begin(), B.end()));
308 LazyCallGraph::Node &C = B.begin()->getNode(CG);
309 EXPECT_EQ(0, std::distance(C.begin(), C.end()));
310
311 CG.insertEdge(C, B.getFunction(), LazyCallGraph::Edge::Call);
312 EXPECT_EQ(1, std::distance(C.begin(), C.end()));
313 EXPECT_EQ(&B, C.begin()->getNode());
314
315 CG.insertEdge(C, C.getFunction(), LazyCallGraph::Edge::Call);
316 EXPECT_EQ(2, std::distance(C.begin(), C.end()));
317 EXPECT_EQ(&B, C.begin()->getNode());
318 EXPECT_EQ(&C, std::next(C.begin())->getNode());
319
320 CG.removeEdge(C, B.getFunction());
321 EXPECT_EQ(1, std::distance(C.begin(), C.end()));
322 EXPECT_EQ(&C, C.begin()->getNode());
323
324 CG.removeEdge(C, C.getFunction());
325 EXPECT_EQ(0, std::distance(C.begin(), C.end()));
326
327 CG.removeEdge(B, C.getFunction());
328 EXPECT_EQ(0, std::distance(B.begin(), B.end()));
329 }
330
TEST(LazyCallGraphTest,InnerSCCFormation)331 TEST(LazyCallGraphTest, InnerSCCFormation) {
332 LLVMContext Context;
333 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
334 LazyCallGraph CG(*M);
335
336 // Now mutate the graph to connect every node into a single RefSCC to ensure
337 // that our inner SCC formation handles the rest.
338 CG.insertEdge(lookupFunction(*M, "d1"), lookupFunction(*M, "a1"),
339 LazyCallGraph::Edge::Ref);
340
341 // Build vectors and sort them for the rest of the assertions to make them
342 // independent of order.
343 std::vector<std::string> Nodes;
344
345 // We should build a single RefSCC for the entire graph.
346 auto I = CG.postorder_ref_scc_begin();
347 LazyCallGraph::RefSCC &RC = *I++;
348 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
349
350 // Now walk the four SCCs which should be in post-order.
351 auto J = RC.begin();
352 LazyCallGraph::SCC &D = *J++;
353 for (LazyCallGraph::Node &N : D)
354 Nodes.push_back(N.getFunction().getName());
355 std::sort(Nodes.begin(), Nodes.end());
356 EXPECT_EQ(3u, Nodes.size());
357 EXPECT_EQ("d1", Nodes[0]);
358 EXPECT_EQ("d2", Nodes[1]);
359 EXPECT_EQ("d3", Nodes[2]);
360 Nodes.clear();
361
362 LazyCallGraph::SCC &B = *J++;
363 for (LazyCallGraph::Node &N : B)
364 Nodes.push_back(N.getFunction().getName());
365 std::sort(Nodes.begin(), Nodes.end());
366 EXPECT_EQ(3u, Nodes.size());
367 EXPECT_EQ("b1", Nodes[0]);
368 EXPECT_EQ("b2", Nodes[1]);
369 EXPECT_EQ("b3", Nodes[2]);
370 Nodes.clear();
371
372 LazyCallGraph::SCC &C = *J++;
373 for (LazyCallGraph::Node &N : C)
374 Nodes.push_back(N.getFunction().getName());
375 std::sort(Nodes.begin(), Nodes.end());
376 EXPECT_EQ(3u, Nodes.size());
377 EXPECT_EQ("c1", Nodes[0]);
378 EXPECT_EQ("c2", Nodes[1]);
379 EXPECT_EQ("c3", Nodes[2]);
380 Nodes.clear();
381
382 LazyCallGraph::SCC &A = *J++;
383 for (LazyCallGraph::Node &N : A)
384 Nodes.push_back(N.getFunction().getName());
385 std::sort(Nodes.begin(), Nodes.end());
386 EXPECT_EQ(3u, Nodes.size());
387 EXPECT_EQ("a1", Nodes[0]);
388 EXPECT_EQ("a2", Nodes[1]);
389 EXPECT_EQ("a3", Nodes[2]);
390 Nodes.clear();
391
392 EXPECT_EQ(RC.end(), J);
393 }
394
TEST(LazyCallGraphTest,MultiArmSCC)395 TEST(LazyCallGraphTest, MultiArmSCC) {
396 LLVMContext Context;
397 // Two interlocking cycles. The really useful thing about this SCC is that it
398 // will require Tarjan's DFS to backtrack and finish processing all of the
399 // children of each node in the SCC. Since this involves call edges, both
400 // Tarjan implementations will have to successfully navigate the structure.
401 std::unique_ptr<Module> M = parseAssembly(Context, "define void @f1() {\n"
402 "entry:\n"
403 " call void @f2()\n"
404 " call void @f4()\n"
405 " ret void\n"
406 "}\n"
407 "define void @f2() {\n"
408 "entry:\n"
409 " call void @f3()\n"
410 " ret void\n"
411 "}\n"
412 "define void @f3() {\n"
413 "entry:\n"
414 " call void @f1()\n"
415 " ret void\n"
416 "}\n"
417 "define void @f4() {\n"
418 "entry:\n"
419 " call void @f5()\n"
420 " ret void\n"
421 "}\n"
422 "define void @f5() {\n"
423 "entry:\n"
424 " call void @f1()\n"
425 " ret void\n"
426 "}\n");
427 LazyCallGraph CG(*M);
428
429 // Force the graph to be fully expanded.
430 auto I = CG.postorder_ref_scc_begin();
431 LazyCallGraph::RefSCC &RC = *I++;
432 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
433
434 LazyCallGraph::Node &N1 = *CG.lookup(lookupFunction(*M, "f1"));
435 LazyCallGraph::Node &N2 = *CG.lookup(lookupFunction(*M, "f2"));
436 LazyCallGraph::Node &N3 = *CG.lookup(lookupFunction(*M, "f3"));
437 LazyCallGraph::Node &N4 = *CG.lookup(lookupFunction(*M, "f4"));
438 LazyCallGraph::Node &N5 = *CG.lookup(lookupFunction(*M, "f4"));
439 EXPECT_EQ(&RC, CG.lookupRefSCC(N1));
440 EXPECT_EQ(&RC, CG.lookupRefSCC(N2));
441 EXPECT_EQ(&RC, CG.lookupRefSCC(N3));
442 EXPECT_EQ(&RC, CG.lookupRefSCC(N4));
443 EXPECT_EQ(&RC, CG.lookupRefSCC(N5));
444
445 ASSERT_EQ(1, RC.size());
446
447 LazyCallGraph::SCC &C = *RC.begin();
448 EXPECT_EQ(&C, CG.lookupSCC(N1));
449 EXPECT_EQ(&C, CG.lookupSCC(N2));
450 EXPECT_EQ(&C, CG.lookupSCC(N3));
451 EXPECT_EQ(&C, CG.lookupSCC(N4));
452 EXPECT_EQ(&C, CG.lookupSCC(N5));
453 }
454
TEST(LazyCallGraphTest,OutgoingEdgeMutation)455 TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
456 LLVMContext Context;
457 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
458 "entry:\n"
459 " call void @b()\n"
460 " call void @c()\n"
461 " ret void\n"
462 "}\n"
463 "define void @b() {\n"
464 "entry:\n"
465 " call void @d()\n"
466 " ret void\n"
467 "}\n"
468 "define void @c() {\n"
469 "entry:\n"
470 " call void @d()\n"
471 " ret void\n"
472 "}\n"
473 "define void @d() {\n"
474 "entry:\n"
475 " ret void\n"
476 "}\n");
477 LazyCallGraph CG(*M);
478
479 // Force the graph to be fully expanded.
480 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
481 (void)RC;
482
483 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
484 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
485 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
486 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
487 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
488 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
489 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
490 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
491 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A);
492 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B);
493 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C);
494 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D);
495 EXPECT_TRUE(ARC.isParentOf(BRC));
496 EXPECT_TRUE(ARC.isParentOf(CRC));
497 EXPECT_FALSE(ARC.isParentOf(DRC));
498 EXPECT_TRUE(ARC.isAncestorOf(DRC));
499 EXPECT_FALSE(DRC.isChildOf(ARC));
500 EXPECT_TRUE(DRC.isDescendantOf(ARC));
501 EXPECT_TRUE(DRC.isChildOf(BRC));
502 EXPECT_TRUE(DRC.isChildOf(CRC));
503
504 EXPECT_EQ(2, std::distance(A.begin(), A.end()));
505 ARC.insertOutgoingEdge(A, D, LazyCallGraph::Edge::Call);
506 EXPECT_EQ(3, std::distance(A.begin(), A.end()));
507 const LazyCallGraph::Edge &NewE = A[D];
508 EXPECT_TRUE(NewE);
509 EXPECT_TRUE(NewE.isCall());
510 EXPECT_EQ(&D, NewE.getNode());
511
512 // Only the parent and child tests sholud have changed. The rest of the graph
513 // remains the same.
514 EXPECT_TRUE(ARC.isParentOf(DRC));
515 EXPECT_TRUE(ARC.isAncestorOf(DRC));
516 EXPECT_TRUE(DRC.isChildOf(ARC));
517 EXPECT_TRUE(DRC.isDescendantOf(ARC));
518 EXPECT_EQ(&AC, CG.lookupSCC(A));
519 EXPECT_EQ(&BC, CG.lookupSCC(B));
520 EXPECT_EQ(&CC, CG.lookupSCC(C));
521 EXPECT_EQ(&DC, CG.lookupSCC(D));
522 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
523 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
524 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
525 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
526
527 ARC.switchOutgoingEdgeToRef(A, D);
528 EXPECT_FALSE(NewE.isCall());
529
530 // Verify the graph remains the same.
531 EXPECT_TRUE(ARC.isParentOf(DRC));
532 EXPECT_TRUE(ARC.isAncestorOf(DRC));
533 EXPECT_TRUE(DRC.isChildOf(ARC));
534 EXPECT_TRUE(DRC.isDescendantOf(ARC));
535 EXPECT_EQ(&AC, CG.lookupSCC(A));
536 EXPECT_EQ(&BC, CG.lookupSCC(B));
537 EXPECT_EQ(&CC, CG.lookupSCC(C));
538 EXPECT_EQ(&DC, CG.lookupSCC(D));
539 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
540 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
541 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
542 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
543
544 ARC.switchOutgoingEdgeToCall(A, D);
545 EXPECT_TRUE(NewE.isCall());
546
547 // Verify the graph remains the same.
548 EXPECT_TRUE(ARC.isParentOf(DRC));
549 EXPECT_TRUE(ARC.isAncestorOf(DRC));
550 EXPECT_TRUE(DRC.isChildOf(ARC));
551 EXPECT_TRUE(DRC.isDescendantOf(ARC));
552 EXPECT_EQ(&AC, CG.lookupSCC(A));
553 EXPECT_EQ(&BC, CG.lookupSCC(B));
554 EXPECT_EQ(&CC, CG.lookupSCC(C));
555 EXPECT_EQ(&DC, CG.lookupSCC(D));
556 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
557 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
558 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
559 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
560
561 ARC.removeOutgoingEdge(A, D);
562 EXPECT_EQ(2, std::distance(A.begin(), A.end()));
563
564 // Now the parent and child tests fail again but the rest remains the same.
565 EXPECT_FALSE(ARC.isParentOf(DRC));
566 EXPECT_TRUE(ARC.isAncestorOf(DRC));
567 EXPECT_FALSE(DRC.isChildOf(ARC));
568 EXPECT_TRUE(DRC.isDescendantOf(ARC));
569 EXPECT_EQ(&AC, CG.lookupSCC(A));
570 EXPECT_EQ(&BC, CG.lookupSCC(B));
571 EXPECT_EQ(&CC, CG.lookupSCC(C));
572 EXPECT_EQ(&DC, CG.lookupSCC(D));
573 EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
574 EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
575 EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
576 EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
577 }
578
TEST(LazyCallGraphTest,IncomingEdgeInsertion)579 TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
580 LLVMContext Context;
581 // We want to ensure we can add edges even across complex diamond graphs, so
582 // we use the diamond of triangles graph defined above. The ascii diagram is
583 // repeated here for easy reference.
584 //
585 // d1 |
586 // / \ |
587 // d3--d2 |
588 // / \ |
589 // b1 c1 |
590 // / \ / \ |
591 // b3--b2 c3--c2 |
592 // \ / |
593 // a1 |
594 // / \ |
595 // a3--a2 |
596 //
597 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
598 LazyCallGraph CG(*M);
599
600 // Force the graph to be fully expanded.
601 for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
602 (void)RC;
603
604 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
605 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
606 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
607 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
608 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
609 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
610 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
611 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
612 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
613 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
614 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
615 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
616 LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(A1);
617 LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(B1);
618 LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(C1);
619 LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(D1);
620 ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
621 ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
622 ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
623 ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
624 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
625 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
626 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
627 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
628 ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
629
630 // Add an edge to make the graph:
631 //
632 // d1 |
633 // / \ |
634 // d3--d2---. |
635 // / \ | |
636 // b1 c1 | |
637 // / \ / \ / |
638 // b3--b2 c3--c2 |
639 // \ / |
640 // a1 |
641 // / \ |
642 // a3--a2 |
643 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
644 // Make sure we connected the nodes.
645 for (LazyCallGraph::Edge E : D2) {
646 if (E.getNode() == &D3)
647 continue;
648 EXPECT_EQ(&C2, E.getNode());
649 }
650 // And marked the D ref-SCC as no longer valid.
651 EXPECT_EQ(1u, MergedRCs.size());
652 EXPECT_EQ(&DRC, MergedRCs[0]);
653
654 // Make sure we have the correct nodes in the SCC sets.
655 EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
656 EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
657 EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
658 EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
659 EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
660 EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
661 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
662 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
663 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
664 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
665 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
666 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
667
668 // And that ancestry tests have been updated.
669 EXPECT_TRUE(ARC.isParentOf(CRC));
670 EXPECT_TRUE(BRC.isParentOf(CRC));
671 }
672
TEST(LazyCallGraphTest,IncomingEdgeInsertionMidTraversal)673 TEST(LazyCallGraphTest, IncomingEdgeInsertionMidTraversal) {
674 LLVMContext Context;
675 // This is the same fundamental test as the previous, but we perform it
676 // having only partially walked the RefSCCs of the graph.
677 std::unique_ptr<Module> M = parseAssembly(Context, DiamondOfTriangles);
678 LazyCallGraph CG(*M);
679
680 // Walk the RefSCCs until we find the one containing 'c1'.
681 auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
682 ASSERT_NE(I, E);
683 LazyCallGraph::RefSCC &DRC = *I;
684 ASSERT_NE(&DRC, nullptr);
685 ++I;
686 ASSERT_NE(I, E);
687 LazyCallGraph::RefSCC &CRC = *I;
688 ASSERT_NE(&CRC, nullptr);
689
690 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1")));
691 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2")));
692 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3")));
693 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1")));
694 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2")));
695 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3")));
696 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
697 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
698 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
699 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
700 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
701 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
702 ASSERT_EQ(&CRC, CG.lookupRefSCC(C1));
703 ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
704 ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
705 ASSERT_EQ(&DRC, CG.lookupRefSCC(D1));
706 ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
707 ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
708 ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
709
710 auto MergedRCs = CRC.insertIncomingRefEdge(D2, C2);
711 // Make sure we connected the nodes.
712 for (LazyCallGraph::Edge E : D2) {
713 if (E.getNode() == &D3)
714 continue;
715 EXPECT_EQ(&C2, E.getNode());
716 }
717 // And marked the D ref-SCC as no longer valid.
718 EXPECT_EQ(1u, MergedRCs.size());
719 EXPECT_EQ(&DRC, MergedRCs[0]);
720
721 // Make sure we have the correct nodes in the RefSCCs.
722 EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
723 EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
724 EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
725 EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
726 EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
727 EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
728
729 // Check that we can form the last two RefSCCs now in a coherent way.
730 ++I;
731 EXPECT_NE(I, E);
732 LazyCallGraph::RefSCC &BRC = *I;
733 EXPECT_NE(&BRC, nullptr);
734 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b1"))));
735 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b2"))));
736 EXPECT_EQ(&BRC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "b3"))));
737 EXPECT_TRUE(BRC.isParentOf(CRC));
738 ++I;
739 EXPECT_NE(I, E);
740 LazyCallGraph::RefSCC &ARC = *I;
741 EXPECT_NE(&ARC, nullptr);
742 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a1"))));
743 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a2"))));
744 EXPECT_EQ(&ARC, CG.lookupRefSCC(*CG.lookup(lookupFunction(*M, "a3"))));
745 EXPECT_TRUE(ARC.isParentOf(CRC));
746 ++I;
747 EXPECT_EQ(E, I);
748 }
749
TEST(LazyCallGraphTest,InternalEdgeMutation)750 TEST(LazyCallGraphTest, InternalEdgeMutation) {
751 LLVMContext Context;
752 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
753 "entry:\n"
754 " call void @b()\n"
755 " ret void\n"
756 "}\n"
757 "define void @b() {\n"
758 "entry:\n"
759 " call void @c()\n"
760 " ret void\n"
761 "}\n"
762 "define void @c() {\n"
763 "entry:\n"
764 " call void @a()\n"
765 " ret void\n"
766 "}\n");
767 LazyCallGraph CG(*M);
768
769 // Force the graph to be fully expanded.
770 auto I = CG.postorder_ref_scc_begin();
771 LazyCallGraph::RefSCC &RC = *I++;
772 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
773
774 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
775 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
776 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
777 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
778 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
779 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
780 EXPECT_EQ(1, RC.size());
781 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
782 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
783 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
784
785 // Insert an edge from 'a' to 'c'. Nothing changes about the graph.
786 RC.insertInternalRefEdge(A, C);
787 EXPECT_EQ(2, std::distance(A.begin(), A.end()));
788 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
789 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
790 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
791 EXPECT_EQ(1, RC.size());
792 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
793 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
794 EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
795
796 // Switch the call edge from 'b' to 'c' to a ref edge. This will break the
797 // call cycle and cause us to form more SCCs. The RefSCC will remain the same
798 // though.
799 RC.switchInternalEdgeToRef(B, C);
800 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
801 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
802 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
803 auto J = RC.begin();
804 // The SCCs must be in *post-order* which means successors before
805 // predecessors. At this point we have call edges from C to A and from A to
806 // B. The only valid postorder is B, A, C.
807 EXPECT_EQ(&*J++, CG.lookupSCC(B));
808 EXPECT_EQ(&*J++, CG.lookupSCC(A));
809 EXPECT_EQ(&*J++, CG.lookupSCC(C));
810 EXPECT_EQ(RC.end(), J);
811
812 // Test turning the ref edge from A to C into a call edge. This will form an
813 // SCC out of A and C. Since we previously had a call edge from C to A, the
814 // C SCC should be preserved and have A merged into it while the A SCC should
815 // be invalidated.
816 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
817 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
818 auto InvalidatedSCCs = RC.switchInternalEdgeToCall(A, C);
819 ASSERT_EQ(1u, InvalidatedSCCs.size());
820 EXPECT_EQ(&AC, InvalidatedSCCs[0]);
821 EXPECT_EQ(2, CC.size());
822 EXPECT_EQ(&CC, CG.lookupSCC(A));
823 EXPECT_EQ(&CC, CG.lookupSCC(C));
824 J = RC.begin();
825 EXPECT_EQ(&*J++, CG.lookupSCC(B));
826 EXPECT_EQ(&*J++, CG.lookupSCC(C));
827 EXPECT_EQ(RC.end(), J);
828 }
829
TEST(LazyCallGraphTest,InternalEdgeRemoval)830 TEST(LazyCallGraphTest, InternalEdgeRemoval) {
831 LLVMContext Context;
832 // A nice fully connected (including self-edges) RefSCC.
833 std::unique_ptr<Module> M = parseAssembly(
834 Context, "define void @a(i8** %ptr) {\n"
835 "entry:\n"
836 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
837 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
838 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
839 " ret void\n"
840 "}\n"
841 "define void @b(i8** %ptr) {\n"
842 "entry:\n"
843 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
844 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
845 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
846 " ret void\n"
847 "}\n"
848 "define void @c(i8** %ptr) {\n"
849 "entry:\n"
850 " store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
851 " store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
852 " store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
853 " ret void\n"
854 "}\n");
855 LazyCallGraph CG(*M);
856
857 // Force the graph to be fully expanded.
858 auto I = CG.postorder_ref_scc_begin();
859 LazyCallGraph::RefSCC &RC = *I++;
860 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
861
862 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
863 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
864 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
865 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
866 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
867 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
868
869 // Remove the edge from b -> a, which should leave the 3 functions still in
870 // a single connected component because of a -> b -> c -> a.
871 SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
872 RC.removeInternalRefEdge(B, A);
873 EXPECT_EQ(0u, NewRCs.size());
874 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
875 EXPECT_EQ(&RC, CG.lookupRefSCC(B));
876 EXPECT_EQ(&RC, CG.lookupRefSCC(C));
877
878 // Remove the edge from c -> a, which should leave 'a' in the original RefSCC
879 // and form a new RefSCC for 'b' and 'c'.
880 NewRCs = RC.removeInternalRefEdge(C, A);
881 EXPECT_EQ(1u, NewRCs.size());
882 EXPECT_EQ(&RC, CG.lookupRefSCC(A));
883 EXPECT_EQ(1, std::distance(RC.begin(), RC.end()));
884 LazyCallGraph::RefSCC *RC2 = CG.lookupRefSCC(B);
885 EXPECT_EQ(RC2, CG.lookupRefSCC(C));
886 EXPECT_EQ(RC2, NewRCs[0]);
887 }
888
TEST(LazyCallGraphTest,InternalCallEdgeToRef)889 TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
890 LLVMContext Context;
891 // A nice fully connected (including self-edges) SCC (and RefSCC)
892 std::unique_ptr<Module> M = parseAssembly(Context, "define void @a() {\n"
893 "entry:\n"
894 " call void @a()\n"
895 " call void @b()\n"
896 " call void @c()\n"
897 " ret void\n"
898 "}\n"
899 "define void @b() {\n"
900 "entry:\n"
901 " call void @a()\n"
902 " call void @b()\n"
903 " call void @c()\n"
904 " ret void\n"
905 "}\n"
906 "define void @c() {\n"
907 "entry:\n"
908 " call void @a()\n"
909 " call void @b()\n"
910 " call void @c()\n"
911 " ret void\n"
912 "}\n");
913 LazyCallGraph CG(*M);
914
915 // Force the graph to be fully expanded.
916 auto I = CG.postorder_ref_scc_begin();
917 LazyCallGraph::RefSCC &RC = *I++;
918 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
919
920 EXPECT_EQ(1, RC.size());
921 LazyCallGraph::SCC &CallC = *RC.begin();
922
923 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
924 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
925 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
926 EXPECT_EQ(&CallC, CG.lookupSCC(A));
927 EXPECT_EQ(&CallC, CG.lookupSCC(B));
928 EXPECT_EQ(&CallC, CG.lookupSCC(C));
929
930 // Remove the call edge from b -> a to a ref edge, which should leave the
931 // 3 functions still in a single connected component because of a -> b ->
932 // c -> a.
933 RC.switchInternalEdgeToRef(B, A);
934 EXPECT_EQ(1, RC.size());
935 EXPECT_EQ(&CallC, CG.lookupSCC(A));
936 EXPECT_EQ(&CallC, CG.lookupSCC(B));
937 EXPECT_EQ(&CallC, CG.lookupSCC(C));
938
939 // Remove the edge from c -> a, which should leave 'a' in the original SCC
940 // and form a new SCC for 'b' and 'c'.
941 RC.switchInternalEdgeToRef(C, A);
942 EXPECT_EQ(2, RC.size());
943 EXPECT_EQ(&CallC, CG.lookupSCC(A));
944 LazyCallGraph::SCC &BCallC = *CG.lookupSCC(B);
945 EXPECT_NE(&BCallC, &CallC);
946 EXPECT_EQ(&BCallC, CG.lookupSCC(C));
947 auto J = RC.find(CallC);
948 EXPECT_EQ(&CallC, &*J);
949 --J;
950 EXPECT_EQ(&BCallC, &*J);
951 EXPECT_EQ(RC.begin(), J);
952
953 // Remove the edge from c -> b, which should leave 'b' in the original SCC
954 // and form a new SCC for 'c'. It shouldn't change 'a's SCC.
955 RC.switchInternalEdgeToRef(C, B);
956 EXPECT_EQ(3, RC.size());
957 EXPECT_EQ(&CallC, CG.lookupSCC(A));
958 EXPECT_EQ(&BCallC, CG.lookupSCC(B));
959 LazyCallGraph::SCC &CCallC = *CG.lookupSCC(C);
960 EXPECT_NE(&CCallC, &CallC);
961 EXPECT_NE(&CCallC, &BCallC);
962 J = RC.find(CallC);
963 EXPECT_EQ(&CallC, &*J);
964 --J;
965 EXPECT_EQ(&BCallC, &*J);
966 --J;
967 EXPECT_EQ(&CCallC, &*J);
968 EXPECT_EQ(RC.begin(), J);
969 }
970
TEST(LazyCallGraphTest,InternalRefEdgeToCall)971 TEST(LazyCallGraphTest, InternalRefEdgeToCall) {
972 LLVMContext Context;
973 // Basic tests for making a ref edge a call. This hits the basics of the
974 // process only.
975 std::unique_ptr<Module> M =
976 parseAssembly(Context, "define void @a() {\n"
977 "entry:\n"
978 " call void @b()\n"
979 " call void @c()\n"
980 " store void()* @d, void()** undef\n"
981 " ret void\n"
982 "}\n"
983 "define void @b() {\n"
984 "entry:\n"
985 " store void()* @c, void()** undef\n"
986 " call void @d()\n"
987 " ret void\n"
988 "}\n"
989 "define void @c() {\n"
990 "entry:\n"
991 " store void()* @b, void()** undef\n"
992 " call void @d()\n"
993 " ret void\n"
994 "}\n"
995 "define void @d() {\n"
996 "entry:\n"
997 " store void()* @a, void()** undef\n"
998 " ret void\n"
999 "}\n");
1000 LazyCallGraph CG(*M);
1001
1002 // Force the graph to be fully expanded.
1003 auto I = CG.postorder_ref_scc_begin();
1004 LazyCallGraph::RefSCC &RC = *I++;
1005 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1006
1007 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1008 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1009 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1010 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1011 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1012 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
1013 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1014 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1015
1016 // Check the initial post-order. Note that B and C could be flipped here (and
1017 // in our mutation) without changing the nature of this test.
1018 ASSERT_EQ(4, RC.size());
1019 EXPECT_EQ(&DC, &RC[0]);
1020 EXPECT_EQ(&BC, &RC[1]);
1021 EXPECT_EQ(&CC, &RC[2]);
1022 EXPECT_EQ(&AC, &RC[3]);
1023
1024 // Switch the ref edge from A -> D to a call edge. This should have no
1025 // effect as it is already in postorder and no new cycles are formed.
1026 auto MergedCs = RC.switchInternalEdgeToCall(A, D);
1027 EXPECT_EQ(0u, MergedCs.size());
1028 ASSERT_EQ(4, RC.size());
1029 EXPECT_EQ(&DC, &RC[0]);
1030 EXPECT_EQ(&BC, &RC[1]);
1031 EXPECT_EQ(&CC, &RC[2]);
1032 EXPECT_EQ(&AC, &RC[3]);
1033
1034 // Switch B -> C to a call edge. This doesn't form any new cycles but does
1035 // require reordering the SCCs.
1036 MergedCs = RC.switchInternalEdgeToCall(B, C);
1037 EXPECT_EQ(0u, MergedCs.size());
1038 ASSERT_EQ(4, RC.size());
1039 EXPECT_EQ(&DC, &RC[0]);
1040 EXPECT_EQ(&CC, &RC[1]);
1041 EXPECT_EQ(&BC, &RC[2]);
1042 EXPECT_EQ(&AC, &RC[3]);
1043
1044 // Switch C -> B to a call edge. This forms a cycle and forces merging SCCs.
1045 MergedCs = RC.switchInternalEdgeToCall(C, B);
1046 ASSERT_EQ(1u, MergedCs.size());
1047 EXPECT_EQ(&CC, MergedCs[0]);
1048 ASSERT_EQ(3, RC.size());
1049 EXPECT_EQ(&DC, &RC[0]);
1050 EXPECT_EQ(&BC, &RC[1]);
1051 EXPECT_EQ(&AC, &RC[2]);
1052 EXPECT_EQ(2, BC.size());
1053 EXPECT_EQ(&BC, CG.lookupSCC(B));
1054 EXPECT_EQ(&BC, CG.lookupSCC(C));
1055 }
1056
TEST(LazyCallGraphTest,InternalRefEdgeToCallNoCycleInterleaved)1057 TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) {
1058 LLVMContext Context;
1059 // Test for having a post-order prior to changing a ref edge to a call edge
1060 // with SCCs connecting to the source and connecting to the target, but not
1061 // connecting to both, interleaved between the source and target. This
1062 // ensures we correctly partition the range rather than simply moving one or
1063 // the other.
1064 std::unique_ptr<Module> M =
1065 parseAssembly(Context, "define void @a() {\n"
1066 "entry:\n"
1067 " call void @b1()\n"
1068 " call void @c1()\n"
1069 " ret void\n"
1070 "}\n"
1071 "define void @b1() {\n"
1072 "entry:\n"
1073 " call void @c1()\n"
1074 " call void @b2()\n"
1075 " ret void\n"
1076 "}\n"
1077 "define void @c1() {\n"
1078 "entry:\n"
1079 " call void @b2()\n"
1080 " call void @c2()\n"
1081 " ret void\n"
1082 "}\n"
1083 "define void @b2() {\n"
1084 "entry:\n"
1085 " call void @c2()\n"
1086 " call void @b3()\n"
1087 " ret void\n"
1088 "}\n"
1089 "define void @c2() {\n"
1090 "entry:\n"
1091 " call void @b3()\n"
1092 " call void @c3()\n"
1093 " ret void\n"
1094 "}\n"
1095 "define void @b3() {\n"
1096 "entry:\n"
1097 " call void @c3()\n"
1098 " call void @d()\n"
1099 " ret void\n"
1100 "}\n"
1101 "define void @c3() {\n"
1102 "entry:\n"
1103 " store void()* @b1, void()** undef\n"
1104 " call void @d()\n"
1105 " ret void\n"
1106 "}\n"
1107 "define void @d() {\n"
1108 "entry:\n"
1109 " store void()* @a, void()** undef\n"
1110 " ret void\n"
1111 "}\n");
1112 LazyCallGraph CG(*M);
1113
1114 // Force the graph to be fully expanded.
1115 auto I = CG.postorder_ref_scc_begin();
1116 LazyCallGraph::RefSCC &RC = *I++;
1117 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1118
1119 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1120 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
1121 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
1122 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
1123 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
1124 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
1125 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
1126 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1127 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1128 LazyCallGraph::SCC &B1C = *CG.lookupSCC(B1);
1129 LazyCallGraph::SCC &B2C = *CG.lookupSCC(B2);
1130 LazyCallGraph::SCC &B3C = *CG.lookupSCC(B3);
1131 LazyCallGraph::SCC &C1C = *CG.lookupSCC(C1);
1132 LazyCallGraph::SCC &C2C = *CG.lookupSCC(C2);
1133 LazyCallGraph::SCC &C3C = *CG.lookupSCC(C3);
1134 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1135
1136 // Several call edges are initially present to force a particual post-order.
1137 // Remove them now, leaving an interleaved post-order pattern.
1138 RC.switchInternalEdgeToRef(B3, C3);
1139 RC.switchInternalEdgeToRef(C2, B3);
1140 RC.switchInternalEdgeToRef(B2, C2);
1141 RC.switchInternalEdgeToRef(C1, B2);
1142 RC.switchInternalEdgeToRef(B1, C1);
1143
1144 // Check the initial post-order. We ensure this order with the extra edges
1145 // that are nuked above.
1146 ASSERT_EQ(8, RC.size());
1147 EXPECT_EQ(&DC, &RC[0]);
1148 EXPECT_EQ(&C3C, &RC[1]);
1149 EXPECT_EQ(&B3C, &RC[2]);
1150 EXPECT_EQ(&C2C, &RC[3]);
1151 EXPECT_EQ(&B2C, &RC[4]);
1152 EXPECT_EQ(&C1C, &RC[5]);
1153 EXPECT_EQ(&B1C, &RC[6]);
1154 EXPECT_EQ(&AC, &RC[7]);
1155
1156 // Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does
1157 // require reordering the SCCs in the face of tricky internal node
1158 // structures.
1159 auto MergedCs = RC.switchInternalEdgeToCall(C3, B1);
1160 EXPECT_EQ(0u, MergedCs.size());
1161 ASSERT_EQ(8, RC.size());
1162 EXPECT_EQ(&DC, &RC[0]);
1163 EXPECT_EQ(&B3C, &RC[1]);
1164 EXPECT_EQ(&B2C, &RC[2]);
1165 EXPECT_EQ(&B1C, &RC[3]);
1166 EXPECT_EQ(&C3C, &RC[4]);
1167 EXPECT_EQ(&C2C, &RC[5]);
1168 EXPECT_EQ(&C1C, &RC[6]);
1169 EXPECT_EQ(&AC, &RC[7]);
1170 }
1171
TEST(LazyCallGraphTest,InternalRefEdgeToCallBothPartitionAndMerge)1172 TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {
1173 LLVMContext Context;
1174 // Test for having a postorder where between the source and target are all
1175 // three kinds of other SCCs:
1176 // 1) One connected to the target only that have to be shifted below the
1177 // source.
1178 // 2) One connected to the source only that have to be shifted below the
1179 // target.
1180 // 3) One connected to both source and target that has to remain and get
1181 // merged away.
1182 //
1183 // To achieve this we construct a heavily connected graph to force
1184 // a particular post-order. Then we remove the forcing edges and connect
1185 // a cycle.
1186 //
1187 // Diagram for the graph we want on the left and the graph we use to force
1188 // the ordering on the right. Edges ponit down or right.
1189 //
1190 // A | A |
1191 // / \ | / \ |
1192 // B E | B \ |
1193 // |\ | | |\ | |
1194 // | D | | C-D-E |
1195 // | \| | | \| |
1196 // C F | \ F |
1197 // \ / | \ / |
1198 // G | G |
1199 //
1200 // And we form a cycle by connecting F to B.
1201 std::unique_ptr<Module> M =
1202 parseAssembly(Context, "define void @a() {\n"
1203 "entry:\n"
1204 " call void @b()\n"
1205 " call void @e()\n"
1206 " ret void\n"
1207 "}\n"
1208 "define void @b() {\n"
1209 "entry:\n"
1210 " call void @c()\n"
1211 " call void @d()\n"
1212 " ret void\n"
1213 "}\n"
1214 "define void @c() {\n"
1215 "entry:\n"
1216 " call void @d()\n"
1217 " call void @g()\n"
1218 " ret void\n"
1219 "}\n"
1220 "define void @d() {\n"
1221 "entry:\n"
1222 " call void @e()\n"
1223 " call void @f()\n"
1224 " ret void\n"
1225 "}\n"
1226 "define void @e() {\n"
1227 "entry:\n"
1228 " call void @f()\n"
1229 " ret void\n"
1230 "}\n"
1231 "define void @f() {\n"
1232 "entry:\n"
1233 " store void()* @b, void()** undef\n"
1234 " call void @g()\n"
1235 " ret void\n"
1236 "}\n"
1237 "define void @g() {\n"
1238 "entry:\n"
1239 " store void()* @a, void()** undef\n"
1240 " ret void\n"
1241 "}\n");
1242 LazyCallGraph CG(*M);
1243
1244 // Force the graph to be fully expanded.
1245 auto I = CG.postorder_ref_scc_begin();
1246 LazyCallGraph::RefSCC &RC = *I++;
1247 EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1248
1249 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
1250 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
1251 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
1252 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
1253 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));
1254 LazyCallGraph::Node &F = *CG.lookup(lookupFunction(*M, "f"));
1255 LazyCallGraph::Node &G = *CG.lookup(lookupFunction(*M, "g"));
1256 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
1257 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
1258 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
1259 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
1260 LazyCallGraph::SCC &EC = *CG.lookupSCC(E);
1261 LazyCallGraph::SCC &FC = *CG.lookupSCC(F);
1262 LazyCallGraph::SCC &GC = *CG.lookupSCC(G);
1263
1264 // Remove the extra edges that were used to force a particular post-order.
1265 RC.switchInternalEdgeToRef(C, D);
1266 RC.switchInternalEdgeToRef(D, E);
1267
1268 // Check the initial post-order. We ensure this order with the extra edges
1269 // that are nuked above.
1270 ASSERT_EQ(7, RC.size());
1271 EXPECT_EQ(&GC, &RC[0]);
1272 EXPECT_EQ(&FC, &RC[1]);
1273 EXPECT_EQ(&EC, &RC[2]);
1274 EXPECT_EQ(&DC, &RC[3]);
1275 EXPECT_EQ(&CC, &RC[4]);
1276 EXPECT_EQ(&BC, &RC[5]);
1277 EXPECT_EQ(&AC, &RC[6]);
1278
1279 // Switch F -> B to a call edge. This merges B, D, and F into a single SCC,
1280 // and has to place the C and E SCCs on either side of it:
1281 // A A |
1282 // / \ / \ |
1283 // B E | E |
1284 // |\ | \ / |
1285 // | D | -> B |
1286 // | \| / \ |
1287 // C F C | |
1288 // \ / \ / |
1289 // G G |
1290 auto MergedCs = RC.switchInternalEdgeToCall(F, B);
1291 ASSERT_EQ(2u, MergedCs.size());
1292 EXPECT_EQ(&FC, MergedCs[0]);
1293 EXPECT_EQ(&DC, MergedCs[1]);
1294 EXPECT_EQ(3, BC.size());
1295
1296 // And make sure the postorder was updated.
1297 ASSERT_EQ(5, RC.size());
1298 EXPECT_EQ(&GC, &RC[0]);
1299 EXPECT_EQ(&CC, &RC[1]);
1300 EXPECT_EQ(&BC, &RC[2]);
1301 EXPECT_EQ(&EC, &RC[3]);
1302 EXPECT_EQ(&AC, &RC[4]);
1303 }
1304
1305 }
1306