<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:0 0 0 .8ex;border-left:1px #ccc solid;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:0 0 0 .8ex;border-left:1px #ccc solid;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/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><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;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:0 0 0 .8ex;border-left:1px #ccc solid;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.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/display/Graal/Graal+Partial+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 class="h5"><br>
<br>
On 06/02/2016 01:12 AM, Scott Egerton wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;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:0 0 0 .8ex;border-left:1px #ccc solid;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/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/7/docs/technotes/guides/vm/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.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 class="HOEnZb"><div class="h5">
<br>
_______________________________________________<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/mailman/listinfo/llvm-dev</a><br>
</div></div></blockquote></div><br></div></div>