OSDN Git Service

[LCG] Add the concept of a "dead" node and use it to avoid a complex
authorChandler Carruth <chandlerc@gmail.com>
Sat, 5 Aug 2017 05:47:37 +0000 (05:47 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Sat, 5 Aug 2017 05:47:37 +0000 (05:47 +0000)
commit95f263eb86dd50d6bbf0814f7d0fe99e246c4faf
tree9b2e902312b5a71861f4e08c5cab546d0c4c3638
parenta4861e0c2b35948a206ebf150403704b718395ee
[LCG] Add the concept of a "dead" node and use it to avoid a complex
walk over the parent set.

When removing a single function from the call graph, we previously would
walk the entire RefSCC's parent set and then walk every outgoing edge
just to find the ones to remove. In addition to this being quite high
complexity in theory, it is also the last fundamental use of the parent
sets.

With this change, when we remove a function we transform the node
containing it to be recognizably "dead" and then teach the edge
iterators to recognize edges to such nodes and skip them the same way
they skip null edges.

We can't move fully to using "dead" nodes -- when disconnecting two live
nodes we need to null out the edge. But the complexity this adds to the
edge sequence isn't too bad and the simplification of lazily handling
this seems like a significant win.

git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@310169 91177308-0d34-0410-b5e6-96231b3b80d8
include/llvm/Analysis/LazyCallGraph.h
lib/Analysis/LazyCallGraph.cpp