]> granicus.if.org Git - llvm/commit
[LCG] Completely remove the map-based association of post-order numbers
authorChandler Carruth <chandlerc@gmail.com>
Wed, 9 Aug 2017 09:37:39 +0000 (09:37 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Wed, 9 Aug 2017 09:37:39 +0000 (09:37 +0000)
commit722597ed5b7fe9b10f29b7e3d360ae934a68bedc
tree0836c266e759a832c56dc082718f90680330f1ea
parentc214702acde9b3855bc628bbeb2c142b1f990a1d
[LCG] Completely remove the map-based association of post-order numbers
to Nodes when removing ref edges from a RefSCC.

This map based association turns out to be pretty expensive for large
RefSCCs and pointless as we already have embedded data members inside
nodes that we use to track the DFS state. We can reuse one of those and
the map becomes unnecessary.

This also fuses the update of those numbers into the scan across the
pending stack of nodes so that we don't walk the nodes twice during the
DFS.

With this I expect the new PM to be faster than the old PM for the test
case I have been optimizing. That said, it also seems simpler and more
direct in many ways. The side storage was always pretty awkward.

The last remaining hot-spot in the profile of the LCG once this is done
will be the edge iterator walk in the DFS. I'll take a look at improving
that next.

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