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!!!!

Michael Eager wrote:
> 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.

My original posting was primarily intended for the gcc developer
community which is familiar with gimple and not so familiar with dwarf. 
I actually think that dwarf is probably pretty good for what it was
designed for and it is also documented much better than most of the
internals of gcc. 

The task I was given was to encode gimple into dwarf, something that
looked like it might be a reasonable idea, but is, in fact, a bad idea. 
My posting was to tell the gcc community, been there, done that, now
lets move on.

I will respond to many of your points but you should not take this as
criticism of dwarf, these are mostly just places where the interface
between gimple and dwarf was particularly troublesome and unless you
want to get in the transporting intermediate code business, which I
strongly suggest you avoid, you can just ignore most of these problems. 

>> 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.
While I understand your point, from a language theoretic point of view,
they really can be thought of a schemata.  They are a description of the
records types that have been written by the compiler (or some other
tool) for the tags and attributes in this module. 
This may not be the way that they evolved in your community, but for
someone coming from the outside with no knowledge of your history, this
is what they are.

>> 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.
What I did was add 4 new DW_FORMS.  This is one of the areas that, I
assume, users are not supposed to extend.  My assumption is based on the
fact that the standard says how to extend tags and attributes, but is
silent on how to extend forms.

The four forms that I added are:

1) counted list of udata.
2) counted list of sdata.
3) flag with false value.
4) flag with true value.

These are things that made my life simpler and provided for a more
compact encoding.
I cannot comment as to if these would be useful in your world. 
>> 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.
It did not occur to me to do this.  I simply skipped to the obvious next
step that if gcc was the only possible reader and the only possible
writer, (excepting tools that were going to try to understand gimple,)
then there was no reason for the abbrev table at all.
>> 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.
My point exactly.
>> 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. :-) )
Gimple is a tree language and tree can naturally be encoded into stacks,
so from very high up, it seemed that we would be able to use the stack
machine to represent the gimple trees.

The problem is that the information in the nodes of a gimple tree is not
a simple value.  It is a value, a type, possibly some flags, maybe a
line number.  The list seems endless. 
So if this is the information in your node, it is problematic to think
of pushing a popping all of this around on a stack. 

The people in my community only focused on the value, since this is
generally the most important part, and just "forgot" about the rest when
the proposal was made.  It wasn't until I actually went to write the
code that it occurred to me that this was not going to fly.

>> 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.
others point this out.  I am ignorant of the history.
>> 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.
I think that this just another mismatch between what dwarf can provide
and what we are going to need to make our stuff acceptable. 
>> 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
>> frustrations.  


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