llvm dev - Aug 2008 - [LLVMdev] Casting between address spaces and address space semantics

Hi Mon Ping,

I've again attached a patch, wich lets LLVM know about about the relations
between different address spaces. Instead of cramming this info in with
TargetData (with all kinds of unwanted side effects, especially for the IR), I
opted to create a new pass, TargetAddrspaces, which holds this information.
Just like TargetData, this can be added to the passmanager by the tool running
the passes.

Unlike TargetData, however, I wanted to be able to subclass TargetAddrspaces
to change the behaviour. To make this possible, I made TargetAddrspaces an
analysis group, with a default implementation AllDisjointAddrspaces (which, as
the name suggests, returns Disjoint for all combinations). Having a default
implementations is useful, so tools are not required to add a TargetAddrspaces
pass to a passmanager.

The last part of this patch is an addition to InstCombine to make use of this
information: It removes any bitcasts from a subset to a superset address
space. It gets at the address space information by requiring the
TargetAddrspaces analysis, which will give it the default implementation in
all current tools.

So, this requires a minimal amount of changes, the current code won't know
the
difference, and in our custom frontend we provide another implementation of
TargetAddrspaces and things work very well.

There are a number of issues still, though. I'm not 100% sure that using an
Analysis pass for this is correct, but currently only analysis passes can be
grouped (though I have the suspicion that this is mainly a question of naming,
really).

Additionally, the "Writing an LLVM Pass" document states: "There
must be
exactly one default implementation available at all times for an Analysis
Group to be used. Only default implementation can derive from
ImmutablePass."

I'm not completely sure why there cannot be other implementations that
derive from ImmutablePass. In this case, I want to have any implementation of
TargetAddrspaces also derive from ImmutablePass, because it makes sense. In
practice, this works as well, our custom implementeation as well as the
default implementation derive from ImmutablePass and everything compiles and
runs fine. Is this perhaps an outdated statement?

Mon Ping suggests using address space information for alias analysis as well,
which seems to make sense. In effect this is a form of type-based alias
analysis, but different address spaces don't preclude pointers from being
equal. A problem here is that pointers in disjoint address spaces would be
marked as not aliasing, but when the default relation is disjoint this is not
so conservative. This might require an extra option "Unknown", which
can be
used as the default instead of "Disjoint". For Unknown, any pass can
do the
conservative thing.

Lastly, I'm still not so sure if InstCombine is the right place for this
simplification. This needs some more thought, but currently it is a problem
that instcombine does not process BitCastConstantExprs. I might end up writing
a seperate pass for just this.


So again, suggestions welcome.

Gr.

Matthijs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: addrspaces.diff
Type: text/x-diff
Size: 9792 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080807/b63e2bde/attachment.diff>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080807/b63e2bde/attachment.sig>

Hi Matthijs,

Sorry for not responding earlier.  I have a few comments.

