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

[Charles Saternos 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 <davide at freebsd.org> wrote:

> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170810/d58f75cc/attachment.html>