[llvm-dev] Linker option to dump dependency graph

[Peter Collingbourne via llvm-dev]

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

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/974ad28a/attachment-0001.html>