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

+ the new llvm-dev

On Fri, Aug 7, 2015 at 11:30 AM, Jingyue Wu <jingyue at google.com> wrote:
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150807/fe2cc2cf/attachment.html>

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

On 08/07/2015 11:35 AM, Jingyue Wu via llvm-dev wrote:
> + the new llvm-dev
>
> On Fri, Aug 7, 2015 at 11:30 AM, Jingyue Wu <jingyue at google.com 
> <mailto:jingyue at google.com>> wrote:
>
>     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
>
>
>
>
> _______________________________________________
> 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/20150807/59b4eed4/attachment.html>

On 08/07/2015 11:35 AM, Jingyue Wu wrote:
> + the new llvm-dev
>
> On Fri, Aug 7, 2015 at 11:30 AM, Jingyue Wu <jingyue at google.com 
> <mailto:jingyue at google.com>> wrote:
>
>     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 address space 0 so in some cases the frontend knows 
more about aliasing address spaces than the target.

-Matt
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150807/cd0e3f45/attachment.html>

On Fri, Aug 7, 2015 at 11:35 AM, Jingyue Wu via llvm-dev
<llvm-dev at lists.llvm.org> wrote:
> + the new llvm-dev
>
> On Fri, Aug 7, 2015 at 11:30 AM, Jingyue Wu <jingyue at google.com>
wrote:
>>
>> 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, ...

On 08/07/2015 12:22 PM, Daniel Berlin via llvm-dev
wrote:
> 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? 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

On Fri, Aug 7, 2015 at 12:22 PM, Daniel Berlin <dberlin at dberlin.org>
wrote:
> On Fri, Aug 7, 2015 at 11:35 AM, Jingyue Wu via llvm-dev
> <llvm-dev at lists.llvm.org> wrote:
> > + the new llvm-dev
> >
> > On Fri, Aug 7, 2015 at 11:30 AM, Jingyue Wu <jingyue at
google.com> wrote:
> >>
> >> 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.

>
> But this is a mild preference, if others think this is a bad idea, ...
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150807/b5ff2dda/attachment.html>

On Fri, Aug 7, 2015 at 12:01 PM, Matt Arsenault <Matthew.Arsenault at
amd.com>
wrote:
> On 08/07/2015 11:35 AM, Jingyue Wu wrote:
>
> + the new llvm-dev
>
> On Fri, Aug 7, 2015 at 11:30 AM, Jingyue Wu <jingyue at google.com>
wrote:
>
>> 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.

> address space 0 so in some cases the frontend knows more about aliasing
> address spaces than the target.
>
> -Matt
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150807/1065bc3e/attachment-0001.html>