Address space extension

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
92 messages Options
12345
Reply | Threaded
Open this post in threaded view
|

Address space extension

Michele Scandale
Hello to everybody,

I would like to start a discussion about a possible extension of address
space concept in LLVM.

The idea was born starting from this discussion in the clang mailing
list (first msg:
http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20130715/084011.html 
- interesting point:
http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20130722/084499.html)
where the fact that "source language level" informations about address
spaces can be useful to perform optimizations in the middle end.

IMHO this information should be a plus that could be *safely* ignored
when not necessary and used where it can provide an improvement in
optimizations. This does not necessary mean the the middle-end (and the
back-ends) must be aware of the semantic of these logical address
spaces, it would be enough just to distinguish between two logically
different address spaces.
The first application I see is alias analysis: for targets that do not
have different physical address spaces (e.g. X86), meaning that in the
IR the 'addrspace' modifier *should* not be present, the knowledge that
two pointers refers to different logical address spaces (e.g. OpenCL
address spaces) can be used to decide the aliasing.

Currently the 'addrspace' modifier refers to target defined address
spaces (physical address spaces), so I would like to know if this
extension is a reasonable approach.
Otherwise changing the 'addrspace' semantic could allow an alternative
way: the middle end would be "automatically" aware of this information
but the address space lowering must be moved elsewhere before the
instruction selection using some language-specific pass the produce the
correct lowering. An issue with this approach is that the
middle-end/back-end pipeline it will rely on a language specific pass or
equivalent mechanism during the instruction selection.

Thanks in advance for the attention and for your future answer.

Best regards,

Michele Scandale
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Matt Arsenault
On 08/07/2013 01:52 PM, Michele Scandale wrote:

IMHO this information should be a plus that could be *safely* ignored when not necessary and used where it can provide an improvement in optimizations. This does not necessary mean the the middle-end (and the back-ends) must be aware of the semantic of these logical address spaces, it would be enough just to distinguish between two logically different address spaces.
The first application I see is alias analysis: for targets that do not have different physical address spaces (e.g. X86), meaning that in the IR the 'addrspace' modifier *should* not be present, the knowledge that two pointers refers to different logical address spaces (e.g. OpenCL address spaces) can be used to decide the aliasing.


There was this patch from a long time ago that never went in to use the address spaces for alias analysis:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129728.html

The decision seems to be that LLVM addrspaces aren't required to not alias. I was thinking of following the suggestion to make the datalayout contain which address spaces can / cannot alias. Alternatively, the tbaa metadata might be appropriate for this, but I haven't looked at how that works.

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Michele Scandale

> There was this patch from a long time ago that never went in to use the
> address spaces for alias analysis:
> http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129728.html
>
> The decision seems to be that LLVM addrspaces aren't required to not
> alias. I was thinking of following the suggestion to make the datalayout
> contain which address spaces can / cannot alias. Alternatively, the tbaa
> metadata might be appropriate for this, but I haven't looked at how that
> works.

Uhm... the fact that that different address spaces may alias is a
problem: target address spaces may alias for whatever reason... This is
an additional aspect that must be analyzed.
Beyond this, my proposal is about adding in a separate way the high
level information to handle that by itself especially for those targets
that do not uses different address spaces in the clang description
target-info like X86. As said in the clang mailing list I think is not
correct to cheat with the translation map to use the IR address spaces
represent OpenCL like address spaces.

With this additional information IMO would be easier to teach the alias
analyzer: by construction the logical address spaces should be
considered disjoint, so having the information about physical and
logical address spaces separated would be fine for the aliasing problem.

What do you think about this?
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Pete Cooper
In reply to this post by Matt Arsenault

On Aug 7, 2013, at 2:07 PM, Matt Arsenault <[hidden email]> wrote:

On 08/07/2013 01:52 PM, Michele Scandale wrote:

IMHO this information should be a plus that could be *safely* ignored when not necessary and used where it can provide an improvement in optimizations. This does not necessary mean the the middle-end (and the back-ends) must be aware of the semantic of these logical address spaces, it would be enough just to distinguish between two logically different address spaces.
The first application I see is alias analysis: for targets that do not have different physical address spaces (e.g. X86), meaning that in the IR the 'addrspace' modifier *should* not be present, the knowledge that two pointers refers to different logical address spaces (e.g. OpenCL address spaces) can be used to decide the aliasing.


