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