LLVM: lib/Analysis/LazyCallGraph.cpp Source File (original) (raw)
1
2
3
4
5
6
7
8
10
30#include
31
32#ifdef EXPENSIVE_CHECKS
34#endif
35
36using namespace llvm;
37
38#define DEBUG_TYPE "lcg"
39
40template struct LLVM_EXPORT_TEMPLATE Any::TypeId<const LazyCallGraph::SCC *>;
41
42void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,
43 Edge::Kind EK) {
44 EdgeIndexMap.try_emplace(&TargetN, Edges.size());
46}
47
48void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) {
49 Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK);
50}
51
52bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) {
53 auto IndexMapI = EdgeIndexMap.find(&TargetN);
54 if (IndexMapI == EdgeIndexMap.end())
55 return false;
56
57 Edges[IndexMapI->second] = Edge();
58 EdgeIndexMap.erase(IndexMapI);
59 return true;
60}
61
66 return;
67
68 LLVM_DEBUG(dbgs() << " Added callable function: " << N.getName() << "\n");
70}
71
73 assert(!Edges && "Must not have already populated the edges for this node!");
74
76 << "' to the graph.\n");
77
78 Edges = EdgeSequence();
79
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
102 if (auto *CB = dyn_cast(&I))
103 if (Function *Callee = CB->getCalledFunction())
104 if (->isDeclaration())
105 if (Callees.insert(Callee).second) {
106 Visited.insert(Callee);
107 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*Callee),
109 }
110
111 for (Value *Op : I.operand_values())
112 if (Constant *C = dyn_cast(Op))
113 if (Visited.insert(C).second)
115 }
116
117
118
119
121 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(F),
123 });
124
125
126
127 for (auto *F : G->LibFunctions)
129 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*F),
131
132 return *Edges;
133}
134
135void LazyCallGraph::Node::replaceFunction(Function &NewF) {
136 assert(F != &NewF && "Must not replace a function with itself!");
137 F = &NewF;
138}
139
140#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
142 dbgs() << *this << '\n';
143}
144#endif
145
148
149
150
151
154}
155
158 LLVM_DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
159 << "\n");
161 if (F.isDeclaration())
162 continue;
163
164
165
167 LibFunctions.insert(&F);
168
169 if (F.hasLocalLinkage())
170 continue;
171
172
173
175 << "' to entry set of the graph.\n");
177 }
178
179
180
181 for (auto &A : M.aliases()) {
182 if (A.hasLocalLinkage())
183 continue;
184 if (Function* F = dyn_cast(A.getAliasee())) {
186 << "' with alias '" << A.getName()
187 << "' to entry set of the graph.\n");
189 }
190 }
191
192
196 if (GV.hasInitializer())
197 if (Visited.insert(GV.getInitializer()).second)
198 Worklist.push_back(GV.getInitializer());
199
201 dbgs() << " Adding functions referenced by global initializers to the "
202 "entry set.\n");
204 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F),
206 });
207}
208
211 EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)),
212 SCCMap(std::move(G.SCCMap)), LibFunctions(std::move(G.LibFunctions)) {
213 updateGraphPtrs();
214}
215
216#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
219 RC.verify();
220 }
221}
222#endif
223
226
227
230}
231
233 BPA = std::move(G.BPA);
234 NodeMap = std::move(G.NodeMap);
235 EntryEdges = std::move(G.EntryEdges);
236 SCCBPA = std::move(G.SCCBPA);
237 SCCMap = std::move(G.SCCMap);
238 LibFunctions = std::move(G.LibFunctions);
239 updateGraphPtrs();
240 return *this;
241}
242
243#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
245 dbgs() << *this << '\n';
246}
247#endif
248
249#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
250void LazyCallGraph::SCC::verify() {
251 assert(OuterRefSCC && "Can't have a null RefSCC!");
252 assert(!Nodes.empty() && "Can't have an empty SCC!");
253
255 assert(N && "Can't have a null node!");
256 assert(OuterRefSCC->G->lookupSCC(*N) == this &&
257 "Node does not map to this SCC!");
258 assert(N->DFSNumber == -1 &&
259 "Must set DFS numbers to -1 when adding a node to an SCC!");
260 assert(N->LowLink == -1 &&
261 "Must set low link to -1 when adding a node to an SCC!");
262 for (Edge &E : **N)
263 assert(E.getNode().isPopulated() && "Can't have an unpopulated node!");
264
265#ifdef EXPENSIVE_CHECKS
266
270 while (!Worklist.empty()) {
272 if (!Visited.insert(VisitingNode).second)
273 continue;
274 for (Edge &E : (*VisitingNode)->calls())
275 Worklist.push_back(&E.getNode());
276 }
277 for (Node *NodeToVisit : Nodes) {
279 "Cannot reach all nodes within SCC");
280 }
281#endif
282 }
283}
284#endif
285
287 if (this == &C)
288 return false;
289
291 for (Edge &E : N->calls())
292 if (OuterRefSCC->G->lookupSCC(E.getNode()) == &C)
293 return true;
294
295
296 return false;
297}
298
300 if (this == &TargetC)
301 return false;
302
304
305
308
309
310 do {
313 for (Edge &E : N->calls()) {
314 SCC *CalleeC = G.lookupSCC(E.getNode());
315 if (!CalleeC)
316 continue;
317
318
319 if (CalleeC == &TargetC)
320 return true;
321
322
323
324 if (Visited.insert(CalleeC).second)
326 }
327 } while (!Worklist.empty());
328
329
330 return false;
331}
332
334
335#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
337 dbgs() << *this << '\n';
338}
339#endif
340
341#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
342void LazyCallGraph::RefSCC::verify() {
343 assert(G && "Can't have a null graph!");
344 assert(!SCCs.empty() && "Can't have an empty SCC!");
345
346
348 for (SCC *C : SCCs) {
349 assert(C && "Can't have a null SCC!");
350 C->verify();
351 assert(&C->getOuterRefSCC() == this &&
352 "SCC doesn't think it is inside this RefSCC!");
353 bool Inserted = SCCSet.insert(C).second;
354 assert(Inserted && "Found a duplicate SCC!");
355 auto IndexIt = SCCIndices.find(C);
356 assert(IndexIt != SCCIndices.end() &&
357 "Found an SCC that doesn't have an index!");
358 }
359
360
361 for (auto [C, I] : SCCIndices) {
362 assert(C && "Can't have a null SCC in the indices!");
363 assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
364 assert(SCCs[I] == C && "Index doesn't point to SCC!");
365 }
366
367
368 for (int I = 0, Size = SCCs.size(); I < Size; ++I) {
369 SCC &SourceSCC = *SCCs[I];
371 for (Edge &E : *N) {
372 if (!E.isCall())
373 continue;
374 SCC &TargetSCC = *G->lookupSCC(E.getNode());
375 if (&TargetSCC.getOuterRefSCC() == this) {
376 assert(SCCIndices.find(&TargetSCC)->second <= I &&
377 "Edge between SCCs violates post-order relationship.");
378 continue;
379 }
380 }
381 }
382
383#ifdef EXPENSIVE_CHECKS
384
386 for (SCC *C : SCCs) {
389 }
394 while (!Worklist.empty()) {
396 if (!Visited.insert(VisitingNode).second)
397 continue;
398 for (Edge &E : **VisitingNode)
399 Worklist.push_back(&E.getNode());
400 }
401 for (Node *NodeToVisit : Nodes) {
403 "Cannot reach all nodes within RefSCC");
404 }
405 }
406#endif
407}
408#endif
409
411 if (&RC == this)
412 return false;
413
414
418 if (G->lookupRefSCC(E.getNode()) == &RC)
419 return true;
420
421 return false;
422}
423
425 if (&RC == this)
426 return false;
427
428
429
430
434 Visited.insert(this);
435 do {
437 for (SCC &C : DescendantRC)
440 auto *ChildRC = G->lookupRefSCC(E.getNode());
441 if (ChildRC == &RC)
442 return true;
443 if (!ChildRC || !Visited.insert(ChildRC).second)
444 continue;
446 }
447 } while (!Worklist.empty());
448
449 return false;
450}
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514template <typename SCCT, typename PostorderSequenceT, typename SCCIndexMapT,
515 typename ComputeSourceConnectedSetCallableT,
516 typename ComputeTargetConnectedSetCallableT>
519 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
520 SCCIndexMapT &SCCIndices,
521 ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
522 ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
523 int SourceIdx = SCCIndices[&SourceSCC];
524 int TargetIdx = SCCIndices[&TargetSCC];
525 assert(SourceIdx < TargetIdx && "Cannot have equal indices here!");
526
528
529
530 ComputeSourceConnectedSet(ConnectedSet);
531
532
533
534
535 auto SourceI = std::stable_partition(
536 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
537 [&ConnectedSet](SCCT *C) { return !ConnectedSet.count(C); });
538 for (int I = SourceIdx, E = TargetIdx + 1; I < E; ++I)
539 SCCIndices.find(SCCs[I])->second = I;
540
541
542
543 if (!ConnectedSet.count(&TargetSCC)) {
544 assert(SourceI > (SCCs.begin() + SourceIdx) &&
545 "Must have moved the source to fix the post-order.");
546 assert(*std::prev(SourceI) == &TargetSCC &&
547 "Last SCC to move should have bene the target.");
548
549
550
551 return make_range(std::prev(SourceI), std::prev(SourceI));
552 }
553
554 assert(SCCs[TargetIdx] == &TargetSCC &&
555 "Should not have moved target if connected!");
556 SourceIdx = SourceI - SCCs.begin();
557 assert(SCCs[SourceIdx] == &SourceSCC &&
558 "Bad updated index computation for the source SCC!");
559
560
561
562
563 if (SourceIdx + 1 < TargetIdx) {
564 ConnectedSet.clear();
565 ComputeTargetConnectedSet(ConnectedSet);
566
567
568
569 auto TargetI = std::stable_partition(
570 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
571 [&ConnectedSet](SCCT *C) { return ConnectedSet.count(C); });
572 for (int I = SourceIdx + 1, E = TargetIdx + 1; I < E; ++I)
573 SCCIndices.find(SCCs[I])->second = I;
574 TargetIdx = std::prev(TargetI) - SCCs.begin();
575 assert(SCCs[TargetIdx] == &TargetSCC &&
576 "Should always end with the target!");
577 }
578
579
580
581
582
583 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
584}
585
587 Node &SourceN, Node &TargetN,
589 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
591
592#ifdef EXPENSIVE_CHECKS
595#endif
596
597 SCC &SourceSCC = *G->lookupSCC(SourceN);
598 SCC &TargetSCC = *G->lookupSCC(TargetN);
599
600
601
602 if (&SourceSCC == &TargetSCC) {
603 SourceN->setEdgeKind(TargetN, Edge::Call);
604 return false;
605 }
606
607
608
609
610
611
612
613 int SourceIdx = SCCIndices[&SourceSCC];
614 int TargetIdx = SCCIndices[&TargetSCC];
615 if (TargetIdx < SourceIdx) {
616 SourceN->setEdgeKind(TargetN, Edge::Call);
617 return false;
618 }
619
620
622#ifdef EXPENSIVE_CHECKS
623
624
626#endif
627 ConnectedSet.insert(&SourceSCC);
628 auto IsConnected = [&](SCC &C) {
630 for (Edge &E : N->calls())
631 if (ConnectedSet.count(G->lookupSCC(E.getNode())))
632 return true;
633
634 return false;
635 };
636
638 make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
639 if (IsConnected(*C))
640 ConnectedSet.insert(C);
641 };
642
643
644
645
646
648#ifdef EXPENSIVE_CHECKS
649
650
652#endif
653 ConnectedSet.insert(&TargetSCC);
656 do {
660 if (!E.isCall())
661 continue;
662 SCC &EdgeC = *G->lookupSCC(E.getNode());
664
665 continue;
666 if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
667
668 continue;
669
670 if (ConnectedSet.insert(&EdgeC).second)
672 }
673 } while (!Worklist.empty());
674 };
675
676
677
678
679
681 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
682 ComputeTargetConnectedSet);
683
684
685 if (MergeCB)
686 MergeCB(ArrayRef(MergeRange.begin(), MergeRange.end()));
687
688
689
690 if (MergeRange.empty()) {
691
692 SourceN->setEdgeKind(TargetN, Edge::Call);
693 return false;
694 }
695
696#ifdef EXPENSIVE_CHECKS
697
698
700#endif
701
702
703
704
705
706
707
708 for (SCC *C : MergeRange) {
710 "We merge *into* the target and shouldn't process it here!");
711 SCCIndices.erase(C);
712 TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end());
714 G->SCCMap[N] = &TargetSCC;
715 C->clear();
717 }
718
719
720
721 int IndexOffset = MergeRange.end() - MergeRange.begin();
722 auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
724 SCCIndices[C] -= IndexOffset;
725
726
727 SourceN->setEdgeKind(TargetN, Edge::Call);
728
729
730 return true;
731}
732
734 Node &TargetN) {
735 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
736
737#ifdef EXPENSIVE_CHECKS
740#endif
741
742 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
743 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
744 assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) &&
745 "Source and Target must be in separate SCCs for this to be trivial!");
746
747
748 SourceN->setEdgeKind(TargetN, Edge::Ref);
749}
750
753 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
754
755#ifdef EXPENSIVE_CHECKS
758#endif
759
760 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
761 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
762
763 SCC &TargetSCC = *G->lookupSCC(TargetN);
764 assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in "
765 "the same SCC to require the "
766 "full CG update.");
767
768
769 SourceN->setEdgeKind(TargetN, Edge::Ref);
770
771
772
773
774
775
776
777
778
779
780
781
782
783 SCC &OldSCC = TargetSCC;
787
788
790 Worklist.swap(OldSCC.Nodes);
791 for (Node *N : Worklist) {
792 N->DFSNumber = N->LowLink = 0;
794 }
795
796
797
798
799
800
801
802
803
804 TargetN.DFSNumber = TargetN.LowLink = -1;
805 OldSCC.Nodes.push_back(&TargetN);
806 G->SCCMap[&TargetN] = &OldSCC;
807
808
809 for (Node *RootN : Worklist) {
811 "Cannot begin a new root with a non-empty DFS stack!");
813 "Cannot begin a new root with pending nodes for an SCC!");
814
815
816 if (RootN->DFSNumber != 0) {
817 assert(RootN->DFSNumber == -1 &&
818 "Shouldn't have any mid-DFS root nodes!");
819 continue;
820 }
821
822 RootN->DFSNumber = RootN->LowLink = 1;
823 int NextDFSNumber = 2;
824
825 DFSStack.emplace_back(RootN, (*RootN)->call_begin());
826 do {
828 auto E = (*N)->call_end();
829 while (I != E) {
830 Node &ChildN = I->getNode();
831 if (ChildN.DFSNumber == 0) {
832
833
835
836 assert(->SCCMap.count(&ChildN) &&
837 "Found a node with 0 DFS number but already in an SCC!");
838 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
839 N = &ChildN;
840 I = (*N)->call_begin();
841 E = (*N)->call_end();
842 continue;
843 }
844
845
846 if (ChildN.DFSNumber == -1) {
847 if (G->lookupSCC(ChildN) == &OldSCC) {
848
849
850
851
852 int OldSize = OldSCC.size();
853 OldSCC.Nodes.push_back(N);
854 OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());
855 PendingSCCStack.clear();
856 while (!DFSStack.empty())
857 OldSCC.Nodes.push_back(DFSStack.pop_back_val().first);
859 N.DFSNumber = N.LowLink = -1;
861 }
862 N = nullptr;
863 break;
864 }
865
866
867
868
869 ++I;
870 continue;
871 }
872
873
874 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
875 if (ChildN.LowLink < N->LowLink)
876 N->LowLink = ChildN.LowLink;
877
878
879 ++I;
880 }
881 if ()
882
883 break;
884
885
886
888
889
890
891 if (N->LowLink != N->DFSNumber)
892 continue;
893
894
895
896 int RootDFSNumber = N->DFSNumber;
897
898
900 PendingSCCStack.rbegin(),
902 return N->DFSNumber < RootDFSNumber;
903 }));
904
905
906
907 NewSCCs.push_back(G->createSCC(*this, SCCNodes));
908 for (Node &N : *NewSCCs.back()) {
909 N.DFSNumber = N.LowLink = -1;
910 G->SCCMap[&N] = NewSCCs.back();
911 }
912 PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
913 } while (!DFSStack.empty());
914 }
915
916
917
918
919
920 int OldIdx = SCCIndices[&OldSCC];
921 SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
922
923
924
926 SCCIndices[SCCs[Idx]] = Idx;
927
928 return make_range(SCCs.begin() + OldIdx,
929 SCCs.begin() + OldIdx + NewSCCs.size());
930}
931
933 Node &TargetN) {
934 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
935
936 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
937 assert(G->lookupRefSCC(TargetN) != this &&
938 "Target must not be in this RefSCC.");
939#ifdef EXPENSIVE_CHECKS
940 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
941 "Target must be a descendant of the Source.");
942#endif
943
944
945
946 SourceN->setEdgeKind(TargetN, Edge::Call);
947
948#ifdef EXPENSIVE_CHECKS
950#endif
951}
952
954 Node &TargetN) {
955 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
956
957 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
958 assert(G->lookupRefSCC(TargetN) != this &&
959 "Target must not be in this RefSCC.");
960#ifdef EXPENSIVE_CHECKS
961 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
962 "Target must be a descendant of the Source.");
963#endif
964
965
966
967 SourceN->setEdgeKind(TargetN, Edge::Ref);
968
969#ifdef EXPENSIVE_CHECKS
971#endif
972}
973
975 Node &TargetN) {
976 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
977 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
978
979 SourceN->insertEdgeInternal(TargetN, Edge::Ref);
980
981#ifdef EXPENSIVE_CHECKS
983#endif
984}
985
988
989 SourceN->insertEdgeInternal(TargetN, EK);
990
991 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
992
993 assert(G->lookupRefSCC(TargetN) != this &&
994 "Target must not be in this RefSCC.");
995#ifdef EXPENSIVE_CHECKS
996 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
997 "Target must be a descendant of the Source.");
998#endif
999
1000#ifdef EXPENSIVE_CHECKS
1002#endif
1003}
1004
1007 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
1008 RefSCC &SourceC = *G->lookupRefSCC(SourceN);
1009 assert(&SourceC != this && "Source must not be in this RefSCC.");
1010#ifdef EXPENSIVE_CHECKS
1012 "Source must be a descendant of the Target.");
1013#endif
1014
1016
1017#ifdef EXPENSIVE_CHECKS
1020#endif
1021
1022 int SourceIdx = G->RefSCCIndices[&SourceC];
1023 int TargetIdx = G->RefSCCIndices[this];
1024 assert(SourceIdx < TargetIdx &&
1025 "Postorder list doesn't see edge as incoming!");
1026
1027
1028
1029
1030
1031
1032
1033
1035 Set.insert(&SourceC);
1036 auto IsConnected = [&](RefSCC &RC) {
1040 if (Set.count(G->lookupRefSCC(E.getNode())))
1041 return true;
1042
1043 return false;
1044 };
1045
1046 for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1,
1047 G->PostOrderRefSCCs.begin() + TargetIdx + 1))
1048 if (IsConnected(*C))
1049 Set.insert(C);
1050 };
1051
1052
1053
1054
1055
1057 Set.insert(this);
1060 do {
1065 RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode());
1066 if (G->getRefSCCIndex(EdgeRC) <= SourceIdx)
1067
1068 continue;
1069
1070 if (Set.insert(&EdgeRC).second)
1072 }
1073 } while (!Worklist.empty());
1074 };
1075
1076
1077
1078
1079
1082 SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices,
1083 ComputeSourceConnectedSet, ComputeTargetConnectedSet);
1084
1085
1086
1088
1089
1090 MergeSet.insert(this);
1091
1092
1093
1095 int SCCIndex = 0;
1096 for (RefSCC *RC : MergeRange) {
1097 assert(RC != this && "We're merging into the target RefSCC, so it "
1098 "shouldn't be in the range.");
1099
1100
1101
1102
1103
1104 for (SCC &InnerC : *RC) {
1105 InnerC.OuterRefSCC = this;
1106 SCCIndices[&InnerC] = SCCIndex++;
1109 }
1110
1111
1112
1113 if (MergedSCCs.empty())
1114 MergedSCCs = std::move(RC->SCCs);
1115 else
1116 MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());
1117 RC->SCCs.clear();
1119 }
1120
1121
1122 for (SCC &InnerC : *this)
1123 SCCIndices[&InnerC] = SCCIndex++;
1124 MergedSCCs.append(SCCs.begin(), SCCs.end());
1125 SCCs = std::move(MergedSCCs);
1126
1127
1128 for (RefSCC *RC : MergeRange)
1129 G->RefSCCIndices.erase(RC);
1130 int IndexOffset = MergeRange.end() - MergeRange.begin();
1131 auto EraseEnd =
1132 G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());
1133 for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))
1134 G->RefSCCIndices[RC] -= IndexOffset;
1135
1136
1137
1138 SourceN->insertEdgeInternal(TargetN, Edge::Ref);
1139
1140
1141
1142
1143
1144 return DeletedRefSCCs;
1145}
1146
1148 assert(G->lookupRefSCC(SourceN) == this &&
1149 "The source must be a member of this RefSCC.");
1150 assert(G->lookupRefSCC(TargetN) != this &&
1151 "The target must not be a member of this RefSCC");
1152
1153#ifdef EXPENSIVE_CHECKS
1156#endif
1157
1158
1159 bool Removed = SourceN->removeEdgeInternal(TargetN);
1160 (void)Removed;
1161 assert(Removed && "Target not in the edge set for this caller?");
1162}
1163
1166 ArrayRef<std::pair<Node *, Node *>> Edges) {
1167
1169
1170#ifdef EXPENSIVE_CHECKS
1171
1172
1173
1176
1177
1178 if (G)
1180 });
1181#endif
1182
1183
1184 for (auto [SourceN, TargetN] : Edges) {
1185 assert(!(**SourceN)[*TargetN].isCall() &&
1186 "Cannot remove a call edge, it must first be made a ref edge");
1187
1188 bool Removed = (*SourceN)->removeEdgeInternal(*TargetN);
1189 (void)Removed;
1190 assert(Removed && "Target not in the edge set for this caller?");
1191 }
1192
1193
1194
1195
1196 if (llvm::all_of(Edges, [&](std::pair<Node *, Node *> E) {
1197 return E.first == E.second ||
1198 G->lookupSCC(*E.first) == G->lookupSCC(*E.second);
1199 }))
1200 return Result;
1201
1202
1203
1204
1205
1206
1207
1208 int PostOrderNumber = 0;
1209
1210
1211
1215 N.DFSNumber = N.LowLink = 0;
1216
1217 Worklist.append(C->Nodes.begin(), C->Nodes.end());
1218 }
1219
1220
1221
1222
1223 const int NumRefSCCNodes = Worklist.size();
1224
1227 do {
1229 "Cannot begin a new root with a non-empty DFS stack!");
1231 "Cannot begin a new root with pending nodes for an SCC!");
1232
1234
1235 if (RootN->DFSNumber != 0) {
1236 assert(RootN->DFSNumber == -1 &&
1237 "Shouldn't have any mid-DFS root nodes!");
1238 continue;
1239 }
1240
1241 RootN->DFSNumber = RootN->LowLink = 1;
1242 int NextDFSNumber = 2;
1243
1245 do {
1247 auto E = (*N)->end();
1248
1249 assert(N->DFSNumber != 0 && "We should always assign a DFS number "
1250 "before processing a node.");
1251
1252 while (I != E) {
1253 Node &ChildN = I->getNode();
1254 if (ChildN.DFSNumber == 0) {
1255
1256
1257
1259
1260
1261 ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1262 N = &ChildN;
1264 E = ChildN->end();
1265 continue;
1266 }
1267 if (ChildN.DFSNumber == -1) {
1268
1269
1270 ++I;
1271 continue;
1272 }
1273
1274
1275
1276 assert(ChildN.LowLink != 0 &&
1277 "Low-link must not be zero with a non-zero DFS number.");
1278 if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
1279 N->LowLink = ChildN.LowLink;
1280 ++I;
1281 }
1282
1283
1284
1286
1287
1288
1289 if (N->LowLink != N->DFSNumber) {
1291 "We never found a viable root for a RefSCC to pop off!");
1292 continue;
1293 }
1294
1295
1296 int RefSCCNumber = PostOrderNumber++;
1297 int RootDFSNumber = N->DFSNumber;
1298
1299
1300
1301
1303 if (N->DFSNumber < RootDFSNumber)
1304
1305 return true;
1306
1307
1308 N->DFSNumber = -1;
1309
1310
1311 N->LowLink = RefSCCNumber;
1312 return false;
1313 });
1314 auto RefSCCNodes = make_range(StackRI.base(), PendingRefSCCStack.end());
1315
1316
1317
1318
1319
1320 if (llvm::size(RefSCCNodes) == NumRefSCCNodes) {
1321
1322 for (Node *N : RefSCCNodes)
1323 N->LowLink = -1;
1324
1325 return Result;
1326 }
1327
1328
1329
1330 PendingRefSCCStack.erase(RefSCCNodes.begin(), PendingRefSCCStack.end());
1331 } while (!DFSStack.empty());
1332
1333 assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
1334 assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");
1335 } while (!Worklist.empty());
1336
1337 assert(PostOrderNumber > 1 &&
1338 "Should never finish the DFS when the existing RefSCC remains valid!");
1339
1340
1341
1342
1343
1344 for (int I = 0; I < PostOrderNumber; ++I)
1345 Result.push_back(G->createRefSCC(*G));
1346
1347
1348
1349
1350
1351
1352
1353
1354 int Idx = G->getRefSCCIndex(*this);
1355 G->PostOrderRefSCCs.erase(G->PostOrderRefSCCs.begin() + Idx);
1356 G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, Result.begin(),
1357 Result.end());
1358 for (int I : seq(Idx, G->PostOrderRefSCCs.size()))
1359 G->RefSCCIndices[G->PostOrderRefSCCs[I]] = I;
1360
1362
1363 int SCCNumber = C->begin()->LowLink;
1364
1365
1367 assert(N.LowLink == SCCNumber &&
1368 "Cannot have different numbers for nodes in the same SCC!");
1369 N.LowLink = -1;
1370 }
1371
1372 RefSCC &RC = *Result[SCCNumber];
1373 int SCCIndex = RC.SCCs.size();
1374 RC.SCCs.push_back(C);
1375 RC.SCCIndices[C] = SCCIndex;
1376 C->OuterRefSCC = &RC;
1377 }
1378
1379
1380
1381 G = nullptr;
1382 SCCs.clear();
1383 SCCIndices.clear();
1384
1385#ifdef EXPENSIVE_CHECKS
1386
1387 for (RefSCC *RC : Result)
1388 RC->verify();
1389#endif
1390
1391
1392 return Result;
1393}
1394
1396 Node &TargetN) {
1397#ifdef EXPENSIVE_CHECKS
1399
1400
1401
1402 SCC &SourceC = *G->lookupSCC(SourceN);
1403 SCC &TargetC = *G->lookupSCC(TargetN);
1404 if (&SourceC != &TargetC)
1405 assert(SourceC.isAncestorOf(TargetC) &&
1406 "Call edge is not trivial in the SCC graph!");
1407#endif
1408
1409
1410 auto [Iterator, Inserted] =
1411 SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size());
1412 if (!Inserted) {
1413
1414 Edge &E = SourceN->Edges[Iterator->second];
1416 return;
1418 } else {
1419
1421 }
1422}
1423
1425#ifdef EXPENSIVE_CHECKS
1427
1428
1429 RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
1430 RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1431 if (&SourceRC != &TargetRC)
1432 assert(SourceRC.isAncestorOf(TargetRC) &&
1433 "Ref edge is not trivial in the RefSCC graph!");
1434#endif
1435
1436
1437 auto [Iterator, Inserted] =
1438 SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size());
1439 (void)Iterator;
1440 if (!Inserted)
1441
1442 return;
1443
1444
1446}
1447
1449 Function &OldF = N.getFunction();
1450
1451#ifdef EXPENSIVE_CHECKS
1453
1454 assert(G->lookupRefSCC(N) == this &&
1455 "Cannot replace the function of a node outside this RefSCC.");
1456
1457 assert(G->NodeMap.find(&NewF) == G->NodeMap.end() &&
1458 "Must not have already walked the new function!'");
1459
1460
1461
1462
1463
1464
1465
1466 assert(&OldF != &NewF && "Cannot replace a function with itself!");
1468 "Must have moved all uses from the old function to the new!");
1469#endif
1470
1471 N.replaceFunction(NewF);
1472
1473
1474 G->NodeMap.erase(&OldF);
1476
1477
1478 if (G->isLibFunction(OldF)) {
1479 G->LibFunctions.remove(&OldF);
1480 G->LibFunctions.insert(&NewF);
1481 }
1482}
1483
1485 assert(SCCMap.empty() &&
1486 "This method cannot be called after SCCs have been formed!");
1487
1488 return SourceN->insertEdgeInternal(TargetN, EK);
1489}
1490
1492 assert(SCCMap.empty() &&
1493 "This method cannot be called after SCCs have been formed!");
1494
1495 bool Removed = SourceN->removeEdgeInternal(TargetN);
1496 (void)Removed;
1497 assert(Removed && "Target not in the edge set for this caller?");
1498}
1499
1501
1502
1503 assert(F.hasZeroLiveUses() &&
1504 "This routine should only be called on trivially dead functions!");
1505
1506
1507
1509 "Must not remove lib functions from the call graph!");
1510
1511 auto NI = NodeMap.find(&F);
1512 assert(NI != NodeMap.end() && "Removed function should be known!");
1513
1515
1516
1518 if (E.isCall())
1519 N->setEdgeKind(E.getNode(), Edge::Ref);
1520 }
1521}
1522
1524 if (DeadFs.empty())
1525 return;
1526
1527
1529 for (Function *DeadF : DeadFs) {
1531#ifndef NDEBUG
1533 assert(!E.isCall() &&
1534 "dead function shouldn't have any outgoing call edges");
1535 }
1536#endif
1538 RCs[RC].push_back(N);
1539 }
1540
1541
1542
1543 for (auto [RC, DeadNs] : RCs) {
1545 for (Node *DeadN : DeadNs) {
1546 for (Edge &E : **DeadN) {
1548 InternalEdgesToRemove.push_back({DeadN, &E.getNode()});
1549 else
1550 RC->removeOutgoingEdge(*DeadN, E.getNode());
1551 }
1552 }
1553
1554
1555 (void)RC->removeInternalRefEdges(InternalEdgesToRemove);
1556 for (Node *DeadN : DeadNs) {
1560 DeadRC->clear();
1561 DeadRC->G = nullptr;
1562 }
1563 }
1564
1565 for (Function *DeadF : DeadFs) {
1567
1568 EntryEdges.removeEdgeInternal(N);
1569 SCCMap.erase(SCCMap.find(&N));
1570 NodeMap.erase(NodeMap.find(DeadF));
1571
1572 N.clear();
1573 N.G = nullptr;
1574 N.F = nullptr;
1575 }
1576}
1577
1578
1579
1580
1581
1584
1585
1586
1587
1588#ifndef NDEBUG
1591#endif
1592
1594 if (auto *CB = dyn_cast(&I)) {
1595 if (Function *Callee = CB->getCalledFunction()) {
1596 if (Callee == &NewFunction)
1598 }
1599 }
1600#ifndef NDEBUG
1601 for (Value *Op : I.operand_values()) {
1602 if (Constant *C = dyn_cast(Op)) {
1603 if (Visited.insert(C).second)
1605 }
1606 }
1607#endif
1608 }
1609
1610#ifndef NDEBUG
1611 bool FoundNewFunction = false;
1613 if (&F == &NewFunction)
1614 FoundNewFunction = true;
1615 });
1616 assert(FoundNewFunction && "No edge from original function to new function");
1617#endif
1618
1620}
1621
1625 "Original function's node should already exist");
1626 Node &OriginalN = get(OriginalFunction);
1629
1630#ifdef EXPENSIVE_CHECKS
1631 OriginalRC->verify();
1632 auto VerifyOnExit = make_scope_exit([&]() { OriginalRC->verify(); });
1633#endif
1634
1636 "New function's node should not already exist");
1637 Node &NewN = initNode(NewFunction);
1638
1640
1641 SCC *NewC = nullptr;
1642 for (Edge &E : *NewN) {
1643 Node &EN = E.getNode();
1645
1646
1647
1648 NewC = OriginalC;
1649 NewC->Nodes.push_back(&NewN);
1650 break;
1651 }
1652 }
1653
1654 if (!NewC) {
1655 for (Edge &E : *NewN) {
1656 Node &EN = E.getNode();
1658
1659
1660
1661 RefSCC *NewRC = OriginalRC;
1663
1664
1665
1666
1667
1668
1669
1670
1671 int InsertIndex = EK == Edge::Kind::Call ? NewRC->SCCIndices[OriginalC]
1672 : NewRC->SCCIndices.size();
1673 NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC);
1674 for (int I = InsertIndex, Size = NewRC->SCCs.size(); I < Size; ++I)
1675 NewRC->SCCIndices[NewRC->SCCs[I]] = I;
1676
1677 break;
1678 }
1679 }
1680 }
1681
1682 if (!NewC) {
1683
1684
1685
1686 RefSCC *NewRC = createRefSCC(*this);
1688 NewRC->SCCIndices[NewC] = 0;
1689 NewRC->SCCs.push_back(NewC);
1690 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1691 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1692 for (int I = OriginalRCIndex, Size = PostOrderRefSCCs.size(); I < Size; ++I)
1693 RefSCCIndices[PostOrderRefSCCs[I]] = I;
1694 }
1695
1696 SCCMap[&NewN] = NewC;
1697
1698 OriginalN->insertEdgeInternal(NewN, EK);
1699}
1700
1703 assert(!NewFunctions.empty() && "Can't add zero functions");
1705 "Original function's node should already exist");
1706 Node &OriginalN = get(OriginalFunction);
1708
1709#ifdef EXPENSIVE_CHECKS
1710 OriginalRC->verify();
1712 OriginalRC->verify();
1713 for (Function *NewFunction : NewFunctions)
1715 });
1716#endif
1717
1718 bool ExistsRefToOriginalRefSCC = false;
1719
1720 for (Function *NewFunction : NewFunctions) {
1721 Node &NewN = initNode(*NewFunction);
1722
1724
1725
1726
1727 for (Edge &E : *NewN) {
1728 if (lookupRefSCC(E.getNode()) == OriginalRC) {
1729 ExistsRefToOriginalRefSCC = true;
1730 break;
1731 }
1732 }
1733 }
1734
1736 if (ExistsRefToOriginalRefSCC) {
1737
1738
1739
1740 NewRC = OriginalRC;
1741 } else {
1742
1743 NewRC = createRefSCC(*this);
1744
1745
1746
1747 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1748 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1749 for (int I = OriginalRCIndex, Size = PostOrderRefSCCs.size(); I < Size; ++I)
1750 RefSCCIndices[PostOrderRefSCCs[I]] = I;
1751 }
1752
1753 for (Function *NewFunction : NewFunctions) {
1754 Node &NewN = get(*NewFunction);
1755
1756
1757
1758
1760
1761
1762
1763 auto Index = NewRC->SCCIndices.size();
1764 NewRC->SCCIndices[NewC] = Index;
1765 NewRC->SCCs.push_back(NewC);
1766 SCCMap[&NewN] = NewC;
1767 }
1768
1769#ifndef NDEBUG
1770 for (Function *F1 : NewFunctions) {
1772 "Expected ref edges from original function to every new function");
1774 for (Function *F2 : NewFunctions) {
1775 if (F1 == F2)
1776 continue;
1779 "Edges between new functions must be ref edges");
1780 }
1781 }
1782#endif
1783}
1784
1786 return *new (MappedN = BPA.Allocate()) Node(*this, F);
1787}
1788
1789void LazyCallGraph::updateGraphPtrs() {
1790
1791
1792 for (auto &FunctionNodePair : NodeMap)
1793 FunctionNodePair.second->G = this;
1794
1795 for (auto *RC : PostOrderRefSCCs)
1796 RC->G = this;
1797}
1798
1801 N.DFSNumber = N.LowLink = -1;
1802 N.populate();
1804 return N;
1805}
1806
1807template <typename RootsT, typename GetBeginT, typename GetEndT,
1808 typename GetNodeT, typename FormSCCCallbackT>
1809void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1810 GetEndT &&GetEnd, GetNodeT &&GetNode,
1811 FormSCCCallbackT &&FormSCC) {
1812 using EdgeItT = decltype(GetBegin(std::declval<Node &>()));
1813
1816
1817
1818 for (Node *RootN : Roots) {
1820 "Cannot begin a new root with a non-empty DFS stack!");
1822 "Cannot begin a new root with pending nodes for an SCC!");
1823
1824
1825 if (RootN->DFSNumber != 0) {
1826 assert(RootN->DFSNumber == -1 &&
1827 "Shouldn't have any mid-DFS root nodes!");
1828 continue;
1829 }
1830
1831 RootN->DFSNumber = RootN->LowLink = 1;
1832 int NextDFSNumber = 2;
1833
1834 DFSStack.emplace_back(RootN, GetBegin(*RootN));
1835 do {
1837 auto E = GetEnd(*N);
1838 while (I != E) {
1839 Node &ChildN = GetNode(I);
1840 if (ChildN.DFSNumber == 0) {
1841
1842
1844
1845 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1846 N = &ChildN;
1848 E = GetEnd(*N);
1849 continue;
1850 }
1851
1852
1853
1854
1855 if (ChildN.DFSNumber == -1) {
1856 ++I;
1857 continue;
1858 }
1859
1860
1861 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
1862 if (ChildN.LowLink < N->LowLink)
1863 N->LowLink = ChildN.LowLink;
1864
1865
1866 ++I;
1867 }
1868
1869
1870
1872
1873
1874
1875 if (N->LowLink != N->DFSNumber)
1876 continue;
1877
1878
1879
1880 int RootDFSNumber = N->DFSNumber;
1881
1882
1884 PendingSCCStack.rbegin(),
1886 return N->DFSNumber < RootDFSNumber;
1887 }));
1888
1889
1890 FormSCC(SCCNodes);
1891 PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
1892 } while (!DFSStack.empty());
1893 }
1894}
1895
1896
1897
1898
1899
1900
1901void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1902 assert(RC.SCCs.empty() && "Already built SCCs!");
1903 assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
1904
1906 assert(N->LowLink >= (*Nodes.begin())->LowLink &&
1907 "We cannot have a low link in an SCC lower than its root on the "
1908 "stack!");
1909
1910
1911
1912 N->DFSNumber = N->LowLink = 0;
1913 }
1914
1915
1916
1917
1918 buildGenericSCCs(
1919 Nodes, [](Node &N) { return N->call_begin(); },
1920 [](Node &N) { return N->call_end(); },
1921 [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); },
1922 [this, &RC](node_stack_range Nodes) {
1923 RC.SCCs.push_back(createSCC(RC, Nodes));
1924 for (Node &N : *RC.SCCs.back()) {
1925 N.DFSNumber = N.LowLink = -1;
1926 SCCMap[&N] = RC.SCCs.back();
1927 }
1928 });
1929
1930
1931 for (int I = 0, Size = RC.SCCs.size(); I < Size; ++I)
1932 RC.SCCIndices[RC.SCCs[I]] = I;
1933}
1934
1936 if (EntryEdges.empty() || !PostOrderRefSCCs.empty())
1937
1938 return;
1939
1940 assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
1941
1943 for (Edge &E : *this)
1945
1946
1947 buildGenericSCCs(
1948 Roots,
1950
1951 N.populate();
1952 return N->begin();
1953 },
1954 [](Node &N) { return N->end(); },
1957 RefSCC *NewRC = createRefSCC(*this);
1958 buildSCCs(*NewRC, Nodes);
1959
1960
1961
1962 bool Inserted =
1963 RefSCCIndices.try_emplace(NewRC, PostOrderRefSCCs.size()).second;
1964 (void)Inserted;
1965 assert(Inserted && "Cannot already have this RefSCC in the index map!");
1966 PostOrderRefSCCs.push_back(NewRC);
1967#ifdef EXPENSIVE_CHECKS
1968 NewRC->verify();
1969#endif
1970 });
1971}
1972
1976 while (!Worklist.empty()) {
1978
1979 if (Function *F = dyn_cast(C)) {
1980 if (->isDeclaration())
1981 Callback(*F);
1982 continue;
1983 }
1984
1985
1986
1987 if (isa(C))
1988 continue;
1989
1990 for (Value *Op : C->operand_values())
1991 if (Visited.insert(cast(Op)).second)
1993 }
1994}
1995
1997
1999
2001 OS << " Edges in function: " << N.getFunction().getName() << "\n";
2003 OS << " " << (E.isCall() ? "call" : "ref ") << " -> "
2004 << E.getFunction().getName() << "\n";
2005
2006 OS << "\n";
2007}
2008
2010 OS << " SCC with " << C.size() << " functions:\n";
2011
2013 OS << " " << N.getFunction().getName() << "\n";
2014}
2015
2017 OS << " RefSCC with " << C.size() << " call SCCs:\n";
2018
2021
2022 OS << "\n";
2023}
2024
2028
2029 OS << "Printing the call graph for module: " << M.getModuleIdentifier()
2030 << "\n\n";
2031
2034
2035 G.buildRefSCCs();
2038
2040}
2041
2044
2046 std::string Name =
2047 "\"" + DOT::EscapeString(std::string(N.getFunction().getName())) + "\"";
2048
2050 OS << " " << Name << " -> \""
2051 << DOT::EscapeString(std::string(E.getFunction().getName())) << "\"";
2052 if (!E.isCall())
2053 OS << " [style=dashed,label=\"ref\"]";
2054 OS << ";\n";
2055 }
2056
2057 OS << "\n";
2058}
2059
2063
2064 OS << "digraph \"" << DOT::EscapeString(M.getModuleIdentifier()) << "\" {\n";
2065
2068
2069 OS << "}\n";
2070
2072}
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
This file contains the declarations for the subclasses of Constant, which represent the different fla...
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
static void printNode(raw_ostream &OS, LazyCallGraph::Node &N)
static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C)
static iterator_range< typename PostorderSequenceT::iterator > updatePostorderSequenceForEdgeInsertion(SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs, SCCIndexMapT &SCCIndices, ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet, ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet)
Generic helper that updates a postorder sequence of SCCs for a potentially cycle-introducing edge ins...
static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N)
static LazyCallGraph::Edge::Kind getEdgeKind(Function &OriginalFunction, Function &NewFunction)
static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C)
static void addEdge(SmallVectorImpl< LazyCallGraph::Edge > &Edges, DenseMap< LazyCallGraph::Node *, int > &EdgeIndexMap, LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK)
static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI)
Implements a lazy call graph analysis and related passes for the new pass manager.
static StringRef getName(Value *V)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file defines the make_scope_exit function, which executes user-defined cleanup logic at scope ex...
Provides some synthesis utilities to produce sequences of values.
This file defines the SmallPtrSet class.
This file defines the SmallVector class.
This templated class represents "all analyses that operate over " (e....
API to communicate dependencies between analyses during invalidation.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
bool empty() const
empty - Check if the array is empty.
LLVM Basic Block Representation.
This is an important base class in LLVM.
This class represents an Operation in the Expression.
std::pair< iterator, bool > try_emplace(KeyT &&Key, Ts &&...Args)
An analysis pass which computes the call graph for a module.
LazyCallGraphDOTPrinterPass(raw_ostream &OS)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
LazyCallGraphPrinterPass(raw_ostream &OS)
An iterator used for the edges to both entry nodes and child nodes.
The edge sequence object.
A class used to represent edges in the call graph.
bool isCall() const
Test whether the edge represents a direct call to a function.
Kind
The kind of edge in the graph.
Node & getNode() const
Get the call graph node referenced by this edge.
A node in the call graph.
A RefSCC of the call graph.
SmallVector< RefSCC *, 1 > insertIncomingRefEdge(Node &SourceN, Node &TargetN)
Insert an edge whose source is in a descendant RefSCC and target is in this RefSCC.
bool switchInternalEdgeToCall(Node &SourceN, Node &TargetN, function_ref< void(ArrayRef< SCC * > MergedSCCs)> MergeCB={})
Make an existing internal ref edge into a call edge.
bool isAncestorOf(const RefSCC &RC) const
Test if this RefSCC is an ancestor of RC.
void insertTrivialRefEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new ref edge.
bool isDescendantOf(const RefSCC &RC) const
Test if this RefSCC is a descendant of RC.
void switchOutgoingEdgeToCall(Node &SourceN, Node &TargetN)
Make an existing outgoing ref edge into a call edge.
void replaceNodeFunction(Node &N, Function &NewF)
Directly replace a node's function with a new function.
void insertOutgoingEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Insert an edge whose parent is in this RefSCC and child is in some child RefSCC.
SmallVector< RefSCC *, 1 > removeInternalRefEdges(ArrayRef< std::pair< Node *, Node * > > Edges)
Remove a list of ref edges which are entirely within this RefSCC.
iterator_range< iterator > switchInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge within a single SCC into a ref edge.
void insertInternalRefEdge(Node &SourceN, Node &TargetN)
Insert a ref edge from one node in this RefSCC to another in this RefSCC.
void insertTrivialCallEdge(Node &SourceN, Node &TargetN)
A convenience wrapper around the above to handle trivial cases of inserting a new call edge.
void removeOutgoingEdge(Node &SourceN, Node &TargetN)
Remove an edge whose source is in this RefSCC and target is not.
void switchOutgoingEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing outgoing call edge into a ref edge.
void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge between separate SCCs into a ref edge.
bool isParentOf(const RefSCC &RC) const
Test if this RefSCC is a parent of RC.
An SCC of the call graph.
bool isAncestorOf(const SCC &C) const
Test if this SCC is an ancestor of C.
bool isParentOf(const SCC &C) const
Test if this SCC is a parent of C.
RefSCC & getOuterRefSCC() const
A lazily constructed view of the call graph of a module.
bool isLibFunction(Function &F) const
Test whether a function is a known and defined library function tracked by the call graph.
RefSCC * lookupRefSCC(Node &N) const
Lookup a function's RefSCC in the graph.
void insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK)
Update the call graph after inserting a new edge.
LazyCallGraph(Module &M, function_ref< TargetLibraryInfo &(Function &)> GetTLI)
Construct a graph for the given module.
static void visitReferences(SmallVectorImpl< Constant * > &Worklist, SmallPtrSetImpl< Constant * > &Visited, function_ref< void(Function &)> Callback)
Recursively visits the defined functions whose address is reachable from every constant in the Workli...
void markDeadFunction(Function &F)
Mark a function as dead to be removed later by removeDeadFunctions().
void addSplitFunction(Function &OriginalFunction, Function &NewFunction)
Add a new function split/outlined from an existing function.
void addSplitRefRecursiveFunctions(Function &OriginalFunction, ArrayRef< Function * > NewFunctions)
Add new ref-recursive functions split/outlined from an existing function.
void removeDeadFunctions(ArrayRef< Function * > DeadFs)
Remove dead functions from the call graph.
void removeEdge(Node &SourceN, Node &TargetN)
Update the call graph after deleting an edge.
Node & get(Function &F)
Get a graph node for a given function, scanning it to populate the graph data as necessary.
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
iterator_range< postorder_ref_scc_iterator > postorder_ref_sccs()
LazyCallGraph & operator=(LazyCallGraph &&RHS)
bool invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
void verify()
Verify that every RefSCC is valid.
Node * lookup(const Function &F) const
Lookup a function in the graph which has already been scanned and added.
A Module instance is used to store all the information related to an LLVM module.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
A templated base class for SmallPtrSet which provides the typesafe interface that is common across al...
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
bool contains(ConstPtrType Ptr) const
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
This class consists of common code factored out of the SmallVector class to reduce code duplication b...
reference emplace_back(ArgTypes &&... Args)
iterator erase(const_iterator CI)
void append(ItTy in_start, ItTy in_end)
Add the specified range to the end of the SmallVector.
void swap(SmallVectorImpl &RHS)
void push_back(const T &Elt)
reverse_iterator rbegin()
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Provides information about what library functions are available for the current target.
bool isKnownVectorFunctionInLibrary(StringRef F) const
Check if the function "F" is listed in a library known to LLVM.
bool getLibFunc(StringRef funcName, LibFunc &F) const
Searches for a particular function name.
LLVM Value Representation.
An efficient, type-erasing, non-owning reference to a callable.
A range adaptor for a pair of iterators.
This class implements an extremely fast bulk output stream that can only output to a stream.
This provides a very simple, boring adaptor for a begin and end iterator into a range type.
@ C
The default llvm calling convention, compatible with C.
std::string EscapeString(const std::string &Label)
This is an optimization pass for GlobalISel generic memory operations.
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
bool all_of(R &&range, UnaryPredicate P)
Provide wrappers to std::all_of which take ranges instead of having to pass begin/end explicitly.
auto size(R &&Range, std::enable_if_t< std::is_base_of< std::random_access_iterator_tag, typename std::iterator_traits< decltype(Range.begin())>::iterator_category >::value, void > *=nullptr)
Get the size of a range.
detail::scope_exit< std::decay_t< Callable > > make_scope_exit(Callable &&F)
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
auto reverse(ContainerTy &&C)
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
auto find_if(R &&Range, UnaryPredicate P)
Provide wrappers to std::find_if which take ranges instead of having to pass begin/end explicitly.
Implement std::hash so that hash_code can be used in STL containers.
A special type used by analysis passes to provide an address that identifies that particular analysis...