<html>
<head>
<meta content="text/html; charset=utf-8" http-equiv="Content-Type">
</head>
<body bgcolor="#FFFFFF" text="#000000">
<p>For the record, I am not a C++ expert or a concurrency expert.
Take everything I say with several grains of salt...</p>
<p>If I remember the key parts of the C++ spec, an atomic store
synchronizes with (establishes an ordering with) only other atomic
operations. <br>
</p>
<p>For acquire and release, the spec is clearly defined in terms of
other atomic memory operations on the same memory location. Given
we've proven the location thread local, by definition no other
thread can contain a atomic memory operation which references it.</p>
<p>acq_rel would seem to follow from the above.</p>
<p>As for csq_cst, I'm really not sure. The wording I can find
defining it is a bit vague and would appear to imply an ordering
involving all memory locations (including the non-thread local
ones). Given this, it is probably safest not to demote seq_cst to
non-atomic without careful consideration. We could always lower
the atomic seq_cst store to a non-atomic store and a set of
fences, but that seems unlikely to be profitable. <br>
</p>
<p>To be very clear, I'm not stating it is illegal to demote thread
local seq_cst stores; I'm just stating that I don't see an obvious
argument why it is definitely legal.<br>
</p>
<p>Philip<br>
</p>
<br>
<div class="moz-cite-prefix">On 12/02/2016 03:20 AM, Madhur
Amilkanthwar wrote:<br>
</div>
<blockquote
cite="mid:CAMTh1gUE=mr+rBMmhEEUXpSRpcd-5_nkSCkJQsETV1awoQxH_w@mail.gmail.com"
type="cite">
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<div dir="ltr">
<div style="font-size:12.8px">
<div><span style="color:rgb(80,0,80);font-size:12.8px">[Philip]</span></div>
<div><span style="color:rgb(80,0,80);font-size:12.8px">If I
know something is thread local:</span><br
style="color:rgb(80,0,80);font-size:12.8px">
<span style="color:rgb(80,0,80);font-size:12.8px">- I can
demote atomic accesses to non-atomic ones.</span><i><br>
</i></div>
<div><span style="color:rgb(80,0,80);font-size:12.8px"><br>
</span></div>
<div><i>[David]</i></div>
<div><i>void barrier() {</i></div>
<div><i> std::atomic<int> z;</i></div>
<div><i> z.store(1, std::memory_order_seq_cst);</i></div>
<div><i>}</i></div>
</div>
<div style="font-size:12.8px"><i><br>
</i></div>
<div style="font-size:12.8px"><i>Does the modification to 'z'
participate in the total ordering?</i></div>
<div style="font-size:12.8px"><i>LLVM doesn't think so.</i></div>
<div style="font-size:12.8px"><i>ICC emits an mfence and no
store.</i></div>
<div style="font-size:12.8px"><i>GCC emits an mfence and a
store.</i></div>
<div style="font-size:12.8px"><i><br>
</i></div>
<div style="font-size:12.8px"><i>I think LLVM's behavior here is
defensible. </i></div>
<div style="font-size:12.8px"><i><br>
</i></div>
<div style="font-size:12.8px"><i><br>
</i></div>
<div style="font-size:12.8px">I think there is a problem here.
If you demote atomic stores to non-atomic store then you are
removing reordering constraints i.e with With atomic store you
cannot move later loads/stores before Z.store() but if you
make it non-atomic too early in compiler then further passes
may reorder loads/stores and the program may not be correct.
Am I right? </div>
</div>
<div class="gmail_extra"><br>
<div class="gmail_quote">On Thu, Jun 9, 2016 at 11:55 PM, David
Majnemer via llvm-dev <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0
.8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr"><br>
<div class="gmail_extra"><br>
<div class="gmail_quote"><span class="">On Thu, Jun 9,
2016 at 10:43 AM, JF Bastien <span dir="ltr"><<a
moz-do-not-send="true"
href="mailto:jfb@google.com" target="_blank">jfb@google.com</a>></span>
wrote:<br>
<blockquote class="gmail_quote" style="margin:0px
0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">On Tue, Jun 7, 2016
at 4:02 PM, Philip Reames via llvm-dev <span
dir="ltr"><<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org"
target="_blank">llvm-dev@lists.llvm.org</a>></span>
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">(+CC
LLVM dev - I'd dropped it in my original
reply unintentionally and just noticed.)<br>
<br>
On 06/07/2016 01:35 PM, Philip Reames
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">(This
was written in a rush. There may be
mistakes; if so I'll try to correct
later.)<br>
<br>
At the moment, most of LLVM is worried
about capture. The only exception I
know of are:<br>
1) isAllocSiteRemovable in InstCombine/<wbr>InstructionCombining.cpp<br>
2) The thread local logic used in LICM's
store promotion<br>
<br>
Let me phrase this informally:<br>
- "capture" - can anyone inspect the
bits of this pointer?<br>
- "escape" - can anyone inspect the
contents of this allocation?<br>
- "thread escape" - can any other thread
inspect the contents of this allocation?<br>
<br>
Generally, "escape" and "thread local"
are about the *contents* of an
allocation. "capture" is about the the
pointer value itself. In practice, we
generally treat "capture" very
conservatively. To have something which
has escaped, but isn't captured, you'd
have to have a way to refer to an object
without being able to determine it's
address. C++ doesn't have this (I
think?). Java does (in very limited
forms), but we haven't tried to be
aggressive here in LLVM. We generally
assume "capture" implies "escape" and
"thread escape".<br>
<br>
Illustrative examples:<br>
- A function which returns the alignment
of a pointer captures a pointer, but
does not cause it to escape or become
non-thread local.<br>
- A function which compares a pointer
against a known constant may capture,
escape, and make non-thread-local all at
once if the constant is known to any
other thread.<br>
- A function which writes a newly
allocated pointer into a thread local
buffer has captured and escaped it, but
has not made it non-thread local.<br>
<br>
If I know something is thread local:<br>
- I can demote atomic accesses to
non-atomic ones.<br>
</blockquote>
</blockquote>
<div><br>
</div>
<div>Agreed you can make it non-atomic, but
with LLVM's memory model can you lose the
ordering effect that the atomic had? I
think in C++ you can (e.g. a stack-local
atomic doesn't enforce ordering, IIRC
majnemer had an example of this), but I
don't think LLVM's model specifies.</div>
</div>
</div>
</div>
</blockquote>
<div><br>
</div>
</span>
<div>IIRC, the example was something like:</div>
<div><br>
</div>
<div>
<div>
<div>void barrier() {</div>
<div> std::atomic<int> z;</div>
<div> z.store(1, std::memory_order_seq_cst);</div>
<div>}</div>
</div>
</div>
<div><br>
</div>
<div>Does the modification to 'z' participate in the
total ordering?</div>
<div>LLVM doesn't think so.</div>
<div>ICC emits an mfence and no store.</div>
<div>GCC emits an mfence and a store.</div>
<div><br>
</div>
<div>I think LLVM's behavior here is defensible.</div>
<div>
<div class="h5">
<div> <br>
</div>
<blockquote class="gmail_quote" style="margin:0px
0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<div dir="ltr">
<div class="gmail_extra">
<div class="gmail_quote">
<div><br>
</div>
<div><br>
</div>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">If
I know something is unescaped:<br>
- I can change the representation of
the contents. (Even if the pointer
*value* has been captured.)<br>
<br>
If I know something is uncaptured:<br>
- I can change the address of the
allocation (but not the internal
layout of the contents.)<br>
<br>
<br>
<br>
<br>
On 06/07/2016 12:56 PM, Nuno Lopes
wrote:<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hey
Philip,<br>
<br>
I think it's important to know
where/why in LLVM it makes a
different re. capture vs escape. Do
you recall the different needs of
the current clients (AA, etc)?<br>
<br>
Thanks,<br>
Nuno<br>
<br>
-----Original Message-----<br>
From: Philip Reames [mailto:<a
moz-do-not-send="true"
href="mailto:listmail@philipreames.com"
target="_blank">listmail@philipreames.<wbr>com</a>]<br>
Sent: 06 June 2016 21:51<br>
To: Scott Egerton <<a
moz-do-not-send="true"
href="mailto:scott.egerton1@gmail.com"
target="_blank">scott.egerton1@gmail.com</a>>;
Nuno Lopes <<a
moz-do-not-send="true"
href="mailto:nunoplopes@sapo.pt"
target="_blank">nunoplopes@sapo.pt</a>><br>
Cc: Anna Thomas <<a
moz-do-not-send="true"
href="mailto:anna@azul.com"
target="_blank">anna@azul.com</a>>;
Sanjoy Das <<a
moz-do-not-send="true"
href="mailto:sanjoy@azulsystems.com"
target="_blank">sanjoy@azulsystems.com</a>><br>
Subject: Re: [llvm-dev] [GSoC 2016]
Capture Tracking Improvements -
BackgroundInformation<br>
<br>
Scott,<br>
<br>
Sorry I missed this. Clearly I need
to adjust my mail filters now that
I'm not able to keep up with
llvm-dev on a routine basis. (Goes
and does so.. okay, should be
addressed.)<br>
<br>
Nuno's suggestion is a good one,
though I'd make sure to read with a
bit of skeptical eye. A lot of the
work on escape analysis tends
towards ever more complicated
analyzes and handling corner cases.
Frankly, we miss enough of the
*simple* cases that we need to start
there. One important point worth
stating explicitly: many many
seemingly complicated cases turn out
to be addressable through the
iterative application of simpler
algorithms. Another general design
thing to keep in mind: Many complex
problems look simple once you find
the right way to slice the problem.
:)<br>
<br>
One really interesting approach I'd
recommend you read is the "partial<br>
escape analysis" stuff done by the
Graal compiler project. It has a<br>
lot of parallels to our
mayBeCapturedBefore. One reasonable
starting point is:<br>
<a moz-do-not-send="true"
href="https://wiki.openjdk.java.net/display/Graal/Graal+Partial+Escape+Analysis"
rel="noreferrer" target="_blank">https://wiki.openjdk.java.net/<wbr>display/Graal/Graal+Partial+<wbr>Escape+Analysis</a>.
<br>
I *think* the best paper starting
point might be "Partial Escape
Analysis and Scalar Replacement for
Java", but there a couple of papers
published by this group. You'll
have to read each of them to get a
full picture of the approach.<br>
<br>
One small thing to watch out for:
"capture" and "escape" are NOT the
same thing. A pointer may be
captured if it's address is
inspected, even if the allocation
never actually escapes. They are
very related notions, but keeping
the difference in mind is necessary.<br>
<br>
Philip
<div>
<div><br>
<br>
On 06/02/2016 01:12 AM, Scott
Egerton wrote:<br>
<blockquote class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hi
Nuno,<br>
<br>
This is great, thank you.<br>
<br>
Scott<br>
<br>
On 30 May 2016 23:15:33 BST,
Nuno Lopes <<a
moz-do-not-send="true"
href="mailto:nunoplopes@sapo.pt"
target="_blank">nunoplopes@sapo.pt</a>>
wrote:<br>
<blockquote
class="gmail_quote"
style="margin:0px 0px 0px
0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">Hey
Scott,<br>
<br>
There has been quite a lot
of research on capture
tracking (aka<br>
escape<br>
analysis) for Java and other
dynamic languages.<br>
See e.g.:<br>
<a moz-do-not-send="true"
href="https://wiki.openjdk.java.net/display/HotSpot/EscapeAnalysis"
rel="noreferrer"
target="_blank">https://wiki.openjdk.java.net/<wbr>display/HotSpot/EscapeAnalysis</a><br>
<a moz-do-not-send="true"
href="http://docs.oracle.com/javase/7/docs/technotes/guides/vm/performance-"
rel="noreferrer"
target="_blank">http://docs.oracle.com/javase/<wbr>7/docs/technotes/guides/vm/<wbr>performance-</a><br>
enhancements-7.html<br>
<a moz-do-not-send="true"
href="http://dl.acm.org/citation.cfm?doid=320384.320386"
rel="noreferrer"
target="_blank">http://dl.acm.org/citation.<wbr>cfm?doid=320384.320386</a><br>
<br>
Nuno<br>
<br>
-----Original Message-----<br>
From: Scott Egerton via
llvm-dev<br>
Sent: Saturday, May 28, 2016
5:10 PM<br>
To: Philip Reames<br>
Cc: llvm-dev<br>
Subject: [llvm-dev] [GSoC
2016] Capture Tracking
Improvements -<br>
BackgroundInformation<br>
<br>
Hi Phillip,<br>
<br>
I've been looking into the
Capture Tracking
Improvements and I was<br>
wondering if there was any
research/documentation that
you know of<br>
that I could use as
background reading?<br>
<br>
Many thanks,<br>
Scott<br>
</blockquote>
</blockquote>
<br>
</div>
</div>
</blockquote>
<br>
</blockquote>
<div>
<div>
<br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org"
target="_blank">llvm-dev@lists.llvm.org</a><br>
<a moz-do-not-send="true"
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
</div>
</div>
</blockquote>
</div>
<br>
</div>
</div>
</blockquote>
</div>
</div>
</div>
<br>
</div>
</div>
<br>
______________________________<wbr>_________________<br>
LLVM Developers mailing list<br>
<a moz-do-not-send="true"
href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a moz-do-not-send="true"
href="http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev"
rel="noreferrer" target="_blank">http://lists.llvm.org/cgi-bin/<wbr>mailman/listinfo/llvm-dev</a><br>
<br>
</blockquote>
</div>
<br>
<br clear="all">
<div><br>
</div>
-- <br>
<div class="gmail_signature" data-smartmail="gmail_signature">
<div dir="ltr">
<div><i style="font-size:12.8px">Disclaimer: Views,
concerns, thoughts, questions, ideas expressed in this
mail are of my own and my employer has no take in it. </i><br>
</div>
<div>Thank You.<br>
Madhur D. Amilkanthwar<br>
<br>
</div>
</div>
</div>
</div>
</blockquote>
<br>
</body>
</html>