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

[Hal Finkel via llvm-dev]

----- Original Message -----

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

> > On Aug 7, 2015, at 8:28 PM, Hal Finkel < hfinkel at anl.gov > wrote:
> 

> > ----- Original Message -----
> 

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

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

> > -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 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20150807/a0460373/attachment.html>