Lines Matching refs:SCC
159 void LazyCallGraph::SCC::insert(Node &N) {
165 bool LazyCallGraph::SCC::isDescendantOf(const SCC &C) const {
166 // Walk up the parents of this SCC and verify that we eventually find C.
167 SmallVector<const SCC *, 4> AncestorWorklist;
170 const SCC *AncestorC = AncestorWorklist.pop_back_val();
173 for (const SCC *ParentC : AncestorC->ParentSCCs)
180 void LazyCallGraph::SCC::insertIntraSCCEdge(Node &CallerN, Node &CalleeN) {
184 assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
185 assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
187 // Nothing changes about this SCC or any other.
190 void LazyCallGraph::SCC::insertOutgoingEdge(Node &CallerN, Node &CalleeN) {
194 assert(G->SCCMap.lookup(&CallerN) == this && "Caller must be in this SCC.");
196 SCC &CalleeC = *G->SCCMap.lookup(&CalleeN);
197 assert(&CalleeC != this && "Callee must not be in this SCC.");
201 // The only change required is to add this SCC to the parent set of the callee.
205 SmallVector<LazyCallGraph::SCC *, 1>
206 LazyCallGraph::SCC::insertIncomingEdge(Node &CallerN, Node &CalleeN) {
210 assert(G->SCCMap.lookup(&CalleeN) == this && "Callee must be in this SCC.");
212 SCC &CallerC = *G->SCCMap.lookup(&CallerN);
213 assert(&CallerC != this && "Caller must not be in this SCC.");
218 // is to walk the SCC inverted DAG formed by the parent SCC sets. The inverse
223 // FIXME: We can get this pruning behavior even after the incremental SCC
226 // during the removal of intra-SCC edges, but could be preserved
231 SmallPtrSet<SCC *, 8> ConnectedSCCs;
236 SmallVector<std::pair<SCC *, SCC::parent_iterator>, 8> DFSSCCs;
237 SmallPtrSet<SCC *, 8> VisitedSCCs;
239 SCC *C = this;
243 SCC &ParentSCC = *I++;
245 // If we have already processed this parent SCC, skip it, and remember
247 // stack. This also handles when we reach a child of the 'this' SCC (the
286 // a connected set with the inserted edge, merge all of them into this SCC.
291 for (SCC *C : ConnectedSCCs) {
294 for (SCC *ParentC : C->ParentSCCs)
301 SCC &ChildC = *G->SCCMap.lookup(&ChildN);
312 SCC &ChildC = *G->SCCMap.lookup(&ChildN);
321 return SmallVector<SCC *, 1>(ConnectedSCCs.begin(), ConnectedSCCs.end());
324 void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) {
329 "The caller must be a member of this SCC.");
331 SCC &CalleeC = *G->SCCMap.lookup(&CalleeN);
333 "This API only supports the rmoval of inter-SCC edges.");
337 "Cannot have a leaf SCC caller with a different SCC callee.");
343 SCC &OtherCalleeC = *G->SCCMap.lookup(&OtherCalleeN);
355 // of SCCs in the graph. However, it may cut an edge of the SCC DAG, making
362 "Did not find the caller SCC in the callee SCC's parent list!");
364 // It may orphan an SCC if it is the last edge reaching it, but that does
369 << " edge orphaned the callee's SCC!\n");
372 // It may make the Caller SCC a leaf SCC.
377 void LazyCallGraph::SCC::internalDFS(
380 SmallVectorImpl<SCC *> &ResultSCCs) {
392 if (SCC *ChildSCC = G->SCCMap.lookup(&ChildN)) {
394 // this SCC. If so, the entire stack is necessarily in that set and we
405 // If this child isn't currently in this SCC, no need to process it.
406 // However, we do need to remove this SCC from its SCC's parent set.
440 // At this point we know that N cannot ever be an SCC root. Its low-link
444 // stack which is pulled into the next SCC to be formed.
456 SmallVector<LazyCallGraph::SCC *, 1>
457 LazyCallGraph::SCC::removeIntraSCCEdge(Node &CallerN,
463 SmallVector<SCC *, 1> ResultSCCs;
465 // Direct recursion doesn't impact the SCC graph at all.
469 // The worklist is every node in the original SCC.
473 // The nodes formerly in this SCC are no longer in any SCC.
479 "edge between them that is within the SCC.");
481 // The callee can already reach every node in this SCC (by definition). It is
482 // the only node we know will stay inside this SCC. Everything which
483 // transitively reaches Callee will also remain in the SCC. To model this we
498 assert(PendingSCCStack.empty() && "Didn't flush all pending SCC nodes!");
501 // Now we need to reconnect the current SCC to the graph.
505 SCC &ChildSCC = *G->SCCMap.lookup(&ChildN);
514 assert(!IsLeafSCC && "This SCC cannot be a leaf as we have split out new "
517 [&](SCC *C) { return C == this; }))
518 assert(!IsLeafSCC && "This SCC cannot be a leaf as it already had child "
521 // If this SCC stopped being a leaf through this edge removal, remove it from
522 // the leaf SCC list.
569 SmallVector<SCC *, 16> Worklist(LeafSCCs.begin(), LeafSCCs.end());
572 SCC *C = Worklist.pop_back_val();
580 LazyCallGraph::SCC *LazyCallGraph::formSCC(Node *RootN,
582 // The tail of the stack is the new SCC. Allocate the SCC and pop the stack
584 SCC *NewSCC = new (SCCBPA.Allocate()) SCC(*this);
588 "We cannot have a low link in an SCC lower than its root on the "
594 // A final pass over all edges in the SCC (this remains linear as we only
595 // do this once when we build the SCC) to connect it to the parent sets of
600 SCC &ChildSCC = *SCCMap.lookup(&SCCChildN);
614 LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() {
622 // If we've handled all candidate entry nodes to the SCC forest, we're done.
649 "Found a node with 0 DFS number but already in an SCC!");
666 // Form the new SCC out of the top of the DFS stack.
669 // At this point we know that N cannot ever be an SCC root. Its low-link
673 // stack which is pulled into the next SCC to be formed.
701 static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &SCC) {
702 ptrdiff_t SCCSize = std::distance(SCC.begin(), SCC.end());
703 OS << " SCC with " << SCCSize << " functions:\n";
705 for (LazyCallGraph::Node *N : SCC)
723 for (LazyCallGraph::SCC &SCC : G.postorder_sccs())
724 printSCC(OS, SCC);