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