<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" xmlns:m="http://schemas.microsoft.com/office/2004/12/omml" xmlns="http://www.w3.org/TR/REC-html40">
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<meta name="Generator" content="Microsoft Word 15 (filtered medium)">
<style><!--
/* Font Definitions */
@font-face
{font-family:Helvetica;
panose-1:2 11 6 4 2 2 2 2 2 4;}
@font-face
{font-family:"Cambria Math";
panose-1:2 4 5 3 5 4 6 3 2 4;}
@font-face
{font-family:Monaco;
panose-1:0 0 0 0 0 0 0 0 0 0;}
/* Style Definitions */
p.MsoNormal, li.MsoNormal, div.MsoNormal
{margin:0in;
margin-bottom:.0001pt;
font-size:12.0pt;
font-family:"Times New Roman",serif;}
a:link, span.MsoHyperlink
{mso-style-priority:99;
color:blue;
text-decoration:underline;}
a:visited, span.MsoHyperlinkFollowed
{mso-style-priority:99;
color:purple;
text-decoration:underline;}
span.EmailStyle17
{mso-style-type:personal-compose;
font-family:"Times New Roman",serif;}
.MsoChpDefault
{mso-style-type:export-only;
font-size:10.0pt;}
@page WordSection1
{size:8.5in 11.0in;
margin:1.0in 1.0in 1.0in 1.0in;}
div.WordSection1
{page:WordSection1;}
--></style><!--[if gte mso 9]><xml>
<o:shapedefaults v:ext="edit" spidmax="1026" />
</xml><![endif]--><!--[if gte mso 9]><xml>
<o:shapelayout v:ext="edit">
<o:idmap v:ext="edit" data="1" />
</o:shapelayout></xml><![endif]-->
</head>
<body lang="EN-US" link="blue" vlink="purple">
<div class="WordSection1">
<p class="MsoNormal">Currently the Synchronization Scope (aka memory scope) information appears not to be used in any atomic related optimizations. It would seem any such optimizations should consider memory scope and an approach such as suggested by Philip
seems reasonable. Could that change be tackled as a separate patch? Initially any atomic optimizations could be restricted to only be allowed when the memory scopes are exactly equal which should be conservatively correct.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">This patch would be a first step towards adding support for atomics with memory scopes used by languages such as OpenCL. Doing this simplifies how memory scope information is passed from CLANG to the code generator as mentioned by Tom.
There seems to be several companies interested in doing this as it will simplify the code and allow atomics to be handled in a consistent way for all languages, and allow atomic optimizations to benefit these languages.<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<p class="MsoNormal">Thanks,<o:p></o:p></p>
<p class="MsoNormal">-Tony<o:p></o:p></p>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal">On Sep 2, 2016, at 11:13 PM, Mehdi Amini <mehdi.amini@apple.com> wrote:<o:p></o:p></p>
</div>
<p class="MsoNormal"><o:p> </o:p></p>
<div>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt;font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><br>
On Sep 2, 2016, at 5:52 PM, Philip Reames via llvm-dev <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><br>
<br>
On 09/01/2016 08:52 AM, Tom Stellard via llvm-dev wrote:<br style="font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<br>
</span><span style="font-size:9.0pt;font-family:Monaco"><o:p></o:p></span></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">On Wed, Aug 31, 2016 at 12:23:34PM -0700, Justin Lebar via llvm-dev wrote:<br>
<br>
<o:p></o:p></span></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">Some optimizations that are related to a single thread could be done without needing to know the actual memory scope.<o:p></o:p></span></p>
</blockquote>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">Right, it's clear to me that there exist optimizations that you cannot<br>
do if we model these ops as target-specific intrinsics.<br>
<br>
But what I think Mehdi and I were trying to get at is: How much of a<br>
problem is this in practice? Are there real-world programs that<br>
suffer because we miss these optimizations? If so, how much?<br>
<br>
The reason I'm asking this question is, there's a real cost to adding<br>
complexity in LLVM. Everyone in the project is going to pay that<br>
cost, forever (or at least, until we remove the feature :). So I want<br>
to try to evaluate whether paying that cost is actually worth while,<br>
as compared to the simple alternative (i.e., intrinsics). Given the<br>
tepid response to this proposal, I'm sort of thinking that now may not<br>
be the time to start paying this cost. (We can always revisit this in<br>
the future.) But I remain open to being convinced.<o:p></o:p></span></p>
</blockquote>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">I think the cost of adding this information to the IR is really low.<br>
There is already a sychronization scope field present for LLVM atomic<br>
instructions, and it is already being encoded as 32-bits, so it is<br>
possible to represent the additional scopes using the existing bitcode<br>
format. Optimization passes are already aware of this synchronization<br>
scope field, so they know how to preserve it when transforming the IR.<o:p></o:p></span></p>
</blockquote>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">I disagree with this assessment. Atomics are an area where additional complexity has a *substantial* conceptual cost. I also question whether the single_thread scope is
actually respected throughout the optimizer in practice.<br>
<br>
I view the request of changing the IR as a fairly big ask. In particular, I'm really nervous about what the exact optimization semantics of such scopes would be. Depending on how that was defined, this could be anything from fairly straight forward to outright
messy. In particular, if there are optimizations which are legal for only some subset of scopes (or subset of pairs of scopes?), I'd really like to see a clear definition given for how those are defined.</span><span style="font-size:9.0pt;font-family:Monaco"><o:p></o:p></span></p>
</div>
</blockquote>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt;font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">(p.s. Is there a current patch with an updated LangRef for the proposal being discussed? I've lost track of it.)</span><span style="font-size:9.0pt;font-family:Monaco"><o:p></o:p></span></p>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco">Here is the patch: <a href="https://reviews.llvm.org/D21723">https://reviews.llvm.org/D21723</a><o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><br style="font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<br>
</span><o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><br>
Let me give an example proposal just to illustrate my point. This isn't really a counter proposal per se, just me thinking out loud.<br>
<br>
Say we added 32 distinct concurrent domains. One of them is used for "single_thread". One is used for "everything else". The remaining 30 are defined in a target specific manner w/the exception that they can't overlap with each other or with the two predefined
ones. The effect of a given atomic operation with respect to each concurrency domain could be defined in terms of a 32 bit mask. If a bit was set, the operation is ordered (according to the separately stated ordering) with that domain. If not, it is explicitly
unordered w.r.t. that domain. A memory operation would be tagged with the memory domains which which it might interact.<br>
<br>
The key bit here is that I can describe transformations in terms of these abstract domains without knowing anything about how the frontend might be using such a domain or how the backend might lower it. In particular, if I have the sequence:<br>
%v = load i64, %p atomic scope {domain3 only}<br>
fence seq_cst scope={domain1 only}<br>
%v2 = load i64, %p atomic scope {domain3 only}<br>
<br>
I can tell that the two loads aren't order with respect to the fence and that I can do load forwarding here.</span><span style="font-size:9.0pt;font-family:Monaco"><o:p></o:p></span></p>
</div>
</blockquote>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco">I see the current proposal as a strip-down version what you describe: the optimizer can reason about operations inside a single scope, but can’t assume anything cross-scope (they may or may
not interact with each other).<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco">What you describes seems like having always non-overlapping domains (from the optimizer point of view), and require the frontend to express the overlapping by attaching a “list" of domains
that an atomic operation interacts with.<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco">I hope I make sense :)<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco">Best,<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco">— <o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco">Mehdi<o:p></o:p></span></p>
</div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<div>
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><o:p> </o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><br>
<br>
<o:p></o:p></span></p>
</div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:Monaco"><br style="font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<br>
</span><o:p></o:p></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<div>
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><br>
<br>
In general, an IR extension needs to be well defined, general enough to be used by multiple distinct users, and fairly battle tested design wise. We're not completely afraid of having to remove bad ideas from the IR, but we really try to avoid adding things
until they're fairly proven.<br>
<br>
<br style="font-variant-caps: normal;orphans: auto;text-align:start;widows: auto;-webkit-text-stroke-width: 0px;word-spacing:0px">
<br>
</span><span style="font-size:9.0pt;font-family:Monaco"><o:p></o:p></span></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><br>
The primary goal here is to pass synchronization scope information from<br>
the fronted to the backend. We already have a mechanism for doing this,<br>
so why not use it? That seems like the lowest cost option to me.<br>
<br>
-Tom<br>
<br>
<br>
<o:p></o:p></span></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">As a point of comparison, we have a rule of thumb that we'll add an<br>
optimization that increases compilation time by x% if we have a<br>
benchmark that is sped up by at least x%. Similarly here, I'd want to<br>
weigh the added complexity against the improvements to user code.<br>
<br>
-Justin<br>
<br>
On Tue, Aug 23, 2016 at 2:28 PM, Tye, Tony via llvm-dev<br>
<<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a>> wrote:<br>
<br>
<o:p></o:p></span></p>
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<blockquote style="margin-top:5.0pt;margin-bottom:5.0pt">
<p class="MsoNormal"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif">Since the scope is “opaque” and target specific, can you elaborate what<br>
kind of generic optimization can be performed?<o:p></o:p></span></p>
</blockquote>
<p class="MsoNormal" style="margin-bottom:12.0pt"><span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><br>
<br>
Some optimizations that are related to a single thread could be done without<br>
needing to know the actual memory scope. For example, an atomic acquire can<br>
restrict reordering memory operations after it, but allow reordering of<br>
memory operations (except another atomic acquire) before it, regardless of<br>
the memory scope.<br>
<br>
<br>
<br>
Thanks,<br>
<br>
-Tony<o:p></o:p></span></p>
</blockquote>
<p class="MsoNormal" style="mso-margin-top-alt:0in;margin-right:4.0in;margin-bottom:5.0pt;margin-left:0in">
<span style="font-size:9.0pt;font-family:"Helvetica",sans-serif"><o:p> </o:p></span></p>
</blockquote>
</blockquote>
</div>
</blockquote>
</div>
</blockquote>
</div>
</div>
</body>
</html>