There was this patch from a long time ago that never went in to use the address spaces for alias analysis:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129728.html

The decision seems to be that LLVM addrspaces aren't required to not alias. I was thinking of following the suggestion to make the datalayout contain which address spaces can / cannot alias. Alternatively, the tbaa metadata might be appropriate for this, but I haven't looked at how that works.
I haven’t thought about using TBAA metadata, but I think some form of metadata would be useful here.

In the clang discussion (http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20130715/084083.html) you noted that address space 3 could be considered constant.  This is a very useful piece of information in itself, and is something we should have in the metadata.  

I don’t know if CUDA has aliasing address spaces, but that would also be useful to consider.  Something simple like this might work.  Note i’m using the examples from the clang discussion, that is "1 = opencl/cuda global, 2 = opencl_local/cuda_shared, 3 = opencl/cuda constant"


!address_spaces = !{!0, !1, !2, !3}

; Address space tuple.  { address space number, parent address space, additional properties }
!0 = metadata !{ i32 0, !{}, !{} }
!1 = metadata !{ i32 1, !0, !{} }
!2 = metadata !{ i32 2, !0, !{} }
!3 = metadata !{ i32 3, !0, !4 }

!4 = metadata !{ “constant” }


This corresponds to 3 address spaces which all are members of address space 0, but which otherwise do not alias each other.  I think this is roughly how TBAA does things.  You can introduce any nodes in the tree of address spaces you need to make children in the tree alias each other.

Additionally, the last address space is marked as constant which could be used for optimization, e.g. LICM.

The alternative to this is to put everything in LLVM code itself.  Personally I think metadata is better, but were it hard coded in the LLVM code i wouldn’t argue against it.

Thanks,
Pete
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Matt Arsenault
On 08/07/2013 02:34 PM, Pete Cooper wrote:
!address_spaces = !{!0, !1, !2, !3}

; Address space tuple.  { address space number, parent address space, additional properties }
!0 = metadata !{ i32 0, !{}, !{} }
!1 = metadata !{ i32 1, !0, !{} }
!2 = metadata !{ i32 2, !0, !{} }
!3 = metadata !{ i32 3, !0, !4 }

!4 = metadata !{ “constant” }


This corresponds to 3 address spaces which all are members of address space 0, but which otherwise do not alias each other.  I think this is roughly how TBAA does things.  You can introduce any nodes in the tree of address spaces you need to make children in the tree alias each other.



I like that approach

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Michele Scandale
In reply to this post by Pete Cooper
> I don’t know if CUDA has aliasing address spaces, but that would also be
> useful to consider.  Something simple like this might work.  Note i’m
> using the examples from the clang discussion, that is "1 = opencl/cuda
> global, 2 = opencl_local/cuda_shared, 3 = opencl/cuda constant"

You are assuming that the target device has different physical address
spaces (like, PTX or R600 or TCE). What for those one with an unique
address space (e.g. X86, ARM) where all opencl/cuda address spaces are
mapped (correctly) to the target address space 0?

>
> !address_spaces = !{!0, !1, !2, !3}
>
> ; Address space tuple.  { address space number, parent address space,
> additional properties }
> !0 = metadata !{ i32 0, !{}, !{} }
> !1 = metadata !{ i32 1, !0, !{} }
> !2 = metadata !{ i32 2, !0, !{} }
> !3 = metadata !{ i32 3, !0, !4 }
>
> !4 = metadata !{ “constant” }
>
>
> This corresponds to 3 address spaces which all are members of address
> space 0, but which otherwise do not alias each other.  I think this is
> roughly how TBAA does things.  You can introduce any nodes in the tree
> of address spaces you need to make children in the tree alias each other.
>
> Additionally, the last address space is marked as constant which could
> be used for optimization, e.g. LICM.

You mean that 1, 2, 3 do not alias each other, but they all alias with
0, right? The address space 0 in used to represent opencl __private
address space, I think it would not alias with the others...

