19 #include "llvm/Config/llvm-config.h"
41 #define DEBUG_TYPE "lcg"
43 void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,
45 EdgeIndexMap.insert({&TargetN, Edges.size()});
49 void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN,
Edge::Kind EK) {
50 Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK);
53 bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) {
54 auto IndexMapI = EdgeIndexMap.find(&TargetN);
55 if (IndexMapI == EdgeIndexMap.end())
58 Edges[IndexMapI->second] = Edge();
59 EdgeIndexMap.erase(IndexMapI);
66 if (!EdgeIndexMap.
insert({&N, Edges.size()}).second)
69 LLVM_DEBUG(
dbgs() <<
" Added callable function: " <<
N.getName() <<
"\n");
74 assert(!Edges &&
"Must not have already populated the edges for this node!");
77 <<
"' to the graph.\n");
79 Edges = EdgeSequence();
103 if (
auto *CB = dyn_cast<CallBase>(&
I))
104 if (
Function *Callee = CB->getCalledFunction())
105 if (!
Callee->isDeclaration())
106 if (Callees.
insert(Callee).second) {
108 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(*Callee),
112 for (
Value *
Op :
I.operand_values())
115 Worklist.push_back(
C);
122 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(
F),
128 for (
auto *
F :
G->LibFunctions)
130 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(*
F),
136 void LazyCallGraph::Node::replaceFunction(
Function &NewF) {
137 assert(
F != &NewF &&
"Must not replace a function with itself!");
141 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
143 dbgs() << *
this <<
'\n';
159 LLVM_DEBUG(
dbgs() <<
"Building CG for module: " <<
M.getModuleIdentifier()
162 if (
F.isDeclaration())
168 LibFunctions.insert(&
F);
170 if (
F.hasLocalLinkage())
176 <<
"' to entry set of the graph.\n");
182 for (
auto &A :
M.aliases()) {
183 if (A.hasLocalLinkage())
185 if (
Function*
F = dyn_cast<Function>(A.getAliasee())) {
187 <<
"' with alias '" << A.getName()
188 <<
"' to entry set of the graph.\n");
197 if (GV.hasInitializer())
198 if (Visited.
insert(GV.getInitializer()).second)
199 Worklist.push_back(GV.getInitializer());
202 dbgs() <<
" Adding functions referenced by global initializers to the "
205 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap,
get(
F),
214 LibFunctions(
std::
move(
G.LibFunctions)) {
238 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
240 dbgs() << *
this <<
'\n';
245 void LazyCallGraph::SCC::verify() {
246 assert(OuterRefSCC &&
"Can't have a null RefSCC!");
247 assert(!Nodes.empty() &&
"Can't have an empty SCC!");
249 for (Node *
N : Nodes) {
250 assert(
N &&
"Can't have a null node!");
251 assert(OuterRefSCC->G->lookupSCC(*
N) ==
this &&
252 "Node does not map to this SCC!");
254 "Must set DFS numbers to -1 when adding a node to an SCC!");
256 "Must set low link to -1 when adding a node to an SCC!");
258 assert(
E.getNode().isPopulated() &&
"Can't have an unpopulated node!");
260 #ifdef EXPENSIVE_CHECKS
264 Worklist.push_back(
N);
265 while (!Worklist.empty()) {
267 if (!Visited.
insert(VisitingNode).second)
269 for (Edge &
E : (*VisitingNode)->calls())
270 Worklist.push_back(&
E.getNode());
272 for (Node *NodeToVisit : Nodes) {
274 "Cannot reach all nodes within SCC");
285 for (
Node &
N : *
this)
286 for (
Edge &
E :
N->calls())
287 if (OuterRefSCC->G->lookupSCC(
E.getNode()) == &
C)
295 if (
this == &TargetC)
308 for (
Edge &
E :
N->calls()) {
309 SCC *CalleeC =
G.lookupSCC(
E.getNode());
314 if (CalleeC == &TargetC)
319 if (Visited.
insert(CalleeC).second)
320 Worklist.push_back(CalleeC);
322 }
while (!Worklist.empty());
330 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
332 dbgs() << *
this <<
'\n';
337 void LazyCallGraph::RefSCC::verify() {
338 assert(
G &&
"Can't have a null graph!");
339 assert(!SCCs.empty() &&
"Can't have an empty SCC!");
343 for (SCC *
C : SCCs) {
344 assert(
C &&
"Can't have a null SCC!");
346 assert(&
C->getOuterRefSCC() ==
this &&
347 "SCC doesn't think it is inside this RefSCC!");
348 bool Inserted = SCCSet.
insert(
C).second;
349 assert(Inserted &&
"Found a duplicate SCC!");
350 auto IndexIt = SCCIndices.find(
C);
351 assert(IndexIt != SCCIndices.end() &&
352 "Found an SCC that doesn't have an index!");
356 for (
auto &SCCIndexPair : SCCIndices) {
357 SCC *
C = SCCIndexPair.first;
358 int i = SCCIndexPair.second;
359 assert(
C &&
"Can't have a null SCC in the indices!");
360 assert(SCCSet.
count(
C) &&
"Found an index for an SCC not in the RefSCC!");
361 assert(SCCs[
i] ==
C &&
"Index doesn't point to SCC!");
365 for (
int i = 0,
Size = SCCs.size();
i <
Size; ++
i) {
366 SCC &SourceSCC = *SCCs[
i];
367 for (Node &
N : SourceSCC)
371 SCC &TargetSCC = *
G->lookupSCC(
E.getNode());
372 if (&TargetSCC.getOuterRefSCC() ==
this) {
373 assert(SCCIndices.find(&TargetSCC)->second <=
i &&
374 "Edge between SCCs violates post-order relationship.");
380 #ifdef EXPENSIVE_CHECKS
383 for (SCC *
C : SCCs) {
387 for (Node *
N : Nodes) {
390 Worklist.push_back(
N);
391 while (!Worklist.empty()) {
393 if (!Visited.
insert(VisitingNode).second)
395 for (Edge &
E : **VisitingNode)
396 Worklist.push_back(&
E.getNode());
398 for (Node *NodeToVisit : Nodes) {
400 "Cannot reach all nodes within RefSCC");
415 if (
G->lookupRefSCC(
E.getNode()) == &RC)
430 Worklist.push_back(
this);
434 for (
SCC &
C : DescendantRC)
437 auto *ChildRC =
G->lookupRefSCC(
E.getNode());
440 if (!ChildRC || !Visited.
insert(ChildRC).second)
442 Worklist.push_back(ChildRC);
444 }
while (!Worklist.empty());
511 template <
typename SCCT,
typename PostorderSequenceT,
typename SCCIndexMapT,
512 typename ComputeSourceConnectedSetCallableT,
513 typename ComputeTargetConnectedSetCallableT>
516 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
517 SCCIndexMapT &SCCIndices,
518 ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
519 ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
520 int SourceIdx = SCCIndices[&SourceSCC];
521 int TargetIdx = SCCIndices[&TargetSCC];
522 assert(SourceIdx < TargetIdx &&
"Cannot have equal indices here!");
527 ComputeSourceConnectedSet(ConnectedSet);
532 auto SourceI = std::stable_partition(
533 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
534 [&ConnectedSet](SCCT *
C) { return !ConnectedSet.count(C); });
535 for (
int i = SourceIdx,
e = TargetIdx + 1;
i <
e; ++
i)
536 SCCIndices.find(SCCs[
i])->second =
i;
540 if (!ConnectedSet.
count(&TargetSCC)) {
541 assert(SourceI > (SCCs.begin() + SourceIdx) &&
542 "Must have moved the source to fix the post-order.");
543 assert(*std::prev(SourceI) == &TargetSCC &&
544 "Last SCC to move should have bene the target.");
548 return make_range(std::prev(SourceI), std::prev(SourceI));
551 assert(SCCs[TargetIdx] == &TargetSCC &&
552 "Should not have moved target if connected!");
553 SourceIdx = SourceI - SCCs.begin();
554 assert(SCCs[SourceIdx] == &SourceSCC &&
555 "Bad updated index computation for the source SCC!");
561 if (SourceIdx + 1 < TargetIdx) {
562 ConnectedSet.
clear();
563 ComputeTargetConnectedSet(ConnectedSet);
567 auto TargetI = std::stable_partition(
568 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
569 [&ConnectedSet](SCCT *
C) { return ConnectedSet.count(C); });
570 for (
int i = SourceIdx + 1,
e = TargetIdx + 1;
i <
e; ++
i)
571 SCCIndices.find(SCCs[
i])->second =
i;
572 TargetIdx = std::prev(TargetI) - SCCs.begin();
573 assert(SCCs[TargetIdx] == &TargetSCC &&
574 "Should always end with the target!");
581 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
588 assert(!(*SourceN)[TargetN].isCall() &&
"Must start with a ref edge!");
591 #ifdef EXPENSIVE_CHECKS
596 SCC &SourceSCC = *
G->lookupSCC(SourceN);
597 SCC &TargetSCC = *
G->lookupSCC(TargetN);
601 if (&SourceSCC == &TargetSCC) {
612 int SourceIdx = SCCIndices[&SourceSCC];
613 int TargetIdx = SCCIndices[&TargetSCC];
614 if (TargetIdx < SourceIdx) {
621 #ifdef EXPENSIVE_CHECKS
626 ConnectedSet.insert(&SourceSCC);
627 auto IsConnected = [&](
SCC &
C) {
629 for (
Edge &
E :
N->calls())
630 if (ConnectedSet.count(
G->lookupSCC(
E.getNode())))
637 make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
639 ConnectedSet.insert(
C);
647 #ifdef EXPENSIVE_CHECKS
652 ConnectedSet.insert(&TargetSCC);
654 Worklist.push_back(&TargetSCC);
661 SCC &EdgeC = *
G->lookupSCC(
E.getNode());
665 if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
669 if (ConnectedSet.insert(&EdgeC).second)
670 Worklist.push_back(&EdgeC);
672 }
while (!Worklist.empty());
680 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
681 ComputeTargetConnectedSet);
685 MergeCB(
makeArrayRef(MergeRange.begin(), MergeRange.end()));
689 if (MergeRange.empty()) {
695 #ifdef EXPENSIVE_CHECKS
707 for (
SCC *
C : MergeRange) {
709 "We merge *into* the target and shouldn't process it here!");
711 TargetSCC.Nodes.append(
C->Nodes.begin(),
C->Nodes.end());
713 G->SCCMap[
N] = &TargetSCC;
715 DeletedSCCs.push_back(
C);
720 int IndexOffset = MergeRange.end() - MergeRange.begin();
721 auto EraseEnd = SCCs.
erase(MergeRange.begin(), MergeRange.end());
723 SCCIndices[
C] -= IndexOffset;
734 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
736 #ifdef EXPENSIVE_CHECKS
741 assert(
G->lookupRefSCC(SourceN) ==
this &&
742 "Source must be in this RefSCC.");
743 assert(
G->lookupRefSCC(TargetN) ==
this &&
744 "Target must be in this RefSCC.");
745 assert(
G->lookupSCC(SourceN) !=
G->lookupSCC(TargetN) &&
746 "Source and Target must be in separate SCCs for this to be trivial!");
749 SourceN->setEdgeKind(TargetN,
Edge::Ref);
754 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
756 #ifdef EXPENSIVE_CHECKS
761 assert(
G->lookupRefSCC(SourceN) ==
this &&
762 "Source must be in this RefSCC.");
763 assert(
G->lookupRefSCC(TargetN) ==
this &&
764 "Target must be in this RefSCC.");
766 SCC &TargetSCC = *
G->lookupSCC(TargetN);
767 assert(
G->lookupSCC(SourceN) == &TargetSCC &&
"Source and Target must be in "
768 "the same SCC to require the "
772 SourceN->setEdgeKind(TargetN,
Edge::Ref);
786 SCC &OldSCC = TargetSCC;
793 Worklist.
swap(OldSCC.Nodes);
794 for (
Node *
N : Worklist) {
795 N->DFSNumber =
N->LowLink = 0;
807 TargetN.DFSNumber = TargetN.LowLink = -1;
808 OldSCC.Nodes.push_back(&TargetN);
809 G->SCCMap[&TargetN] = &OldSCC;
812 for (
Node *RootN : Worklist) {
813 assert(DFSStack.empty() &&
814 "Cannot begin a new root with a non-empty DFS stack!");
815 assert(PendingSCCStack.empty() &&
816 "Cannot begin a new root with pending nodes for an SCC!");
819 if (RootN->DFSNumber != 0) {
820 assert(RootN->DFSNumber == -1 &&
821 "Shouldn't have any mid-DFS root nodes!");
825 RootN->DFSNumber = RootN->LowLink = 1;
826 int NextDFSNumber = 2;
828 DFSStack.push_back({RootN, (*RootN)->call_begin()});
833 auto E = (*N)->call_end();
835 Node &ChildN =
I->getNode();
836 if (ChildN.DFSNumber == 0) {
839 DFSStack.push_back({
N,
I});
841 assert(!
G->SCCMap.count(&ChildN) &&
842 "Found a node with 0 DFS number but already in an SCC!");
843 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
845 I = (*N)->call_begin();
846 E = (*N)->call_end();
851 if (ChildN.DFSNumber == -1) {
852 if (
G->lookupSCC(ChildN) == &OldSCC) {
857 int OldSize = OldSCC.
size();
858 OldSCC.Nodes.push_back(
N);
859 OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());
860 PendingSCCStack.
clear();
861 while (!DFSStack.empty())
864 N.DFSNumber =
N.LowLink = -1;
865 G->SCCMap[&
N] = &OldSCC;
879 assert(ChildN.LowLink > 0 &&
"Must have a positive low-link number!");
880 if (ChildN.LowLink <
N->LowLink)
881 N->LowLink = ChildN.LowLink;
892 PendingSCCStack.push_back(
N);
896 if (
N->LowLink !=
N->DFSNumber)
901 int RootDFSNumber =
N->DFSNumber;
905 PendingSCCStack.rbegin(),
907 return N->DFSNumber < RootDFSNumber;
912 NewSCCs.push_back(
G->createSCC(*
this, SCCNodes));
913 for (
Node &
N : *NewSCCs.back()) {
914 N.DFSNumber =
N.LowLink = -1;
915 G->SCCMap[&
N] = NewSCCs.back();
917 PendingSCCStack.
erase(SCCNodes.end().base(), PendingSCCStack.end());
918 }
while (!DFSStack.empty());
925 int OldIdx = SCCIndices[&OldSCC];
926 SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
930 for (
int Idx = OldIdx,
Size = SCCs.size(); Idx <
Size; ++Idx)
931 SCCIndices[SCCs[Idx]] = Idx;
934 SCCs.begin() + OldIdx + NewSCCs.size());
939 assert(!(*SourceN)[TargetN].isCall() &&
"Must start with a ref edge!");
941 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
942 assert(
G->lookupRefSCC(TargetN) !=
this &&
943 "Target must not be in this RefSCC.");
944 #ifdef EXPENSIVE_CHECKS
945 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
946 "Target must be a descendant of the Source.");
953 #ifdef EXPENSIVE_CHECKS
960 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
962 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
963 assert(
G->lookupRefSCC(TargetN) !=
this &&
964 "Target must not be in this RefSCC.");
965 #ifdef EXPENSIVE_CHECKS
966 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
967 "Target must be a descendant of the Source.");
972 SourceN->setEdgeKind(TargetN,
Edge::Ref);
974 #ifdef EXPENSIVE_CHECKS
981 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
982 assert(
G->lookupRefSCC(TargetN) ==
this &&
"Target must be in this RefSCC.");
984 SourceN->insertEdgeInternal(TargetN,
Edge::Ref);
986 #ifdef EXPENSIVE_CHECKS
994 SourceN->insertEdgeInternal(TargetN, EK);
996 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
998 assert(
G->lookupRefSCC(TargetN) !=
this &&
999 "Target must not be in this RefSCC.");
1000 #ifdef EXPENSIVE_CHECKS
1001 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
1002 "Target must be a descendant of the Source.");
1005 #ifdef EXPENSIVE_CHECKS
1012 assert(
G->lookupRefSCC(TargetN) ==
this &&
"Target must be in this RefSCC.");
1013 RefSCC &SourceC = *
G->lookupRefSCC(SourceN);
1014 assert(&SourceC !=
this &&
"Source must not be in this RefSCC.");
1015 #ifdef EXPENSIVE_CHECKS
1017 "Source must be a descendant of the Target.");
1022 #ifdef EXPENSIVE_CHECKS
1027 int SourceIdx =
G->RefSCCIndices[&SourceC];
1028 int TargetIdx =
G->RefSCCIndices[
this];
1029 assert(SourceIdx < TargetIdx &&
1030 "Postorder list doesn't see edge as incoming!");
1040 Set.insert(&SourceC);
1041 auto IsConnected = [&](
RefSCC &RC) {
1045 if (Set.count(
G->lookupRefSCC(
E.getNode())))
1052 G->PostOrderRefSCCs.begin() + TargetIdx + 1))
1053 if (IsConnected(*
C))
1064 Worklist.push_back(
this);
1070 RefSCC &EdgeRC = *
G->lookupRefSCC(
E.getNode());
1071 if (
G->getRefSCCIndex(EdgeRC) <= SourceIdx)
1075 if (Set.insert(&EdgeRC).second)
1076 Worklist.push_back(&EdgeRC);
1078 }
while (!Worklist.empty());
1087 SourceC, *
this,
G->PostOrderRefSCCs,
G->RefSCCIndices,
1088 ComputeSourceConnectedSet, ComputeTargetConnectedSet);
1101 for (
RefSCC *RC : MergeRange) {
1102 assert(RC !=
this &&
"We're merging into the target RefSCC, so it "
1103 "shouldn't be in the range.");
1109 for (
SCC &InnerC : *RC) {
1110 InnerC.OuterRefSCC =
this;
1111 SCCIndices[&InnerC] = SCCIndex++;
1112 for (
Node &
N : InnerC)
1113 G->SCCMap[&
N] = &InnerC;
1118 if (MergedSCCs.empty())
1121 MergedSCCs.
append(RC->SCCs.begin(), RC->SCCs.end());
1123 DeletedRefSCCs.push_back(RC);
1127 for (
SCC &InnerC : *
this)
1128 SCCIndices[&InnerC] = SCCIndex++;
1129 MergedSCCs.
append(SCCs.begin(), SCCs.end());
1133 for (
RefSCC *RC : MergeRange)
1134 G->RefSCCIndices.erase(RC);
1135 int IndexOffset = MergeRange.end() - MergeRange.begin();
1137 G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());
1139 G->RefSCCIndices[RC] -= IndexOffset;
1143 SourceN->insertEdgeInternal(TargetN,
Edge::Ref);
1149 return DeletedRefSCCs;
1153 assert(
G->lookupRefSCC(SourceN) ==
this &&
1154 "The source must be a member of this RefSCC.");
1155 assert(
G->lookupRefSCC(TargetN) !=
this &&
1156 "The target must not be a member of this RefSCC");
1158 #ifdef EXPENSIVE_CHECKS
1164 bool Removed = SourceN->removeEdgeInternal(TargetN);
1166 assert(Removed &&
"Target not in the edge set for this caller?");
1175 #ifdef EXPENSIVE_CHECKS
1189 for (
Node *TargetN : TargetNs) {
1190 assert(!(*SourceN)[*TargetN].isCall() &&
1191 "Cannot remove a call edge, it must first be made a ref edge");
1193 bool Removed = SourceN->removeEdgeInternal(*TargetN);
1195 assert(Removed &&
"Target not in the edge set for this caller?");
1200 [&](
Node *TargetN) {
return &SourceN == TargetN; }))
1205 SCC &SourceC = *
G->lookupSCC(SourceN);
1207 return G->lookupSCC(*TargetN) == &SourceC;
1217 int PostOrderNumber = 0;
1222 for (
SCC *
C : SCCs) {
1224 N.DFSNumber =
N.LowLink = 0;
1226 Worklist.
append(
C->Nodes.begin(),
C->Nodes.end());
1232 const int NumRefSCCNodes = Worklist.size();
1237 assert(DFSStack.empty() &&
1238 "Cannot begin a new root with a non-empty DFS stack!");
1239 assert(PendingRefSCCStack.empty() &&
1240 "Cannot begin a new root with pending nodes for an SCC!");
1244 if (RootN->DFSNumber != 0) {
1245 assert(RootN->DFSNumber == -1 &&
1246 "Shouldn't have any mid-DFS root nodes!");
1250 RootN->DFSNumber = RootN->LowLink = 1;
1251 int NextDFSNumber = 2;
1253 DFSStack.push_back({RootN, (*RootN)->
begin()});
1258 auto E = (*N)->end();
1260 assert(
N->DFSNumber != 0 &&
"We should always assign a DFS number "
1261 "before processing a node.");
1264 Node &ChildN =
I->getNode();
1265 if (ChildN.DFSNumber == 0) {
1269 DFSStack.push_back({
N,
I});
1272 ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1278 if (ChildN.DFSNumber == -1) {
1287 assert(ChildN.LowLink != 0 &&
1288 "Low-link must not be zero with a non-zero DFS number.");
1289 if (ChildN.LowLink >= 0 && ChildN.LowLink <
N->LowLink)
1290 N->LowLink = ChildN.LowLink;
1296 PendingRefSCCStack.push_back(
N);
1300 if (
N->LowLink !=
N->DFSNumber) {
1301 assert(!DFSStack.empty() &&
1302 "We never found a viable root for a RefSCC to pop off!");
1307 int RefSCCNumber = PostOrderNumber++;
1308 int RootDFSNumber =
N->DFSNumber;
1314 if (
N->DFSNumber < RootDFSNumber)
1322 N->LowLink = RefSCCNumber;
1325 auto RefSCCNodes =
make_range(StackRI.base(), PendingRefSCCStack.end());
1331 if (
llvm::size(RefSCCNodes) == NumRefSCCNodes) {
1333 for (
Node *
N : RefSCCNodes)
1341 PendingRefSCCStack.
erase(RefSCCNodes.begin(), PendingRefSCCStack.end());
1342 }
while (!DFSStack.empty());
1344 assert(DFSStack.empty() &&
"Didn't flush the entire DFS stack!");
1345 assert(PendingRefSCCStack.empty() &&
"Didn't flush all pending nodes!");
1346 }
while (!Worklist.empty());
1348 assert(PostOrderNumber > 1 &&
1349 "Should never finish the DFS when the existing RefSCC remains valid!");
1355 for (
int i = 0;
i < PostOrderNumber; ++
i)
1356 Result.push_back(
G->createRefSCC(*
G));
1365 int Idx =
G->getRefSCCIndex(*
this);
1366 G->PostOrderRefSCCs.erase(
G->PostOrderRefSCCs.begin() + Idx);
1367 G->PostOrderRefSCCs.insert(
G->PostOrderRefSCCs.begin() + Idx, Result.begin(),
1369 for (
int i : seq<int>(Idx,
G->PostOrderRefSCCs.size()))
1370 G->RefSCCIndices[
G->PostOrderRefSCCs[
i]] =
i;
1372 for (
SCC *
C : SCCs) {
1374 int SCCNumber =
C->begin()->LowLink;
1378 assert(
N.LowLink == SCCNumber &&
1379 "Cannot have different numbers for nodes in the same SCC!");
1383 RefSCC &RC = *Result[SCCNumber];
1384 int SCCIndex = RC.SCCs.size();
1385 RC.SCCs.push_back(
C);
1386 RC.SCCIndices[
C] = SCCIndex;
1387 C->OuterRefSCC = &RC;
1396 #ifdef EXPENSIVE_CHECKS
1398 for (
RefSCC *RC : Result)
1408 #ifdef EXPENSIVE_CHECKS
1413 SCC &SourceC = *
G->lookupSCC(SourceN);
1414 SCC &TargetC = *
G->lookupSCC(TargetN);
1415 if (&SourceC != &TargetC)
1416 assert(SourceC.isAncestorOf(TargetC) &&
1417 "Call edge is not trivial in the SCC graph!");
1422 SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1423 if (!InsertResult.second) {
1425 Edge &
E = SourceN->Edges[InsertResult.first->second];
1436 #ifdef EXPENSIVE_CHECKS
1440 RefSCC &SourceRC = *
G->lookupRefSCC(SourceN);
1441 RefSCC &TargetRC = *
G->lookupRefSCC(TargetN);
1442 if (&SourceRC != &TargetRC)
1443 assert(SourceRC.isAncestorOf(TargetRC) &&
1444 "Ref edge is not trivial in the RefSCC graph!");
1449 SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1450 if (!InsertResult.second)
1461 #ifdef EXPENSIVE_CHECKS
1464 assert(
G->lookupRefSCC(
N) ==
this &&
1465 "Cannot replace the function of a node outside this RefSCC.");
1467 assert(
G->NodeMap.find(&NewF) ==
G->NodeMap.end() &&
1468 "Must not have already walked the new function!'");
1476 assert(&OldF != &NewF &&
"Cannot replace a function with itself!");
1478 "Must have moved all uses from the old function to the new!");
1481 N.replaceFunction(NewF);
1484 G->NodeMap.erase(&OldF);
1485 G->NodeMap[&NewF] = &
N;
1490 "This method cannot be called after SCCs have been formed!");
1492 return SourceN->insertEdgeInternal(TargetN, EK);
1497 "This method cannot be called after SCCs have been formed!");
1499 bool Removed = SourceN->removeEdgeInternal(TargetN);
1501 assert(Removed &&
"Target not in the edge set for this caller?");
1508 "This routine should only be called on trivially dead functions!");
1513 "Must not remove lib functions from the call graph!");
1515 auto NI = NodeMap.find(&
F);
1516 if (NI == NodeMap.end())
1520 Node &
N = *NI->second;
1524 EntryEdges.removeEdgeInternal(
N);
1526 if (SCCMap.empty()) {
1535 auto CI = SCCMap.find(&
N);
1536 assert(CI != SCCMap.end() &&
1537 "Tried to remove a node without an SCC after DFS walk started!");
1538 SCC &
C = *CI->second;
1540 RefSCC &RC =
C.getOuterRefSCC();
1545 assert(
C.size() == 1 &&
"Dead functions must be in a singular SCC");
1546 assert(RC.
size() == 1 &&
"Dead functions must be in a singular RefSCC");
1548 auto RCIndexI = RefSCCIndices.find(&RC);
1549 int RCIndex = RCIndexI->second;
1550 PostOrderRefSCCs.erase(PostOrderRefSCCs.begin() + RCIndex);
1551 RefSCCIndices.erase(RCIndexI);
1552 for (
int i = RCIndex,
Size = PostOrderRefSCCs.size();
i <
Size; ++
i)
1553 RefSCCIndices[PostOrderRefSCCs[
i]] =
i;
1584 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
1586 if (
Callee == &NewFunction)
1591 for (
Value *
Op :
I.operand_values()) {
1594 Worklist.push_back(
C);
1601 bool FoundNewFunction =
false;
1603 if (&
F == &NewFunction)
1604 FoundNewFunction =
true;
1606 assert(FoundNewFunction &&
"No edge from original function to new function");
1609 return LazyCallGraph::Edge::Kind::Ref;
1615 "Original function's node should already exist");
1616 Node &OriginalN =
get(OriginalFunction);
1620 #ifdef EXPENSIVE_CHECKS
1621 OriginalRC->verify();
1626 "New function's node should not already exist");
1627 Node &NewN = initNode(NewFunction);
1631 SCC *NewC =
nullptr;
1632 for (
Edge &
E : *NewN) {
1633 Node &EN =
E.getNode();
1639 NewC->Nodes.push_back(&NewN);
1645 for (
Edge &
E : *NewN) {
1646 Node &EN =
E.getNode();
1651 RefSCC *NewRC = OriginalRC;
1662 : NewRC->SCCIndices.size();
1663 NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC);
1664 for (
int I = InsertIndex,
Size = NewRC->SCCs.size();
I <
Size; ++
I)
1665 NewRC->SCCIndices[NewRC->SCCs[
I]] =
I;
1676 RefSCC *NewRC = createRefSCC(*
this);
1678 NewRC->SCCIndices[NewC] = 0;
1679 NewRC->SCCs.push_back(NewC);
1680 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1681 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1682 for (
int I = OriginalRCIndex,
Size = PostOrderRefSCCs.size();
I <
Size; ++
I)
1683 RefSCCIndices[PostOrderRefSCCs[
I]] =
I;
1686 SCCMap[&NewN] = NewC;
1688 OriginalN->insertEdgeInternal(NewN, EK);
1693 assert(!NewFunctions.
empty() &&
"Can't add zero functions");
1695 "Original function's node should already exist");
1696 Node &OriginalN =
get(OriginalFunction);
1699 #ifdef EXPENSIVE_CHECKS
1700 OriginalRC->verify();
1702 OriginalRC->verify();
1703 for (
Function *NewFunction : NewFunctions)
1708 bool ExistsRefToOriginalRefSCC =
false;
1710 for (
Function *NewFunction : NewFunctions) {
1711 Node &NewN = initNode(*NewFunction);
1713 OriginalN->insertEdgeInternal(NewN, Edge::Kind::Ref);
1717 for (
Edge &
E : *NewN) {
1719 ExistsRefToOriginalRefSCC =
true;
1726 if (ExistsRefToOriginalRefSCC) {
1733 NewRC = createRefSCC(*
this);
1737 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1738 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1739 for (
int I = OriginalRCIndex,
Size = PostOrderRefSCCs.size();
I <
Size; ++
I)
1740 RefSCCIndices[PostOrderRefSCCs[
I]] =
I;
1743 for (
Function *NewFunction : NewFunctions) {
1744 Node &NewN =
get(*NewFunction);
1753 auto Index = NewRC->SCCIndices.size();
1754 NewRC->SCCIndices[NewC] =
Index;
1755 NewRC->SCCs.push_back(NewC);
1756 SCCMap[&NewN] = NewC;
1760 for (
Function *F1 : NewFunctions) {
1762 "Expected ref edges from original function to every new function");
1764 for (
Function *F2 : NewFunctions) {
1769 "Edges between new functions must be ref edges");
1776 return *
new (MappedN = BPA.Allocate()) Node(*
this,
F);
1779 void LazyCallGraph::updateGraphPtrs() {
1782 for (
auto &FunctionNodePair : NodeMap)
1783 FunctionNodePair.second->G =
this;
1785 for (
auto *RC : PostOrderRefSCCs)
1791 N.DFSNumber =
N.LowLink = -1;
1797 template <
typename RootsT,
typename GetBeginT,
typename GetEndT,
1798 typename GetNodeT,
typename FormSCCCallbackT>
1799 void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1800 GetEndT &&GetEnd, GetNodeT &&GetNode,
1801 FormSCCCallbackT &&FormSCC) {
1802 using EdgeItT = decltype(GetBegin(std::declval<Node &>()));
1808 for (Node *RootN : Roots) {
1809 assert(DFSStack.empty() &&
1810 "Cannot begin a new root with a non-empty DFS stack!");
1811 assert(PendingSCCStack.empty() &&
1812 "Cannot begin a new root with pending nodes for an SCC!");
1815 if (RootN->DFSNumber != 0) {
1816 assert(RootN->DFSNumber == -1 &&
1817 "Shouldn't have any mid-DFS root nodes!");
1821 RootN->DFSNumber = RootN->LowLink = 1;
1822 int NextDFSNumber = 2;
1824 DFSStack.push_back({RootN, GetBegin(*RootN)});
1829 auto E = GetEnd(*
N);
1831 Node &ChildN = GetNode(
I);
1832 if (ChildN.DFSNumber == 0) {
1835 DFSStack.push_back({
N,
I});
1837 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1847 if (ChildN.DFSNumber == -1) {
1853 assert(ChildN.LowLink > 0 &&
"Must have a positive low-link number!");
1854 if (ChildN.LowLink <
N->LowLink)
1855 N->LowLink = ChildN.LowLink;
1863 PendingSCCStack.push_back(
N);
1867 if (
N->LowLink !=
N->DFSNumber)
1872 int RootDFSNumber =
N->DFSNumber;
1876 PendingSCCStack.rbegin(),
1878 return N->DFSNumber < RootDFSNumber;
1883 PendingSCCStack.
erase(SCCNodes.end().base(), PendingSCCStack.end());
1884 }
while (!DFSStack.empty());
1893 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1894 assert(RC.SCCs.empty() &&
"Already built SCCs!");
1895 assert(RC.SCCIndices.empty() &&
"Already mapped SCC indices!");
1897 for (Node *
N : Nodes) {
1898 assert(
N->LowLink >= (*Nodes.begin())->LowLink &&
1899 "We cannot have a low link in an SCC lower than its root on the "
1904 N->DFSNumber =
N->LowLink = 0;
1911 Nodes, [](Node &
N) {
return N->call_begin(); },
1912 [](Node &
N) {
return N->call_end(); },
1913 [](EdgeSequence::call_iterator
I) -> Node & {
return I->getNode(); },
1914 [
this, &RC](node_stack_range Nodes) {
1915 RC.SCCs.push_back(createSCC(RC, Nodes));
1916 for (Node &
N : *RC.SCCs.back()) {
1917 N.DFSNumber =
N.LowLink = -1;
1918 SCCMap[&
N] = RC.SCCs.back();
1923 for (
int i = 0,
Size = RC.SCCs.size();
i <
Size; ++
i)
1924 RC.SCCIndices[RC.SCCs[
i]] =
i;
1928 if (EntryEdges.
empty() || !PostOrderRefSCCs.empty())
1932 assert(RefSCCIndices.empty() &&
"Already mapped RefSCC indices!");
1935 for (
Edge &
E : *
this)
1936 Roots.push_back(&
E.getNode());
1946 [](
Node &
N) {
return N->end(); },
1949 RefSCC *NewRC = createRefSCC(*
this);
1950 buildSCCs(*NewRC, Nodes);
1955 RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second;
1957 assert(Inserted &&
"Cannot already have this RefSCC in the index map!");
1958 PostOrderRefSCCs.push_back(NewRC);
1959 #ifdef EXPENSIVE_CHECKS
1970 OS <<
" Edges in function: " <<
N.getFunction().getName() <<
"\n";
1972 OS <<
" " << (
E.isCall() ?
"call" :
"ref ") <<
" -> "
1973 <<
E.getFunction().getName() <<
"\n";
1979 OS <<
" SCC with " <<
C.size() <<
" functions:\n";
1982 OS <<
" " <<
N.getFunction().getName() <<
"\n";
1986 OS <<
" RefSCC with " <<
C.size() <<
" call SCCs:\n";
1998 OS <<
"Printing the call graph for module: " <<
M.getModuleIdentifier()
2019 OS <<
" " <<
Name <<
" -> \""
2022 OS <<
" [style=dashed,label=\"ref\"]";