Re: First cut on outputing gimple for LTO using DWARF3. Discussion invited!!!!

[Michael Eager <eager at eagercon dot com>]

Kenneth Zadeck wrote:
> This posting is a progress report of my task of encoding and decoding
> the GIMPLE stream into LTO.   Included in this posting is a patch that
> encodes functions and dumps the result to files.  

I have only a limited understanding of GIMPLE and LTO, but here are my
comments regarding DWARF.

DWARF is a debugging format used to describe a program's source and how
it is represented in an executable file.  GIMPLE is an intermediate
representation, not program source.  It's always interesting to see one
tool used in a different context, but I'm not clear that in this case
you are using the right tool for the right task in the way that it was
designed.

Speaking on behalf of the DWARF Standards Workgroup, we welcome
suggestions for extensions or improvements in the DWARF standard.
I wasn't able to identify any specific extension in your email (although
I didn't look at the patch in detail).  If there are specific areas
where DWARF can be improved, please let me know.


> 1) ABBREV TABLES ARE BAD FOR LTO.
>
> The abbrev table is a mechanism for making a DWARF3 file self
> descriptive.  It contains a set of templates that are used to describe
> the records and attributes that are written to describe the object
> module.
>
> This self description mechanism is much weaker (an therefor much more
> compact) than an XML file's schemata because it depends on a common
> understanding of the meaning of the tags and attributes that describe
> the pieces of the data.  The tags them selves can be thought of as
> characters, and an abbrev entry is a magic cookie that tells you how
> to break the characters into words.

DWARF is not self-descriptive, except in the very limited sense that
several sections contain version numbers.  The DWARF abbreviation table
is not intended to be self-descriptive or to be descriptive of the
DWARF data.  It is a simple compression scheme which compacts the
Tag/Attribute/Value structure of a DWARF DIE into a much more condensed
format.

Certainly the DWARF Abbrev table makes no pretense of being anything
similar to an XML schema.  I wouldn't use an XML schema for debugging
information (it would be huge and slow), and I wouldn't expect to use
DWARF abbreviation tables to describe anything at all.

> However, this mechanism is only self descriptive if you do not extend
> the set of tags.  That is not an option for LTO.  While the DWARF3
> designers seem to have added every conceivable tag to describe object
> code, it is not be surprising that this comes up short when describing
> GIMPLE.  While some of GIMPLE could be shoe-horned into the existing
> tags, all of it will not fit, so anyone who wants to understand
> GIMPLE, will need to use the GCC headers.

The DWARF standard provides for a consistent means to extend
the debugging format.  If you extend DWARF beyond the standard, as has
often been done, you will need to provide descriptions (in some form)
of what these extensions mean.  You can provide this as written
material, or you can have the implementer read the code.  In either
case, the Abbrev tables only provide compression for the Tag/Attr/Val
structure of a DIE.  They do no provide any semantic description.

> Using the abbrev tables also add a lot of complexity. It should be
> understood that while the abbrev table for two separate files encodes
> the same information, the way that the abbrev tables are generated
> almost guarantees that the abbrev table will be encoded differently for each
> file.  The abbrev table is a sequential list of record
> descriptors. The way that the list is generated is first needed, first
> output, and you only output the records you need.  Each of these
> records is numbered sequentially.  So the numbering of the abbrev
> records will generally be different for the two created object files since
> they reference different GIMPLE nodes.

There is no need for Abbrev tables to be generated differently
for each object file.  Several compilers generate a standard Abbrev
table and then generate DWARF using these predefined abbreviations.

The DWARF standard also allows the Abbrev table to be stored in a
shared object and referenced by individual object files.  I'm not
aware of any actual implementation of this, but the structure is
there.

> I strongly believe that for LTO to work, we are going to have to
> implement some mechanism where the function bodies are loaded into the
> compiler on demand (possibly kept in cache, but maybe not).  This
> will be more cumbersome if we have to keep reloading each object
> file's abbrev table just to tear apart a single function in that .o
> file.  While the abbrev sections average slightly less than %2 of the
> of the size of the GIMPLE encoding for an entire file, each abbrev table
> averages about the same size as a single function.  Thus, we will either
> have to keep all the abbrev entries for an entire compilation, implement
> a second caching mechanism, or do about twice the file reading to load
> a single function.

