1 //===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Analysis/LazyCallGraph.h"
11 #include "llvm/AsmParser/Parser.h"
12 #include "llvm/IR/Function.h"
13 #include "llvm/IR/LLVMContext.h"
14 #include "llvm/IR/Module.h"
15 #include "llvm/Support/ErrorHandling.h"
16 #include "llvm/Support/SourceMgr.h"
17 #include "gtest/gtest.h"
24 std::unique_ptr<Module> parseAssembly(const char *Assembly) {
26 std::unique_ptr<Module> M =
27 parseAssemblyString(Assembly, Error, getGlobalContext());
30 raw_string_ostream OS(ErrMsg);
33 // A failure here means that the test itself is buggy.
35 report_fatal_error(OS.str().c_str());
40 // IR forming a call graph with a diamond of triangle-shaped SCCs:
54 // All call edges go up between SCCs, and clockwise around the SCC.
55 static const char DiamondOfTriangles[] =
56 "define void @a1() {\n"
63 "define void @a2() {\n"
68 "define void @a3() {\n"
73 "define void @b1() {\n"
79 "define void @b2() {\n"
84 "define void @b3() {\n"
89 "define void @c1() {\n"
95 "define void @c2() {\n"
100 "define void @c3() {\n"
105 "define void @d1() {\n"
110 "define void @d2() {\n"
115 "define void @d3() {\n"
121 TEST(LazyCallGraphTest, BasicGraphFormation) {
122 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
123 LazyCallGraph CG(*M);
125 // The order of the entry nodes should be stable w.r.t. the source order of
126 // the IR, and everything in our module is an entry node, so just directly
127 // build variables for each node.
129 LazyCallGraph::Node &A1 = *I++;
130 EXPECT_EQ("a1", A1.getFunction().getName());
131 LazyCallGraph::Node &A2 = *I++;
132 EXPECT_EQ("a2", A2.getFunction().getName());
133 LazyCallGraph::Node &A3 = *I++;
134 EXPECT_EQ("a3", A3.getFunction().getName());
135 LazyCallGraph::Node &B1 = *I++;
136 EXPECT_EQ("b1", B1.getFunction().getName());
137 LazyCallGraph::Node &B2 = *I++;
138 EXPECT_EQ("b2", B2.getFunction().getName());
139 LazyCallGraph::Node &B3 = *I++;
140 EXPECT_EQ("b3", B3.getFunction().getName());
141 LazyCallGraph::Node &C1 = *I++;
142 EXPECT_EQ("c1", C1.getFunction().getName());
143 LazyCallGraph::Node &C2 = *I++;
144 EXPECT_EQ("c2", C2.getFunction().getName());
145 LazyCallGraph::Node &C3 = *I++;
146 EXPECT_EQ("c3", C3.getFunction().getName());
147 LazyCallGraph::Node &D1 = *I++;
148 EXPECT_EQ("d1", D1.getFunction().getName());
149 LazyCallGraph::Node &D2 = *I++;
150 EXPECT_EQ("d2", D2.getFunction().getName());
151 LazyCallGraph::Node &D3 = *I++;
152 EXPECT_EQ("d3", D3.getFunction().getName());
153 EXPECT_EQ(CG.end(), I);
155 // Build vectors and sort them for the rest of the assertions to make them
156 // independent of order.
157 std::vector<std::string> Nodes;
159 for (LazyCallGraph::Node &N : A1)
160 Nodes.push_back(N.getFunction().getName());
161 std::sort(Nodes.begin(), Nodes.end());
162 EXPECT_EQ("a2", Nodes[0]);
163 EXPECT_EQ("b2", Nodes[1]);
164 EXPECT_EQ("c3", Nodes[2]);
167 EXPECT_EQ(A2.end(), std::next(A2.begin()));
168 EXPECT_EQ("a3", A2.begin()->getFunction().getName());
169 EXPECT_EQ(A3.end(), std::next(A3.begin()));
170 EXPECT_EQ("a1", A3.begin()->getFunction().getName());
172 for (LazyCallGraph::Node &N : B1)
173 Nodes.push_back(N.getFunction().getName());
174 std::sort(Nodes.begin(), Nodes.end());
175 EXPECT_EQ("b2", Nodes[0]);
176 EXPECT_EQ("d3", Nodes[1]);
179 EXPECT_EQ(B2.end(), std::next(B2.begin()));
180 EXPECT_EQ("b3", B2.begin()->getFunction().getName());
181 EXPECT_EQ(B3.end(), std::next(B3.begin()));
182 EXPECT_EQ("b1", B3.begin()->getFunction().getName());
184 for (LazyCallGraph::Node &N : C1)
185 Nodes.push_back(N.getFunction().getName());
186 std::sort(Nodes.begin(), Nodes.end());
187 EXPECT_EQ("c2", Nodes[0]);
188 EXPECT_EQ("d2", Nodes[1]);
191 EXPECT_EQ(C2.end(), std::next(C2.begin()));
192 EXPECT_EQ("c3", C2.begin()->getFunction().getName());
193 EXPECT_EQ(C3.end(), std::next(C3.begin()));
194 EXPECT_EQ("c1", C3.begin()->getFunction().getName());
196 EXPECT_EQ(D1.end(), std::next(D1.begin()));
197 EXPECT_EQ("d2", D1.begin()->getFunction().getName());
198 EXPECT_EQ(D2.end(), std::next(D2.begin()));
199 EXPECT_EQ("d3", D2.begin()->getFunction().getName());
200 EXPECT_EQ(D3.end(), std::next(D3.begin()));
201 EXPECT_EQ("d1", D3.begin()->getFunction().getName());
203 // Now lets look at the SCCs.
204 auto SCCI = CG.postorder_scc_begin();
206 LazyCallGraph::SCC &D = *SCCI++;
207 for (LazyCallGraph::Node *N : D)
208 Nodes.push_back(N->getFunction().getName());
209 std::sort(Nodes.begin(), Nodes.end());
210 EXPECT_EQ(3u, Nodes.size());
211 EXPECT_EQ("d1", Nodes[0]);
212 EXPECT_EQ("d2", Nodes[1]);
213 EXPECT_EQ("d3", Nodes[2]);
215 EXPECT_FALSE(D.isParentOf(D));
216 EXPECT_FALSE(D.isChildOf(D));
217 EXPECT_FALSE(D.isAncestorOf(D));
218 EXPECT_FALSE(D.isDescendantOf(D));
220 LazyCallGraph::SCC &C = *SCCI++;
221 for (LazyCallGraph::Node *N : C)
222 Nodes.push_back(N->getFunction().getName());
223 std::sort(Nodes.begin(), Nodes.end());
224 EXPECT_EQ(3u, Nodes.size());
225 EXPECT_EQ("c1", Nodes[0]);
226 EXPECT_EQ("c2", Nodes[1]);
227 EXPECT_EQ("c3", Nodes[2]);
229 EXPECT_TRUE(C.isParentOf(D));
230 EXPECT_FALSE(C.isChildOf(D));
231 EXPECT_TRUE(C.isAncestorOf(D));
232 EXPECT_FALSE(C.isDescendantOf(D));
234 LazyCallGraph::SCC &B = *SCCI++;
235 for (LazyCallGraph::Node *N : B)
236 Nodes.push_back(N->getFunction().getName());
237 std::sort(Nodes.begin(), Nodes.end());
238 EXPECT_EQ(3u, Nodes.size());
239 EXPECT_EQ("b1", Nodes[0]);
240 EXPECT_EQ("b2", Nodes[1]);
241 EXPECT_EQ("b3", Nodes[2]);
243 EXPECT_TRUE(B.isParentOf(D));
244 EXPECT_FALSE(B.isChildOf(D));
245 EXPECT_TRUE(B.isAncestorOf(D));
246 EXPECT_FALSE(B.isDescendantOf(D));
247 EXPECT_FALSE(B.isAncestorOf(C));
248 EXPECT_FALSE(C.isAncestorOf(B));
250 LazyCallGraph::SCC &A = *SCCI++;
251 for (LazyCallGraph::Node *N : A)
252 Nodes.push_back(N->getFunction().getName());
253 std::sort(Nodes.begin(), Nodes.end());
254 EXPECT_EQ(3u, Nodes.size());
255 EXPECT_EQ("a1", Nodes[0]);
256 EXPECT_EQ("a2", Nodes[1]);
257 EXPECT_EQ("a3", Nodes[2]);
259 EXPECT_TRUE(A.isParentOf(B));
260 EXPECT_TRUE(A.isParentOf(C));
261 EXPECT_FALSE(A.isParentOf(D));
262 EXPECT_TRUE(A.isAncestorOf(B));
263 EXPECT_TRUE(A.isAncestorOf(C));
264 EXPECT_TRUE(A.isAncestorOf(D));
266 EXPECT_EQ(CG.postorder_scc_end(), SCCI);
269 static Function &lookupFunction(Module &M, StringRef Name) {
270 for (Function &F : M)
271 if (F.getName() == Name)
273 report_fatal_error("Couldn't find function!");
276 TEST(LazyCallGraphTest, BasicGraphMutation) {
277 std::unique_ptr<Module> M = parseAssembly(
278 "define void @a() {\n"
284 "define void @b() {\n"
288 "define void @c() {\n"
292 LazyCallGraph CG(*M);
294 LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
295 LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
296 EXPECT_EQ(2, std::distance(A.begin(), A.end()));
297 EXPECT_EQ(0, std::distance(B.begin(), B.end()));
299 CG.insertEdge(B, lookupFunction(*M, "c"));
300 EXPECT_EQ(1, std::distance(B.begin(), B.end()));
301 LazyCallGraph::Node &C = *B.begin();
302 EXPECT_EQ(0, std::distance(C.begin(), C.end()));
304 CG.insertEdge(C, B.getFunction());
305 EXPECT_EQ(1, std::distance(C.begin(), C.end()));
306 EXPECT_EQ(&B, &*C.begin());
308 CG.insertEdge(C, C.getFunction());
309 EXPECT_EQ(2, std::distance(C.begin(), C.end()));
310 EXPECT_EQ(&B, &*C.begin());
311 EXPECT_EQ(&C, &*std::next(C.begin()));
313 CG.removeEdge(C, B.getFunction());
314 EXPECT_EQ(1, std::distance(C.begin(), C.end()));
315 EXPECT_EQ(&C, &*C.begin());
317 CG.removeEdge(C, C.getFunction());
318 EXPECT_EQ(0, std::distance(C.begin(), C.end()));
320 CG.removeEdge(B, C.getFunction());
321 EXPECT_EQ(0, std::distance(B.begin(), B.end()));
324 TEST(LazyCallGraphTest, MultiArmSCC) {
325 // Two interlocking cycles. The really useful thing about this SCC is that it
326 // will require Tarjan's DFS to backtrack and finish processing all of the
327 // children of each node in the SCC.
328 std::unique_ptr<Module> M = parseAssembly(
329 "define void @a() {\n"
335 "define void @b() {\n"
340 "define void @c() {\n"
345 "define void @d() {\n"
350 "define void @e() {\n"
355 LazyCallGraph CG(*M);
357 // Force the graph to be fully expanded.
358 auto SCCI = CG.postorder_scc_begin();
359 LazyCallGraph::SCC &SCC = *SCCI++;
360 EXPECT_EQ(CG.postorder_scc_end(), SCCI);
362 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
363 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
364 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
365 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
366 LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));
367 EXPECT_EQ(&SCC, CG.lookupSCC(A));
368 EXPECT_EQ(&SCC, CG.lookupSCC(B));
369 EXPECT_EQ(&SCC, CG.lookupSCC(C));
370 EXPECT_EQ(&SCC, CG.lookupSCC(D));
371 EXPECT_EQ(&SCC, CG.lookupSCC(E));
374 TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) {
375 std::unique_ptr<Module> M = parseAssembly(
376 "define void @a() {\n"
382 "define void @b() {\n"
387 "define void @c() {\n"
392 "define void @d() {\n"
396 LazyCallGraph CG(*M);
398 // Force the graph to be fully expanded.
399 for (LazyCallGraph::SCC &C : CG.postorder_sccs())
402 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
403 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
404 LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
405 LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
406 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
407 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
408 LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
409 LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
410 EXPECT_TRUE(AC.isAncestorOf(BC));
411 EXPECT_TRUE(AC.isAncestorOf(CC));
412 EXPECT_TRUE(AC.isAncestorOf(DC));
413 EXPECT_TRUE(DC.isDescendantOf(AC));
414 EXPECT_TRUE(DC.isDescendantOf(BC));
415 EXPECT_TRUE(DC.isDescendantOf(CC));
417 EXPECT_EQ(2, std::distance(A.begin(), A.end()));
418 AC.insertOutgoingEdge(A, D);
419 EXPECT_EQ(3, std::distance(A.begin(), A.end()));
420 EXPECT_TRUE(AC.isParentOf(DC));
421 EXPECT_EQ(&AC, CG.lookupSCC(A));
422 EXPECT_EQ(&BC, CG.lookupSCC(B));
423 EXPECT_EQ(&CC, CG.lookupSCC(C));
424 EXPECT_EQ(&DC, CG.lookupSCC(D));
427 TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) {
428 // We want to ensure we can add edges even across complex diamond graphs, so
429 // we use the diamond of triangles graph defined above. The ascii diagram is
430 // repeated here for easy reference.
444 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
445 LazyCallGraph CG(*M);
447 // Force the graph to be fully expanded.
448 for (LazyCallGraph::SCC &C : CG.postorder_sccs())
451 LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
452 LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
453 LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
454 LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
455 LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
456 LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
457 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
458 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
459 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
460 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
461 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
462 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
463 LazyCallGraph::SCC &AC = *CG.lookupSCC(A1);
464 LazyCallGraph::SCC &BC = *CG.lookupSCC(B1);
465 LazyCallGraph::SCC &CC = *CG.lookupSCC(C1);
466 LazyCallGraph::SCC &DC = *CG.lookupSCC(D1);
467 ASSERT_EQ(&AC, CG.lookupSCC(A2));
468 ASSERT_EQ(&AC, CG.lookupSCC(A3));
469 ASSERT_EQ(&BC, CG.lookupSCC(B2));
470 ASSERT_EQ(&BC, CG.lookupSCC(B3));
471 ASSERT_EQ(&CC, CG.lookupSCC(C2));
472 ASSERT_EQ(&CC, CG.lookupSCC(C3));
473 ASSERT_EQ(&DC, CG.lookupSCC(D2));
474 ASSERT_EQ(&DC, CG.lookupSCC(D3));
475 ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
477 // Add an edge to make the graph:
490 CC.insertIncomingEdge(D2, C2);
491 // Make sure we connected the nodes.
492 EXPECT_EQ(2, std::distance(D2.begin(), D2.end()));
494 // Make sure we have the correct nodes in the SCC sets.
495 EXPECT_EQ(&AC, CG.lookupSCC(A1));
496 EXPECT_EQ(&AC, CG.lookupSCC(A2));
497 EXPECT_EQ(&AC, CG.lookupSCC(A3));
498 EXPECT_EQ(&BC, CG.lookupSCC(B1));
499 EXPECT_EQ(&BC, CG.lookupSCC(B2));
500 EXPECT_EQ(&BC, CG.lookupSCC(B3));
501 EXPECT_EQ(&CC, CG.lookupSCC(C1));
502 EXPECT_EQ(&CC, CG.lookupSCC(C2));
503 EXPECT_EQ(&CC, CG.lookupSCC(C3));
504 EXPECT_EQ(&CC, CG.lookupSCC(D1));
505 EXPECT_EQ(&CC, CG.lookupSCC(D2));
506 EXPECT_EQ(&CC, CG.lookupSCC(D3));
508 // And that ancestry tests have been updated.
509 EXPECT_TRUE(AC.isParentOf(BC));
510 EXPECT_TRUE(AC.isParentOf(CC));
511 EXPECT_FALSE(AC.isAncestorOf(DC));
512 EXPECT_FALSE(BC.isAncestorOf(DC));
513 EXPECT_FALSE(CC.isAncestorOf(DC));
516 TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) {
517 // This is the same fundamental test as the previous, but we perform it
518 // having only partially walked the SCCs of the graph.
519 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
520 LazyCallGraph CG(*M);
522 // Walk the SCCs until we find the one containing 'c1'.
523 auto SCCI = CG.postorder_scc_begin(), SCCE = CG.postorder_scc_end();
524 ASSERT_NE(SCCI, SCCE);
525 LazyCallGraph::SCC &DC = *SCCI;
526 ASSERT_NE(&DC, nullptr);
528 ASSERT_NE(SCCI, SCCE);
529 LazyCallGraph::SCC &CC = *SCCI;
530 ASSERT_NE(&CC, nullptr);
532 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1")));
533 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2")));
534 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3")));
535 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1")));
536 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2")));
537 ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3")));
538 LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
539 LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
540 LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
541 LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
542 LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
543 LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
544 ASSERT_EQ(&CC, CG.lookupSCC(C1));
545 ASSERT_EQ(&CC, CG.lookupSCC(C2));
546 ASSERT_EQ(&CC, CG.lookupSCC(C3));
547 ASSERT_EQ(&DC, CG.lookupSCC(D1));
548 ASSERT_EQ(&DC, CG.lookupSCC(D2));
549 ASSERT_EQ(&DC, CG.lookupSCC(D3));
550 ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
552 CC.insertIncomingEdge(D2, C2);
553 EXPECT_EQ(2, std::distance(D2.begin(), D2.end()));
555 // Make sure we have the correct nodes in the SCC sets.
556 EXPECT_EQ(&CC, CG.lookupSCC(C1));
557 EXPECT_EQ(&CC, CG.lookupSCC(C2));
558 EXPECT_EQ(&CC, CG.lookupSCC(C3));
559 EXPECT_EQ(&CC, CG.lookupSCC(D1));
560 EXPECT_EQ(&CC, CG.lookupSCC(D2));
561 EXPECT_EQ(&CC, CG.lookupSCC(D3));
563 // Check that we can form the last two SCCs now in a coherent way.
565 EXPECT_NE(SCCI, SCCE);
566 LazyCallGraph::SCC &BC = *SCCI;
567 EXPECT_NE(&BC, nullptr);
568 EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b1"))));
569 EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b2"))));
570 EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b3"))));
572 EXPECT_NE(SCCI, SCCE);
573 LazyCallGraph::SCC &AC = *SCCI;
574 EXPECT_NE(&AC, nullptr);
575 EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a1"))));
576 EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a2"))));
577 EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a3"))));
579 EXPECT_EQ(SCCI, SCCE);
582 TEST(LazyCallGraphTest, InterSCCEdgeRemoval) {
583 std::unique_ptr<Module> M = parseAssembly(
584 "define void @a() {\n"
589 "define void @b() {\n"
593 LazyCallGraph CG(*M);
595 // Force the graph to be fully expanded.
596 for (LazyCallGraph::SCC &C : CG.postorder_sccs())
599 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
600 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
601 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
602 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
604 EXPECT_EQ("b", A.begin()->getFunction().getName());
605 EXPECT_EQ(B.end(), B.begin());
606 EXPECT_EQ(&AC, &*BC.parent_begin());
608 AC.removeInterSCCEdge(A, B);
610 EXPECT_EQ(A.end(), A.begin());
611 EXPECT_EQ(B.end(), B.begin());
612 EXPECT_EQ(BC.parent_end(), BC.parent_begin());
615 TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) {
616 std::unique_ptr<Module> M1 = parseAssembly(
617 "define void @a() {\n"
622 "define void @b() {\n"
627 "define void @c() {\n"
632 LazyCallGraph CG1(*M1);
634 // Force the graph to be fully expanded.
635 auto SCCI = CG1.postorder_scc_begin();
636 LazyCallGraph::SCC &SCC = *SCCI++;
637 EXPECT_EQ(CG1.postorder_scc_end(), SCCI);
639 LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a"));
640 LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b"));
641 LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c"));
642 EXPECT_EQ(&SCC, CG1.lookupSCC(A));
643 EXPECT_EQ(&SCC, CG1.lookupSCC(B));
644 EXPECT_EQ(&SCC, CG1.lookupSCC(C));
646 // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs.
647 SCC.insertIntraSCCEdge(A, C);
648 EXPECT_EQ(2, std::distance(A.begin(), A.end()));
649 EXPECT_EQ(&SCC, CG1.lookupSCC(A));
650 EXPECT_EQ(&SCC, CG1.lookupSCC(B));
651 EXPECT_EQ(&SCC, CG1.lookupSCC(C));
653 // Insert a self edge from 'a' back to 'a'.
654 SCC.insertIntraSCCEdge(A, A);
655 EXPECT_EQ(3, std::distance(A.begin(), A.end()));
656 EXPECT_EQ(&SCC, CG1.lookupSCC(A));
657 EXPECT_EQ(&SCC, CG1.lookupSCC(B));
658 EXPECT_EQ(&SCC, CG1.lookupSCC(C));
661 TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
662 // A nice fully connected (including self-edges) SCC.
663 std::unique_ptr<Module> M1 = parseAssembly(
664 "define void @a() {\n"
671 "define void @b() {\n"
678 "define void @c() {\n"
685 LazyCallGraph CG1(*M1);
687 // Force the graph to be fully expanded.
688 auto SCCI = CG1.postorder_scc_begin();
689 LazyCallGraph::SCC &SCC = *SCCI++;
690 EXPECT_EQ(CG1.postorder_scc_end(), SCCI);
692 LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a"));
693 LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b"));
694 LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c"));
695 EXPECT_EQ(&SCC, CG1.lookupSCC(A));
696 EXPECT_EQ(&SCC, CG1.lookupSCC(B));
697 EXPECT_EQ(&SCC, CG1.lookupSCC(C));
699 // Remove the edge from b -> a, which should leave the 3 functions still in
700 // a single connected component because of a -> b -> c -> a.
701 SmallVector<LazyCallGraph::SCC *, 1> NewSCCs = SCC.removeIntraSCCEdge(B, A);
702 EXPECT_EQ(0u, NewSCCs.size());
703 EXPECT_EQ(&SCC, CG1.lookupSCC(A));
704 EXPECT_EQ(&SCC, CG1.lookupSCC(B));
705 EXPECT_EQ(&SCC, CG1.lookupSCC(C));
707 // Remove the edge from c -> a, which should leave 'a' in the original SCC
708 // and form a new SCC for 'b' and 'c'.
709 NewSCCs = SCC.removeIntraSCCEdge(C, A);
710 EXPECT_EQ(1u, NewSCCs.size());
711 EXPECT_EQ(&SCC, CG1.lookupSCC(A));
712 EXPECT_EQ(1, std::distance(SCC.begin(), SCC.end()));
713 LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B);
714 EXPECT_EQ(SCC2, CG1.lookupSCC(C));
715 EXPECT_EQ(SCC2, NewSCCs[0]);