+void LazyCallGraph::SCC::removeInterSCCEdge(Node &CallerN, Node &CalleeN) {
+ // First remove it from the node.
+ CallerN.removeEdgeInternal(CalleeN.getFunction());
+
+ assert(G->SCCMap.lookup(&CallerN) == this &&
+ "The caller must be a member of this SCC.");
+
+ SCC &CalleeC = *G->SCCMap.lookup(&CalleeN);
+ assert(&CalleeC != this &&
+ "This API only supports the rmoval of inter-SCC edges.");
+
+ assert(std::find(G->LeafSCCs.begin(), G->LeafSCCs.end(), this) ==
+ G->LeafSCCs.end() &&
+ "Cannot have a leaf SCC caller with a different SCC callee.");
+
+ bool HasOtherCallToCalleeC = false;
+ bool HasOtherCallOutsideSCC = false;
+ for (Node *N : *this) {
+ for (Node &OtherCalleeN : *N) {
+ SCC &OtherCalleeC = *G->SCCMap.lookup(&OtherCalleeN);
+ if (&OtherCalleeC == &CalleeC) {
+ HasOtherCallToCalleeC = true;
+ break;
+ }
+ if (&OtherCalleeC != this)
+ HasOtherCallOutsideSCC = true;
+ }
+ if (HasOtherCallToCalleeC)
+ break;
+ }
+ // Because the SCCs form a DAG, deleting such an edge cannot change the set
+ // of SCCs in the graph. However, it may cut an edge of the SCC DAG, making
+ // the caller no longer a parent of the callee. Walk the other call edges
+ // in the caller to tell.
+ if (!HasOtherCallToCalleeC) {
+ bool Removed = CalleeC.ParentSCCs.erase(this);
+ (void)Removed;
+ assert(Removed &&
+ "Did not find the caller SCC in the callee SCC's parent list!");
+
+ // It may orphan an SCC if it is the last edge reaching it, but that does
+ // not violate any invariants of the graph.
+ if (CalleeC.ParentSCCs.empty())
+ DEBUG(dbgs() << "LCG: Update removing " << CallerN.getFunction().getName()
+ << " -> " << CalleeN.getFunction().getName()
+ << " edge orphaned the callee's SCC!\n");
+ }
+
+ // It may make the Caller SCC a leaf SCC.
+ if (!HasOtherCallOutsideSCC)
+ G->LeafSCCs.push_back(this);
+}
+
+void LazyCallGraph::SCC::internalDFS(
+ SmallVectorImpl<std::pair<Node *, Node::iterator>> &DFSStack,
+ SmallVectorImpl<Node *> &PendingSCCStack, Node *N,
+ SmallVectorImpl<SCC *> &ResultSCCs) {
+ Node::iterator I = N->begin();
+ N->LowLink = N->DFSNumber = 1;
+ int NextDFSNumber = 2;
+ for (;;) {
+ assert(N->DFSNumber != 0 && "We should always assign a DFS number "
+ "before processing a node.");
+
+ // We simulate recursion by popping out of the nested loop and continuing.
+ Node::iterator E = N->end();
+ while (I != E) {
+ Node &ChildN = *I;
+ if (SCC *ChildSCC = G->SCCMap.lookup(&ChildN)) {
+ // Check if we have reached a node in the new (known connected) set of
+ // this SCC. If so, the entire stack is necessarily in that set and we
+ // can re-start.
+ if (ChildSCC == this) {
+ insert(*N);
+ while (!PendingSCCStack.empty())
+ insert(*PendingSCCStack.pop_back_val());
+ while (!DFSStack.empty())
+ insert(*DFSStack.pop_back_val().first);
+ return;
+ }
+
+ // If this child isn't currently in this SCC, no need to process it.
+ // However, we do need to remove this SCC from its SCC's parent set.
+ ChildSCC->ParentSCCs.erase(this);
+ ++I;
+ continue;
+ }
+
+ if (ChildN.DFSNumber == 0) {
+ // Mark that we should start at this child when next this node is the
+ // top of the stack. We don't start at the next child to ensure this
+ // child's lowlink is reflected.
+ DFSStack.push_back(std::make_pair(N, I));
+
+ // Continue, resetting to the child node.
+ ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
+ N = &ChildN;
+ I = ChildN.begin();
+ E = ChildN.end();
+ continue;
+ }
+
+ // Track the lowest link of the children, if any are still in the stack.
+ // Any child not on the stack will have a LowLink of -1.
+ assert(ChildN.LowLink != 0 &&
+ "Low-link must not be zero with a non-zero DFS number.");
+ if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
+ N->LowLink = ChildN.LowLink;
+ ++I;
+ }
+
+ if (N->LowLink == N->DFSNumber) {
+ ResultSCCs.push_back(G->formSCC(N, PendingSCCStack));
+ if (DFSStack.empty())
+ return;
+ } else {
+ // At this point we know that N cannot ever be an SCC root. Its low-link
+ // is not its dfs-number, and we've processed all of its children. It is
+ // just sitting here waiting until some node further down the stack gets
+ // low-link == dfs-number and pops it off as well. Move it to the pending
+ // stack which is pulled into the next SCC to be formed.
+ PendingSCCStack.push_back(N);
+
+ assert(!DFSStack.empty() && "We shouldn't have an empty stack!");
+ }
+
+ N = DFSStack.back().first;
+ I = DFSStack.back().second;
+ DFSStack.pop_back();