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
20using namespace llvm;
21
22namespace {
23
24std::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.
57static 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
123TEST(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
271static 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
278TEST(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
326TEST(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
376TEST(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
429TEST(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
518TEST(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
584TEST(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
617TEST(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
663TEST(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