[RFC] BasicAA considers address spaces?

  • the new llvm-dev

+1 to the general idea of a target dependent hook for describing aliasing of address spaces. I have no opinion on the particular implementation strategy proposed.

We definitely need something to handle this. I think a TTI::addressSpaceAlias is a good idea, although I don’t think this fully solves the language vs. target address space distinction a metadata based approach was supposed to handle although it would be easier to implement. For our GPU purposes this would mostly be enough. For example, the fact that in OpenCL local vs. global pointers won’t alias is a useful distinction, even though for a CPU target those will all be mapped to address space 0 so in some cases the frontend knows more about aliasing address spaces than the target. -Matt

+ the new llvm-dev

Hi folks,

Unsurprisingly, leveraging the fact that certain address spaces don't
alias can significantly improve alias analysis precision and enhance
(observably 2x performance gain) load/store optimizations such as LICM and
DSE.

Not shocking

This sounds to me an overdue feature. I saw several discussion threads on
that direction, but none of them really happened.

(1)
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129615.html.
Justin Holewinski proposed to add an address-space alias analysis that
treats pointers in different address spaces not aliasing. This patch got
shot down because, in some targets, address spaces may alias. For example,
in CUDA+NVPTX, addrspace(0) aliases everyone.

ITYM other addrspace may alias addrspace(0).

Sorry to be pedantic, but i think it's important to make sure we are
all on the same page that backends can't change the aliasing behavior
of the default address space, only the aliasing behavior of the other
address spaces.

So, can we make BasicAA to consider address spaces? Specifically, I am
proposing:
a) adding a new interface like TTI::addressSpacesAlias(unsigned,
unsigned), and
b) adding a little piece of logic in BasicAA that reports "no alias" if
address spaces don't alias.

This approach addresses the issue brought up in (2) because TTI can see
the entire codegen. It also resolves the issue that shut down (1) because it
allows address spaces to alias in a target-defined way. Actually, John
Criswell did mention in that thread the idea of embedding alias info in
TargetData. Now that we have TTI, it seems a better place to hold
target-specific alias info than DataLayout.

Any comments?

First, I agree this is a really useful feature to have.
If it really is target specific (and it seems to be), ISTM like TTI is
the right place to add a hook.

However, i'd still rather see it as a pass (as it was in 2011) and
something exposing the AA interface, than further push things into
basicaa.

It's not at all clear to me why basicaa should have this knowledge.

But this is a mild preference, if others think this is a bad idea, ...

Are you saying that we can't say address space 0 doesn't alias other address spaces? In this case we really need to fix LLVM's concept of default address space because this is highly problematic for us. We're constrained to use it in some cases because we can't alloca in a different address space, but ideally if we have problems like this we wouldn't ever use address space 0.

-Matt

Sorry to be pedantic, but i think it's important to make sure we are
all on the same page that backends can't change the aliasing behavior
of the default address space, only the aliasing behavior of the other
address spaces.

Are you saying that we can't say address space 0 doesn't alias other address
spaces?

No.
I'm saying "your target can't directly change what address space 0's
aliasing properties are".

So if you wanted to say "on NVPTX, address space 0 aliases *everything
in the world, including everything in address space 0*", that is not
okay.

If they want to say "on NVPTX, all non-default address spaces alias
everything in address space 0", that is fine.
(Note: This does end up changing what alias queries return for
pointers in different address spaces, but it has no effect on two
pointers solely in address space 0)

In practice, because you can change the properties *of the other
address spaces*, and mayAlias is a symmetric relationship, it doesn't
matter for this.

But he wrote " For example,

in CUDA+NVPTX, addrspace(0) aliases everyone."

This is pedantically wrong. CUDA+NVPTX cannot and does not change the
behavior of aliasing in address space 0, it changes the behavior of
aliasing in all the other address spaces so that they alias pointers
in address space 0 :P.

(As i said, it's really pedantic, but we need to be absolutely clear
that targets do not control the properties of address space 0)

>>
>> Sorry to be pedantic, but i think it's important to make sure we are
>> all on the same page that backends can't change the aliasing behavior
>> of the default address space, only the aliasing behavior of the other
>> address spaces.
>
> Are you saying that we can't say address space 0 doesn't alias other
address
> spaces?

