Lines Matching defs:RefSCC
218 for (RefSCC &RC : postorder_ref_sccs()) {
251 assert(OuterRefSCC && "Can't have a null RefSCC!");
333 LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
336 LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {
342 void LazyCallGraph::RefSCC::verify() {
352 "SCC doesn't think it is inside this RefSCC!");
363 assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
384 // Verify that all nodes in this RefSCC can reach all other nodes.
403 "Cannot reach all nodes within RefSCC");
410 bool LazyCallGraph::RefSCC::isParentOf(const RefSCC &RC) const {
424 bool LazyCallGraph::RefSCC::isAncestorOf(const RefSCC &RC) const {
428 // For each descendant of this RefSCC, see if one of its children is the
431 SmallVector<const RefSCC *, 4> Worklist;
432 SmallPtrSet<const RefSCC *, 4> Visited;
436 const RefSCC &DescendantRC = *Worklist.pop_back_val();
586 bool LazyCallGraph::RefSCC::switchInternalEdgeToCall(
623 // Check that the RefSCC is still valid before computing this as the
649 // Check that the RefSCC is still valid before computing this as the
664 // Not in this RefSCC...
697 // Before merging, check that the RefSCC remains valid after all the
733 void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN,
742 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
743 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
751 iterator_range<LazyCallGraph::RefSCC::iterator>
752 LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) {
760 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
761 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
932 void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,
936 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
938 "Target must not be in this RefSCC.");
953 void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,
957 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
959 "Target must not be in this RefSCC.");
974 void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,
976 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
977 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
986 void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,
991 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
994 "Target must not be in this RefSCC.");
1005 SmallVector<LazyCallGraph::RefSCC *, 1>
1006 LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {
1007 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
1008 RefSCC &SourceC = *G->lookupRefSCC(SourceN);
1009 assert(&SourceC != this && "Source must not be in this RefSCC.");
1015 SmallVector<RefSCC *, 1> DeletedRefSCCs;
1028 // working backwards from the source using the parent set in each RefSCC,
1034 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1036 auto IsConnected = [&](RefSCC &RC) {
1046 for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1,
1056 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1058 SmallVector<RefSCC *, 4> Worklist;
1061 RefSCC &RC = *Worklist.pop_back_val();
1065 RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode());
1080 iterator_range<SmallVectorImpl<RefSCC *>::iterator> MergeRange =
1085 // Build a set, so we can do fast tests for whether a RefSCC will end up as
1086 // part of the merged RefSCC.
1087 SmallPtrSet<RefSCC *, 16> MergeSet(MergeRange.begin(), MergeRange.end());
1089 // This RefSCC will always be part of that set, so just insert it here.
1096 for (RefSCC *RC : MergeRange) {
1097 assert(RC != this && "We're merging into the target RefSCC, so it "
1128 for (RefSCC *RC : MergeRange)
1133 for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))
1136 // At this point we have a merged RefSCC with a post-order SCCs list, just
1147 void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {
1149 "The source must be a member of this RefSCC.");
1151 "The target must not be a member of this RefSCC");
1164 SmallVector<LazyCallGraph::RefSCC *, 1>
1165 LazyCallGraph::RefSCC::removeInternalRefEdges(
1168 SmallVector<RefSCC *, 1> Result;
1171 // Verify the RefSCC is valid to start with and that either we return an empty
1172 // list of result RefSCCs and this RefSCC remains valid, or we return new
1173 // RefSCCs and this RefSCC is dead.
1176 // If we didn't replace our RefSCC with new ones, check that this one
1195 // were removed there is no RefSCC structure change.
1220 // Track the number of nodes in this RefSCC so that we can quickly recognize
1222 // this RefSCC.
1268 // If this child isn't currently in this RefSCC, no need to process
1284 // stack to eventually get merged into a RefSCC.
1291 "We never found a viable root for a RefSCC to pop off!");
1295 // Otherwise, form a new RefSCC from the top of the pending node stack.
1316 // If we find a cycle containing all nodes originally in this RefSCC then
1328 // We've already marked the nodes internally with the RefSCC number so
1338 "Should never finish the DFS when the existing RefSCC remains valid!");
1340 // Otherwise we create a collection of new RefSCC nodes and build
1348 // sequence before the current RefSCC in that sequence, and then remove the
1372 RefSCC &RC = *Result[SCCNumber];
1387 for (RefSCC *RC : Result)
1395 void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
1424 void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {
1428 // Check that we aren't breaking some invariants of the RefSCC graph.
1429 RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
1430 RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1433 "Ref edge is not trivial in the RefSCC graph!");
1448 void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) {
1455 "Cannot replace the function of a node outside this RefSCC.");
1527 // Group dead functions by the RefSCC they're in.
1528 DenseMap<RefSCC *, SmallVector<Node *, 1>> RCs;
1537 RefSCC *RC = lookupRefSCC(*N);
1557 RefSCC *DeadRC = lookupRefSCC(*DeadN);
1628 RefSCC *OriginalRC = lookupRefSCC(OriginalN);
1647 // it is in the same SCC (and RefSCC) as the original function.
1659 // original function's RefSCC, it is in the same RefSCC as the original
1661 RefSCC *NewRC = OriginalRC;
1683 // We didn't find any edges back to the original function's RefSCC, so the
1684 // new function belongs in a new RefSCC. The new RefSCC goes before the
1685 // original function's RefSCC.
1686 RefSCC *NewRC = createRefSCC(*this);
1707 RefSCC *OriginalRC = lookupRefSCC(OriginalN);
1726 // the original function's RefSCC.
1735 RefSCC *NewRC;
1738 // original function's RefSCC, all new functions will be in the same RefSCC
1742 // Otherwise the new functions are in their own RefSCC.
1744 // The new RefSCC goes before the original function's RefSCC in postorder
1745 // since there are only edges from the original function's RefSCC to the new
1746 // RefSCC.
1761 // SCCs in the RefSCC. Either way, they can go at the back of the postorder
1896 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1901 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1910 // This node will go into the next RefSCC, clear out its DFS and low link
1915 // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1940 assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
1957 RefSCC *NewRC = createRefSCC(*this);
1965 assert(Inserted && "Cannot already have this RefSCC in the index map!");
2016 static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) {
2017 OS << " RefSCC with " << C.size() << " call SCCs:\n";
2036 for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())