Address space extension

Project Infrastructure LLVM Dev List Archives
#1

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

#2

There was this patch from a long time ago that never went in to use the address spaces for alias analysis: 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.

#3

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?

#4

There was this patch from a long time ago that never went in to use the address spaces for alias analysis: 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

#5

I like that approach

#6

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!

#7

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 :slight_smile:

#8

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

#9

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

#10

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

#11

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

#12

>> 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*.

#13

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?

#14

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?

#15

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;
            // ...
        }
}

#16

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.

#17

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.

#18

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.

#19

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.

#20

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.