No.
I'm saying "your target can't directly change what address space 0's
aliasing properties are".

So if you wanted to say "on NVPTX, address space 0 aliases *everything
in the world, including everything in address space 0*", that is not
okay.

If they want to say "on NVPTX, all non-default address spaces alias
everything in address space 0", that is fine.
(Note: This does end up changing what alias queries return for
pointers in different address spaces, but it has no effect on two
pointers solely in address space 0)

In practice, because you can change the properties *of the other
address spaces*, and mayAlias is a symmetric relationship, it doesn't
matter for this.

But he wrote " For example,
>> in CUDA+NVPTX, addrspace(0) aliases everyone."

This is pedantically wrong. CUDA+NVPTX cannot and does not change the
behavior of aliasing in address space 0, it changes the behavior of
aliasing in all the other address spaces so that they alias pointers
in address space 0 :P.

Yes. We are on the same page. I was talking about whether two address
spaces alias instead of pointers within the same address space aliasing.

> + the new llvm-dev
>
>>
>> Hi folks,
>>
>> Unsurprisingly, leveraging the fact that certain address spaces don't
>> alias can significantly improve alias analysis precision and enhance
>> (observably 2x performance gain) load/store optimizations such as LICM
and
>> DSE.

Not shocking

>>
>> This sounds to me an overdue feature. I saw several discussion threads
on
>> that direction, but none of them really happened.
>>
>> (1)
>>
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129615.html
.
>> Justin Holewinski proposed to add an address-space alias analysis that
>> treats pointers in different address spaces not aliasing. This patch got
>> shot down because, in some targets, address spaces may alias. For
example,
>> in CUDA+NVPTX, addrspace(0) aliases everyone.

ITYM other addrspace may alias addrspace(0).

Sorry to be pedantic, but i think it's important to make sure we are
all on the same page that backends can't change the aliasing behavior
of the default address space, only the aliasing behavior of the other
address spaces.

>>
>> So, can we make BasicAA to consider address spaces? Specifically, I am
>> proposing:
>> a) adding a new interface like TTI::addressSpacesAlias(unsigned,
>> unsigned), and
>> b) adding a little piece of logic in BasicAA that reports "no alias" if
>> address spaces don't alias.

>>
>> This approach addresses the issue brought up in (2) because TTI can see
>> the entire codegen. It also resolves the issue that shut down (1)
because it
>> allows address spaces to alias in a target-defined way. Actually, John
>> Criswell did mention in that thread the idea of embedding alias info in
>> TargetData. Now that we have TTI, it seems a better place to hold
>> target-specific alias info than DataLayout.
>>
>> Any comments?

First, I agree this is a really useful feature to have.
If it really is target specific (and it seems to be), ISTM like TTI is
the right place to add a hook.

However, i'd still rather see it as a pass (as it was in 2011) and
something exposing the AA interface, than further push things into
basicaa.

It's not at all clear to me why basicaa should have this knowledge.

Either way sounds fine with me.

+ the new llvm-dev

Hi folks,

Unsurprisingly, leveraging the fact that certain address spaces don't
alias can significantly improve alias analysis precision and enhance
(observably 2x performance gain) load/store optimizations such as LICM and
DSE.

This sounds to me an overdue feature. I saw several discussion threads on
that direction, but none of them really happened.

(1)
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129615.html.
Justin Holewinski proposed to add an address-space alias analysis that
treats pointers in different address spaces not aliasing. This patch got
shot down because, in some targets, address spaces may alias. For example,
in CUDA+NVPTX, addrspace(0) aliases everyone.

(2) http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064620.html.
Michele Scandale proposed address space extensions in IR metadata which
TBAA could then leverage to prove non-aliasing. This approach didn't fly
either because address spaces are target-specific. The front end doesn't
know enough to decide aliasing.

So, can we make BasicAA to consider address spaces? Specifically, I am
proposing:
a) adding a new interface like TTI::addressSpacesAlias(unsigned,
unsigned), and
b) adding a little piece of logic in BasicAA that reports "no alias" if
address spaces don't alias.

This approach addresses the issue brought up in (2) because TTI can see
the entire codegen. It also resolves the issue that shut down (1) because
it allows address spaces to alias in a target-defined way. Actually, John
Criswell did mention in that thread the idea of embedding alias info in
TargetData. Now that we have TTI, it seems a better place to hold
target-specific alias info than DataLayout.

