[LCG] Implement Tarjan's algorithm correctly this time. We have to walk
authorChandler Carruth <chandlerc@gmail.com>
Wed, 23 Apr 2014 10:31:17 +0000 (10:31 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Wed, 23 Apr 2014 10:31:17 +0000 (10:31 +0000)
commitb9619110af557a73bf18c504d061d2cbb8507de2
tree786d0ab1a015a0e7443d89e38f04f8de721fb973
parent57683b8abad0c6144cb5e88172509c3afc9fc97a
[LCG] Implement Tarjan's algorithm correctly this time. We have to walk
up the stack finishing the exploration of each entries children before
we're finished in addition to accounting for their low-links. Added
a unittest that really hammers home the need for this with interlocking
cycles that would each appear distinct otherwise and crash or compute
the wrong result. As part of this, nuke a stale fixme and bring the rest
of the implementation still more closely in line with the original
algorithm.

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