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 
24 std::unique_ptr<Module> parseAssembly(const char *Assembly) {
25   auto M = make_unique<Module>("Module", getGlobalContext());
26 
27   SMDiagnostic Error;
28   bool Parsed =
29       ParseAssemblyString(Assembly, M.get(), Error, M->getContext()) == M.get();
30 
31   std::string ErrMsg;
32   raw_string_ostream OS(ErrMsg);
33   Error.print("", OS);
34 
35   // A failure here means that the test itself is buggy.
36   if (!Parsed)
37     report_fatal_error(OS.str().c_str());
38 
39   return M;
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 static const char DiamondOfTriangles[] =
58      "define void @a1() {\n"
59      "entry:\n"
60      "  call void @a2()\n"
61      "  call void @b2()\n"
62      "  call void @c3()\n"
63      "  ret void\n"
64      "}\n"
65      "define void @a2() {\n"
66      "entry:\n"
67      "  call void @a3()\n"
68      "  ret void\n"
69      "}\n"
70      "define void @a3() {\n"
71      "entry:\n"
72      "  call void @a1()\n"
73      "  ret void\n"
74      "}\n"
75      "define void @b1() {\n"
76      "entry:\n"
77      "  call void @b2()\n"
78      "  call void @d3()\n"
79      "  ret void\n"
80      "}\n"
81      "define void @b2() {\n"
82      "entry:\n"
83      "  call void @b3()\n"
84      "  ret void\n"
85      "}\n"
86      "define void @b3() {\n"
87      "entry:\n"
88      "  call void @b1()\n"
89      "  ret void\n"
90      "}\n"
91      "define void @c1() {\n"
92      "entry:\n"
93      "  call void @c2()\n"
94      "  call void @d2()\n"
95      "  ret void\n"
96      "}\n"
97      "define void @c2() {\n"
98      "entry:\n"
99      "  call void @c3()\n"
100      "  ret void\n"
101      "}\n"
102      "define void @c3() {\n"
103      "entry:\n"
104      "  call void @c1()\n"
105      "  ret void\n"
106      "}\n"
107      "define void @d1() {\n"
108      "entry:\n"
109      "  call void @d2()\n"
110      "  ret void\n"
111      "}\n"
112      "define void @d2() {\n"
113      "entry:\n"
114      "  call void @d3()\n"
115      "  ret void\n"
116      "}\n"
117      "define void @d3() {\n"
118      "entry:\n"
119      "  call void @d1()\n"
120      "  ret void\n"
121      "}\n";
122 
123 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("d1", Nodes[0]);
213   EXPECT_EQ("d2", Nodes[1]);
214   EXPECT_EQ("d3", Nodes[2]);
215   EXPECT_EQ(3u, Nodes.size());
216   Nodes.clear();
217 
218   LazyCallGraph::SCC *C = *SCCI++;
219   for (LazyCallGraph::Node *N : *C)
220     Nodes.push_back(N->getFunction().getName());
221   std::sort(Nodes.begin(), Nodes.end());
222   EXPECT_EQ("c1", Nodes[0]);
223   EXPECT_EQ("c2", Nodes[1]);
224   EXPECT_EQ("c3", Nodes[2]);
225   EXPECT_EQ(3u, Nodes.size());
226   Nodes.clear();
227 
228   LazyCallGraph::SCC *B = *SCCI++;
229   for (LazyCallGraph::Node *N : *B)
230     Nodes.push_back(N->getFunction().getName());
231   std::sort(Nodes.begin(), Nodes.end());
232   EXPECT_EQ("b1", Nodes[0]);
233   EXPECT_EQ("b2", Nodes[1]);
234   EXPECT_EQ("b3", Nodes[2]);
235   EXPECT_EQ(3u, Nodes.size());
236   Nodes.clear();
237 
238   LazyCallGraph::SCC *A = *SCCI++;
239   for (LazyCallGraph::Node *N : *A)
240     Nodes.push_back(N->getFunction().getName());
241   std::sort(Nodes.begin(), Nodes.end());
242   EXPECT_EQ("a1", Nodes[0]);
243   EXPECT_EQ("a2", Nodes[1]);
244   EXPECT_EQ("a3", Nodes[2]);
245   EXPECT_EQ(3u, Nodes.size());
246   Nodes.clear();
247 
248   EXPECT_EQ(CG.postorder_scc_end(), SCCI);
249 }
250 
251 static Function &lookupFunction(Module &M, StringRef Name) {
252   for (Function &F : M)
253     if (F.getName() == Name)
254       return F;
255   report_fatal_error("Couldn't find function!");
256 }
257 
258 TEST(LazyCallGraphTest, MultiArmSCC) {
259   // Two interlocking cycles. The really useful thing about this SCC is that it
260   // will require Tarjan's DFS to backtrack and finish processing all of the
261   // children of each node in the SCC.
262   std::unique_ptr<Module> M = parseAssembly(
263       "define void @a() {\n"
264       "entry:\n"
265       "  call void @b()\n"
266       "  call void @d()\n"
267       "  ret void\n"
268       "}\n"
269       "define void @b() {\n"
270       "entry:\n"
271       "  call void @c()\n"
272       "  ret void\n"
273       "}\n"
274       "define void @c() {\n"
275       "entry:\n"
276       "  call void @a()\n"
277       "  ret void\n"
278       "}\n"
279       "define void @d() {\n"
280       "entry:\n"
281       "  call void @e()\n"
282       "  ret void\n"
283       "}\n"
284       "define void @e() {\n"
285       "entry:\n"
286       "  call void @a()\n"
287       "  ret void\n"
288       "}\n");
289   LazyCallGraph CG(*M);
290 
291   // Force the graph to be fully expanded.
292   auto SCCI = CG.postorder_scc_begin();
293   LazyCallGraph::SCC *SCC = *SCCI++;
294   EXPECT_EQ(CG.postorder_scc_end(), SCCI);
295 
296   LazyCallGraph::Node *A = CG.lookup(lookupFunction(*M, "a"));
297   LazyCallGraph::Node *B = CG.lookup(lookupFunction(*M, "b"));
298   LazyCallGraph::Node *C = CG.lookup(lookupFunction(*M, "c"));
299   LazyCallGraph::Node *D = CG.lookup(lookupFunction(*M, "d"));
300   LazyCallGraph::Node *E = CG.lookup(lookupFunction(*M, "e"));
301   EXPECT_EQ(SCC, CG.lookupSCC(A->getFunction()));
302   EXPECT_EQ(SCC, CG.lookupSCC(B->getFunction()));
303   EXPECT_EQ(SCC, CG.lookupSCC(C->getFunction()));
304   EXPECT_EQ(SCC, CG.lookupSCC(D->getFunction()));
305   EXPECT_EQ(SCC, CG.lookupSCC(E->getFunction()));
306 }
307 
308 TEST(LazyCallGraphTest, InterSCCEdgeRemoval) {
309   std::unique_ptr<Module> M = parseAssembly(
310       "define void @a() {\n"
311       "entry:\n"
312       "  call void @b()\n"
313       "  ret void\n"
314       "}\n"
315       "define void @b() {\n"
316       "entry:\n"
317       "  ret void\n"
318       "}\n");
319   LazyCallGraph CG(*M);
320 
321   // Force the graph to be fully expanded.
322   for (LazyCallGraph::SCC *C : CG.postorder_sccs())
323     (void)C;
324 
325   LazyCallGraph::Node *A = CG.lookup(lookupFunction(*M, "a"));
326   LazyCallGraph::Node *B = CG.lookup(lookupFunction(*M, "b"));
327   LazyCallGraph::SCC *AC = CG.lookupSCC(lookupFunction(*M, "a"));
328   LazyCallGraph::SCC *BC = CG.lookupSCC(lookupFunction(*M, "b"));
329 
330   EXPECT_EQ("b", A->begin()->getFunction().getName());
331   EXPECT_EQ(B->end(), B->begin());
332   EXPECT_EQ(AC, *BC->parent_begin());
333 
334   CG.removeEdge(*A, lookupFunction(*M, "b"));
335 
336   EXPECT_EQ(A->end(), A->begin());
337   EXPECT_EQ(B->end(), B->begin());
338   EXPECT_EQ(BC->parent_end(), BC->parent_begin());
339 }
340 
341 TEST(LazyCallGraphTest, IntraSCCEdgeRemoval) {
342   // A nice fully connected (including self-edges) SCC.
343   std::unique_ptr<Module> M1 = parseAssembly(
344       "define void @a() {\n"
345       "entry:\n"
346       "  call void @a()\n"
347       "  call void @b()\n"
348       "  call void @c()\n"
349       "  ret void\n"
350       "}\n"
351       "define void @b() {\n"
352       "entry:\n"
353       "  call void @a()\n"
354       "  call void @b()\n"
355       "  call void @c()\n"
356       "  ret void\n"
357       "}\n"
358       "define void @c() {\n"
359       "entry:\n"
360       "  call void @a()\n"
361       "  call void @b()\n"
362       "  call void @c()\n"
363       "  ret void\n"
364       "}\n");
365   LazyCallGraph CG1(*M1);
366 
367   // Force the graph to be fully expanded.
368   auto SCCI = CG1.postorder_scc_begin();
369   LazyCallGraph::SCC *SCC = *SCCI++;
370   EXPECT_EQ(CG1.postorder_scc_end(), SCCI);
371 
372   LazyCallGraph::Node *A = CG1.lookup(lookupFunction(*M1, "a"));
373   LazyCallGraph::Node *B = CG1.lookup(lookupFunction(*M1, "b"));
374   LazyCallGraph::Node *C = CG1.lookup(lookupFunction(*M1, "c"));
375   EXPECT_EQ(SCC, CG1.lookupSCC(A->getFunction()));
376   EXPECT_EQ(SCC, CG1.lookupSCC(B->getFunction()));
377   EXPECT_EQ(SCC, CG1.lookupSCC(C->getFunction()));
378 
379   // Remove the edge from b -> a, which should leave the 3 functions still in
380   // a single connected component because of a -> b -> c -> a.
381   CG1.removeEdge(*B, A->getFunction());
382   EXPECT_EQ(SCC, CG1.lookupSCC(A->getFunction()));
383   EXPECT_EQ(SCC, CG1.lookupSCC(B->getFunction()));
384   EXPECT_EQ(SCC, CG1.lookupSCC(C->getFunction()));
385 
386   // Remove the edge from c -> a, which should leave 'a' in the original SCC
387   // and form a new SCC for 'b' and 'c'.
388   CG1.removeEdge(*C, A->getFunction());
389   EXPECT_EQ(SCC, CG1.lookupSCC(A->getFunction()));
390   EXPECT_EQ(1, std::distance(SCC->begin(), SCC->end()));
391   LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B->getFunction());
392   EXPECT_EQ(SCC2, CG1.lookupSCC(C->getFunction()));
393 }
394 
395 }
396