Any comments?

Jingyue

We definitely need something to handle this.

I think a TTI::addressSpaceAlias is a good idea, although I don't think
this fully solves the language vs. target address space distinction a
metadata based approach was supposed to handle although it would be easier
to implement. For our GPU purposes this would mostly be enough. For
example, the fact that in OpenCL local vs. global pointers won't alias is a
useful distinction, even though for a CPU target those will all be mapped
to

Thanks for pointing this out, Matt. In that case, I'd suggest LLVM have
both TTI- and metadata-based approaches, the former for targets being more
knowledgeable, and the latter for front-ends being more knowledgeable. They
are quite orthogonal.

From: "Jingyue Wu" <jingyue@google.com>
To: "Matt Arsenault" <Matthew.Arsenault@amd.com>
Cc: llvm-dev@lists.llvm.org, "Hal Finkel" <hfinkel@anl.gov>, "Justin
Holewinski" <jholewinski@nvidia.com>, "Eli Bendersky"
<eliben@google.com>, "Xuetian Weng" <xweng@google.com>
Sent: Friday, August 7, 2015 3:44:29 PM
Subject: Re: [RFC] BasicAA considers address spaces?

> > + the new llvm-dev
>

>

> > > Hi folks,
> >
>

> > > Unsurprisingly, leveraging the fact that certain address spaces
> > > don't
> > > alias can significantly improve alias analysis precision and
> > > enhance
> > > (observably 2x performance gain) load/store optimizations such
> > > as
> > > LICM and DSE.
> >
>

> > > This sounds to me an overdue feature. I saw several discussion
> > > threads on that direction, but none of them really happened.
> >
>

> > > (1)
> > > http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129615.html
> > > . Justin Holewinski proposed to add an address-space alias
> > > analysis
> > > that treats pointers in different address spaces not aliasing.
> > > This
> > > patch got shot down because, in some targets, address spaces
> > > may
> > > alias. For example, in CUDA+NVPTX, addrspace(0) aliases
> > > everyone.
> >
>

> > > (2)
> > > http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064620.html
> > > .
> > > Michele Scandale proposed address space extensions in IR
> > > metadata
> > > which TBAA could then leverage to prove non-aliasing. This
> > > approach
> > > didn't fly either because address spaces are target-specific.
> > > The
> > > front end doesn't know enough to decide aliasing.
> >
>

> > > So, can we make BasicAA to consider address spaces?
> > > Specifically,
> > > I
> > > am proposing:
> >
>

> > > a) adding a new interface like
> > > TTI::addressSpacesAlias(unsigned,
> > > unsigned), and
> >
>

> > > b) adding a little piece of logic in BasicAA that reports "no
> > > alias"
> > > if address spaces don't alias.
> >
>

> > > This approach addresses the issue brought up in (2) because TTI
> > > can
> > > see the entire codegen. It also resolves the issue that shut
> > > down
> > > (1) because it allows address spaces to alias in a
> > > target-defined
> > > way. Actually, John Criswell did mention in that thread the
> > > idea
> > > of
> > > embedding alias info in TargetData. Now that we have TTI, it
> > > seems
> > > a
> > > better place to hold target-specific alias info than
> > > DataLayout.
> >
>

> > > Any comments?
> >
>

> > > Jingyue
> >
>

> We definitely need something to handle this.

> I think a TTI::addressSpaceAlias is a good idea, although I don't
> think this fully solves the language vs. target address space
> distinction a metadata based approach was supposed to handle
> although it would be easier to implement. For our GPU purposes this
> would mostly be enough. For example, the fact that in OpenCL local
> vs. global pointers won't alias is a useful distinction, even
> though
> for a CPU target those will all be mapped to

Thanks for pointing this out, Matt. In that case, I'd suggest LLVM
have both TTI- and metadata-based approaches, the former for targets
being more knowledgeable, and the latter for front-ends being more
knowledgeable. They are quite orthogonal.

I don't understand this. If the frontend has more target knowledge than the target, something seems wrong. Could you please provide an example of when this could be a useful setup, and such knowledge should not be moved into the target?

-Hal