BTW, I like the approach: it allows a fine description of relationship
between address spaces that can be used in the middle-end, and the
frontend is responsible for the correct emission of this language
specific information. That's great!

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Pete Cooper

On Aug 7, 2013, at 2:54 PM, Michele Scandale <[hidden email]> wrote:

>> I don’t know if CUDA has aliasing address spaces, but that would also be
>> useful to consider.  Something simple like this might work.  Note i’m
>> using the examples from the clang discussion, that is "1 = opencl/cuda
>> global, 2 = opencl_local/cuda_shared, 3 = opencl/cuda constant"
>
> You are assuming that the target device has different physical address spaces (like, PTX or R600 or TCE). What for those one with an unique address space (e.g. X86, ARM) where all opencl/cuda address spaces are mapped (correctly) to the target address space 0?
That seems like something only the backend needs to care about, but it is a very important thing to consider.

You could extend my approach below with one more field which for each address space tells you the HW address space it maps to.  Then the selection DAG builder can use that information (if it exists) to do the translation.  Thats perhaps not the cleanest implementation, but it would work.

I was going to suggest that an alternative is to pass this information in to the load/store instructions in the backend, but it looks like that information is already available.  That is, MachinePointerInfo has a getAddrSpace() method.  This could potentially allow you to optimize MachineInstrs using the same knowledge you have here, e.g., constness for addrspace(3) in MachineLICM.

>
>>
>> !address_spaces = !{!0, !1, !2, !3}
>>
>> ; Address space tuple.  { address space number, parent address space,
>> additional properties }
>> !0 = metadata !{ i32 0, !{}, !{} }
>> !1 = metadata !{ i32 1, !0, !{} }
>> !2 = metadata !{ i32 2, !0, !{} }
>> !3 = metadata !{ i32 3, !0, !4 }
>>
>> !4 = metadata !{ “constant” }
>>
>>
>> This corresponds to 3 address spaces which all are members of address
>> space 0, but which otherwise do not alias each other.  I think this is
>> roughly how TBAA does things.  You can introduce any nodes in the tree
>> of address spaces you need to make children in the tree alias each other.
>>
>> Additionally, the last address space is marked as constant which could
>> be used for optimization, e.g. LICM.
>
> You mean that 1, 2, 3 do not alias each other, but they all alias with 0, right? The address space 0 in used to represent opencl __private address space, I think it would not alias with the others…
Yeah, thats right, i have them all alias 0.  If 0 is private and doesn’t alias anything then thats even better.  Potentially that means that the optimizer will be able to reorder any access to globals with any other access to the stack for example.  That will really help it optimize very well.
>
> BTW, I like the approach: it allows a fine description of relationship between address spaces that can be used in the middle-end, and the frontend is responsible for the correct emission of this language specific information. That's great!
Thanks :)
>


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Michele Scandale
On 08/08/2013 12:24 AM, Pete Cooper wrote:

>
> On Aug 7, 2013, at 2:54 PM, Michele Scandale <[hidden email]> wrote:
>
>>> I don’t know if CUDA has aliasing address spaces, but that would also be
>>> useful to consider.  Something simple like this might work.  Note i’m
>>> using the examples from the clang discussion, that is "1 = opencl/cuda
>>> global, 2 = opencl_local/cuda_shared, 3 = opencl/cuda constant"
>>
>> You are assuming that the target device has different physical address spaces (like, PTX or R600 or TCE). What for those one with an unique address space (e.g. X86, ARM) where all opencl/cuda address spaces are mapped (correctly) to the target address space 0?
> That seems like something only the backend needs to care about, but it is a very important thing to consider.
>
> You could extend my approach below with one more field which for each address space tells you the HW address space it maps to.  Then the selection DAG builder can use that information (if it exists) to do the translation.  Thats perhaps not the cleanest implementation, but it would work.
>
> I was going to suggest that an alternative is to pass this information in to the load/store instructions in the backend, but it looks like that information is already available.  That is, MachinePointerInfo has a getAddrSpace() method.  This could potentially allow you to optimize MachineInstrs using the same knowledge you have here, e.g., constness for addrspace(3) in MachineLICM.

 From here: http://llvm.org/docs/LangRef.html#pointer-type

"The semantics of non-zero address spaces are target-specific."

