[LLVMdev] Fwd: [RFC] 3-bit Waymarking

[Jay Foad]

I forgot to Cc this (and some other unimportant replies) to the list.

Jay.

---------- Forwarded message ----------
From: Jay Foad <jay.foad at gmail.com>
Date: 23 April 2014 09:50
Subject: Re: [LLVMdev] [RFC] 3-bit Waymarking
To: Gabor Greif <ggreif at gmail.com>


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

Hi Gabor,

I've looked at your slides. I have two comments about the new
waymarking scheme, as described in your "Comparison" slide.


1. I assert without proof :-) that most Values have two Uses, so by
far the worst thing about the current scheme is that it takes *2*
accesses to get from the penultimate Use to the User. When you upgrade
from 2 to 3 bits you get four more tags to play with, so how about
using one or more of them as additional Full Stop tags, that tell you
exactly how far away the user is? E.g. if you created four more full
stop tags you could go from this access pattern:

2 bits: ...654654343221

to this:

3 bits: ...543432211111

I realise that this is asymptotically worse than your scheme, but I
reckon it might be better in the very common case where there are few
Uses.


2. Your "number of accesses" is a bit misleading. I think all the
numbers should be increased by one, because after following the
waymarks we *always* look at the next word as well, to see whether it
is the start of the User, or a pointer to the User. So another way of
spending the four new tags would be to have different kinds of full
stop:

S = full Stop, User follows inline
P = full stoP, Pointer to User follows

This avoids the extra access in the (hopefully common) case where the
User follows inline.


I reckon these two ideas can be combined, e.g. you could have five
full stop bits as follows:

P = full stoP, Pointer to User follows
S0 = full Stop, User follows inline after this Use
S1 = full Stop, User follows inline after 1 more Use
S2 = full Stop, User follows inline after 2 more Uses
S3 = full Stop, User follows inline after 3 more Uses

This would optimise for the case where the Uses are inline, and there
are <= 4 of them.

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