This is an archive of the discontinued LLVM Phabricator instance.

[SyntheticCounts] Rewrite the code using only graph traits.
ClosedPublic

Authored by eraman on Jan 19 2018, 12:36 PM.

Details

Summary

The intent of this is to allow the code to be used with ThinLTO. In
Thinlink phase, a traditional Callgraph can not be computed even though
all the necessary information (nodes and edges of a call graph) is
available. This is due to the fact that CallGraph class is closely tied
to the IR. This patch first extends GraphTraits to add a CallGraphTraits
graph. This is then used to implement a version of counts propagation
on a generic callgraph.

Diff Detail

Event Timeline

eraman created this revision.Jan 19 2018, 12:36 PM

I like the idea here a lot, but i don't understand why you need to make a new type of graph traits with things called call_edge_begin/end.
Can you explain the necessity here?
(IE why can you just not implement a graphtraits, why do you need a callgraphtraits)

davidxl added inline comments.Jan 22 2018, 10:00 AM
include/llvm/Analysis/CallGraph.h
541

use 'child_begin()/child_end()'?

546

Is it better to push this method into the base class ( template<> GraphTraits<Callgraph*> )?

include/llvm/Analysis/SyntheticCountsUtils.h
31

nit: I suggest not using 'Utils' in the name. Also the profile propagation engine will be used for partial profile case as well, so it is not completely Synthetic. May be just call it 'ProfileCountProp' or ProfCountPropagator'

eraman added inline comments.Jan 22 2018, 11:35 AM
include/llvm/Analysis/CallGraph.h
541

child_begin/end is used in CallGraphTraits to iterate over children nodes.

546

This is not really a graph trait and obviously doesn't make sense for other graphs. So an algorithm that works on a general graph which is specialized for GraphTraits cannot do GraphTraits<G>::has_function_def and so this logically belongs here.

davidxl added inline comments.Jan 22 2018, 11:48 AM
include/llvm/Analysis/CallGraph.h
541

ok. Does it make sense to push edge_begin method to the subclass instead?

546

ok. Makes sense

I don't understand why you need has_function_def. It looks very much like a thing you should just be using a filter_iterator for or something. It does not look like it belongs in the graphtraits at all.

Is it a thing that is even different for each callgraph implementation? (If not, why is it a trait?)
Even if it is, if you look, you'll see we don't try to encode random computed Node property differences in GraphTraits. Only the things that *every* graph algorithm needs (IE it caters to anything, not everything). Random node property differences are handled through other trait classes or filtering. This does not, at a glance, seem like a thing that literally every algorithm that is going to use a Callgraph needs. It looks like one that some may need. You even prove this yourself.

If you want to do something different here for CallGraphTraits, i'd like to understand what advantage it has. At least in this patch as currently written, there is no advantage to has_function_def existing as a CallGraphTrait.
It would work just existing fine outside of CallGraphTraits, and even as a templated function local to a single file.

eraman updated this revision to Diff 131147.Jan 23 2018, 2:56 PM

Remove has_function_def from CallGraphTraits and fixup counts propagation code.

This revision is now accepted and ready to land.Jan 25 2018, 11:34 AM
This revision was automatically updated to reflect the committed changes.