[llvm-dev] RFC: alloca -- specify address space for allocation

[Joseph Tremoulet via llvm-dev]

To clarify one point in case people are accidentally talking past each other with mismatched terminology:

Swaroop in his (ii)/(iii) below and Andy in his response are referring to the distinction between what MS/CLR term "object" and "managed" pointers, which corresponds to what LLVM's statepoint doc http://llvm.org/docs/Statepoints.html#base-derived-pointers (and Philip who wrote it) defines as "base" and "derived" pointers respectively.

Philip's response asks " the distinction between a 'generic managed pointer' and a 'managed pointer which happens to point outside the gc heap' is purely an optimization right?", and the answer to that is yes, but I just want to make it clear that that's NOT the distinction that Andy and Swaroop are talking about, and I'm pretty sure everyone agrees that the type system doesn't need different types there.

-Joseph


-----Original Message-----
From: Andy Ayers 
Sent: Monday, August 31, 2015 2:28 PM
To: Philip Reames <listmail at philipreames.com>; 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>; Russell Hadley <rhadley at microsoft.com>
Subject: RE: RFC: alloca -- specify address space for allocation

Re "object" vs "managed" pointer....

Given the ability to have GC references in structs we likely see a higher volume of live references at a safepoint than what you're used to seeing in Java (hence our concerns about the IR costs of safepoints and the way on-stack references will be described). But admittedly GCs are rare.

>From an operational standpoint the distinction is indeed an optimization -- managed pointers require extra work during a GC -- first because they may not point into the GC heap at all, and second because if they do point into the GC heap the relevant object header must be located, and third there is bookkeeping for the fixup work needed when they do point into the heap and the objects are relocated during GC. 

During our bring-up I believe we're reporting everything as a managed pointer and we don't expect that to cause any serious problems. Any perf impact is likely to be swamped right now by other dumb things we're doing elsewhere.

However there's another angle -- managed pointers are relatively rare and GC reporting is tricky to get right. We'd like to the compiler to make the strongest assertions possible and the runtime verify where it can. So if we think a pointer refers to the root of a heap object we'd like to describe it that way for the GC.

At any rate I'm not sure we'd ask for a third class of pointer. We can likely sort out object vs managed with some late approximate data flow.

-----Original Message-----
From: Philip Reames [mailto:listmail at philipreames.com]
Sent: Monday, August 31, 2015 10:14 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

A couple of minor responses inline, but I think we're mostly in agreement here.

On 08/28/2015 09:30 PM, Swaroop Sridhar wrote:
>> -----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.
Slight restatement: The only legal address space for an alloca is zero today.  As a result, blindly creating addrspace zero allocas is correct by construction.  If we introduced additional address spaces for allocas, then it would become a problem.
>
>>> 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.
Unless I misunderstand you, it really sounds like the distinction between a 'generic managed pointer' and a 'managed pointer which happens to point outside the gc heap' is purely an optimization right?  I'm generally hesitant to introduce new concepts for optimization benefit without evidence that the optimization is needed.  I'll note that I have no direct experience with a language with GC and stack based allocation, so it's possible I'm underestimating how important this is.

Side note: One of the things that's really bugging me is that you seem to be optimizing for work performed by the collector at safepoints.  My mental model is that safepoints are infrequent and that a minor amount of additional work at the safepoint doesn't really matter.  What am I missing here?  Polling for a safepoint has to happen pretty frequently, but we don't need to parse the stack unless we actually call into the collector right?
>
>> 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.
Great.  We can revisit if needed.
>
>> 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.
Me too honestly.  I think we need to address this relative soon. Not immediately, but probably not 5 years from now either.
>
> Again, I'm OK if we want to keep using addrspacecast until we hit a 
> concrete case where it breaks down.
>
> Swaroop.
>