My interpretation is that address spaces are TARGET dependent, so they
want to represent the physical address spaces. So it is *bad* cheating
with this modifier adding a translation that do not reflect the target
features. The assumption I see is that the backend knows how to handle
the address space numbers used here. So use this modifier would imply
that any backend should be aware of the semantic of opencl/cuda address
spaces.
I discussed about this for a correlated issue in cfe-commits (please
follow the message chain starting from here
http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20130715/084011.html).

The idea of using metadata to represent the mapping sounds good, *but
the semantic of addrspace modifier in the IR must change*.

Do you agree with this?

Indeed the lowering phase of address space must be explicit somewhere.
I agree with you that generically the instruction selection is fine, but
the high level information should not be dropped: the target address
space must be used for the instruction selection but the high level
information must be accessible from the MachineInstr if needed.
 From what I see the MachinePointerInfo::getAddrSpace uses the IR Value*
associated and return the address space saved in the IR. If in the IR we
have the logical address space, somewhere else I expect to have the
physical one (its recomputation may be fine).


>> You mean that 1, 2, 3 do not alias each other, but they all alias with 0, right? The address space 0 in used to represent opencl __private address space, I think it would not alias with the others…
> Yeah, thats right, i have them all alias 0.  If 0 is private and doesn’t alias anything then thats even better.  Potentially that means that the optimizer will be able to reorder any access to globals with any other access to the stack for example.  That will really help it optimize very well.

In the opencl specification is said that the four address spaces are
disjoint, so my conclusion of non aliasing with the others.

I hope that the discussion will bring us to a nice and clear solution :-).

Thanks.

-Michele
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Matt Arsenault
On 08/07/2013 03:52 PM, Michele Scandale wrote:
>
> In the opencl specification is said that the four address spaces are
> disjoint, so my conclusion of non aliasing with the others.
In OpenCL 2.0, you can cast between the generic address space and
global/local/private, so there's also that to consider.

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Erik Schnetter
On 2013-08-07, at 18:55 , Matt Arsenault <[hidden email]> wrote:

> On 08/07/2013 03:52 PM, Michele Scandale wrote:
>>
>> In the opencl specification is said that the four address spaces are disjoint, so my conclusion of non aliasing with the others.
> In OpenCL 2.0, you can cast between the generic address space and global/local/private, so there's also that to consider.


I believe this just means that there is a single equivalent of "void*" that can hold all kinds of pointers and address spaces. Casting forth and back must preserve the address space. If I read the standard correctly, the OpenCL compiler may also compile functions several times, once for each combination of address spaces.

-erik

--
Erik Schnetter <[hidden email]>
http://www.perimeterinstitute.ca/personal/eschnetter/

My email is as private as my paper mail. I therefore support encrypting
and signing email messages. Get my PGP key from http://pgp.mit.edu/.


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Michele Scandale
In reply to this post by Matt Arsenault
On 08/08/2013 12:55 AM, Matt Arsenault wrote:
> On 08/07/2013 03:52 PM, Michele Scandale wrote:
>>
>> In the opencl specification is said that the four address spaces are
>> disjoint, so my conclusion of non aliasing with the others.
> In OpenCL 2.0, you can cast between the generic address space and
> global/local/private, so there's also that to consider.
>
Thanks for correction. My reference was the opencl 1.2 specification.

Considering the case of OpenCL 2.0 IMO we would have another address
space that contains the private, the global and the local address spaces.


-Michele
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Justin Holewinski-2
In reply to this post by Pete Cooper

On Wed, Aug 7, 2013 at 6:24 PM, Pete Cooper <[hidden email]> wrote:

On Aug 7, 2013, at 2:54 PM, Michele Scandale <[hidden email]> wrote:

>> I don’t know if CUDA has aliasing address spaces, but that would also be
>> useful to consider.  Something simple like this might work.  Note i’m
>> using the examples from the clang discussion, that is "1 = opencl/cuda
>> global, 2 = opencl_local/cuda_shared, 3 = opencl/cuda constant"
>
> You are assuming that the target device has different physical address spaces (like, PTX or R600 or TCE). What for those one with an unique address space (e.g. X86, ARM) where all opencl/cuda address spaces are mapped (correctly) to the target address space 0?
That seems like something only the backend needs to care about, but it is a very important thing to consider.

