llvm dev - Aug 2015 - [RFC] BasicAA considers address spaces?

Personally I feel the most intuitive approach would be to have an equivalent of
isTriviallyDisjoint for IR; we already have a model for how it would work, and
it could be a TTI call. I’ve kind of wanted this for a while because there’s a
lot of address-space-esque aliasing relationships that can’t be easily modeled
on the IR level.

For example (in our model), we have some constraints like this:

Global memory can’t alias local memory.
Global writeable memory can’t alias global readonly memory (different address
spaces).
Stack memory can’t alias global memory (different address spaces).
Texture reads cannot alias texture writes, because you can’t bind a texture as
readable and writeable at the same time. Texture writes, however, can alias each
other.
Vertex shader outputs can’t really alias each other, even though they are
technically “stores”.
(there’s more where that came from)

These are all very trivial to express in code (the trivially disjoint function
in our backend is like 50 lines of code to cover all the cases), but a few of
them are slightly more complex than “address space A can’t alias B”, so having a
generic callback might be nicer and more powerful than a “does address space A
alias address space B” callback, I think.

—escha

----- Original Message -----
> From: "escha" <escha at apple.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> Cc: "Matt Arsenault" <Matthew.Arsenault at amd.com>,
llvm-dev at lists.llvm.org, "Justin Holewinski"
> <jholewinski at nvidia.com>
> Sent: Sunday, August 9, 2015 7:46:26 AM
> Subject: Re: [llvm-dev] [RFC] BasicAA considers address spaces?
> 
> Personally I feel the most intuitive approach would be to have an
> equivalent of isTriviallyDisjoint for IR; we already have a model
> for how it would work, and it could be a TTI call. I’ve kind of
> wanted this for a while because there’s a lot of address-space-esque
> aliasing relationships that can’t be easily modeled on the IR level.
> 
> For example (in our model), we have some constraints like this:
> 
> Global memory can’t alias local memory.
> Global writeable memory can’t alias global readonly memory (different
> address spaces).
> Stack memory can’t alias global memory (different address spaces).
> Texture reads cannot alias texture writes, because you can’t bind a
> texture as readable and writeable at the same time. Texture writes,
> however, can alias each other.
> Vertex shader outputs can’t really alias each other, even though they
> are technically “stores”.
> (there’s more where that came from)
> 
> These are all very trivial to express in code (the trivially disjoint
> function in our backend is like 50 lines of code to cover all the
> cases), but a few of them are slightly more complex than “address
> space A can’t alias B”, so having a generic callback might be nicer
> and more powerful than a “does address space A alias address space
> B” callback, I think.
Could you provide a specific example of a case where the address space is not
enough? [maybe you did above, but if so, I don't know which one].

Perhaps we should just do the most generic thing: Provide an AA/TTI shim which
allows any target provide an implementation of AA (as part of the chain of AA
passes). Thoughts?

 -Hal
> 
> —escha
-- 
Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

> On Aug 9, 2015, at 2:34 PM, Hal Finkel <hfinkel at anl.gov> wrote:
> 
> ----- Original Message -----
>> From: "escha" <escha at apple.com <mailto:escha at
apple.com>>
>> To: "Hal Finkel" <hfinkel at anl.gov <mailto:hfinkel at
anl.gov>>
>> Cc: "Matt Arsenault" <Matthew.Arsenault at amd.com
<mailto:Matthew.Arsenault at amd.com>>, llvm-dev at lists.llvm.org
<mailto:llvm-dev at lists.llvm.org>, "Justin Holewinski"
>> <jholewinski at nvidia.com <mailto:jholewinski at
nvidia.com>>
>> Sent: Sunday, August 9, 2015 7:46:26 AM
>> Subject: Re: [llvm-dev] [RFC] BasicAA considers address spaces?
>> 
>> Personally I feel the most intuitive approach would be to have an
>> equivalent of isTriviallyDisjoint for IR; we already have a model
>> for how it would work, and it could be a TTI call. I’ve kind of
>> wanted this for a while because there’s a lot of address-space-esque
>> aliasing relationships that can’t be easily modeled on the IR level.
>> 
>> For example (in our model), we have some constraints like this:
>> 
>> Global memory can’t alias local memory.
>> Global writeable memory can’t alias global readonly memory (different
>> address spaces).
>> Stack memory can’t alias global memory (different address spaces).
>> Texture reads cannot alias texture writes, because you can’t bind a
>> texture as readable and writeable at the same time. Texture writes,
>> however, can alias each other.
>> Vertex shader outputs can’t really alias each other, even though they
>> are technically “stores”.
>> (there’s more where that came from)
>> 
>> These are all very trivial to express in code (the trivially disjoint
>> function in our backend is like 50 lines of code to cover all the
>> cases), but a few of them are slightly more complex than “address
>> space A can’t alias B”, so having a generic callback might be nicer
>> and more powerful than a “does address space A alias address space
>> B” callback, I think.
> 
> Could you provide a specific example of a case where the address space is
not enough? [maybe you did above, but if so, I don't know which one].
The texture one is the simplest example I can think of:

Texture writes can alias other texture writes, but cannot alias texture reads,
because under the programming model, textures cannot be bound as both read and
write. This is equivalent to saying:

Loads from AS X can alias each other.
Stores to AS X can alias each other.
Stores to AS X cannot alias loads from AS X.

Therefore, texture reads can be freely reordered (they have no memory
dependencies), even past texture writes. However, texture writes must be ordered
with respect to each other. But they’re all to the same address space.

I suppose you could hack around this particular case by just marking texture
reads as not reading memory (a convenient lie), which I think we’ve already
done.

—escha


-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150809/49ca1f69/attachment.html>

I was lost from the thread at some point.

Making the interface more general sounds good to me. This helps to solve
Escha's concern that targets can know more about aliasing than just
comparing address spaces.

If there are no objections, I'll
1) add a new interface to TTI such as isTriviallyDisjoint. It returns false
by default.
2) create a new AA that checks this interface, and add it to the AA chain.
It could be named TargetAwareAliasAnalysis.

