llvm dev - Aug 2017 - [ThinLTO] Suggestions on how to traverse SCCs in the Module Summary Index bottom up

Hey all,

I'm working on adding function attribute propagation to function summaries
in the ThinLTO index, and have run into some trouble with ensuring
bottom-up traversal when finding the SCCs in the call graph.

I'm basing my implementation for the GraphTraits for the ModuleSummaryIndex
off the GraphTraits<CallGraph *> implementation (
http://llvm-cs.pcc.me.uk/include/llvm/Analysis/CallGraph.h#407). In the
GraphTrait<CallGraph *> definition, the getEntryNode function returns the
external calling node (
http://llvm-cs.pcc.me.uk/include/llvm/Analysis/CallGraph.h#450), which I
assume is supposed to be at the bottom of the callgraph. Would doing same
for the ModuleSummaryIndex ensure the scc_iterator traverses bottom up (if
that even makes sense)?

Rather than returning a dummy FunctionSummary that's empty for external
functions (which is what I'm doing right now), would it make more sense to
have one node that represents all external FunctionSummaries? If I used
this FunctionSummary as the entry point for the scc_iterator traversal of
the ModuleSummaryIndex callgraph would the traversal be bottom up?

Here's my patch in its current state: https://reviews.llvm.org/D36311

Thanks,
Charles
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170809/df55c67a/attachment.html>

I just realized that I've been misunderstanding this (I think). If I'm
understanding it now, the entry node for the graph should actually be the
graph's root (not a bottom node), and that the scc_iterator works its way
down. So for the ModuleSummary, I should find the main function and return
that (or whatever function is the entry point for the entire program).

If anyone has suggestions for the patch, I'd still be interested in hearing
them.

- Charles

On Wed, Aug 9, 2017 at 10:21 AM, Charles Saternos <
charles.saternos at gmail.com> wrote:
> Hey all,
>
> I'm working on adding function attribute propagation to function
summaries
> in the ThinLTO index, and have run into some trouble with ensuring
> bottom-up traversal when finding the SCCs in the call graph.
>
> I'm basing my implementation for the GraphTraits for the
> ModuleSummaryIndex off the GraphTraits<CallGraph *> implementation (
> http://llvm-cs.pcc.me.uk/include/llvm/Analysis/CallGraph.h#407). In the
> GraphTrait<CallGraph *> definition, the getEntryNode function returns
the
> external calling node (http://llvm-cs.pcc.me.uk/include/llvm/Analysis/
> CallGraph.h#450), which I assume is supposed to be at the bottom of the
> callgraph. Would doing same for the ModuleSummaryIndex ensure the
> scc_iterator traverses bottom up (if that even makes sense)?
>
> Rather than returning a dummy FunctionSummary that's empty for external
> functions (which is what I'm doing right now), would it make more sense
to
> have one node that represents all external FunctionSummaries? If I used
> this FunctionSummary as the entry point for the scc_iterator traversal of
> the ModuleSummaryIndex callgraph would the traversal be bottom up?
>
> Here's my patch in its current state: https://reviews.llvm.org/D36311
>
> Thanks,
> Charles
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170809/fe64a0f6/attachment.html>

On Wed, Aug 9, 2017 at 3:04 PM, Charles Saternos via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> I just realized that I've been misunderstanding this (I think). If
I'm
> understanding it now, the entry node for the graph should actually be the
> graph's root (not a bottom node), and that the scc_iterator works its
way
> down. So for the ModuleSummary, I should find the main function and return
> that (or whatever function is the entry point for the entire program).
>
You can look at how the traits are used. Several passes in tree use
them, so you can get an idea (look for CGSCC, for example, the
inliner). Also, SCCs are discovered in post-order. If you want a
different visitation order you should built that yourself on top of
the existing one (see for example the code in FunctionAttrs.cpp which
discovers the SCC in RPO).

That said, I'm not sure why you need to find the entry point of the program.
SCCs (collapsed) create a DAG so you can first propagate the attribute
within the SCC (until convergence) and then propagate across SCCs (see
the strong component section of
http://www.imm.dtu.dk/~hrni/PPA/slides6.pdf ). Unless I misunderstood
your problem (which I might have :), you don't need to start from the
entry point, as long as you have a topological order.

--
Davide