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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

George Karpenkov via llvm-dev
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

_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

George Karpenkov via llvm-dev
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 <[hidden email]> 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


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

George Karpenkov via llvm-dev
On Wed, Aug 9, 2017 at 3:04 PM, Charles Saternos via llvm-dev
<[hidden email]> 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
_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

George Karpenkov via llvm-dev
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 :), 

OK cool, the slideshow clarified what SCCs do. So it looks like scc_iterator will navigate the reduced graph in topological order, which means all I have to worry about are describing the graphtraits, and the scc_iterator does the rest?

you don't need to start from the entry point, as long as you have a topological order.

That makes sense. I was going off the implementation of the callgraph (which starts at the callgraph's entry point), but I was misinterpreting the significance of that. It looks like my problem is just a bug in my GraphTraits implementation then, because I'm only finding 2 SCCs (each with one node) in my test example which should be finding 10 nodes. 

Thanks for the help Davide!
- Charles

On Thu, Aug 10, 2017 at 3:39 AM, Davide Italiano <[hidden email]> wrote:
On Wed, Aug 9, 2017 at 3:04 PM, Charles Saternos via llvm-dev
<[hidden email]> 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


_______________________________________________
LLVM Developers mailing list
[hidden email]
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Loading...