[LLVMdev] LLD input graph handling proposal

[Shankar Easwaran]

Hi Nick,

On 9/20/2013 5:59 PM, Nick Kledzik wrote:
> 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.
Sorry for the long mail. This should explain things better.

Here is a example with a state diagram on how the above proposal works. 
The main idea is to keep a running state of the resolver and the 
capturing the resolver state of each input file in the group by the 
linkingcontext.

lld -flavor gnu main.o thread.o --start-group libc.a libpthread.a 
--end-group function.o

main.o has atoms
------------------------
main (defined)
printf(undefined)
fn(undefined)

thread.o has atoms
-----------------------------
pthread_create (undefined)

libc.a(printf.o) has atoms
------------------------------------
printf(defined)

libc.a(exit.o) has atoms
----------------------------------
exit(defined)

libpthread.a has atoms
---------------------------------
pthread_create(defined)
exit(undefined)

function.o has atoms
-------------------------------
fn(defined)


State diagram with time information

Resolver resolverState                                          
Context(nextFile)
-------------- ------------------ ----------------
resolverState = initialState
nextFile(resolverState) initialState ELFContextState=processingFileNode, 
return a.o
resolverState = nochange
process(a.o)
state = definedatoms/undefinedatoms (reason: main/printf)
nextFile(resolverState) definedAtoms/undefinedAtoms 
ELFContextState=processingFileNode, return b.o
resolverState = nochange
process(b.o)
state = undefinedatoms(reason: pthread_create)
nextFile(resolverState) undefinedAtoms 
ELFContextState=processingGroupNode, return libc.a
resolverState=nochange
process(libc.a)
process(printf.o)
state = definedatom (reason: printf)
nextFile(resolverState) definedAtoms 
ELFContextState=processingGroupNode, state[libc.a]=definedAtoms, return 
libpthread.a
resolverState=nochange
process(libpthread.a)
process(pthread.o)
state = definedatom/undefinedatoms (reason: pthread_create/exit)
nextFile(resolverState) definedAtoms/undefinedatoms 
ELFContextState=processingGroupNode, 
state[libpthread.a]=definedAtoms|undefinedAtoms, return libc.a
(returns the first file in the group)

*LinkingContext would exit the GroupNode only if the state of each file 
in the group is unchanged, or has only definedAtoms.*
///LinkingContext here, finds that libc.a has definedAtoms, whereas 
libpthread.a has undefinedAtoms, so traverses the group back./*

*resolverState=nochange
process(libc.a)
process(exit.o)
state = definedatom (reason: exit)
nextfile(resolverState) definedAtoms 
ELFContextState=processingGroupNode, state[libc.a] = definedAtoms, 
return libpthread.a
resolverState=nochange
process(libc.a)
state = nochange
nextfile(resolverState) nochange ELFContextState=processingGroupNode, 
state[libpthread.a] = nochange,

/                                          LinkingContext //finds that 
libc.a state has "definedAtoms", and libpthread.a has "nochange", so 
exits the group./*

*resolverState=nochange
process(function.o)
state  = definedatom (reason: fn)

Exit.

Thanks

Shankar Easwaran

-- 
Qualcomm Innovation Center, Inc. is a member of Code Aurora Forum, hosted by the Linux Foundation

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