1	//===- LazyCallGraphTest.cpp - Unit tests for the lazy CG analysis --------===//
2	//
3	// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4	// See https://llvm.org/LICENSE.txt for license information.
5	// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6	//
7	//===----------------------------------------------------------------------===//
8
9	#include "llvm/Analysis/LazyCallGraph.h"
10	#include "llvm/AsmParser/Parser.h"
11	#include "llvm/IR/Function.h"
12	#include "llvm/IR/Instructions.h"
13	#include "llvm/IR/LLVMContext.h"
14	#include "llvm/IR/Module.h"
15	#include "llvm/IR/Verifier.h"
16	#include "llvm/Support/ErrorHandling.h"
17	#include "llvm/Support/SourceMgr.h"
18	#include "llvm/TargetParser/Triple.h"
19	#include "gtest/gtest.h"
20	#include <memory>
21
22	using namespace llvm;
23
24	namespace {
25
26	std::unique_ptr<Module> parseAssembly(LLVMContext &Context,
27	const char *Assembly) {
28	SMDiagnostic Error;
29	std::unique_ptr<Module> M = parseAssemblyString(AsmString: Assembly, Err&: Error, Context);
30
31	std::string ErrMsg;
32	raw_string_ostream OS(ErrMsg);
33	Error.print(ProgName: "", S&: OS);
34
35	// A failure here means that the test itself is buggy.
36	if (!M)
37	report_fatal_error(reason: OS.str().c_str());
38
39	return M;
40	}
41
42	/*
43	IR forming a call graph with a diamond of triangle-shaped SCCs:
44
45	d1
46	/ \
47	d3--d2
48	/ \
49	b1 c1
50	/ \ / \
51	b3--b2 c3--c2
52	\ /
53	a1
54	/ \
55	a3--a2
56
57	All call edges go up between SCCs, and clockwise around the SCC.
58	*/
59	static const char DiamondOfTriangles[] =
60	"define void @a1() {\n"
61	"entry:\n"
62	" call void @a2()\n"
63	" call void @b2()\n"
64	" call void @c3()\n"
65	" ret void\n"
66	"}\n"
67	"define void @a2() {\n"
68	"entry:\n"
69	" call void @a3()\n"
70	" ret void\n"
71	"}\n"
72	"define void @a3() {\n"
73	"entry:\n"
74	" call void @a1()\n"
75	" ret void\n"
76	"}\n"
77	"define void @b1() {\n"
78	"entry:\n"
79	" call void @b2()\n"
80	" call void @d3()\n"
81	" ret void\n"
82	"}\n"
83	"define void @b2() {\n"
84	"entry:\n"
85	" call void @b3()\n"
86	" ret void\n"
87	"}\n"
88	"define void @b3() {\n"
89	"entry:\n"
90	" call void @b1()\n"
91	" ret void\n"
92	"}\n"
93	"define void @c1() {\n"
94	"entry:\n"
95	" call void @c2()\n"
96	" call void @d2()\n"
97	" ret void\n"
98	"}\n"
99	"define void @c2() {\n"
100	"entry:\n"
101	" call void @c3()\n"
102	" ret void\n"
103	"}\n"
104	"define void @c3() {\n"
105	"entry:\n"
106	" call void @c1()\n"
107	" ret void\n"
108	"}\n"
109	"define void @d1() {\n"
110	"entry:\n"
111	" call void @d2()\n"
112	" ret void\n"
113	"}\n"
114	"define void @d2() {\n"
115	"entry:\n"
116	" call void @d3()\n"
117	" ret void\n"
118	"}\n"
119	"define void @d3() {\n"
120	"entry:\n"
121	" call void @d1()\n"
122	" ret void\n"
123	"}\n";
124
125	/*
126	IR forming a reference graph with a diamond of triangle-shaped RefSCCs
127
128	d1
129	/ \
130	d3--d2
131	/ \
132	b1 c1
133	/ \ / \
134	b3--b2 c3--c2
135	\ /
136	a1
137	/ \
138	a3--a2
139
140	All call edges go up between RefSCCs, and clockwise around the RefSCC.
141	*/
142	static const char DiamondOfTrianglesRefGraph[] =
143	"define void @a1() {\n"
144	"entry:\n"
145	" %a = alloca void ()*\n"
146	" store void ()* @a2, void ()** %a\n"
147	" store void ()* @b2, void ()** %a\n"
148	" store void ()* @c3, void ()** %a\n"
149	" ret void\n"
150	"}\n"
151	"define void @a2() {\n"
152	"entry:\n"
153	" %a = alloca void ()*\n"
154	" store void ()* @a3, void ()** %a\n"
155	" ret void\n"
156	"}\n"
157	"define void @a3() {\n"
158	"entry:\n"
159	" %a = alloca void ()*\n"
160	" store void ()* @a1, void ()** %a\n"
161	" ret void\n"
162	"}\n"
163	"define void @b1() {\n"
164	"entry:\n"
165	" %a = alloca void ()*\n"
166	" store void ()* @b2, void ()** %a\n"
167	" store void ()* @d3, void ()** %a\n"
168	" ret void\n"
169	"}\n"
170	"define void @b2() {\n"
171	"entry:\n"
172	" %a = alloca void ()*\n"
173	" store void ()* @b3, void ()** %a\n"
174	" ret void\n"
175	"}\n"
176	"define void @b3() {\n"
177	"entry:\n"
178	" %a = alloca void ()*\n"
179	" store void ()* @b1, void ()** %a\n"
180	" ret void\n"
181	"}\n"
182	"define void @c1() {\n"
183	"entry:\n"
184	" %a = alloca void ()*\n"
185	" store void ()* @c2, void ()** %a\n"
186	" store void ()* @d2, void ()** %a\n"
187	" ret void\n"
188	"}\n"
189	"define void @c2() {\n"
190	"entry:\n"
191	" %a = alloca void ()*\n"
192	" store void ()* @c3, void ()** %a\n"
193	" ret void\n"
194	"}\n"
195	"define void @c3() {\n"
196	"entry:\n"
197	" %a = alloca void ()*\n"
198	" store void ()* @c1, void ()** %a\n"
199	" ret void\n"
200	"}\n"
201	"define void @d1() {\n"
202	"entry:\n"
203	" %a = alloca void ()*\n"
204	" store void ()* @d2, void ()** %a\n"
205	" ret void\n"
206	"}\n"
207	"define void @d2() {\n"
208	"entry:\n"
209	" %a = alloca void ()*\n"
210	" store void ()* @d3, void ()** %a\n"
211	" ret void\n"
212	"}\n"
213	"define void @d3() {\n"
214	"entry:\n"
215	" %a = alloca void ()*\n"
216	" store void ()* @d1, void ()** %a\n"
217	" ret void\n"
218	"}\n";
219
220	static LazyCallGraph buildCG(Module &M) {
221	TargetLibraryInfoImpl TLII(Triple(M.getTargetTriple()));
222	TargetLibraryInfo TLI(TLII);
223	auto GetTLI = [&TLI](Function &F) -> TargetLibraryInfo & { return TLI; };
224
225	LazyCallGraph CG(M, GetTLI);
226	return CG;
227	}
228
229	TEST(LazyCallGraphTest, BasicGraphFormation) {
230	LLVMContext Context;
231	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: DiamondOfTriangles);
232	LazyCallGraph CG = buildCG(M&: *M);
233
234	// The order of the entry nodes should be stable w.r.t. the source order of
235	// the IR, and everything in our module is an entry node, so just directly
236	// build variables for each node.
237	auto I = CG.begin();
238	LazyCallGraph::Node &A1 = (I++)->getNode();
239	EXPECT_EQ("a1", A1.getFunction().getName());
240	LazyCallGraph::Node &A2 = (I++)->getNode();
241	EXPECT_EQ("a2", A2.getFunction().getName());
242	LazyCallGraph::Node &A3 = (I++)->getNode();
243	EXPECT_EQ("a3", A3.getFunction().getName());
244	LazyCallGraph::Node &B1 = (I++)->getNode();
245	EXPECT_EQ("b1", B1.getFunction().getName());
246	LazyCallGraph::Node &B2 = (I++)->getNode();
247	EXPECT_EQ("b2", B2.getFunction().getName());
248	LazyCallGraph::Node &B3 = (I++)->getNode();
249	EXPECT_EQ("b3", B3.getFunction().getName());
250	LazyCallGraph::Node &C1 = (I++)->getNode();
251	EXPECT_EQ("c1", C1.getFunction().getName());
252	LazyCallGraph::Node &C2 = (I++)->getNode();
253	EXPECT_EQ("c2", C2.getFunction().getName());
254	LazyCallGraph::Node &C3 = (I++)->getNode();
255	EXPECT_EQ("c3", C3.getFunction().getName());
256	LazyCallGraph::Node &D1 = (I++)->getNode();
257	EXPECT_EQ("d1", D1.getFunction().getName());
258	LazyCallGraph::Node &D2 = (I++)->getNode();
259	EXPECT_EQ("d2", D2.getFunction().getName());
260	LazyCallGraph::Node &D3 = (I++)->getNode();
261	EXPECT_EQ("d3", D3.getFunction().getName());
262	EXPECT_EQ(CG.end(), I);
263
264	// Build vectors and sort them for the rest of the assertions to make them
265	// independent of order.
266	std::vector<std::string> Nodes;
267
268	for (LazyCallGraph::Edge &E : A1.populate())
269	Nodes.push_back(x: std::string(E.getFunction().getName()));
270	llvm::sort(C&: Nodes);
271	EXPECT_EQ("a2", Nodes[0]);
272	EXPECT_EQ("b2", Nodes[1]);
273	EXPECT_EQ("c3", Nodes[2]);
274	Nodes.clear();
275
276	A2.populate();
277	EXPECT_EQ(A2->end(), std::next(A2->begin()));
278	EXPECT_EQ("a3", A2->begin()->getFunction().getName());
279	A3.populate();
280	EXPECT_EQ(A3->end(), std::next(A3->begin()));
281	EXPECT_EQ("a1", A3->begin()->getFunction().getName());
282
283	for (LazyCallGraph::Edge &E : B1.populate())
284	Nodes.push_back(x: std::string(E.getFunction().getName()));
285	llvm::sort(C&: Nodes);
286	EXPECT_EQ("b2", Nodes[0]);
287	EXPECT_EQ("d3", Nodes[1]);
288	Nodes.clear();
289
290	B2.populate();
291	EXPECT_EQ(B2->end(), std::next(B2->begin()));
292	EXPECT_EQ("b3", B2->begin()->getFunction().getName());
293	B3.populate();
294	EXPECT_EQ(B3->end(), std::next(B3->begin()));
295	EXPECT_EQ("b1", B3->begin()->getFunction().getName());
296
297	for (LazyCallGraph::Edge &E : C1.populate())
298	Nodes.push_back(x: std::string(E.getFunction().getName()));
299	llvm::sort(C&: Nodes);
300	EXPECT_EQ("c2", Nodes[0]);
301	EXPECT_EQ("d2", Nodes[1]);
302	Nodes.clear();
303
304	C2.populate();
305	EXPECT_EQ(C2->end(), std::next(C2->begin()));
306	EXPECT_EQ("c3", C2->begin()->getFunction().getName());
307	C3.populate();
308	EXPECT_EQ(C3->end(), std::next(C3->begin()));
309	EXPECT_EQ("c1", C3->begin()->getFunction().getName());
310
311	D1.populate();
312	EXPECT_EQ(D1->end(), std::next(D1->begin()));
313	EXPECT_EQ("d2", D1->begin()->getFunction().getName());
314	D2.populate();
315	EXPECT_EQ(D2->end(), std::next(D2->begin()));
316	EXPECT_EQ("d3", D2->begin()->getFunction().getName());
317	D3.populate();
318	EXPECT_EQ(D3->end(), std::next(D3->begin()));
319	EXPECT_EQ("d1", D3->begin()->getFunction().getName());
320
321	// Now lets look at the RefSCCs and SCCs.
322	CG.buildRefSCCs();
323	auto J = CG.postorder_ref_scc_begin();
324
325	LazyCallGraph::RefSCC &D = *J++;
326	ASSERT_EQ(1, D.size());
327	for (LazyCallGraph::Node &N : *D.begin())
328	Nodes.push_back(x: std::string(N.getFunction().getName()));
329	llvm::sort(C&: Nodes);
330	EXPECT_EQ(3u, Nodes.size());
331	EXPECT_EQ("d1", Nodes[0]);
332	EXPECT_EQ("d2", Nodes[1]);
333	EXPECT_EQ("d3", Nodes[2]);
334	Nodes.clear();
335	EXPECT_FALSE(D.isParentOf(D));
336	EXPECT_FALSE(D.isChildOf(D));
337	EXPECT_FALSE(D.isAncestorOf(D));
338	EXPECT_FALSE(D.isDescendantOf(D));
339	EXPECT_EQ(&D, &*CG.postorder_ref_scc_begin());
340
341	LazyCallGraph::RefSCC &B = *J++;
342	ASSERT_EQ(1, B.size());
343	for (LazyCallGraph::Node &N : *B.begin())
344	Nodes.push_back(x: std::string(N.getFunction().getName()));
345	llvm::sort(C&: Nodes);
346	EXPECT_EQ(3u, Nodes.size());
347	EXPECT_EQ("b1", Nodes[0]);
348	EXPECT_EQ("b2", Nodes[1]);
349	EXPECT_EQ("b3", Nodes[2]);
350	Nodes.clear();
351	EXPECT_TRUE(B.isParentOf(D));
352	EXPECT_FALSE(B.isChildOf(D));
353	EXPECT_TRUE(B.isAncestorOf(D));
354	EXPECT_FALSE(B.isDescendantOf(D));
355	EXPECT_EQ(&B, &*std::next(CG.postorder_ref_scc_begin()));
356
357	LazyCallGraph::RefSCC &C = *J++;
358	ASSERT_EQ(1, C.size());
359	for (LazyCallGraph::Node &N : *C.begin())
360	Nodes.push_back(x: std::string(N.getFunction().getName()));
361	llvm::sort(C&: Nodes);
362	EXPECT_EQ(3u, Nodes.size());
363	EXPECT_EQ("c1", Nodes[0]);
364	EXPECT_EQ("c2", Nodes[1]);
365	EXPECT_EQ("c3", Nodes[2]);
366	Nodes.clear();
367	EXPECT_FALSE(B.isAncestorOf(C));
368	EXPECT_FALSE(C.isAncestorOf(B));
369	EXPECT_TRUE(C.isParentOf(D));
370	EXPECT_FALSE(C.isChildOf(D));
371	EXPECT_TRUE(C.isAncestorOf(D));
372	EXPECT_FALSE(C.isDescendantOf(D));
373	EXPECT_EQ(&C, &*std::next(CG.postorder_ref_scc_begin(), 2));
374
375	LazyCallGraph::RefSCC &A = *J++;
376	ASSERT_EQ(1, A.size());
377	for (LazyCallGraph::Node &N : *A.begin())
378	Nodes.push_back(x: std::string(N.getFunction().getName()));
379	llvm::sort(C&: Nodes);
380	EXPECT_EQ(3u, Nodes.size());
381	EXPECT_EQ("a1", Nodes[0]);
382	EXPECT_EQ("a2", Nodes[1]);
383	EXPECT_EQ("a3", Nodes[2]);
384	Nodes.clear();
385	EXPECT_TRUE(A.isParentOf(B));
386	EXPECT_TRUE(A.isParentOf(C));
387	EXPECT_FALSE(A.isParentOf(D));
388	EXPECT_TRUE(A.isAncestorOf(B));
389	EXPECT_TRUE(A.isAncestorOf(C));
390	EXPECT_TRUE(A.isAncestorOf(D));
391	EXPECT_EQ(&A, &*std::next(CG.postorder_ref_scc_begin(), 3));
392
393	EXPECT_EQ(CG.postorder_ref_scc_end(), J);
394	EXPECT_EQ(J, std::next(CG.postorder_ref_scc_begin(), 4));
395	}
396
397	static Function &lookupFunction(Module &M, StringRef Name) {
398	for (Function &F : M)
399	if (F.getName() == Name)
400	return F;
401	report_fatal_error(reason: "Couldn't find function!");
402	}
403
404	TEST(LazyCallGraphTest, BasicGraphMutation) {
405	LLVMContext Context;
406	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @a() {\n"
407	"entry:\n"
408	" call void @b()\n"
409	" call void @c()\n"
410	" ret void\n"
411	"}\n"
412	"define void @b() {\n"
413	"entry:\n"
414	" ret void\n"
415	"}\n"
416	"define void @c() {\n"
417	"entry:\n"
418	" ret void\n"
419	"}\n");
420	LazyCallGraph CG = buildCG(M&: *M);
421
422	LazyCallGraph::Node &A = CG.get(F&: lookupFunction(M&: *M, Name: "a"));
423	LazyCallGraph::Node &B = CG.get(F&: lookupFunction(M&: *M, Name: "b"));
424	A.populate();
425	EXPECT_EQ(2, std::distance(A->begin(), A->end()));
426	B.populate();
427	EXPECT_EQ(0, std::distance(B->begin(), B->end()));
428
429	LazyCallGraph::Node &C = CG.get(F&: lookupFunction(M&: *M, Name: "c"));
430	C.populate();
431	CG.insertEdge(SourceN&: B, TargetN&: C, EK: LazyCallGraph::Edge::Call);
432	EXPECT_EQ(1, std::distance(B->begin(), B->end()));
433	EXPECT_EQ(0, std::distance(C->begin(), C->end()));
434
435	CG.insertEdge(SourceN&: C, TargetN&: B, EK: LazyCallGraph::Edge::Call);
436	EXPECT_EQ(1, std::distance(C->begin(), C->end()));
437	EXPECT_EQ(&B, &C->begin()->getNode());
438
439	CG.insertEdge(SourceN&: C, TargetN&: C, EK: LazyCallGraph::Edge::Call);
440	EXPECT_EQ(2, std::distance(C->begin(), C->end()));
441	EXPECT_EQ(&B, &C->begin()->getNode());
442	EXPECT_EQ(&C, &std::next(C->begin())->getNode());
443
444	CG.removeEdge(SourceN&: C, TargetN&: B);
445	EXPECT_EQ(1, std::distance(C->begin(), C->end()));
446	EXPECT_EQ(&C, &C->begin()->getNode());
447
448	CG.removeEdge(SourceN&: C, TargetN&: C);
449	EXPECT_EQ(0, std::distance(C->begin(), C->end()));
450
451	CG.removeEdge(SourceN&: B, TargetN&: C);
452	EXPECT_EQ(0, std::distance(B->begin(), B->end()));
453	}
454
455	TEST(LazyCallGraphTest, InnerSCCFormation) {
456	LLVMContext Context;
457	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: DiamondOfTriangles);
458	LazyCallGraph CG = buildCG(M&: *M);
459
460	// Now mutate the graph to connect every node into a single RefSCC to ensure
461	// that our inner SCC formation handles the rest.
462	LazyCallGraph::Node &D1 = CG.get(F&: lookupFunction(M&: *M, Name: "d1"));
463	LazyCallGraph::Node &A1 = CG.get(F&: lookupFunction(M&: *M, Name: "a1"));
464	A1.populate();
465	D1.populate();
466	CG.insertEdge(SourceN&: D1, TargetN&: A1, EK: LazyCallGraph::Edge::Ref);
467
468	// Build vectors and sort them for the rest of the assertions to make them
469	// independent of order.
470	std::vector<std::string> Nodes;
471
472	// We should build a single RefSCC for the entire graph.
473	CG.buildRefSCCs();
474	auto I = CG.postorder_ref_scc_begin();
475	LazyCallGraph::RefSCC &RC = *I++;
476	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
477
478	// Now walk the four SCCs which should be in post-order.
479	auto J = RC.begin();
480	LazyCallGraph::SCC &D = *J++;
481	for (LazyCallGraph::Node &N : D)
482	Nodes.push_back(x: std::string(N.getFunction().getName()));
483	llvm::sort(C&: Nodes);
484	EXPECT_EQ(3u, Nodes.size());
485	EXPECT_EQ("d1", Nodes[0]);
486	EXPECT_EQ("d2", Nodes[1]);
487	EXPECT_EQ("d3", Nodes[2]);
488	Nodes.clear();
489
490	LazyCallGraph::SCC &B = *J++;
491	for (LazyCallGraph::Node &N : B)
492	Nodes.push_back(x: std::string(N.getFunction().getName()));
493	llvm::sort(C&: Nodes);
494	EXPECT_EQ(3u, Nodes.size());
495	EXPECT_EQ("b1", Nodes[0]);
496	EXPECT_EQ("b2", Nodes[1]);
497	EXPECT_EQ("b3", Nodes[2]);
498	Nodes.clear();
499
500	LazyCallGraph::SCC &C = *J++;
501	for (LazyCallGraph::Node &N : C)
502	Nodes.push_back(x: std::string(N.getFunction().getName()));
503	llvm::sort(C&: Nodes);
504	EXPECT_EQ(3u, Nodes.size());
505	EXPECT_EQ("c1", Nodes[0]);
506	EXPECT_EQ("c2", Nodes[1]);
507	EXPECT_EQ("c3", Nodes[2]);
508	Nodes.clear();
509
510	LazyCallGraph::SCC &A = *J++;
511	for (LazyCallGraph::Node &N : A)
512	Nodes.push_back(x: std::string(N.getFunction().getName()));
513	llvm::sort(C&: Nodes);
514	EXPECT_EQ(3u, Nodes.size());
515	EXPECT_EQ("a1", Nodes[0]);
516	EXPECT_EQ("a2", Nodes[1]);
517	EXPECT_EQ("a3", Nodes[2]);
518	Nodes.clear();
519
520	EXPECT_EQ(RC.end(), J);
521	}
522
523	TEST(LazyCallGraphTest, MultiArmSCC) {
524	LLVMContext Context;
525	// Two interlocking cycles. The really useful thing about this SCC is that it
526	// will require Tarjan's DFS to backtrack and finish processing all of the
527	// children of each node in the SCC. Since this involves call edges, both
528	// Tarjan implementations will have to successfully navigate the structure.
529	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f1() {\n"
530	"entry:\n"
531	" call void @f2()\n"
532	" call void @f4()\n"
533	" ret void\n"
534	"}\n"
535	"define void @f2() {\n"
536	"entry:\n"
537	" call void @f3()\n"
538	" ret void\n"
539	"}\n"
540	"define void @f3() {\n"
541	"entry:\n"
542	" call void @f1()\n"
543	" ret void\n"
544	"}\n"
545	"define void @f4() {\n"
546	"entry:\n"
547	" call void @f5()\n"
548	" ret void\n"
549	"}\n"
550	"define void @f5() {\n"
551	"entry:\n"
552	" call void @f1()\n"
553	" ret void\n"
554	"}\n");
555	LazyCallGraph CG = buildCG(M&: *M);
556
557	// Force the graph to be fully expanded.
558	CG.buildRefSCCs();
559	auto I = CG.postorder_ref_scc_begin();
560	LazyCallGraph::RefSCC &RC = *I++;
561	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
562
563	LazyCallGraph::Node &N1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "f1"));
564	LazyCallGraph::Node &N2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "f2"));
565	LazyCallGraph::Node &N3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "f3"));
566	LazyCallGraph::Node &N4 = *CG.lookup(F: lookupFunction(M&: *M, Name: "f4"));
567	LazyCallGraph::Node &N5 = *CG.lookup(F: lookupFunction(M&: *M, Name: "f4"));
568	EXPECT_EQ(&RC, CG.lookupRefSCC(N1));
569	EXPECT_EQ(&RC, CG.lookupRefSCC(N2));
570	EXPECT_EQ(&RC, CG.lookupRefSCC(N3));
571	EXPECT_EQ(&RC, CG.lookupRefSCC(N4));
572	EXPECT_EQ(&RC, CG.lookupRefSCC(N5));
573
574	ASSERT_EQ(1, RC.size());
575
576	LazyCallGraph::SCC &C = *RC.begin();
577	EXPECT_EQ(&C, CG.lookupSCC(N1));
578	EXPECT_EQ(&C, CG.lookupSCC(N2));
579	EXPECT_EQ(&C, CG.lookupSCC(N3));
580	EXPECT_EQ(&C, CG.lookupSCC(N4));
581	EXPECT_EQ(&C, CG.lookupSCC(N5));
582	}
583
584	TEST(LazyCallGraphTest, OutgoingEdgeMutation) {
585	LLVMContext Context;
586	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @a() {\n"
587	"entry:\n"
588	" call void @b()\n"
589	" call void @c()\n"
590	" ret void\n"
591	"}\n"
592	"define void @b() {\n"
593	"entry:\n"
594	" call void @d()\n"
595	" ret void\n"
596	"}\n"
597	"define void @c() {\n"
598	"entry:\n"
599	" call void @d()\n"
600	" ret void\n"
601	"}\n"
602	"define void @d() {\n"
603	"entry:\n"
604	" ret void\n"
605	"}\n");
606	LazyCallGraph CG = buildCG(M&: *M);
607
608	// Force the graph to be fully expanded.
609	CG.buildRefSCCs();
610	for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
611	dbgs() << "Formed RefSCC: " << RC << "\n";
612
613	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
614	LazyCallGraph::Node &B = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
615	LazyCallGraph::Node &C = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
616	LazyCallGraph::Node &D = *CG.lookup(F: lookupFunction(M&: *M, Name: "d"));
617	LazyCallGraph::SCC &AC = *CG.lookupSCC(N&: A);
618	LazyCallGraph::SCC &BC = *CG.lookupSCC(N&: B);
619	LazyCallGraph::SCC &CC = *CG.lookupSCC(N&: C);
620	LazyCallGraph::SCC &DC = *CG.lookupSCC(N&: D);
621	LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(N&: A);
622	LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(N&: B);
623	LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(N&: C);
624	LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(N&: D);
625	EXPECT_TRUE(ARC.isParentOf(BRC));
626	EXPECT_TRUE(AC.isParentOf(BC));
627	EXPECT_TRUE(ARC.isParentOf(CRC));
628	EXPECT_TRUE(AC.isParentOf(CC));
629	EXPECT_FALSE(ARC.isParentOf(DRC));
630	EXPECT_FALSE(AC.isParentOf(DC));
631	EXPECT_TRUE(ARC.isAncestorOf(DRC));
632	EXPECT_TRUE(AC.isAncestorOf(DC));
633	EXPECT_FALSE(DRC.isChildOf(ARC));
634	EXPECT_FALSE(DC.isChildOf(AC));
635	EXPECT_TRUE(DRC.isDescendantOf(ARC));
636	EXPECT_TRUE(DC.isDescendantOf(AC));
637	EXPECT_TRUE(DRC.isChildOf(BRC));
638	EXPECT_TRUE(DC.isChildOf(BC));
639	EXPECT_TRUE(DRC.isChildOf(CRC));
640	EXPECT_TRUE(DC.isChildOf(CC));
641
642	EXPECT_EQ(2, std::distance(A->begin(), A->end()));
643	ARC.insertOutgoingEdge(SourceN&: A, TargetN&: D, EK: LazyCallGraph::Edge::Call);
644	EXPECT_EQ(3, std::distance(A->begin(), A->end()));
645	const LazyCallGraph::Edge &NewE = (*A)[D];
646	EXPECT_TRUE(NewE);
647	EXPECT_TRUE(NewE.isCall());
648	EXPECT_EQ(&D, &NewE.getNode());
649
650	// Only the parent and child tests sholud have changed. The rest of the graph
651	// remains the same.
652	EXPECT_TRUE(ARC.isParentOf(DRC));
653	EXPECT_TRUE(AC.isParentOf(DC));
654	EXPECT_TRUE(ARC.isAncestorOf(DRC));
655	EXPECT_TRUE(AC.isAncestorOf(DC));
656	EXPECT_TRUE(DRC.isChildOf(ARC));
657	EXPECT_TRUE(DC.isChildOf(AC));
658	EXPECT_TRUE(DRC.isDescendantOf(ARC));
659	EXPECT_TRUE(DC.isDescendantOf(AC));
660	EXPECT_EQ(&AC, CG.lookupSCC(A));
661	EXPECT_EQ(&BC, CG.lookupSCC(B));
662	EXPECT_EQ(&CC, CG.lookupSCC(C));
663	EXPECT_EQ(&DC, CG.lookupSCC(D));
664	EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
665	EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
666	EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
667	EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
668
669	ARC.switchOutgoingEdgeToRef(SourceN&: A, TargetN&: D);
670	EXPECT_FALSE(NewE.isCall());
671
672	// Verify the reference graph remains the same but the SCC graph is updated.
673	EXPECT_TRUE(ARC.isParentOf(DRC));
674	EXPECT_FALSE(AC.isParentOf(DC));
675	EXPECT_TRUE(ARC.isAncestorOf(DRC));
676	EXPECT_TRUE(AC.isAncestorOf(DC));
677	EXPECT_TRUE(DRC.isChildOf(ARC));
678	EXPECT_FALSE(DC.isChildOf(AC));
679	EXPECT_TRUE(DRC.isDescendantOf(ARC));
680	EXPECT_TRUE(DC.isDescendantOf(AC));
681	EXPECT_EQ(&AC, CG.lookupSCC(A));
682	EXPECT_EQ(&BC, CG.lookupSCC(B));
683	EXPECT_EQ(&CC, CG.lookupSCC(C));
684	EXPECT_EQ(&DC, CG.lookupSCC(D));
685	EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
686	EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
687	EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
688	EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
689
690	ARC.switchOutgoingEdgeToCall(SourceN&: A, TargetN&: D);
691	EXPECT_TRUE(NewE.isCall());
692
693	// Verify the reference graph remains the same but the SCC graph is updated.
694	EXPECT_TRUE(ARC.isParentOf(DRC));
695	EXPECT_TRUE(AC.isParentOf(DC));
696	EXPECT_TRUE(ARC.isAncestorOf(DRC));
697	EXPECT_TRUE(AC.isAncestorOf(DC));
698	EXPECT_TRUE(DRC.isChildOf(ARC));
699	EXPECT_TRUE(DC.isChildOf(AC));
700	EXPECT_TRUE(DRC.isDescendantOf(ARC));
701	EXPECT_TRUE(DC.isDescendantOf(AC));
702	EXPECT_EQ(&AC, CG.lookupSCC(A));
703	EXPECT_EQ(&BC, CG.lookupSCC(B));
704	EXPECT_EQ(&CC, CG.lookupSCC(C));
705	EXPECT_EQ(&DC, CG.lookupSCC(D));
706	EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
707	EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
708	EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
709	EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
710
711	ARC.removeOutgoingEdge(SourceN&: A, TargetN&: D);
712	EXPECT_EQ(2, std::distance(A->begin(), A->end()));
713
714	// Now the parent and child tests fail again but the rest remains the same.
715	EXPECT_FALSE(ARC.isParentOf(DRC));
716	EXPECT_FALSE(AC.isParentOf(DC));
717	EXPECT_TRUE(ARC.isAncestorOf(DRC));
718	EXPECT_TRUE(AC.isAncestorOf(DC));
719	EXPECT_FALSE(DRC.isChildOf(ARC));
720	EXPECT_FALSE(DC.isChildOf(AC));
721	EXPECT_TRUE(DRC.isDescendantOf(ARC));
722	EXPECT_TRUE(DC.isDescendantOf(AC));
723	EXPECT_EQ(&AC, CG.lookupSCC(A));
724	EXPECT_EQ(&BC, CG.lookupSCC(B));
725	EXPECT_EQ(&CC, CG.lookupSCC(C));
726	EXPECT_EQ(&DC, CG.lookupSCC(D));
727	EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
728	EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
729	EXPECT_EQ(&CRC, CG.lookupRefSCC(C));
730	EXPECT_EQ(&DRC, CG.lookupRefSCC(D));
731	}
732
733	TEST(LazyCallGraphTest, IncomingEdgeInsertion) {
734	LLVMContext Context;
735	// We want to ensure we can add edges even across complex diamond graphs, so
736	// we use the diamond of triangles graph defined above. The ascii diagram is
737	// repeated here for easy reference.
738	//
739	// d1 |
740	// / \ |
741	// d3--d2 |
742	// / \ |
743	// b1 c1 |
744	// / \ / \ |
745	// b3--b2 c3--c2 |
746	// \ / |
747	// a1 |
748	// / \ |
749	// a3--a2 |
750	//
751	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: DiamondOfTriangles);
752	LazyCallGraph CG = buildCG(M&: *M);
753
754	// Force the graph to be fully expanded.
755	CG.buildRefSCCs();
756	for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
757	dbgs() << "Formed RefSCC: " << RC << "\n";
758
759	LazyCallGraph::Node &A1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a1"));
760	LazyCallGraph::Node &A2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a2"));
761	LazyCallGraph::Node &A3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a3"));
762	LazyCallGraph::Node &B1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b1"));
763	LazyCallGraph::Node &B2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b2"));
764	LazyCallGraph::Node &B3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b3"));
765	LazyCallGraph::Node &C1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c1"));
766	LazyCallGraph::Node &C2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c2"));
767	LazyCallGraph::Node &C3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c3"));
768	LazyCallGraph::Node &D1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d1"));
769	LazyCallGraph::Node &D2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d2"));
770	LazyCallGraph::Node &D3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d3"));
771	LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(N&: A1);
772	LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(N&: B1);
773	LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(N&: C1);
774	LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(N&: D1);
775	ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
776	ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
777	ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
778	ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
779	ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
780	ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
781	ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
782	ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
783	ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
784
785	// Add an edge to make the graph:
786	//
787	// d1 |
788	// / \ |
789	// d3--d2---. |
790	// / \ | |
791	// b1 c1 | |
792	// / \ / \ / |
793	// b3--b2 c3--c2 |
794	// \ / |
795	// a1 |
796	// / \ |
797	// a3--a2 |
798	auto MergedRCs = CRC.insertIncomingRefEdge(SourceN&: D2, TargetN&: C2);
799	// Make sure we connected the nodes.
800	for (LazyCallGraph::Edge E : *D2) {
801	if (&E.getNode() == &D3)
802	continue;
803	EXPECT_EQ(&C2, &E.getNode());
804	}
805	// And marked the D ref-SCC as no longer valid.
806	EXPECT_EQ(1u, MergedRCs.size());
807	EXPECT_EQ(&DRC, MergedRCs[0]);
808
809	// Make sure we have the correct nodes in the SCC sets.
810	EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
811	EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
812	EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
813	EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
814	EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
815	EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
816	EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
817	EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
818	EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
819	EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
820	EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
821	EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
822
823	// And that ancestry tests have been updated.
824	EXPECT_TRUE(ARC.isParentOf(CRC));
825	EXPECT_TRUE(BRC.isParentOf(CRC));
826
827	// And verify the post-order walk reflects the updated structure.
828	auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
829	ASSERT_NE(I, E);
830	EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
831	ASSERT_NE(++I, E);
832	EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
833	ASSERT_NE(++I, E);
834	EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
835	EXPECT_EQ(++I, E);
836	}
837
838	TEST(LazyCallGraphTest, IncomingEdgeInsertionRefGraph) {
839	LLVMContext Context;
840	// Another variation of the above test but with all the edges switched to
841	// references rather than calls.
842	std::unique_ptr<Module> M =
843	parseAssembly(Context, Assembly: DiamondOfTrianglesRefGraph);
844	LazyCallGraph CG = buildCG(M&: *M);
845
846	// Force the graph to be fully expanded.
847	CG.buildRefSCCs();
848	for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
849	dbgs() << "Formed RefSCC: " << RC << "\n";
850
851	LazyCallGraph::Node &A1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a1"));
852	LazyCallGraph::Node &A2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a2"));
853	LazyCallGraph::Node &A3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a3"));
854	LazyCallGraph::Node &B1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b1"));
855	LazyCallGraph::Node &B2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b2"));
856	LazyCallGraph::Node &B3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b3"));
857	LazyCallGraph::Node &C1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c1"));
858	LazyCallGraph::Node &C2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c2"));
859	LazyCallGraph::Node &C3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c3"));
860	LazyCallGraph::Node &D1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d1"));
861	LazyCallGraph::Node &D2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d2"));
862	LazyCallGraph::Node &D3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d3"));
863	LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(N&: A1);
864	LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(N&: B1);
865	LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(N&: C1);
866	LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(N&: D1);
867	ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
868	ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
869	ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
870	ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
871	ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
872	ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
873	ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
874	ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
875	ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
876
877	// Add an edge to make the graph:
878	//
879	// d1 |
880	// / \ |
881	// d3--d2---. |
882	// / \ | |
883	// b1 c1 | |
884	// / \ / \ / |
885	// b3--b2 c3--c2 |
886	// \ / |
887	// a1 |
888	// / \ |
889	// a3--a2 |
890	auto MergedRCs = CRC.insertIncomingRefEdge(SourceN&: D2, TargetN&: C2);
891	// Make sure we connected the nodes.
892	for (LazyCallGraph::Edge E : *D2) {
893	if (&E.getNode() == &D3)
894	continue;
895	EXPECT_EQ(&C2, &E.getNode());
896	}
897	// And marked the D ref-SCC as no longer valid.
898	EXPECT_EQ(1u, MergedRCs.size());
899	EXPECT_EQ(&DRC, MergedRCs[0]);
900
901	// Make sure we have the correct nodes in the SCC sets.
902	EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
903	EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
904	EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
905	EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
906	EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
907	EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
908	EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
909	EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
910	EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
911	EXPECT_EQ(&CRC, CG.lookupRefSCC(D1));
912	EXPECT_EQ(&CRC, CG.lookupRefSCC(D2));
913	EXPECT_EQ(&CRC, CG.lookupRefSCC(D3));
914
915	// And that ancestry tests have been updated.
916	EXPECT_TRUE(ARC.isParentOf(CRC));
917	EXPECT_TRUE(BRC.isParentOf(CRC));
918
919	// And verify the post-order walk reflects the updated structure.
920	auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
921	ASSERT_NE(I, E);
922	EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
923	ASSERT_NE(++I, E);
924	EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
925	ASSERT_NE(++I, E);
926	EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
927	EXPECT_EQ(++I, E);
928	}
929
930	TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeCallCycle) {
931	LLVMContext Context;
932	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @a() {\n"
933	"entry:\n"
934	" call void @b()\n"
935	" ret void\n"
936	"}\n"
937	"define void @b() {\n"
938	"entry:\n"
939	" call void @c()\n"
940	" ret void\n"
941	"}\n"
942	"define void @c() {\n"
943	"entry:\n"
944	" call void @d()\n"
945	" ret void\n"
946	"}\n"
947	"define void @d() {\n"
948	"entry:\n"
949	" ret void\n"
950	"}\n");
951	LazyCallGraph CG = buildCG(M&: *M);
952
953	// Force the graph to be fully expanded.
954	CG.buildRefSCCs();
955	for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
956	dbgs() << "Formed RefSCC: " << RC << "\n";
957
958	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
959	LazyCallGraph::Node &B = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
960	LazyCallGraph::Node &C = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
961	LazyCallGraph::Node &D = *CG.lookup(F: lookupFunction(M&: *M, Name: "d"));
962	LazyCallGraph::SCC &AC = *CG.lookupSCC(N&: A);
963	LazyCallGraph::SCC &BC = *CG.lookupSCC(N&: B);
964	LazyCallGraph::SCC &CC = *CG.lookupSCC(N&: C);
965	LazyCallGraph::SCC &DC = *CG.lookupSCC(N&: D);
966	LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(N&: A);
967	LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(N&: B);
968	LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(N&: C);
969	LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(N&: D);
970
971	// Connect the top to the bottom forming a large RefSCC made up mostly of calls.
972	auto MergedRCs = ARC.insertIncomingRefEdge(SourceN&: D, TargetN&: A);
973	// Make sure we connected the nodes.
974	EXPECT_NE(D->begin(), D->end());
975	EXPECT_EQ(&A, &D->begin()->getNode());
976
977	// Check that we have the dead RCs, but ignore the order.
978	EXPECT_EQ(3u, MergedRCs.size());
979	EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());
980	EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());
981	EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());
982
983	// Make sure the nodes point to the right place now.
984	EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
985	EXPECT_EQ(&ARC, CG.lookupRefSCC(B));
986	EXPECT_EQ(&ARC, CG.lookupRefSCC(C));
987	EXPECT_EQ(&ARC, CG.lookupRefSCC(D));
988
989	// Check that the SCCs are in postorder.
990	EXPECT_EQ(4, ARC.size());
991	EXPECT_EQ(&DC, &ARC[0]);
992	EXPECT_EQ(&CC, &ARC[1]);
993	EXPECT_EQ(&BC, &ARC[2]);
994	EXPECT_EQ(&AC, &ARC[3]);
995
996	// And verify the post-order walk reflects the updated structure.
997	auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
998	ASSERT_NE(I, E);
999	EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1000	EXPECT_EQ(++I, E);
1001	}
1002
1003	TEST(LazyCallGraphTest, IncomingEdgeInsertionLargeRefCycle) {
1004	LLVMContext Context;
1005	std::unique_ptr<Module> M =
1006	parseAssembly(Context, Assembly: "define void @a() {\n"
1007	"entry:\n"
1008	" %p = alloca void ()*\n"
1009	" store void ()* @b, void ()** %p\n"
1010	" ret void\n"
1011	"}\n"
1012	"define void @b() {\n"
1013	"entry:\n"
1014	" %p = alloca void ()*\n"
1015	" store void ()* @c, void ()** %p\n"
1016	" ret void\n"
1017	"}\n"
1018	"define void @c() {\n"
1019	"entry:\n"
1020	" %p = alloca void ()*\n"
1021	" store void ()* @d, void ()** %p\n"
1022	" ret void\n"
1023	"}\n"
1024	"define void @d() {\n"
1025	"entry:\n"
1026	" ret void\n"
1027	"}\n");
1028	LazyCallGraph CG = buildCG(M&: *M);
1029
1030	// Force the graph to be fully expanded.
1031	CG.buildRefSCCs();
1032	for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
1033	dbgs() << "Formed RefSCC: " << RC << "\n";
1034
1035	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1036	LazyCallGraph::Node &B = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
1037	LazyCallGraph::Node &C = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
1038	LazyCallGraph::Node &D = *CG.lookup(F: lookupFunction(M&: *M, Name: "d"));
1039	LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(N&: A);
1040	LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(N&: B);
1041	LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(N&: C);
1042	LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(N&: D);
1043
1044	// Connect the top to the bottom forming a large RefSCC made up just of
1045	// references.
1046	auto MergedRCs = ARC.insertIncomingRefEdge(SourceN&: D, TargetN&: A);
1047	// Make sure we connected the nodes.
1048	EXPECT_NE(D->begin(), D->end());
1049	EXPECT_EQ(&A, &D->begin()->getNode());
1050
1051	// Check that we have the dead RCs, but ignore the order.
1052	EXPECT_EQ(3u, MergedRCs.size());
1053	EXPECT_NE(find(MergedRCs, &BRC), MergedRCs.end());
1054	EXPECT_NE(find(MergedRCs, &CRC), MergedRCs.end());
1055	EXPECT_NE(find(MergedRCs, &DRC), MergedRCs.end());
1056
1057	// Make sure the nodes point to the right place now.
1058	EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
1059	EXPECT_EQ(&ARC, CG.lookupRefSCC(B));
1060	EXPECT_EQ(&ARC, CG.lookupRefSCC(C));
1061	EXPECT_EQ(&ARC, CG.lookupRefSCC(D));
1062
1063	// And verify the post-order walk reflects the updated structure.
1064	auto I = CG.postorder_ref_scc_begin(), End = CG.postorder_ref_scc_end();
1065	ASSERT_NE(I, End);
1066	EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1067	EXPECT_EQ(++I, End);
1068	}
1069
1070	TEST(LazyCallGraphTest, InlineAndDeleteFunction) {
1071	LLVMContext Context;
1072	// We want to ensure we can delete nodes from relatively complex graphs and
1073	// so use the diamond of triangles graph defined above.
1074	//
1075	// The ascii diagram is repeated here for easy reference.
1076	//
1077	// d1 |
1078	// / \ |
1079	// d3--d2 |
1080	// / \ |
1081	// b1 c1 |
1082	// / \ / \ |
1083	// b3--b2 c3--c2 |
1084	// \ / |
1085	// a1 |
1086	// / \ |
1087	// a3--a2 |
1088	//
1089	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: DiamondOfTriangles);
1090	LazyCallGraph CG = buildCG(M&: *M);
1091
1092	// Force the graph to be fully expanded.
1093	CG.buildRefSCCs();
1094	for (LazyCallGraph::RefSCC &RC : CG.postorder_ref_sccs())
1095	dbgs() << "Formed RefSCC: " << RC << "\n";
1096
1097	LazyCallGraph::Node &A1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a1"));
1098	LazyCallGraph::Node &A2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a2"));
1099	LazyCallGraph::Node &A3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "a3"));
1100	LazyCallGraph::Node &B1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b1"));
1101	LazyCallGraph::Node &B2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b2"));
1102	LazyCallGraph::Node &B3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b3"));
1103	LazyCallGraph::Node &C1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c1"));
1104	LazyCallGraph::Node &C2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c2"));
1105	LazyCallGraph::Node &C3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c3"));
1106	LazyCallGraph::Node &D1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d1"));
1107	LazyCallGraph::Node &D2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d2"));
1108	LazyCallGraph::Node &D3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "d3"));
1109	LazyCallGraph::RefSCC &ARC = *CG.lookupRefSCC(N&: A1);
1110	LazyCallGraph::RefSCC &BRC = *CG.lookupRefSCC(N&: B1);
1111	LazyCallGraph::RefSCC &CRC = *CG.lookupRefSCC(N&: C1);
1112	LazyCallGraph::RefSCC &DRC = *CG.lookupRefSCC(N&: D1);
1113	ASSERT_EQ(&ARC, CG.lookupRefSCC(A2));
1114	ASSERT_EQ(&ARC, CG.lookupRefSCC(A3));
1115	ASSERT_EQ(&BRC, CG.lookupRefSCC(B2));
1116	ASSERT_EQ(&BRC, CG.lookupRefSCC(B3));
1117	ASSERT_EQ(&CRC, CG.lookupRefSCC(C2));
1118	ASSERT_EQ(&CRC, CG.lookupRefSCC(C3));
1119	ASSERT_EQ(&DRC, CG.lookupRefSCC(D2));
1120	ASSERT_EQ(&DRC, CG.lookupRefSCC(D3));
1121	ASSERT_EQ(1, std::distance(D2->begin(), D2->end()));
1122
1123	// Delete d2 from the graph, as if it had been inlined.
1124	//
1125	// d1 |
1126	// / / |
1127	// d3--. |
1128	// / \ |
1129	// b1 c1 |
1130	// / \ / \ |
1131	// b3--b2 c3--c2 |
1132	// \ / |
1133	// a1 |
1134	// / \ |
1135	// a3--a2 |
1136
1137	Function &D2F = D2.getFunction();
1138	CallInst *C1Call = nullptr, *D1Call = nullptr;
1139	for (User *U : D2F.users()) {
1140	CallInst *CI = dyn_cast<CallInst>(Val: U);
1141	ASSERT_TRUE(CI) << "Expected a call: " << *U;
1142	if (CI->getParent()->getParent() == &C1.getFunction()) {
1143	ASSERT_EQ(nullptr, C1Call) << "Found too many C1 calls: " << *CI;
1144	C1Call = CI;
1145	} else if (CI->getParent()->getParent() == &D1.getFunction()) {
1146	ASSERT_EQ(nullptr, D1Call) << "Found too many D1 calls: " << *CI;
1147	D1Call = CI;
1148	} else {
1149	FAIL() << "Found an unexpected call instruction: " << *CI;
1150	}
1151	}
1152	ASSERT_NE(C1Call, nullptr);
1153	ASSERT_NE(D1Call, nullptr);
1154	ASSERT_EQ(&D2F, C1Call->getCalledFunction());
1155	ASSERT_EQ(&D2F, D1Call->getCalledFunction());
1156	C1Call->setCalledFunction(&D3.getFunction());
1157	D1Call->setCalledFunction(&D3.getFunction());
1158	ASSERT_EQ(0u, D2F.getNumUses());
1159
1160	// Insert new edges first.
1161	CRC.insertTrivialCallEdge(SourceN&: C1, TargetN&: D3);
1162	DRC.insertTrivialCallEdge(SourceN&: D1, TargetN&: D3);
1163
1164	// Then remove the old ones.
1165	LazyCallGraph::SCC &DC = *CG.lookupSCC(N&: D2);
1166	auto NewCs = DRC.switchInternalEdgeToRef(SourceN&: D1, TargetN&: D2);
1167	EXPECT_EQ(&DC, CG.lookupSCC(D2));
1168	EXPECT_EQ(NewCs.end(), std::next(NewCs.begin()));
1169	LazyCallGraph::SCC &NewDC = *NewCs.begin();
1170	EXPECT_EQ(&NewDC, CG.lookupSCC(D1));
1171	EXPECT_EQ(&NewDC, CG.lookupSCC(D3));
1172	auto NewRCs = DRC.removeInternalRefEdge(SourceN&: D1, TargetNs: {&D2});
1173	ASSERT_EQ(2u, NewRCs.size());
1174	LazyCallGraph::RefSCC &NewDRC = *NewRCs[0];
1175	EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
1176	EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
1177	LazyCallGraph::RefSCC &D2RC = *NewRCs[1];
1178	EXPECT_EQ(&D2RC, CG.lookupRefSCC(D2));
1179	EXPECT_FALSE(NewDRC.isParentOf(D2RC));
1180	EXPECT_TRUE(CRC.isParentOf(D2RC));
1181	EXPECT_TRUE(CRC.isParentOf(NewDRC));
1182	EXPECT_TRUE(D2RC.isParentOf(NewDRC));
1183	CRC.removeOutgoingEdge(SourceN&: C1, TargetN&: D2);
1184	EXPECT_FALSE(CRC.isParentOf(D2RC));
1185	EXPECT_TRUE(CRC.isParentOf(NewDRC));
1186	EXPECT_TRUE(D2RC.isParentOf(NewDRC));
1187
1188	// Now that we've updated the call graph, D2 is dead, so remove it.
1189	CG.removeDeadFunction(F&: D2F);
1190
1191	// Check that the graph still looks the same.
1192	EXPECT_EQ(&ARC, CG.lookupRefSCC(A1));
1193	EXPECT_EQ(&ARC, CG.lookupRefSCC(A2));
1194	EXPECT_EQ(&ARC, CG.lookupRefSCC(A3));
1195	EXPECT_EQ(&BRC, CG.lookupRefSCC(B1));
1196	EXPECT_EQ(&BRC, CG.lookupRefSCC(B2));
1197	EXPECT_EQ(&BRC, CG.lookupRefSCC(B3));
1198	EXPECT_EQ(&CRC, CG.lookupRefSCC(C1));
1199	EXPECT_EQ(&CRC, CG.lookupRefSCC(C2));
1200	EXPECT_EQ(&CRC, CG.lookupRefSCC(C3));
1201	EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D1));
1202	EXPECT_EQ(&NewDRC, CG.lookupRefSCC(D3));
1203	EXPECT_TRUE(CRC.isParentOf(NewDRC));
1204
1205	// Verify the post-order walk hasn't changed.
1206	auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1207	ASSERT_NE(I, E);
1208	EXPECT_EQ(&NewDRC, &*I) << "Actual RefSCC: " << *I;
1209	ASSERT_NE(++I, E);
1210	EXPECT_EQ(&BRC, &*I) << "Actual RefSCC: " << *I;
1211	ASSERT_NE(++I, E);
1212	EXPECT_EQ(&CRC, &*I) << "Actual RefSCC: " << *I;
1213	ASSERT_NE(++I, E);
1214	EXPECT_EQ(&ARC, &*I) << "Actual RefSCC: " << *I;
1215	EXPECT_EQ(++I, E);
1216	}
1217
1218	TEST(LazyCallGraphTest, InternalEdgeMutation) {
1219	LLVMContext Context;
1220	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @a() {\n"
1221	"entry:\n"
1222	" call void @b()\n"
1223	" ret void\n"
1224	"}\n"
1225	"define void @b() {\n"
1226	"entry:\n"
1227	" call void @c()\n"
1228	" ret void\n"
1229	"}\n"
1230	"define void @c() {\n"
1231	"entry:\n"
1232	" call void @a()\n"
1233	" ret void\n"
1234	"}\n");
1235	LazyCallGraph CG = buildCG(M&: *M);
1236
1237	// Force the graph to be fully expanded.
1238	CG.buildRefSCCs();
1239	auto I = CG.postorder_ref_scc_begin();
1240	LazyCallGraph::RefSCC &RC = *I++;
1241	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1242
1243	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1244	LazyCallGraph::Node &B = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
1245	LazyCallGraph::Node &C = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
1246	EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1247	EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1248	EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1249	EXPECT_EQ(1, RC.size());
1250	EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
1251	EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
1252	EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
1253
1254	// Insert an edge from 'a' to 'c'. Nothing changes about the graph.
1255	RC.insertInternalRefEdge(SourceN&: A, TargetN&: C);
1256	EXPECT_EQ(2, std::distance(A->begin(), A->end()));
1257	EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1258	EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1259	EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1260	EXPECT_EQ(1, RC.size());
1261	EXPECT_EQ(&*RC.begin(), CG.lookupSCC(A));
1262	EXPECT_EQ(&*RC.begin(), CG.lookupSCC(B));
1263	EXPECT_EQ(&*RC.begin(), CG.lookupSCC(C));
1264
1265	// Switch the call edge from 'b' to 'c' to a ref edge. This will break the
1266	// call cycle and cause us to form more SCCs. The RefSCC will remain the same
1267	// though.
1268	auto NewCs = RC.switchInternalEdgeToRef(SourceN&: B, TargetN&: C);
1269	EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1270	EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1271	EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1272	auto J = RC.begin();
1273	// The SCCs must be in *post-order* which means successors before
1274	// predecessors. At this point we have call edges from C to A and from A to
1275	// B. The only valid postorder is B, A, C.
1276	EXPECT_EQ(&*J++, CG.lookupSCC(B));
1277	EXPECT_EQ(&*J++, CG.lookupSCC(A));
1278	EXPECT_EQ(&*J++, CG.lookupSCC(C));
1279	EXPECT_EQ(RC.end(), J);
1280	// And the returned range must be the slice of this sequence containing new
1281	// SCCs.
1282	EXPECT_EQ(RC.begin(), NewCs.begin());
1283	EXPECT_EQ(std::prev(RC.end()), NewCs.end());
1284
1285	// Test turning the ref edge from A to C into a call edge. This will form an
1286	// SCC out of A and C. Since we previously had a call edge from C to A, the
1287	// C SCC should be preserved and have A merged into it while the A SCC should
1288	// be invalidated.
1289	LazyCallGraph::SCC &AC = *CG.lookupSCC(N&: A);
1290	LazyCallGraph::SCC &CC = *CG.lookupSCC(N&: C);
1291	EXPECT_TRUE(RC.switchInternalEdgeToCall(A, C, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1292	ASSERT_EQ(1u, MergedCs.size());
1293	EXPECT_EQ(&AC, MergedCs[0]);
1294	}));
1295	EXPECT_EQ(2, CC.size());
1296	EXPECT_EQ(&CC, CG.lookupSCC(A));
1297	EXPECT_EQ(&CC, CG.lookupSCC(C));
1298	J = RC.begin();
1299	EXPECT_EQ(&*J++, CG.lookupSCC(B));
1300	EXPECT_EQ(&*J++, CG.lookupSCC(C));
1301	EXPECT_EQ(RC.end(), J);
1302	}
1303
1304	TEST(LazyCallGraphTest, InternalEdgeRemoval) {
1305	LLVMContext Context;
1306	// A nice fully connected (including self-edges) RefSCC.
1307	std::unique_ptr<Module> M = parseAssembly(
1308	Context, Assembly: "define void @a(i8** %ptr) {\n"
1309	"entry:\n"
1310	" store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1311	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1312	" store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1313	" ret void\n"
1314	"}\n"
1315	"define void @b(i8** %ptr) {\n"
1316	"entry:\n"
1317	" store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1318	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1319	" store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1320	" ret void\n"
1321	"}\n"
1322	"define void @c(i8** %ptr) {\n"
1323	"entry:\n"
1324	" store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1325	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1326	" store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1327	" ret void\n"
1328	"}\n");
1329	LazyCallGraph CG = buildCG(M&: *M);
1330
1331	// Force the graph to be fully expanded.
1332	CG.buildRefSCCs();
1333	auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1334	LazyCallGraph::RefSCC &RC = *I;
1335	EXPECT_EQ(E, std::next(I));
1336
1337	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1338	LazyCallGraph::Node &B = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
1339	LazyCallGraph::Node &C = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
1340	EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1341	EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1342	EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1343
1344	// Remove the edge from b -> a, which should leave the 3 functions still in
1345	// a single connected component because of a -> b -> c -> a.
1346	SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1347	RC.removeInternalRefEdge(SourceN&: B, TargetNs: {&A});
1348	EXPECT_EQ(0u, NewRCs.size());
1349	EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1350	EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1351	EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1352	auto J = CG.postorder_ref_scc_begin();
1353	EXPECT_EQ(I, J);
1354	EXPECT_EQ(&RC, &*J);
1355	EXPECT_EQ(E, std::next(J));
1356
1357	// Increment I before we actually mutate the structure so that it remains
1358	// a valid iterator.
1359	++I;
1360
1361	// Remove the edge from c -> a, which should leave 'a' in the original RefSCC
1362	// and form a new RefSCC for 'b' and 'c'.
1363	NewRCs = RC.removeInternalRefEdge(SourceN&: C, TargetNs: {&A});
1364	ASSERT_EQ(2u, NewRCs.size());
1365	LazyCallGraph::RefSCC &BCRC = *NewRCs[0];
1366	LazyCallGraph::RefSCC &ARC = *NewRCs[1];
1367	EXPECT_EQ(&ARC, CG.lookupRefSCC(A));
1368	EXPECT_EQ(1, std::distance(ARC.begin(), ARC.end()));
1369	EXPECT_EQ(&BCRC, CG.lookupRefSCC(B));
1370	EXPECT_EQ(&BCRC, CG.lookupRefSCC(C));
1371	J = CG.postorder_ref_scc_begin();
1372	EXPECT_NE(I, J);
1373	EXPECT_EQ(&BCRC, &*J);
1374	++J;
1375	EXPECT_NE(I, J);
1376	EXPECT_EQ(&ARC, &*J);
1377	++J;
1378	EXPECT_EQ(I, J);
1379	EXPECT_EQ(E, J);
1380	}
1381
1382	TEST(LazyCallGraphTest, InternalMultiEdgeRemoval) {
1383	LLVMContext Context;
1384	// A nice fully connected (including self-edges) RefSCC.
1385	std::unique_ptr<Module> M = parseAssembly(
1386	Context, Assembly: "define void @a(i8** %ptr) {\n"
1387	"entry:\n"
1388	" store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1389	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1390	" store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1391	" ret void\n"
1392	"}\n"
1393	"define void @b(i8** %ptr) {\n"
1394	"entry:\n"
1395	" store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1396	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1397	" store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1398	" ret void\n"
1399	"}\n"
1400	"define void @c(i8** %ptr) {\n"
1401	"entry:\n"
1402	" store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1403	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1404	" store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1405	" ret void\n"
1406	"}\n");
1407	LazyCallGraph CG = buildCG(M&: *M);
1408
1409	// Force the graph to be fully expanded.
1410	CG.buildRefSCCs();
1411	auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1412	LazyCallGraph::RefSCC &RC = *I;
1413	EXPECT_EQ(E, std::next(I));
1414
1415	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1416	LazyCallGraph::Node &B = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
1417	LazyCallGraph::Node &C = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
1418	EXPECT_EQ(&RC, CG.lookupRefSCC(A));
1419	EXPECT_EQ(&RC, CG.lookupRefSCC(B));
1420	EXPECT_EQ(&RC, CG.lookupRefSCC(C));
1421
1422	// Increment I before we actually mutate the structure so that it remains
1423	// a valid iterator.
1424	++I;
1425
1426	// Remove the edges from b -> a and b -> c, leaving b in its own RefSCC.
1427	SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1428	RC.removeInternalRefEdge(SourceN&: B, TargetNs: {&A, &C});
1429
1430	ASSERT_EQ(2u, NewRCs.size());
1431	LazyCallGraph::RefSCC &BRC = *NewRCs[0];
1432	LazyCallGraph::RefSCC &ACRC = *NewRCs[1];
1433	EXPECT_EQ(&BRC, CG.lookupRefSCC(B));
1434	EXPECT_EQ(1, std::distance(BRC.begin(), BRC.end()));
1435	EXPECT_EQ(&ACRC, CG.lookupRefSCC(A));
1436	EXPECT_EQ(&ACRC, CG.lookupRefSCC(C));
1437	auto J = CG.postorder_ref_scc_begin();
1438	EXPECT_NE(I, J);
1439	EXPECT_EQ(&BRC, &*J);
1440	++J;
1441	EXPECT_NE(I, J);
1442	EXPECT_EQ(&ACRC, &*J);
1443	++J;
1444	EXPECT_EQ(I, J);
1445	EXPECT_EQ(E, J);
1446	}
1447
1448	TEST(LazyCallGraphTest, InternalNoOpEdgeRemoval) {
1449	LLVMContext Context;
1450	// A graph with a single cycle formed both from call and reference edges
1451	// which makes the reference edges trivial to delete. The graph looks like:
1452	//
1453	// Reference edges: a -> b -> c -> a
1454	// Call edges: a -> c -> b -> a
1455	std::unique_ptr<Module> M = parseAssembly(
1456	Context, Assembly: "define void @a(i8** %ptr) {\n"
1457	"entry:\n"
1458	" call void @b(i8** %ptr)\n"
1459	" store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
1460	" ret void\n"
1461	"}\n"
1462	"define void @b(i8** %ptr) {\n"
1463	"entry:\n"
1464	" store i8* bitcast (void(i8**)* @a to i8*), i8** %ptr\n"
1465	" call void @c(i8** %ptr)\n"
1466	" ret void\n"
1467	"}\n"
1468	"define void @c(i8** %ptr) {\n"
1469	"entry:\n"
1470	" call void @a(i8** %ptr)\n"
1471	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
1472	" ret void\n"
1473	"}\n");
1474	LazyCallGraph CG = buildCG(M&: *M);
1475
1476	// Force the graph to be fully expanded.
1477	CG.buildRefSCCs();
1478	auto I = CG.postorder_ref_scc_begin(), E = CG.postorder_ref_scc_end();
1479	LazyCallGraph::RefSCC &RC = *I;
1480	EXPECT_EQ(E, std::next(I));
1481
1482	LazyCallGraph::SCC &C = *RC.begin();
1483	EXPECT_EQ(RC.end(), std::next(RC.begin()));
1484
1485	LazyCallGraph::Node &AN = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1486	LazyCallGraph::Node &BN = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
1487	LazyCallGraph::Node &CN = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
1488	EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1489	EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1490	EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1491	EXPECT_EQ(&C, CG.lookupSCC(AN));
1492	EXPECT_EQ(&C, CG.lookupSCC(BN));
1493	EXPECT_EQ(&C, CG.lookupSCC(CN));
1494
1495	// Remove the edge from a -> c which doesn't change anything.
1496	SmallVector<LazyCallGraph::RefSCC *, 1> NewRCs =
1497	RC.removeInternalRefEdge(SourceN&: AN, TargetNs: {&CN});
1498	EXPECT_EQ(0u, NewRCs.size());
1499	EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1500	EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1501	EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1502	EXPECT_EQ(&C, CG.lookupSCC(AN));
1503	EXPECT_EQ(&C, CG.lookupSCC(BN));
1504	EXPECT_EQ(&C, CG.lookupSCC(CN));
1505	auto J = CG.postorder_ref_scc_begin();
1506	EXPECT_EQ(I, J);
1507	EXPECT_EQ(&RC, &*J);
1508	EXPECT_EQ(E, std::next(J));
1509
1510	// Remove the edge from b -> a and c -> b; again this doesn't change
1511	// anything.
1512	NewRCs = RC.removeInternalRefEdge(SourceN&: BN, TargetNs: {&AN});
1513	NewRCs = RC.removeInternalRefEdge(SourceN&: CN, TargetNs: {&BN});
1514	EXPECT_EQ(0u, NewRCs.size());
1515	EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
1516	EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
1517	EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
1518	EXPECT_EQ(&C, CG.lookupSCC(AN));
1519	EXPECT_EQ(&C, CG.lookupSCC(BN));
1520	EXPECT_EQ(&C, CG.lookupSCC(CN));
1521	J = CG.postorder_ref_scc_begin();
1522	EXPECT_EQ(I, J);
1523	EXPECT_EQ(&RC, &*J);
1524	EXPECT_EQ(E, std::next(J));
1525	}
1526
1527	TEST(LazyCallGraphTest, InternalCallEdgeToRef) {
1528	LLVMContext Context;
1529	// A nice fully connected (including self-edges) SCC (and RefSCC)
1530	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @a() {\n"
1531	"entry:\n"
1532	" call void @a()\n"
1533	" call void @b()\n"
1534	" call void @c()\n"
1535	" ret void\n"
1536	"}\n"
1537	"define void @b() {\n"
1538	"entry:\n"
1539	" call void @a()\n"
1540	" call void @b()\n"
1541	" call void @c()\n"
1542	" ret void\n"
1543	"}\n"
1544	"define void @c() {\n"
1545	"entry:\n"
1546	" call void @a()\n"
1547	" call void @b()\n"
1548	" call void @c()\n"
1549	" ret void\n"
1550	"}\n");
1551	LazyCallGraph CG = buildCG(M&: *M);
1552
1553	// Force the graph to be fully expanded.
1554	CG.buildRefSCCs();
1555	auto I = CG.postorder_ref_scc_begin();
1556	LazyCallGraph::RefSCC &RC = *I++;
1557	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1558
1559	EXPECT_EQ(1, RC.size());
1560	LazyCallGraph::SCC &AC = *RC.begin();
1561
1562	LazyCallGraph::Node &AN = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1563	LazyCallGraph::Node &BN = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
1564	LazyCallGraph::Node &CN = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
1565	EXPECT_EQ(&AC, CG.lookupSCC(AN));
1566	EXPECT_EQ(&AC, CG.lookupSCC(BN));
1567	EXPECT_EQ(&AC, CG.lookupSCC(CN));
1568
1569	// Remove the call edge from b -> a to a ref edge, which should leave the
1570	// 3 functions still in a single connected component because of a -> b ->
1571	// c -> a.
1572	auto NewCs = RC.switchInternalEdgeToRef(SourceN&: BN, TargetN&: AN);
1573	EXPECT_EQ(NewCs.begin(), NewCs.end());
1574	EXPECT_EQ(1, RC.size());
1575	EXPECT_EQ(&AC, CG.lookupSCC(AN));
1576	EXPECT_EQ(&AC, CG.lookupSCC(BN));
1577	EXPECT_EQ(&AC, CG.lookupSCC(CN));
1578
1579	// Remove the edge from c -> a, which should leave 'a' in the original SCC
1580	// and form a new SCC for 'b' and 'c'.
1581	NewCs = RC.switchInternalEdgeToRef(SourceN&: CN, TargetN&: AN);
1582	EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
1583	EXPECT_EQ(2, RC.size());
1584	EXPECT_EQ(&AC, CG.lookupSCC(AN));
1585	LazyCallGraph::SCC &BC = *CG.lookupSCC(N&: BN);
1586	EXPECT_NE(&BC, &AC);
1587	EXPECT_EQ(&BC, CG.lookupSCC(CN));
1588	auto J = RC.find(C&: AC);
1589	EXPECT_EQ(&AC, &*J);
1590	--J;
1591	EXPECT_EQ(&BC, &*J);
1592	EXPECT_EQ(RC.begin(), J);
1593	EXPECT_EQ(J, NewCs.begin());
1594
1595	// Remove the edge from c -> b, which should leave 'b' in the original SCC
1596	// and form a new SCC for 'c'. It shouldn't change 'a's SCC.
1597	NewCs = RC.switchInternalEdgeToRef(SourceN&: CN, TargetN&: BN);
1598	EXPECT_EQ(1, std::distance(NewCs.begin(), NewCs.end()));
1599	EXPECT_EQ(3, RC.size());
1600	EXPECT_EQ(&AC, CG.lookupSCC(AN));
1601	EXPECT_EQ(&BC, CG.lookupSCC(BN));
1602	LazyCallGraph::SCC &CC = *CG.lookupSCC(N&: CN);
1603	EXPECT_NE(&CC, &AC);
1604	EXPECT_NE(&CC, &BC);
1605	J = RC.find(C&: AC);
1606	EXPECT_EQ(&AC, &*J);
1607	--J;
1608	EXPECT_EQ(&BC, &*J);
1609	--J;
1610	EXPECT_EQ(&CC, &*J);
1611	EXPECT_EQ(RC.begin(), J);
1612	EXPECT_EQ(J, NewCs.begin());
1613	}
1614
1615	TEST(LazyCallGraphTest, InternalRefEdgeToCall) {
1616	LLVMContext Context;
1617	// Basic tests for making a ref edge a call. This hits the basics of the
1618	// process only.
1619	std::unique_ptr<Module> M =
1620	parseAssembly(Context, Assembly: "define void @a() {\n"
1621	"entry:\n"
1622	" call void @b()\n"
1623	" call void @c()\n"
1624	" store void()* @d, void()** undef\n"
1625	" ret void\n"
1626	"}\n"
1627	"define void @b() {\n"
1628	"entry:\n"
1629	" store void()* @c, void()** undef\n"
1630	" call void @d()\n"
1631	" ret void\n"
1632	"}\n"
1633	"define void @c() {\n"
1634	"entry:\n"
1635	" store void()* @b, void()** undef\n"
1636	" call void @d()\n"
1637	" ret void\n"
1638	"}\n"
1639	"define void @d() {\n"
1640	"entry:\n"
1641	" store void()* @a, void()** undef\n"
1642	" ret void\n"
1643	"}\n");
1644	LazyCallGraph CG = buildCG(M&: *M);
1645
1646	// Force the graph to be fully expanded.
1647	CG.buildRefSCCs();
1648	auto I = CG.postorder_ref_scc_begin();
1649	LazyCallGraph::RefSCC &RC = *I++;
1650	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1651
1652	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1653	LazyCallGraph::Node &B = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
1654	LazyCallGraph::Node &C = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
1655	LazyCallGraph::Node &D = *CG.lookup(F: lookupFunction(M&: *M, Name: "d"));
1656	LazyCallGraph::SCC &AC = *CG.lookupSCC(N&: A);
1657	LazyCallGraph::SCC &BC = *CG.lookupSCC(N&: B);
1658	LazyCallGraph::SCC &CC = *CG.lookupSCC(N&: C);
1659	LazyCallGraph::SCC &DC = *CG.lookupSCC(N&: D);
1660
1661	// Check the initial post-order. Note that B and C could be flipped here (and
1662	// in our mutation) without changing the nature of this test.
1663	ASSERT_EQ(4, RC.size());
1664	EXPECT_EQ(&DC, &RC[0]);
1665	EXPECT_EQ(&BC, &RC[1]);
1666	EXPECT_EQ(&CC, &RC[2]);
1667	EXPECT_EQ(&AC, &RC[3]);
1668
1669	// Switch the ref edge from A -> D to a call edge. This should have no
1670	// effect as it is already in postorder and no new cycles are formed.
1671	EXPECT_FALSE(RC.switchInternalEdgeToCall(A, D));
1672	ASSERT_EQ(4, RC.size());
1673	EXPECT_EQ(&DC, &RC[0]);
1674	EXPECT_EQ(&BC, &RC[1]);
1675	EXPECT_EQ(&CC, &RC[2]);
1676	EXPECT_EQ(&AC, &RC[3]);
1677
1678	// Switch B -> C to a call edge. This doesn't form any new cycles but does
1679	// require reordering the SCCs.
1680	EXPECT_FALSE(RC.switchInternalEdgeToCall(B, C));
1681	ASSERT_EQ(4, RC.size());
1682	EXPECT_EQ(&DC, &RC[0]);
1683	EXPECT_EQ(&CC, &RC[1]);
1684	EXPECT_EQ(&BC, &RC[2]);
1685	EXPECT_EQ(&AC, &RC[3]);
1686
1687	// Switch C -> B to a call edge. This forms a cycle and forces merging SCCs.
1688	EXPECT_TRUE(RC.switchInternalEdgeToCall(C, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1689	ASSERT_EQ(1u, MergedCs.size());
1690	EXPECT_EQ(&CC, MergedCs[0]);
1691	}));
1692	ASSERT_EQ(3, RC.size());
1693	EXPECT_EQ(&DC, &RC[0]);
1694	EXPECT_EQ(&BC, &RC[1]);
1695	EXPECT_EQ(&AC, &RC[2]);
1696	EXPECT_EQ(2, BC.size());
1697	EXPECT_EQ(&BC, CG.lookupSCC(B));
1698	EXPECT_EQ(&BC, CG.lookupSCC(C));
1699	}
1700
1701	TEST(LazyCallGraphTest, InternalRefEdgeToCallNoCycleInterleaved) {
1702	LLVMContext Context;
1703	// Test for having a post-order prior to changing a ref edge to a call edge
1704	// with SCCs connecting to the source and connecting to the target, but not
1705	// connecting to both, interleaved between the source and target. This
1706	// ensures we correctly partition the range rather than simply moving one or
1707	// the other.
1708	std::unique_ptr<Module> M =
1709	parseAssembly(Context, Assembly: "define void @a() {\n"
1710	"entry:\n"
1711	" call void @b1()\n"
1712	" call void @c1()\n"
1713	" ret void\n"
1714	"}\n"
1715	"define void @b1() {\n"
1716	"entry:\n"
1717	" call void @c1()\n"
1718	" call void @b2()\n"
1719	" ret void\n"
1720	"}\n"
1721	"define void @c1() {\n"
1722	"entry:\n"
1723	" call void @b2()\n"
1724	" call void @c2()\n"
1725	" ret void\n"
1726	"}\n"
1727	"define void @b2() {\n"
1728	"entry:\n"
1729	" call void @c2()\n"
1730	" call void @b3()\n"
1731	" ret void\n"
1732	"}\n"
1733	"define void @c2() {\n"
1734	"entry:\n"
1735	" call void @b3()\n"
1736	" call void @c3()\n"
1737	" ret void\n"
1738	"}\n"
1739	"define void @b3() {\n"
1740	"entry:\n"
1741	" call void @c3()\n"
1742	" call void @d()\n"
1743	" ret void\n"
1744	"}\n"
1745	"define void @c3() {\n"
1746	"entry:\n"
1747	" store void()* @b1, void()** undef\n"
1748	" call void @d()\n"
1749	" ret void\n"
1750	"}\n"
1751	"define void @d() {\n"
1752	"entry:\n"
1753	" store void()* @a, void()** undef\n"
1754	" ret void\n"
1755	"}\n");
1756	LazyCallGraph CG = buildCG(M&: *M);
1757
1758	// Force the graph to be fully expanded.
1759	CG.buildRefSCCs();
1760	auto I = CG.postorder_ref_scc_begin();
1761	LazyCallGraph::RefSCC &RC = *I++;
1762	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1763
1764	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1765	LazyCallGraph::Node &B1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b1"));
1766	LazyCallGraph::Node &B2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b2"));
1767	LazyCallGraph::Node &B3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "b3"));
1768	LazyCallGraph::Node &C1 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c1"));
1769	LazyCallGraph::Node &C2 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c2"));
1770	LazyCallGraph::Node &C3 = *CG.lookup(F: lookupFunction(M&: *M, Name: "c3"));
1771	LazyCallGraph::Node &D = *CG.lookup(F: lookupFunction(M&: *M, Name: "d"));
1772	LazyCallGraph::SCC &AC = *CG.lookupSCC(N&: A);
1773	LazyCallGraph::SCC &B1C = *CG.lookupSCC(N&: B1);
1774	LazyCallGraph::SCC &B2C = *CG.lookupSCC(N&: B2);
1775	LazyCallGraph::SCC &B3C = *CG.lookupSCC(N&: B3);
1776	LazyCallGraph::SCC &C1C = *CG.lookupSCC(N&: C1);
1777	LazyCallGraph::SCC &C2C = *CG.lookupSCC(N&: C2);
1778	LazyCallGraph::SCC &C3C = *CG.lookupSCC(N&: C3);
1779	LazyCallGraph::SCC &DC = *CG.lookupSCC(N&: D);
1780
1781	// Several call edges are initially present to force a particual post-order.
1782	// Remove them now, leaving an interleaved post-order pattern.
1783	RC.switchTrivialInternalEdgeToRef(SourceN&: B3, TargetN&: C3);
1784	RC.switchTrivialInternalEdgeToRef(SourceN&: C2, TargetN&: B3);
1785	RC.switchTrivialInternalEdgeToRef(SourceN&: B2, TargetN&: C2);
1786	RC.switchTrivialInternalEdgeToRef(SourceN&: C1, TargetN&: B2);
1787	RC.switchTrivialInternalEdgeToRef(SourceN&: B1, TargetN&: C1);
1788
1789	// Check the initial post-order. We ensure this order with the extra edges
1790	// that are nuked above.
1791	ASSERT_EQ(8, RC.size());
1792	EXPECT_EQ(&DC, &RC[0]);
1793	EXPECT_EQ(&C3C, &RC[1]);
1794	EXPECT_EQ(&B3C, &RC[2]);
1795	EXPECT_EQ(&C2C, &RC[3]);
1796	EXPECT_EQ(&B2C, &RC[4]);
1797	EXPECT_EQ(&C1C, &RC[5]);
1798	EXPECT_EQ(&B1C, &RC[6]);
1799	EXPECT_EQ(&AC, &RC[7]);
1800
1801	// Switch C3 -> B1 to a call edge. This doesn't form any new cycles but does
1802	// require reordering the SCCs in the face of tricky internal node
1803	// structures.
1804	EXPECT_FALSE(RC.switchInternalEdgeToCall(C3, B1));
1805	ASSERT_EQ(8, RC.size());
1806	EXPECT_EQ(&DC, &RC[0]);
1807	EXPECT_EQ(&B3C, &RC[1]);
1808	EXPECT_EQ(&B2C, &RC[2]);
1809	EXPECT_EQ(&B1C, &RC[3]);
1810	EXPECT_EQ(&C3C, &RC[4]);
1811	EXPECT_EQ(&C2C, &RC[5]);
1812	EXPECT_EQ(&C1C, &RC[6]);
1813	EXPECT_EQ(&AC, &RC[7]);
1814	}
1815
1816	TEST(LazyCallGraphTest, InternalRefEdgeToCallBothPartitionAndMerge) {
1817	LLVMContext Context;
1818	// Test for having a postorder where between the source and target are all
1819	// three kinds of other SCCs:
1820	// 1) One connected to the target only that have to be shifted below the
1821	// source.
1822	// 2) One connected to the source only that have to be shifted below the
1823	// target.
1824	// 3) One connected to both source and target that has to remain and get
1825	// merged away.
1826	//
1827	// To achieve this we construct a heavily connected graph to force
1828	// a particular post-order. Then we remove the forcing edges and connect
1829	// a cycle.
1830	//
1831	// Diagram for the graph we want on the left and the graph we use to force
1832	// the ordering on the right. Edges point down or right.
1833	//
1834	// A | A |
1835	// / \ | / \ |
1836	// B E | B \ |
1837	// |\ | | |\ | |
1838	// | D | | C-D-E |
1839	// | \| | | \| |
1840	// C F | \ F |
1841	// \ / | \ / |
1842	// G | G |
1843	//
1844	// And we form a cycle by connecting F to B.
1845	std::unique_ptr<Module> M =
1846	parseAssembly(Context, Assembly: "define void @a() {\n"
1847	"entry:\n"
1848	" call void @b()\n"
1849	" call void @e()\n"
1850	" ret void\n"
1851	"}\n"
1852	"define void @b() {\n"
1853	"entry:\n"
1854	" call void @c()\n"
1855	" call void @d()\n"
1856	" ret void\n"
1857	"}\n"
1858	"define void @c() {\n"
1859	"entry:\n"
1860	" call void @d()\n"
1861	" call void @g()\n"
1862	" ret void\n"
1863	"}\n"
1864	"define void @d() {\n"
1865	"entry:\n"
1866	" call void @e()\n"
1867	" call void @f()\n"
1868	" ret void\n"
1869	"}\n"
1870	"define void @e() {\n"
1871	"entry:\n"
1872	" call void @f()\n"
1873	" ret void\n"
1874	"}\n"
1875	"define void @f() {\n"
1876	"entry:\n"
1877	" store void()* @b, void()** undef\n"
1878	" call void @g()\n"
1879	" ret void\n"
1880	"}\n"
1881	"define void @g() {\n"
1882	"entry:\n"
1883	" store void()* @a, void()** undef\n"
1884	" ret void\n"
1885	"}\n");
1886	LazyCallGraph CG = buildCG(M&: *M);
1887
1888	// Force the graph to be fully expanded.
1889	CG.buildRefSCCs();
1890	auto I = CG.postorder_ref_scc_begin();
1891	LazyCallGraph::RefSCC &RC = *I++;
1892	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1893
1894	LazyCallGraph::Node &A = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
1895	LazyCallGraph::Node &B = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
1896	LazyCallGraph::Node &C = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
1897	LazyCallGraph::Node &D = *CG.lookup(F: lookupFunction(M&: *M, Name: "d"));
1898	LazyCallGraph::Node &E = *CG.lookup(F: lookupFunction(M&: *M, Name: "e"));
1899	LazyCallGraph::Node &F = *CG.lookup(F: lookupFunction(M&: *M, Name: "f"));
1900	LazyCallGraph::Node &G = *CG.lookup(F: lookupFunction(M&: *M, Name: "g"));
1901	LazyCallGraph::SCC &AC = *CG.lookupSCC(N&: A);
1902	LazyCallGraph::SCC &BC = *CG.lookupSCC(N&: B);
1903	LazyCallGraph::SCC &CC = *CG.lookupSCC(N&: C);
1904	LazyCallGraph::SCC &DC = *CG.lookupSCC(N&: D);
1905	LazyCallGraph::SCC &EC = *CG.lookupSCC(N&: E);
1906	LazyCallGraph::SCC &FC = *CG.lookupSCC(N&: F);
1907	LazyCallGraph::SCC &GC = *CG.lookupSCC(N&: G);
1908
1909	// Remove the extra edges that were used to force a particular post-order.
1910	RC.switchTrivialInternalEdgeToRef(SourceN&: C, TargetN&: D);
1911	RC.switchTrivialInternalEdgeToRef(SourceN&: D, TargetN&: E);
1912
1913	// Check the initial post-order. We ensure this order with the extra edges
1914	// that are nuked above.
1915	ASSERT_EQ(7, RC.size());
1916	EXPECT_EQ(&GC, &RC[0]);
1917	EXPECT_EQ(&FC, &RC[1]);
1918	EXPECT_EQ(&EC, &RC[2]);
1919	EXPECT_EQ(&DC, &RC[3]);
1920	EXPECT_EQ(&CC, &RC[4]);
1921	EXPECT_EQ(&BC, &RC[5]);
1922	EXPECT_EQ(&AC, &RC[6]);
1923
1924	// Switch F -> B to a call edge. This merges B, D, and F into a single SCC,
1925	// and has to place the C and E SCCs on either side of it:
1926	// A A |
1927	// / \ / \ |
1928	// B E | E |
1929	// |\ | \ / |
1930	// | D | -> B |
1931	// | \| / \ |
1932	// C F C | |
1933	// \ / \ / |
1934	// G G |
1935	EXPECT_TRUE(RC.switchInternalEdgeToCall(
1936	F, B, [&](ArrayRef<LazyCallGraph::SCC *> MergedCs) {
1937	ASSERT_EQ(2u, MergedCs.size());
1938	EXPECT_EQ(&FC, MergedCs[0]);
1939	EXPECT_EQ(&DC, MergedCs[1]);
1940	}));
1941	EXPECT_EQ(3, BC.size());
1942
1943	// And make sure the postorder was updated.
1944	ASSERT_EQ(5, RC.size());
1945	EXPECT_EQ(&GC, &RC[0]);
1946	EXPECT_EQ(&CC, &RC[1]);
1947	EXPECT_EQ(&BC, &RC[2]);
1948	EXPECT_EQ(&EC, &RC[3]);
1949	EXPECT_EQ(&AC, &RC[4]);
1950	}
1951
1952	// Test for IR containing constants using blockaddress constant expressions.
1953	// These are truly unique constructs: constant expressions with non-constant
1954	// operands.
1955	TEST(LazyCallGraphTest, HandleBlockAddress) {
1956	LLVMContext Context;
1957	std::unique_ptr<Module> M =
1958	parseAssembly(Context, Assembly: "define void @f() {\n"
1959	"entry:\n"
1960	" ret void\n"
1961	"bb:\n"
1962	" unreachable\n"
1963	"}\n"
1964	"define void @g(i8** %ptr) {\n"
1965	"entry:\n"
1966	" store i8* blockaddress(@f, %bb), i8** %ptr\n"
1967	" ret void\n"
1968	"}\n");
1969	LazyCallGraph CG = buildCG(M&: *M);
1970
1971	CG.buildRefSCCs();
1972	auto I = CG.postorder_ref_scc_begin();
1973	LazyCallGraph::RefSCC &FRC = *I++;
1974	LazyCallGraph::RefSCC &GRC = *I++;
1975	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
1976
1977	LazyCallGraph::Node &F = *CG.lookup(F: lookupFunction(M&: *M, Name: "f"));
1978	LazyCallGraph::Node &G = *CG.lookup(F: lookupFunction(M&: *M, Name: "g"));
1979	EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
1980	EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
1981	EXPECT_FALSE(GRC.isParentOf(FRC));
1982	EXPECT_FALSE(FRC.isParentOf(GRC));
1983	}
1984
1985	// Test that a blockaddress that refers to itself creates no new RefSCC
1986	// connections. https://bugs.llvm.org/show_bug.cgi?id=40722
1987	TEST(LazyCallGraphTest, HandleBlockAddress2) {
1988	LLVMContext Context;
1989	std::unique_ptr<Module> M =
1990	parseAssembly(Context, Assembly: "define void @f() {\n"
1991	" ret void\n"
1992	"}\n"
1993	"define void @g(i8** %ptr) {\n"
1994	"bb:\n"
1995	" store i8* blockaddress(@g, %bb), i8** %ptr\n"
1996	" ret void\n"
1997	"}\n");
1998	LazyCallGraph CG = buildCG(M&: *M);
1999
2000	CG.buildRefSCCs();
2001	auto I = CG.postorder_ref_scc_begin();
2002	LazyCallGraph::RefSCC &FRC = *I++;
2003	LazyCallGraph::RefSCC &GRC = *I++;
2004	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2005
2006	LazyCallGraph::Node &F = *CG.lookup(F: lookupFunction(M&: *M, Name: "f"));
2007	LazyCallGraph::Node &G = *CG.lookup(F: lookupFunction(M&: *M, Name: "g"));
2008	EXPECT_EQ(&FRC, CG.lookupRefSCC(F));
2009	EXPECT_EQ(&GRC, CG.lookupRefSCC(G));
2010	EXPECT_FALSE(GRC.isParentOf(FRC));
2011	EXPECT_FALSE(FRC.isParentOf(GRC));
2012	}
2013
2014	TEST(LazyCallGraphTest, ReplaceNodeFunction) {
2015	LLVMContext Context;
2016	// A graph with several different kinds of edges pointing at a particular
2017	// function.
2018	std::unique_ptr<Module> M =
2019	parseAssembly(Context,
2020	Assembly: "define void @a(i8** %ptr) {\n"
2021	"entry:\n"
2022	" store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2023	" ret void\n"
2024	"}\n"
2025	"define void @b(i8** %ptr) {\n"
2026	"entry:\n"
2027	" store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2028	" store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2029	" call void @d(i8** %ptr)"
2030	" ret void\n"
2031	"}\n"
2032	"define void @c(i8** %ptr) {\n"
2033	"entry:\n"
2034	" call void @d(i8** %ptr)"
2035	" call void @d(i8** %ptr)"
2036	" store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2037	" ret void\n"
2038	"}\n"
2039	"define void @d(i8** %ptr) {\n"
2040	"entry:\n"
2041	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
2042	" call void @c(i8** %ptr)"
2043	" call void @d(i8** %ptr)"
2044	" store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2045	" ret void\n"
2046	"}\n");
2047	LazyCallGraph CG = buildCG(M&: *M);
2048
2049	// Force the graph to be fully expanded.
2050	CG.buildRefSCCs();
2051	auto I = CG.postorder_ref_scc_begin();
2052	LazyCallGraph::RefSCC &RC1 = *I++;
2053	LazyCallGraph::RefSCC &RC2 = *I++;
2054	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2055
2056	ASSERT_EQ(2, RC1.size());
2057	LazyCallGraph::SCC &C1 = RC1[0];
2058	LazyCallGraph::SCC &C2 = RC1[1];
2059
2060	LazyCallGraph::Node &AN = *CG.lookup(F: lookupFunction(M&: *M, Name: "a"));
2061	LazyCallGraph::Node &BN = *CG.lookup(F: lookupFunction(M&: *M, Name: "b"));
2062	LazyCallGraph::Node &CN = *CG.lookup(F: lookupFunction(M&: *M, Name: "c"));
2063	LazyCallGraph::Node &DN = *CG.lookup(F: lookupFunction(M&: *M, Name: "d"));
2064	EXPECT_EQ(&C1, CG.lookupSCC(DN));
2065	EXPECT_EQ(&C1, CG.lookupSCC(CN));
2066	EXPECT_EQ(&C2, CG.lookupSCC(BN));
2067	EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
2068	EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
2069	EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
2070	EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
2071
2072	// Now we need to build a new function 'e' with the same signature as 'd'.
2073	Function &D = DN.getFunction();
2074	Function &E = *Function::Create(Ty: D.getFunctionType(), Linkage: D.getLinkage(), N: "e");
2075	D.getParent()->getFunctionList().insert(where: D.getIterator(), New: &E);
2076
2077	// Change each use of 'd' to use 'e'. This is particularly easy as they have
2078	// the same type.
2079	D.replaceAllUsesWith(V: &E);
2080
2081	// Splice the body of the old function into the new one.
2082	E.splice(ToIt: E.begin(), FromF: &D);
2083	// And fix up the one argument.
2084	D.arg_begin()->replaceAllUsesWith(V: &*E.arg_begin());
2085	E.arg_begin()->takeName(V: &*D.arg_begin());
2086
2087	// Now replace the function in the graph.
2088	RC1.replaceNodeFunction(N&: DN, NewF&: E);
2089
2090	EXPECT_EQ(&E, &DN.getFunction());
2091	EXPECT_EQ(&DN, &(*CN)[DN].getNode());
2092	EXPECT_EQ(&DN, &(*BN)[DN].getNode());
2093	}
2094
2095	TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRef) {
2096	LLVMContext Context;
2097	// A graph with a couple of RefSCCs.
2098	std::unique_ptr<Module> M =
2099	parseAssembly(Context,
2100	Assembly: "define void @a(i8** %ptr) {\n"
2101	"entry:\n"
2102	" store i8* bitcast (void(i8**)* @d to i8*), i8** %ptr\n"
2103	" ret void\n"
2104	"}\n"
2105	"define void @b(i8** %ptr) {\n"
2106	"entry:\n"
2107	" store i8* bitcast (void(i8**)* @c to i8*), i8** %ptr\n"
2108	" ret void\n"
2109	"}\n"
2110	"define void @c(i8** %ptr) {\n"
2111	"entry:\n"
2112	" call void @d(i8** %ptr)"
2113	" ret void\n"
2114	"}\n"
2115	"define void @d(i8** %ptr) {\n"
2116	"entry:\n"
2117	" call void @c(i8** %ptr)"
2118	" store i8* bitcast (void(i8**)* @b to i8*), i8** %ptr\n"
2119	" ret void\n"
2120	"}\n"
2121	"define void @dead() {\n"
2122	"entry:\n"
2123	" ret void\n"
2124	"}\n");
2125	LazyCallGraph CG = buildCG(M&: *M);
2126
2127	// Insert spurious ref edges.
2128	LazyCallGraph::Node &AN = CG.get(F&: lookupFunction(M&: *M, Name: "a"));
2129	LazyCallGraph::Node &BN = CG.get(F&: lookupFunction(M&: *M, Name: "b"));
2130	LazyCallGraph::Node &CN = CG.get(F&: lookupFunction(M&: *M, Name: "c"));
2131	LazyCallGraph::Node &DN = CG.get(F&: lookupFunction(M&: *M, Name: "d"));
2132	LazyCallGraph::Node &DeadN = CG.get(F&: lookupFunction(M&: *M, Name: "dead"));
2133	AN.populate();
2134	BN.populate();
2135	CN.populate();
2136	DN.populate();
2137	DeadN.populate();
2138	CG.insertEdge(SourceN&: AN, TargetN&: DeadN, EK: LazyCallGraph::Edge::Ref);
2139	CG.insertEdge(SourceN&: BN, TargetN&: DeadN, EK: LazyCallGraph::Edge::Ref);
2140	CG.insertEdge(SourceN&: CN, TargetN&: DeadN, EK: LazyCallGraph::Edge::Ref);
2141	CG.insertEdge(SourceN&: DN, TargetN&: DeadN, EK: LazyCallGraph::Edge::Ref);
2142
2143	// Force the graph to be fully expanded.
2144	CG.buildRefSCCs();
2145	auto I = CG.postorder_ref_scc_begin();
2146	LazyCallGraph::RefSCC &DeadRC = *I++;
2147	LazyCallGraph::RefSCC &RC1 = *I++;
2148	LazyCallGraph::RefSCC &RC2 = *I++;
2149	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2150
2151	ASSERT_EQ(2, RC1.size());
2152	LazyCallGraph::SCC &C1 = RC1[0];
2153	LazyCallGraph::SCC &C2 = RC1[1];
2154
2155	EXPECT_EQ(&DeadRC, CG.lookupRefSCC(DeadN));
2156	EXPECT_EQ(&C1, CG.lookupSCC(DN));
2157	EXPECT_EQ(&C1, CG.lookupSCC(CN));
2158	EXPECT_EQ(&C2, CG.lookupSCC(BN));
2159	EXPECT_EQ(&RC1, CG.lookupRefSCC(DN));
2160	EXPECT_EQ(&RC1, CG.lookupRefSCC(CN));
2161	EXPECT_EQ(&RC1, CG.lookupRefSCC(BN));
2162	EXPECT_EQ(&RC2, CG.lookupRefSCC(AN));
2163
2164	// Now delete 'dead'. There are no uses of this function but there are
2165	// spurious references.
2166	CG.removeDeadFunction(F&: DeadN.getFunction());
2167
2168	// The only observable change should be that the RefSCC is gone from the
2169	// postorder sequence.
2170	I = CG.postorder_ref_scc_begin();
2171	EXPECT_EQ(&RC1, &*I++);
2172	EXPECT_EQ(&RC2, &*I++);
2173	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2174	}
2175
2176	TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive) {
2177	LLVMContext Context;
2178	std::unique_ptr<Module> M =
2179	parseAssembly(Context, Assembly: "define void @a(ptr %p) {\n"
2180	" store ptr @b, ptr %p\n"
2181	" ret void\n"
2182	"}\n"
2183	"define void @b(ptr %p) {\n"
2184	" store ptr @c, ptr %p\n"
2185	" ret void\n"
2186	"}\n"
2187	"define void @c(ptr %p) {\n"
2188	" ret void\n"
2189	"}\n");
2190	LazyCallGraph CG = buildCG(M&: *M);
2191
2192	LazyCallGraph::Node &AN = CG.get(F&: lookupFunction(M&: *M, Name: "a"));
2193	LazyCallGraph::Node &BN = CG.get(F&: lookupFunction(M&: *M, Name: "b"));
2194	LazyCallGraph::Node &CN = CG.get(F&: lookupFunction(M&: *M, Name: "c"));
2195	AN.populate();
2196	BN.populate();
2197	CN.populate();
2198	// Insert spurious ref edge.
2199	CG.insertEdge(SourceN&: CN, TargetN&: AN, EK: LazyCallGraph::Edge::Ref);
2200
2201	// Force the graph to be fully expanded.
2202	CG.buildRefSCCs();
2203	auto I = CG.postorder_ref_scc_begin();
2204	LazyCallGraph::RefSCC &RC = *I++;
2205	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2206
2207	ASSERT_EQ(RC.size(), 3);
2208
2209	EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2210	EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2211	EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2212
2213	// Now delete 'a'. There are no uses of this function but there are
2214	// spurious references.
2215	CG.removeDeadFunction(F&: AN.getFunction());
2216
2217	// The only observable change should be that the RefSCC is gone from the
2218	// postorder sequence.
2219	I = CG.postorder_ref_scc_begin();
2220	EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);
2221	EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2222	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2223	}
2224
2225	TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive2) {
2226	LLVMContext Context;
2227	std::unique_ptr<Module> M =
2228	parseAssembly(Context, Assembly: "define void @a(ptr %p) {\n"
2229	" store ptr @b, ptr %p\n"
2230	" ret void\n"
2231	"}\n"
2232	"define void @b(ptr %p) {\n"
2233	" store ptr @c, ptr %p\n"
2234	" ret void\n"
2235	"}\n"
2236	"define void @c(ptr %p) {\n"
2237	" store ptr @b, ptr %p\n"
2238	" store ptr @d, ptr %p\n"
2239	" ret void\n"
2240	"}\n"
2241	"define void @d(ptr %p) {\n"
2242	" ret void\n"
2243	"}\n");
2244	LazyCallGraph CG = buildCG(M&: *M);
2245
2246	LazyCallGraph::Node &AN = CG.get(F&: lookupFunction(M&: *M, Name: "a"));
2247	LazyCallGraph::Node &BN = CG.get(F&: lookupFunction(M&: *M, Name: "b"));
2248	LazyCallGraph::Node &CN = CG.get(F&: lookupFunction(M&: *M, Name: "c"));
2249	LazyCallGraph::Node &DN = CG.get(F&: lookupFunction(M&: *M, Name: "d"));
2250	AN.populate();
2251	BN.populate();
2252	CN.populate();
2253	DN.populate();
2254	// Insert spurious ref edge.
2255	CG.insertEdge(SourceN&: DN, TargetN&: AN, EK: LazyCallGraph::Edge::Ref);
2256
2257	// Force the graph to be fully expanded.
2258	CG.buildRefSCCs();
2259	auto I = CG.postorder_ref_scc_begin();
2260	LazyCallGraph::RefSCC &RC = *I++;
2261	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2262
2263	ASSERT_EQ(4, RC.size());
2264
2265	EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2266	EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2267	EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2268	EXPECT_EQ(&RC, CG.lookupRefSCC(DN));
2269
2270	// Now delete 'a'. There are no uses of this function but there are
2271	// spurious references.
2272	CG.removeDeadFunction(F&: AN.getFunction());
2273
2274	// The only observable change should be that the RefSCC is gone from the
2275	// postorder sequence.
2276	I = CG.postorder_ref_scc_begin();
2277	EXPECT_EQ(CG.lookupRefSCC(DN), &*I++);
2278	EXPECT_EQ(CG.lookupRefSCC(CN), &*I);
2279	EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2280	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2281	}
2282
2283	TEST(LazyCallGraphTest, RemoveFunctionWithSpuriousRefRecursive3) {
2284	LLVMContext Context;
2285	std::unique_ptr<Module> M =
2286	parseAssembly(Context, Assembly: "define void @a(ptr %p) {\n"
2287	" store ptr @b, ptr %p\n"
2288	" ret void\n"
2289	"}\n"
2290	"define void @b(ptr %p) {\n"
2291	" store ptr @c, ptr %p\n"
2292	" ret void\n"
2293	"}\n"
2294	"define void @c(ptr %p) {\n"
2295	" ret void\n"
2296	"}\n");
2297	LazyCallGraph CG = buildCG(M&: *M);
2298
2299	LazyCallGraph::Node &AN = CG.get(F&: lookupFunction(M&: *M, Name: "a"));
2300	LazyCallGraph::Node &BN = CG.get(F&: lookupFunction(M&: *M, Name: "b"));
2301	LazyCallGraph::Node &CN = CG.get(F&: lookupFunction(M&: *M, Name: "c"));
2302	AN.populate();
2303	BN.populate();
2304	CN.populate();
2305	// Insert spurious ref edges.
2306	CG.insertEdge(SourceN&: CN, TargetN&: AN, EK: LazyCallGraph::Edge::Ref);
2307	CG.insertEdge(SourceN&: BN, TargetN&: AN, EK: LazyCallGraph::Edge::Ref);
2308
2309	// Force the graph to be fully expanded.
2310	CG.buildRefSCCs();
2311	auto I = CG.postorder_ref_scc_begin();
2312	LazyCallGraph::RefSCC &RC = *I++;
2313	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2314
2315	ASSERT_EQ(RC.size(), 3);
2316
2317	EXPECT_EQ(&RC, CG.lookupRefSCC(AN));
2318	EXPECT_EQ(&RC, CG.lookupRefSCC(BN));
2319	EXPECT_EQ(&RC, CG.lookupRefSCC(CN));
2320
2321	// Now delete 'a'. There are no uses of this function but there are
2322	// spurious references.
2323	CG.removeDeadFunction(F&: AN.getFunction());
2324
2325	// The only observable change should be that the RefSCC is gone from the
2326	// postorder sequence.
2327	I = CG.postorder_ref_scc_begin();
2328	EXPECT_EQ(CG.lookupRefSCC(CN), &*I++);
2329	EXPECT_EQ(CG.lookupRefSCC(BN), &*I++);
2330	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2331	}
2332
2333	TEST(LazyCallGraphTest, AddSplitFunction1) {
2334	LLVMContext Context;
2335	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2336	" ret void\n"
2337	"}\n");
2338	LazyCallGraph CG = buildCG(M&: *M);
2339
2340	Function &F = lookupFunction(M&: *M, Name: "f");
2341	LazyCallGraph::Node &FN = CG.get(F);
2342
2343	// Force the graph to be fully expanded.
2344	CG.buildRefSCCs();
2345	auto I = CG.postorder_ref_scc_begin();
2346	LazyCallGraph::RefSCC *ORC = &*I++;
2347	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2348
2349	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2350	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2351	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2352	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2353
2354	// Create f -call-> g.
2355	(void)CallInst::Create(Func: G, Args: {}, NameStr: "", InsertBefore: &*F.getEntryBlock().begin());
2356
2357	EXPECT_FALSE(verifyModule(*M, &errs()));
2358
2359	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2360
2361	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2362	EXPECT_TRUE(GN);
2363
2364	I = CG.postorder_ref_scc_begin();
2365	LazyCallGraph::RefSCC *RC1 = &*I++;
2366	EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2367	LazyCallGraph::RefSCC *RC2 = &*I++;
2368	EXPECT_EQ(RC2, ORC);
2369	EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2370	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2371	}
2372
2373	TEST(LazyCallGraphTest, AddSplitFunction2) {
2374	LLVMContext Context;
2375	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2376	" ret void\n"
2377	"}\n");
2378	LazyCallGraph CG = buildCG(M&: *M);
2379
2380	Function &F = lookupFunction(M&: *M, Name: "f");
2381	LazyCallGraph::Node &FN = CG.get(F);
2382
2383	// Force the graph to be fully expanded.
2384	CG.buildRefSCCs();
2385	auto I = CG.postorder_ref_scc_begin();
2386	LazyCallGraph::RefSCC *ORC = &*I++;
2387	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2388
2389	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2390	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2391	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2392	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2393
2394	// Create f -ref-> g.
2395	(void)CastInst::CreatePointerCast(S: G, Ty: PointerType::getUnqual(C&: Context), Name: "",
2396	InsertBefore: &*F.getEntryBlock().begin());
2397
2398	EXPECT_FALSE(verifyModule(*M, &errs()));
2399
2400	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2401
2402	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2403	EXPECT_TRUE(GN);
2404
2405	I = CG.postorder_ref_scc_begin();
2406	LazyCallGraph::RefSCC *RC1 = &*I++;
2407	EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2408	LazyCallGraph::RefSCC *RC2 = &*I++;
2409	EXPECT_EQ(RC2, ORC);
2410	EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2411	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2412	}
2413
2414	TEST(LazyCallGraphTest, AddSplitFunction3) {
2415	LLVMContext Context;
2416	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2417	" ret void\n"
2418	"}\n");
2419	LazyCallGraph CG = buildCG(M&: *M);
2420
2421	Function &F = lookupFunction(M&: *M, Name: "f");
2422	LazyCallGraph::Node &FN = CG.get(F);
2423
2424	// Force the graph to be fully expanded.
2425	CG.buildRefSCCs();
2426	auto I = CG.postorder_ref_scc_begin();
2427	LazyCallGraph::RefSCC *ORC = &*I++;
2428	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2429
2430	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2431	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2432	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2433	// Create g -ref-> f.
2434	(void)CastInst::CreatePointerCast(S: &F, Ty: PointerType::getUnqual(C&: Context), Name: "",
2435	InsertAtEnd: GBB);
2436	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2437
2438	// Create f -call-> g.
2439	(void)CallInst::Create(Func: G, Args: {}, NameStr: "", InsertBefore: &*F.getEntryBlock().begin());
2440
2441	EXPECT_FALSE(verifyModule(*M, &errs()));
2442
2443	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2444
2445	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2446	EXPECT_TRUE(GN);
2447
2448	I = CG.postorder_ref_scc_begin();
2449	LazyCallGraph::RefSCC *RC = &*I++;
2450	EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2451	EXPECT_EQ(RC, ORC);
2452	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2453
2454	EXPECT_EQ(2, RC->size());
2455	EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2456	EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]);
2457	}
2458
2459	TEST(LazyCallGraphTest, AddSplitFunction4) {
2460	LLVMContext Context;
2461	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2462	" ret void\n"
2463	"}\n");
2464	LazyCallGraph CG = buildCG(M&: *M);
2465
2466	Function &F = lookupFunction(M&: *M, Name: "f");
2467	LazyCallGraph::Node &FN = CG.get(F);
2468
2469	// Force the graph to be fully expanded.
2470	CG.buildRefSCCs();
2471	auto I = CG.postorder_ref_scc_begin();
2472	LazyCallGraph::RefSCC *ORC = &*I++;
2473	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2474
2475	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2476	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2477	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2478	// Create g -ref-> f.
2479	(void)CastInst::CreatePointerCast(S: &F, Ty: PointerType::getUnqual(C&: Context), Name: "",
2480	InsertAtEnd: GBB);
2481	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2482
2483	// Create f -ref-> g.
2484	(void)CastInst::CreatePointerCast(S: G, Ty: PointerType::getUnqual(C&: Context), Name: "",
2485	InsertBefore: &*F.getEntryBlock().begin());
2486
2487	EXPECT_FALSE(verifyModule(*M, &errs()));
2488
2489	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2490
2491	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2492	EXPECT_TRUE(GN);
2493
2494	I = CG.postorder_ref_scc_begin();
2495	LazyCallGraph::RefSCC *RC = &*I++;
2496	EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2497	EXPECT_EQ(RC, ORC);
2498	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2499
2500	// Order doesn't matter for sibling SCCs.
2501	EXPECT_EQ(2, RC->size());
2502	EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC);
2503	EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2504	}
2505
2506	TEST(LazyCallGraphTest, AddSplitFunction5) {
2507	LLVMContext Context;
2508	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2509	" ret void\n"
2510	"}\n");
2511	LazyCallGraph CG = buildCG(M&: *M);
2512
2513	Function &F = lookupFunction(M&: *M, Name: "f");
2514	LazyCallGraph::Node &FN = CG.get(F);
2515
2516	// Force the graph to be fully expanded.
2517	CG.buildRefSCCs();
2518	auto I = CG.postorder_ref_scc_begin();
2519	LazyCallGraph::RefSCC *ORC = &*I++;
2520	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2521
2522	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2523	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2524	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2525	// Create g -call-> f.
2526	(void)CallInst::Create(Func: &F, Args: {}, NameStr: "", InsertAtEnd: GBB);
2527	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2528
2529	// Create f -ref-> g.
2530	(void)CastInst::CreatePointerCast(S: G, Ty: PointerType::getUnqual(C&: Context), Name: "",
2531	InsertBefore: &*F.getEntryBlock().begin());
2532
2533	EXPECT_FALSE(verifyModule(*M, &errs()));
2534
2535	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2536
2537	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2538	EXPECT_TRUE(GN);
2539
2540	I = CG.postorder_ref_scc_begin();
2541	LazyCallGraph::RefSCC *RC = &*I++;
2542	EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2543	EXPECT_EQ(RC, ORC);
2544	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2545
2546	EXPECT_EQ(2, RC->size());
2547	EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2548	EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]);
2549	}
2550
2551	TEST(LazyCallGraphTest, AddSplitFunction6) {
2552	LLVMContext Context;
2553	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2554	" ret void\n"
2555	"}\n");
2556	LazyCallGraph CG = buildCG(M&: *M);
2557
2558	Function &F = lookupFunction(M&: *M, Name: "f");
2559	LazyCallGraph::Node &FN = CG.get(F);
2560
2561	// Force the graph to be fully expanded.
2562	CG.buildRefSCCs();
2563	auto I = CG.postorder_ref_scc_begin();
2564	LazyCallGraph::RefSCC *ORC = &*I++;
2565	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2566
2567	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2568	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2569	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2570	// Create g -call-> f.
2571	(void)CallInst::Create(Func: &F, Args: {}, NameStr: "", InsertAtEnd: GBB);
2572	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2573
2574	// Create f -call-> g.
2575	(void)CallInst::Create(Func: G, Args: {}, NameStr: "", InsertBefore: &*F.getEntryBlock().begin());
2576
2577	EXPECT_FALSE(verifyModule(*M, &errs()));
2578
2579	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2580
2581	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2582	EXPECT_TRUE(GN);
2583
2584	I = CG.postorder_ref_scc_begin();
2585	LazyCallGraph::RefSCC *RC = &*I++;
2586	EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2587	EXPECT_EQ(RC, ORC);
2588	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2589
2590	EXPECT_EQ(1, RC->size());
2591	EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2592	EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2593	}
2594
2595	TEST(LazyCallGraphTest, AddSplitFunction7) {
2596	LLVMContext Context;
2597	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2598	" call void @f2()\n"
2599	" ret void\n"
2600	"}\n"
2601	"define void @f2() {\n"
2602	" call void @f()\n"
2603	" ret void\n"
2604	"}\n");
2605	LazyCallGraph CG = buildCG(M&: *M);
2606
2607	Function &F = lookupFunction(M&: *M, Name: "f");
2608	LazyCallGraph::Node &FN = CG.get(F);
2609	Function &F2 = lookupFunction(M&: *M, Name: "f2");
2610	LazyCallGraph::Node &F2N = CG.get(F&: F2);
2611
2612	// Force the graph to be fully expanded.
2613	CG.buildRefSCCs();
2614	auto I = CG.postorder_ref_scc_begin();
2615	LazyCallGraph::RefSCC *ORC = &*I++;
2616	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2617
2618	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2619	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2620	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2621	// Create g -call-> f2.
2622	(void)CallInst::Create(Func: &F2, Args: {}, NameStr: "", InsertAtEnd: GBB);
2623	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2624
2625	// Create f -call-> g.
2626	(void)CallInst::Create(Func: G, Args: {}, NameStr: "", InsertBefore: &*F.getEntryBlock().begin());
2627
2628	EXPECT_FALSE(verifyModule(*M, &errs()));
2629
2630	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2631
2632	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2633	EXPECT_TRUE(GN);
2634
2635	I = CG.postorder_ref_scc_begin();
2636	LazyCallGraph::RefSCC *RC = &*I++;
2637	EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2638	EXPECT_EQ(RC, ORC);
2639	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2640
2641	EXPECT_EQ(1, RC->size());
2642	EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2643	EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]);
2644	EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2645	}
2646
2647	TEST(LazyCallGraphTest, AddSplitFunction8) {
2648	LLVMContext Context;
2649	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2650	" call void @f2()\n"
2651	" ret void\n"
2652	"}\n"
2653	"define void @f2() {\n"
2654	" call void @f()\n"
2655	" ret void\n"
2656	"}\n");
2657	LazyCallGraph CG = buildCG(M&: *M);
2658
2659	Function &F = lookupFunction(M&: *M, Name: "f");
2660	LazyCallGraph::Node &FN = CG.get(F);
2661	Function &F2 = lookupFunction(M&: *M, Name: "f2");
2662	LazyCallGraph::Node &F2N = CG.get(F&: F2);
2663
2664	// Force the graph to be fully expanded.
2665	CG.buildRefSCCs();
2666	auto I = CG.postorder_ref_scc_begin();
2667	LazyCallGraph::RefSCC *ORC = &*I++;
2668	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2669
2670	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2671	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2672	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2673	// Create g -call-> f2.
2674	(void)CallInst::Create(Func: &F2, Args: {}, NameStr: "", InsertAtEnd: GBB);
2675	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2676
2677	// Create f -ref-> g.
2678	(void)CastInst::CreatePointerCast(S: G, Ty: PointerType::getUnqual(C&: Context), Name: "",
2679	InsertBefore: &*F.getEntryBlock().begin());
2680
2681	EXPECT_FALSE(verifyModule(*M, &errs()));
2682
2683	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2684
2685	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2686	EXPECT_TRUE(GN);
2687
2688	I = CG.postorder_ref_scc_begin();
2689	LazyCallGraph::RefSCC *RC = &*I++;
2690	EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2691	EXPECT_EQ(RC, ORC);
2692	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2693
2694	EXPECT_EQ(2, RC->size());
2695	EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[0]);
2696	EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[0]);
2697	EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[1]);
2698	}
2699
2700	TEST(LazyCallGraphTest, AddSplitFunction9) {
2701	LLVMContext Context;
2702	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2703	" call void @f2()\n"
2704	" ret void\n"
2705	"}\n"
2706	"define void @f2() {\n"
2707	" call void @f()\n"
2708	" ret void\n"
2709	"}\n");
2710	LazyCallGraph CG = buildCG(M&: *M);
2711
2712	Function &F = lookupFunction(M&: *M, Name: "f");
2713	LazyCallGraph::Node &FN = CG.get(F);
2714	Function &F2 = lookupFunction(M&: *M, Name: "f2");
2715	LazyCallGraph::Node &F2N = CG.get(F&: F2);
2716
2717	// Force the graph to be fully expanded.
2718	CG.buildRefSCCs();
2719	auto I = CG.postorder_ref_scc_begin();
2720	LazyCallGraph::RefSCC *ORC = &*I++;
2721	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2722
2723	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2724	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2725	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2726	// Create g -ref-> f2.
2727	(void)CastInst::CreatePointerCast(S: &F2, Ty: PointerType::getUnqual(C&: Context), Name: "",
2728	InsertAtEnd: GBB);
2729	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2730
2731	// Create f -call-> g.
2732	(void)CallInst::Create(Func: G, Args: {}, NameStr: "", InsertBefore: &*F.getEntryBlock().begin());
2733
2734	EXPECT_FALSE(verifyModule(*M, &errs()));
2735
2736	CG.addSplitFunction(OriginalFunction&: F, NewFunction&: *G);
2737
2738	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2739	EXPECT_TRUE(GN);
2740
2741	I = CG.postorder_ref_scc_begin();
2742	LazyCallGraph::RefSCC *RC = &*I++;
2743	EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2744	EXPECT_EQ(RC, ORC);
2745	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2746
2747	EXPECT_EQ(2, RC->size());
2748	EXPECT_EQ(CG.lookupSCC(*GN), &(*RC)[0]);
2749	EXPECT_EQ(CG.lookupSCC(FN), &(*RC)[1]);
2750	EXPECT_EQ(CG.lookupSCC(F2N), &(*RC)[1]);
2751	}
2752
2753	TEST(LazyCallGraphTest, AddSplitFunctions1) {
2754	LLVMContext Context;
2755	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2756	" ret void\n"
2757	"}\n");
2758	LazyCallGraph CG = buildCG(M&: *M);
2759
2760	Function &F = lookupFunction(M&: *M, Name: "f");
2761	LazyCallGraph::Node &FN = CG.get(F);
2762
2763	// Force the graph to be fully expanded.
2764	CG.buildRefSCCs();
2765	auto I = CG.postorder_ref_scc_begin();
2766	LazyCallGraph::RefSCC *ORC = &*I++;
2767	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2768
2769	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2770	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2771	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2772	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2773
2774	// Create f -ref-> g.
2775	(void)CastInst::CreatePointerCast(S: G, Ty: PointerType::getUnqual(C&: Context), Name: "",
2776	InsertBefore: &*F.getEntryBlock().begin());
2777
2778	EXPECT_FALSE(verifyModule(*M, &errs()));
2779
2780	CG.addSplitRefRecursiveFunctions(OriginalFunction&: F, NewFunctions: SmallVector<Function *, 1>({G}));
2781
2782	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2783	EXPECT_TRUE(GN);
2784
2785	I = CG.postorder_ref_scc_begin();
2786	LazyCallGraph::RefSCC *RC1 = &*I++;
2787	EXPECT_EQ(RC1, CG.lookupRefSCC(*GN));
2788	LazyCallGraph::RefSCC *RC2 = &*I++;
2789	EXPECT_EQ(RC2, ORC);
2790	EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2791	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2792	}
2793
2794	TEST(LazyCallGraphTest, AddSplitFunctions2) {
2795	LLVMContext Context;
2796	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2797	" ret void\n"
2798	"}\n");
2799	LazyCallGraph CG = buildCG(M&: *M);
2800
2801	Function &F = lookupFunction(M&: *M, Name: "f");
2802	LazyCallGraph::Node &FN = CG.get(F);
2803
2804	// Force the graph to be fully expanded.
2805	CG.buildRefSCCs();
2806	auto I = CG.postorder_ref_scc_begin();
2807	LazyCallGraph::RefSCC *ORC = &*I++;
2808	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2809
2810	auto *G = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2811	AddrSpace: F.getAddressSpace(), N: "g", M: F.getParent());
2812	BasicBlock *GBB = BasicBlock::Create(Context, Name: "", Parent: G);
2813	// Create g -ref-> f.
2814	(void)CastInst::CreatePointerCast(S: &F, Ty: PointerType::getUnqual(C&: Context), Name: "",
2815	InsertAtEnd: GBB);
2816	(void)ReturnInst::Create(C&: Context, InsertAtEnd: GBB);
2817
2818	// Create f -ref-> g.
2819	(void)CastInst::CreatePointerCast(S: G, Ty: PointerType::getUnqual(C&: Context), Name: "",
2820	InsertBefore: &*F.getEntryBlock().begin());
2821
2822	EXPECT_FALSE(verifyModule(*M, &errs()));
2823
2824	CG.addSplitRefRecursiveFunctions(OriginalFunction&: F, NewFunctions: SmallVector<Function *, 1>({G}));
2825
2826	LazyCallGraph::Node *GN = CG.lookup(F: *G);
2827	EXPECT_TRUE(GN);
2828
2829	I = CG.postorder_ref_scc_begin();
2830	LazyCallGraph::RefSCC *RC = &*I++;
2831	EXPECT_EQ(RC, CG.lookupRefSCC(*GN));
2832	EXPECT_EQ(RC, ORC);
2833	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2834
2835	// Order doesn't matter for sibling SCCs.
2836	EXPECT_EQ(2, RC->size());
2837	EXPECT_EQ(&CG.lookupSCC(*GN)->getOuterRefSCC(), RC);
2838	EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2839	}
2840
2841	TEST(LazyCallGraphTest, AddSplitFunctions3) {
2842	LLVMContext Context;
2843	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2844	" ret void\n"
2845	"}\n");
2846	LazyCallGraph CG = buildCG(M&: *M);
2847
2848	Function &F = lookupFunction(M&: *M, Name: "f");
2849	LazyCallGraph::Node &FN = CG.get(F);
2850
2851	// Force the graph to be fully expanded.
2852	CG.buildRefSCCs();
2853	auto I = CG.postorder_ref_scc_begin();
2854	LazyCallGraph::RefSCC *ORC = &*I++;
2855	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2856
2857	auto *G1 = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2858	AddrSpace: F.getAddressSpace(), N: "g1", M: F.getParent());
2859	auto *G2 = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2860	AddrSpace: F.getAddressSpace(), N: "g2", M: F.getParent());
2861	BasicBlock *G1BB = BasicBlock::Create(Context, Name: "", Parent: G1);
2862	BasicBlock *G2BB = BasicBlock::Create(Context, Name: "", Parent: G2);
2863	// Create g1 -ref-> g2 and g2 -ref-> g1.
2864	(void)CastInst::CreatePointerCast(S: G2, Ty: PointerType::getUnqual(C&: Context), Name: "",
2865	InsertAtEnd: G1BB);
2866	(void)CastInst::CreatePointerCast(S: G1, Ty: PointerType::getUnqual(C&: Context), Name: "",
2867	InsertAtEnd: G2BB);
2868	(void)ReturnInst::Create(C&: Context, InsertAtEnd: G1BB);
2869	(void)ReturnInst::Create(C&: Context, InsertAtEnd: G2BB);
2870
2871	// Create f -ref-> g1 and f -ref-> g2.
2872	(void)CastInst::CreatePointerCast(S: G1, Ty: PointerType::getUnqual(C&: Context), Name: "",
2873	InsertBefore: &*F.getEntryBlock().begin());
2874	(void)CastInst::CreatePointerCast(S: G2, Ty: PointerType::getUnqual(C&: Context), Name: "",
2875	InsertBefore: &*F.getEntryBlock().begin());
2876
2877	EXPECT_FALSE(verifyModule(*M, &errs()));
2878
2879	CG.addSplitRefRecursiveFunctions(OriginalFunction&: F, NewFunctions: SmallVector<Function *, 1>({G1, G2}));
2880
2881	LazyCallGraph::Node *G1N = CG.lookup(F: *G1);
2882	EXPECT_TRUE(G1N);
2883	LazyCallGraph::Node *G2N = CG.lookup(F: *G2);
2884	EXPECT_TRUE(G2N);
2885
2886	I = CG.postorder_ref_scc_begin();
2887	LazyCallGraph::RefSCC *RC1 = &*I++;
2888	EXPECT_EQ(2, RC1->size());
2889	EXPECT_EQ(RC1, CG.lookupRefSCC(*G1N));
2890	EXPECT_EQ(RC1, CG.lookupRefSCC(*G2N));
2891	LazyCallGraph::RefSCC *RC2 = &*I++;
2892	EXPECT_EQ(RC2, ORC);
2893	EXPECT_EQ(RC2, CG.lookupRefSCC(FN));
2894	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2895	}
2896
2897	TEST(LazyCallGraphTest, AddSplitFunctions4) {
2898	LLVMContext Context;
2899	std::unique_ptr<Module> M = parseAssembly(Context, Assembly: "define void @f() {\n"
2900	" ret void\n"
2901	"}\n");
2902	LazyCallGraph CG = buildCG(M&: *M);
2903
2904	Function &F = lookupFunction(M&: *M, Name: "f");
2905	LazyCallGraph::Node &FN = CG.get(F);
2906
2907	// Force the graph to be fully expanded.
2908	CG.buildRefSCCs();
2909	auto I = CG.postorder_ref_scc_begin();
2910	LazyCallGraph::RefSCC *ORC = &*I++;
2911	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2912
2913	auto *G1 = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2914	AddrSpace: F.getAddressSpace(), N: "g1", M: F.getParent());
2915	auto *G2 = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2916	AddrSpace: F.getAddressSpace(), N: "g2", M: F.getParent());
2917	BasicBlock *G1BB = BasicBlock::Create(Context, Name: "", Parent: G1);
2918	BasicBlock *G2BB = BasicBlock::Create(Context, Name: "", Parent: G2);
2919	// Create g1 -ref-> g2 and g2 -ref-> g1.
2920	(void)CastInst::CreatePointerCast(S: G2, Ty: PointerType::getUnqual(C&: Context), Name: "",
2921	InsertAtEnd: G1BB);
2922	(void)CastInst::CreatePointerCast(S: G1, Ty: PointerType::getUnqual(C&: Context), Name: "",
2923	InsertAtEnd: G2BB);
2924	// Create g2 -ref-> f.
2925	(void)CastInst::CreatePointerCast(S: &F, Ty: PointerType::getUnqual(C&: Context), Name: "",
2926	InsertAtEnd: G2BB);
2927	(void)ReturnInst::Create(C&: Context, InsertAtEnd: G1BB);
2928	(void)ReturnInst::Create(C&: Context, InsertAtEnd: G2BB);
2929
2930	// Create f -ref-> g1 and f -ref-> g2.
2931	(void)CastInst::CreatePointerCast(S: G1, Ty: PointerType::getUnqual(C&: Context), Name: "",
2932	InsertBefore: &*F.getEntryBlock().begin());
2933	(void)CastInst::CreatePointerCast(S: G2, Ty: PointerType::getUnqual(C&: Context), Name: "",
2934	InsertBefore: &*F.getEntryBlock().begin());
2935
2936	EXPECT_FALSE(verifyModule(*M, &errs()));
2937
2938	CG.addSplitRefRecursiveFunctions(OriginalFunction&: F, NewFunctions: SmallVector<Function *, 1>({G1, G2}));
2939
2940	LazyCallGraph::Node *G1N = CG.lookup(F: *G1);
2941	EXPECT_TRUE(G1N);
2942	LazyCallGraph::Node *G2N = CG.lookup(F: *G2);
2943	EXPECT_TRUE(G2N);
2944
2945	I = CG.postorder_ref_scc_begin();
2946	LazyCallGraph::RefSCC *RC = &*I++;
2947	EXPECT_EQ(RC, ORC);
2948	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2949
2950	// Order doesn't matter for sibling SCCs.
2951	EXPECT_EQ(3, RC->size());
2952	EXPECT_EQ(&CG.lookupSCC(FN)->getOuterRefSCC(), RC);
2953	EXPECT_EQ(&CG.lookupSCC(*G1N)->getOuterRefSCC(), RC);
2954	EXPECT_EQ(&CG.lookupSCC(*G2N)->getOuterRefSCC(), RC);
2955	EXPECT_EQ(RC, CG.lookupRefSCC(*G1N));
2956	EXPECT_EQ(RC, CG.lookupRefSCC(*G2N));
2957	}
2958
2959	TEST(LazyCallGraphTest, AddSplitFunctions5) {
2960	LLVMContext Context;
2961	std::unique_ptr<Module> M =
2962	parseAssembly(Context, Assembly: "define void @f() {\n"
2963	" %1 = bitcast void ()* @f2 to i8*\n"
2964	" ret void\n"
2965	"}\n"
2966	"define void @f2() {\n"
2967	" call void @f()\n"
2968	" ret void\n"
2969	"}\n");
2970	LazyCallGraph CG = buildCG(M&: *M);
2971
2972	Function &F = lookupFunction(M&: *M, Name: "f");
2973	LazyCallGraph::Node &FN = CG.get(F);
2974	Function &F2 = lookupFunction(M&: *M, Name: "f2");
2975	LazyCallGraph::Node &F2N = CG.get(F);
2976
2977	// Force the graph to be fully expanded.
2978	CG.buildRefSCCs();
2979	auto I = CG.postorder_ref_scc_begin();
2980	LazyCallGraph::RefSCC *ORC = &*I++;
2981	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
2982
2983	auto *G1 = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2984	AddrSpace: F.getAddressSpace(), N: "g1", M: F.getParent());
2985	auto *G2 = Function::Create(Ty: F.getFunctionType(), Linkage: F.getLinkage(),
2986	AddrSpace: F.getAddressSpace(), N: "g2", M: F.getParent());
2987	BasicBlock *G1BB = BasicBlock::Create(Context, Name: "", Parent: G1);
2988	BasicBlock *G2BB = BasicBlock::Create(Context, Name: "", Parent: G2);
2989	// Create g1 -ref-> g2 and g2 -ref-> g1.
2990	(void)CastInst::CreatePointerCast(S: G2, Ty: PointerType::getUnqual(C&: Context), Name: "",
2991	InsertAtEnd: G1BB);
2992	(void)CastInst::CreatePointerCast(S: G1, Ty: PointerType::getUnqual(C&: Context), Name: "",
2993	InsertAtEnd: G2BB);
2994	// Create g2 -ref-> f2.
2995	(void)CastInst::CreatePointerCast(S: &F2, Ty: PointerType::getUnqual(C&: Context), Name: "",
2996	InsertAtEnd: G2BB);
2997	(void)ReturnInst::Create(C&: Context, InsertAtEnd: G1BB);
2998	(void)ReturnInst::Create(C&: Context, InsertAtEnd: G2BB);
2999
3000	// Create f -ref-> g1 and f -ref-> g2.
3001	(void)CastInst::CreatePointerCast(S: G1, Ty: PointerType::getUnqual(C&: Context), Name: "",
3002	InsertBefore: &*F.getEntryBlock().begin());
3003	(void)CastInst::CreatePointerCast(S: G2, Ty: PointerType::getUnqual(C&: Context), Name: "",
3004	InsertBefore: &*F.getEntryBlock().begin());
3005
3006	EXPECT_FALSE(verifyModule(*M, &errs()));
3007
3008	CG.addSplitRefRecursiveFunctions(OriginalFunction&: F, NewFunctions: SmallVector<Function *, 1>({G1, G2}));
3009
3010	LazyCallGraph::Node *G1N = CG.lookup(F: *G1);
3011	EXPECT_TRUE(G1N);
3012	LazyCallGraph::Node *G2N = CG.lookup(F: *G2);
3013	EXPECT_TRUE(G2N);
3014
3015	I = CG.postorder_ref_scc_begin();
3016	LazyCallGraph::RefSCC *RC = &*I++;
3017	EXPECT_EQ(4, RC->size());
3018	EXPECT_EQ(RC, ORC);
3019	EXPECT_EQ(RC, CG.lookupRefSCC(*G1N));
3020	EXPECT_EQ(RC, CG.lookupRefSCC(*G2N));
3021	EXPECT_EQ(RC, CG.lookupRefSCC(FN));
3022	EXPECT_EQ(RC, CG.lookupRefSCC(F2N));
3023	EXPECT_EQ(CG.postorder_ref_scc_end(), I);
3024	}
3025	}
3026