Lines Matching defs:RefSCC
216 for (RefSCC &RC : postorder_ref_sccs()) {
249 assert(OuterRefSCC && "Can't have a null RefSCC!");
331 LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
334 LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {
340 void LazyCallGraph::RefSCC::verify() {
350 "SCC doesn't think it is inside this RefSCC!");
361 assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
382 // Verify that all nodes in this RefSCC can reach all other nodes.
401 "Cannot reach all nodes within RefSCC");
408 bool LazyCallGraph::RefSCC::isParentOf(const RefSCC &RC) const {
422 bool LazyCallGraph::RefSCC::isAncestorOf(const RefSCC &RC) const {
426 // For each descendant of this RefSCC, see if one of its children is the
429 SmallVector<const RefSCC *, 4> Worklist;
430 SmallPtrSet<const RefSCC *, 4> Visited;
434 const RefSCC &DescendantRC = *Worklist.pop_back_val();
584 bool LazyCallGraph::RefSCC::switchInternalEdgeToCall(
621 // Check that the RefSCC is still valid before computing this as the
647 // Check that the RefSCC is still valid before computing this as the
662 // Not in this RefSCC...
695 // Before merging, check that the RefSCC remains valid after all the
731 void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN,
740 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
741 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
749 iterator_range<LazyCallGraph::RefSCC::iterator>
750 LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) {
758 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
759 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
930 void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,
934 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
936 "Target must not be in this RefSCC.");
951 void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,
955 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
957 "Target must not be in this RefSCC.");
972 void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,
974 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
975 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
984 void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,
989 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
992 "Target must not be in this RefSCC.");
1003 SmallVector<LazyCallGraph::RefSCC *, 1>
1004 LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {
1005 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
1006 RefSCC &SourceC = *G->lookupRefSCC(SourceN);
1007 assert(&SourceC != this && "Source must not be in this RefSCC.");
1013 SmallVector<RefSCC *, 1> DeletedRefSCCs;
1026 // working backwards from the source using the parent set in each RefSCC,
1032 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1034 auto IsConnected = [&](RefSCC &RC) {
1044 for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1,
1054 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1056 SmallVector<RefSCC *, 4> Worklist;
1059 RefSCC &RC = *Worklist.pop_back_val();
1063 RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode());
1078 iterator_range<SmallVectorImpl<RefSCC *>::iterator> MergeRange =
1083 // Build a set, so we can do fast tests for whether a RefSCC will end up as
1084 // part of the merged RefSCC.
1085 SmallPtrSet<RefSCC *, 16> MergeSet(MergeRange.begin(), MergeRange.end());
1087 // This RefSCC will always be part of that set, so just insert it here.
1094 for (RefSCC *RC : MergeRange) {
1095 assert(RC != this && "We're merging into the target RefSCC, so it "
1126 for (RefSCC *RC : MergeRange)
1131 for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))
1134 // At this point we have a merged RefSCC with a post-order SCCs list, just
1145 void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {
1147 "The source must be a member of this RefSCC.");
1149 "The target must not be a member of this RefSCC");
1162 SmallVector<LazyCallGraph::RefSCC *, 1>
1163 LazyCallGraph::RefSCC::removeInternalRefEdges(
1166 SmallVector<RefSCC *, 1> Result;
1169 // Verify the RefSCC is valid to start with and that either we return an empty
1170 // list of result RefSCCs and this RefSCC remains valid, or we return new
1171 // RefSCCs and this RefSCC is dead.
1174 // If we didn't replace our RefSCC with new ones, check that this one
1193 // were removed there is no RefSCC structure change.
1218 // Track the number of nodes in this RefSCC so that we can quickly recognize
1220 // this RefSCC.
1266 // If this child isn't currently in this RefSCC, no need to process
1282 // stack to eventually get merged into a RefSCC.
1289 "We never found a viable root for a RefSCC to pop off!");
1293 // Otherwise, form a new RefSCC from the top of the pending node stack.
1314 // If we find a cycle containing all nodes originally in this RefSCC then
1326 // We've already marked the nodes internally with the RefSCC number so
1336 "Should never finish the DFS when the existing RefSCC remains valid!");
1338 // Otherwise we create a collection of new RefSCC nodes and build
1346 // sequence before the current RefSCC in that sequence, and then remove the
1370 RefSCC &RC = *Result[SCCNumber];
1385 for (RefSCC *RC : Result)
1393 void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
1422 void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {
1426 // Check that we aren't breaking some invariants of the RefSCC graph.
1427 RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
1428 RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1431 "Ref edge is not trivial in the RefSCC graph!");
1446 void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) {
1453 "Cannot replace the function of a node outside this RefSCC.");
1525 // Group dead functions by the RefSCC they're in.
1526 DenseMap<RefSCC *, SmallVector<Node *, 1>> RCs;
1535 RefSCC *RC = lookupRefSCC(*N);
1555 RefSCC *DeadRC = lookupRefSCC(*DeadN);
1626 RefSCC *OriginalRC = lookupRefSCC(OriginalN);
1645 // it is in the same SCC (and RefSCC) as the original function.
1657 // original function's RefSCC, it is in the same RefSCC as the original
1659 RefSCC *NewRC = OriginalRC;
1681 // We didn't find any edges back to the original function's RefSCC, so the
1682 // new function belongs in a new RefSCC. The new RefSCC goes before the
1683 // original function's RefSCC.
1684 RefSCC *NewRC = createRefSCC(*this);
1705 RefSCC *OriginalRC = lookupRefSCC(OriginalN);
1724 // the original function's RefSCC.
1733 RefSCC *NewRC;
1736 // original function's RefSCC, all new functions will be in the same RefSCC
1740 // Otherwise the new functions are in their own RefSCC.
1742 // The new RefSCC goes before the original function's RefSCC in postorder
1743 // since there are only edges from the original function's RefSCC to the new
1744 // RefSCC.
1759 // SCCs in the RefSCC. Either way, they can go at the back of the postorder
1894 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1899 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1908 // This node will go into the next RefSCC, clear out its DFS and low link
1913 // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1938 assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
1955 RefSCC *NewRC = createRefSCC(*this);
1963 assert(Inserted && "Cannot already have this RefSCC in the index map!");
2014 static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) {
2015 OS << " RefSCC with " << C.size() << " call SCCs:\n";
2034 for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())