17 #include "llvm/Config/llvm-config.h"
37 #ifdef EXPENSIVE_CHECKS
43 #define DEBUG_TYPE "lcg"
45 void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,
47 EdgeIndexMap.insert({&TargetN, Edges.size()});
51 void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN,
Edge::Kind EK) {
52 Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK);
55 bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) {
56 auto IndexMapI = EdgeIndexMap.find(&TargetN);
57 if (IndexMapI == EdgeIndexMap.end())
60 Edges[IndexMapI->second] = Edge();
61 EdgeIndexMap.erase(IndexMapI);
68 if (!EdgeIndexMap.
insert({&N, Edges.size()}).second)
71 LLVM_DEBUG(
dbgs() <<
" Added callable function: " <<
N.getName() <<
"\n");
76 assert(!Edges &&
"Must not have already populated the edges for this node!");
79 <<
"' to the graph.\n");
81 Edges = EdgeSequence();
105 if (
auto *CB = dyn_cast<CallBase>(&
I))
106 if (
Function *Callee = CB->getCalledFunction())
107 if (!
Callee->isDeclaration())
108 if (Callees.
insert(Callee).second) {
110 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(*Callee),
114 for (
Value *
Op :
I.operand_values())
117 Worklist.push_back(
C);
124 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(
F),
130 for (
auto *
F :
G->LibFunctions)
132 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(*
F),
138 void LazyCallGraph::Node::replaceFunction(
Function &NewF) {
139 assert(
F != &NewF &&
"Must not replace a function with itself!");
143 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
145 dbgs() << *
this <<
'\n';
161 LLVM_DEBUG(
dbgs() <<
"Building CG for module: " <<
M.getModuleIdentifier()
164 if (
F.isDeclaration())
170 LibFunctions.insert(&
F);
172 if (
F.hasLocalLinkage())
178 <<
"' to entry set of the graph.\n");
184 for (
auto &A :
M.aliases()) {
185 if (A.hasLocalLinkage())
187 if (
Function*
F = dyn_cast<Function>(A.getAliasee())) {
189 <<
"' with alias '" << A.getName()
190 <<
"' to entry set of the graph.\n");
199 if (GV.hasInitializer())
200 if (Visited.
insert(GV.getInitializer()).second)
201 Worklist.push_back(GV.getInitializer());
204 dbgs() <<
" Adding functions referenced by global initializers to the "
207 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap,
get(
F),
216 LibFunctions(
std::
move(
G.LibFunctions)) {
239 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
241 dbgs() << *
this <<
'\n';
245 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
246 void LazyCallGraph::SCC::verify() {
247 assert(OuterRefSCC &&
"Can't have a null RefSCC!");
248 assert(!Nodes.empty() &&
"Can't have an empty SCC!");
250 for (Node *
N : Nodes) {
251 assert(
N &&
"Can't have a null node!");
252 assert(OuterRefSCC->G->lookupSCC(*
N) ==
this &&
253 "Node does not map to this SCC!");
255 "Must set DFS numbers to -1 when adding a node to an SCC!");
257 "Must set low link to -1 when adding a node to an SCC!");
259 assert(
E.getNode().isPopulated() &&
"Can't have an unpopulated node!");
261 #ifdef EXPENSIVE_CHECKS
265 Worklist.push_back(
N);
266 while (!Worklist.empty()) {
268 if (!Visited.
insert(VisitingNode).second)
270 for (Edge &
E : (*VisitingNode)->calls())
271 Worklist.push_back(&
E.getNode());
273 for (Node *NodeToVisit : Nodes) {
275 "Cannot reach all nodes within SCC");
286 for (
Node &
N : *
this)
287 for (
Edge &
E :
N->calls())
288 if (OuterRefSCC->G->lookupSCC(
E.getNode()) == &
C)
296 if (
this == &TargetC)
309 for (
Edge &
E :
N->calls()) {
310 SCC *CalleeC =
G.lookupSCC(
E.getNode());
315 if (CalleeC == &TargetC)
320 if (Visited.
insert(CalleeC).second)
321 Worklist.push_back(CalleeC);
323 }
while (!Worklist.empty());
331 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
333 dbgs() << *
this <<
'\n';
337 #if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
338 void LazyCallGraph::RefSCC::verify() {
339 assert(
G &&
"Can't have a null graph!");
340 assert(!SCCs.empty() &&
"Can't have an empty SCC!");
344 for (
SCC *
C : SCCs) {
345 assert(
C &&
"Can't have a null SCC!");
347 assert(&
C->getOuterRefSCC() ==
this &&
348 "SCC doesn't think it is inside this RefSCC!");
349 bool Inserted = SCCSet.
insert(
C).second;
350 assert(Inserted &&
"Found a duplicate SCC!");
351 auto IndexIt = SCCIndices.find(
C);
352 assert(IndexIt != SCCIndices.end() &&
353 "Found an SCC that doesn't have an index!");
357 for (
auto &SCCIndexPair : SCCIndices) {
358 SCC *
C = SCCIndexPair.first;
359 int i = SCCIndexPair.second;
360 assert(
C &&
"Can't have a null SCC in the indices!");
361 assert(SCCSet.
count(
C) &&
"Found an index for an SCC not in the RefSCC!");
362 assert(SCCs[
i] ==
C &&
"Index doesn't point to SCC!");
366 for (
int i = 0, Size = SCCs.size();
i < Size; ++
i) {
367 SCC &SourceSCC = *SCCs[
i];
368 for (Node &
N : SourceSCC)
372 SCC &TargetSCC = *
G->lookupSCC(
E.getNode());
373 if (&TargetSCC.getOuterRefSCC() ==
this) {
374 assert(SCCIndices.find(&TargetSCC)->second <=
i &&
375 "Edge between SCCs violates post-order relationship.");
381 #ifdef EXPENSIVE_CHECKS
384 for (
SCC *
C : SCCs) {
388 for (Node *
N : Nodes) {
391 Worklist.push_back(
N);
392 while (!Worklist.empty()) {
394 if (!Visited.
insert(VisitingNode).second)
396 for (Edge &
E : **VisitingNode)
397 Worklist.push_back(&
E.getNode());
399 for (Node *NodeToVisit : Nodes) {
401 "Cannot reach all nodes within RefSCC");
416 if (
G->lookupRefSCC(
E.getNode()) == &RC)
431 Worklist.push_back(
this);
435 for (
SCC &
C : DescendantRC)
438 auto *ChildRC =
G->lookupRefSCC(
E.getNode());
441 if (!ChildRC || !Visited.
insert(ChildRC).second)
443 Worklist.push_back(ChildRC);
445 }
while (!Worklist.empty());
512 template <
typename SCCT,
typename PostorderSequenceT,
typename SCCIndexMapT,
513 typename ComputeSourceConnectedSetCallableT,
514 typename ComputeTargetConnectedSetCallableT>
517 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
518 SCCIndexMapT &SCCIndices,
519 ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
520 ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
521 int SourceIdx = SCCIndices[&SourceSCC];
522 int TargetIdx = SCCIndices[&TargetSCC];
523 assert(SourceIdx < TargetIdx &&
"Cannot have equal indices here!");
528 ComputeSourceConnectedSet(ConnectedSet);
533 auto SourceI = std::stable_partition(
534 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
535 [&ConnectedSet](SCCT *
C) { return !ConnectedSet.count(C); });
536 for (
int i = SourceIdx,
e = TargetIdx + 1;
i <
e; ++
i)
537 SCCIndices.find(SCCs[
i])->second =
i;
541 if (!ConnectedSet.
count(&TargetSCC)) {
542 assert(SourceI > (SCCs.begin() + SourceIdx) &&
543 "Must have moved the source to fix the post-order.");
544 assert(*std::prev(SourceI) == &TargetSCC &&
545 "Last SCC to move should have bene the target.");
549 return make_range(std::prev(SourceI), std::prev(SourceI));
552 assert(SCCs[TargetIdx] == &TargetSCC &&
553 "Should not have moved target if connected!");
554 SourceIdx = SourceI - SCCs.begin();
555 assert(SCCs[SourceIdx] == &SourceSCC &&
556 "Bad updated index computation for the source SCC!");
562 if (SourceIdx + 1 < TargetIdx) {
563 ConnectedSet.
clear();
564 ComputeTargetConnectedSet(ConnectedSet);
568 auto TargetI = std::stable_partition(
569 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
570 [&ConnectedSet](SCCT *
C) { return ConnectedSet.count(C); });
571 for (
int i = SourceIdx + 1,
e = TargetIdx + 1;
i <
e; ++
i)
572 SCCIndices.find(SCCs[
i])->second =
i;
573 TargetIdx = std::prev(TargetI) - SCCs.begin();
574 assert(SCCs[TargetIdx] == &TargetSCC &&
575 "Should always end with the target!");
582 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
589 assert(!(*SourceN)[TargetN].isCall() &&
"Must start with a ref edge!");
592 #ifdef EXPENSIVE_CHECKS
597 SCC &SourceSCC = *
G->lookupSCC(SourceN);
598 SCC &TargetSCC = *
G->lookupSCC(TargetN);
602 if (&SourceSCC == &TargetSCC) {
613 int SourceIdx = SCCIndices[&SourceSCC];
614 int TargetIdx = SCCIndices[&TargetSCC];
615 if (TargetIdx < SourceIdx) {
622 #ifdef EXPENSIVE_CHECKS
627 ConnectedSet.insert(&SourceSCC);
628 auto IsConnected = [&](
SCC &
C) {
630 for (
Edge &
E :
N->calls())
631 if (ConnectedSet.count(
G->lookupSCC(
E.getNode())))
638 make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
640 ConnectedSet.insert(
C);
648 #ifdef EXPENSIVE_CHECKS
653 ConnectedSet.insert(&TargetSCC);
655 Worklist.push_back(&TargetSCC);
662 SCC &EdgeC = *
G->lookupSCC(
E.getNode());
666 if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
670 if (ConnectedSet.insert(&EdgeC).second)
671 Worklist.push_back(&EdgeC);
673 }
while (!Worklist.empty());
681 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
682 ComputeTargetConnectedSet);
686 MergeCB(
makeArrayRef(MergeRange.begin(), MergeRange.end()));
690 if (MergeRange.empty()) {
696 #ifdef EXPENSIVE_CHECKS
708 for (
SCC *
C : MergeRange) {
710 "We merge *into* the target and shouldn't process it here!");
712 TargetSCC.Nodes.append(
C->Nodes.begin(),
C->Nodes.end());
714 G->SCCMap[
N] = &TargetSCC;
716 DeletedSCCs.push_back(
C);
721 int IndexOffset = MergeRange.end() - MergeRange.begin();
722 auto EraseEnd = SCCs.
erase(MergeRange.begin(), MergeRange.end());
724 SCCIndices[
C] -= IndexOffset;
735 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
737 #ifdef EXPENSIVE_CHECKS
742 assert(
G->lookupRefSCC(SourceN) ==
this &&
743 "Source must be in this RefSCC.");
744 assert(
G->lookupRefSCC(TargetN) ==
this &&
745 "Target must be in this RefSCC.");
746 assert(
G->lookupSCC(SourceN) !=
G->lookupSCC(TargetN) &&
747 "Source and Target must be in separate SCCs for this to be trivial!");
750 SourceN->setEdgeKind(TargetN,
Edge::Ref);
755 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
757 #ifdef EXPENSIVE_CHECKS
762 assert(
G->lookupRefSCC(SourceN) ==
this &&
763 "Source must be in this RefSCC.");
764 assert(
G->lookupRefSCC(TargetN) ==
this &&
765 "Target must be in this RefSCC.");
767 SCC &TargetSCC = *
G->lookupSCC(TargetN);
768 assert(
G->lookupSCC(SourceN) == &TargetSCC &&
"Source and Target must be in "
769 "the same SCC to require the "
773 SourceN->setEdgeKind(TargetN,
Edge::Ref);
787 SCC &OldSCC = TargetSCC;
794 Worklist.
swap(OldSCC.Nodes);
795 for (
Node *
N : Worklist) {
796 N->DFSNumber =
N->LowLink = 0;
808 TargetN.DFSNumber = TargetN.LowLink = -1;
809 OldSCC.Nodes.push_back(&TargetN);
810 G->SCCMap[&TargetN] = &OldSCC;
813 for (
Node *RootN : Worklist) {
814 assert(DFSStack.empty() &&
815 "Cannot begin a new root with a non-empty DFS stack!");
816 assert(PendingSCCStack.empty() &&
817 "Cannot begin a new root with pending nodes for an SCC!");
820 if (RootN->DFSNumber != 0) {
821 assert(RootN->DFSNumber == -1 &&
822 "Shouldn't have any mid-DFS root nodes!");
826 RootN->DFSNumber = RootN->LowLink = 1;
827 int NextDFSNumber = 2;
829 DFSStack.push_back({RootN, (*RootN)->call_begin()});
834 auto E = (*N)->call_end();
836 Node &ChildN =
I->getNode();
837 if (ChildN.DFSNumber == 0) {
840 DFSStack.push_back({
N,
I});
842 assert(!
G->SCCMap.count(&ChildN) &&
843 "Found a node with 0 DFS number but already in an SCC!");
844 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
846 I = (*N)->call_begin();
847 E = (*N)->call_end();
852 if (ChildN.DFSNumber == -1) {
853 if (
G->lookupSCC(ChildN) == &OldSCC) {
858 int OldSize = OldSCC.
size();
859 OldSCC.Nodes.push_back(
N);
860 OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());
861 PendingSCCStack.
clear();
862 while (!DFSStack.empty())
865 N.DFSNumber =
N.LowLink = -1;
866 G->SCCMap[&
N] = &OldSCC;
880 assert(ChildN.LowLink > 0 &&
"Must have a positive low-link number!");
881 if (ChildN.LowLink <
N->LowLink)
882 N->LowLink = ChildN.LowLink;
893 PendingSCCStack.push_back(
N);
897 if (
N->LowLink !=
N->DFSNumber)
902 int RootDFSNumber =
N->DFSNumber;
906 PendingSCCStack.rbegin(),
908 return N->DFSNumber < RootDFSNumber;
913 NewSCCs.push_back(
G->createSCC(*
this, SCCNodes));
914 for (
Node &
N : *NewSCCs.back()) {
915 N.DFSNumber =
N.LowLink = -1;
916 G->SCCMap[&
N] = NewSCCs.back();
918 PendingSCCStack.
erase(SCCNodes.end().base(), PendingSCCStack.end());
919 }
while (!DFSStack.empty());
926 int OldIdx = SCCIndices[&OldSCC];
927 SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
931 for (
int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
932 SCCIndices[SCCs[Idx]] = Idx;
935 SCCs.begin() + OldIdx + NewSCCs.size());
940 assert(!(*SourceN)[TargetN].isCall() &&
"Must start with a ref edge!");
942 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
943 assert(
G->lookupRefSCC(TargetN) !=
this &&
944 "Target must not be in this RefSCC.");
945 #ifdef EXPENSIVE_CHECKS
946 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
947 "Target must be a descendant of the Source.");
954 #ifdef EXPENSIVE_CHECKS
961 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
963 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
964 assert(
G->lookupRefSCC(TargetN) !=
this &&
965 "Target must not be in this RefSCC.");
966 #ifdef EXPENSIVE_CHECKS
967 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
968 "Target must be a descendant of the Source.");
973 SourceN->setEdgeKind(TargetN,
Edge::Ref);
975 #ifdef EXPENSIVE_CHECKS
982 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
983 assert(
G->lookupRefSCC(TargetN) ==
this &&
"Target must be in this RefSCC.");
985 SourceN->insertEdgeInternal(TargetN,
Edge::Ref);
987 #ifdef EXPENSIVE_CHECKS
995 SourceN->insertEdgeInternal(TargetN, EK);
997 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
999 assert(
G->lookupRefSCC(TargetN) !=
this &&
1000 "Target must not be in this RefSCC.");
1001 #ifdef EXPENSIVE_CHECKS
1002 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
1003 "Target must be a descendant of the Source.");
1006 #ifdef EXPENSIVE_CHECKS
1013 assert(
G->lookupRefSCC(TargetN) ==
this &&
"Target must be in this RefSCC.");
1014 RefSCC &SourceC = *
G->lookupRefSCC(SourceN);
1015 assert(&SourceC !=
this &&
"Source must not be in this RefSCC.");
1016 #ifdef EXPENSIVE_CHECKS
1018 "Source must be a descendant of the Target.");
1023 #ifdef EXPENSIVE_CHECKS
1028 int SourceIdx =
G->RefSCCIndices[&SourceC];
1029 int TargetIdx =
G->RefSCCIndices[
this];
1030 assert(SourceIdx < TargetIdx &&
1031 "Postorder list doesn't see edge as incoming!");
1041 Set.insert(&SourceC);
1042 auto IsConnected = [&](
RefSCC &RC) {
1046 if (Set.count(
G->lookupRefSCC(
E.getNode())))
1053 G->PostOrderRefSCCs.begin() + TargetIdx + 1))
1054 if (IsConnected(*
C))
1065 Worklist.push_back(
this);
1071 RefSCC &EdgeRC = *
G->lookupRefSCC(
E.getNode());
1072 if (
G->getRefSCCIndex(EdgeRC) <= SourceIdx)
1076 if (Set.insert(&EdgeRC).second)
1077 Worklist.push_back(&EdgeRC);
1079 }
while (!Worklist.empty());
1088 SourceC, *
this,
G->PostOrderRefSCCs,
G->RefSCCIndices,
1089 ComputeSourceConnectedSet, ComputeTargetConnectedSet);
1102 for (
RefSCC *RC : MergeRange) {
1103 assert(RC !=
this &&
"We're merging into the target RefSCC, so it "
1104 "shouldn't be in the range.");
1110 for (
SCC &InnerC : *RC) {
1111 InnerC.OuterRefSCC =
this;
1112 SCCIndices[&InnerC] = SCCIndex++;
1113 for (
Node &
N : InnerC)
1114 G->SCCMap[&
N] = &InnerC;
1119 if (MergedSCCs.empty())
1122 MergedSCCs.
append(RC->SCCs.begin(), RC->SCCs.end());
1124 DeletedRefSCCs.push_back(RC);
1128 for (
SCC &InnerC : *
this)
1129 SCCIndices[&InnerC] = SCCIndex++;
1130 MergedSCCs.
append(SCCs.begin(), SCCs.end());
1134 for (
RefSCC *RC : MergeRange)
1135 G->RefSCCIndices.erase(RC);
1136 int IndexOffset = MergeRange.end() - MergeRange.begin();
1138 G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());
1140 G->RefSCCIndices[RC] -= IndexOffset;
1144 SourceN->insertEdgeInternal(TargetN,
Edge::Ref);
1150 return DeletedRefSCCs;
1154 assert(
G->lookupRefSCC(SourceN) ==
this &&
1155 "The source must be a member of this RefSCC.");
1156 assert(
G->lookupRefSCC(TargetN) !=
this &&
1157 "The target must not be a member of this RefSCC");
1159 #ifdef EXPENSIVE_CHECKS
1165 bool Removed = SourceN->removeEdgeInternal(TargetN);
1167 assert(Removed &&
"Target not in the edge set for this caller?");
1176 #ifdef EXPENSIVE_CHECKS
1190 for (
Node *TargetN : TargetNs) {
1191 assert(!(*SourceN)[*TargetN].isCall() &&
1192 "Cannot remove a call edge, it must first be made a ref edge");
1194 bool Removed = SourceN->removeEdgeInternal(*TargetN);
1196 assert(Removed &&
"Target not in the edge set for this caller?");
1201 [&](
Node *TargetN) {
return &SourceN == TargetN; }))
1206 SCC &SourceC = *
G->lookupSCC(SourceN);
1208 return G->lookupSCC(*TargetN) == &SourceC;
1218 int PostOrderNumber = 0;
1223 for (
SCC *
C : SCCs) {
1225 N.DFSNumber =
N.LowLink = 0;
1227 Worklist.
append(
C->Nodes.begin(),
C->Nodes.end());
1233 const int NumRefSCCNodes = Worklist.size();
1238 assert(DFSStack.empty() &&
1239 "Cannot begin a new root with a non-empty DFS stack!");
1240 assert(PendingRefSCCStack.empty() &&
1241 "Cannot begin a new root with pending nodes for an SCC!");
1245 if (RootN->DFSNumber != 0) {
1246 assert(RootN->DFSNumber == -1 &&
1247 "Shouldn't have any mid-DFS root nodes!");
1251 RootN->DFSNumber = RootN->LowLink = 1;
1252 int NextDFSNumber = 2;
1254 DFSStack.push_back({RootN, (*RootN)->
begin()});
1259 auto E = (*N)->end();
1261 assert(
N->DFSNumber != 0 &&
"We should always assign a DFS number "
1262 "before processing a node.");
1265 Node &ChildN =
I->getNode();
1266 if (ChildN.DFSNumber == 0) {
1270 DFSStack.push_back({
N,
I});
1273 ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1279 if (ChildN.DFSNumber == -1) {
1288 assert(ChildN.LowLink != 0 &&
1289 "Low-link must not be zero with a non-zero DFS number.");
1290 if (ChildN.LowLink >= 0 && ChildN.LowLink <
N->LowLink)
1291 N->LowLink = ChildN.LowLink;
1297 PendingRefSCCStack.push_back(
N);
1301 if (
N->LowLink !=
N->DFSNumber) {
1302 assert(!DFSStack.empty() &&
1303 "We never found a viable root for a RefSCC to pop off!");
1308 int RefSCCNumber = PostOrderNumber++;
1309 int RootDFSNumber =
N->DFSNumber;
1315 if (
N->DFSNumber < RootDFSNumber)
1323 N->LowLink = RefSCCNumber;
1326 auto RefSCCNodes =
make_range(StackRI.base(), PendingRefSCCStack.end());
1332 if (
llvm::size(RefSCCNodes) == NumRefSCCNodes) {
1334 for (
Node *
N : RefSCCNodes)
1342 PendingRefSCCStack.
erase(RefSCCNodes.begin(), PendingRefSCCStack.end());
1343 }
while (!DFSStack.empty());
1345 assert(DFSStack.empty() &&
"Didn't flush the entire DFS stack!");
1346 assert(PendingRefSCCStack.empty() &&
"Didn't flush all pending nodes!");
1347 }
while (!Worklist.empty());
1349 assert(PostOrderNumber > 1 &&
1350 "Should never finish the DFS when the existing RefSCC remains valid!");
1356 for (
int i = 0;
i < PostOrderNumber; ++
i)
1357 Result.push_back(
G->createRefSCC(*
G));
1366 int Idx =
G->getRefSCCIndex(*
this);
1367 G->PostOrderRefSCCs.erase(
G->PostOrderRefSCCs.begin() + Idx);
1368 G->PostOrderRefSCCs.insert(
G->PostOrderRefSCCs.begin() + Idx, Result.begin(),
1370 for (
int i : seq<int>(Idx,
G->PostOrderRefSCCs.size()))
1371 G->RefSCCIndices[
G->PostOrderRefSCCs[
i]] =
i;
1373 for (
SCC *
C : SCCs) {
1375 int SCCNumber =
C->begin()->LowLink;
1379 assert(
N.LowLink == SCCNumber &&
1380 "Cannot have different numbers for nodes in the same SCC!");
1384 RefSCC &RC = *Result[SCCNumber];
1385 int SCCIndex = RC.SCCs.size();
1386 RC.SCCs.push_back(
C);
1387 RC.SCCIndices[
C] = SCCIndex;
1388 C->OuterRefSCC = &RC;
1397 #ifdef EXPENSIVE_CHECKS
1399 for (
RefSCC *RC : Result)
1409 #ifdef EXPENSIVE_CHECKS
1414 SCC &SourceC = *
G->lookupSCC(SourceN);
1415 SCC &TargetC = *
G->lookupSCC(TargetN);
1416 if (&SourceC != &TargetC)
1417 assert(SourceC.isAncestorOf(TargetC) &&
1418 "Call edge is not trivial in the SCC graph!");
1423 SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1424 if (!InsertResult.second) {
1426 Edge &
E = SourceN->Edges[InsertResult.first->second];
1437 #ifdef EXPENSIVE_CHECKS
1441 RefSCC &SourceRC = *
G->lookupRefSCC(SourceN);
1442 RefSCC &TargetRC = *
G->lookupRefSCC(TargetN);
1443 if (&SourceRC != &TargetRC)
1444 assert(SourceRC.isAncestorOf(TargetRC) &&
1445 "Ref edge is not trivial in the RefSCC graph!");
1450 SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1451 if (!InsertResult.second)
1462 #ifdef EXPENSIVE_CHECKS
1465 assert(
G->lookupRefSCC(
N) ==
this &&
1466 "Cannot replace the function of a node outside this RefSCC.");
1468 assert(
G->NodeMap.find(&NewF) ==
G->NodeMap.end() &&
1469 "Must not have already walked the new function!'");
1477 assert(&OldF != &NewF &&
"Cannot replace a function with itself!");
1479 "Must have moved all uses from the old function to the new!");
1482 N.replaceFunction(NewF);
1485 G->NodeMap.erase(&OldF);
1486 G->NodeMap[&NewF] = &
N;
1491 "This method cannot be called after SCCs have been formed!");
1493 return SourceN->insertEdgeInternal(TargetN, EK);
1498 "This method cannot be called after SCCs have been formed!");
1500 bool Removed = SourceN->removeEdgeInternal(TargetN);
1502 assert(Removed &&
"Target not in the edge set for this caller?");
1509 "This routine should only be called on trivially dead functions!");
1514 "Must not remove lib functions from the call graph!");
1516 auto NI = NodeMap.find(&
F);
1517 if (NI == NodeMap.end())
1521 Node &
N = *NI->second;
1525 EntryEdges.removeEdgeInternal(
N);
1529 auto CI = SCCMap.find(&
N);
1530 assert(CI != SCCMap.end() &&
1531 "Tried to remove a node without an SCC after DFS walk started!");
1532 SCC &
C = *CI->second;
1534 RefSCC &RC =
C.getOuterRefSCC();
1539 assert(
C.size() == 1 &&
"Dead functions must be in a singular SCC");
1540 assert(RC.
size() == 1 &&
"Dead functions must be in a singular RefSCC");
1572 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
1574 if (
Callee == &NewFunction)
1579 for (
Value *
Op :
I.operand_values()) {
1582 Worklist.push_back(
C);
1589 bool FoundNewFunction =
false;
1591 if (&
F == &NewFunction)
1592 FoundNewFunction =
true;
1594 assert(FoundNewFunction &&
"No edge from original function to new function");
1597 return LazyCallGraph::Edge::Kind::Ref;
1603 "Original function's node should already exist");
1604 Node &OriginalN =
get(OriginalFunction);
1608 #ifdef EXPENSIVE_CHECKS
1609 OriginalRC->verify();
1614 "New function's node should not already exist");
1615 Node &NewN = initNode(NewFunction);
1619 SCC *NewC =
nullptr;
1620 for (
Edge &
E : *NewN) {
1621 Node &EN =
E.getNode();
1627 NewC->Nodes.push_back(&NewN);
1633 for (
Edge &
E : *NewN) {
1634 Node &EN =
E.getNode();
1639 RefSCC *NewRC = OriginalRC;
1650 : NewRC->SCCIndices.size();
1651 NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC);
1652 for (
int I = InsertIndex, Size = NewRC->SCCs.size();
I < Size; ++
I)
1653 NewRC->SCCIndices[NewRC->SCCs[
I]] =
I;
1664 RefSCC *NewRC = createRefSCC(*
this);
1666 NewRC->SCCIndices[NewC] = 0;
1667 NewRC->SCCs.push_back(NewC);
1668 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1669 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1670 for (
int I = OriginalRCIndex, Size = PostOrderRefSCCs.size();
I < Size; ++
I)
1671 RefSCCIndices[PostOrderRefSCCs[
I]] =
I;
1674 SCCMap[&NewN] = NewC;
1676 OriginalN->insertEdgeInternal(NewN, EK);
1681 assert(!NewFunctions.
empty() &&
"Can't add zero functions");
1683 "Original function's node should already exist");
1684 Node &OriginalN =
get(OriginalFunction);
1687 #ifdef EXPENSIVE_CHECKS
1688 OriginalRC->verify();
1690 OriginalRC->verify();
1691 for (
Function *NewFunction : NewFunctions)
1696 bool ExistsRefToOriginalRefSCC =
false;
1698 for (
Function *NewFunction : NewFunctions) {
1699 Node &NewN = initNode(*NewFunction);
1701 OriginalN->insertEdgeInternal(NewN, Edge::Kind::Ref);
1705 for (
Edge &
E : *NewN) {
1707 ExistsRefToOriginalRefSCC =
true;
1714 if (ExistsRefToOriginalRefSCC) {
1721 NewRC = createRefSCC(*
this);
1725 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1726 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1727 for (
int I = OriginalRCIndex, Size = PostOrderRefSCCs.size();
I < Size; ++
I)
1728 RefSCCIndices[PostOrderRefSCCs[
I]] =
I;
1731 for (
Function *NewFunction : NewFunctions) {
1732 Node &NewN =
get(*NewFunction);
1741 auto Index = NewRC->SCCIndices.size();
1742 NewRC->SCCIndices[NewC] =
Index;
1743 NewRC->SCCs.push_back(NewC);
1744 SCCMap[&NewN] = NewC;
1748 for (
Function *F1 : NewFunctions) {
1750 "Expected ref edges from original function to every new function");
1752 for (
Function *F2 : NewFunctions) {
1757 "Edges between new functions must be ref edges");
1764 return *
new (MappedN = BPA.Allocate()) Node(*
this,
F);
1767 void LazyCallGraph::updateGraphPtrs() {
1770 for (
auto &FunctionNodePair : NodeMap)
1771 FunctionNodePair.second->G =
this;
1773 for (
auto *RC : PostOrderRefSCCs)
1779 N.DFSNumber =
N.LowLink = -1;
1785 template <
typename RootsT,
typename GetBeginT,
typename GetEndT,
1786 typename GetNodeT,
typename FormSCCCallbackT>
1787 void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1788 GetEndT &&GetEnd, GetNodeT &&GetNode,
1789 FormSCCCallbackT &&FormSCC) {
1790 using EdgeItT = decltype(GetBegin(std::declval<Node &>()));
1796 for (Node *RootN : Roots) {
1797 assert(DFSStack.empty() &&
1798 "Cannot begin a new root with a non-empty DFS stack!");
1799 assert(PendingSCCStack.empty() &&
1800 "Cannot begin a new root with pending nodes for an SCC!");
1803 if (RootN->DFSNumber != 0) {
1804 assert(RootN->DFSNumber == -1 &&
1805 "Shouldn't have any mid-DFS root nodes!");
1809 RootN->DFSNumber = RootN->LowLink = 1;
1810 int NextDFSNumber = 2;
1812 DFSStack.push_back({RootN, GetBegin(*RootN)});
1817 auto E = GetEnd(*
N);
1819 Node &ChildN = GetNode(
I);
1820 if (ChildN.DFSNumber == 0) {
1823 DFSStack.push_back({
N,
I});
1825 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1835 if (ChildN.DFSNumber == -1) {
1841 assert(ChildN.LowLink > 0 &&
"Must have a positive low-link number!");
1842 if (ChildN.LowLink <
N->LowLink)
1843 N->LowLink = ChildN.LowLink;
1851 PendingSCCStack.push_back(
N);
1855 if (
N->LowLink !=
N->DFSNumber)
1860 int RootDFSNumber =
N->DFSNumber;
1864 PendingSCCStack.rbegin(),
1866 return N->DFSNumber < RootDFSNumber;
1871 PendingSCCStack.
erase(SCCNodes.end().base(), PendingSCCStack.end());
1872 }
while (!DFSStack.empty());
1881 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1882 assert(RC.SCCs.empty() &&
"Already built SCCs!");
1883 assert(RC.SCCIndices.empty() &&
"Already mapped SCC indices!");
1885 for (Node *
N : Nodes) {
1886 assert(
N->LowLink >= (*Nodes.begin())->LowLink &&
1887 "We cannot have a low link in an SCC lower than its root on the "
1892 N->DFSNumber =
N->LowLink = 0;
1899 Nodes, [](Node &
N) {
return N->call_begin(); },
1900 [](Node &
N) {
return N->call_end(); },
1901 [](EdgeSequence::call_iterator
I) -> Node & {
return I->getNode(); },
1902 [
this, &RC](node_stack_range Nodes) {
1903 RC.SCCs.push_back(createSCC(RC, Nodes));
1904 for (Node &
N : *RC.SCCs.back()) {
1905 N.DFSNumber =
N.LowLink = -1;
1906 SCCMap[&
N] = RC.SCCs.back();
1911 for (
int i = 0, Size = RC.SCCs.size();
i <
Size; ++
i)
1912 RC.SCCIndices[RC.SCCs[
i]] =
i;
1916 if (EntryEdges.
empty() || !PostOrderRefSCCs.empty())
1920 assert(RefSCCIndices.empty() &&
"Already mapped RefSCC indices!");
1923 for (
Edge &
E : *
this)
1924 Roots.push_back(&
E.getNode());
1934 [](
Node &
N) {
return N->end(); },
1937 RefSCC *NewRC = createRefSCC(*
this);
1938 buildSCCs(*NewRC, Nodes);
1943 RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second;
1945 assert(Inserted &&
"Cannot already have this RefSCC in the index map!");
1946 PostOrderRefSCCs.push_back(NewRC);
1947 #ifdef EXPENSIVE_CHECKS
1956 while (!Worklist.empty()) {
1960 if (!
F->isDeclaration())
1967 if (isa<BlockAddress>(
C))
1970 for (
Value *
Op :
C->operand_values())
1971 if (Visited.
insert(cast<Constant>(
Op)).second)
1972 Worklist.push_back(cast<Constant>(
Op));
1981 OS <<
" Edges in function: " <<
N.getFunction().getName() <<
"\n";
1983 OS <<
" " << (
E.isCall() ?
"call" :
"ref ") <<
" -> "
1984 <<
E.getFunction().getName() <<
"\n";
1990 OS <<
" SCC with " <<
C.size() <<
" functions:\n";
1993 OS <<
" " <<
N.getFunction().getName() <<
"\n";
1997 OS <<
" RefSCC with " <<
C.size() <<
" call SCCs:\n";
2009 OS <<
"Printing the call graph for module: " <<
M.getModuleIdentifier()
2030 OS <<
" " <<
Name <<
" -> \""
2033 OS <<
" [style=dashed,label=\"ref\"]";