[llvm-dev] RFC: alloca -- specify address space for allocation
Swaroop Sridhar via llvm-dev
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.
Matt Arsenault via llvm-dev
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.
It would be useful to fully avoid all of the special semantics that addrspace(0) implies.
Chandler Carruth via llvm-dev
_______________________________________________
Thanks,
Swaroop.
LLVM Developers mailing list
llvm...@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
Hal Finkel via llvm-dev
> From: "Swaroop Sridhar via llvm-dev" <llvm...@lists.llvm.org>
> To: "llvm-dev" <llvm...@lists.llvm.org>, "Philip Reames" <list...@philipreames.com>, "Sanjoy Das"
> <san...@playingwithpointers.com>
> Sent: Wednesday, August 26, 2015 8:46:08 PM
> Subject: [llvm-dev] RFC: alloca -- specify address space for allocation
>
> 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 .
>
> handle arbitrary address space casting.
>
> So, it is desirable to obtain the addrespace(1)* pointer by
> construction.
>
Is the mental model here that a function using this feature actually has multiple stacks, in different address spaces, and this allows creating local stack allocations in those non-addrspace-0 stacks?
Would there be any defined interaction with @llvm.stacksave/@llvm.stackrestore?
Normally we assume that distinct allocas can't alias, but what about allocas with different address spaces? Can they alias?
-Hal
>
>
> Thanks,
>
> Swaroop.
> _______________________________________________
> LLVM Developers mailing list
> llvm...@lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
--
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory
Matt Arsenault via llvm-dev
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.
Mehdi Amini via llvm-dev
On Aug 26, 2015, at 8:24 PM, Matt Arsenault via llvm-dev <llvm...@lists.llvm.org> wrote:On 08/26/2015 07:02 PM, Chandler Carruth via llvm-dev wrote:
For my use case, some of the assumptions about addrspace(0) don't make any sense, so having the option of not using it for stack allocations would avoid some special case problems. For example, it's assumed that 0 is the address space of code, and stack, but for us these are unrelated concepts and have different pointer sizes. The assumption that 0 is not a valid pointer value is also incorrect, since
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.
we want stack pointers to be a 32-bit offset and 0 is valid. For this use case, all allocas should be created with the same address space, so it could be part of the datalayout. In the backend, we have 3 different memory types we would like to place stack objects, so being able to mark these with different address space IDs would also be helpful (although we wouldn't care about the middle end deciding that some allocas should be in a different address space from a single one specified by the data layout)
Swaroop Sridhar via llvm-dev
Please see inline.
From: Chandler Carruth [mailto:chan...@google.com]
Sent: Wednesday, August 26, 2015 7:03 PM
To: Swaroop Sridhar <Swaroop...@microsoft.com>; llvm-dev <llvm...@lists.llvm.org>; Philip Reames <list...@philipreames.com>; Sanjoy Das <san...@playingwithpointers.com>
Subject: Re: [llvm-dev] RFC: alloca -- specify address space for allocation
On Wed, Aug 26, 2015 at 6:46 PM Swaroop Sridhar via llvm-dev <llvm...@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)...
CLR defines the a kind of GC pointer called “managed pointer” , which can point to a local variable, heap object, parameter, field of a compound type, or element of an array. The semantics of managed pointer is liberally defined to support by-reference passing. For example, in this C# example:
public class Obj { public int i; }
public static int Test() {
Obj obj = new Obj();
int i=0;
…
if(cond) {
Fn(ref i); // managed pointer to a stack location
}
else {
Fn(ref obj.i); // managed pointer to a heap location
}
}
- Can I promote such a location to an SSA register?
The rules for the stack location is the same as any address-taken location.
I don’t think the fact that the generated address is a managed pointer should make a difference.
- What does it mean to collect a stack location?
The stack location is not GCed or relocated.
For a reported managed pointer, if the referenced location is outside the bounds of the GC-heap, the runtime leaves it alone.
- 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?
I’ll answer these questions in my next email.
Marcello Maggioni via llvm-dev
Owen Anderson via llvm-dev
Chandler Carruth via llvm-dev
David Chisnall via llvm-dev
>
> On Wed, Aug 26, 2015 at 8:25 PM Matt Arsenault <Matthew....@amd.com> wrote:
> On 08/26/2015 07:02 PM, Chandler Carruth via llvm-dev wrote:
>>
>> 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.
>>
> For my use case, some of the assumptions about addrspace(0) don't make any sense, so having the option of not using it for stack allocations would avoid some special case problems. For example, it's assumed that 0 is the address space of code, and stack, but for us these are unrelated concepts and have different pointer sizes. The assumption that 0 is not a valid pointer value is also incorrect, since we want stack pointers to be a 32-bit offset and 0 is valid. For this use case, all allocas should be created with the same address space, so it could be part of the datalayout. In the backend, we have 3 different memory types we would like to place stack objects, so being able to mark these with different address space IDs would also be helpful (although we wouldn't care about the middle end deciding that some allocas should be in a different address space from a single one specified by the data layout)
>
> FWIW, these use cases seem really straight forward for address spaces. For example, I don't think any of my questions about the semantics apply. It seems straight forward to define a set of allowed address spaces for allocas in the data layout, and a default address space[1] for them that the optimizer could use if it creates or fuses allocas in ways that leave some ambiguity.
We have patches locally that allow you to specify the address space for allocas in the DataLayout, because in one of our ABIs the stack moves to a non-zero address space. These would be relatively easy to extract, and if it’s an approach that would be useful then I could probably post them for review this week.
Having allocas in two address spaces seems plausible if they’re conceptually on different stacks, but using them for GC’d allocations seems odd, as you’d need to ensure that they were copied if live at the end of the stack frame, effectively turning the model into a collection of garbage collected activation records, rather than a stack. For this use, I suspect that you’d need something more like a gc-alloca instruction, which could be promoted to an SSA register if its address isn’t taken, to a stack allocation if escape analysis can prove that pointers to it don’t persist beyond the end of the function, or to a GC’d heap allocation in other cases.
David
Philip Reames via llvm-dev
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.
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.
I think it would help if we took a step back, summarized the requirements, and approached this anew. I know that some of this has already been discussed off list, but given this has reached the point of making proposals to the community as a whole, I think the conversation needs be in public at this time.
(I'll also reply to a couple of specific points down thread.)
Philip
Philip Reames via llvm-dev
On Wed, Aug 26, 2015 at 6:46 PM Swaroop Sridhar via llvm-dev <llvm...@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?
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.
Philip Reames via llvm-dev
Philip
Philip Reames via llvm-dev
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.
Swaroop Sridhar via llvm-dev
From: Philip Reames [mailto:list...@philipreames.com]
Sent: Thursday, August 27, 2015 1:27 PM
To: Chandler Carruth <chan...@google.com>; Swaroop Sridhar <Swaroop...@microsoft.com>; llvm-dev <llvm...@lists.llvm.org>; Sanjoy Das <san...@playingwithpointers.com>
Subject: Re: [llvm-dev] RFC: alloca -- specify address space for allocation
>- 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.
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?
Sanjoy Das via llvm-dev
- 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
Swaroop Sridhar via llvm-dev
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:list...@philipreames.com]
_______________________________________________
Sanjoy Das via llvm-dev
<Swaroop...@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
Philip Reames via llvm-dev
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 Sridhar via llvm-dev
From: Philip Reames [mailto:list...@philipreames.com]
Sent: Thursday, August 27, 2015 11:01 AM
To: Swaroop Sridhar <Swaroop...@microsoft.com>; llvm-dev <llvm...@lists.llvm.org>; Sanjoy Das <san...@playingwithpointers.com>
Cc: Joseph Tremoulet <jot...@microsoft.com>; Andy Ayers <an...@microsoft.com>; Russell Hadley <rha...@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.
Swaroop Sridhar via llvm-dev
> From: Dr D. Chisnall [mailto:dc...@hermes.cam.ac.uk] On Behalf Of David
> Chisnall
> Sent: Thursday, August 27, 2015 2:26 AM
> To: Chandler Carruth <chan...@google.com>
> Cc: Matt Arsenault <Matthew....@amd.com>; Swaroop Sridhar
> <Swaroop...@microsoft.com>; llvm-dev <llvm...@lists.llvm.org>;
>
> On 27 Aug 2015, at 07:40, Chandler Carruth via llvm-dev <llvm-
To garbage-collect stack locations, or the keep them alive beyond the stack's
natural lifetime.
Only change is to type the pointer to the alloca'ed memory to be compatible
with gc-pointer type, to facilitate their interoperability.
Swaroop Sridhar via llvm-dev
> From: Hal Finkel [mailto:hfi...@anl.gov]
> Sent: Wednesday, August 26, 2015 7:43 PM
> To: Swaroop Sridhar <Swaroop...@microsoft.com>
> <list...@philipreames.com>; Sanjoy Das
> <san...@playingwithpointers.com>
Yes, we can conceptualize the model as multiple stacks in different address-spaces.
Apart from this, there should be no impact on layout. Two distinct allocas can still not alias each other.
Swaroop Sridhar via llvm-dev
> -----Original Message-----
> From: Philip Reames [mailto:list...@philipreames.com]
> Sent: Thursday, August 27, 2015 2:50 PM
> To: Swaroop Sridhar <Swaroop...@microsoft.com>; llvm-dev <llvm-
> d...@lists.llvm.org>; Sanjoy Das <san...@playingwithpointers.com>
> Cc: Joseph Tremoulet <jot...@microsoft.com>; Andy Ayers
> <an...@microsoft.com>; Russell Hadley <rha...@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.
David Chisnall via llvm-dev
>
> David: As I replied to some other messages on this thread, the intention is not
> To garbage-collect stack locations, or the keep them alive beyond the stack's
> natural lifetime.
In that case, I think what you want to do can be represented by a stack allocation followed by an address space cast to AS 1 and pass that to the statepoint and then do an AS cast back after the statepoint.
David
Chandler Carruth via llvm-dev
Philip Reames via llvm-dev
> Inline.
>
> From: Philip Reames [mailto:list...@philipreames.com]
> Sent: Thursday, August 27, 2015 11:01 AM
> To: Swaroop Sridhar <Swaroop...@microsoft.com>; llvm-dev <llvm...@lists.llvm.org>; Sanjoy Das <san...@playingwithpointers.com>
> Cc: Joseph Tremoulet <jot...@microsoft.com>; Andy Ayers <an...@microsoft.com>; Russell Hadley <rha...@microsoft.com>
> Subject: Re: RFC: alloca -- specify address space for allocation
>
>> 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.
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).
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
Philip Reames via llvm-dev
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
Swaroop Sridhar via llvm-dev
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.
Swaroop Sridhar via llvm-dev
> From: Philip Reames [mailto:list...@philipreames.com]
> Sent: Friday, August 28, 2015 9:38 AM
> To: Swaroop Sridhar <Swaroop...@microsoft.com>; llvm-dev <llvm-
> d...@lists.llvm.org>; Sanjoy Das <san...@playingwithpointers.com>
> Cc: Joseph Tremoulet <jot...@microsoft.com>; Andy Ayers
> <an...@microsoft.com>; Russell Hadley <rha...@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.
Joseph Tremoulet via llvm-dev
HF> Is the mental model here that a function using this feature actually has multiple stacks, in different address spaces, and this allows creating local stack allocations in those non-addrspace-0 stacks?
PR> the reason we originally went with addrspaces to mark GC pointers was that the managed and non-managed heaps for us are semantically non-overlapping
PR> 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
CC> these use cases seem really straight forward for address spaces... But this is very different from the idea of using an alloca with an address spaces for GC pointers to stack objects
I think it's an important question whether address spaces are a good fit for what we're trying to model here. So I'll explain my mental model of LLILC's address spaces, and I'd be very interested in feedback on whether this seems like a good fit for LLVM's address space concept, or a bastardization thereof:
[preface: it's been my understanding that dereferences of pointers in different address spaces can alias is semantically meaningful ways; i.e. that it's appropriate to use different address spaces to model different means of indexing the same memory. Some of the comments/questions on this thread seemed to imply instead an expectation that distinct address spaces always reference semantically disjoint storage; if that's a hard assumption, then nothing I'm about to say will make sense and we'll almost certainly need a different mechanism to model GC pointers]
1. The value of an unmanaged/addrspace(0) pointer is an address (in the virtual memory available to the process)
2. The value of a managed/addrspace(1) pointer is conceptually an (ID, offset) pair. The first component is the "identity" of the object that the offset component is relative to. Identity is distinct from address; you could imagine the GC heap allocator having a counter that it increments with each allocation, and that an object's identity is the value the counter had when it was allocated.
3. There are two special reserved IDs for pseudo-objects:
3a. one reserved ID for the null pseudo-object (i.e. what nullptr points to)
3b. one reserved ID for the "everything-outside-the-GC-heap" pseudo-object. Conceptually this is an infinitely-large object and the data at offset N in this object is the data at address N (in the virtual memory available to the process, and with a requirement that N does not correspond to an address in the GC heap)
4. The benefit of this conceptual model is that garbage collections are value-preserving, which is why we don't need to model safepoints as rewriting GC pointers (until the RewriteStatepointsForGC pass where we rewrite the IR in terms of addresses rather than object identity)
5. We know that the representation of an addrspace(1) pointer into the outside-the-GC-heap pseudo-object is bit-identical to the representation of an addrspace(0) pointer to the corresponding address (question: Doesn't that mean we can/should be using bitcast instead of addrspacecast when we know the value in question is an outside-the-GC-heap pointer?)
6. Our source language includes constructs that expose a managed pointer's address (which have well-defined semantics only if the object in question is "pinned"). These naturally correspond to addrspace casts (or maybe need to be additionally constrained?) and are a function of not only the input pointer but also of the layout of the GC heap and the runtime's pinning state. This is where we can get a mix of addrspace(0) and addrspace(1) pointers whose dereferences alias (in semantically well-defined ways).
Again, I'd love feedback on how sane that sounds to those of you familiar with LLVM's address space notion.
I think that 3b is the part that seems to generate the most surprise/consternation. The reason our source language includes the "outside-the-GC-heap" pseudo-object is that it allows more powerful code (you could think of it as allowing polymorphism over GC-heap-ness of inputs) with no adverse effects to the system's typesafety guarantees.
Relating this back to the question of what address space an alloca belongs in (which I'm doing to contextualize, not in an attempt to continue the debate), as the stack (of which there is only one) is outside-the-GC-heap, the question is one of whether you want to conceptualize an alloca as producing an unmanaged address or as producing a pointer into the outside-the-GC-heap pseudo-object. I'd argue that our source language conceptualizes it as the latter[1], which (as Swaroop points out below) is why it would feel natural to model it that way in LLVM, but of course (as Swaroop also points out below) we could also decompose the source construct into two steps in LLVM IR. As far as compiler-introduced allocas, they of course wouldn't be referenced in the source, and so we wouldn't have a hard requirement either way.
Thanks
-Joseph
[1] - To be more pedantic/precise:
- Static allocas are implied by local variable declarations, and those declarations are not annotated with a pointer type
- Our source language includes a compact form that can be used to describe a load or store of a local variable; these compact forms are not annotated with a pointer type
- Everywhere else that our source language refers to the address of a local variable, it uses the managed pointer type
Philip Reames via llvm-dev
agreement here.
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.
Andy Ayers via llvm-dev
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.
Joseph Tremoulet via llvm-dev
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
Marcello Maggioni via llvm-dev
this makes the use case much more clear.
Now though, as far as I would like actually to see supported in LLVM the capability of not having any special meaning assigned to address space 0 your proposal goes slightly in contrast with how I always thought of address spaces in LLVM.
I also have to say that I don’t know deeply how address spaces are meant to be intended in LLVM so my vision of them might be actually off the LLVM-way.
This is how I see them though:
If in OpenCL for example we demark private memory with addrspace(0) and global memory with addrspace(1) what addrspace 0 or 1 tells me is an information about the memory pointed by the pointer (whether it is private or global memory). So it tells me something about the “pointee” and not the pointer.
What you are proposing here though is the opposite if I understood correctly, which is that actually addrspace(1) is telling us an information about the pointer (the fact that is a managed pointer) and nothing about the pointee (which is just some address on the stack I assume).
Still my idea of address spaces and my understanding of what you are trying to do could still be completely wrong … :P
Marcello
Swaroop Sridhar via llvm-dev
> > 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.
>
> 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?
Wrt the impact of the GC-time on performance , just wanted to add that
this really depends on the workload. We've seen some workloads
(ex: compiling large projects using a compiler written in managed code) where
the GC-time was a significant portion of the overall execution time.
In some benchmarks, the particular issue of precisely reporting
(iii) managed pointer vs (ii) object pointer in the GCTables did impact performance.
Anyway, we'll use the conservatively correct method of reporting all Gc-pointers
as (iii) generic managed pointers for bring-up. We can come back to
the distinction between (ii) and (iii) while tuning the performance.
Thanks,
Swaroop.
Joseph Tremoulet via llvm-dev
It sounds like you're understanding correctly what we're trying to do.
Reading your take prompted me to look back over how I came to my understanding of address spaces. I think one part of it was reading a recent RFC[1] which explicitly discusses both aliased and disjoint address spaces. Another aspect was the notion/name of the 'addrspacecast' operation. I wonder: in your usage where address spaces demark private and global memory, is addrspacecast illegal, or does it require copying data around (and if so how would one know how much to copy), or can some memory be both private and global, or ... ? The LangRef does state that "if the address space conversion is legal then both result and operand refer to the same memory location"[2].
At any rate, looking this up led me to the LangRef's section on data layout [3], which indicates that pointers into different address spaces can have different sizes, which is a property of the pointer and not the pointee. So it must be possible that address spaces can tell us something about both pointer and pointee. Sometimes (as in your case) the pointers are the same and only the pointee differs, and I wonder whether it's novel that LLILC's plan is to have the pointees the same and only the pointers differ.
Reading further, I see both that addrspacecast "can be a no-op cast or a complex value modification"[2] and that bitcast "may only be [used on pointers] with the same address space"[4].
So I'm getting the impression that it's ok to have a model with semantically meaningful aliasing between address spaces, but also that anywhere we want to reference a local's address with an addrspace(1) pointer (which is everywhere our source language takes its address), as things stand now we need either to use an addrspace cast which will be assumed to possibly have side-effects, or to round-trip through ptrtoint/inttoptr which I presume will obscure the aliasing information. It certainly gives us a correct place to start from, but (unless I'm misunderstanding and the "complex value modification" type of addrspacecast isn't assumed to have side-effects) I wouldn't be surprised if we come back to this wanting a way to represent a cast across address spaces that's as transparent as a bitcast.
Thanks
-Joseph
[1] - http://lists.llvm.org/pipermail/llvm-dev/2015-August/thread.html#89023
[2] - http://llvm.org/docs/LangRef.html#addrspacecast-to-instruction
[3] - http://llvm.org/docs/LangRef.html#data-layout
[4] - http://llvm.org/docs/LangRef.html#i-bitcast
-----Original Message-----
From: Marcello Maggioni [mailto:mmag...@apple.com]
Sent: Monday, August 31, 2015 10:49 PM
To: Joseph Tremoulet <jot...@microsoft.com>
Cc: Swaroop Sridhar <Swaroop...@microsoft.com>; Philip Reames <list...@philipreames.com>; llvm-dev <llvm...@lists.llvm.org>; Sanjoy Das <san...@playingwithpointers.com>
Subject: Re: [llvm-dev] RFC: alloca -- specify address space for allocation
Thanks,
this makes the use case much more clear.
Now though, as far as I would like actually to see supported in LLVM the capability of not having any special meaning assigned to address space 0 your proposal goes slightly in contrast with how I always thought of address spaces in LLVM.
I also have to say that I don’t know deeply how address spaces are meant to be intended in LLVM so my vision of them might be actually off the LLVM-way.
This is how I see them though:
If in OpenCL for example we demark private memory with addrspace(0) and global memory with addrspace(1) what addrspace 0 or 1 tells me is an information about the memory pointed by the pointer (whether it is private or global memory). So it tells me something about the “pointee” and not the pointer.
What you are proposing here though is the opposite if I understood correctly, which is that actually addrspace(1) is telling us an information about the pointer (the fact that is a managed pointer) and nothing about the pointee (which is just some address on the stack I assume).
Still my idea of address spaces and my understanding of what you are trying to do could still be completely wrong … :P
Marcello
> On 30 Aug 2015, at 19:45, Joseph Tremoulet via llvm-dev <llvm...@lists.llvm.org> wrote:
>
> MM> It is not clear to me if these GC pointers are actually living in
> MM> have two different stacks)
> PR> the reason we originally went with addrspaces to mark GC pointers
> PR> non-overlapping we might be better off introducing an orthogonal
> PR> notion for tracking gc references entirely. The addrspace
> PR> mechanism has worked, but it is a little bit of a hack
> CC> an address spaces for GC pointers to stack objects
> llvm.org%2fcgi-bin%2fmailman%2flistinfo%2fllvm-dev&data=01%7c01%7cjotr
> em%40microsoft.com%7cf2366f15c9204210a02608d2b277eac3%7c72f988bf86f141
> af91ab2d7cd011db47%7c1&sdata=zYbhjIodbTD9pi5YrJouAqZi4ciWLvX2Ai8%2bVJS
> LDbE%3d
David Chisnall via llvm-dev
>
> Reading further, I see both that addrspacecast "can be a no-op cast or a complex value modification"[2] and that bitcast "may only be [used on pointers] with the same address space"[4].
>
> So I'm getting the impression that it's ok to have a model with semantically meaningful aliasing between address spaces, but also that anywhere we want to reference a local's address with an addrspace(1) pointer (which is everywhere our source language takes its address), as things stand now we need either to use an addrspace cast which will be assumed to possibly have side-effects, or to round-trip through ptrtoint/inttoptr which I presume will obscure the aliasing information. It certainly gives us a correct place to start from, but (unless I'm misunderstanding and the "complex value modification" type of addrspacecast isn't assumed to have side-effects) I wouldn't be surprised if we come back to this wanting a way to represent a cast across address spaces that's as transparent as a bitcast.
To give a bit of background on that:
The use case for introducing AS casts as distinct from bitcasts (and not going via inttoptr / ptrtoint) is architectures that have different pointer representations. For example, some microcontrollers have a 16-bit PC and 32-bit address registers, allowing code pointers to be smaller than data pointers. Some GPUs (used to?) use different sized pointers for the various different places in the memory hierarchy. In our architecture, this is even more complicated, because we support two different pointer representations:
- 256-bit (or 128-bit, on newer revisions) memory capabilities, that both identify and grant access to a region of memory and have unforgeability guaranteed by the hardware. In LLVM, we represent these as pointers with AS 0.
- 64-bit legacy-compabible pointers that are implicitly relative to a global capability (and so are only dereferenceable within a restricted range of the process’ virtual address space). In LLVM, we represent these as pointers with AS 0.
For us, an AS cast between AS 0 and AS 200 will succeed if and only if the address is within the current range of the global capability. Any address in AS 0 may alias any address in AS 200 (except in some trivial cases, it’s impossible to determine statically that they don’t), but one value is an integer interpreted as an address, whereas the other is a fat pointer with bounds and permissions enforced in hardware.
David
David Chisnall via llvm-dev
>
> - 256-bit (or 128-bit, on newer revisions) memory capabilities, that both identify and grant access to a region of memory and have unforgeability guaranteed by the hardware. In LLVM, we represent these as pointers with AS 0.
Sorry, this should have been AS 200.
Joseph Tremoulet via llvm-dev
I actually think our use case is somewhat similar in spirit, as one of the key points of our system is treating object identity as unforgeable/unforged (guaranteed by type rules in verified safe code, assumed but unverified in trusted unsafe code).
So the main question left for me is how much of a hinderance the pervasive addrspacecasts we may have will be for optimization. Things like:
- Can two addrspace casts be reordered past each other?
- Can an addrspace cast be reordered across memory dereferences?
- Can two addrspacecasts with the same input value be CSE'd?
- Is an address presumed to be escaped when it is addrspacecasted?
- If we load from a pointer `%p` and from a pointer `%q` which is an addrspacecast of `%p`, will those loads be seen as redundant?
- Can a store to `%p` feeding a load from `%q`, or vice-versa, be replaced with an SSA value?
- Can an addrspacecast be hoisted to where it will be speculatively executed?
Popping up a level: when I have these sorts of questions about an opcode, and I don't see them spelled out in its entry in the LangRef, where should I look? Is there some central place describing such properties, or would I just need to read/test the relevant optimizations?
Thanks
-Joseph
-----Original Message-----
From: Dr D. Chisnall [mailto:dc...@hermes.cam.ac.uk] On Behalf Of David Chisnall
To: Joseph Tremoulet <jot...@microsoft.com>
Cc: Marcello Maggioni <mmag...@apple.com>; llvm-dev <llvm...@lists.llvm.org>
Subject: Re: [llvm-dev] RFC: alloca -- specify address space for allocation
>
> Reading further, I see both that addrspacecast "can be a no-op cast or a complex value modification"[2] and that bitcast "may only be [used on pointers] with the same address space"[4].
>
> So I'm getting the impression that it's ok to have a model with semantically meaningful aliasing between address spaces, but also that anywhere we want to reference a local's address with an addrspace(1) pointer (which is everywhere our source language takes its address), as things stand now we need either to use an addrspace cast which will be assumed to possibly have side-effects, or to round-trip through ptrtoint/inttoptr which I presume will obscure the aliasing information. It certainly gives us a correct place to start from, but (unless I'm misunderstanding and the "complex value modification" type of addrspacecast isn't assumed to have side-effects) I wouldn't be surprised if we come back to this wanting a way to represent a cast across address spaces that's as transparent as a bitcast.
To give a bit of background on that:
The use case for introducing AS casts as distinct from bitcasts (and not going via inttoptr / ptrtoint) is architectures that have different pointer representations. For example, some microcontrollers have a 16-bit PC and 32-bit address registers, allowing code pointers to be smaller than data pointers. Some GPUs (used to?) use different sized pointers for the various different places in the memory hierarchy. In our architecture, this is even more complicated, because we support two different pointer representations:
Chandler Carruth via llvm-dev
Thanks, having that context is very helpful.
I actually think our use case is somewhat similar in spirit, as one of the key points of our system is treating object identity as unforgeable/unforged (guaranteed by type rules in verified safe code, assumed but unverified in trusted unsafe code).
So the main question left for me is how much of a hinderance the pervasive addrspacecasts we may have will be for optimization. Things like:
- Can two addrspace casts be reordered past each other?
- Can an addrspace cast be reordered across memory dereferences?
- Can two addrspacecasts with the same input value be CSE'd?
- Is an address presumed to be escaped when it is addrspacecasted?
- If we load from a pointer `%p` and from a pointer `%q` which is an addrspacecast of `%p`, will those loads be seen as redundant?
- Can a store to `%p` feeding a load from `%q`, or vice-versa, be replaced with an SSA value?
- Can an addrspacecast be hoisted to where it will be speculatively executed?
Popping up a level: when I have these sorts of questions about an opcode, and I don't see them spelled out in its entry in the LangRef, where should I look? Is there some central place describing such properties, or would I just need to read/test the relevant optimizations?