[LLVMdev] LLD input graph handling proposal

Rui Ueyama ruiu at google.com
Fri Sep 20 16:39:04 PDT 2013

On Fri, Sep 20, 2013 at 3:59 PM, Nick Kledzik <kledzik at apple.com> wrote:

> On Sep 20, 2013, at 3:37 PM, Rui Ueyama <ruiu at google.com> wrote:
> On Fri, Sep 20, 2013 at 3:29 PM, Nick Kledzik <kledzik at apple.com> wrote:
>> Rui,
>> I like this in general, but have a few questions.
>> On Sep 20, 2013, at 2:30 PM, Rui Ueyama <ruiu at google.com> wrote:
>> 2. We would instead add a new method nextFile() to LinkingContext, which
>> returns a new file from which Resolver should try to resolve undefined
>> symbols. Resolver wouldn't handle the input graph at all. Instead, Resolver
>> calls nextFile() repeatedly to link until nextFile() returns a null value.
>> 3. Resolver will notify Linking Context when (A) all undefined symbols
>> are resolved (success), or (B) it detects it's in an infinite loop in which
>> it cannot resolve any symbols anymore (failure). Linking Context will do
>> whatever it thinks appropriate for the event notification.
>> How does the Resolver detect an infinite loop?  As in the example below,
>> it is supposed to keep getting a,b,c,a,b,c…    At some point, no more
>> undefines are being fulfilled by a,b,c,a,b,c…, but how does the resolver
>> know that the files are repeating, to know to tell the InputGraph to move
>> on?
> nextFile() should returns the same file objects for the same file, so
> Resolver can notice if it haven't resolved any symbol since last time it
> saw the same file.
> That is not how groups work.  The resolver has to keep checking each file
> in the group, in order, until there is one full pass of the group and none
> in the group provided any more content.
> On Sep 20, 2013, at 3:42 PM, Shankar Easwaran <shankare at codeaurora.org>
> wrote:
> nextFile could pass the current resolver state at the time when its
> called, the linkingcontext can return the next file to be processed as
> below :-
> nextFile(currentResolverState) :-
> a) Returns the next file if the current node is not a group node
> b) Returns the next file in the group node, if the current node is a group
> node and the resolver state states undefined /weak / shared library atoms
> were added.
> c) Returns the start file in the group node, if the resolver state states
> undefined/weak/shared library atoms were added
> d) If the state is unchanged, no symbols were added exit the group and
> move to the next node.
> What causes the Resolver state to change?   I understand the state of
> “there are undefines remaining”, but the “something was added” is a
> transient state.  Each last file, changes it.
> The InputGraph knows how to exit a group, but does not know if it should.
> The Resolver knows which files added content, but does not know which
> files are in what groups.
> How about this for InputGraph:
> void fileAddedContent(File *); // asserts that File* param is the same
> thing nextFile() last returned
>  File *nextFile();
> The Resolver, also tells the InputGraph which files it used.  When in a
> group, the InputGraph keeps a flag for the group of whether it has
> contributed anything.  It starts as false for the first entry in the group.
> If fileAddedContent() is called, the flag is updated.  When nextFile() is
> called and the previous entry was the last in the group, if the flag says
> nothing in that pass contributed, the InputGraph exits the group and moves
> on to the next file.

I don't want to make Resolver to have a reference to input graph. The point
of this proposal is to separate input graph handling from Resolver and
instead making Linker Context to do that task. Resolver shouldn't have
knowledge on how it should iterate over input files, focusing only on core
linking. Linking Context should implement the policy and "feed" input files
to Resolver. Resolver should blindly consume an input file given by Linking
Context, and report its status to Linking Context.

How about this: add integer parameters to nextFile() to report the current
number of undefined and defined atoms. With that information, Linking
Context is able to decide what file should be fed to Resolver next. For
example, it can detect from the atom counts whether Resolver need to exit
--{start,end}-group loop or not.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130920/bd91cf7a/attachment.html>

More information about the llvm-dev mailing list