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

Philip: I think there are two separate issues:
1) Handling GC pointers stored in stack locations -- tracking their liveness,
reporting them to the GC. etc.
2) Treating pointers to stack locations as GC-pointers.

I think the two options that you presented here are for solving (1).
I'm trying to solve issue (2) using alloca in addrspace(1).

Basically, we want to create a pointer to a stack location (the location itself
may not have any gc-pointers) and give it a type such that it can be used
interchangeably with GC-pointers.
Today, we can achieve this by using an alloca followed by an addrspacecast. It
could be done in one instruction if the alloca can specify the addrspace of the
pointer created.

The advantage of doing this in one step is, for example, that we can check that
there are no (other) addrspace(0) -> addrspace(1) casts.
(introduced inadvertently by user code or compiler transformations).

Swaroop.
 

From: Philip Reames [mailto:listmail at philipreames.com] 
Sent: Thursday, August 27, 2015 1:47 PM
To: Swaroop Sridhar <Swaroop.Sridhar at microsoft.com>; llvm-dev
<llvm-dev at lists.llvm.org>; Sanjoy Das <sanjoy at
playingwithpointers.com>
Cc: Joseph Tremoulet <jotrem at microsoft.com>; Andy Ayers <andya at
microsoft.com>; Russell Hadley <rhadley at microsoft.com>
Subject: Re: RFC: alloca -- specify address space for allocation

For the record, at least two other implementation strategies to address the
original problem have been discussed.

Option 1 (Rejected) - Explode the stack based object into individual fields
individual fields before the safepoint and store them back into the alloca
afterwards.  Only the exploded SSA values would get listed in the stackmap. 
This could work today, but does not meet a functional requirement.  A pointer to
a stack based object can be escaped and a callee (or another thread) can write
to the field location.  As a result, the reform of the stack based object after
the safepoint can introduce writes which didn't exist in the original
program.

Option 2 - Consider pointers within stack based objects (allocas in addrspace 0)
as being live and add their addresses (not values) to the stackmap.  This could
be done by extending the liveness analysis already in RewriteStatepointsForGC to
consider allocas containing pointers.  There wouldn't be any addrspace casts
involved since the members of the stack based object are addrspace(1) pointers
to start with.  Loading them produces an SSA value which can be relocated as
usual.  I don't remember hearing a clearly expressed reason why this
doesn't work.  I believe there were some concerns about the density/size of
the generated stack maps, but I haven't seen any evaluation of this. 


On 08/26/2015 06:46 PM, Swaroop Sridhar 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.
 
Thanks,
Swaroop.

On Thu, Aug 27, 2015 at 2:40 PM, Swaroop Sridhar
<Swaroop.Sridhar at microsoft.com> wrote:
> Philip: I think there are two separate issues:
> 1) Handling GC pointers stored in stack locations -- tracking their
liveness, reporting them to the GC. etc.
> 2) Treating pointers to stack locations as GC-pointers.
>
> I think the two options that you presented here are for solving (1).
My response has the same problem, so you can basically ignore it.

-- Sanjoy

