<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 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 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 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 href="mailto:listmail@philipreames.com" target="_blank">listmail@philipreames.<wbr>com</a>]<br>
Sent: 06 June 2016 21:51<br>
To: Scott Egerton <<a href="mailto:scott.egerton1@gmail.com" target="_blank">scott.egerton1@gmail.com</a>>; Nuno Lopes <<a href="mailto:nunoplopes@sapo.pt" target="_blank">nunoplopes@sapo.pt</a>><br>
Cc: Anna Thomas <<a href="mailto:anna@azul.com" target="_blank">anna@azul.com</a>>; Sanjoy Das <<a 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 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 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 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 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 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 href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a><br>
<a 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 href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a><br>
<a 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>