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) {
25 auto M = make_unique<Module>("Module", getGlobalContext());
29 ParseAssemblyString(Assembly, M.get(), Error, M->getContext()) == M.get();
32 raw_string_ostream OS(ErrMsg);
35 // A failure here means that the test itself is buggy.
37 report_fatal_error(OS.str().c_str());
42 // IR forming a call graph with a diamond of triangle-shaped SCCs:
56 // All call edges go up between SCCs, and clockwise around the SCC.
57 static const char DiamondOfTriangles[] =
58 "define void @a1() {\n"
65 "define void @a2() {\n"
70 "define void @a3() {\n"
75 "define void @b1() {\n"
81 "define void @b2() {\n"
86 "define void @b3() {\n"
91 "define void @c1() {\n"
97 "define void @c2() {\n"
102 "define void @c3() {\n"
107 "define void @d1() {\n"
112 "define void @d2() {\n"
117 "define void @d3() {\n"
123 TEST(LazyCallGraphTest, BasicGraphFormation) {
124 std::unique_ptr<Module> M = parseAssembly(DiamondOfTriangles);
125 LazyCallGraph CG(*M);
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.
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);
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;
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]);
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());
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]);
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());
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]);
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());
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());
205 // Now lets look at the SCCs.
206 auto SCCI = CG.postorder_scc_begin();
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());
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());
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());
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());
248 EXPECT_EQ(CG.postorder_scc_end(), SCCI);
251 static Function &lookupFunction(Module &M, StringRef Name) {
252 for (Function &F : M)
253 if (F.getName() == Name)
255 report_fatal_error("Couldn't find function!");
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"
269 "define void @b() {\n"
274 "define void @c() {\n"
279 "define void @d() {\n"
284 "define void @e() {\n"
289 LazyCallGraph CG(*M);
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);
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));
302 EXPECT_EQ(&SCC, CG.lookupSCC(B));
303 EXPECT_EQ(&SCC, CG.lookupSCC(C));
304 EXPECT_EQ(&SCC, CG.lookupSCC(D));
305 EXPECT_EQ(&SCC, CG.lookupSCC(E));
308 TEST(LazyCallGraphTest, InterSCCEdgeRemoval) {
309 std::unique_ptr<Module> M = parseAssembly(
310 "define void @a() {\n"
315 "define void @b() {\n"
319 LazyCallGraph CG(*M);
321 // Force the graph to be fully expanded.
322 for (LazyCallGraph::SCC &C : CG.postorder_sccs())
325 LazyCallGraph::Node &A = *CG.lookup(lookupFunction(*M, "a"));
326 LazyCallGraph::Node &B = *CG.lookup(lookupFunction(*M, "b"));
327 LazyCallGraph::SCC &AC = *CG.lookupSCC(A);
328 LazyCallGraph::SCC &BC = *CG.lookupSCC(B);
330 EXPECT_EQ("b", A.begin()->getFunction().getName());
331 EXPECT_EQ(B.end(), B.begin());
332 EXPECT_EQ(&AC, &*BC.parent_begin());
334 CG.removeEdge(A, lookupFunction(*M, "b"));
336 EXPECT_EQ(A.end(), A.begin());
337 EXPECT_EQ(B.end(), B.begin());
338 EXPECT_EQ(BC.parent_end(), BC.parent_begin());
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"
351 "define void @b() {\n"
358 "define void @c() {\n"
365 LazyCallGraph CG1(*M1);
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);
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));
376 EXPECT_EQ(&SCC, CG1.lookupSCC(B));
377 EXPECT_EQ(&SCC, CG1.lookupSCC(C));
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));
383 EXPECT_EQ(&SCC, CG1.lookupSCC(B));
384 EXPECT_EQ(&SCC, CG1.lookupSCC(C));
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));
390 EXPECT_EQ(1, std::distance(SCC.begin(), SCC.end()));
391 LazyCallGraph::SCC *SCC2 = CG1.lookupSCC(B);
392 EXPECT_EQ(SCC2, CG1.lookupSCC(C));