From: “Jingyue Wu” <jingyue@google.com>
To: “Matt Arsenault” <Matthew.Arsenault@amd.com>
Cc: llvm-dev@lists.llvm.org, “Hal Finkel” <hfinkel@anl.gov>, “Justin Holewinski” <jholewinski@nvidia.com>, “Eli Bendersky” <eliben@google.com>, “Xuetian Weng” <xweng@google.com>
Sent: Friday, August 7, 2015 3:44:29 PM
Subject: Re: [RFC] BasicAA considers address spaces?

I don’t understand this. If the frontend has more target knowledge than the target, something seems wrong. Could you please provide an example of when this could be a useful setup, and such knowledge should not be moved into the target?

Part of the problem is the loss of information going from source to a target-dependent representation. If you compile an OpenCL kernel to LLVM IR for x86, both global and local memory may map to address space 0. So the target would not be able to state that a pointer to global memory does not alias a pointer to local memory. But in the source language, you do have that information.

From: "Justin Holewinski" <jholewinski@nvidia.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Jingyue Wu" <jingyue@google.com>, llvm-dev@lists.llvm.org, "Eli
Bendersky" <eliben@google.com>, "Xuetian Weng" <xweng@google.com>,
"Matt Arsenault" <Matthew.Arsenault@amd.com>
Sent: Friday, August 7, 2015 7:33:46 PM
Subject: Re: [RFC] BasicAA considers address spaces?

> > From: "Jingyue Wu" < jingyue@google.com >
>

> > To: "Matt Arsenault" < Matthew.Arsenault@amd.com >
>

> > Cc: llvm-dev@lists.llvm.org , "Hal Finkel" < hfinkel@anl.gov >,
> > "Justin Holewinski" < jholewinski@nvidia.com >, "Eli Bendersky" <
> > eliben@google.com >, "Xuetian Weng" < xweng@google.com >
>

> > Sent: Friday, August 7, 2015 3:44:29 PM
>

> > Subject: Re: [RFC] BasicAA considers address spaces?
>

>

> >
>

> > > > + the new llvm-dev
> > >
> >
>

> > >
> >
>

> > > > > Hi folks,
> > > >
> > >
> >
>

> > > > > Unsurprisingly, leveraging the fact that certain address
> > > > > spaces
> > > > > don't
> > > > > alias can significantly improve alias analysis precision
> > > > > and
> > > > > enhance
> > > > > (observably 2x performance gain) load/store optimizations
> > > > > such
> > > > > as
> > > > > LICM and DSE.
> > > >
> > >
> >
>

> > > > > This sounds to me an overdue feature. I saw several
> > > > > discussion
> > > > > threads on that direction, but none of them really
> > > > > happened.
> > > >
> > >
> >
>

> > > > > (1)
> > > > > http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129615.html
> > > > > . Justin Holewinski proposed to add an address-space alias
> > > > > analysis
> > > > > that treats pointers in different address spaces not
> > > > > aliasing.
> > > > > This
> > > > > patch got shot down because, in some targets, address
> > > > > spaces
> > > > > may
> > > > > alias. For example, in CUDA+NVPTX, addrspace(0) aliases
> > > > > everyone.
> > > >
> > >
> >
>

> > > > > (2)
> > > > > http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064620.html
> > > > > .
> > > > > Michele Scandale proposed address space extensions in IR
> > > > > metadata
> > > > > which TBAA could then leverage to prove non-aliasing. This
> > > > > approach
> > > > > didn't fly either because address spaces are
> > > > > target-specific.
> > > > > The
> > > > > front end doesn't know enough to decide aliasing.
> > > >
> > >
> >
>

> > > > > So, can we make BasicAA to consider address spaces?
> > > > > Specifically,
> > > > > I
> > > > > am proposing:
> > > >
> > >
> >
>

> > > > > a) adding a new interface like
> > > > > TTI::addressSpacesAlias(unsigned,
> > > > > unsigned), and
> > > >
> > >
> >
>

> > > > > b) adding a little piece of logic in BasicAA that reports
> > > > > "no
> > > > > alias"
> > > > > if address spaces don't alias.
> > > >
> > >
> >
>