On Aug 7, 2008, at 7:41 AM, Matthijs Kooijman wrote:
> Hi Mon Ping,
>
> I've again attached a patch, wich lets LLVM know about about the  
> relations
> between different address spaces. Instead of cramming this info in  
> with
> TargetData (with all kinds of unwanted side effects, especially for  
> the IR), I
> opted to create a new pass, TargetAddrspaces, which holds this  
> information.
> Just like TargetData, this can be added to the passmanager by the  
> tool running
> the passes.
>
> Unlike TargetData, however, I wanted to be able to subclass  
> TargetAddrspaces
> to change the behaviour. To make this possible, I made  
> TargetAddrspaces an
> analysis group, with a default implementation AllDisjointAddrspaces  
> (which, as
> the name suggests, returns Disjoint for all combinations). Having a  
> default
> implementations is useful, so tools are not required to add a  
> TargetAddrspaces
> pass to a passmanager.
>
I don't have a problem having another class, TargetAddrSpace, to store  
this information.  However, I don't think it make sense being a  
standalone pass.  Address spaces seems to part of the TargetData and  
it seems more natural to ask the TargetData to return the  
TargetAddrSpace object  (similar to struct layout) to describe the  
relationships between address spaces.  BTW, there is a comment in  
TargetAddrspaces.h that indicate the default is that all address  
spaces are equivalent. I assume you meant disjoint here.
> The last part of this patch is an addition to InstCombine to make  
> use of this
> information: It removes any bitcasts from a subset to a superset  
> address
> space. It gets at the address space information by requiring the
> TargetAddrspaces analysis, which will give it the default  
> implementation in
> all current tools.
For the case of a GetElementPointer, we are replacing a bitcast to a  
pointer, getelem with a getelem bitcast.  The assumption is the latter  
bitcast will hopefully go away when we iterate through those uses.
>
>
> So, this requires a minimal amount of changes, the current code  
> won't know the
> difference, and in our custom frontend we provide another  
> implementation of
> TargetAddrspaces and things work very well.
>
> There are a number of issues still, though. I'm not 100% sure that  
> using an
> Analysis pass for this is correct, but currently only analysis  
> passes can be
> grouped (though I have the suspicion that this is mainly a question  
> of naming,
> really).
>
> Additionally, the "Writing an LLVM Pass" document states:
"There
> must be
> exactly one default implementation available at all times for an  
> Analysis
> Group to be used. Only default implementation can derive from  
> ImmutablePass."
>
> I'm not completely sure why there cannot be other implementations that
> derive from ImmutablePass. In this case, I want to have any  
> implementation of
> TargetAddrspaces also derive from ImmutablePass, because it makes  
> sense. In
> practice, this works as well, our custom implementeation as well as  
> the
> default implementation derive from ImmutablePass and everything  
> compiles and
> runs fine. Is this perhaps an outdated statement?
>
> Mon Ping suggests using address space information for alias analysis  
> as well,
> which seems to make sense. In effect this is a form of type-based  
> alias
> analysis, but different address spaces don't preclude pointers from  
> being
> equal. A problem here is that pointers in disjoint address spaces  
> would be
> marked as not aliasing, but when the default relation is disjoint  
> this is not
> so conservative. This might require an extra option "Unknown",
which
> can be
> used as the default instead of "Disjoint". For Unknown, any pass
can
> do the
> conservative thing.
What I'm suggesting is that Alias Analysis can be a client to where we  
store address space information.  In the example you gave, alias  
analysis will examine two memory locations, ask the TargetAddressSpace  
what the relationship is and if it is disjoint, it will return no  
alias.  If the address spaces are in subset relationship, the alias  
analysis returns maybe unless it has more information.  If a client  
doesn't tell the compiler the correct address space information, the  
client shouldn't expect correct answers from coming out of the compiler.
>
>
> Lastly, I'm still not so sure if InstCombine is the right place for  
> this
> simplification. This needs some more thought, but currently it is a  
> problem
> that instcombine does not process BitCastConstantExprs. I might end  
> up writing
> a seperate pass for just this.
>
I'm not sure either. At some level, what we want is to propagate the  
most precise address space (or restrict) information to its use.  This  
means that ideally we would want to be able to handle copies of the  
value stored in some temporary and track it all the way through to it  
use.  InstCombine will not handle this case, e.g, address space 1 is a  
subset of 2
    int<1>* ptr = ...
    int<2>* ptr2 = ptr1+4
    *ptr2 = ...

InstCombine will not cleanup this case though a copy propagation phase  
could clean this up.

-- Mon Ping
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080809/fc23945f/attachment.html>

Hi Mon Ping,
> I don't have a problem having another class, TargetAddrSpace, to store
this
> information.  However, I don't think it make sense being a standalone
pass.
>  Address spaces seems to part of the TargetData and it seems more natural 
> to ask the TargetData to return the TargetAddrSpace object  (similar to 
> struct layout) to describe the relationships between address spaces.
This is pretty much what I did in my first patch, but Chris didn't like it.
Currently, the TargetData class can be completely described using it's
string
representation (which is also stored inside a module). Adding address space
information to target data breaks this, unless we also make a string
representation of the address spaces that we can put in a module.

