[llvm-dev] Linker option to dump dependency graph

[Rui Ueyama via llvm-dev]

On Wed, Feb 27, 2019 at 4:46 PM Peter Collingbourne <peter at pcc.me.uk> wrote:

>
>
> On Wed, Feb 27, 2019 at 4:41 PM Rui Ueyama <ruiu at google.com> wrote:
>
>> On Wed, Feb 27, 2019 at 1:37 PM Peter Collingbourne <peter at pcc.me.uk>
>> wrote:
>>
>>>
>>>
>>> On Tue, Feb 26, 2019 at 2:24 PM Rui Ueyama via llvm-dev <
>>> llvm-dev at lists.llvm.org> wrote:
>>>
>>>> Hi,
>>>>
>>>> I've heard people say that they want to analyze dependencies between
>>>> object files at the linker level so that they can run a whole-program
>>>> analysis which cannot be done at the compiler that works for one
>>>> compilation unit at a time. I'd like to start a discussion as to what we
>>>> can do with it and how to make it possible. I'm also sharing my idea about
>>>> how to make it possible.
>>>>
>>>> *Dependency analyses*
>>>> First, let me start with a few examples of analyses I'm heard of or
>>>> thinking about. Dependencies between object files can be represented as a
>>>> graph where vertices are input sections and edges are symbols and
>>>> relocations. Analyses would work on the dependency graph. Examples of
>>>> analyses include but not limited to the following:
>>>>
>>>>  - Figure out why some library or an object file gets linked.
>>>>
>>>>  - Finding a candidate to eliminate dependency by finding a "weak" link
>>>> to a library. We can for example say the dependency to a library is
>>>> *weak* if the library in the graph can be unreachable if we remove *N* edges
>>>> from the graph (which is likely to correspond to removing *N* function
>>>> calls from the code), where *N* is a small number.
>>>>
>>>>  - Understanding which of new dependencies increase the executable size
>>>> the most, compare to a previous build.
>>>>
>>>>  - Finding bad or circular dependencies between sub-components.
>>>>
>>>> There would be many more analyses you want to run at the linker input
>>>> level. Currently, lld doesn't actively support such analyses. There are a
>>>> few options to make the linker emit dependency information (e.g. --cref or
>>>> -Map), but the output of the options is not comprehensive; you cannot
>>>> reconstruct a dependency graph from the output of the options.
>>>>
>>>> *Dumping dependency graph*
>>>> So, I'm thinking if it would be desirable to add a new feature to the
>>>> linker to dump an entire dependency graph in such a way that a graph can be
>>>> reconstructed by reading it back. Once we have such feature, we can link a
>>>> program with the feature enabled and run any kind of dependency analysis on
>>>> the output. You can save dumps to compare to previous builds. You can run
>>>> any number of analyses on a dump, instead of invoking the linker for each
>>>> analysis.
>>>>
>>>> I don't have a concrete idea about the file output format, but I
>>>> believe it is essentially enough to emit triplets of (<from input section>,
>>>> <symbol>, <to input section>), which represents an edge, to reconstruct a
>>>> graph.
>>>>
>>>
>>> A couple of points:
>>>
>>> - Symbols are not the only kind of dependency edge from one section to
>>> another -- there's also SHF_LINK_ORDER. Maybe we can just call the edge
>>> "SHF_LINK_ORDER" in that case.
>>> - Do we want to mark up the GC roots in some way? I imagine that we
>>> could do that with a synthetic node that represents the GC root, and then
>>> have all roots include edges from it. With my proposal for partitioning,
>>> perhaps we could have one GC root node per partition.
>>>
>>
>> I think we should mark up the GC root in some way. One thing to note is
>> that not only input sections but also symbols can be GC root. In terms of
>> the graph, both edge and vertex should have a "GC root" bit.
>>
>
> You can represent both with a synthetic GC root vertex, though? e.g.
>
> GC root --[ExportedFunction]--> .text.ExportedFunction
> GC root --[.init_array]--> .init_array.InitializedGlobal
>

I think that should work, but I'm not sure if this is easier to handle than
adding a bit to each vertex/edge.


> Peter
>
>>
>>
>>> Peter
>>>
>>>
>>>> Thoughts?
>>>> _______________________________________________
>>>> LLVM Developers mailing list
>>>> llvm-dev at lists.llvm.org
>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>>
>>>
>>>
>>> --
>>> --
>>> Peter
>>>
>>
>
> --
> --
> Peter
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190227/9894447a/attachment.html>