Rolling my own appending linkage

Project Infrastructure LLVM Dev List Archives
1

Hey all, it’s been a while since I have posted on llvm-dev, but that’s mainly because I have been making good progress with my LLVM project. :slight_smile:

In any case, I’d like some advice on implementing my own version of appending linkage as a linker plugin. As I have pointed out on this list before, the existing appending linkage type isn’t useful for me for two reasons:

  1. There’s no way for the compiled code to determine the length of the combined array. Appending linkage concatenates all of the array fragments with the same name together, but there’s no simple way to get a count of the number of elements, or even to insert a sentinel value at the end of the list (Some have suggested solutions involving mucking about with linker sections, but that’s too complicated and fragile IMHO).

  2. If your appended array contains pointer references to globals that would otherwise be dead and stripped from the code, having them in the array will keep them alive. In other words, what I need for my use case is to eliminate dead globals, and then only afterward take the live globals remaining and put them into the array.

To give an example of my use case, suppose I want to create an array of static roots for the garbage collector - that is, I want an array of pointers to all statically-allocated data structures which themselves contains object references. Ideally, the way this would work is as follows: Each time the compiler outputs a static data structure, it would check the type information to see if that structure contains any object references that need to be traced. If so, it would “mark” that structure somehow (how, I am not certain). Then at link time, after dead global elimination, it would collect all of the marked structures and create an array of pointers to those structures, with a NULL pointer at the end of the list. The address of this array would then be passed into the garbage collector when it is first initialized.

Really, all I need to make this work is some way to ‘mark’ a global so that my custom pass can query for all marked globals. Any ideas on this?

2

Hi Talin,

Really, all I need to make this work is some way to 'mark' a global so that my
custom pass can query for all marked globals. Any ideas on this?

metadata maybe?

Ciao, Duncan.

3

A better approach would be to create an global array of strings to hold names of marked globals. You know the name of this special array and use it to query all marked globals. This is the trick llvm-gcc uses to support PCH.

4

Hi Talin,

Really, all I need to make this work is some way to ‘mark’ a global so that my
custom pass can query for all marked globals. Any ideas on this?

metadata maybe?

A better approach would be to create an global array of strings to hold names of marked globals. You know the name of this special array and use it to query all marked globals. This is the trick llvm-gcc uses to support PCH.

OK thanks, I’ll try that :slight_smile:

5

Hi Talin,

Really, all I need to make this work is some way to ‘mark’ a global so that my
custom pass can query for all marked globals. Any ideas on this?

metadata maybe?

A better approach would be to create an global array of strings to hold names of marked globals. You know the name of this special array and use it to query all marked globals. This is the trick llvm-gcc uses to support PCH.

Actually, the ability to attach metadata nodes to globals would be a cleaner way to do this - and it sounds like it would fit your use case as well, plus others that I can think of, such as annotation processing.

6

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.

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 :slight_smile:

7

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.

8

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.” 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. {
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.