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

Inline.

From: Philip Reames [mailto:listmail at philipreames.com] 
Sent: Thursday, August 27, 2015 11:01 AM
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
>>Managed language clients typically use address space 1 to represent
GC-pointers.
>  This is not an entirely accurate statement.  There are currently one in
tree GC strategy which uses addrspace(1) for this purpose and two out of tree
GCs. 
>    Its not really fair to say there's a convention established.  
OK Thanks for the correction. 
Basically, the intention here is that there exists some GC-strategy that uses
address-space annotation to differentiate gc-pointers from native-pointers.
> I'm not directly opposed to this proposal, but I'm not really in
support of it either. 
> I think there a number of smaller engineering changes which could be made
to RewriteStatepointsForGC to address this issue. 
> I am not convinced we need to allow addrspace on allocas to solve that
problem.
> More generally, I'm a bit bothered by how your asserting that a pointer
to a stack based object is the same as a managed pointer into the heap. 
> They share some properties - the GC needs to know about them and mark
through them - but they're also moderately different as well - stack based
>  objects do not get relocated, heap ones do.  Given this differences,
it's not even entirely clear to me that these two classes of pointers should
be treated the same. 
> In particular, I don't see why RewriteStatepointsForGC needs to insert
explicit relocations for stack based objects. 
> That makes no sense to me.
Yes pointers to the stack are different in that they are not relocated or
collected.
However, CLR's "managed pointers" are defined as a super-type of
pointers-to-the GC-heap and pointers-to-unmanaged-memory.
These managed pointers should be reported to the GC. They will be updated during
a collection relocated if the referenced object is relocated.

Wrt the RewriteStatepointsForGC phase:
If we know that a particular managed pointer is definitely coming from an
alloca, it is OK to not report it, and not insert relocations.
However, sometimes we cannot tell this unambiguously, if a managed pointer comes
from a PHI(alloca pointer, heap pointer).
> I think it would help if we took a step back, summarized the requirements,
and approached this anew. 
The real requirement we have is: A way to construct a managed pointer to a stack
location (or any other unmanaged location) such that it is interoperable with
other GC pointers.

The way we do it currently is using addrspacecast:
  %loc0 = alloca i8
  %1 = addrspacecast i8* %loc0 to i8 addrspace(1)*

I'm wondering if:
(a) There is a better way to do this to better suite managed-code
analysis/transformation phases, and
(b) If generating the managed-pointer by construction alloca addrspace(1)* is
the way to do it.

Thanks,
Swaroop.

On 08/27/2015 04:24 PM, Swaroop Sridhar wrote:
> Inline.
>
> From: Philip Reames [mailto:listmail at philipreames.com]
> Sent: Thursday, August 27, 2015 11:01 AM
> 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
>
> *trimmed for length*
>> I'm not directly opposed to this proposal, but I'm not really
in support of it either.
>> I think there a number of smaller engineering changes which could be
made to RewriteStatepointsForGC to address this issue.
>> I am not convinced we need to allow addrspace on allocas to solve that
problem.
>> More generally, I'm a bit bothered by how your asserting that a
pointer to a stack based object is the same as a managed pointer into the heap.
>> They share some properties - the GC needs to know about them and mark
through them - but they're also moderately different as well - stack based
>>   objects do not get relocated, heap ones do.  Given this differences,
it's not even entirely clear to me that these two classes of pointers should
be treated the same.
>> In particular, I don't see why RewriteStatepointsForGC needs to
insert explicit relocations for stack based objects.
>> That makes no sense to me.
> Yes pointers to the stack are different in that they are not relocated or
collected.
> However, CLR's "managed pointers" are defined as a super-type
of pointers-to-the GC-heap and pointers-to-unmanaged-memory.
> These managed pointers should be reported to the GC. They will be updated
during a collection relocated if the referenced object is relocated.
Rather than explaining what your expectations are, can you explain why?  
For example, I'm assuming here that you need to report stack based 
objects exclusively for determining liveness of objects they might 
contain pointers to (i.e. identifying roots).  I'm assuming that the 
actual stack allocation does not get any special magic handling by the 
GC other than marking through it.  Correct?
>
> Wrt the RewriteStatepointsForGC phase:
> If we know that a particular managed pointer is definitely coming from an
alloca, it is OK to not report it, and not insert relocations.
> However, sometimes we cannot tell this unambiguously, if a managed pointer
comes from a PHI(alloca pointer, heap pointer).
This is a sound point.  So the conservatively correct thing to do is to 
relocate all SSA pointers which are either heap objects or stack objects 
(e.g. all managed pointers in your terms).  An inference pass which 
proved that a particular SSA value was based on an alloca (address of a 
stack object) would not need to be relocated, but would need to be 
tracked for liveness purposes?  Right now, we really don't have that 
distinction (live vs needing relocation) within 
RewriteStatepointsForGC.  Do we need to add it?