I think that having a seperate class is somewhat cleaner, since it also makes
sure that this info is only made available to the passes that actually use it.
> BTW, there is a comment in TargetAddrspaces.h that indicate the default is
> that all address spaces are equivalent. I assume you meant disjoint here.
Uh, yeah :-)
>> The last part of this patch is an addition to InstCombine to make use
of
>> this information: It removes any bitcasts from a subset to a superset
>> address space. It gets at the address space information by requiring
the
>> TargetAddrspaces analysis, which will give it the default
implementation in
>> all current tools.
>
> For the case of a GetElementPointer, we are replacing a bitcast to a 
> pointer, getelem with a getelem bitcast.  The assumption is the latter 
> bitcast will hopefully go away when we iterate through those uses.
Uh? Is this a comment about what the current code or my patch does, or what it
should do? I don't understand what you mean here.
>> Mon Ping suggests using address space information for alias analysis as
>> well, which seems to make sense. In effect this is a form of type-based
>> alias analysis, but different address spaces don't preclude
pointers from
>> being equal. A problem here is that pointers in disjoint address spaces
>> would be marked as not aliasing, but when the default relation is
disjoint
>> this is not so conservative. This might require an extra option
"Unknown",
>> which can be used as the default instead of "Disjoint". For
Unknown, any
>> pass can do the conservative thing.
>
> What I'm suggesting is that Alias Analysis can be a client to where we 
> store address space information.  In the example you gave, alias analysis 
> will examine two memory locations, ask the TargetAddressSpace what the 
> relationship is and if it is disjoint, it will return no alias.  If the 
> address spaces are in subset relationship, the alias analysis returns maybe
> unless it has more information.  If a client doesn't tell the compiler
the
> correct address space information, the client shouldn't expect correct 
> answers from coming out of the compiler.
True, anyone actually using address space should make sure that this info is
correct anyway. So, no need for an unknown default?
>> Lastly, I'm still not so sure if InstCombine is the right place for
this
>> simplification. This needs some more thought, but currently it is a
problem
>> that instcombine does not process BitCastConstantExprs. I might end up
>> writing a seperate pass for just this.
>
> I'm not sure either. At some level, what we want is to propagate the
most
> precise address space (or restrict) information to its use.
Exactly.
> This means that ideally we would want to be able to handle copies of the
> value stored in some temporary and track it all the way through to it use.
> InstCombine will not handle this case, e.g, address space 1 is a subset of
2
>    int<1>* ptr = ...
>    int<2>* ptr2 = ptr1+4
>    *ptr2 = ...
Won't this code produce a bitcast in the IR, which can be propagated? My
current patch doesn't do this, but it should be easy to extend it to also
propagate a bitcast past pointer arithmetic.

Ie, it should change

%tmp = bitcast i32 addrspace(1)* %ptr1 to i32 addrspace(2)*
%ptr2 = add i32 addrspace(2)* %tmp, 4
store i32 0 i32 addrspace(2)* %ptr2

to 

%tmp  = add i32 addrspace(1)* %ptr, 4
%ptr2 = bitcast %tmp to i32 addrspace(2)
store i32 0 i32 addrspace(2)* %ptr2

and then to 

%ptr2  = add i32 addrspace(1)* %ptr, 4
store i32 0 i32 addrspace(1)* %ptr2

Which shouldn't be too hard?

Coming to think of it, the above won't even use the add instruction, but
will
probably use a GEP to do the +4. The current code already propagates bitcasts
past GEP instructions. Also, I suspect that our C frontends will already
produce the second version of the IR for the C code you give.

Or am I totally missing the point you are making here?


Gr.

Matthijs
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20080811/59bb448b/attachment.sig>