I'm not exactly sure what you are trying to do, but encoding
an IR representation into DWARF Abbrev tables doesn't sound
like a good idea off the top of my head.

> The alternative is to just have static records that are hard coded
> into the reader and writer.  The records will be the same as the records
> used a abbrev file, but the record schemata's will be hard coded
> rather than assigned on a file by file basis.
>
> A lot of my design decisions are biased by wanting to be able to load
> pieces of an object file without touching large parts of it.  I think
> that if we cannot do this, LTO will be a toy for specmarking and
> nothing more.
>
>
> 2) I PROMISED TO USE THE DWARF3 STACK MACHINE AND I DID NOT.
>
> Rumsfield thought we would be out of Iraq in a few months.  He was
> wrong too.  
>
> It sounded good from a high level but the devil is in the details.
> The problem is that GIMPLE has a lot of hair.  Each tree node has a
> type, a bunch of flags, perhaps a line number, and God only knows what
> else I have missed.  There is no place in the DWARF3 stack machine to
> shove that stuff.

DWARF implements a simple stack machine intended to be used to
compute location expressions.  "GIMPLE has a lot of hair" may
be a clever comment, but it doesn't give a clue about what it
is that you are trying to do, or what features are missing from
the DWARF stack machine which prevent you from doing it.

DWARF doesn't impress me as a good way to represent an IR node.
Seems to be like trying to fix your watch with a hammer, just because
that's the tool you have in your hand.  (There, I, too, threw in
a clever, but essentially meaningless, comment. :-) )

> 3) THERE IS NO COMPRESSION IN DWARF3.
>
> Despite what I was told about abbrev tables providing some compaction
> (see point 1), there are no mechanisms in DWARF3 for compressing the
> data.  The only mechanism that is suggested in the spec is to use a
> lot of sections, and then if you have a smart linker, it can notice
> that many of these sections are duplicates.  This is most likely quite
> useful for C++ templates and if it is, we can play the same game with
> our own encoding, by putting each function or template in its own
> section and depending on our smart linker to purge duplicates.  There
> is nothing in DWARF3 that aids in doing this, the spec simply has a
> section on how to name things so that this could work if you have a
> good linker.

Well, Abbrev tables are a significant compression method (just compare
with DWARF 1), and not the only method.

There are a number of features in DWARF which may be used for compression.
Some, as you mention, expect that they will be performed by a linker,
such as GNU Binutils.

There is also support for DWARF functions and references to similar
DIEs which are overwritten by specific data.

> The abbrev tables take less than 2% of the space and compress about 3:1.
> It is not surprising that the abbrev tables compress so much because
> DWARF3 requires that extension tags have large ids.  Since these tag
> values only live in the abbrev table, all of that air is there, not in
> the part
> that encodes the GIMPLE.

The normal progression in DWARF is that an implementation will use the
User Extension space to prove a concept and then submit the extension
for adoption into the DWARF standard.  At that time, the Tag/Attr values
are defined within the "Standard space" and will, as a result, be more
compact.

> 4) I CHEATED TO GET THE COMPRESSION THAT I GOT.
>
> I must confess that I have actually extended the mechanisms further
> than the DWARF3 standard allows.  I added record forms which is not an
> allowed extension.  The forms that I added were for vectors of
> things. DWARF3's design seems to have been influenced by the GCC design
> that everything can be expressed as a tree.  While this is true, I
> simply applied the same observation that is being done in our tree
> cleanup that vectors are a more compact representation that tree
> lists.  This can be undone, but it will bulk up the representation
> even more.  

Nope, DWARF's design was not influenced by GCC design.  I doubt that
GCC design was influenced by DWARF's design either, although that's
possible.

> To give a concrete example, the successor edge list of a basic block
> is encoded as n + 1 uleb128 numbers.  The first one tells how many
> edges there are and the rest are the block numbers of the successors.
> To do this in DWARF3 without extension, would take almost double the
> space, for each edge, one uleb128 number would be required to
> reference the abbrev entry, and a second one for the successor block.
> The list is then terminated with a 0.  And if we abandon DWARF3, as I
> am advocating, my encoding is the right way to go.



