[LLVMdev] Rolling my own appending linkage

[Talin]

On Tue, Feb 1, 2011 at 9:20 AM, Devang Patel <dpatel at apple.com> wrote:

>
> On Jan 30, 2011, at 8:36 PM, Talin wrote:
>
> > So, I spent the better part of a day making sure that each and every
> static global had a well-formed and unique name. So far so good.
> >
> > However, It turns out that what I need is a little different than what I
> described - I not only need to know which globals should be traced, but I
> also need to associate with each of these globals a data structure that
> tells the garbage collector how to trace it.
> >
> > Let me describe the setup: For each compiled module, the compiler
> generates a list of all statically allocated data structures in the module.
> Each list entry is a 2-tuple containing a pointer to the static global and a
> pointer to the trace table for that global. Globals that have the same type
> will share the same trace table.
> >
> > OK so what I need to have happen at link time is the following:
> >
> > -- Run the dead global elimination pass to determine which globals will
> be included in the final output.
> > -- For the globals that remain, find the trace table pointer that was
> originally associated with that global.
> > -- Collect the globals and their associated table pointers into a list of
> tuples, which is given to the garbage collector as a parameter on startup.
>
> You could use metadata to hold this list of tuples. If you create this list
> before running dead global elimination pass then the optimizer won't see
> this metadata and any globals that are deleted will be turned into null in
> your tuple.
>
> Oooh, I like that. I didn't realize that metadata nodes could point to
non-metadata nodes. That would solve a number of problems for me.

Now of course there's no "appending linkage" for metadata nodes, so I
imagine I'd have to come up with a different method for combining the nodes
from each module. I suppose I would have the frontend create a node for each
module with some naming convention such as "moduledata.<modulename>" and
then in the linker do a search for all metadata nodes that begin with
"moduledata" and combine them.

This technique would also be useful for annotation indexes. I'll give an
example: Let's say someone comes up with a new annotation in my language,
let's call it @Configured, which is used to indicate that this class has
some configuration data associated with it. At runtime, there's a
configuration reader class that needs to find all classes which have this
annotation. But we don't want the presence of that annotation to prevent
classes from becoming dead if they aren't used. So we could use this
technique to create metadata nodes representing the set of classes with the
annotation, and at link time the linker builds a global index of the classes
that didn't get eliminated.

The metadata would probably look something like this:

moduledata.<modulename> {
  roots: [list of root tuples]
  annotation-1 [list of globals]
  annotation-2 [list of globals]
  ... and so forth
}

A person who creates a new annotation needs only to iterate through the set
of classes in the index:

   for cls in Annotation.findClassesWith(Configured) {
     configureClass(cls);
   }

This would be useful for things like command-line arguments (similar to
LLVM's command argument system), logging, dependency injection, and a lot of
other things. It's like JavaBeans for non-Java languages.

Now, one thing that remains is that I don't want the trace tables (the
second element in the tuple) to be eliminated by the dead global pass. As
you say, referencing a global via a metadata node won't prevent the node
from being deleted, and while some of those tables will be referred to by
other symbols, many will not be referred to by anything. So I guess the
answer is to have some dummy global that refers to all of these tables. Then
once we've built the global static roots table, go ahead and delete this
dummy global, so that any trace tables that didn't get referred to by some
root are now dead. Then go ahead and run the dead global pass a second time.


> > There are a couple of steps in the above that aren't quite clear to me.
> The main problem is that I don't want the trace tables themselves to be
> eliminated by the dead global elimination pass - or conversely, if they are
> eliminated, I need a way to add them back into the module again. This also
> includes any function pointers embedded in the trace table structures, which
> might have been considered dead when the trace table was dead.
> >
> > In other words, what I'd like to be able to do is run the dead global
> elimination pass without considering the trace tables at all, and then once
> I know which globals are live, go ahead and re-associate the trace table
> with each global, and then re-run the dead global pass to remove any trace
> tables that weren't referred to.
> >
> > Any suggestions would be welcome. I'm otherwise very close to getting a
> simple, non-shadow-stack collector working :)
> >
>
> -
> Devang




-- 
-- Talin
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20110201/7709414b/attachment.html>