(Also, I've been expecting to see patches from you fixing bugs in 
RSForGC around alloca handling.  Your using it in ways I never designed 
for, so I'm a bit surprised not to have seen these.  Have you audited 
the code and tested the cases you care about?  Having concrete test 
cases in tree would make a lot of this discussion
easier.)
>
>> I think it would help if we took a step back, summarized the
requirements, and approached this anew.
> The real requirement we have is: A way to construct a managed pointer to a
stack location (or any other unmanaged location) such that it is interoperable
with other GC pointers.
>
> The way we do it currently is using addrspacecast:
>    %loc0 = alloca i8
>    %1 = addrspacecast i8* %loc0 to i8 addrspace(1)*
>
> I'm wondering if:
> (a) There is a better way to do this to better suite managed-code
analysis/transformation phases, and
> (b) If generating the managed-pointer by construction alloca addrspace(1)*
is the way to do it.
I would lean towards one of two approaches:
1) Use an addrspace cast.
2) Add a custom out of tree intrinsic which consumes the alloca address 
and returns a managed pointer.  The lowering for this would be trivial, 
but it would give you a place to customize optimizer behavior if 
needed.  It might also make the semantics a bit more obvious in the IR.

The key bit here is that I think Chandler is right.  You are effectively 
casting a stack allocation *into* a managed pointer. Having something to 
mark that transition seems reasonable.

Of course, having said that all, I'm back to thinking that having a 
marker on the alloca would be somewhat reasonable too.  However, I think 
we need a much stronger justification to change the IR than has been 
provided.  If you can show that the cast based model doesn't work for 
some reason, we can re-evaluate.

Worth noting is that we might be better off introducing an orthogonal 
notion for tracking gc references entirely.  The addrspace mechanism has 
worked, but it is a little bit of a hack. We've talked about the need 
for an opaque pointer type.  Maybe when we actually get around to 
defining that, the alloca case is one we should consider.

Philip

I'm in the process of throwing together a design doc to summarize what I 
know about the stack based object case we need to support for CLR.  You 
can find the in progress draft here:
https://docs.google.com/document/d/1H5am1PyY8n8hc1hIAisDQMgbZDmMgnjU8wdN25YqMbQ/edit?usp=sharing

I'm finding I'm having a hard time tracking the details through all of 
the threads and conversations and figured it would be a good idea to get 
everything centralized into one place.

Philip