> 2) LOCAL DECLARATIONS  
>
> Mark was going to do all of the types and all of the declarations.
> His plan was to use the existing DWARF3 and enhance it where it was
> necessary eventually replacing the GCC type trees with direct
> references to the DWARF3 symbol table.  This could still work for the
> types and the global variables.  However, I do not see how this could
> work for the local decls, especially when we move to SSA form.  The
> timing of when the declarations are written for debugging is, by
> definition, quite late so that the debugging info actually contains
> instructions to the debugger to access each of the variables.  Some
> variables, especially SSA names do not last that long.  Thus, I feel
> that I am going to at least have to put out my own local variable
> table.  The types and global variables are likely OK, or at least Mark
> should be able to add any missing info.

While it's possible to use DWARF data directly, it was designed
to be a file representation which can be quickly read and converted
into the internal format used by a debugger.  Note that this means
that there are a number of trade-offs, both explicit and implicit,
which make generating DWARF data slower or more complex.

> 3) ADDING COMPRESSION
>
> I have been using zlib as my measurements because I just always use
> zlib.  Furthermore, I know there is a zlib subdirectory in the GCC
> tree so I assume it is available in some form.  I know there are other
> compressors and I leave it to a compression specialist to suggest a
> better alternative.
>
> I should point out that there is a good reasons why DWARF3 is not
> compressed:  there are mechanisms for cross linking the DWARF3 trees
> and if you are either going to rely on the assembler to fix up these
> cross references or expect to memory map the debugging info in and
> just walk around in it, compression is not for you.

Yes, one of DWARF's design criteria is that the data can be processed
by existing (or even past) tools, such as linkers or loaders, without
requiring any modification.  There are a number of restrictions on the
format as a result, including one that no novel encoding or compression
schemes can be used.

> However, the LTO information is not GIMPLE, it is an encoding of
> GIMPLE and needs to be decoded in order to be used by the compiler.
> So passing it through an expander on loading is not an issue.  I also
> do not cross link the DWARF3 trees.  Labels, decls, types, and strings
> all are indirected thru side tables.  This keeps their offsets
> compact.  Thus there is nothing hard about running my sections thru a
> compressor before dumping the binary into the assembly stream.
>
> 4) OTHER INFO
>
> We will also need to add other structures to the object files.  We
> will need to have a version of the cgraph, in a separate section, that
> is in a form so that all of the cgraphs from all of the object files
> can be read a processed without looking at the actual function bodies.
>
> Likewise, we will have to restructure the existing IPA passes into two
> parts: one part computes the local information and the second part
> does some interprocedural closure on that information.  The first part
> of the information can be written in so form into the object files and
> the during LTO processing, read back in so that the interprocedural
> closure can be done.  
>
> For example, the current pure and constant function determination pass
> first determines which functions are locally pure or constant and then
> does a closure over the call graph to make sure that each pure
> function only calls other pure functions and so on...  If we simply
> label the call graph with the locally pure and locally constant
> attributes, the closure phase can be done for all of the functions in
> the LTO compilation without having to reprocess their bodies.
> Virtually all inteprocedural optimizations, including aliasing, can
> and must be structured this way.
>
> 5) ADDING THE READER.
>
> I will add this when we reach a consensus on DWARF3.
>
>
> IF I RULED THE EARTH, THIS IS WHAT I WOULD DO
>
> I would strip out the DWARF3 from this patch.  It is about 1/3 of the
> code, but basically leave the encoding as it is with the exception that
> the abbrev table references would be changes to hard coded record type
> numbers in an include file.  Then run each function through a
> compressor and write it a separate ELF section.  
>
> I have not done this because I do not rule the earth.  That was not
> what I was assigned to do, and I agreed that DWARF3 sounded like a
> reasonable way to go.  Now that I understand the details of DWARF3, I
> have changed my mind about the correct direction.  Now is the time to
> make that change before there is a lot of infrastructure built that
> assumes the DWARF3 encoding.
>
> I understand that this should be a community decision.  I believe that
> attached patch will let anyone play with this so the discussion can
> avoid being just idle speculation.  In particular, the amount of
> compression may change if there are found to be significant problems
> with my understanding of GIMPLE.  Adding the line number info will
> also change the compression ratios though I expect it will only make
> them larger.
>
> I invite your discussion, comments and general venting of personal
> frustrations.  

--
Michael Eager	 eager@eagercon.com
1960 Park Blvd., Palo Alto, CA 94306  650-325-8077