[LCG] Add the last (and most complex) of the edge insertion mutation
authorChandler Carruth <chandlerc@gmail.com>
Sun, 4 May 2014 09:38:32 +0000 (09:38 +0000)
committerChandler Carruth <chandlerc@gmail.com>
Sun, 4 May 2014 09:38:32 +0000 (09:38 +0000)
commitfebf86d7e3c6ebab9f1974ea369919811c2eda28
tree4bdd3a8c824df2341d9bb1d0ef60f227e6a39c61
parent57a38b856ee453772c6b2b98a1470b051565f41b
[LCG] Add the last (and most complex) of the edge insertion mutation
operations on the call graph. This one forms a cycle, and while not as
complex as removing an internal edge from an SCC, it involves
a reasonable amount of work to find all of the nodes newly connected in
a cycle.

Also somewhat alarming is the worst case complexity here: it might have
to walk roughly the entire SCC inverse DAG to insert a single edge. This
is carefully documented in the API (I hope).

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