32#ifdef EXPENSIVE_CHECKS
38#define DEBUG_TYPE "lcg"
40void LazyCallGraph::EdgeSequence::insertEdgeInternal(
Node &TargetN,
42 EdgeIndexMap.try_emplace(&TargetN, Edges.
size());
46void LazyCallGraph::EdgeSequence::setEdgeKind(
Node &TargetN,
Edge::Kind EK) {
47 Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK);
50bool LazyCallGraph::EdgeSequence::removeEdgeInternal(
Node &TargetN) {
51 auto IndexMapI = EdgeIndexMap.find(&TargetN);
52 if (IndexMapI == EdgeIndexMap.end())
55 Edges[IndexMapI->second] = Edge();
56 EdgeIndexMap.erase(IndexMapI);
66 LLVM_DEBUG(
dbgs() <<
" Added callable function: " <<
N.getName() <<
"\n");
71 assert(!Edges &&
"Must not have already populated the edges for this node!");
74 <<
"' to the graph.\n");
76 Edges = EdgeSequence();
100 if (
auto *CB = dyn_cast<CallBase>(&
I))
101 if (
Function *Callee = CB->getCalledFunction())
102 if (!
Callee->isDeclaration())
103 if (Callees.
insert(Callee).second) {
105 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(*Callee),
109 for (
Value *
Op :
I.operand_values())
119 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(
F),
125 for (
auto *
F :
G->LibFunctions)
127 addEdge(Edges->Edges, Edges->EdgeIndexMap,
G->get(*
F),
133void LazyCallGraph::Node::replaceFunction(
Function &NewF) {
134 assert(
F != &NewF &&
"Must not replace a function with itself!");
138#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
140 dbgs() << *
this <<
'\n';
156 LLVM_DEBUG(
dbgs() <<
"Building CG for module: " << M.getModuleIdentifier()
159 if (
F.isDeclaration())
165 LibFunctions.insert(&
F);
167 if (
F.hasLocalLinkage())
173 <<
"' to entry set of the graph.\n");
179 for (
auto &
A : M.aliases()) {
180 if (
A.hasLocalLinkage())
182 if (
Function*
F = dyn_cast<Function>(
A.getAliasee())) {
184 <<
"' with alias '" <<
A.getName()
185 <<
"' to entry set of the graph.\n");
194 if (GV.hasInitializer())
195 if (Visited.
insert(GV.getInitializer()).second)
199 dbgs() <<
" Adding functions referenced by global initializers to the "
202 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap,
get(
F),
223 BPA = std::move(
G.BPA);
224 NodeMap = std::move(
G.NodeMap);
225 EntryEdges = std::move(
G.EntryEdges);
226 SCCBPA = std::move(
G.SCCBPA);
227 SCCMap = std::move(
G.SCCMap);
228 LibFunctions = std::move(
G.LibFunctions);
233#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
235 dbgs() << *
this <<
'\n';
239#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
240void LazyCallGraph::SCC::verify() {
241 assert(OuterRefSCC &&
"Can't have a null RefSCC!");
242 assert(!Nodes.empty() &&
"Can't have an empty SCC!");
244 for (
Node *
N : Nodes) {
245 assert(
N &&
"Can't have a null node!");
246 assert(OuterRefSCC->G->lookupSCC(*
N) ==
this &&
247 "Node does not map to this SCC!");
249 "Must set DFS numbers to -1 when adding a node to an SCC!");
251 "Must set low link to -1 when adding a node to an SCC!");
253 assert(
E.getNode().isPopulated() &&
"Can't have an unpopulated node!");
255#ifdef EXPENSIVE_CHECKS
260 while (!Worklist.
empty()) {
262 if (!Visited.
insert(VisitingNode).second)
264 for (Edge &
E : (*VisitingNode)->calls())
267 for (
Node *NodeToVisit : Nodes) {
269 "Cannot reach all nodes within SCC");
280 for (
Node &
N : *
this)
281 for (
Edge &
E :
N->calls())
282 if (OuterRefSCC->G->lookupSCC(
E.getNode()) == &
C)
290 if (
this == &TargetC)
303 for (
Edge &
E :
N->calls()) {
304 SCC *CalleeC =
G.lookupSCC(
E.getNode());
309 if (CalleeC == &TargetC)
314 if (Visited.
insert(CalleeC).second)
317 }
while (!Worklist.
empty());
325#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
327 dbgs() << *
this <<
'\n';
331#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
332void LazyCallGraph::RefSCC::verify() {
333 assert(
G &&
"Can't have a null graph!");
334 assert(!SCCs.empty() &&
"Can't have an empty SCC!");
338 for (SCC *
C : SCCs) {
339 assert(
C &&
"Can't have a null SCC!");
341 assert(&
C->getOuterRefSCC() ==
this &&
342 "SCC doesn't think it is inside this RefSCC!");
343 bool Inserted = SCCSet.
insert(
C).second;
344 assert(Inserted &&
"Found a duplicate SCC!");
345 auto IndexIt = SCCIndices.find(
C);
346 assert(IndexIt != SCCIndices.end() &&
347 "Found an SCC that doesn't have an index!");
351 for (
auto [
C,
I] : SCCIndices) {
352 assert(
C &&
"Can't have a null SCC in the indices!");
353 assert(SCCSet.
count(
C) &&
"Found an index for an SCC not in the RefSCC!");
354 assert(SCCs[
I] ==
C &&
"Index doesn't point to SCC!");
358 for (
int I = 0,
Size = SCCs.size();
I <
Size; ++
I) {
359 SCC &SourceSCC = *SCCs[
I];
360 for (
Node &
N : SourceSCC)
364 SCC &TargetSCC = *
G->lookupSCC(
E.getNode());
365 if (&TargetSCC.getOuterRefSCC() ==
this) {
366 assert(SCCIndices.find(&TargetSCC)->second <=
I &&
367 "Edge between SCCs violates post-order relationship.");
373#ifdef EXPENSIVE_CHECKS
376 for (SCC *
C : SCCs) {
380 for (
Node *
N : Nodes) {
384 while (!Worklist.
empty()) {
386 if (!Visited.
insert(VisitingNode).second)
388 for (Edge &
E : **VisitingNode)
391 for (
Node *NodeToVisit : Nodes) {
393 "Cannot reach all nodes within RefSCC");
408 if (
G->lookupRefSCC(
E.getNode()) == &RC)
427 for (
SCC &
C : DescendantRC)
430 auto *ChildRC =
G->lookupRefSCC(
E.getNode());
433 if (!ChildRC || !Visited.
insert(ChildRC).second)
437 }
while (!Worklist.
empty());
504template <
typename SCCT,
typename PostorderSequenceT,
typename SCCIndexMapT,
505 typename ComputeSourceConnectedSetCallableT,
506 typename ComputeTargetConnectedSetCallableT>
509 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
510 SCCIndexMapT &SCCIndices,
511 ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
512 ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
513 int SourceIdx = SCCIndices[&SourceSCC];
514 int TargetIdx = SCCIndices[&TargetSCC];
515 assert(SourceIdx < TargetIdx &&
"Cannot have equal indices here!");
520 ComputeSourceConnectedSet(ConnectedSet);
525 auto SourceI = std::stable_partition(
526 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
527 [&ConnectedSet](SCCT *
C) { return !ConnectedSet.count(C); });
528 for (
int I = SourceIdx,
E = TargetIdx + 1;
I <
E; ++
I)
529 SCCIndices.find(SCCs[
I])->second =
I;
533 if (!ConnectedSet.
count(&TargetSCC)) {
534 assert(SourceI > (SCCs.begin() + SourceIdx) &&
535 "Must have moved the source to fix the post-order.");
536 assert(*std::prev(SourceI) == &TargetSCC &&
537 "Last SCC to move should have bene the target.");
541 return make_range(std::prev(SourceI), std::prev(SourceI));
544 assert(SCCs[TargetIdx] == &TargetSCC &&
545 "Should not have moved target if connected!");
546 SourceIdx = SourceI - SCCs.begin();
547 assert(SCCs[SourceIdx] == &SourceSCC &&
548 "Bad updated index computation for the source SCC!");
553 if (SourceIdx + 1 < TargetIdx) {
554 ConnectedSet.
clear();
555 ComputeTargetConnectedSet(ConnectedSet);
559 auto TargetI = std::stable_partition(
560 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
561 [&ConnectedSet](SCCT *
C) { return ConnectedSet.count(C); });
562 for (
int I = SourceIdx + 1,
E = TargetIdx + 1;
I <
E; ++
I)
563 SCCIndices.find(SCCs[
I])->second =
I;
564 TargetIdx = std::prev(TargetI) - SCCs.begin();
565 assert(SCCs[TargetIdx] == &TargetSCC &&
566 "Should always end with the target!");
573 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
579 assert(!(*SourceN)[TargetN].isCall() &&
"Must start with a ref edge!");
582#ifdef EXPENSIVE_CHECKS
587 SCC &SourceSCC = *
G->lookupSCC(SourceN);
588 SCC &TargetSCC = *
G->lookupSCC(TargetN);
592 if (&SourceSCC == &TargetSCC) {
603 int SourceIdx = SCCIndices[&SourceSCC];
604 int TargetIdx = SCCIndices[&TargetSCC];
605 if (TargetIdx < SourceIdx) {
612#ifdef EXPENSIVE_CHECKS
617 ConnectedSet.insert(&SourceSCC);
618 auto IsConnected = [&](
SCC &
C) {
620 for (
Edge &
E :
N->calls())
621 if (ConnectedSet.count(
G->lookupSCC(
E.getNode())))
628 make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
630 ConnectedSet.insert(
C);
638#ifdef EXPENSIVE_CHECKS
643 ConnectedSet.insert(&TargetSCC);
652 SCC &EdgeC = *
G->lookupSCC(
E.getNode());
656 if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
660 if (ConnectedSet.insert(&EdgeC).second)
663 }
while (!Worklist.
empty());
671 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
672 ComputeTargetConnectedSet);
676 MergeCB(
ArrayRef(MergeRange.begin(), MergeRange.end()));
680 if (MergeRange.empty()) {
686#ifdef EXPENSIVE_CHECKS
698 for (
SCC *
C : MergeRange) {
700 "We merge *into* the target and shouldn't process it here!");
702 TargetSCC.Nodes.append(
C->Nodes.begin(),
C->Nodes.end());
704 G->SCCMap[
N] = &TargetSCC;
711 int IndexOffset = MergeRange.end() - MergeRange.begin();
712 auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
714 SCCIndices[
C] -= IndexOffset;
725 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
727#ifdef EXPENSIVE_CHECKS
732 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
733 assert(
G->lookupRefSCC(TargetN) ==
this &&
"Target must be in this RefSCC.");
734 assert(
G->lookupSCC(SourceN) !=
G->lookupSCC(TargetN) &&
735 "Source and Target must be in separate SCCs for this to be trivial!");
738 SourceN->setEdgeKind(TargetN,
Edge::Ref);
743 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
745#ifdef EXPENSIVE_CHECKS
750 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
751 assert(
G->lookupRefSCC(TargetN) ==
this &&
"Target must be in this RefSCC.");
753 SCC &TargetSCC = *
G->lookupSCC(TargetN);
754 assert(
G->lookupSCC(SourceN) == &TargetSCC &&
"Source and Target must be in "
755 "the same SCC to require the "
759 SourceN->setEdgeKind(TargetN,
Edge::Ref);
773 SCC &OldSCC = TargetSCC;
780 Worklist.
swap(OldSCC.Nodes);
781 for (
Node *
N : Worklist) {
782 N->DFSNumber =
N->LowLink = 0;
794 TargetN.DFSNumber = TargetN.LowLink = -1;
795 OldSCC.Nodes.push_back(&TargetN);
796 G->SCCMap[&TargetN] = &OldSCC;
799 for (
Node *RootN : Worklist) {
801 "Cannot begin a new root with a non-empty DFS stack!");
803 "Cannot begin a new root with pending nodes for an SCC!");
806 if (RootN->DFSNumber != 0) {
807 assert(RootN->DFSNumber == -1 &&
808 "Shouldn't have any mid-DFS root nodes!");
812 RootN->DFSNumber = RootN->LowLink = 1;
813 int NextDFSNumber = 2;
818 auto E = (*N)->call_end();
820 Node &ChildN =
I->getNode();
821 if (ChildN.DFSNumber == 0) {
826 assert(!
G->SCCMap.count(&ChildN) &&
827 "Found a node with 0 DFS number but already in an SCC!");
828 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
830 I = (*N)->call_begin();
831 E = (*N)->call_end();
836 if (ChildN.DFSNumber == -1) {
837 if (
G->lookupSCC(ChildN) == &OldSCC) {
842 int OldSize = OldSCC.
size();
843 OldSCC.Nodes.push_back(
N);
844 OldSCC.Nodes.append(PendingSCCStack.
begin(), PendingSCCStack.
end());
845 PendingSCCStack.
clear();
846 while (!DFSStack.
empty())
849 N.DFSNumber =
N.LowLink = -1;
850 G->SCCMap[&
N] = &OldSCC;
864 assert(ChildN.LowLink > 0 &&
"Must have a positive low-link number!");
865 if (ChildN.LowLink <
N->LowLink)
866 N->LowLink = ChildN.LowLink;
881 if (
N->LowLink !=
N->DFSNumber)
886 int RootDFSNumber =
N->DFSNumber;
892 return N->DFSNumber < RootDFSNumber;
897 NewSCCs.
push_back(
G->createSCC(*
this, SCCNodes));
899 N.DFSNumber =
N.LowLink = -1;
900 G->SCCMap[&
N] = NewSCCs.
back();
902 PendingSCCStack.
erase(SCCNodes.end().base(), PendingSCCStack.
end());
903 }
while (!DFSStack.
empty());
910 int OldIdx = SCCIndices[&OldSCC];
911 SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.
begin(), NewSCCs.
end());
916 SCCIndices[SCCs[
Idx]] =
Idx;
919 SCCs.begin() + OldIdx + NewSCCs.
size());
924 assert(!(*SourceN)[TargetN].isCall() &&
"Must start with a ref edge!");
926 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
927 assert(
G->lookupRefSCC(TargetN) !=
this &&
928 "Target must not be in this RefSCC.");
929#ifdef EXPENSIVE_CHECKS
930 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
931 "Target must be a descendant of the Source.");
938#ifdef EXPENSIVE_CHECKS
945 assert((*SourceN)[TargetN].isCall() &&
"Must start with a call edge!");
947 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
948 assert(
G->lookupRefSCC(TargetN) !=
this &&
949 "Target must not be in this RefSCC.");
950#ifdef EXPENSIVE_CHECKS
951 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
952 "Target must be a descendant of the Source.");
957 SourceN->setEdgeKind(TargetN,
Edge::Ref);
959#ifdef EXPENSIVE_CHECKS
966 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
967 assert(
G->lookupRefSCC(TargetN) ==
this &&
"Target must be in this RefSCC.");
969 SourceN->insertEdgeInternal(TargetN,
Edge::Ref);
971#ifdef EXPENSIVE_CHECKS
979 SourceN->insertEdgeInternal(TargetN, EK);
981 assert(
G->lookupRefSCC(SourceN) ==
this &&
"Source must be in this RefSCC.");
983 assert(
G->lookupRefSCC(TargetN) !=
this &&
984 "Target must not be in this RefSCC.");
985#ifdef EXPENSIVE_CHECKS
986 assert(
G->lookupRefSCC(TargetN)->isDescendantOf(*
this) &&
987 "Target must be a descendant of the Source.");
990#ifdef EXPENSIVE_CHECKS
997 assert(
G->lookupRefSCC(TargetN) ==
this &&
"Target must be in this RefSCC.");
998 RefSCC &SourceC = *
G->lookupRefSCC(SourceN);
999 assert(&SourceC !=
this &&
"Source must not be in this RefSCC.");
1000#ifdef EXPENSIVE_CHECKS
1002 "Source must be a descendant of the Target.");
1007#ifdef EXPENSIVE_CHECKS
1012 int SourceIdx =
G->RefSCCIndices[&SourceC];
1013 int TargetIdx =
G->RefSCCIndices[
this];
1014 assert(SourceIdx < TargetIdx &&
1015 "Postorder list doesn't see edge as incoming!");
1025 Set.insert(&SourceC);
1026 auto IsConnected = [&](
RefSCC &RC) {
1030 if (Set.count(
G->lookupRefSCC(
E.getNode())))
1037 G->PostOrderRefSCCs.begin() + TargetIdx + 1))
1038 if (IsConnected(*
C))
1055 RefSCC &EdgeRC = *
G->lookupRefSCC(
E.getNode());
1056 if (
G->getRefSCCIndex(EdgeRC) <= SourceIdx)
1060 if (Set.insert(&EdgeRC).second)
1063 }
while (!Worklist.
empty());
1072 SourceC, *
this,
G->PostOrderRefSCCs,
G->RefSCCIndices,
1073 ComputeSourceConnectedSet, ComputeTargetConnectedSet);
1086 for (
RefSCC *RC : MergeRange) {
1087 assert(RC !=
this &&
"We're merging into the target RefSCC, so it "
1088 "shouldn't be in the range.");
1094 for (
SCC &InnerC : *RC) {
1095 InnerC.OuterRefSCC =
this;
1096 SCCIndices[&InnerC] = SCCIndex++;
1097 for (
Node &
N : InnerC)
1098 G->SCCMap[&
N] = &InnerC;
1103 if (MergedSCCs.
empty())
1104 MergedSCCs = std::move(RC->SCCs);
1106 MergedSCCs.
append(RC->SCCs.begin(), RC->SCCs.end());
1112 for (
SCC &InnerC : *
this)
1113 SCCIndices[&InnerC] = SCCIndex++;
1114 MergedSCCs.
append(SCCs.begin(), SCCs.end());
1115 SCCs = std::move(MergedSCCs);
1118 for (
RefSCC *RC : MergeRange)
1119 G->RefSCCIndices.erase(RC);
1120 int IndexOffset = MergeRange.
end() - MergeRange.
begin();
1122 G->PostOrderRefSCCs.erase(MergeRange.
begin(), MergeRange.
end());
1124 G->RefSCCIndices[RC] -= IndexOffset;
1128 SourceN->insertEdgeInternal(TargetN,
Edge::Ref);
1134 return DeletedRefSCCs;
1138 assert(
G->lookupRefSCC(SourceN) ==
this &&
1139 "The source must be a member of this RefSCC.");
1140 assert(
G->lookupRefSCC(TargetN) !=
this &&
1141 "The target must not be a member of this RefSCC");
1143#ifdef EXPENSIVE_CHECKS
1149 bool Removed = SourceN->removeEdgeInternal(TargetN);
1151 assert(Removed &&
"Target not in the edge set for this caller?");
1160#ifdef EXPENSIVE_CHECKS
1174 for (
Node *TargetN : TargetNs) {
1175 assert(!(*SourceN)[*TargetN].isCall() &&
1176 "Cannot remove a call edge, it must first be made a ref edge");
1178 bool Removed = SourceN->removeEdgeInternal(*TargetN);
1180 assert(Removed &&
"Target not in the edge set for this caller?");
1185 [&](
Node *TargetN) {
return &SourceN == TargetN; }))
1190 SCC &SourceC = *
G->lookupSCC(SourceN);
1192 return G->lookupSCC(*TargetN) == &SourceC;
1202 int PostOrderNumber = 0;
1207 for (
SCC *
C : SCCs) {
1209 N.DFSNumber =
N.LowLink = 0;
1211 Worklist.
append(
C->Nodes.begin(),
C->Nodes.end());
1217 const int NumRefSCCNodes = Worklist.
size();
1223 "Cannot begin a new root with a non-empty DFS stack!");
1225 "Cannot begin a new root with pending nodes for an SCC!");
1229 if (RootN->DFSNumber != 0) {
1230 assert(RootN->DFSNumber == -1 &&
1231 "Shouldn't have any mid-DFS root nodes!");
1235 RootN->DFSNumber = RootN->LowLink = 1;
1236 int NextDFSNumber = 2;
1241 auto E = (*N)->end();
1243 assert(
N->DFSNumber != 0 &&
"We should always assign a DFS number "
1244 "before processing a node.");
1247 Node &ChildN =
I->getNode();
1248 if (ChildN.DFSNumber == 0) {
1255 ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1261 if (ChildN.DFSNumber == -1) {
1270 assert(ChildN.LowLink != 0 &&
1271 "Low-link must not be zero with a non-zero DFS number.");
1272 if (ChildN.LowLink >= 0 && ChildN.LowLink <
N->LowLink)
1273 N->LowLink = ChildN.LowLink;
1283 if (
N->LowLink !=
N->DFSNumber) {
1285 "We never found a viable root for a RefSCC to pop off!");
1290 int RefSCCNumber = PostOrderNumber++;
1291 int RootDFSNumber =
N->DFSNumber;
1297 if (
N->DFSNumber < RootDFSNumber)
1305 N->LowLink = RefSCCNumber;
1308 auto RefSCCNodes =
make_range(StackRI.base(), PendingRefSCCStack.
end());
1314 if (
llvm::size(RefSCCNodes) == NumRefSCCNodes) {
1316 for (
Node *
N : RefSCCNodes)
1324 PendingRefSCCStack.
erase(RefSCCNodes.begin(), PendingRefSCCStack.
end());
1325 }
while (!DFSStack.
empty());
1327 assert(DFSStack.
empty() &&
"Didn't flush the entire DFS stack!");
1328 assert(PendingRefSCCStack.
empty() &&
"Didn't flush all pending nodes!");
1329 }
while (!Worklist.
empty());
1331 assert(PostOrderNumber > 1 &&
1332 "Should never finish the DFS when the existing RefSCC remains valid!");
1338 for (
int I = 0;
I < PostOrderNumber; ++
I)
1339 Result.push_back(
G->createRefSCC(*
G));
1348 int Idx =
G->getRefSCCIndex(*
this);
1349 G->PostOrderRefSCCs.erase(
G->PostOrderRefSCCs.begin() +
Idx);
1350 G->PostOrderRefSCCs.insert(
G->PostOrderRefSCCs.begin() +
Idx, Result.begin(),
1352 for (
int I : seq<int>(
Idx,
G->PostOrderRefSCCs.size()))
1353 G->RefSCCIndices[
G->PostOrderRefSCCs[
I]] =
I;
1355 for (
SCC *
C : SCCs) {
1357 int SCCNumber =
C->begin()->LowLink;
1361 assert(
N.LowLink == SCCNumber &&
1362 "Cannot have different numbers for nodes in the same SCC!");
1366 RefSCC &RC = *Result[SCCNumber];
1367 int SCCIndex = RC.SCCs.size();
1368 RC.SCCs.push_back(
C);
1369 RC.SCCIndices[
C] = SCCIndex;
1370 C->OuterRefSCC = &RC;
1379#ifdef EXPENSIVE_CHECKS
1381 for (
RefSCC *RC : Result)
1391#ifdef EXPENSIVE_CHECKS
1396 SCC &SourceC = *
G->lookupSCC(SourceN);
1397 SCC &TargetC = *
G->lookupSCC(TargetN);
1398 if (&SourceC != &TargetC)
1399 assert(SourceC.isAncestorOf(TargetC) &&
1400 "Call edge is not trivial in the SCC graph!");
1404 auto [Iterator, Inserted] =
1405 SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.
size());
1408 Edge &
E = SourceN->Edges[Iterator->second];
1419#ifdef EXPENSIVE_CHECKS
1423 RefSCC &SourceRC = *
G->lookupRefSCC(SourceN);
1424 RefSCC &TargetRC = *
G->lookupRefSCC(TargetN);
1425 if (&SourceRC != &TargetRC)
1426 assert(SourceRC.isAncestorOf(TargetRC) &&
1427 "Ref edge is not trivial in the RefSCC graph!");
1431 auto [Iterator, Inserted] =
1432 SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.
size());
1445#ifdef EXPENSIVE_CHECKS
1448 assert(
G->lookupRefSCC(
N) ==
this &&
1449 "Cannot replace the function of a node outside this RefSCC.");
1451 assert(
G->NodeMap.find(&NewF) ==
G->NodeMap.end() &&
1452 "Must not have already walked the new function!'");
1460 assert(&OldF != &NewF &&
"Cannot replace a function with itself!");
1462 "Must have moved all uses from the old function to the new!");
1465 N.replaceFunction(NewF);
1468 G->NodeMap.erase(&OldF);
1469 G->NodeMap[&NewF] = &
N;
1472 if (
G->isLibFunction(OldF)) {
1473 G->LibFunctions.remove(&OldF);
1474 G->LibFunctions.insert(&NewF);
1480 "This method cannot be called after SCCs have been formed!");
1482 return SourceN->insertEdgeInternal(TargetN, EK);
1487 "This method cannot be called after SCCs have been formed!");
1489 bool Removed = SourceN->removeEdgeInternal(TargetN);
1491 assert(Removed &&
"Target not in the edge set for this caller?");
1498 "This routine should only be called on trivially dead functions!");
1503 "Must not remove lib functions from the call graph!");
1505 auto NI = NodeMap.find(&
F);
1506 if (NI == NodeMap.end())
1510 Node &
N = *NI->second;
1514 auto CI = SCCMap.find(&
N);
1515 assert(CI != SCCMap.end() &&
1516 "Tried to remove a node without an SCC after DFS walk started!");
1517 SCC &
C = *CI->second;
1518 RefSCC *RC = &
C.getOuterRefSCC();
1523 if (RC->
size() != 1) {
1525 for (
SCC &OtherC : *RC) {
1526 for (
Node &OtherN : OtherC)
1529 for (
Node *OtherN : NodesInRC) {
1530 if ((*OtherN)->lookup(
N)) {
1535 if (!NewRefSCCs.empty())
1536 RC = &
C.getOuterRefSCC();
1542 EntryEdges.removeEdgeInternal(
N);
1548 assert(
C.size() == 1 &&
"Dead functions must be in a singular SCC");
1549 assert(RC->
size() == 1 &&
"Dead functions must be in a singular RefSCC");
1581 if (
auto *CB = dyn_cast<CallBase>(&
I)) {
1582 if (
Function *Callee = CB->getCalledFunction()) {
1583 if (Callee == &NewFunction)
1588 for (
Value *
Op :
I.operand_values()) {
1598 bool FoundNewFunction =
false;
1600 if (&
F == &NewFunction)
1601 FoundNewFunction =
true;
1603 assert(FoundNewFunction &&
"No edge from original function to new function");
1612 "Original function's node should already exist");
1613 Node &OriginalN =
get(OriginalFunction);
1617#ifdef EXPENSIVE_CHECKS
1618 OriginalRC->verify();
1623 "New function's node should not already exist");
1624 Node &NewN = initNode(NewFunction);
1628 SCC *NewC =
nullptr;
1629 for (
Edge &
E : *NewN) {
1630 Node &EN =
E.getNode();
1636 NewC->Nodes.push_back(&NewN);
1642 for (
Edge &
E : *NewN) {
1643 Node &EN =
E.getNode();
1648 RefSCC *NewRC = OriginalRC;
1659 : NewRC->SCCIndices.size();
1660 NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC);
1661 for (
int I = InsertIndex,
Size = NewRC->SCCs.size();
I <
Size; ++
I)
1662 NewRC->SCCIndices[NewRC->SCCs[
I]] =
I;
1673 RefSCC *NewRC = createRefSCC(*
this);
1675 NewRC->SCCIndices[NewC] = 0;
1676 NewRC->SCCs.push_back(NewC);
1677 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1678 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1679 for (
int I = OriginalRCIndex,
Size = PostOrderRefSCCs.size();
I <
Size; ++
I)
1680 RefSCCIndices[PostOrderRefSCCs[
I]] =
I;
1683 SCCMap[&NewN] = NewC;
1685 OriginalN->insertEdgeInternal(NewN, EK);
1690 assert(!NewFunctions.
empty() &&
"Can't add zero functions");
1692 "Original function's node should already exist");
1693 Node &OriginalN =
get(OriginalFunction);
1696#ifdef EXPENSIVE_CHECKS
1697 OriginalRC->verify();
1699 OriginalRC->verify();
1700 for (
Function *NewFunction : NewFunctions)
1705 bool ExistsRefToOriginalRefSCC =
false;
1707 for (
Function *NewFunction : NewFunctions) {
1708 Node &NewN = initNode(*NewFunction);
1714 for (
Edge &
E : *NewN) {
1716 ExistsRefToOriginalRefSCC =
true;
1723 if (ExistsRefToOriginalRefSCC) {
1730 NewRC = createRefSCC(*
this);
1734 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second;
1735 PostOrderRefSCCs.insert(PostOrderRefSCCs.begin() + OriginalRCIndex, NewRC);
1736 for (
int I = OriginalRCIndex,
Size = PostOrderRefSCCs.size();
I <
Size; ++
I)
1737 RefSCCIndices[PostOrderRefSCCs[
I]] =
I;
1740 for (
Function *NewFunction : NewFunctions) {
1741 Node &NewN =
get(*NewFunction);
1750 auto Index = NewRC->SCCIndices.size();
1751 NewRC->SCCIndices[NewC] =
Index;
1752 NewRC->SCCs.push_back(NewC);
1753 SCCMap[&NewN] = NewC;
1757 for (
Function *F1 : NewFunctions) {
1759 "Expected ref edges from original function to every new function");
1761 for (
Function *F2 : NewFunctions) {
1766 "Edges between new functions must be ref edges");
1773 return *
new (MappedN = BPA.Allocate()) Node(*
this,
F);
1776void LazyCallGraph::updateGraphPtrs() {
1779 for (
auto &FunctionNodePair : NodeMap)
1780 FunctionNodePair.second->G =
this;
1782 for (
auto *RC : PostOrderRefSCCs)
1788 N.DFSNumber =
N.LowLink = -1;
1794template <
typename RootsT,
typename GetBeginT,
typename GetEndT,
1795 typename GetNodeT,
typename FormSCCCallbackT>
1796void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1797 GetEndT &&GetEnd, GetNodeT &&GetNode,
1798 FormSCCCallbackT &&FormSCC) {
1799 using EdgeItT =
decltype(GetBegin(std::declval<Node &>()));
1805 for (
Node *RootN : Roots) {
1807 "Cannot begin a new root with a non-empty DFS stack!");
1809 "Cannot begin a new root with pending nodes for an SCC!");
1812 if (RootN->DFSNumber != 0) {
1813 assert(RootN->DFSNumber == -1 &&
1814 "Shouldn't have any mid-DFS root nodes!");
1818 RootN->DFSNumber = RootN->LowLink = 1;
1819 int NextDFSNumber = 2;
1824 auto E = GetEnd(*
N);
1826 Node &ChildN = GetNode(
I);
1827 if (ChildN.DFSNumber == 0) {
1832 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1842 if (ChildN.DFSNumber == -1) {
1848 assert(ChildN.LowLink > 0 &&
"Must have a positive low-link number!");
1849 if (ChildN.LowLink <
N->LowLink)
1850 N->LowLink = ChildN.LowLink;
1862 if (
N->LowLink !=
N->DFSNumber)
1867 int RootDFSNumber =
N->DFSNumber;
1871 PendingSCCStack.
rbegin(),
1873 return N->DFSNumber < RootDFSNumber;
1878 PendingSCCStack.
erase(SCCNodes.end().base(), PendingSCCStack.
end());
1879 }
while (!DFSStack.
empty());
1888void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1889 assert(RC.SCCs.empty() &&
"Already built SCCs!");
1890 assert(RC.SCCIndices.empty() &&
"Already mapped SCC indices!");
1892 for (
Node *
N : Nodes) {
1893 assert(
N->LowLink >= (*Nodes.begin())->LowLink &&
1894 "We cannot have a low link in an SCC lower than its root on the "
1899 N->DFSNumber =
N->LowLink = 0;
1906 Nodes, [](
Node &
N) {
return N->call_begin(); },
1907 [](
Node &
N) {
return N->call_end(); },
1908 [](EdgeSequence::call_iterator
I) ->
Node & {
return I->getNode(); },
1909 [
this, &RC](node_stack_range Nodes) {
1910 RC.SCCs.push_back(createSCC(RC, Nodes));
1911 for (
Node &
N : *RC.SCCs.back()) {
1912 N.DFSNumber =
N.LowLink = -1;
1913 SCCMap[&
N] = RC.SCCs.back();
1918 for (
int I = 0,
Size = RC.SCCs.size();
I <
Size; ++
I)
1919 RC.SCCIndices[RC.SCCs[
I]] =
I;
1923 if (EntryEdges.
empty() || !PostOrderRefSCCs.empty())
1927 assert(RefSCCIndices.empty() &&
"Already mapped RefSCC indices!");
1930 for (
Edge &
E : *
this)
1941 [](
Node &
N) {
return N->end(); },
1944 RefSCC *NewRC = createRefSCC(*
this);
1945 buildSCCs(*NewRC, Nodes);
1950 RefSCCIndices.try_emplace(NewRC, PostOrderRefSCCs.size()).second;
1952 assert(Inserted &&
"Cannot already have this RefSCC in the index map!");
1953 PostOrderRefSCCs.push_back(NewRC);
1954#ifdef EXPENSIVE_CHECKS
1963 while (!Worklist.
empty()) {
1967 if (!
F->isDeclaration())
1974 if (isa<BlockAddress>(
C))
1977 for (
Value *
Op :
C->operand_values())
1978 if (Visited.
insert(cast<Constant>(
Op)).second)
1988 OS <<
" Edges in function: " <<
N.getFunction().getName() <<
"\n";
1990 OS <<
" " << (
E.isCall() ?
"call" :
"ref ") <<
" -> "
1991 <<
E.getFunction().getName() <<
"\n";
1997 OS <<
" SCC with " <<
C.size() <<
" functions:\n";
2000 OS <<
" " <<
N.getFunction().getName() <<
"\n";
2004 OS <<
" RefSCC with " <<
C.size() <<
" call SCCs:\n";
2016 OS <<
"Printing the call graph for module: " << M.getModuleIdentifier()
2037 OS <<
" " <<
Name <<
" -> \""
2040 OS <<
" [style=dashed,label=\"ref\"]";
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
#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
Select target instructions out of generic instructions
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.
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
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 <a particular IR unit>" (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.
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 > removeInternalRefEdge(Node &SourceN, ArrayRef< Node * > TargetNs)
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 removeDeadFunction(Function &F)
Remove a dead function from the call graph (typically to delete it).
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 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.
LazyCallGraph & operator=(LazyCallGraph &&RHS)
bool invalidate(Module &, const PreservedAnalyses &PA, ModuleAnalysisManager::Invalidator &)
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...