llvm dev - Aug 2015 - RFC: alloca -- specify address space for allocation

On 08/26/2015 07:02 PM, Chandler Carruth wrote:
> On Wed, Aug 26, 2015 at 6:46 PM Swaroop Sridhar via llvm-dev 
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
>
>     Currently, the alloca instruction always allocates in the generic
>     address space (0).
>
>     This proposal is to extend the semantics of alloca instruction to
>     allow allocation in any specified address space.
>
>     *Proposed Syntax*
>
>     <result> = alloca [inalloca] <type> [, <ty>
<NumElements>] [,
>     align <alignment>] *[, addrspace <num>]* ; yields type
>     addrspace(num)*:result
>
>     *Motivation*
>
>     Managed language clients typically use address space 1 to
>     represent GC-pointers.
>
>     Some managed clients (CLR, in particular) allow construction of GC
>     pointers to stack locations.
>
>     For example, MSIL instruction ldloca (ECMA 335, p 370) creates a
>     GC pointer to a stack local.
>
>     Creating an addrespace(1)* pointer to a stack location currently
>     involves two steps: the alloca, and an addrspacecast.
>
>     Managed code transformations (ex: RewriteStatepointsForGC) do not
>     handle arbitrary address space casting.
>
>     So, it is desirable to obtain the addrespace(1)* pointer by
>     construction.
>
> I don't have a particular or specific objection here necessarily, but 
> I have to admit I don't understand the use case (yet). I'm hoping
you
> can explain it to me more thoroughly.
>
> What semantics do you expect for GC pointer to a stack location? 
> That's what I don't really understand. Some questions that leap to 
> mind, but may be the wrong questions (so feel free to point me in the 
> right direction here)...
>
> - Can I promote such a location to an SSA register?
> - What does it mean to collect a stack location?
> - Can I merge stack allocations that are GC pointers? Can I re-use 
> them? What semantics do I get?
> - Do GC pointers to stack locations have any different aliasing 
> properties?
> - When the optimizer needs to create a new stack allocation, what 
> address space should it be in?
For the proposed solution, what I think Swaroop is going for is simply 
having a mechanism to distinguish some allocas from others without 
otherwise effecting code generation.  They are still stack based 
objects; they don't escape unless unused at a safepoint; they're not 
relocated.  They may contain pointers to objects which do need to be 
relocated, so we need to have a mechanism to track them.  In particular, 
it would be perfectly legal to promote to SSA since the interior 
pointers would become addrspace(1) SSA values and be handled correctly 
by the relocation logic.

I can't answer the merging question above.  There are entirely sane 
semantics which could be assigned to stack allocation merging, but I'm 
not sure what expectations the CLR GCs have.

Swaroop - If I've misstated anything above, please correct me.
>
> Ultimately, to make this change, you'll also need to change a decent 
> amount of code in the optimizer that will blindly create stack 
> allocations in address space zero.
>
> Without a better understanding of both the motivation and the 
> resulting consequences such as what I've outlined in my questions 
> above, it is very hard for me to feel comfortable with this kind of 
> change.
This is basically my reaction as well.  This seems like a big hammer to 
a problem I'm not sure is actually a nail.
>
>     Thanks,
>
>     Swaroop.
>
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150827/2e710fb2/attachment.html>

Inline.

From: Philip Reames [mailto:listmail at philipreames.com] 
Sent: Thursday, August 27, 2015 1:27 PM
To: Chandler Carruth <chandlerc at google.com>; Swaroop Sridhar
<Swaroop.Sridhar at microsoft.com>; llvm-dev <llvm-dev at
lists.llvm.org>; Sanjoy Das <sanjoy at playingwithpointers.com>
Subject: Re: [llvm-dev] RFC: alloca -- specify address space for allocation
 
>- Can I promote such a location to an SSA register?
>- What does it mean to collect a stack location?
>- Can I merge stack allocations that are GC pointers? Can I re-use them?
What semantics do I get?
-> Do GC pointers to stack locations have any different aliasing
properties?
>- When the optimizer needs to create a new stack allocation, what address
space should it be in?
> For the proposed solution, what I think Swaroop is going for is simply
having a mechanism to distinguish some allocas from others without otherwise
effecting code generation.  They are still stack based objects; they don't
escape unless unused at a safepoint; they're not relocated.  They may
contain pointers  to objects which do need to be relocated, so we need to have a
mechanism to track them.  In particular, it would be perfectly legal to promote
to SSA since the interior pointers would become addrspace(1) SSA values and be
handled correctly by the relocation logic.
> I can't answer the merging question above.  There are entirely sane
semantics which could be assigned to stack allocation merging, but I'm not
sure what expectations the CLR GCs have. 
> Swaroop - If I've misstated anything above, please correct me.  
Yes, the semantics of alloca with a non-zero address-space specification should
behave similar to the regular alloca, followed by a cast of the pointer to that
address-space.
The intention is to use the address-space region annotation to add to the type
specification. Apart from this, stack layout should not be affected.

The aliasing properties are also not expected to be any different from other
addrspace(0) or addrspace(1) pointers.
Maybe I'm not appreciating the aliasing concern here -- Can you please give
an example?

Swaroop.

Some vocabulary, to avoid confusion later:

 - the "alloca" == the pointer to the stack slot that the alloca
   allocated (e.g. %rbp - 0x30)

 - the "value" stored or contained in an alloca == at a given point
   during the execution, what is the N-byte value that is present in
   the location that is the result of the alloca instruction.

This is my understanding of the situation: the allocas in question are
not themselves GC pointers, but the value stored in those allocas are.
We could represent the alloca's as address space 0 pointers if we had
a way to do a precise liveness analysis on them late.

However, I think there is a basic problem with doing a precise late
liveness analysis to determine which allocas live over a safepoint
*contain* a gc reference.  Since the pointee type of a pointer is not
a strong distinction (more so once we finally have a singular "ptr"
pointer type) we can have IR like:

 entry:
  br i1 %cond, label %left, label %right

 left:
  %x = alloca addrspace(1)*
  store addrspace(1)* %gcptr, addrspace(1)** %x
  %xc = bitcast addrspace(1)** %x to i8*
  br label %merge

 right:
  %y = alloca i64
  store i64 42, i64* %y
  %yc = bitcast i64* %y to i8*
  br label %merge

 merge:
  %m = phi i8* [ %xc ] [ %yc ]
  safepoint()
  br i1 %cond, label %left1, label %right1

 right1:
  ret void

 left1:
  %xd = bitcast i8* %m to addrspace(1)**
  %gcptr = load addrspace(1)*, addrspace(1)** %xd
  use(%gcptr)

Now the only thing live over the safepoint is the phi of allocas =`%m` but
depending on control flow the runtime value of `%m` (which
will be an alloca) can either contain a legitimate gc pointer, or
i64 42.

Therefore, if we wish to precisely distinguish, at compile time,
between "normal" allocas that cannot contains gc pointers and
"interesting" allocas that *can contain* gc pointers, then we need to
make the pointer types of the "normal" and "interesting"
allocas
fundamentally different (i.e. be of different address spaces).
However, I think re-using addresspace(1) for this is a mistake, we
should use a second address space for this (addressspace(2) let's say)
that distinguish pointers that point to locations that may *contain*
gc pointers, but are not themselves gc pointers.

-- Sanjoy