This is an archive of the discontinued LLVM Phabricator instance.

[CallGraph] Add support for callback call sites
ClosedPublic

Authored by sdmitriev on Jun 25 2020, 9:03 AM.

Details

Summary

This patch changes call graph analysis to recognize callback call sites
and add an artificial 'reference' call record from the broker function
caller to the callback function in the call graph. A presence of such
reference enforces bottom-up traversal order for callback functions in
CG SCC pass manager because callback function logically becomes a callee
of the broker function caller.

Diff Detail

Event Timeline

sdmitriev created this revision.Jun 25 2020, 9:03 AM
sdmitriev updated this revision to Diff 273423.Jun 25 2020, 9:59 AM

Fixed 'clang-format' issue reported by pre-merge checks.

sdmitriev updated this revision to Diff 273523.Jun 25 2020, 2:40 PM

One more fix for pre-merge check issues.

Looks pretty good. We need more documentation in the CallGraph and CallGraphNode though.

llvm/include/llvm/Analysis/CallGraph.h
178

This change is unrelated, right? Or did I miss where you differentiate between None and nullptr? If so, we should probably describe here what each means.

sdmitriev added inline comments.Jun 25 2020, 5:53 PM
llvm/include/llvm/Analysis/CallGraph.h
178

No, it is related. For ‘reference’ edges that are not associated with any call instruction CallRecord is created with the first field set to None, while real calls have instruction address there (please see lines 246-247 below). Therefore all real calls are expected to have a value in this field and it is not supposed to be nullptr. I will add a comment explaining this.

sdmitriev updated this revision to Diff 273577.Jun 25 2020, 6:54 PM
sdmitriev marked an inline comment as done.
jdoerfert added inline comments.Jun 25 2020, 7:40 PM
llvm/include/llvm/Analysis/CallGraph.h
178

I see. The comment helps but I might not have phrased my questions the right way. Didn't we already use an explicit nullptr as the "call" for the external call edges? That's why I thought you replaced nullptr with none now and asked if we distinguish between the two. It seems not.

The nullptr edge is for example in llvm/test/Analysis/CallGraph/non-leaf-intrinsics.ll

sdmitriev added inline comments.Jun 26 2020, 8:48 AM
llvm/include/llvm/Analysis/CallGraph.h
178

Ah, I see what you mean. So, you are basically asking why that change from nullptr to None is needed if nullptr is already used for representing external ‘call’ edges which are in fact ‘reference’ edges? Can’t we use explicit nullptr for “call” edges to callbacks?

You are right, in the current implementation explicit nullptr indeed represents a ‘reference’ edge, but such edge is allowed only for special “external” nodes which have nullptr function or for nodes representing function declarations. And a presence of an edge with nullptr call site for a defined function is considered as an error. CG SCC pass manager assumes that such situation can occur only if pass deleted a call instruction (which nulls WeakTrackingVH), but forgot to update the call graph with that change (please see llvm/lib/Analysis/CallGraphSCCPass.cpp below, lines starting from 236).

Therefore, use of explicit nullptr for an edge to callback function cannot be differentiated from the error case when pass forgot to update call graph after deleting call site. That is the reason why I made call site in the CallRecord optional. If CallRecord represents a real call it will always have value in the call site field (i.e. hasValue() will return true), and this value cannot be nullptr (otherwise it would be a stale edge). A ‘reference’ edge will not have a value in the call site field (hasValue() will be false). Does this sound reasonable?

jdoerfert accepted this revision.Jun 26 2020, 1:38 PM

The changes LGTM. There are parts that you could split into an NFC patch and commit right away, e.g. most of the stuff in llvm/lib/Analysis/CallGraphSCCPass.cpp and llvm/lib/Transforms/IPO/SyntheticCountsPropagation.cpp.

Wait with the rest until next week but I doubt it will impact anyone negatively, assuming the code to determine something is not a abstract call site is fast enough (for this purpose).
If it would be a problem, we might need to check the presence of metadata first in the foreachCallbackXXX functions.

llvm/include/llvm/Analysis/CallGraph.h
178

It does. I failed to see the check for an explicit nullptr before. Thanks for the details!

This revision is now accepted and ready to land.Jun 26 2020, 1:38 PM
sdmitriev updated this revision to Diff 273992.Jun 28 2020, 8:52 PM

Rebase after committing NFC patch (D82686).

This revision was automatically updated to reflect the committed changes.