[llvm-dev] [GSoC 2016] Capture Tracking Improvements - BackgroundInformation
Philip Reames via llvm-dev
llvm-dev at lists.llvm.org
Fri Dec 2 11:10:34 PST 2016
For the record, I am not a C++ expert or a concurrency expert. Take
everything I say with several grains of salt...
If I remember the key parts of the C++ spec, an atomic store
synchronizes with (establishes an ordering with) only other atomic
operations.
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.
acq_rel would seem to follow from the above.
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.
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.
Philip
On 12/02/2016 03:20 AM, Madhur Amilkanthwar wrote:
> [Philip]
> If I know something is thread local:
> - I can demote atomic accesses to non-atomic ones./
> /
>
> /[David]/
> /void barrier() {/
> / std::atomic<int> z;/
> / z.store(1, std::memory_order_seq_cst);/
> /}/
> /
> /
> /Does the modification to 'z' participate in the total ordering?/
> /LLVM doesn't think so./
> /ICC emits an mfence and no store./
> /GCC emits an mfence and a store./
> /
> /
> /I think LLVM's behavior here is defensible. /
> /
> /
> /
> /
> 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?
>
> On Thu, Jun 9, 2016 at 11:55 PM, David Majnemer via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
>
>
> On Thu, Jun 9, 2016 at 10:43 AM, JF Bastien <jfb at google.com
> <mailto:jfb at google.com>> wrote:
>
> On Tue, Jun 7, 2016 at 4:02 PM, Philip Reames via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote:
>
> (+CC LLVM dev - I'd dropped it in my original reply
> unintentionally and just noticed.)
>
> On 06/07/2016 01:35 PM, Philip Reames wrote:
>
> (This was written in a rush. There may be mistakes;
> if so I'll try to correct later.)
>
> At the moment, most of LLVM is worried about capture.
> The only exception I know of are:
> 1) isAllocSiteRemovable in
> InstCombine/InstructionCombining.cpp
> 2) The thread local logic used in LICM's store promotion
>
> Let me phrase this informally:
> - "capture" - can anyone inspect the bits of this pointer?
> - "escape" - can anyone inspect the contents of this
> allocation?
> - "thread escape" - can any other thread inspect the
> contents of this allocation?
>
> 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".
>
> Illustrative examples:
> - A function which returns the alignment of a pointer
> captures a pointer, but does not cause it to escape or
> become non-thread local.
> - 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.
> - 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.
>
> If I know something is thread local:
> - I can demote atomic accesses to non-atomic ones.
>
>
> 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.
>
>
> IIRC, the example was something like:
>
> void barrier() {
> std::atomic<int> z;
> z.store(1, std::memory_order_seq_cst);
> }
>
> Does the modification to 'z' participate in the total ordering?
> LLVM doesn't think so.
> ICC emits an mfence and no store.
> GCC emits an mfence and a store.
>
> I think LLVM's behavior here is defensible.
>
>
>
> If I know something is unescaped:
> - I can change the representation of the contents.
> (Even if the pointer *value* has been captured.)
>
> If I know something is uncaptured:
> - I can change the address of the allocation (but not
> the internal layout of the contents.)
>
>
>
>
> On 06/07/2016 12:56 PM, Nuno Lopes wrote:
>
> Hey Philip,
>
> 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)?
>
> Thanks,
> Nuno
>
> -----Original Message-----
> From: Philip Reames
> [mailto:listmail at philipreames.com
> <mailto:listmail at philipreames.com>]
> Sent: 06 June 2016 21:51
> To: Scott Egerton <scott.egerton1 at gmail.com
> <mailto:scott.egerton1 at gmail.com>>; Nuno Lopes
> <nunoplopes at sapo.pt <mailto:nunoplopes at sapo.pt>>
> Cc: Anna Thomas <anna at azul.com
> <mailto:anna at azul.com>>; Sanjoy Das
> <sanjoy at azulsystems.com
> <mailto:sanjoy at azulsystems.com>>
> Subject: Re: [llvm-dev] [GSoC 2016] Capture
> Tracking Improvements - BackgroundInformation
>
> Scott,
>
> 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.)
>
> 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. :)
>
> One really interesting approach I'd recommend you
> read is the "partial
> escape analysis" stuff done by the Graal compiler
> project. It has a
> lot of parallels to our mayBeCapturedBefore. One
> reasonable starting point is:
> https://wiki.openjdk.java.net/display/Graal/Graal+Partial+Escape+Analysis
> <https://wiki.openjdk.java.net/display/Graal/Graal+Partial+Escape+Analysis>.
>
> 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.
>
> 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.
>
> Philip
>
>
> On 06/02/2016 01:12 AM, Scott Egerton wrote:
>
> Hi Nuno,
>
> This is great, thank you.
>
> Scott
>
> On 30 May 2016 23:15:33 BST, Nuno Lopes
> <nunoplopes at sapo.pt
> <mailto:nunoplopes at sapo.pt>> wrote:
>
> Hey Scott,
>
> There has been quite a lot of research on
> capture tracking (aka
> escape
> analysis) for Java and other dynamic
> languages.
> See e.g.:
> https://wiki.openjdk.java.net/display/HotSpot/EscapeAnalysis
> <https://wiki.openjdk.java.net/display/HotSpot/EscapeAnalysis>
> http://docs.oracle.com/javase/7/docs/technotes/guides/vm/performance-
> <http://docs.oracle.com/javase/7/docs/technotes/guides/vm/performance->
> enhancements-7.html
> http://dl.acm.org/citation.cfm?doid=320384.320386
> <http://dl.acm.org/citation.cfm?doid=320384.320386>
>
> Nuno
>
> -----Original Message-----
> From: Scott Egerton via llvm-dev
> Sent: Saturday, May 28, 2016 5:10 PM
> To: Philip Reames
> Cc: llvm-dev
> Subject: [llvm-dev] [GSoC 2016] Capture
> Tracking Improvements -
> BackgroundInformation
>
> Hi Phillip,
>
> I've been looking into the Capture
> Tracking Improvements and I was
> wondering if there was any
> research/documentation that you know of
> that I could use as background reading?
>
> Many thanks,
> Scott
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>
>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
> <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
>
>
>
>
> --
> /Disclaimer: Views, concerns, thoughts, questions, ideas expressed in
> this mail are of my own and my employer has no take in it. /
> Thank You.
> Madhur D. Amilkanthwar
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161202/056436d4/attachment.html>
More information about the llvm-dev
mailing list