[LLVMdev] LLD input graph handling proposal

Nick Kledzik kledzik at apple.com
Fri Sep 20 15:59:25 PDT 2013

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.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20130920/d97f34b9/attachment.html>

More information about the llvm-dev mailing list