<html><head><style type='text/css'>p { margin: 0; }</style></head><body><div style='font-family: arial,helvetica,sans-serif; font-size: 10pt; color: #000000'><br><br><hr id="zwchr"><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><b>From: </b>"Justin Holewinski" <jholewinski@nvidia.com><br><b>To: </b>"Hal Finkel" <hfinkel@anl.gov><br><b>Cc: </b>"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><br><b>Sent: </b>Friday, August 7, 2015 7:33:46 PM<br><b>Subject: </b>Re: [RFC] BasicAA considers address spaces?<br><br>
<br class="">
<div>
<blockquote class="">
<div class="">On Aug 7, 2015, at 8:28 PM, Hal Finkel <<a href="mailto:hfinkel@anl.gov" class="" target="_blank">hfinkel@anl.gov</a>> wrote:</div>
<br class="Apple-interchange-newline">
<div class="">
<div style="font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; font-family: arial,helvetica,sans-serif; font-size: 10pt;" class="">
<br class="">
<br class="">
<hr id="zwchr" class="">
<blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;" class="">
<b class="">From:<span class="Apple-converted-space"> </span></b>"Jingyue Wu" <<a href="mailto:jingyue@google.com" class="" target="_blank">jingyue@google.com</a>><br class="">
<b class="">To:<span class="Apple-converted-space"> </span></b>"Matt Arsenault" <<a href="mailto:Matthew.Arsenault@amd.com" class="" target="_blank">Matthew.Arsenault@amd.com</a>><br class="">
<b class="">Cc:<span class="Apple-converted-space"> </span></b><a href="mailto:llvm-dev@lists.llvm.org" class="" target="_blank">llvm-dev@lists.llvm.org</a>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" class="" target="_blank">hfinkel@anl.gov</a>>, "Justin Holewinski" <<a href="mailto:jholewinski@nvidia.com" class="" target="_blank">jholewinski@nvidia.com</a>>,
"Eli Bendersky" <<a href="mailto:eliben@google.com" class="" target="_blank">eliben@google.com</a>>, "Xuetian Weng" <<a href="mailto:xweng@google.com" class="" target="_blank">xweng@google.com</a>><br class="">
<b class="">Sent:<span class="Apple-converted-space"> </span></b>Friday, August 7, 2015 3:44:29 PM<br class="">
<b class="">Subject:<span class="Apple-converted-space"> </span></b>Re: [RFC] BasicAA considers address spaces?<br class="">
<br class="">
<div dir="ltr" class="">
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On Fri, Aug 7, 2015 at 12:01 PM, Matt Arsenault<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:Matthew.Arsenault@amd.com" target="_blank" class="">Matthew.Arsenault@amd.com</a>></span><span class="Apple-converted-space"> </span>wrote:<br class="">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="">
<div class="">
<div class="h5">
<div class="">On 08/07/2015 11:35 AM, Jingyue Wu wrote:<br class="">
</div>
<blockquote class="">
<div dir="ltr" class="">+ the new llvm-dev</div>
<div class="gmail_extra"><br class="">
<div class="gmail_quote">On Fri, Aug 7, 2015 at 11:30 AM, Jingyue Wu<span class="Apple-converted-space"> </span><span dir="ltr" class=""><<a href="mailto:jingyue@google.com" target="_blank" class="">jingyue@google.com</a>></span><span class="Apple-converted-space"> </span>wrote:<br class="">
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div dir="ltr" class="">
<div class="">Hi folks,</div>
<div class=""><br class="">
</div>
<div class="">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. </div>
<div class=""><br class="">
</div>
<div class="">This sounds to me an overdue feature. I saw several discussion threads on that direction, but none of them really happened. </div>
<div class=""><br class="">
</div>
(1)<span class="Apple-converted-space"> </span><a href="http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129615.html" target="_blank" class="">http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20111010/129615.html</a>. 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.
<div class="">
<div class=""><br class="">
</div>
<div class="">(2) <a href="http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064620.html" target="_blank" class="">http://lists.cs.uiuc.edu/pipermail/llvmdev/2013-August/064620.html</a>. 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. <br class="">
</div>
<br class="">
So, can we make BasicAA to consider address spaces? Specifically, I am proposing:</div>
<div class="">a) adding a new interface like TTI::addressSpacesAlias(unsigned, unsigned), and</div>
<div class="">b) adding a little piece of logic in BasicAA that reports "no alias" if address spaces don't alias. </div>
<div class=""><br class="">
</div>
<div class="">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. </div>
<div class=""><br class="">
</div>
<div class="">Any comments? </div>
<span class=""><font class="" color="#888888">
<div class=""><br class="">
</div>
<div class="">Jingyue</div>
</font></span></div>
</blockquote>
</div>
<br class="">
</div>
</blockquote>
</div>
</div>
We definitely need something to handle this.<br class="">
<br class="">
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<span class="Apple-converted-space"> </span></div>
</blockquote>
<div class=""><br class="">
</div>
<div id="DWT1487" class="">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.</div>
</div>
</div>
</div>
</blockquote>
<br class="">
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?<br class="">
</div>
</div>
</blockquote>
<div><br class="">
</div>
<div id="DWT1832">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.</div></div></blockquote>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?<br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div><div id="DWT1844"> 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.</div></div></blockquote><br>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?<br><br>Thanks again,<br>Hal<br><br><blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; color: rgb(0, 0, 0); font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;"><div><div></div>
<div><br class="">
</div>
<br class="">
<blockquote class="">
<div class="">
<div style="font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; text-align: start; text-indent: 0px; text-transform: none; white-space: normal; word-spacing: 0px; font-family: arial,helvetica,sans-serif; font-size: 10pt;" class="">
<br class="">
-Hal<br class="">
<br class="">
<blockquote style="border-left: 2px solid rgb(16, 16, 255); margin-left: 5px; padding-left: 5px; font-weight: normal; font-style: normal; text-decoration: none; font-family: Helvetica,Arial,sans-serif; font-size: 12pt;" class="">
<div dir="ltr" class="">
<div class="gmail_extra">
<div class="gmail_quote">
<div class=""></div>
<div class=""> </div>
<blockquote class="gmail_quote" style="margin: 0pt 0pt 0pt 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1ex;">
<div class="">address space 0 so in some cases the frontend knows more about aliasing address spaces than the target.<span class="HOEnZb"><font class="" color="#888888"><br class="">
<br class="">
-Matt<br class="">
</font></span></div>
</blockquote>
</div>
<br class="">
</div>
</div>
</blockquote>
<br class="">
<br class="">
<br class="">
--<span class="Apple-converted-space"> </span><br class="">
<div class=""><span class=""></span>Hal Finkel<br class="">
Assistant Computational Scientist<br class="">
Leadership Computing Facility<br class="">
Argonne National Laboratory</div>
</div>
</div>
</blockquote>
</div>
<br class="">
<div>
<hr>
</div>
<div>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. </div>
<div>
<hr>
</div>
</blockquote><br><br><br>-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></div></body></html>