llvm dev - Sep 2012 - [LLVMdev] [PATCH / PROPOSAL] bitcode encoding that is ~15% smaller for large bitcode files...

On Wed, Sep 26, 2012 at 2:07 AM, Renato Golin <rengolin at
systemcall.org>wrote:
> On 26 September 2012 01:08, Jan Voung <jvoung at chromium.org> wrote:
> > - Forward references will create negative-valued ids (which end up
being
> > written out as large 32-bit integers, as far as I could tell).
>
> Can you use an SLEB-like representation?
>
> It's probably not going to be backwards compatible, but if there
isn't
> an SLEB/ULEB representation in bitcode, I'd say it's a good
> improvement. ;)
>
>
I think most of the instructions operands are encoded as VBR(N)
for some N number of bits, and it seems to me that VBR(8) is like ULEB?
I think that the default N is 6 bits, but I haven't tried tweaking these
parameters.


> --
> cheers,
> --renato
>
> http://systemcall.org/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120926/07294d3c/attachment.html>

On 26 September 2012 22:08, Jan Voung <jvoung at chromium.org>
wrote:
> I think most of the instructions operands are encoded as VBR(N)
> for some N number of bits, and it seems to me that VBR(8) is like ULEB?
> I think that the default N is 6 bits, but I haven't tried tweaking
these
> parameters.
It has a similar purpose, but slightly different. SLEB (the signed
version) wouldn't use the whole word for -1, since the sign expansion
happens after the number is encoded to 7 bits package, so any negative
number that can be represented using 7 bits would still be stored in a
byte.


-- 
cheers,
--renato

http://systemcall.org/

On Thu, Sep 27, 2012 at 2:57 AM, Renato Golin <rengolin at
systemcall.org>wrote:
> On 26 September 2012 22:08, Jan Voung <jvoung at chromium.org> wrote:
> > I think most of the instructions operands are encoded as VBR(N)
> > for some N number of bits, and it seems to me that VBR(8) is like
ULEB?
> > I think that the default N is 6 bits, but I haven't tried tweaking
these
> > parameters.
>
> It has a similar purpose, but slightly different. SLEB (the signed
> version) wouldn't use the whole word for -1, since the sign expansion
> happens after the number is encoded to 7 bits package, so any negative
> number that can be represented using 7 bits would still be stored in a
> byte.
>
>
Ah I see.  It looks like LLVM's bitcode writer does have a signed version
of the VBRs, which is used for integer constants.  I tried using that for
phis and added the data to the *second sheet* in the original
spreadsheet.  See the tab "With SLEB-like Signed VBR for phi",
at the bottom.

It's certainly a bit better (1.3% uncompressed and 0.7% with gzip too),
but it's not always better, and I think it can still be done in a backward
compatible way.

I added numbers for what would happen if we didn't touch phis at all, too.

Finally, checked the average size of individual bc files from a build of
the llvm-test-suite (vs llvm-linked bitcode files), to make sure this isn't
really regressing sizes of small files.  The average size of such
small bitcode object files is ~3.5% better.  Didn't check compression
for that case though...


>
> --
> cheers,
> --renato
>
> http://systemcall.org/
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120927/c3ab8cd6/attachment.html>