[LLVMdev] [RFC] 3-bit Waymarking

[Jay Foad]

On 22 April 2014 15:28, Gabor Greif <ggreif at gmail.com> wrote:

> Hi devs,
>
> after my intentionally "playful" EuroLLVM presentation (*) I think it
> would be time to get serious about merging to ToT. But we should
> probably find out whether an optimized algorithm is desired at all.
>
> So I'd solicit comments from the code owners (Use.{h,cpp}) and anybody
> who is interested. For closer scrutiny, the code is here:
> <http://llvm.org/viewvc/llvm-project/llvm/branches/ggreif/waymark-64-new/>
>

Just to stimulate discussion, here's another playful/bizarre idea for
improving the current 2-bit waymarking scheme.

Use this encoding:

00 = s (stop)
01 = 1
10 = 2
11 = 3

Change the order of fields in a Use to be prev, next, value. I think we can
guarantee that the first word of a User has 00 in its low order bits, so if
you try to read just beyond the end of the Use array, it'll look like a
stop tag.

Then the sequence goes like this, where I've used a colon to separate the
real tags (in Uses) from the fake tag (in the first word of the User):

encoding: ...s121s112s32s22s12s3s1s:s
accesses: ...5876576546546545434332:

To decode this, skip digits until you reach a stop tag, and then read all
the digits up to the next stop tag. The digits tell you how far to skip
from the terminating stop tag to the start of the User, using a "3-adic
numeration system" (http://en.wikipedia.org/wiki/Bijective_numeration):

0 = (empty string)
1 = 1
2 = 2
3 = 3
4 = 11
5 = 12
6 = 13
7 = 21
...
13 = 111
14 = 112
15 = 113
16 = 121
...

This is asymptotically better than the current system because it's (more or
less) using base 3 instead of base 2 to encode the skip distances. However,
it's probably not very good in practice, because it needs more accesses
when there are only one or two Uses, which is probably the common case. Oh
well.

Jay.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20140423/c3a9b595/attachment.html>