[LLVMdev] Interfacing llvm with a precise, relocating GC

[Philip Reames]

On 10/24/13 3:42 PM, Sanjoy Das wrote:
> Hi Rafael, Andrew,
>
> Thank you for the prompt reply.
>
> One approach we've been considering involves representing the
> constraint "pointers to heap objects are invalidated at every
> safepoint" somehow in the IR itself.
To say this differently, every heap pointer either needs to be remapped 
in place or invalidated and reloaded on next use.  In principal, you 
could use a "trap on access to unmapped page" style read barrier which 
wouldn't require this invariant, but that scheme is undesirable for 
other reasons.  (i.e. performance, unbounded pinning, etc..)

> So, if %a and %b are values the
> GC is interested in, the safepoint at the back-edge of a loop might
> look like:
>
>    ; <label>: body
>      %a = phi i32 [ %a.relocated, %body ] [ %a.initial_value, %pred ]
>      %b = phi i32 [ %b.relocated, %body ] [ %b.initial_value, %pred ]
>      ;; Use %a and %b
>
>      ;; The safepoint starts here
>      %a.relocated = @llvm.gc_relocate(%a)
>      %b.relocated = @llvm.gc_relocate(%b)
>      br %body
>
> This allows us to not bother with relocating derived pointers pointing
> inside %a and %b, since it is semantically incorrect for llvm to reuse
> them in the next iteration of the loop.  We lower gc_relocate to a
> pseudo opcode which lowered into nothing after register allocation.
>
> The problem is, of course, the performance penalty.  Does it make
> sense to get the register allocator "see" the gc_relocate instruction
> as a copy so that they get the same register / slot?  Will that
> violate the intended semantics of gc_relocate (for example, after
> assigning the same register / slot to %a and %a.relocated, are there
> passes that will try to cache derived pointers across loop
> iterations)?
Not a direct response, but building on the idea...

It seems like there might be an entire spectrum of interesting designs 
here.  An initial correct, but slow implementation might introduce 
explicit redefinitions during the initial construction of the IR.  
Alternatively, a separate pass could add these explicit relocations 
before a problematic point in the pipeline if the set of "interesting 
pointers" could be reliably identified.  This would potentially allow 
incremental performance improvement over time with incremental effort.  
I haven't spent the time to establish whether identifying the set of 
"interesting pointers" could be done reliably yet, but I suspect it 
probably could.

Philip