• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/Analysis/LazyCallGraph.h"
11 #include "llvm/AsmParser/Parser.h"
12 #include "llvm/IR/Function.h"
13 #include "llvm/IR/LLVMContext.h"
14 #include "llvm/IR/Module.h"
15 #include "llvm/Support/ErrorHandling.h"
16 #include "llvm/Support/SourceMgr.h"
17 #include "gtest/gtest.h"
18 #include <memory>
19 
20 using namespace llvm;
21 
22 namespace {
23 
parseAssembly(const char * Assembly)24 std::unique_ptr<Module> parseAssembly(const char *Assembly) {
25   SMDiagnostic Error;
26   std::unique_ptr<Module> M =
27       parseAssemblyString(Assembly, Error, getGlobalContext());
28 
29   std::string ErrMsg;
30   raw_string_ostream OS(ErrMsg);
31   Error.print("", OS);
32 
33   // A failure here means that the test itself is buggy.
34   if (!M)
35     report_fatal_error(OS.str().c_str());
36 
37   return M;
38 }
39 
40 /*
41    IR forming a call graph with a diamond of triangle-shaped SCCs:
42 
43            d1
44           /  \
45          d3--d2
46         /     \
47        b1     c1
48      /  \    /  \
49     b3--b2  c3--c2
50          \  /
51           a1
52          /  \
53         a3--a2
54 
55    All call edges go up between SCCs, and clockwise around the SCC.
56  */
57 static const char DiamondOfTriangles[] =
58      "define void @a1() {\n"
59      "entry:\n"
60      "  call void @a2()\n"
61      "  call void @b2()\n"
62      "  call void @c3()\n"
63      "  ret void\n"
64      "}\n"
65      "define void @a2() {\n"
66      "entry:\n"
67      "  call void @a3()\n"
68      "  ret void\n"
69      "}\n"
70      "define void @a3() {\n"
71      "entry:\n"
72      "  call void @a1()\n"
73      "  ret void\n"
74      "}\n"
75      "define void @b1() {\n"
76      "entry:\n"
77      "  call void @b2()\n"
78      "  call void @d3()\n"
79      "  ret void\n"
80      "}\n"
81      "define void @b2() {\n"
82      "entry:\n"
83      "  call void @b3()\n"
84      "  ret void\n"
85      "}\n"
86      "define void @b3() {\n"
87      "entry:\n"
88      "  call void @b1()\n"
89      "  ret void\n"
90      "}\n"
91      "define void @c1() {\n"
92      "entry:\n"
93      "  call void @c2()\n"
94      "  call void @d2()\n"
95      "  ret void\n"
96      "}\n"
97      "define void @c2() {\n"
98      "entry:\n"
99      "  call void @c3()\n"
100      "  ret void\n"
101      "}\n"
102      "define void @c3() {\n"
103      "entry:\n"
104      "  call void @c1()\n"
105      "  ret void\n"
106      "}\n"
107      "define void @d1() {\n"
108      "entry:\n"
109      "  call void @d2()\n"
110      "  ret void\n"
111      "}\n"
112      "define void @d2() {\n"
113      "entry:\n"
114      "  call void @d3()\n"
115      "  ret void\n"
116      "}\n"
117      "define void @d3() {\n"
118      "entry:\n"
119      "  call void @d1()\n"
120      "  ret void\n"
121      "}\n";
122 
TEST(LazyCallGraphTest,BasicGraphFormation)123 TEST(LazyCallGraphTest, BasicGraphFormation) {
124   std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
125   LazyCallGraph CG(*M);
126 
127   // The order of the entry nodes should be stable w.r.t. the source order of
128   // the IR, and everything in our module is an entry node, so just directly
129   // build variables for each node.
130   auto I = CG.begin();
131   LazyCallGraph::Node &A1 = *I++;
132   EXPECT_EQ("a1", A1.getFunction().getName());
133   LazyCallGraph::Node &A2 = *I++;
134   EXPECT_EQ("a2", A2.getFunction().getName());
135   LazyCallGraph::Node &A3 = *I++;
136   EXPECT_EQ("a3", A3.getFunction().getName());
137   LazyCallGraph::Node &B1 = *I++;
138   EXPECT_EQ("b1", B1.getFunction().getName());
139   LazyCallGraph::Node &B2 = *I++;
140   EXPECT_EQ("b2", B2.getFunction().getName());
141   LazyCallGraph::Node &B3 = *I++;
142   EXPECT_EQ("b3", B3.getFunction().getName());
143   LazyCallGraph::Node &C1 = *I++;
144   EXPECT_EQ("c1", C1.getFunction().getName());
145   LazyCallGraph::Node &C2 = *I++;
146   EXPECT_EQ("c2", C2.getFunction().getName());
147   LazyCallGraph::Node &C3 = *I++;
148   EXPECT_EQ("c3", C3.getFunction().getName());
149   LazyCallGraph::Node &D1 = *I++;
150   EXPECT_EQ("d1", D1.getFunction().getName());
151   LazyCallGraph::Node &D2 = *I++;
152   EXPECT_EQ("d2", D2.getFunction().getName());
153   LazyCallGraph::Node &D3 = *I++;
154   EXPECT_EQ("d3", D3.getFunction().getName());
155   EXPECT_EQ(CG.end(), I);
156 
157   // Build vectors and sort them for the rest of the assertions to make them
158   // independent of order.
159   std::vector<std::string> Nodes;
160 
161   for (LazyCallGraph::Node &N : A1)
162     Nodes.push_back(N.getFunction().getName());
163   std::sort(Nodes.begin(), Nodes.end());
164   EXPECT_EQ("a2", Nodes[0]);
165   EXPECT_EQ("b2", Nodes[1]);
166   EXPECT_EQ("c3", Nodes[2]);
167   Nodes.clear();
168 
169   EXPECT_EQ(A2.end(), std::next(A2.begin()));
170   EXPECT_EQ("a3", A2.begin()->getFunction().getName());
171   EXPECT_EQ(A3.end(), std::next(A3.begin()));
172   EXPECT_EQ("a1", A3.begin()->getFunction().getName());
173 
174   for (LazyCallGraph::Node &N : B1)
175     Nodes.push_back(N.getFunction().getName());
176   std::sort(Nodes.begin(), Nodes.end());
177   EXPECT_EQ("b2", Nodes[0]);
178   EXPECT_EQ("d3", Nodes[1]);
179   Nodes.clear();
180 
181   EXPECT_EQ(B2.end(), std::next(B2.begin()));
182   EXPECT_EQ("b3", B2.begin()->getFunction().getName());
183   EXPECT_EQ(B3.end(), std::next(B3.begin()));
184   EXPECT_EQ("b1", B3.begin()->getFunction().getName());
185 
186   for (LazyCallGraph::Node &N : C1)
187     Nodes.push_back(N.getFunction().getName());
188   std::sort(Nodes.begin(), Nodes.end());
189   EXPECT_EQ("c2", Nodes[0]);
190   EXPECT_EQ("d2", Nodes[1]);
191   Nodes.clear();
192 
193   EXPECT_EQ(C2.end(), std::next(C2.begin()));
194   EXPECT_EQ("c3", C2.begin()->getFunction().getName());
195   EXPECT_EQ(C3.end(), std::next(C3.begin()));
196   EXPECT_EQ("c1", C3.begin()->getFunction().getName());
197 
198   EXPECT_EQ(D1.end(), std::next(D1.begin()));
199   EXPECT_EQ("d2", D1.begin()->getFunction().getName());
200   EXPECT_EQ(D2.end(), std::next(D2.begin()));
201   EXPECT_EQ("d3", D2.begin()->getFunction().getName());
202   EXPECT_EQ(D3.end(), std::next(D3.begin()));
203   EXPECT_EQ("d1", D3.begin()->getFunction().getName());
204 
205   // Now lets look at the SCCs.
206   auto SCCI = CG.postorder_scc_begin();
207 
208   LazyCallGraph::SCC &D = *SCCI++;
209   for (LazyCallGraph::Node *N : D)
210     Nodes.push_back(N->getFunction().getName());
211   std::sort(Nodes.begin(), Nodes.end());
212   EXPECT_EQ(3u, Nodes.size());
213   EXPECT_EQ("d1", Nodes[0]);
214   EXPECT_EQ("d2", Nodes[1]);
215   EXPECT_EQ("d3", Nodes[2]);
216   Nodes.clear();
217   EXPECT_FALSE(D.isParentOf(D));
218   EXPECT_FALSE(D.isChildOf(D));
219   EXPECT_FALSE(D.isAncestorOf(D));
220   EXPECT_FALSE(D.isDescendantOf(D));
221 
222   LazyCallGraph::SCC &C = *SCCI++;
223   for (LazyCallGraph::Node *N : C)
224     Nodes.push_back(N->getFunction().getName());
225   std::sort(Nodes.begin(), Nodes.end());
226   EXPECT_EQ(3u, Nodes.size());
227   EXPECT_EQ("c1", Nodes[0]);
228   EXPECT_EQ("c2", Nodes[1]);
229   EXPECT_EQ("c3", Nodes[2]);
230   Nodes.clear();
231   EXPECT_TRUE(C.isParentOf(D));
232   EXPECT_FALSE(C.isChildOf(D));
233   EXPECT_TRUE(C.isAncestorOf(D));
234   EXPECT_FALSE(C.isDescendantOf(D));
235 
236   LazyCallGraph::SCC &B = *SCCI++;
237   for (LazyCallGraph::Node *N : B)
238     Nodes.push_back(N->getFunction().getName());
239   std::sort(Nodes.begin(), Nodes.end());
240   EXPECT_EQ(3u, Nodes.size());
241   EXPECT_EQ("b1", Nodes[0]);
242   EXPECT_EQ("b2", Nodes[1]);
243   EXPECT_EQ("b3", Nodes[2]);
244   Nodes.clear();
245   EXPECT_TRUE(B.isParentOf(D));
246   EXPECT_FALSE(B.isChildOf(D));
247   EXPECT_TRUE(B.isAncestorOf(D));
248   EXPECT_FALSE(B.isDescendantOf(D));
249   EXPECT_FALSE(B.isAncestorOf(C));
250   EXPECT_FALSE(C.isAncestorOf(B));
251 
252   LazyCallGraph::SCC &A = *SCCI++;
253   for (LazyCallGraph::Node *N : A)
254     Nodes.push_back(N->getFunction().getName());
255   std::sort(Nodes.begin(), Nodes.end());
256   EXPECT_EQ(3u, Nodes.size());
257   EXPECT_EQ("a1", Nodes[0]);
258   EXPECT_EQ("a2", Nodes[1]);
259   EXPECT_EQ("a3", Nodes[2]);
260   Nodes.clear();
261   EXPECT_TRUE(A.isParentOf(B));
262   EXPECT_TRUE(A.isParentOf(C));
263   EXPECT_FALSE(A.isParentOf(D));
264   EXPECT_TRUE(A.isAncestorOf(B));
265   EXPECT_TRUE(A.isAncestorOf(C));
266   EXPECT_TRUE(A.isAncestorOf(D));
267 
268   EXPECT_EQ(CG.postorder_scc_end(), SCCI);
269 }
270 
lookupFunction(Module & M,StringRef Name)271 static Function &lookupFunction(Module &M, StringRef Name) {
272   for (Function &F : M)
273     if (F.getName() == Name)
274       return F;
275   report_fatal_error("Couldn't find function!");
276 }
277 
TEST(LazyCallGraphTest,BasicGraphMutation)278 TEST(LazyCallGraphTest, BasicGraphMutation) {
279   std::unique_ptr<Module> M = parseAssembly(
280       "define void @a() {\n"
281       "entry:\n"
282       "  call void @b()\n"
283       "  call void @c()\n"
284       "  ret void\n"
285       "}\n"
286       "define void @b() {\n"
287       "entry:\n"
288       "  ret void\n"
289       "}\n"
290       "define void @c() {\n"
291       "entry:\n"
292       "  ret void\n"
293       "}\n");
294   LazyCallGraph CG(*M);
295 
296   LazyCallGraph::Node &A = CG.get(lookupFunction(*M, "a"));
297   LazyCallGraph::Node &B = CG.get(lookupFunction(*M, "b"));
298   EXPECT_EQ(2, std::distance(A.begin(), A.end()));
299   EXPECT_EQ(0, std::distance(B.begin(), B.end()));
300 
301   CG.insertEdge(B, lookupFunction(*M, "c"));
302   EXPECT_EQ(1, std::distance(B.begin(), B.end()));
303   LazyCallGraph::Node &C = *B.begin();
304   EXPECT_EQ(0, std::distance(C.begin(), C.end()));
305 
306   CG.insertEdge(C, B.getFunction());
307   EXPECT_EQ(1, std::distance(C.begin(), C.end()));
308   EXPECT_EQ(&B, &*C.begin());
309 
310   CG.insertEdge(C, C.getFunction());
311   EXPECT_EQ(2, std::distance(C.begin(), C.end()));
312   EXPECT_EQ(&B, &*C.begin());
313   EXPECT_EQ(&C, &*std::next(C.begin()));
314 
315   CG.removeEdge(C, B.getFunction());
316   EXPECT_EQ(1, std::distance(C.begin(), C.end()));
317   EXPECT_EQ(&C, &*C.begin());
318 
319   CG.removeEdge(C, C.getFunction());
320   EXPECT_EQ(0, std::distance(C.begin(), C.end()));
321 
322   CG.removeEdge(B, C.getFunction());
323   EXPECT_EQ(0, std::distance(B.begin(), B.end()));
324 }
325 
TEST(LazyCallGraphTest,MultiArmSCC)326 TEST(LazyCallGraphTest, MultiArmSCC) {
327   // Two interlocking cycles. The really useful thing about this SCC is that it
328   // will require Tarjan's DFS to backtrack and finish processing all of the
329   // children of each node in the SCC.
330   std::unique_ptr<Module> M = parseAssembly(
331       "define void @a() {\n"
332       "entry:\n"
333       "  call void @b()\n"
334       "  call void @d()\n"
335       "  ret void\n"
336       "}\n"
337       "define void @b() {\n"
338       "entry:\n"
339       "  call void @c()\n"
340       "  ret void\n"
341       "}\n"
342       "define void @c() {\n"
343       "entry:\n"
344       "  call void @a()\n"
345       "  ret void\n"
346       "}\n"
347       "define void @d() {\n"
348       "entry:\n"
349       "  call void @e()\n"
350       "  ret void\n"
351       "}\n"
352       "define void @e() {\n"
353       "entry:\n"
354       "  call void @a()\n"
355       "  ret void\n"
356       "}\n");
357   LazyCallGraph CG(*M);
358 
359   // Force the graph to be fully expanded.
360   auto SCCI = CG.postorder_scc_begin();
361   LazyCallGraph::SCC &SCC = *SCCI++;
362   EXPECT_EQ(CG.postorder_scc_end(), SCCI);
363 
364   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
365   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
366   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
367   LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
368   LazyCallGraph::Node &E = *CG.lookup(lookupFunction(*M, "e"));
369   EXPECT_EQ(&SCC, CG.lookupSCC(A));
370   EXPECT_EQ(&SCC, CG.lookupSCC(B));
371   EXPECT_EQ(&SCC, CG.lookupSCC(C));
372   EXPECT_EQ(&SCC, CG.lookupSCC(D));
373   EXPECT_EQ(&SCC, CG.lookupSCC(E));
374 }
375 
TEST(LazyCallGraphTest,OutgoingSCCEdgeInsertion)376 TEST(LazyCallGraphTest, OutgoingSCCEdgeInsertion) {
377   std::unique_ptr<Module> M = parseAssembly(
378       "define void @a() {\n"
379       "entry:\n"
380       "  call void @b()\n"
381       "  call void @c()\n"
382       "  ret void\n"
383       "}\n"
384       "define void @b() {\n"
385       "entry:\n"
386       "  call void @d()\n"
387       "  ret void\n"
388       "}\n"
389       "define void @c() {\n"
390       "entry:\n"
391       "  call void @d()\n"
392       "  ret void\n"
393       "}\n"
394       "define void @d() {\n"
395       "entry:\n"
396       "  ret void\n"
397       "}\n");
398   LazyCallGraph CG(*M);
399 
400   // Force the graph to be fully expanded.
401   for (LazyCallGraph::SCC &C : CG.postorder_sccs())
402     (void)C;
403 
404   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
405   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
406   LazyCallGraph::Node &C = *CG.lookup(lookupFunction(*M, "c"));
407   LazyCallGraph::Node &D = *CG.lookup(lookupFunction(*M, "d"));
408   LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
409   LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
410   LazyCallGraph::SCC &CC = *CG.lookupSCC(C);
411   LazyCallGraph::SCC &DC = *CG.lookupSCC(D);
412   EXPECT_TRUE(AC.isAncestorOf(BC));
413   EXPECT_TRUE(AC.isAncestorOf(CC));
414   EXPECT_TRUE(AC.isAncestorOf(DC));
415   EXPECT_TRUE(DC.isDescendantOf(AC));
416   EXPECT_TRUE(DC.isDescendantOf(BC));
417   EXPECT_TRUE(DC.isDescendantOf(CC));
418 
419   EXPECT_EQ(2, std::distance(A.begin(), A.end()));
420   AC.insertOutgoingEdge(A, D);
421   EXPECT_EQ(3, std::distance(A.begin(), A.end()));
422   EXPECT_TRUE(AC.isParentOf(DC));
423   EXPECT_EQ(&AC, CG.lookupSCC(A));
424   EXPECT_EQ(&BC, CG.lookupSCC(B));
425   EXPECT_EQ(&CC, CG.lookupSCC(C));
426   EXPECT_EQ(&DC, CG.lookupSCC(D));
427 }
428 
TEST(LazyCallGraphTest,IncomingSCCEdgeInsertion)429 TEST(LazyCallGraphTest, IncomingSCCEdgeInsertion) {
430   // We want to ensure we can add edges even across complex diamond graphs, so
431   // we use the diamond of triangles graph defined above. The ascii diagram is
432   // repeated here for easy reference.
433   //
434   //         d1       |
435   //        /  \      |
436   //       d3--d2     |
437   //      /     \     |
438   //     b1     c1    |
439   //   /  \    /  \   |
440   //  b3--b2  c3--c2  |
441   //       \  /       |
442   //        a1        |
443   //       /  \       |
444   //      a3--a2      |
445   //
446   std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
447   LazyCallGraph CG(*M);
448 
449   // Force the graph to be fully expanded.
450   for (LazyCallGraph::SCC &C : CG.postorder_sccs())
451     (void)C;
452 
453   LazyCallGraph::Node &A1 = *CG.lookup(lookupFunction(*M, "a1"));
454   LazyCallGraph::Node &A2 = *CG.lookup(lookupFunction(*M, "a2"));
455   LazyCallGraph::Node &A3 = *CG.lookup(lookupFunction(*M, "a3"));
456   LazyCallGraph::Node &B1 = *CG.lookup(lookupFunction(*M, "b1"));
457   LazyCallGraph::Node &B2 = *CG.lookup(lookupFunction(*M, "b2"));
458   LazyCallGraph::Node &B3 = *CG.lookup(lookupFunction(*M, "b3"));
459   LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
460   LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
461   LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
462   LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
463   LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
464   LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
465   LazyCallGraph::SCC &AC = *CG.lookupSCC(A1);
466   LazyCallGraph::SCC &BC = *CG.lookupSCC(B1);
467   LazyCallGraph::SCC &CC = *CG.lookupSCC(C1);
468   LazyCallGraph::SCC &DC = *CG.lookupSCC(D1);
469   ASSERT_EQ(&AC, CG.lookupSCC(A2));
470   ASSERT_EQ(&AC, CG.lookupSCC(A3));
471   ASSERT_EQ(&BC, CG.lookupSCC(B2));
472   ASSERT_EQ(&BC, CG.lookupSCC(B3));
473   ASSERT_EQ(&CC, CG.lookupSCC(C2));
474   ASSERT_EQ(&CC, CG.lookupSCC(C3));
475   ASSERT_EQ(&DC, CG.lookupSCC(D2));
476   ASSERT_EQ(&DC, CG.lookupSCC(D3));
477   ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
478 
479   // Add an edge to make the graph:
480   //
481   //         d1         |
482   //        /  \        |
483   //       d3--d2---.   |
484   //      /     \    |  |
485   //     b1     c1   |  |
486   //   /  \    /  \ /   |
487   //  b3--b2  c3--c2    |
488   //       \  /         |
489   //        a1          |
490   //       /  \         |
491   //      a3--a2        |
492   CC.insertIncomingEdge(D2, C2);
493   // Make sure we connected the nodes.
494   EXPECT_EQ(2, std::distance(D2.begin(), D2.end()));
495 
496   // Make sure we have the correct nodes in the SCC sets.
497   EXPECT_EQ(&AC, CG.lookupSCC(A1));
498   EXPECT_EQ(&AC, CG.lookupSCC(A2));
499   EXPECT_EQ(&AC, CG.lookupSCC(A3));
500   EXPECT_EQ(&BC, CG.lookupSCC(B1));
501   EXPECT_EQ(&BC, CG.lookupSCC(B2));
502   EXPECT_EQ(&BC, CG.lookupSCC(B3));
503   EXPECT_EQ(&CC, CG.lookupSCC(C1));
504   EXPECT_EQ(&CC, CG.lookupSCC(C2));
505   EXPECT_EQ(&CC, CG.lookupSCC(C3));
506   EXPECT_EQ(&CC, CG.lookupSCC(D1));
507   EXPECT_EQ(&CC, CG.lookupSCC(D2));
508   EXPECT_EQ(&CC, CG.lookupSCC(D3));
509 
510   // And that ancestry tests have been updated.
511   EXPECT_TRUE(AC.isParentOf(BC));
512   EXPECT_TRUE(AC.isParentOf(CC));
513   EXPECT_FALSE(AC.isAncestorOf(DC));
514   EXPECT_FALSE(BC.isAncestorOf(DC));
515   EXPECT_FALSE(CC.isAncestorOf(DC));
516 }
517 
TEST(LazyCallGraphTest,IncomingSCCEdgeInsertionMidTraversal)518 TEST(LazyCallGraphTest, IncomingSCCEdgeInsertionMidTraversal) {
519   // This is the same fundamental test as the previous, but we perform it
520   // having only partially walked the SCCs of the graph.
521   std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
522   LazyCallGraph CG(*M);
523 
524   // Walk the SCCs until we find the one containing 'c1'.
525   auto SCCI = CG.postorder_scc_begin(), SCCE = CG.postorder_scc_end();
526   ASSERT_NE(SCCI, SCCE);
527   LazyCallGraph::SCC &DC = *SCCI;
528   ASSERT_NE(&DC, nullptr);
529   ++SCCI;
530   ASSERT_NE(SCCI, SCCE);
531   LazyCallGraph::SCC &CC = *SCCI;
532   ASSERT_NE(&CC, nullptr);
533 
534   ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a1")));
535   ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a2")));
536   ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "a3")));
537   ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b1")));
538   ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b2")));
539   ASSERT_EQ(nullptr, CG.lookup(lookupFunction(*M, "b3")));
540   LazyCallGraph::Node &C1 = *CG.lookup(lookupFunction(*M, "c1"));
541   LazyCallGraph::Node &C2 = *CG.lookup(lookupFunction(*M, "c2"));
542   LazyCallGraph::Node &C3 = *CG.lookup(lookupFunction(*M, "c3"));
543   LazyCallGraph::Node &D1 = *CG.lookup(lookupFunction(*M, "d1"));
544   LazyCallGraph::Node &D2 = *CG.lookup(lookupFunction(*M, "d2"));
545   LazyCallGraph::Node &D3 = *CG.lookup(lookupFunction(*M, "d3"));
546   ASSERT_EQ(&CC, CG.lookupSCC(C1));
547   ASSERT_EQ(&CC, CG.lookupSCC(C2));
548   ASSERT_EQ(&CC, CG.lookupSCC(C3));
549   ASSERT_EQ(&DC, CG.lookupSCC(D1));
550   ASSERT_EQ(&DC, CG.lookupSCC(D2));
551   ASSERT_EQ(&DC, CG.lookupSCC(D3));
552   ASSERT_EQ(1, std::distance(D2.begin(), D2.end()));
553 
554   CC.insertIncomingEdge(D2, C2);
555   EXPECT_EQ(2, std::distance(D2.begin(), D2.end()));
556 
557   // Make sure we have the correct nodes in the SCC sets.
558   EXPECT_EQ(&CC, CG.lookupSCC(C1));
559   EXPECT_EQ(&CC, CG.lookupSCC(C2));
560   EXPECT_EQ(&CC, CG.lookupSCC(C3));
561   EXPECT_EQ(&CC, CG.lookupSCC(D1));
562   EXPECT_EQ(&CC, CG.lookupSCC(D2));
563   EXPECT_EQ(&CC, CG.lookupSCC(D3));
564 
565   // Check that we can form the last two SCCs now in a coherent way.
566   ++SCCI;
567   EXPECT_NE(SCCI, SCCE);
568   LazyCallGraph::SCC &BC = *SCCI;
569   EXPECT_NE(&BC, nullptr);
570   EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b1"))));
571   EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b2"))));
572   EXPECT_EQ(&BC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "b3"))));
573   ++SCCI;
574   EXPECT_NE(SCCI, SCCE);
575   LazyCallGraph::SCC &AC = *SCCI;
576   EXPECT_NE(&AC, nullptr);
577   EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a1"))));
578   EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a2"))));
579   EXPECT_EQ(&AC, CG.lookupSCC(*CG.lookup(lookupFunction(*M, "a3"))));
580   ++SCCI;
581   EXPECT_EQ(SCCI, SCCE);
582 }
583 
TEST(LazyCallGraphTest,InterSCCEdgeRemoval)584 TEST(LazyCallGraphTest, InterSCCEdgeRemoval) {
585   std::unique_ptr<Module> M = parseAssembly(
586       "define void @a() {\n"
587       "entry:\n"
588       "  call void @b()\n"
589       "  ret void\n"
590       "}\n"
591       "define void @b() {\n"
592       "entry:\n"
593       "  ret void\n"
594       "}\n");
595   LazyCallGraph CG(*M);
596 
597   // Force the graph to be fully expanded.
598   for (LazyCallGraph::SCC &C : CG.postorder_sccs())
599     (void)C;
600 
601   LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
602   LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
603   LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
604   LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
605 
606   EXPECT_EQ("b", A.begin()->getFunction().getName());
607   EXPECT_EQ(B.end(), B.begin());
608   EXPECT_EQ(&AC, &*BC.parent_begin());
609 
610   AC.removeInterSCCEdge(A, B);
611 
612   EXPECT_EQ(A.end(), A.begin());
613   EXPECT_EQ(B.end(), B.begin());
614   EXPECT_EQ(BC.parent_end(), BC.parent_begin());
615 }
616 
TEST(LazyCallGraphTest,IntraSCCEdgeInsertion)617 TEST(LazyCallGraphTest, IntraSCCEdgeInsertion) {
618   std::unique_ptr<Module> M1 = parseAssembly(
619       "define void @a() {\n"
620       "entry:\n"
621       "  call void @b()\n"
622       "  ret void\n"
623       "}\n"
624       "define void @b() {\n"
625       "entry:\n"
626       "  call void @c()\n"
627       "  ret void\n"
628       "}\n"
629       "define void @c() {\n"
630       "entry:\n"
631       "  call void @a()\n"
632       "  ret void\n"
633       "}\n");
634   LazyCallGraph CG1(*M1);
635 
636   // Force the graph to be fully expanded.
637   auto SCCI = CG1.postorder_scc_begin();
638   LazyCallGraph::SCC &SCC = *SCCI++;
639   EXPECT_EQ(CG1.postorder_scc_end(), SCCI);
640 
641   LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a"));
642   LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b"));
643   LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c"));
644   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
645   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
646   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
647 
648   // Insert an edge from 'a' to 'c'. Nothing changes about the SCCs.
649   SCC.insertIntraSCCEdge(A, C);
650   EXPECT_EQ(2, std::distance(A.begin(), A.end()));
651   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
652   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
653   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
654 
655   // Insert a self edge from 'a' back to 'a'.
656   SCC.insertIntraSCCEdge(A, A);
657   EXPECT_EQ(3, std::distance(A.begin(), A.end()));
658   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
659   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
660   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
661 }
662 
TEST(LazyCallGraphTest,IntraSCCEdgeRemoval)663 TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
664   // A nice fully connected (including self-edges) SCC.
665   std::unique_ptr<Module> M1 = parseAssembly(
666       "define void @a() {\n"
667       "entry:\n"
668       "  call void @a()\n"
669       "  call void @b()\n"
670       "  call void @c()\n"
671       "  ret void\n"
672       "}\n"
673       "define void @b() {\n"
674       "entry:\n"
675       "  call void @a()\n"
676       "  call void @b()\n"
677       "  call void @c()\n"
678       "  ret void\n"
679       "}\n"
680       "define void @c() {\n"
681       "entry:\n"
682       "  call void @a()\n"
683       "  call void @b()\n"
684       "  call void @c()\n"
685       "  ret void\n"
686       "}\n");
687   LazyCallGraph CG1(*M1);
688 
689   // Force the graph to be fully expanded.
690   auto SCCI = CG1.postorder_scc_begin();
691   LazyCallGraph::SCC &SCC = *SCCI++;
692   EXPECT_EQ(CG1.postorder_scc_end(), SCCI);
693 
694   LazyCallGraph::Node &A = *CG1.lookup(lookupFunction(*M1, "a"));
695   LazyCallGraph::Node &B = *CG1.lookup(lookupFunction(*M1, "b"));
696   LazyCallGraph::Node &C = *CG1.lookup(lookupFunction(*M1, "c"));
697   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
698   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
699   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
700 
701   // Remove the edge from b -> a, which should leave the 3 functions still in
702   // a single connected component because of a -> b -> c -> a.
703   SmallVector<LazyCallGraph::SCC *, 1> NewSCCs = SCC.removeIntraSCCEdge(B, A);
704   EXPECT_EQ(0u, NewSCCs.size());
705   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
706   EXPECT_EQ(&SCC, CG1.lookupSCC(B));
707   EXPECT_EQ(&SCC, CG1.lookupSCC(C));
708 
709   // Remove the edge from c -> a, which should leave 'a' in the original SCC
710   // and form a new SCC for 'b' and 'c'.
711   NewSCCs = SCC.removeIntraSCCEdge(C, A);
712   EXPECT_EQ(1u, NewSCCs.size());
713   EXPECT_EQ(&SCC, CG1.lookupSCC(A));
714   EXPECT_EQ(1, std::distance(SCC.begin(), SCC.end()));
715   LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B);
716   EXPECT_EQ(SCC2, CG1.lookupSCC(C));
717   EXPECT_EQ(SCC2, NewSCCs[0]);
718 }
719 
720 }
721