On 08/27/2015 02:40 PM, Swaroop Sridhar wrote:
> Philip: I think there are two separate issues:
> 1) Handling GC pointers stored in stack locations -- tracking their
liveness, reporting them to the GC. etc.
> 2) Treating pointers to stack locations as GC-pointers.
>
> I think the two options that you presented here are for solving (1).
Your right.  I was focused on (1), mostly because I don't understand the 
challenge with (2).
> I'm trying to solve issue (2) using alloca in addrspace(1).
>
> Basically, we want to create a pointer to a stack location (the location
itself may not have any gc-pointers) and give it a type such that it can be used
interchangeably with GC-pointers.
Can you explain what you mean here?  Is this an issue with being able to 
pass the pointer to a function which expects gc references without 
having to bitcast?  Or is there a lowering challenge I'm not seeing?
> Today, we can achieve this by using an alloca followed by an addrspacecast.
It could be done in one instruction if the alloca can specify the addrspace of
the pointer created.
>
> The advantage of doing this in one step is, for example, that we can check
that there are no (other) addrspace(0) -> addrspace(1) casts.
> (introduced inadvertently by user code or compiler transformations).
Is there a reason that your custom verifier can't use metadata or 
pattern matching to accept these special addrspace casts of allocas?  We 
have a similar custom verifier which uses a metadata based exception 
mechanism which has been pretty successful for us. We've had to 
occasionally fix a dropped metadata issue, but I think we've hit one or 
two of these ever.
>
> Swaroop.
>   
>
> From: Philip Reames [mailto:listmail at philipreames.com]
> Sent: Thursday, August 27, 2015 1:47 PM
> To: Swaroop Sridhar <Swaroop.Sridhar at microsoft.com>; llvm-dev
<llvm-dev at lists.llvm.org>; Sanjoy Das <sanjoy at
playingwithpointers.com>
> Cc: Joseph Tremoulet <jotrem at microsoft.com>; Andy Ayers <andya
at microsoft.com>; Russell Hadley <rhadley at microsoft.com>
> Subject: Re: RFC: alloca -- specify address space for allocation
>
> For the record, at least two other implementation strategies to address the
original problem have been discussed.
>
> Option 1 (Rejected) - Explode the stack based object into individual fields
individual fields before the safepoint and store them back into the alloca
afterwards.  Only the exploded SSA values would get listed in the stackmap. 
This could work today, but does not meet a functional requirement.  A pointer to
a stack based object can be escaped and a callee (or another thread) can write
to the field location.  As a result, the reform of the stack based object after
the safepoint can introduce writes which didn't exist in the original
program.
>
> Option 2 - Consider pointers within stack based objects (allocas in
addrspace 0) as being live and add their addresses (not values) to the stackmap.
This could be done by extending the liveness analysis already in
RewriteStatepointsForGC to consider allocas containing pointers.  There
wouldn't be any addrspace casts involved since the members of the stack
based object are addrspace(1) pointers to start with.  Loading them produces an
SSA value which can be relocated as usual.  I don't remember hearing a
clearly expressed reason why this doesn't work.  I believe there were some
concerns about the density/size of the generated stack maps, but I haven't
seen any evaluation of this.
>
>
> On 08/26/2015 06:46 PM, Swaroop Sridhar 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.
>   
> Thanks,
> Swaroop.
>

Inline.
> -----Original Message-----
> From: Philip Reames [mailto:listmail at philipreames.com]
> Sent: Thursday, August 27, 2015 2:50 PM
> To: Swaroop Sridhar <Swaroop.Sridhar at microsoft.com>; llvm-dev
<llvm-
> dev at lists.llvm.org>; Sanjoy Das <sanjoy at
playingwithpointers.com>
> Cc: Joseph Tremoulet <jotrem at microsoft.com>; Andy Ayers
> <andya at microsoft.com>; Russell Hadley <rhadley at
microsoft.com>
> Subject: Re: RFC: alloca -- specify address space for allocation
> 
> 
> 
> On 08/27/2015 02:40 PM, Swaroop Sridhar wrote:
> > Philip: I think there are two separate issues:
> > 1) Handling GC pointers stored in stack locations -- tracking their
liveness,
> reporting them to the GC. etc.
> > 2) Treating pointers to stack locations as GC-pointers.
> >
> > I think the two options that you presented here are for solving (1).
> Your right.  I was focused on (1), mostly because I don't understand
the
> challenge with (2).
> > I'm trying to solve issue (2) using alloca in addrspace(1).
> >
> > Basically, we want to create a pointer to a stack location (the
location itself
> may not have any gc-pointers) and give it a type such that it can be used
> interchangeably with GC-pointers.
> Can you explain what you mean here?  Is this an issue with being able to
pass
> the pointer to a function which expects gc references without having to
> bitcast?  Or is there a lowering challenge I'm not seeing?
Yes this is a matter of interoperability of the stack and heap pointers, when
passed as managed pointers.
I don't think there is a problem with lowering.
> > Today, we can achieve this by using an alloca followed by an
addrspacecast.
> It could be done in one instruction if the alloca can specify the addrspace
of
> the pointer created.
> >
> > The advantage of doing this in one step is, for example, that we can
check
> that there are no (other) addrspace(0) -> addrspace(1) casts.
> > (introduced inadvertently by user code or compiler transformations).
> Is there a reason that your custom verifier can't use metadata or
pattern
> matching to accept these special addrspace casts of allocas?  We have a
> similar custom verifier which uses a metadata based exception mechanism
> which has been pretty successful for us. We've had to occasionally fix
a
> dropped metadata issue, but I think we've hit one or two of these ever.
OK, let me think about it. 
It is possible to add specific pattern matching cases (to handle specific
addrspacecasts) to analysis phases including RewriteStatepointsForGC.
Apart from alloca, there are some other cases in MSIL (like pinning of GC
pointers) where we'll need to perform the addrspacecast to fo unmanaged
<-> managed pointer conversion. These will also need special handling.

I'm not sure if the analysis will be cumbersome after optimization
transforms -- but likely OK for the case of addrspacecasts fed by alloca.

Swaroop.