[LCG] Add the really, *really* boring edge insertion case: adding an
edge entirely within an existing SCC. Shockingly, making the connected
component more connected is ... a total snooze fest. =]

An

[LCG] Add the really, *really* boring edge insertion case: adding an
edge entirely within an existing SCC. Shockingly, making the connected
component more connected is ... a total snooze fest. =]

Anyways, its wired up, and I even added a test case to make sure it
pretty much sorta works. =D

llvm-svn: 207631

show more ...

Fix multiline comment warning.

../unittests/Analysis/LazyCallGraphTest.cpp:45:1: warning: multi-line comment [-Wcomment]
// / \
^

llvm-svn: 207629

[LCG] Actually test the *basic* edge removal bits (IE, the non-SCC
bits), and discover that it's totally broken. Yay tests. Boo bug. Fix
the basic edge removal so that it works by nulling out the rem

[LCG] Actually test the *basic* edge removal bits (IE, the non-SCC
bits), and discover that it's totally broken. Yay tests. Boo bug. Fix
the basic edge removal so that it works by nulling out the removed edges
rather than actually removing them. This leaves the indices valid in the
map from callee to index, and preserves some of the locality for
iterating over edges. The iterator is made bidirectional to reflect that
it now has to skip over null entries, and the skipping logic is layered
onto it.

As future work, I would like to track essentially the "load factor" of
the edge list, and when it falls below a threshold do a compaction.

An alternative I considered (and continue to consider) is storing the
callees in a doubly linked list where each element of the list is in
a set (which is essentially the classical linked-hash-table
datastructure). The problem with that approach is that either you need
to heap allocate the linked list nodes and use pointers to them, or use
a bucket hash table (with even *more* linked list pointer overhead!),
etc. It's pretty easy to get 5x overhead for values that are just
pointers. So far, I think punching holes in the vector, and periodic
compaction is likely to be much more efficient overall in the space/time
tradeoff.

llvm-svn: 207619

show more ...

[LCG] Add the most basic of edge insertion to the lazy call graph. This
just handles the pre-DFS case. Also add some test cases for this case to
make sure it works.

llvm-svn: 207411

[LCG] Make the return of the IntraSCC removal method actually match its
contract (and be much more useful). It now provides exactly the
post-order traversal a caller might need to perform on newly fo

[LCG] Make the return of the IntraSCC removal method actually match its
contract (and be much more useful). It now provides exactly the
post-order traversal a caller might need to perform on newly formed
SCCs.

llvm-svn: 207410

show more ...

[LCG] Re-organize the methods for mutating a call graph to make their
API requirements much more obvious.

The key here is that there are two totally different use cases for
mutating the graph. Prior

[LCG] Re-organize the methods for mutating a call graph to make their
API requirements much more obvious.

The key here is that there are two totally different use cases for
mutating the graph. Prior to doing any SCC formation, it is very easy to
mutate the graph. There may be users that want to do small tweaks here,
and then use the already-built graph for their SCC-based operations.
This method remains on the graph itself and is documented carefully as
being cheap but unavailable once SCCs are formed.

Once SCCs are formed, and there is some in-flight DFS building them, we
have to be much more careful in how we mutate the graph. These mutation
operations are sunk onto the SCCs themselves, which both simplifies
things (the code was already there!) and helps make it obvious that
these interfaces are only applicable within that context. The other
primary constraint is that the edge being mutated is actually related to
the SCC on which we call the method. This helps make it obvious that you
cannot arbitrarily mutate some other SCC.

I've tried to write much more complete documentation for the interesting
mutation API -- intra-SCC edge removal. Currently one aspect of this
documentation is a lie (the result list of SCCs) but we also don't even
have tests for that API. =[ I'm going to add tests and fix it to match
the documentation next.

llvm-svn: 207339

show more ...

[LCG] Re-order expectations to provide more useful output when debugging
an issue. This way you see that the number of nodes was wrong before
a crash due to accessing too many nodes.

llvm-svn: 207094

[LCG] Switch the SCC's parent iterators to be value iterators rather
than pointer iterators.

llvm-svn: 207086

[LCG] Normalize the post-order SCC iterator to just iterate over the SCC
values rather than having pointers in weird places.

llvm-svn: 207053

[LCG] Switch the primary node iterator to be a *much* more normal C++
iterator, returning a Node by reference on dereference.

llvm-svn: 207048

[LCG] Switch the SCC lookup to be in terms of call graph nodes rather
than functions. So far, this access pattern is *much* more common. It
seems likely that any user of this interface is going to ha

[LCG] Switch the SCC lookup to be in terms of call graph nodes rather
than functions. So far, this access pattern is *much* more common. It
seems likely that any user of this interface is going to have nodes at
the point that they are querying the SCCs.

No functionality changed.

llvm-svn: 207045

show more ...

[LCG] Add the first round of mutation support to the lazy call graph.
This implements the core functionality necessary to remove an edge from
the call graph and correctly update both the basic graph

[LCG] Add the first round of mutation support to the lazy call graph.
This implements the core functionality necessary to remove an edge from
the call graph and correctly update both the basic graph and the SCC
structure. As part of that it has to run a tiny (in number of nodes)
Tarjan-style DFS walk of an SCC being mutated to compute newly formed
SCCs, etc.

This is *very rough* and a WIP. I have a bunch of FIXMEs for code
cleanup that will reduce the boilerplate in this change substantially.
I also have a bunch of simplifications to various parts of both
algorithms that I want to make, but first I'd like to have a more
holistic picture. Ideally, I'd also like more testing. I'll probably add
quite a few more unit tests as I go here to cover the various different
aspects and corner cases of removing edges from the graph.

Still, this is, so far, successfully updating the SCC graph in-place
without disrupting the identity established for the existing SCCs even
when we do challenging things like delete the critical edge that made an
SCC cycle at all and have to reform things as a tree of smaller SCCs.
Getting this to work is really critical for the new pass manager as it
is going to associate significant state with the SCC instance and needs
it to be stable. That is also the motivation behind the return of the
newly formed SCCs. Eventually, I'll wire this all the way up to the
public API so that the pass manager can use it to correctly re-enqueue
newly formed SCCs into a fresh postorder traversal.

llvm-svn: 206968

show more ...

[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-l

[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.

llvm-svn: 206966

show more ...

[LCG] Add a unittest for the LazyCallGraph. I had a weak moment and
resisted this for too long. Just with the basic testing here I was able
to exercise the analysis in more detail and sift out both t

[LCG] Add a unittest for the LazyCallGraph. I had a weak moment and
resisted this for too long. Just with the basic testing here I was able
to exercise the analysis in more detail and sift out both type signature
bugs in the API and a bug in the DFS numbering. All of these are fixed
here as well.

The unittests will be much more important for the mutation support where
it is necessary to craft minimal mutations and then inspect the state of
the graph. There is just no way to do that with a standard FileCheck
test. However, unittesting these kinds of analyses is really quite easy,
especially as they're designed with the new pass manager where there is
essentially no infrastructure required to rig up the core logic and
exercise it at an API level.

As a minor aside about the DFS numbering bug, the DFS numbering used in
LCG is a bit unusual. Rather than numbering from 0, we number from 1,
and use 0 as the sentinel "unvisited" state. Other implementations often
use '-1' for this, but I find it easier to deal with 0 and it shouldn't
make any real difference provided someone doesn't write silly bugs like
forgetting to actually initialize the DFS numbering. Oops. ;]

llvm-svn: 206954

show more ...