Lines Matching +full:edge +full:- +full:low
1 //===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
41 Edge::Kind EK) { in insertEdgeInternal()
46 void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) { in setEdgeKind()
47 Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK); in setEdgeKind()
55 Edges[IndexMapI->second] = Edge(); in removeEdgeInternal()
60 static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges, in addEdge()
62 LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) { in addEdge()
67 Edges.emplace_back(LazyCallGraph::Edge(N, EK)); in addEdge()
89 // edge. Even if the function's definition is subject to replacement by in populateSlow()
97 // safety of optimizing a direct call edge. in populateSlow()
101 if (Function *Callee = CB->getCalledFunction()) in populateSlow()
102 if (!Callee->isDeclaration()) in populateSlow()
105 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*Callee), in populateSlow()
106 LazyCallGraph::Edge::Call); in populateSlow()
119 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(F), in populateSlow()
120 LazyCallGraph::Edge::Ref); in populateSlow()
124 // haven't found an explicit edge). in populateSlow()
125 for (auto *F : G->LibFunctions) in populateSlow()
127 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*F), in populateSlow()
128 LazyCallGraph::Edge::Ref); in populateSlow()
174 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), Edge::Ref); in LazyCallGraph()
183 LLVM_DEBUG(dbgs() << " Adding '" << F->getName() in LazyCallGraph()
186 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(*F), Edge::Ref); in LazyCallGraph()
203 LazyCallGraph::Edge::Ref); in LazyCallGraph()
254 assert(OuterRefSCC->G->lookupSCC(*N) == this && in verify()
256 assert(N->DFSNumber == -1 && in verify()
257 "Must set DFS numbers to -1 when adding a node to an SCC!"); in verify()
258 assert(N->LowLink == -1 && in verify()
259 "Must set low link to -1 when adding a node to an SCC!"); in verify()
260 for (Edge &E : **N) in verify()
272 for (Edge &E : (*VisitingNode)->calls()) in verify()
289 for (Edge &E : N->calls()) in isParentOf()
290 if (OuterRefSCC->G->lookupSCC(E.getNode()) == &C) in isParentOf()
301 LazyCallGraph &G = *OuterRefSCC->G; in isAncestorOf()
311 for (Edge &E : N->calls()) { in isAncestorOf()
348 C->verify(); in verify()
349 assert(&C->getOuterRefSCC() == this && in verify()
365 // Check that the SCCs are in fact in post-order. in verify()
369 for (Edge &E : *N) { in verify()
372 SCC &TargetSCC = *G->lookupSCC(E.getNode()); in verify()
374 assert(SCCIndices.find(&TargetSCC)->second <= I && in verify()
375 "Edge between SCCs violates post-order relationship."); in verify()
396 for (Edge &E : **VisitingNode) in verify()
415 for (Edge &E : *N) in isParentOf()
416 if (G->lookupRefSCC(E.getNode()) == &RC) in isParentOf()
437 for (Edge &E : *N) { in isAncestorOf()
438 auto *ChildRC = G->lookupRefSCC(E.getNode()); in isAncestorOf()
451 /// cycle-introducing edge insertion.
459 /// insert a "downward" edge which will require changing the sequence to
462 /// When inserting an edge from an earlier SCC to a later SCC in some postorder
469 /// target SCC in postorder and for each SCC, if it has an edge to an SCC
476 /// and thus the new edge will flow toward the start, we are done.
485 /// including the target SCC and the source SCC. Inserting the edge from
491 /// - Only mutates the SCCs when adding the edge actually changes the SCC
493 /// - Never mutates SCCs which are unaffected by the change.
494 /// - Updates the postorder sequence to correctly satisfy the postorder
495 /// constraint after the edge is inserted.
496 /// - Only reorders SCCs in the closed postorder sequence from the source to
498 /// - Big-O is the number of edges in the closed postorder range of SCCs from
530 // Partition the SCCs in this part of the port-order sequence so only SCCs in updatePostorderSequenceForEdgeInsertion()
537 SCCIndices.find(SCCs[I])->second = I; in updatePostorderSequenceForEdgeInsertion()
540 // post-order and there are no cycles formed. in updatePostorderSequenceForEdgeInsertion()
543 "Must have moved the source to fix the post-order."); in updatePostorderSequenceForEdgeInsertion()
554 SourceIdx = SourceI - SCCs.begin(); in updatePostorderSequenceForEdgeInsertion()
571 SCCIndices.find(SCCs[I])->second = I; in updatePostorderSequenceForEdgeInsertion()
572 TargetIdx = std::prev(TargetI) - SCCs.begin(); in updatePostorderSequenceForEdgeInsertion()
587 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!"); in switchInternalEdgeToCall()
595 SCC &SourceSCC = *G->lookupSCC(SourceN); in switchInternalEdgeToCall()
596 SCC &TargetSCC = *G->lookupSCC(TargetN); in switchInternalEdgeToCall()
601 SourceN->setEdgeKind(TargetN, Edge::Call); in switchInternalEdgeToCall()
606 // insertion of an edge changes the SCC structure in any way. in switchInternalEdgeToCall()
609 // edge is toward the beginning of the postorder sequence because all edges in switchInternalEdgeToCall()
614 SourceN->setEdgeKind(TargetN, Edge::Call); in switchInternalEdgeToCall()
628 for (Edge &E : N->calls()) in switchInternalEdgeToCall()
629 if (ConnectedSet.count(G->lookupSCC(E.getNode()))) in switchInternalEdgeToCall()
657 for (Edge &E : *N) { in switchInternalEdgeToCall()
660 SCC &EdgeC = *G->lookupSCC(E.getNode()); in switchInternalEdgeToCall()
664 if (SCCIndices.find(&EdgeC)->second <= SourceIdx) in switchInternalEdgeToCall()
675 // a range of any SCCs connected into a cycle by inserting this edge. This in switchInternalEdgeToCall()
686 // If the merge range is empty, then adding the edge didn't actually form any in switchInternalEdgeToCall()
690 SourceN->setEdgeKind(TargetN, Edge::Call); in switchInternalEdgeToCall()
704 // reachable from the target, meaning any SCC-wide properties deduced about it in switchInternalEdgeToCall()
710 TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end()); in switchInternalEdgeToCall()
711 for (Node *N : C->Nodes) in switchInternalEdgeToCall()
712 G->SCCMap[N] = &TargetSCC; in switchInternalEdgeToCall()
713 C->clear(); in switchInternalEdgeToCall()
719 int IndexOffset = MergeRange.end() - MergeRange.begin(); in switchInternalEdgeToCall()
722 SCCIndices[C] -= IndexOffset; in switchInternalEdgeToCall()
725 SourceN->setEdgeKind(TargetN, Edge::Call); in switchInternalEdgeToCall()
733 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!"); in switchTrivialInternalEdgeToRef()
740 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); in switchTrivialInternalEdgeToRef()
741 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC."); in switchTrivialInternalEdgeToRef()
742 assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) && in switchTrivialInternalEdgeToRef()
745 // Set the edge kind. in switchTrivialInternalEdgeToRef()
746 SourceN->setEdgeKind(TargetN, Edge::Ref); in switchTrivialInternalEdgeToRef()
751 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!"); in switchInternalEdgeToRef()
758 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); in switchInternalEdgeToRef()
759 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC."); in switchInternalEdgeToRef()
761 SCC &TargetSCC = *G->lookupSCC(TargetN); in switchInternalEdgeToRef()
762 assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in " in switchInternalEdgeToRef()
766 // Set the edge kind. in switchInternalEdgeToRef()
767 SourceN->setEdgeKind(TargetN, Edge::Ref); in switchInternalEdgeToRef()
769 // Otherwise we are removing a call edge from a single SCC. This may break in switchInternalEdgeToRef()
771 // DFS over the nodes within the SCC to form any sub-cycles that remain as in switchInternalEdgeToRef()
790 N->DFSNumber = N->LowLink = 0; in switchInternalEdgeToRef()
791 G->SCCMap.erase(N); in switchInternalEdgeToRef()
795 // a very significant short-cut in the standard Tarjan walk to re-form SCCs in switchInternalEdgeToRef()
796 // below: whenever we build an edge that reaches the target node, we know in switchInternalEdgeToRef()
802 TargetN.DFSNumber = TargetN.LowLink = -1; in switchInternalEdgeToRef()
804 G->SCCMap[&TargetN] = &OldSCC; in switchInternalEdgeToRef()
809 "Cannot begin a new root with a non-empty DFS stack!"); in switchInternalEdgeToRef()
814 if (RootN->DFSNumber != 0) { in switchInternalEdgeToRef()
815 assert(RootN->DFSNumber == -1 && in switchInternalEdgeToRef()
816 "Shouldn't have any mid-DFS root nodes!"); in switchInternalEdgeToRef()
820 RootN->DFSNumber = RootN->LowLink = 1; in switchInternalEdgeToRef()
823 DFSStack.emplace_back(RootN, (*RootN)->call_begin()); in switchInternalEdgeToRef()
826 auto E = (*N)->call_end(); in switchInternalEdgeToRef()
828 Node &ChildN = I->getNode(); in switchInternalEdgeToRef()
834 assert(!G->SCCMap.count(&ChildN) && in switchInternalEdgeToRef()
838 I = (*N)->call_begin(); in switchInternalEdgeToRef()
839 E = (*N)->call_end(); in switchInternalEdgeToRef()
844 if (ChildN.DFSNumber == -1) { in switchInternalEdgeToRef()
845 if (G->lookupSCC(ChildN) == &OldSCC) { in switchInternalEdgeToRef()
857 N.DFSNumber = N.LowLink = -1; in switchInternalEdgeToRef()
858 G->SCCMap[&N] = &OldSCC; in switchInternalEdgeToRef()
865 // couldn't impact the low-link of this parent because it isn't in switchInternalEdgeToRef()
866 // connected, and thus its low-link isn't relevant so skip it. in switchInternalEdgeToRef()
872 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!"); in switchInternalEdgeToRef()
873 if (ChildN.LowLink < N->LowLink) in switchInternalEdgeToRef()
874 N->LowLink = ChildN.LowLink; in switchInternalEdgeToRef()
876 // Move to the next edge. in switchInternalEdgeToRef()
889 if (N->LowLink != N->DFSNumber) in switchInternalEdgeToRef()
894 int RootDFSNumber = N->DFSNumber; in switchInternalEdgeToRef()
900 return N->DFSNumber < RootDFSNumber; in switchInternalEdgeToRef()
905 NewSCCs.push_back(G->createSCC(*this, SCCNodes)); in switchInternalEdgeToRef()
907 N.DFSNumber = N.LowLink = -1; in switchInternalEdgeToRef()
908 G->SCCMap[&N] = NewSCCs.back(); in switchInternalEdgeToRef()
915 // other SCCs we form because it contains the target node of the removed edge in switchInternalEdgeToRef()
932 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!"); in switchOutgoingEdgeToCall()
934 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); in switchOutgoingEdgeToCall()
935 assert(G->lookupRefSCC(TargetN) != this && in switchOutgoingEdgeToCall()
938 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) && in switchOutgoingEdgeToCall()
943 // just flip the edge here. in switchOutgoingEdgeToCall()
944 SourceN->setEdgeKind(TargetN, Edge::Call); in switchOutgoingEdgeToCall()
953 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!"); in switchOutgoingEdgeToRef()
955 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); in switchOutgoingEdgeToRef()
956 assert(G->lookupRefSCC(TargetN) != this && in switchOutgoingEdgeToRef()
959 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) && in switchOutgoingEdgeToRef()
964 // just flip the edge here. in switchOutgoingEdgeToRef()
965 SourceN->setEdgeKind(TargetN, Edge::Ref); in switchOutgoingEdgeToRef()
974 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); in insertInternalRefEdge()
975 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC."); in insertInternalRefEdge()
977 SourceN->insertEdgeInternal(TargetN, Edge::Ref); in insertInternalRefEdge()
985 Edge::Kind EK) { in insertOutgoingEdge()
987 SourceN->insertEdgeInternal(TargetN, EK); in insertOutgoingEdge()
989 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC."); in insertOutgoingEdge()
991 assert(G->lookupRefSCC(TargetN) != this && in insertOutgoingEdge()
994 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) && in insertOutgoingEdge()
1005 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC."); in insertIncomingRefEdge()
1006 RefSCC &SourceC = *G->lookupRefSCC(SourceN); in insertIncomingRefEdge()
1020 int SourceIdx = G->RefSCCIndices[&SourceC]; in insertIncomingRefEdge()
1021 int TargetIdx = G->RefSCCIndices[this]; in insertIncomingRefEdge()
1023 "Postorder list doesn't see edge as incoming!"); in insertIncomingRefEdge()
1028 // advantage of walking the sparser parent edge (in high fan-out graphs) but in insertIncomingRefEdge()
1037 for (Edge &E : *N) in insertIncomingRefEdge()
1038 if (Set.count(G->lookupRefSCC(E.getNode()))) in insertIncomingRefEdge()
1044 for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1, in insertIncomingRefEdge()
1045 G->PostOrderRefSCCs.begin() + TargetIdx + 1)) in insertIncomingRefEdge()
1062 for (Edge &E : *N) { in insertIncomingRefEdge()
1063 RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode()); in insertIncomingRefEdge()
1064 if (G->getRefSCCIndex(EdgeRC) <= SourceIdx) in insertIncomingRefEdge()
1075 // a range of any RefSCCs connected into a cycle by inserting this edge. This in insertIncomingRefEdge()
1080 SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices, in insertIncomingRefEdge()
1091 // a connected set with the inserted edge, merge all of them into this SCC. in insertIncomingRefEdge()
1098 // Walk the inner SCCs to update their up-pointer and walk all the edges to in insertIncomingRefEdge()
1100 // FIXME: We should try to find a way to avoid this (rather expensive) edge in insertIncomingRefEdge()
1106 G->SCCMap[&N] = &InnerC; in insertIncomingRefEdge()
1112 MergedSCCs = std::move(RC->SCCs); in insertIncomingRefEdge()
1114 MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end()); in insertIncomingRefEdge()
1115 RC->SCCs.clear(); in insertIncomingRefEdge()
1127 G->RefSCCIndices.erase(RC); in insertIncomingRefEdge()
1128 int IndexOffset = MergeRange.end() - MergeRange.begin(); in insertIncomingRefEdge()
1130 G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end()); in insertIncomingRefEdge()
1131 for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end())) in insertIncomingRefEdge()
1132 G->RefSCCIndices[RC] -= IndexOffset; in insertIncomingRefEdge()
1134 // At this point we have a merged RefSCC with a post-order SCCs list, just in insertIncomingRefEdge()
1135 // connect the nodes to form the new edge. in insertIncomingRefEdge()
1136 SourceN->insertEdgeInternal(TargetN, Edge::Ref); in insertIncomingRefEdge()
1146 assert(G->lookupRefSCC(SourceN) == this && in removeOutgoingEdge()
1148 assert(G->lookupRefSCC(TargetN) != this && in removeOutgoingEdge()
1157 bool Removed = SourceN->removeEdgeInternal(TargetN); in removeOutgoingEdge()
1159 assert(Removed && "Target not in the edge set for this caller?"); in removeOutgoingEdge()
1165 // We return a list of the resulting *new* RefSCCs in post-order. in removeInternalRefEdges()
1184 "Cannot remove a call edge, it must first be made a ref edge"); in removeInternalRefEdges()
1186 bool Removed = (*SourceN)->removeEdgeInternal(*TargetN); in removeInternalRefEdges()
1188 assert(Removed && "Target not in the edge set for this caller?"); in removeInternalRefEdges()
1196 G->lookupSCC(*E.first) == G->lookupSCC(*E.second); in removeInternalRefEdges()
1201 // for each inner SCC. We store these inside the low-link field of the nodes in removeInternalRefEdges()
1202 // rather than associated with SCCs because this saves a round-trip through in removeInternalRefEdges()
1203 // the node->SCC map and in the common case, SCCs are small. We will verify in removeInternalRefEdges()
1215 Worklist.append(C->Nodes.begin(), C->Nodes.end()); in removeInternalRefEdges()
1219 // an important special case of the edge removal not breaking the cycle of in removeInternalRefEdges()
1227 "Cannot begin a new root with a non-empty DFS stack!"); in removeInternalRefEdges()
1233 if (RootN->DFSNumber != 0) { in removeInternalRefEdges()
1234 assert(RootN->DFSNumber == -1 && in removeInternalRefEdges()
1235 "Shouldn't have any mid-DFS root nodes!"); in removeInternalRefEdges()
1239 RootN->DFSNumber = RootN->LowLink = 1; in removeInternalRefEdges()
1242 DFSStack.emplace_back(RootN, (*RootN)->begin()); in removeInternalRefEdges()
1245 auto E = (*N)->end(); in removeInternalRefEdges()
1247 assert(N->DFSNumber != 0 && "We should always assign a DFS number " in removeInternalRefEdges()
1251 Node &ChildN = I->getNode(); in removeInternalRefEdges()
1261 I = ChildN->begin(); in removeInternalRefEdges()
1262 E = ChildN->end(); in removeInternalRefEdges()
1265 if (ChildN.DFSNumber == -1) { in removeInternalRefEdges()
1273 // Any child not on the stack will have a LowLink of -1. in removeInternalRefEdges()
1275 "Low-link must not be zero with a non-zero DFS number."); in removeInternalRefEdges()
1276 if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink) in removeInternalRefEdges()
1277 N->LowLink = ChildN.LowLink; in removeInternalRefEdges()
1287 if (N->LowLink != N->DFSNumber) { in removeInternalRefEdges()
1295 int RootDFSNumber = N->DFSNumber; in removeInternalRefEdges()
1298 // root DFS number. Update the DFS numbers and low link numbers in the in removeInternalRefEdges()
1299 // process to avoid re-walking this list where possible. in removeInternalRefEdges()
1301 if (N->DFSNumber < RootDFSNumber) in removeInternalRefEdges()
1306 N->DFSNumber = -1; in removeInternalRefEdges()
1307 // Save the post-order number in the lowlink field so that we can use in removeInternalRefEdges()
1309 N->LowLink = RefSCCNumber; in removeInternalRefEdges()
1319 // Clear out the low link field as we won't need it. in removeInternalRefEdges()
1321 N->LowLink = -1; in removeInternalRefEdges()
1339 // a radix-sort style map from postorder number to these new RefSCCs. We then in removeInternalRefEdges()
1343 Result.push_back(G->createRefSCC(*G)); in removeInternalRefEdges()
1352 int Idx = G->getRefSCCIndex(*this); in removeInternalRefEdges()
1353 G->PostOrderRefSCCs.erase(G->PostOrderRefSCCs.begin() + Idx); in removeInternalRefEdges()
1354 G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, Result.begin(), in removeInternalRefEdges()
1356 for (int I : seq<int>(Idx, G->PostOrderRefSCCs.size())) in removeInternalRefEdges()
1357 G->RefSCCIndices[G->PostOrderRefSCCs[I]] = I; in removeInternalRefEdges()
1360 // We store the SCC number in the node's low-link field above. in removeInternalRefEdges()
1361 int SCCNumber = C->begin()->LowLink; in removeInternalRefEdges()
1362 // Clear out all the SCC's node's low-link fields now that we're done in removeInternalRefEdges()
1363 // using them as side-storage. in removeInternalRefEdges()
1367 N.LowLink = -1; in removeInternalRefEdges()
1374 C->OuterRefSCC = &RC; in removeInternalRefEdges()
1386 RC->verify(); in removeInternalRefEdges()
1400 SCC &SourceC = *G->lookupSCC(SourceN); in insertTrivialCallEdge()
1401 SCC &TargetC = *G->lookupSCC(TargetN); in insertTrivialCallEdge()
1404 "Call edge is not trivial in the SCC graph!"); in insertTrivialCallEdge()
1407 // First insert it into the source or find the existing edge. in insertTrivialCallEdge()
1409 SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size()); in insertTrivialCallEdge()
1411 // Already an edge, just update it. in insertTrivialCallEdge()
1412 Edge &E = SourceN->Edges[Iterator->second]; in insertTrivialCallEdge()
1415 E.setKind(Edge::Call); in insertTrivialCallEdge()
1417 // Create the new edge. in insertTrivialCallEdge()
1418 SourceN->Edges.emplace_back(TargetN, Edge::Call); in insertTrivialCallEdge()
1427 RefSCC &SourceRC = *G->lookupRefSCC(SourceN); in insertTrivialRefEdge()
1428 RefSCC &TargetRC = *G->lookupRefSCC(TargetN); in insertTrivialRefEdge()
1431 "Ref edge is not trivial in the RefSCC graph!"); in insertTrivialRefEdge()
1434 // First insert it into the source or find the existing edge. in insertTrivialRefEdge()
1436 SourceN->EdgeIndexMap.try_emplace(&TargetN, SourceN->Edges.size()); in insertTrivialRefEdge()
1439 // Already an edge, we're done. in insertTrivialRefEdge()
1442 // Create the new edge. in insertTrivialRefEdge()
1443 SourceN->Edges.emplace_back(TargetN, Edge::Ref); in insertTrivialRefEdge()
1452 assert(G->lookupRefSCC(N) == this && in replaceNodeFunction()
1455 assert(G->NodeMap.find(&NewF) == G->NodeMap.end() && in replaceNodeFunction()
1472 G->NodeMap.erase(&OldF); in replaceNodeFunction()
1473 G->NodeMap[&NewF] = &N; in replaceNodeFunction()
1476 if (G->isLibFunction(OldF)) { in replaceNodeFunction()
1477 G->LibFunctions.remove(&OldF); in replaceNodeFunction()
1478 G->LibFunctions.insert(&NewF); in replaceNodeFunction()
1482 void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) { in insertEdge()
1486 return SourceN->insertEdgeInternal(TargetN, EK); in insertEdge()
1493 bool Removed = SourceN->removeEdgeInternal(TargetN); in removeEdge()
1495 assert(Removed && "Target not in the edge set for this caller?"); in removeEdge()
1505 // the call graph is in use -- every function definition refers to them. in markDeadFunction()
1512 Node &N = *NI->second; in markDeadFunction()
1515 for (Edge E : *N) { in markDeadFunction()
1517 N->setEdgeKind(E.getNode(), Edge::Ref); in markDeadFunction()
1530 for (Edge &E : **N) { in removeDeadFunctions()
1544 for (Edge &E : **DeadN) { in removeDeadFunctions()
1548 RC->removeOutgoingEdge(*DeadN, E.getNode()); in removeDeadFunctions()
1553 (void)RC->removeInternalRefEdges(InternalEdgesToRemove); in removeDeadFunctions()
1556 assert(DeadRC->size() == 1); in removeDeadFunctions()
1557 assert(DeadRC->begin()->size() == 1); in removeDeadFunctions()
1558 DeadRC->clear(); in removeDeadFunctions()
1559 DeadRC->G = nullptr; in removeDeadFunctions()
1576 // Gets the Edge::Kind from one function to another by looking at the function's
1577 // instructions. Asserts if there is no edge.
1578 // Useful for determining what type of edge should exist between functions when
1579 // the edge hasn't been created yet.
1580 static LazyCallGraph::Edge::Kind getEdgeKind(Function &OriginalFunction, in getEdgeKind()
1583 // function, then there is a ref edge. In debug builds, keep track of in getEdgeKind()
1584 // references to assert that there is actually a ref edge if there is no call in getEdgeKind()
1585 // edge. in getEdgeKind()
1593 if (Function *Callee = CB->getCalledFunction()) { in getEdgeKind()
1595 return LazyCallGraph::Edge::Kind::Call; in getEdgeKind()
1614 assert(FoundNewFunction && "No edge from original function to new function"); in getEdgeKind()
1617 return LazyCallGraph::Edge::Kind::Ref; in getEdgeKind()
1629 OriginalRC->verify(); in addSplitFunction()
1630 auto VerifyOnExit = make_scope_exit([&]() { OriginalRC->verify(); }); in addSplitFunction()
1637 Edge::Kind EK = getEdgeKind(OriginalFunction, NewFunction); in addSplitFunction()
1640 for (Edge &E : *NewN) { in addSplitFunction()
1642 if (EK == Edge::Kind::Call && E.isCall() && lookupSCC(EN) == OriginalC) { in addSplitFunction()
1643 // If the edge to the new function is a call edge and there is a call edge in addSplitFunction()
1647 NewC->Nodes.push_back(&NewN); in addSplitFunction()
1653 for (Edge &E : *NewN) { in addSplitFunction()
1656 // If there is any edge from the new function to any function in the in addSplitFunction()
1663 // SCC, since that case was handled earlier. If the edge from the in addSplitFunction()
1664 // original function to the new function was a call edge, then we need in addSplitFunction()
1669 int InsertIndex = EK == Edge::Kind::Call ? NewRC->SCCIndices[OriginalC] in addSplitFunction()
1670 : NewRC->SCCIndices.size(); in addSplitFunction()
1671 NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC); in addSplitFunction()
1672 for (int I = InsertIndex, Size = NewRC->SCCs.size(); I < Size; ++I) in addSplitFunction()
1673 NewRC->SCCIndices[NewRC->SCCs[I]] = I; in addSplitFunction()
1686 NewRC->SCCIndices[NewC] = 0; in addSplitFunction()
1687 NewRC->SCCs.push_back(NewC); in addSplitFunction()
1688 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second; in addSplitFunction()
1696 OriginalN->insertEdgeInternal(NewN, EK); in addSplitFunction()
1708 OriginalRC->verify(); in addSplitRefRecursiveFunctions()
1710 OriginalRC->verify(); in addSplitRefRecursiveFunctions()
1712 lookupRefSCC(get(*NewFunction))->verify(); in addSplitRefRecursiveFunctions()
1721 OriginalN->insertEdgeInternal(NewN, Edge::Kind::Ref); in addSplitRefRecursiveFunctions()
1723 // Check if there is any edge from any new function back to any function in in addSplitRefRecursiveFunctions()
1725 for (Edge &E : *NewN) { in addSplitRefRecursiveFunctions()
1735 // If there is any edge from any new function to any function in the in addSplitRefRecursiveFunctions()
1745 auto OriginalRCIndex = RefSCCIndices.find(OriginalRC)->second; in addSplitRefRecursiveFunctions()
1754 // have a ref edge to new functions, and no other existing functions can in addSplitRefRecursiveFunctions()
1755 // have references to new functions. Each new function only has a ref edge in addSplitRefRecursiveFunctions()
1761 auto Index = NewRC->SCCIndices.size(); in addSplitRefRecursiveFunctions()
1762 NewRC->SCCIndices[NewC] = Index; in addSplitRefRecursiveFunctions()
1763 NewRC->SCCs.push_back(NewC); in addSplitRefRecursiveFunctions()
1769 assert(getEdgeKind(OriginalFunction, *F1) == Edge::Kind::Ref && in addSplitRefRecursiveFunctions()
1776 assert(!N1->lookup(N2)->isCall() && in addSplitRefRecursiveFunctions()
1791 FunctionNodePair.second->G = this; in updateGraphPtrs()
1794 RC->G = this; in updateGraphPtrs()
1799 N.DFSNumber = N.LowLink = -1; in initNode()
1818 "Cannot begin a new root with a non-empty DFS stack!"); in buildGenericSCCs()
1823 if (RootN->DFSNumber != 0) { in buildGenericSCCs()
1824 assert(RootN->DFSNumber == -1 && in buildGenericSCCs()
1825 "Shouldn't have any mid-DFS root nodes!"); in buildGenericSCCs()
1829 RootN->DFSNumber = RootN->LowLink = 1; in buildGenericSCCs()
1851 // couldn't impact the low-link of this parent because it isn't in buildGenericSCCs()
1852 // connected, and thus its low-link isn't relevant so skip it. in buildGenericSCCs()
1853 if (ChildN.DFSNumber == -1) { in buildGenericSCCs()
1859 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!"); in buildGenericSCCs()
1860 if (ChildN.LowLink < N->LowLink) in buildGenericSCCs()
1861 N->LowLink = ChildN.LowLink; in buildGenericSCCs()
1863 // Move to the next edge. in buildGenericSCCs()
1873 if (N->LowLink != N->DFSNumber) in buildGenericSCCs()
1878 int RootDFSNumber = N->DFSNumber; in buildGenericSCCs()
1884 return N->DFSNumber < RootDFSNumber; in buildGenericSCCs()
1904 assert(N->LowLink >= (*Nodes.begin())->LowLink && in buildSCCs()
1905 "We cannot have a low link in an SCC lower than its root on the " in buildSCCs()
1908 // This node will go into the next RefSCC, clear out its DFS and low link in buildSCCs()
1910 N->DFSNumber = N->LowLink = 0; in buildSCCs()
1917 Nodes, [](Node &N) { return N->call_begin(); }, in buildSCCs()
1918 [](Node &N) { return N->call_end(); }, in buildSCCs()
1919 [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); }, in buildSCCs()
1923 N.DFSNumber = N.LowLink = -1; in buildSCCs()
1935 // RefSCCs are either non-existent or already built! in buildRefSCCs()
1941 for (Edge &E : *this) in buildRefSCCs()
1950 return N->begin(); in buildRefSCCs()
1952 [](Node &N) { return N->end(); }, in buildRefSCCs()
1953 [](EdgeSequence::iterator I) -> Node & { return I->getNode(); }, in buildRefSCCs()
1966 NewRC->verify(); in buildRefSCCs()
1978 if (!F->isDeclaration()) in visitReferences()
1988 for (Value *Op : C->operand_values()) in visitReferences()
2000 for (LazyCallGraph::Edge &E : N.populate()) in printNode()
2001 OS << " " << (E.isCall() ? "call" : "ref ") << " -> " in printNode()
2047 for (LazyCallGraph::Edge &E : N.populate()) { in printNodeDOT()
2048 OS << " " << Name << " -> \"" in printNodeDOT()
2050 if (!E.isCall()) // It is a ref edge. in printNodeDOT()