On 08/28/2015 09:37 AM, Philip Reames wrote:
> On 08/27/2015 04:24 PM, Swaroop Sridhar wrote:
>> Inline.
>>
>> From: Philip Reames [mailto:listmail at philipreames.com]
>> Sent: Thursday, August 27, 2015 11:01 AM
>> 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
>>
>> *trimmed for length*
>>> I'm not directly opposed to this proposal, but I'm not
really in
>>> support of it either.
>>> I think there a number of smaller engineering changes which could
be
>>> made to RewriteStatepointsForGC to address this issue.
>>> I am not convinced we need to allow addrspace on allocas to solve 
>>> that problem.
>>> More generally, I'm a bit bothered by how your asserting that a
>>> pointer to a stack based object is the same as a managed pointer 
>>> into the heap.
>>> They share some properties - the GC needs to know about them and 
>>> mark through them - but they're also moderately different as
well -
>>> stack based
>>>   objects do not get relocated, heap ones do.  Given this 
>>> differences, it's not even entirely clear to me that these two 
>>> classes of pointers should be treated the same.
>>> In particular, I don't see why RewriteStatepointsForGC needs to
>>> insert explicit relocations for stack based objects.
>>> That makes no sense to me.
>> Yes pointers to the stack are different in that they are not 
>> relocated or collected.
>> However, CLR's "managed pointers" are defined as a
super-type of
>> pointers-to-the GC-heap and pointers-to-unmanaged-memory.
>> These managed pointers should be reported to the GC. They will be 
>> updated during a collection relocated if the referenced object is 
>> relocated.
> Rather than explaining what your expectations are, can you explain 
> why?  For example, I'm assuming here that you need to report stack 
> based objects exclusively for determining liveness of objects they 
> might contain pointers to (i.e. identifying roots).  I'm assuming that 
> the actual stack allocation does not get any special magic handling by 
> the GC other than marking through it.  Correct?
>>
>> Wrt the RewriteStatepointsForGC phase:
>> If we know that a particular managed pointer is definitely coming 
>> from an alloca, it is OK to not report it, and not insert relocations.
>> However, sometimes we cannot tell this unambiguously, if a managed 
>> pointer comes from a PHI(alloca pointer, heap pointer).
> This is a sound point.  So the conservatively correct thing to do is 
> to relocate all SSA pointers which are either heap objects or stack 
> objects (e.g. all managed pointers in your terms).  An inference pass 
> which proved that a particular SSA value was based on an alloca 
> (address of a stack object) would not need to be relocated, but would 
> need to be tracked for liveness purposes? Right now, we really don't 
> have that distinction (live vs needing relocation) within 
> RewriteStatepointsForGC.  Do we need to add it?
>
> (Also, I've been expecting to see patches from you fixing bugs in 
> RSForGC around alloca handling.  Your using it in ways I never 
> designed for, so I'm a bit surprised not to have seen these.  Have you 
> audited the code and tested the cases you care about?  Having concrete 
> test cases in tree would make a lot of this discussion easier.)
>>
>>> I think it would help if we took a step back, summarized the 
>>> requirements, and approached this anew.
>> The real requirement we have is: A way to construct a managed pointer 
>> to a stack location (or any other unmanaged location) such that it is 
>> interoperable with other GC pointers.
>>
>> The way we do it currently is using addrspacecast:
>>    %loc0 = alloca i8
>>    %1 = addrspacecast i8* %loc0 to i8 addrspace(1)*
>>
>> I'm wondering if:
>> (a) There is a better way to do this to better suite managed-code 
>> analysis/transformation phases, and
>> (b) If generating the managed-pointer by construction alloca 
>> addrspace(1)* is the way to do it.
> I would lean towards one of two approaches:
> 1) Use an addrspace cast.
> 2) Add a custom out of tree intrinsic which consumes the alloca 
> address and returns a managed pointer.  The lowering for this would be 
> trivial, but it would give you a place to customize optimizer behavior 
> if needed.  It might also make the semantics a bit more obvious in the 
> IR.
>
> The key bit here is that I think Chandler is right.  You are 
> effectively casting a stack allocation *into* a managed pointer. 
> Having something to mark that transition seems reasonable.
>
> Of course, having said that all, I'm back to thinking that having a 
> marker on the alloca would be somewhat reasonable too.  However, I 
> think we need a much stronger justification to change the IR than has 
> been provided.  If you can show that the cast based model doesn't work 
> for some reason, we can re-evaluate.
>
> Worth noting is that we might be better off introducing an orthogonal 
> notion for tracking gc references entirely.  The addrspace mechanism 
> has worked, but it is a little bit of a hack. We've talked about the 
> need for an opaque pointer type.  Maybe when we actually get around to 
> defining that, the alloca case is one we should consider.
>
> Philip

