diff options
author | Chandler Carruth <chandlerc@gmail.com> | 2014-04-26 09:45:55 +0000 |
---|---|---|
committer | Chandler Carruth <chandlerc@gmail.com> | 2014-04-26 09:45:55 +0000 |
commit | 9a1fab37c72e134bfca980bd69a58a593a7bc148 (patch) | |
tree | 35151a4f74dfdcead3a28f4853fedfa4ef4b541f /lib/Analysis/LazyCallGraph.cpp | |
parent | 797bbced53454aeb6bb143bcd23db5a32b4a9b06 (diff) | |
download | llvm-9a1fab37c72e134bfca980bd69a58a593a7bc148.tar.gz llvm-9a1fab37c72e134bfca980bd69a58a593a7bc148.tar.bz2 llvm-9a1fab37c72e134bfca980bd69a58a593a7bc148.tar.xz |
[LCG] Rather than removing nodes from the SCC entry set when we process
them, just skip over any DFS-numbered nodes when finding the next root
of a DFS. This allows the entry set to just be a vector as we populate
it from a uniqued source. It also removes the possibility for a linear
scan of the entry set to actually do the removal which can make things
go quadratic if we get unlucky.
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@207312 91177308-0d34-0410-b5e6-96231b3b80d8
Diffstat (limited to 'lib/Analysis/LazyCallGraph.cpp')
-rw-r--r-- | lib/Analysis/LazyCallGraph.cpp | 13 |
1 files changed, 7 insertions, 6 deletions
diff --git a/lib/Analysis/LazyCallGraph.cpp b/lib/Analysis/LazyCallGraph.cpp index 50accb3a75..196003430a 100644 --- a/lib/Analysis/LazyCallGraph.cpp +++ b/lib/Analysis/LazyCallGraph.cpp @@ -100,9 +100,9 @@ LazyCallGraph::LazyCallGraph(Module &M) : NextDFSNumber(0) { for (auto &Entry : EntryNodes) if (Function *F = Entry.dyn_cast<Function *>()) - SCCEntryNodes.insert(F); + SCCEntryNodes.push_back(F); else - SCCEntryNodes.insert(&Entry.get<Node *>()->getFunction()); + SCCEntryNodes.push_back(&Entry.get<Node *>()->getFunction()); } LazyCallGraph::LazyCallGraph(LazyCallGraph &&G) @@ -437,10 +437,12 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() { DFSStack.pop_back(); } else { // If we've handled all candidate entry nodes to the SCC forest, we're done. - if (SCCEntryNodes.empty()) - return nullptr; + do { + if (SCCEntryNodes.empty()) + return nullptr; - N = &get(*SCCEntryNodes.pop_back_val()); + N = &get(*SCCEntryNodes.pop_back_val()); + } while (N->DFSNumber != 0); I = N->begin(); N->LowLink = N->DFSNumber = 1; NextDFSNumber = 2; @@ -463,7 +465,6 @@ LazyCallGraph::SCC *LazyCallGraph::getNextSCCInPostOrder() { assert(!SCCMap.count(&ChildN) && "Found a node with 0 DFS number but already in an SCC!"); ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++; - SCCEntryNodes.remove(&ChildN.getFunction()); N = &ChildN; I = ChildN.begin(); E = ChildN.end(); |