[LCG] Rotate the full SCC finding algorithm to avoid round-trips through
authorChandler Carruth <chandlerc@gmail.com>
Sat, 26 Apr 2014 09:28:00 +0000 (09:28 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Sat, 26 Apr 2014 09:28:00 +0000 (09:28 +0000)
commit797bbced53454aeb6bb143bcd23db5a32b4a9b06
tree94427dd97410e5c34d5fb74d97de735a85ba3f0d
parent84956691129f75835e4683139a08dd70d6f6063f
[LCG] Rotate the full SCC finding algorithm to avoid round-trips through
the DFS stack for leaves in the call graph. As mentioned in my previous
commit, this is particularly interesting for graphs which have high fan
out but low connectivity resulting in many leaves. For such graphs, this
can remove a large % of the DFS stack traffic even though it doesn't
make the stack much smaller.

It's a bit easier to formulate this for the full algorithm because that
one stops completely for each SCC. For example, I was able to directly
eliminate the "Recurse" boolean used to continue an outer loop from the
inner loop.

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