Inline
> -----Original Message-----
> From: Philip Reames [mailto:listmail at philipreames.com]
> Sent: Friday, August 28, 2015 9:38 AM
> 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 04:24 PM, Swaroop Sridhar wrote:
> > Inline.
> >
> > From: Philip Reames [mailto:listmail at philipreames.com]
> > Sent: Thursday, August 27, 2015 11:01 AM
> > 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
> >
> > *trimmed for length*
> >> I'm not directly opposed to this proposal, but I'm not
really in support of it
> either.
> >> I think there a number of smaller engineering changes which could
be
> made to RewriteStatepointsForGC to address this issue.
> >> I am not convinced we need to allow addrspace on allocas to solve
that
> problem.
> >> More generally, I'm a bit bothered by how your asserting that
a pointer to
> a stack based object is the same as a managed pointer into the heap.
> >> They share some properties - the GC needs to know about them and
> mark through them - but they're also moderately different as well -
stack
> based
> >>   objects do not get relocated, heap ones do.  Given this
differences, it's
> not even entirely clear to me that these two classes of pointers should be
> treated the same.
> >> In particular, I don't see why RewriteStatepointsForGC needs
to insert
> explicit relocations for stack based objects.
> >> That makes no sense to me.
> > Yes pointers to the stack are different in that they are not relocated
or
> collected.
> > However, CLR's "managed pointers" are defined as a
super-type of
> > pointers-to-the GC-heap and pointers-to-unmanaged-memory.
> > These managed pointers should be reported to the GC. They will be
> > updated during a collection relocated if the referenced object is
relocated.
>>
>
> Rather than explaining what your expectations are, can you explain why?
> For example, I'm assuming here that you need to report stack based
objects
> exclusively for determining liveness of objects they might contain pointers
to
> (i.e. identifying roots).  I'm assuming that the actual stack
allocation does not
> get any special magic handling by the GC other than marking through it.
> Correct?
I'm sure about what explanation you're asking. But I think there are a
few different aspects here:
(1) GC-Pointers living in the stack: All pointers to heap objects (including
pointers to the middle of objects) held in stack slots and in registers must be
reported for seeding liveness computation. This part is not CLR specific.
(2) Pointers to stack slots: Pointers to stack locations that are typed as (gc)
managed-pointers need not be reported, because the GC does not handle them.
(3) Managed pointers (which could point to the heap or elsewhere) must be
reported if we cannot definitively establish that don't point to the heap.
> > Wrt the RewriteStatepointsForGC phase:
> > If we know that a particular managed pointer is definitely coming from
an
> alloca, it is OK to not report it, and not insert relocations.
> > However, sometimes we cannot tell this unambiguously, if a managed
> pointer comes from a PHI(alloca pointer, heap pointer).
> This is a sound point.  So the conservatively correct thing to do is to
relocate
> all SSA pointers which are either heap objects or stack objects (e.g. all
> managed pointers in your terms).  
Yes relocating and reporting all managed-pointers will be conservatively
correct.
> An inference pass which proved that a
> particular SSA value was based on an alloca (address of a stack object)
would
> not need to be relocated, but would need to be tracked for liveness
> purposes?  Right now, we really don't have that distinction (live vs
needing
> relocation) within RewriteStatepointsForGC.  Do we need to add it?
If the inference pass can prove that a particular SSA value comes from an
alloca,
we can skip reporting and relocating the alloca pointer -- as an optimization.
As an orthogonal issue -- if the stack location (pointed to) contains any
gc-pointers within it,
then those locations will still need to be considered for reporting/relocation.
> (Also, I've been expecting to see patches from you fixing bugs in
RSForGC
> around alloca handling.  Your using it in ways I never designed for, so
I'm a bit
> surprised not to have seen these.  Have you audited the code and tested the
> cases you care about?  Having concrete test cases in tree would make a lot
of
> this discussion easier.)
RSForGC phase tracks the liveness of alloca pointers. 

For example:
  %loc0 = alloca i8
  %0 = addrspacecast i8* %loc0 to i8 addrspace(1)*, !dbg !10
  %safepoint_token = call i32 (i64, i32, void ()*, i32, i32, ...)
@llvm.experimental.gc.statepoint.p0f_isVoidf(i64 2882400000, i32 0, void
()*@CORINFO_HELP_POLL_GC::JitHelper, i32 0, i32 0, i32 0, i32 0, i8
addrspace(1)* %0)

I had to make some changes in the StatepointLowering to work around some special
handling of alloca pointers.
I did not post it for review yet, to get some more test coverage (with more MSIL
functions).
But I can certainly checkin the test cases (and also prepare the change for
review) if that makes discussion easier.

Swaroop.

