From 84956691129f75835e4683139a08dd70d6f6063f Mon Sep 17 00:00:00 2001 From: Chandler Carruth Date: Sat, 26 Apr 2014 09:06:53 +0000 Subject: [LCG] Hoist the main DFS loop out of the edge removal function. This makes working through the worklist much cleaner, and makes it possible to avoid the 'bool-to-continue-the-outer-loop' hack. Not a huge difference, but I think this is approaching as polished as I can make it. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207310 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Analysis/LazyCallGraph.cpp | 144 ++++++++++++++++++++--------------------- 1 file changed, 70 insertions(+), 74 deletions(-) (limited to 'lib/Analysis/LazyCallGraph.cpp') diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index 45d289b8c0..1e7f796057 100644 --- a/lib/Analysis/LazyCallGraph.cpp +++ b/lib/Analysis/LazyCallGraph.cpp @@ -180,71 +180,21 @@ void LazyCallGraph::SCC::removeEdge(LazyCallGraph &G, Function &Caller, G.LeafSCCs.push_back(this); } -SmallVector -LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller, - Node &Callee) { - // We return a list of the resulting SCCs, where 'this' is always the first - // element. - SmallVector ResultSCCs; - ResultSCCs.push_back(this); - - // Direct recursion doesn't impact the SCC graph at all. - if (&Caller == &Callee) - return ResultSCCs; - - // We're going to do a full mini-Tarjan's walk using a local stack here. - int NextDFSNumber; - SmallVector, 4> DFSStack; - SmallVector PendingSCCStack; - - // The worklist is every node in the original SCC. - SmallVector Worklist; - Worklist.swap(Nodes); - for (Node *N : Worklist) { - // The nodes formerly in this SCC are no longer in any SCC. - N->DFSNumber = 0; - N->LowLink = 0; - G.SCCMap.erase(N); - } - assert(Worklist.size() > 1 && "We have to have at least two nodes to have an " - "edge between them that is within the SCC."); - - // The callee can already reach every node in this SCC (by definition). It is - // the only node we know will stay inside this SCC. Everything which - // transitively reaches Callee will also remain in the SCC. To model this we - // incrementally add any chain of nodes which reaches something in the new - // node set to the new node set. This short circuits one side of the Tarjan's - // walk. - insert(G, Callee); - - Node *N = nullptr; - Node::iterator ChildI; +void LazyCallGraph::SCC::internalDFS( + LazyCallGraph &G, + SmallVectorImpl> &DFSStack, + SmallVectorImpl &PendingSCCStack, Node *N, + SmallVectorImpl &ResultSCCs) { + Node::iterator I = N->begin(); + N->LowLink = N->DFSNumber = 1; + int NextDFSNumber = 2; for (;;) { - if (!N) { - if (!DFSStack.empty()) { - N = DFSStack.back().first; - ChildI = DFSStack.back().second; - DFSStack.pop_back(); - } else { - // Clear off any nodes which have already been visited in the DFS. - while (!Worklist.empty() && Worklist.back()->DFSNumber != 0) - Worklist.pop_back(); - if (Worklist.empty()) - break; - N = Worklist.pop_back_val(); - N->LowLink = N->DFSNumber = 1; - NextDFSNumber = 2; - ChildI = N->begin(); - assert(PendingSCCStack.empty() && "Cannot start a fresh DFS walk with " - "pending nodes from a prior walk."); - } - } 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. - bool Recurse = false; - for (auto I = ChildI, E = N->end(); I != E; ++I) { + 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 @@ -256,14 +206,13 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller, insert(G, *PendingSCCStack.pop_back_val()); while (!DFSStack.empty()) insert(G, *DFSStack.pop_back_val().first); - N = nullptr; - Recurse = true; - break; + 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; } @@ -273,12 +222,12 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller, // child's lowlink is reflected. DFSStack.push_back(std::make_pair(N, I)); - // Recurse onto this node via a tail call. + // Continue, resetting to the child node. ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++; N = &ChildN; - ChildI = ChildN.begin(); - Recurse = true; - break; + I = ChildN.begin(); + E = ChildN.end(); + continue; } // Track the lowest link of the childen, if any are still in the stack. @@ -287,11 +236,14 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller, "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 (Recurse) - continue; - if (N->LowLink != N->DFSNumber) { + 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 @@ -300,13 +252,57 @@ LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller, PendingSCCStack.push_back(N); assert(!DFSStack.empty() && "We shouldn't have an empty stack!"); - N = nullptr; - continue; } - ResultSCCs.push_back(G.formSCC(N, PendingSCCStack)); - N = nullptr; + N = DFSStack.back().first; + I = DFSStack.back().second; + DFSStack.pop_back(); + } +} + +SmallVector +LazyCallGraph::SCC::removeInternalEdge(LazyCallGraph &G, Node &Caller, + Node &Callee) { + // We return a list of the resulting SCCs, where 'this' is always the first + // element. + SmallVector ResultSCCs; + ResultSCCs.push_back(this); + + // Direct recursion doesn't impact the SCC graph at all. + if (&Caller == &Callee) + return ResultSCCs; + + // The worklist is every node in the original SCC. + SmallVector Worklist; + Worklist.swap(Nodes); + for (Node *N : Worklist) { + // The nodes formerly in this SCC are no longer in any SCC. + N->DFSNumber = 0; + N->LowLink = 0; + G.SCCMap.erase(N); } + assert(Worklist.size() > 1 && "We have to have at least two nodes to have an " + "edge between them that is within the SCC."); + + // The callee can already reach every node in this SCC (by definition). It is + // the only node we know will stay inside this SCC. Everything which + // transitively reaches Callee will also remain in the SCC. To model this we + // incrementally add any chain of nodes which reaches something in the new + // node set to the new node set. This short circuits one side of the Tarjan's + // walk. + insert(G, Callee); + + // We're going to do a full mini-Tarjan's walk using a local stack here. + SmallVector, 4> DFSStack; + SmallVector PendingSCCStack; + do { + Node *N = Worklist.pop_back_val(); + if (N->DFSNumber == 0) + internalDFS(G, DFSStack, PendingSCCStack, N, ResultSCCs); + + assert(DFSStack.empty() && "Didn't flush the entire DFS stack!"); + assert(PendingSCCStack.empty() && "Didn't flush all pending SCC nodes!"); + } while (!Worklist.empty()); // Now we need to reconnect the current SCC to the graph. bool IsLeafSCC = true; -- cgit v1.2.3