This is an archive of the discontinued LLVM Phabricator instance.

[PM/LCG] Teach the LazyCallGraph how to replace a function without disturbing the graph or having to update edges.
ClosedPublic

Authored by chandlerc on Feb 6 2017, 2:10 AM.

Details

Summary

This is motivated by porting argument promotion to the new pass manager.
Because of how LLVM IR Function objects work, in order to change their
signature a new object needs to be created. This is efficient and
straight forward in the IR but previously was very hard to implement in
LCG. We could easily replace the function a node in the graph
represents. The challenging part is how to handle updating the edges in
the graph.

LCG previously used an edge to a raw function to represent a node that
had not yet been scanned for calls and references. This was the core
of its laziness. However, that model causes this kind of update to be
very hard:

  1. The keys to lookup an edge need to be Function*s that would all need to be updated when we update the node.
  2. There will be some unknown number of edges that haven't transitioned from Function* edges to Node* edges.

All of this complexity isn't necessary. Instead, we can always build
a node around any function, always pointing edges at it and always using
it as the key to lookup an edge. To maintain the laziness, we need to
sink the *edges* of a node into a secondary object and explicitly model
transitioning a node from empty to populated by scanning the function.
This design seems much cleaner in a number of ways, but importantly
there is now exactly *one* place where the Function* has to be
updated!

Some other cleanups that fall out of this include having something to
model the *entry* edges more accurately. Rather than hand rolling parts
of the node in the graph itself, we have an explicit EdgeSequence
object that gives us exactly the functionality needed. We also have
a consistent place to define the edge iterators and can use them for
both the entry edges and the internal edges of the graph.

The API used to model the separation between a node and its edges is
intentionally very thin as most clients are expected to deal with nodes
that have populated edges. We model this exactly as an optional does
with an additional method to populate the edges when that is
a reasonable thing for a client to do. This is based on API design
suggestions from Richard Smith and David Blaikie, credit goes to them
for helping pick how to model this without it being either too explicit
or too implicit.

The patch is somewhat noisy due to shifting around iterator types and
new syntax for walking the edges of a node, but most of the
functionality change is in the Edge, EdgeSequence, and Node types.

Depends on D29381.

Event Timeline

chandlerc created this revision.Feb 6 2017, 2:10 AM
davide edited edge metadata.Feb 7 2017, 11:30 AM

While this patch is large, a fair amount of it are just mechanical changes. I wasn't able to spot any obvious mistake, but I would appreciate another pair of eyes looking at it (@sanjoy ?)

include/llvm/Analysis/LazyCallGraph.h
330–331

Not sure if static_cast<bool> works here, but I would prefer that, if possible.

chandlerc updated this revision to Diff 87600.Feb 8 2017, 12:05 AM

Rebase and address a comment from Davide.

chandlerc marked an inline comment as done.Feb 8 2017, 12:06 AM
chandlerc added inline comments.
include/llvm/Analysis/LazyCallGraph.h
330–331

Sure, but we can do better with Optional::hasValue.

davide accepted this revision.Feb 8 2017, 7:30 AM

LGTM

This revision is now accepted and ready to land.Feb 8 2017, 7:30 AM
sanjoy accepted this revision.Feb 8 2017, 9:22 PM

lgtm, but I glossed over much of the mechanical changes.

chandlerc marked an inline comment as done.Feb 9 2017, 3:06 PM

Thanks all, landing!

This revision was automatically updated to reflect the committed changes.