Jingyue

On Sun, Aug 9, 2015 at 2:34 PM, Hal Finkel via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> ----- Original Message -----
> > From: "escha" <escha at apple.com>
> > To: "Hal Finkel" <hfinkel at anl.gov>
> > Cc: "Matt Arsenault" <Matthew.Arsenault at amd.com>,
> llvm-dev at lists.llvm.org, "Justin Holewinski"
> > <jholewinski at nvidia.com>
> > Sent: Sunday, August 9, 2015 7:46:26 AM
> > Subject: Re: [llvm-dev] [RFC] BasicAA considers address spaces?
> >
> > Personally I feel the most intuitive approach would be to have an
> > equivalent of isTriviallyDisjoint for IR; we already have a model
> > for how it would work, and it could be a TTI call. I’ve kind of
> > wanted this for a while because there’s a lot of address-space-esque
> > aliasing relationships that can’t be easily modeled on the IR level.
> >
> > For example (in our model), we have some constraints like this:
> >
> > Global memory can’t alias local memory.
> > Global writeable memory can’t alias global readonly memory (different
> > address spaces).
> > Stack memory can’t alias global memory (different address spaces).
> > Texture reads cannot alias texture writes, because you can’t bind a
> > texture as readable and writeable at the same time. Texture writes,
> > however, can alias each other.
> > Vertex shader outputs can’t really alias each other, even though they
> > are technically “stores”.
> > (there’s more where that came from)
> >
> > These are all very trivial to express in code (the trivially disjoint
> > function in our backend is like 50 lines of code to cover all the
> > cases), but a few of them are slightly more complex than “address
> > space A can’t alias B”, so having a generic callback might be nicer
> > and more powerful than a “does address space A alias address space
> > B” callback, I think.
>
> Could you provide a specific example of a case where the address space is
> not enough? [maybe you did above, but if so, I don't know which one].
>
> Perhaps we should just do the most generic thing: Provide an AA/TTI shim
> which allows any target provide an implementation of AA (as part of the
> chain of AA passes). Thoughts?
>
>  -Hal
>
> >
> > —escha
>
> --
> Hal Finkel
> Assistant Computational Scientist
> Leadership Computing Facility
> Argonne National Laboratory
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org         http://llvm.cs.uiuc.edu
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150812/1bf694dc/attachment.html>