[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)
commit2cd28b2ba0b4c3d6fb667113e11bc0ff8968ab26
treedb764e85f926ba17e69064cd5d8c684150447585
parent8756b3fbecfb54741298cb61dc68c849f5871692
[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.

llvm-svn: 310456
llvm/lib/Analysis/LazyCallGraph.cpp