Page MenuHomePhabricator

[CallGraph] Refine call graph for indirect calls with !callees metadata
ClosedPublic

Authored by rudkx on Oct 26 2017, 11:35 AM.

Details

Summary

For indirect call sites having a small set of possible callees, !callees metadata can be used to indicate what those callees are. This patch updates the call graph and lazy call graph analyses so that they consider this metadata when encountering call sites. For the call graph, it adds a new external call graph node to the graph for each unique !callees metadata node. A call graph edge connects an indirect call site with the external node associated with the !callees metadata that is attached to it. And there is an edge from this external node to each of the callees indicated by the metadata. Similarly, for the lazy call graph, the patch adds Ref edges from a caller to the possible callees indicated by the metadata.

The primary purpose of the patch is to facilitate iterating over the functions in a module such that all of the callees indicated by a given !callees metadata node will be visited prior to the functions containing call sites annotated by that node. This property is required by optimizations performing a bottom-up traversal of the SCC DAG. For example, the inliner can be made to inline through an indirect call. If the call site is annotated with !callees metadata, this patch ensures that the inliner will have visited all of the callees prior to the caller, allowing it to reliably compute the cost of inlining one or more of the potential callees.

Diff Detail

Repository
rL LLVM

Event Timeline

mssimpso created this revision.Oct 26 2017, 11:35 AM
mssimpso updated this revision to Diff 122317.Nov 9 2017, 1:52 PM
mssimpso edited the summary of this revision. (Show Details)
  • Incorporated the change into the lazy call graph as well. The metadata is represented as ref edges there.
  • Added a helper in CallSite to get the functions listed in the metadata.
fhahn added a subscriber: fhahn.Nov 10 2017, 2:01 AM
mssimpso updated this revision to Diff 141407.Apr 6 2018, 12:57 PM

Updated to work with the latest revision of D39869.

davidxl added a subscriber: davidxl.
rudkx added a subscriber: rudkx.Mon, Jul 22, 10:40 AM
Herald added a project: Restricted Project. · View Herald TranscriptMon, Jul 22, 10:40 AM

@mssimpso Is this something you're still interested in pushing forward?

I was just looking at how we could use callee metadata to improve code, and was going to implement a patch like this to update the call graph so that we had more accurate bottom-up code generation, and then started poking around and found this patch.

@mssimpso Is this something you're still interested in pushing forward?

I was just looking at how we could use callee metadata to improve code, and was going to implement a patch like this to update the call graph so that we had more accurate bottom-up code generation, and then started poking around and found this patch.

I'm no longer working on this, so feel free to take it over if you like. The purpose of the patch was to refine the iteration order over functions, and there was a related patch (D39869) that used the !callees metadata for inlining.

rudkx commandeered this revision.Sun, Aug 4, 4:33 PM
rudkx added a reviewer: mssimpso.

I'll take a look at getting this or something like it in.

rudkx updated this revision to Diff 215097.Wed, Aug 14, 5:52 AM

Apply the original changes to top of tree.

bogner added a subscriber: bogner.Wed, Aug 14, 9:39 AM
bogner added inline comments.
llvm/include/llvm/Analysis/CallGraph.h
88 ↗(On Diff #215097)

Does this really need to be void *? AFAICT it's always CallBase * or null. If that's not correct, it'd probably still be better to use PointerUnion or something.

llvm/lib/Analysis/CallGraph.cpp
182–189 ↗(On Diff #215097)

Maybe I'm misreading this, but isn't CGN == nullptr here, given the assignment just above?

rudkx added inline comments.Wed, Aug 14, 9:52 AM
llvm/include/llvm/Analysis/CallGraph.h
88 ↗(On Diff #215097)

These are actually keyed by MDNode *. I suspect the intent here was to make it more generally useful for creating dummy nodes mapped from various keys. I will change it to MDNode * and it can be generalized in the future if needed.

llvm/lib/Analysis/CallGraph.cpp
182–189 ↗(On Diff #215097)

GCN should be a non-null CallGraphNode holding a Function * that has a nullptr value.

bogner added inline comments.Wed, Aug 14, 9:59 AM
llvm/lib/Analysis/CallGraph.cpp
182–189 ↗(On Diff #215097)

Ah right. In that case, doesn't the node get destroyed when the unique_ptr goes out of scope here? You may have meant to use .release(), but in that case who owns this object?

rudkx updated this revision to Diff 215149.Wed, Aug 14, 9:59 AM

Address review feedback regarding using void* as a key.

rudkx added inline comments.Wed, Aug 14, 10:11 AM
llvm/lib/Analysis/CallGraph.cpp
182–189 ↗(On Diff #215097)

GCN is a reference to the unique_ptr<T> in the map, and unique_ptr has a move assignment operator, so it transfers ownership to the map node right after it is allocated.

bogner accepted this revision.Wed, Aug 14, 2:22 PM

LGTM

llvm/lib/Analysis/CallGraph.cpp
182–189 ↗(On Diff #215097)

Ah, I see. The use of auto & is subtle and I didn't notice that we were actually assigning a reference here. Nevermind.

This revision is now accepted and ready to land.Wed, Aug 14, 2:22 PM
uenoku added a subscriber: uenoku.Wed, Aug 14, 10:02 PM
This revision was automatically updated to reflect the committed changes.