> -----Original Message-----
> From: Philip Reames [mailto:listmail at philipreames.com]
> Sent: Friday, August 28, 2015 9:38 AM
> 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
> 
>> I think for the use case you are outlining, an addrspacecast is the
correct IR model --
>> you're specifically saying that it is OK in this case to turn a
pointer from addrspace 0
>> into one for addrspace N because N is your "managed pointer"
set that can be *either*
>> a GC-pointer or a non-GC-pointer. 
>> What the FE is saying is that this is an *acceptable* transition of
addrspace, because your
>> language and runtime semantics have provided for it. 
>> I think the proper way to say that is with a cast.
> The key bit here is that I think Chandler is right.  You are effectively
casting a
> stack allocation *into* a managed pointer. Having something to mark that
> transition seems reasonable.
I think there are two views here:

(1) MSIL level view:
In CLR, the stack, is a part of "managed memory" (which is not the
same as gc-heap, which is managed and garbage-collected memory).
Therefore, all *references* to stack locations are "managed
addresses,"  in the sense that the compiler/runtime exercises certain
control over (values that are) managed-address:
For example: it enforces certain restrictions to guarantee safety -- ex:
lifetime restrictions, non-null requirement in certain contexts, etc.

This is different from a notion of "unmanaged memory" which is for
interoperability with native code.
*Pointers* to unmanaged memory are not controlled by the runtime (ex: do not
provide any safety guarantees).

So, from the language semantics point of view, stack addresses are created as
managed pointers.
Which is why the proposal is to have alloca directly in the managed
address-space seemed natural.

Joseph has written more details in the document that Philip shared out in this
thread.

 (2) A more Lower level IR view:
LLVM creates all stack locations in addrespace(0) for all code, whether it comes
from managed-code or native code.
Of these, Stack locations corresponding to the managed-stack are promoted to
managed-addresses via addrspacecast.
As an optimization, the FrontEnd inserts the addrspace casts only for those
stack locations that are actually address-taken.

If I understand correctly, the recommendation (by Philip, Chandler and David) is
approach (2) because:
(a) No change to Instruction-Set is necessary when the semantics is achievable
via existing instructions.
(b) It saves changing the optimizer to allocate in the correct address-space. 
Looks like the problem here is that: the optimizer is expected to create
type-preserving transformation
by allocating in the correct address-space, but blindly allocates in the default
address space today.
I don't know the LLVM optimizer well enough to have a good estimate of the
magnitude of changes
necessary here. But, I agree that (avoiding) substantial changes to the
optimizer is a strong consideration.
>> You might need N to be a distinct address space from 
>> the one used for GC-pointers and to have similar casts emitted by the
frontend.
Yes, eventually we'll need to differentiate between:
(i) Pointers to unmanaged memory -- which will never be reported to the runtime
(ii) Pointers to GC-heap objects -- which will always be reported to the runtime
(iii) Generic managed pointer -- which may need to be reported if we cannot
establish that it points outside the GC heap.

Currently we report all pointers to the runtime as managed pointers.
This is inefficient because the GC then needs to do extra work to figure out
what kind of pointer it is:
Pointer to a heap object, pointer within a heap object, or outside the heap.
> Of course, having said that all, I'm back to thinking that having a
marker on
> the alloca would be somewhat reasonable too.  However, I think we need a
> much stronger justification to change the IR than has been provided.  If
you
> can show that the cast based model doesn't work for some reason, we can
> re-evaluate.
I don't think we can say that the cast-based model will not work. 
The question is whether alloca addrspace(1)* is a better fit for MSIL semantics,
analysis phases,
and managed-code specific optimizations.

I'm OK if we conclude that we'll keep using the cast model until we hit
a concrete case
where it does not work, or seems architecturally misfit.
> Worth noting is that we might be better off introducing an orthogonal
notion
> for tracking gc references entirely.  The addrspace mechanism has worked,
> but it is a little bit of a hack. We've talked about the need for an
opaque
> pointer type.  Maybe when we actually get around to defining that, the
alloca
> case is one we should consider.
Yes, I'm mainly concerned about getting the right types on the different
kinds of
pointers. If adders space annotation implies more constraints (ex: on layout)
than
what's already necessitated by the type distinction, we should use a
separate
mechanism.

Again, I'm OK if we want to keep using addrspacecast until we hit a concrete
case
where it breaks down.

Swaroop.