This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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

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

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.


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

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

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.


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. :-) )


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.


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.


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.


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.


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.


I will add this when we reach a consensus on DWARF3.


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

-- Michael Eager 1960 Park Blvd., Palo Alto, CA 94306 650-325-8077

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]