[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)
commitc718b8e7c35d0677a68ecdfd8d575b58205a970f
tree9442d243f8b09f1a972dbc7c70d13b892efee64d
parent335fad1c24d0dbeb3ae366bfa8a7ffb54cfc4bb5
[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.

llvm-svn: 310169
llvm/include/llvm/Analysis/LazyCallGraph.h
llvm/lib/Analysis/LazyCallGraph.cpp