]> git.proxmox.com Git - rustc.git/blame - src/llvm/unittests/Analysis/LazyCallGraphTest.cpp
projects / rustc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
Imported Upstream version 1.0.0+dfsg1
[rustc.git] / src / llvm / unittests / Analysis / LazyCallGraphTest.cpp
CommitLineData
1a4d82fc
JJ		 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 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
85aaf69f
SL		 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 */
1a4d82fc
JJ		 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}
backport for Debian buster