Re: [llvm-dev] [RFC] BasicAA considers address spaces?

[Jingyue Wu via llvm-dev]

+ the new llvm-dev

On Fri, Aug 7, 2015 at 11:30 AM, Jingyue Wu <jin...@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

[Philip Reames via 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. 

_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org         http://llvm.cs.uiuc.edu
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[Matt Arsenault via llvm-dev]

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

[Daniel Berlin via llvm-dev]

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

[Matt Arsenault via llvm-dev]

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

[Daniel Berlin via llvm-dev]

On Fri, Aug 7, 2015 at 12:45 PM, Matt Arsenault
<Matthew....@amd.com> wrote:
> 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?

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)

[Jingyue Wu via llvm-dev]

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. 

[Jingyue Wu via llvm-dev]

Either way sounds fine with me. 

[Jingyue Wu via llvm-dev]

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.

[Hal Finkel via llvm-dev]

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

 

address space 0 so in some cases the frontend knows more about aliasing address spaces than the target.

-Matt

--

Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

[Justin Holewinski via llvm-dev]

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.

 -Hal

 

address space 0 so in some cases the frontend knows more about aliasing address spaces than the target.

-Matt

-- 

Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

---

This email message is for the sole use of the intended recipient(s) and may contain confidential information.  Any unauthorized review, use, disclosure or distribution is prohibited.  If you are not the intended recipient, please contact the sender by reply email and destroy all copies of the original message.

---

[Hal Finkel via llvm-dev]

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

[Matt Arsenault via llvm-dev]

On 08/07/2015 06:13 PM, Hal Finkel wrote:
> 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

[Hal Finkel via llvm-dev]

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

> On 08/07/2015 06:13 PM, Hal Finkel wrote:
> > 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

>

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

[escha via llvm-dev]

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

[Hal Finkel via llvm-dev]

----- Original Message -----
> From: "escha" <es...@apple.com>
> To: "Hal Finkel" <hfi...@anl.gov>

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

[escha via llvm-dev]

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

[Jingyue Wu via llvm-dev]

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

[Daniel Berlin via llvm-dev]

SGTM

[Hal Finkel via llvm-dev]

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

> SGTM

+1

-Hal

[Hal Finkel via llvm-dev]

----- Original Message -----
> From: "Hal Finkel via llvm-dev" <llvm...@lists.llvm.org>
> To: "Daniel Berlin" <dbe...@dberlin.org>
> Cc: llvm...@lists.llvm.org, "Justin Holewinski" <jhole...@nvidia.com>
> Sent: Wednesday, August 12, 2015 2:06:41 PM
> Subject: Re: [llvm-dev] [RFC] BasicAA considers address spaces?
>
> ----- Original Message -----
> > From: "Daniel Berlin" <dbe...@dberlin.org>
> > To: "Jingyue Wu" <jin...@google.com>
> > Cc: "Hal Finkel" <hfi...@anl.gov>, llvm...@lists.llvm.org,
> > "Justin Holewinski" <jhole...@nvidia.com>
> > Sent: Wednesday, August 12, 2015 2:03:34 PM
> > Subject: Re: [llvm-dev] [RFC] BasicAA considers address spaces?
> >
> > SGTM
>
> +1

Actually, upon further reflection, I don't we should create a new AA interface for this unless that's really necessary. AA passes can currently provide alias, pointsToConstantMemory, getArgModRefInfo, etc. and the target can quite reasonably want to enhance many of these.

Unless there's some reason why we can't, I think we should provide the target the ability to provide an AA analysis pass to be inserted in the chain, or maybe TTI should just *be* an AA pass that gets inserted into the chain?

-Hal

[Jingyue Wu via llvm-dev]

Then, we need to run this target-provided AA under -O3 to benefit the optimizations in O3. 

I'm not sure what's the best practice of doing this. One way is pass

1) add a new interface TTI.getTargetAwareAliasAnalysis that returns the target-provided AA or nullptr

2) Embed TTI in PassManagerBuilder

3) When PassManagerBuilder::addInitialAliasAnalysisPass adds TTI.getTargetAwareAliasAnalysis to the pipeline. 

Any better ideas? 

[Daniel Berlin via llvm-dev]

So, the one downside of doing it this way is that the information
never will get to the other parts of the world.
We definitely don't want to go crazy and have tons of target-specific
alias info encoded into the AA interface.

