Redesign LLVM 2.0 bytecode format

[lattner]

Bugzilla Link	1127
Resolution	FIXED
Resolved on	Feb 22, 2010 12:54
Version	1.0
OS	All
CC	@isanbard

Extended Description

We want to scrap the current way we handle .bc files. Here are some ideas/desires for the new format:

1. I'd like to get rid of libbzip2.
2. I think it makes sense to use a completely variable bitwidth format, not trying to keep things at byte
   alignments.
3. We should probably keep type planes, as they allow us to use the type constraints in llvm to make
   the encoding more dense.
4. We should consider a packetized format like dwarf for things like the moduleinfoblock and
   functioninfoblocks, which makes it easier to extend the format without a new revision #.

Any other ideas?

-Chris

[llvmbot]

I agree with all of those. I have some other things I'd like to achieve as well.

I don't like the way the BytecodeHandler is currently implemented (calls to
handler from inside bcreader). Instead I would like to see a generic Recognizer
class that handles all the low level bit stream details, packets, headers, etc.
The Recognizer extracts values/data from the bitstream but doesn't do anything
with that data except invoke a handler method. The recognizer could be a
template to minimize the cost of the handler functions. It should also be an
exported API from LLVM. Both the Analyzer and the BCReader would then use this
reader (instantiate it with there own handler) to implement what should be done
for its particular purpose. This approach allows bytecode reading to be extended
for other purposes as well.

I would like to make an llvm-dump tool that dumps the raw bit stream and also
tells you what it means. This could be an invaluable tool as we implement the
new bit stream format. Given the Recognizer interface, it shouldn't be too much
trouble.

Since we are getting rid of bzip2 compression we need to ensure that the
bitstream is as compact as possible. Some ideas for this:

1. fold redundant strings (array initializers, symtab, etc.)
2. organize type planes and etc. so that the most frequently used values have
   the lowest slot numbers.
3. find other ways to factor out commonalities and redundancies. For example, a
   group of global variables with the same type, same alignment, same section,
   etc could be codified as a "type of global" using a small integer. The only
   difference might be the initializer.
4. Revise the instruction encoding to be as compact as possible. Right now there
   are too many "format 0" situations resulting from changes in opcodes.
5. Possibly fold redundancies in PHI lists?

This puts a much bigger burden on the writer, but I think it makes sense to
optimize for both bytecode size (reduced I/O on read) and reader speed. The goal
is to get the bytecode translated to the C++ IR as fast as possible. If that
penalizes writing, so be it.

I agree that bzip2 support in LLVM should be removed, but we need to leave hooks
in the code for clients that wish to compact the bytecode. While LLVM won't
implement this, other systems (like HLVM) would like to offer "jar" type
functionality with compressed bytecode files in an archive. The Reader interface
shouldn't prevent this. To some extent this depends on how well the new bitcode
is compressed in its raw format. Algorithms like zip and bzip2 might not be able
to do much with it. Some analysis would be in order (a reason to keep
llvm-bcanalyzer).

We need to support integer constants > 64bits. This is a "to do" item for my
current project, but we musn't prohibit it in the new design.

Can we just use ELF? Or is that too verbose?

[lattner]

Instead I would like to see a generic Recognizer
class that handles all the low level bit stream details, packets, headers, etc.

I'm fine with that as long as reading is still efficient.

4. Revise the instruction encoding to be as compact as possible. Right now there
   are too many "format 0" situations resulting from changes in opcodes.

We should just completely drop 'formats' for instruction encodings. That's a throwback to trying to
have fixed 32-bit instructions.

The goal is to get the bytecode translated to the C++ IR as fast as possible. If that
penalizes writing, so be it.

I totally agree. I also think that disk size should be secondary to decoding speed. Of course, decoding
speed is reduced if the file sizes are MUCH larger, but I think going to a full library like bzip2 was
overkill.

we need to leave hooks in the code for clients that wish to compact the bytecode.

Hooks sound fine to me, I just don't want everything that uses libsupport to be dependent on a
compression library. We can actually remove bzip2 from CVS today, which is a bytecode format
change, and gives us incentive to implement this PR :)

We need to support integer constants > 64bits. This is a "to do" item for my
current project, but we musn't prohibit it in the new design.

That should be trivial with variable bitwidths.

Can we just use ELF? Or is that too verbose?

ELF has nothing interesting to us.

-Chris

[llvmbot]

Okay, sounds like we're in agreement. Thanks for the cc :)

And, let's get this a little closer to working before we go removing the bzip2
library.

Perhaps the place to start is to write the documentation for the new format
first? That way we can hash out alternatives in the bitstream format before
touching implementation.

[lattner]

Sounds good, I will add some notes to your doc when I get a chance.

[lattner]

also, re: bzip2: would you accept defaulting the bc writers to write out uncompressed .bc files? bzip2
does make the files on disk smaller but makes them much much more expensive to read.

[llvmbot]

Sure, defaulting to uncompressed is fine. I just don't want to take the
compression capability away until there's a way to replace it (via an API) so
someone who wants compression can have it (at their expense).

Reid.

[lattner]

Makes sense!

[lattner]

This is done. Welcome bitcode.