You could extend my approach below with one more field which for each address space tells you the HW address space it maps to.  Then the selection DAG builder can use that information (if it exists) to do the translation.  Thats perhaps not the cleanest implementation, but it would work.

I was going to suggest that an alternative is to pass this information in to the load/store instructions in the backend, but it looks like that information is already available.  That is, MachinePointerInfo has a getAddrSpace() method.  This could potentially allow you to optimize MachineInstrs using the same knowledge you have here, e.g., constness for addrspace(3) in MachineLICM.\

I don't believe MachinePointerInfo is guaranteed to be meaningful for all loads/stores.  It is populated with an llvm::Value*, but loads/stores generated in a backend may not be associated with a Value*.
 
>
>>
>> !address_spaces = !{!0, !1, !2, !3}
>>
>> ; Address space tuple.  { address space number, parent address space,
>> additional properties }
>> !0 = metadata !{ i32 0, !{}, !{} }
>> !1 = metadata !{ i32 1, !0, !{} }
>> !2 = metadata !{ i32 2, !0, !{} }
>> !3 = metadata !{ i32 3, !0, !4 }
>>
>> !4 = metadata !{ “constant” }
>>
>>
>> This corresponds to 3 address spaces which all are members of address
>> space 0, but which otherwise do not alias each other.  I think this is
>> roughly how TBAA does things.  You can introduce any nodes in the tree
>> of address spaces you need to make children in the tree alias each other.
>>
>> Additionally, the last address space is marked as constant which could
>> be used for optimization, e.g. LICM.
>
> You mean that 1, 2, 3 do not alias each other, but they all alias with 0, right? The address space 0 in used to represent opencl __private address space, I think it would not alias with the others…
Yeah, thats right, i have them all alias 0.  If 0 is private and doesn’t alias anything then thats even better.  Potentially that means that the optimizer will be able to reorder any access to globals with any other access to the stack for example.  That will really help it optimize very well.
>
> BTW, I like the approach: it allows a fine description of relationship between address spaces that can be used in the middle-end, and the frontend is responsible for the correct emission of this language specific information. That's great!
Thanks :)
>


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev



--

Thanks,

Justin Holewinski

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Justin Holewinski-2
In reply to this post by Pete Cooper
On Wed, Aug 7, 2013 at 5:34 PM, Pete Cooper <[hidden email]> wrote:

On Aug 7, 2013, at 2:07 PM, Matt Arsenault <[hidden email]> wrote:

On 08/07/2013 01:52 PM, Michele Scandale wrote:

IMHO this information should be a plus that could be *safely* ignored when not necessary and used where it can provide an improvement in optimizations. This does not necessary mean the the middle-end (and the back-ends) must be aware of the semantic of these logical address spaces, it would be enough just to distinguish between two logically different address spaces.
The first application I see is alias analysis: for targets that do not have different physical address spaces (e.g. X86), meaning that in the IR the 'addrspace' modifier *should* not be present, the knowledge that two pointers refers to different logical address spaces (e.g. OpenCL address spaces) can be used to decide the aliasing.


There was this patch from a long time ago that never went in to use the address spaces for alias analysis:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129728.html

The decision seems to be that LLVM addrspaces aren't required to not alias. I was thinking of following the suggestion to make the datalayout contain which address spaces can / cannot alias. Alternatively, the tbaa metadata might be appropriate for this, but I haven't looked at how that works.
I haven’t thought about using TBAA metadata, but I think some form of metadata would be useful here.