I agree also, in general, this belongs in an AA pass and not the
interface (IE i don't think basicaa needs it).

However, for things like "memory spaces being disjoint", some other AA
passes may want to be able to know that.
IE If CFL-AA can tell that memory spaces are disjoint, it could avoid
unioning in stuff that can't really alias. Without such a hook, it
would be relegated to calling something like alias() on every pair :P

So i'm torn on how best to make that happen, without people going off
and completely making things like basicaa super target-specific using
hooks (such that it ends up providing pretty crappy answers unless you
implement 60 different target hooks)

[Hal Finkel via llvm-dev]

[+Chandler]

----- Original Message -----
> From: "Jingyue Wu" <jin...@google.com>
> To: "Hal Finkel" <hfi...@anl.gov>
> Cc: llvm...@lists.llvm.org, "Justin Holewinski" <jhole...@nvidia.com>
> Sent: Wednesday, August 12, 2015 3:39:52 PM
> Subject: Re: [llvm-dev] [RFC] BasicAA considers address spaces?
>

> Then, we need to run this target-provided AA under -O3 to benefit the
> optimizations in O3.
>
> I'm not sure what's the best practice of doing this. One way is pass
> 1) add a new interface TTI.getTargetAwareAliasAnalysis that returns
> the target-provided AA or nullptr
> 2) Embed TTI in PassManagerBuilder
> 3) When PassManagerBuilder::addInitialAliasAnalysisPass adds
> TTI.getTargetAwareAliasAnalysis to the pipeline.
>
> Any better ideas?

I've cc'd Chandler so he can comment here.

Currently, TargetMachine can optionally return a TargetIRAnalysis object; this is then provided a function for which it can produce the actual TargetTransformInfo-derived object. TargetTransformInfoWrapperPass is the actual pass, and it just holds a pointer to the TargetIRAnalysis object.

In our case, we'd like to provide the target a way to add some AA pass to take advantage of target-specific knowledge regarding address spaces, intrinsics, and other IR constructs whose meaning is completely target specific. I'm not sure how well it fits into this model.

In addition, we have other use cases where targets want to add passes to handle target-specific things into the pipeline (http://reviews.llvm.org/D11782, for example, for doing target-specific loop-idiom recognition).

Plus, we already have a mechanism for allowing extension of the optimization pipeline, and I think the best way of approaching this (which is also useful for other use cases), is to provide the targets the ability to use this mechanism. I understand that this could be ripe for abuse (so we'd need to be vigilant in watching the targets), but nevertheless, how about this:

1. Add a function to TargetMachine called, for example, registerPassManagerBuilderExtensions(PassManagerBuilder *PMB). This would need to be called, for example, by the code in EmitAssemblyHelper in Clang in tools/clang/lib/CodeGen/BackendUtil.cpp (just as it currently calls TM->getTargetIRAnalysis() and so that it can call createTargetTransformInfoWrapperPass) and also registers other extensions itself.

2. registerPassManagerExtensions's job will be to call PassManagerBuilder::addExtension (or addGlobalExtension) as appropriate.

3. Create a new extension point for AA passes, and call addExtensionsToPM inside PassManagerBuilder::addInitialAliasAnalysisPasses

This will automatically cover a wide variety of use cases, including this one. Thoughts?

-Hal

>
>

[Hal Finkel via llvm-dev]

----- Original Message -----
> From: "Daniel Berlin" <dbe...@dberlin.org>
> To: "Hal Finkel" <hfi...@anl.gov>
> Cc: llvm...@lists.llvm.org, "Justin Holewinski" <jhole...@nvidia.com>
> Sent: Wednesday, August 12, 2015 4:36:54 PM
> Subject: Re: [llvm-dev] [RFC] BasicAA considers address spaces?
>

> So, the one downside of doing it this way is that the information
> never will get to the other parts of the world.
> We definitely don't want to go crazy and have tons of target-specific
> alias info encoded into the AA interface.
>
> I agree also, in general, this belongs in an AA pass and not the
> interface (IE i don't think basicaa needs it).
>
> However, for things like "memory spaces being disjoint", some other
> AA
> passes may want to be able to know that.
> IE If CFL-AA can tell that memory spaces are disjoint, it could avoid
> unioning in stuff that can't really alias. Without such a hook, it
> would be relegated to calling something like alias() on every pair :P
>
> So i'm torn on how best to make that happen, without people going off
> and completely making things like basicaa super target-specific using
> hooks (such that it ends up providing pretty crappy answers unless
> you
> implement 60 different target hooks)

We might be able to consider address spaces somewhat special in this regard -- they're already somewhat special. Like target-specific intrinsics, they are an IR-level feature with target-defined semantics. As a result, I feel it would be justified to add some additional IR-level support to provide some more information to the generic IR analysis. We could, for example, use module-level metadata to encode address-space disjointness information, and that could be leveraged by BasicAA, etc.

This fits with the role of metadata, in that if the metadata were dropped, the IR analysis would simply fallback to making the same kinds of conservative decisions it makes now.