> > > > > This approach addresses the issue brought up in (2) because
> > > > > TTI
> > > > > can
> > > > > see the entire codegen. It also resolves the issue that
> > > > > shut
> > > > > down
> > > > > (1) because it allows address spaces to alias in a
> > > > > target-defined
> > > > > way. Actually, John Criswell did mention in that thread the
> > > > > idea
> > > > > of
> > > > > embedding alias info in TargetData. Now that we have TTI,
> > > > > it
> > > > > seems
> > > > > a
> > > > > better place to hold target-specific alias info than
> > > > > DataLayout.
> > > >
> > >
> >
>

> > > > > Any comments?
> > > >
> > >
> >
>

> > > > > Jingyue
> > > >
> > >
> >
>

> > > We definitely need something to handle this.
> >
>

> > > I think a TTI::addressSpaceAlias is a good idea, although I
> > > don't
> > > think this fully solves the language vs. target address space
> > > distinction a metadata based approach was supposed to handle
> > > although it would be easier to implement. For our GPU purposes
> > > this
> > > would mostly be enough. For example, the fact that in OpenCL
> > > local
> > > vs. global pointers won't alias is a useful distinction, even
> > > though
> > > for a CPU target those will all be mapped to
> >
>

> > Thanks for pointing this out, Matt. In that case, I'd suggest
> > LLVM
> > have both TTI- and metadata-based approaches, the former for
> > targets
> > being more knowledgeable, and the latter for front-ends being
> > more
> > knowledgeable. They are quite orthogonal.
>

> I don't understand this. If the frontend has more target knowledge
> than the target, something seems wrong. Could you please provide an
> example of when this could be a useful setup, and such knowledge
> should not be moved into the target?

Part of the problem is the loss of information going from source to a
target-dependent representation. If you compile an OpenCL kernel to
LLVM IR for x86, both global and local memory may map to address
space 0.

But you seem to be implying that you'll use different address spaces at the IR level, but that these address spaces will be changed prior to the target seeing them? Or that the target will internally map them all to address space 0 (instead of aborting). If the target knows to do this mapping, it can also understand the aliasing, no?

So the target would not be able to state that a pointer to global
memory does not alias a pointer to local memory. But in the source
language, you do have that information.

And, regardless, you might want to use the associated aliasing information during CodeGen. For information the target can't have, using aliasing metadata seems like it might be a better solution here?

Thanks again,
Hal

clang performs the mapping from source address space to target address space. See AddrSpaceMap in clang's TargetInfo

From: "Matt Arsenault" <Matthew.Arsenault@amd.com>
To: "Hal Finkel" <hfinkel@anl.gov>, "Justin Holewinski" <jholewinski@nvidia.com>
Cc: "Jingyue Wu" <jingyue@google.com>, llvm-dev@lists.llvm.org, "Eli Bendersky" <eliben@google.com>, "Xuetian Weng"
<xweng@google.com>
Sent: Friday, August 7, 2015 8:21:27 PM
Subject: Re: [RFC] BasicAA considers address spaces?

> But you seem to be implying that you'll use different address
> spaces
> at the IR level, but that these address spaces will be changed
> prior
> to the target seeing them? Or that the target will internally map
> them
> all to address space 0 (instead of aborting). If the target knows
> to
> do this mapping, it can also understand the aliasing, no?

clang performs the mapping from source address space to target
address
space. See AddrSpaceMap in clang's TargetInfo

But then that's too late for any address-space-based metadata. What you need is just aliasing metadata, which is another matter (and, to some extent, we already have).

-Hal

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

From: "escha" <escha@apple.com>
To: "Hal Finkel" <hfinkel@anl.gov>
Cc: "Matt Arsenault" <Matthew.Arsenault@amd.com>, llvm-dev@lists.llvm.org, "Justin Holewinski"
<jholewinski@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

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

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

SGTM

From: "Daniel Berlin" <dberlin@dberlin.org>
To: "Jingyue Wu" <jingyue@google.com>
Cc: "Hal Finkel" <hfinkel@anl.gov>, llvm-dev@lists.llvm.org, "Justin Holewinski" <jholewinski@nvidia.com>
Sent: Wednesday, August 12, 2015 2:03:34 PM
Subject: Re: [llvm-dev] [RFC] BasicAA considers address spaces?

SGTM

+1

-Hal