In the clang discussion (http://lists.cs.uiuc.edu/pipermail/cfe-commits/Week-of-Mon-20130715/084083.html) you noted that address space 3 could be considered constant.  This is a very useful piece of information in itself, and is something we should have in the metadata.  

I don’t know if CUDA has aliasing address spaces, but that would also be useful to consider.  Something simple like this might work.  Note i’m using the examples from the clang discussion, that is "1 = opencl/cuda global, 2 = opencl_local/cuda_shared, 3 = opencl/cuda constant"


Yes, CUDA does have aliasing address spaces, but that is captured in your tree below.  The generic address space (0) can represent addresses in the shared and global (local and global in OpenCL terms) address spaces.
 

!address_spaces = !{!0, !1, !2, !3}

; Address space tuple.  { address space number, parent address space, additional properties }
!0 = metadata !{ i32 0, !{}, !{} }
!1 = metadata !{ i32 1, !0, !{} }
!2 = metadata !{ i32 2, !0, !{} }
!3 = metadata !{ i32 3, !0, !4 }

!4 = metadata !{ “constant” }


This corresponds to 3 address spaces which all are members of address space 0, but which otherwise do not alias each other.  I think this is roughly how TBAA does things.  You can introduce any nodes in the tree of address spaces you need to make children in the tree alias each other.

Additionally, the last address space is marked as constant which could be used for optimization, e.g. LICM.

The alternative to this is to put everything in LLVM code itself.  Personally I think metadata is better, but were it hard coded in the LLVM code i wouldn’t argue against it.

Perhaps I'm just missing the context of the cfe-dev thread, but are these representing the target-dependent address spaces in the IR, or a language-specific address space mapping that is used to annotate the IR?
 

Thanks,
Pete

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev




--

Thanks,

Justin Holewinski

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Justin Holewinski-2
In reply to this post by Michele Scandale
It's not clear to me how this would work for targets that use the same physical address space for multiple language-specific address spaces.  If a target maps both constant and global to address space 42 (for example), how would the optimizer differentiate between these two?


On Wed, Aug 7, 2013 at 7:15 PM, Michele Scandale <[hidden email]> wrote:
On 08/08/2013 12:55 AM, Matt Arsenault wrote:
On 08/07/2013 03:52 PM, Michele Scandale wrote:

In the opencl specification is said that the four address spaces are
disjoint, so my conclusion of non aliasing with the others.
In OpenCL 2.0, you can cast between the generic address space and
global/local/private, so there's also that to consider.

Thanks for correction. My reference was the opencl 1.2 specification.

Considering the case of OpenCL 2.0 IMO we would have another address space that contains the private, the global and the local address spaces.


-Michele

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev



--

Thanks,

Justin Holewinski

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Matt Arsenault
In reply to this post by Erik Schnetter
On 08/07/2013 04:07 PM, Erik Schnetter wrote:

> On 2013-08-07, at 18:55 , Matt Arsenault <[hidden email]> wrote:
>
>> On 08/07/2013 03:52 PM, Michele Scandale wrote:
>>> In the opencl specification is said that the four address spaces are disjoint, so my conclusion of non aliasing with the others.
>> In OpenCL 2.0, you can cast between the generic address space and global/local/private, so there's also that to consider.
>
> I believe this just means that there is a single equivalent of "void*" that can hold all kinds of pointers and address spaces. Casting forth and back must preserve the address space. If I read the standard correctly, the OpenCL compiler may also compile functions several times, once for each combination of address spaces.
>
> -erik
>
Allowing casts to the specific address spaces makes that not work in the
general case. For example, a function like this could not simply be
duplicated for each address space and have it still work:

void foo(int* x, int is_local)
{
      if (is_local)
      {
           local int* y = (local int*) x;
           // ...
       }
       else
       {
            global int* z = (global int*) z;
            // ...
        }
}

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Michele Scandale
In reply to this post by Justin Holewinski-2
On 08/08/2013 01:36 AM, Justin Holewinski wrote:
> It's not clear to me how this would work for targets that use the same
> physical address space for multiple language-specific address spaces.
>   If a target maps both constant and global to address space 42 (for
> example), how would the optimizer differentiate between these two?
>

I think that the proposal of Pete would imply that in the IR the logical
address spaces are represented with addrspace modifier (3 for constant
and 1 for global) so the optimizer can distinguish the two and using
"address space metadata" can derive properties related to this address
spaces.
During the instruction selection the mapping information are used to
drive the selection phase.

IMO whenever possible both address spaces informations must be maintained.

>
> On Wed, Aug 7, 2013 at 7:15 PM, Michele Scandale
> <[hidden email] <mailto:[hidden email]>> wrote:
>
>     On 08/08/2013 12:55 AM, Matt Arsenault wrote:
>
>         On 08/07/2013 03:52 PM, Michele Scandale wrote:
>
>
>             In the opencl specification is said that the four address
>             spaces are
>             disjoint, so my conclusion of non aliasing with the others.
>
>         In OpenCL 2.0, you can cast between the generic address space and
>         global/local/private, so there's also that to consider.
>
>     Thanks for correction. My reference was the opencl 1.2 specification.
>
>     Considering the case of OpenCL 2.0 IMO we would have another address
>     space that contains the private, the global and the local address
>     spaces.
>
>
>     -Michele
>
>     _________________________________________________
>     LLVM Developers mailing list
>     [hidden email] <mailto:[hidden email]> http://llvm.cs.uiuc.edu
>     http://lists.cs.uiuc.edu/__mailman/listinfo/llvmdev
>     <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>
>
>
>
>
> --
>
> Thanks,
>
> Justin Holewinski

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Justin Holewinski-2



On Wed, Aug 7, 2013 at 7:45 PM, Michele Scandale <[hidden email]> wrote:
On 08/08/2013 01:36 AM, Justin Holewinski wrote:
It's not clear to me how this would work for targets that use the same
physical address space for multiple language-specific address spaces.
  If a target maps both constant and global to address space 42 (for
example), how would the optimizer differentiate between these two?


I think that the proposal of Pete would imply that in the IR the logical address spaces are represented with addrspace modifier (3 for constant and 1 for global) so the optimizer can distinguish the two and using "address space metadata" can derive properties related to this address spaces.
During the instruction selection the mapping information are used to drive the selection phase.

IMO whenever possible both address spaces informations must be maintained.

This worries me a bit.  This would introduce language-specific processing into SelectionDAG.  OpenCL maps address spaces one way, other languages map them in other ways.  Currently, it is the job of the front-end to map pointers into the correct address space for the target (hence the address space map in clang).  With (my understanding of) this proposal, there would be a pre-defined set of language-specific address spaces that the target would need to know about. IMO it should be the job of the front-end to do this mapping.



On Wed, Aug 7, 2013 at 7:15 PM, Michele Scandale
<[hidden email] <mailto:[hidden email]>> wrote:

    On 08/08/2013 12:55 AM, Matt Arsenault wrote:

        On 08/07/2013 03:52 PM, Michele Scandale wrote:


            In the opencl specification is said that the four address
            spaces are
            disjoint, so my conclusion of non aliasing with the others.

        In OpenCL 2.0, you can cast between the generic address space and
        global/local/private, so there's also that to consider.

    Thanks for correction. My reference was the opencl 1.2 specification.

    Considering the case of OpenCL 2.0 IMO we would have another address
    space that contains the private, the global and the local address
    spaces.


    -Michele

    _________________________________________________
    LLVM Developers mailing list
    [hidden email] <mailto:[hidden email]> http://llvm.cs.uiuc.edu
    http://lists.cs.uiuc.edu/__mailman/listinfo/llvmdev

    <http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev>




--

Thanks,

Justin Holewinski




--

Thanks,

Justin Holewinski

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Michele Scandale
On 08/08/2013 02:02 AM, Justin Holewinski wrote:
> This worries me a bit.  This would introduce language-specific
> processing into SelectionDAG.  OpenCL maps address spaces one way, other
> languages map them in other ways.  Currently, it is the job of the
> front-end to map pointers into the correct address space for the target
> (hence the address space map in clang).  With (my understanding of) this
> proposal, there would be a pre-defined set of language-specific address
> spaces that the target would need to know about. IMO it should be the
> job of the front-end to do this mapping.

The begin of the discussion was about possible way to represent high
level address space information in the IR different from target address
spaces (to have the information orthogonally respect the mapping so to
handle also those targets that have the trivial mapping).

My interpretation of the solution proposed by Pete is that the frontend
emits metadata that describe address spaces (overlapping information and
mapping target specific). The instruction selection simply applis the
mapping encoded in the metadata. So there is no pre-defined set, but
there is only a mapping algorithm implemented in the instruction
selection phase "table driven", the table is encoded as metadata.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Pete Cooper

On Aug 7, 2013, at 5:12 PM, Michele Scandale <[hidden email]> wrote:

> On 08/08/2013 02:02 AM, Justin Holewinski wrote:
>> This worries me a bit.  This would introduce language-specific
>> processing into SelectionDAG.  OpenCL maps address spaces one way, other
>> languages map them in other ways.  Currently, it is the job of the
>> front-end to map pointers into the correct address space for the target
>> (hence the address space map in clang).  With (my understanding of) this
>> proposal, there would be a pre-defined set of language-specific address
>> spaces that the target would need to know about. IMO it should be the
>> job of the front-end to do this mapping.
>
> The begin of the discussion was about possible way to represent high level address space information in the IR different from target address spaces (to have the information orthogonally respect the mapping so to handle also those targets that have the trivial mapping).
>
> My interpretation of the solution proposed by Pete is that the frontend emits metadata that describe address spaces (overlapping information and mapping target specific). The instruction selection simply applis the mapping encoded in the metadata. So there is no pre-defined set, but there is only a mapping algorithm implemented in the instruction selection phase "table driven", the table is encoded as metadata.
I think its fair to have this be dealt with by targets instead of the front-end.  That way the optimizer can remain generic and use only the metadata.  CPU targets will just map every address space to 0 as they have only a single physical memory space.  GPU targets such as PTX and R600 can map to the actual HW spaces they want.

This way you have the target specific information in the backend where I believe it should be, and the front-end can target agnostic (note, I know, its not really agnostic and already contains target specific information, but I just don’t want to add more unless its really needed)

On the casting between address spaces topic "you can cast between the generic address space and global/local/private, so there's also that to consider.”.  This terrifies me.  I don’t know how to generate code for this on a system which has disjoint physical memory without branching on every memory access to that address space.
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: Address space extension

Pete Cooper

On Aug 7, 2013, at 6:16 PM, Pete Cooper <[hidden email]> wrote:


On Aug 7, 2013, at 5:12 PM, Michele Scandale <[hidden email]> wrote:

On 08/08/2013 02:02 AM, Justin Holewinski wrote:
This worries me a bit.  This would introduce language-specific
processing into SelectionDAG.  OpenCL maps address spaces one way, other
languages map them in other ways.  Currently, it is the job of the
front-end to map pointers into the correct address space for the target
(hence the address space map in clang).  With (my understanding of) this
proposal, there would be a pre-defined set of language-specific address
spaces that the target would need to know about. IMO it should be the
job of the front-end to do this mapping.

The begin of the discussion was about possible way to represent high level address space information in the IR different from target address spaces (to have the information orthogonally respect the mapping so to handle also those targets that have the trivial mapping).

My interpretation of the solution proposed by Pete is that the frontend emits metadata that describe address spaces (overlapping information and mapping target specific). The instruction selection simply applis the mapping encoded in the metadata. So there is no pre-defined set, but there is only a mapping algorithm implemented in the instruction selection phase "table driven", the table is encoded as metadata.
I think its fair to have this be dealt with by targets instead of the front-end.  That way the optimizer can remain generic and use only the metadata.  CPU targets will just map every address space to 0 as they have only a single physical memory space.  GPU targets such as PTX and R600 can map to the actual HW spaces they want.

This way you have the target specific information in the backend where I believe it should be, and the front-end can target agnostic (note, I know, its not really agnostic and already contains target specific information, but I just don’t want to add more unless its really needed)

On the casting between address spaces topic "you can cast between the generic address space and global/local/private, so there's also that to consider.”.  This terrifies me.  I don’t know how to generate code for this on a system which has disjoint physical memory without branching on every memory access to that address space.
Thinking about this more…  

If you do implement something like alias analysis for address spaces, then casting between address spaces will be unsafe.

Lets say we have 3 address spaces: local, global, all.  Local and global are disjoint, all is the union of the two.

If you cast local to all, or global to all, then alias analysis will be ok as an ‘all’ pointer already aliased local or global.  However, if you cast local to all to global, then you now don’t know if other local pointers alias that so called global pointer or not.  This is analogous to casting int* to float* in C++.  Its undefined behavior according to the spec, and the compiler will optimize it as such.

Personally i’d treat it as undefined behavior and implement your code as such, but i’m no CL/CUDA expert so others may disagree.
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
12345