Lines Matching full:edge
41 Edge::Kind EK) { in insertEdgeInternal()
46 void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind 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()
106 LazyCallGraph::Edge::Call); in populateSlow()
120 LazyCallGraph::Edge::Ref); in populateSlow()
124 // haven't found an explicit edge). in populateSlow()
128 LazyCallGraph::Edge::Ref); in populateSlow()
174 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), Edge::Ref); in LazyCallGraph()
186 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(*F), Edge::Ref); in LazyCallGraph()
203 LazyCallGraph::Edge::Ref); in LazyCallGraph()
260 for (Edge &E : **N) in verify()
272 for (Edge &E : (*VisitingNode)->calls()) in verify()
289 for (Edge &E : N->calls()) in isParentOf()
311 for (Edge &E : N->calls()) { in isAncestorOf()
369 for (Edge &E : *N) { 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()
437 for (Edge &E : *N) { 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
495 /// constraint after the edge is inserted.
587 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!"); 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()
657 for (Edge &E : *N) { 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()
725 SourceN->setEdgeKind(TargetN, Edge::Call); in switchInternalEdgeToCall()
733 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!"); 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()
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()
796 // below: whenever we build an edge that reaches the target node, we know in switchInternalEdgeToRef()
876 // Move to the next edge. 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()
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()
964 // just flip the edge here. in switchOutgoingEdgeToRef()
965 SourceN->setEdgeKind(TargetN, Edge::Ref); in switchOutgoingEdgeToRef()
977 SourceN->insertEdgeInternal(TargetN, Edge::Ref); in insertInternalRefEdge()
985 Edge::Kind EK) { in insertOutgoingEdge()
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()
1062 for (Edge &E : *N) { in insertIncomingRefEdge()
1075 // a range of any RefSCCs connected into a cycle by inserting this edge. This in insertIncomingRefEdge()
1091 // a connected set with the inserted edge, merge all of them into this SCC. in insertIncomingRefEdge()
1100 // FIXME: We should try to find a way to avoid this (rather expensive) edge in insertIncomingRefEdge()
1135 // connect the nodes to form the new edge. in insertIncomingRefEdge()
1136 SourceN->insertEdgeInternal(TargetN, Edge::Ref); in insertIncomingRefEdge()
1159 assert(Removed && "Target not in the edge set for this caller?"); in removeOutgoingEdge()
1184 "Cannot remove a call edge, it must first be made a ref edge"); in removeInternalRefEdges()
1188 assert(Removed && "Target not in the edge set for this caller?"); in removeInternalRefEdges()
1219 // an important special case of the edge removal not breaking the cycle of in removeInternalRefEdges()
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()
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()
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()
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()
1482 void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) { in insertEdge()
1495 assert(Removed && "Target not in the edge set for this caller?"); in removeEdge()
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()
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()
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()
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()
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()
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()
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()
1769 assert(getEdgeKind(OriginalFunction, *F1) == Edge::Kind::Ref && in addSplitRefRecursiveFunctions()
1863 // Move to the next edge. in buildGenericSCCs()
1941 for (Edge &E : *this) in buildRefSCCs()
2000 for (LazyCallGraph::Edge &E : N.populate()) in printNode()
2047 for (LazyCallGraph::Edge &E : N.populate()) { in printNodeDOT()
2050 if (!E.isCall()) // It is a ref edge. in printNodeDOT()