[LLVMdev] LLVM Archive Format Extension Proposal

Thu Dec 6 10:11:56 PST 2012

On Nov 21, 2012, at 11:07 AM, Nick Kledzik <kledzik at apple.com<mailto:kledzik at apple.com>> wrote:

On Nov 21, 2012, at 8:55 AM, Relph, Richard wrote:
AMD would like to add new functionality to ranlib (and later ar and nm) and to the bits of LLVM Core that read (and later write) archives.
Herewith a terse summary of the change, which we want to improve support of OpenCL for multiple GPUs in a single run-time.

Conceptually, a serialized archive is really 2 pieces: a few header members and a set of normal file members. There are no constraints on the normal members in the 'pure' archive format. They could be text files, pictures, or, as we're all familiar with, object modules. Most object file archives are "libraries" and the have a special header member that is a global symbol table, associating global scope names with defining object module members in the archive body.

We have N very large archives, defining essentially the same set of symbols. Many of the normal file members of each are duplicated in other archives, but not all. The goal is the produce a single "super-archive" that contains 1 copy of each unique object file member no matter how many archives it is part of, and N symbol table members representing each of the original N archives.
Let me see if I understand your need here.  You are dynamically generating code and need to link it.  The linking step requires some support routines which makes sense to have in a static library.  Since this must work on machines not set up with developer tools, you are packaging the static library inside a DLL/DSO.  In addition, with all the minor variations of GPUs, having a separate archive for every GPU type would be too large, so you need some way to remove duplicates of support functions.

If the above summary is close, then here are two other ideas that avoid the need for archive/TOC changes:
1) Have lots of little archives which removes duplicates.  Give each archive a unique name, then have a lookup table which lists which sequence of archives to use for which specific GPU.  When linking for a particular GPU, you pass the linker that particular sequence of little archives to search.
2) Have one giant archive for per GPU family and use name mangling scheme to filter.  For instance, the compiler emits references to support routine "foo" as "foo$gpu1".  Then you construct the support libraries with aliases for each support function.  So a particular implementation of foo in an archive may show up in the symbol table through its aliases "foo$gpu3", "foo$gpu4", "foo$gpu7".   When the linker is only looking for "foo$gpu1", it will ignore all other foo implementations and just pick the one aliased to "foo$gpu1".

We've figured out that this doesn't really work for us, unfortunately.
The OpenCL library has many, many functions that differ only in the size of the vector they accept. There's sin for float, float2, float3, float4, float8, and float16, for example. And the doubles as well. We have a "common" vector expansion archive that defines most of these in terms of their smaller brethren, though we often have a x4 specific function. But the bottom-level x1 sin is often "per target GPU". The R700 variant is different than the R800 variant is different than the SI variant. The conversion functions are similarly situated and have various rounding mode variants as well, which often alias.
As we currently have the library implemented, for any GPU family, we start by including the library specific to that GPU, then we include the next-newest family's library, and so on, until we arrive at the "if all else fails" library, which is where the "default" conversions and vector expansion functions are defined. So a cos(float16) call would, currently, search, arrive at the bottom layer, resolve to a pair of cos(float8) calls, search starting at the top again, arrive at the bottom, resolve to a pair of cos(float4) calls, which may be defined in any one (or more than one) of the "per generation" libraries, and so on. Virtually ALL of the functions end up calling family-specific implementations somewhere along the line.
The net effect is that to discriminate between the cos(float16) that ends up resolving to the correct cos(float) for a particular GPU family means defining GPU-specific variations of ALL of the functions that are currently defined in the "common" library. This results in almost everything being GPU-specific, which wipes out any advantage at all… we might as well just have N completely separate libraries.

Richard

BTW,  Apple/Darwin has a similar issue with supporting multiple CPUs.  Our solution is "fat" archives.  The ranlib tool sorts all archive members by cpu, builds "thin" archive libraries for each cpu, then concatenates the thin libraries together with a "fat header" which specifies the file offset and size of each thin archive.  The linker, when it comes across a fat static library, looks at the fat header thens seeks along to the contained thin archive relevant to the cpu type being linked.  This scheme works well, but it can produce large files because there is no attempt to reduce duplicates.

-Nick

The symbol table for each original archive can properly index to the relevant members in the archive, even if other members in the super-archive (not referenced in this particular symbol table, of course) define the same symbols.

I've considered 3 approaches to the problem so far. All involve a new archive member type.

First, a new archive member type "up front" that describes each of the original archives and its symbol table.
Second, a normal/default symbol table member "up front" and a new archive member type that describes alternate symbol tables contained in the archive.
Third, a "hiding" archive member type that is essentially a way to "skip over" additional normal archive file headers to reach the first normal member, which (in all approaches) all archives share.

The third, I think, requires the least changes to the existing implementation, so I'm leaning towards it. The "hiding" archive member would have the "file name" of the represented archive immediately following the member header, followed by a completely normal archive representation starting with "<!arch>\n" and optionally including an additional "hiding" archive member covering even more hidden archives.

The plan is to extend the Archive class to provide for a way for clients to select a desired archive. I also will enhance ranlib to accept multiple archive names on the command line and produce the "super-archive" from ranlib.

A further need we have is to serialize the TOCs and the super-archive in a memory image (our archives are embedded in our DLL/SO, not stored separately on disk) and then provide an interface to the relevant LLVM classes (Linker, primarily) for accessing archives in memory rather than on disk, a feature absent from the current implementation.

For our purposes, extending the Archive class to support specification of the archive using a memory object instead of a file, recognizing the "hiding" member type, and extending ranlib to produce the new super archives is all we really need.

Any thoughts or suggestions would be welcome.

Thanks,
Richard

_______________________________________________
LLVM Developers mailing list
LLVMdev at cs.uiuc.edu<mailto:LLVMdev at cs.uiuc.edu>         http://llvm.cs.uiuc.edu<http://llvm.cs.uiuc.edu/>
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

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