[llvm-dev] [GSoC 2016] Capture Tracking Improvements - BackgroundInformation

Fri Dec 2 03:20:48 PST 2016

[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> wrote:

>
>
> On Thu, Jun 9, 2016 at 10:43 AM, JF Bastien <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> 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]
>>>>> Sent: 06 June 2016 21:51
>>>>> To: Scott Egerton <scott.egerton1 at gmail.com>; Nuno Lopes <
>>>>> nunoplopes at sapo.pt>
>>>>> Cc: Anna Thomas <anna at azul.com>; Sanjoy Das <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.
>>>>> 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> 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
>>>>>>> http://docs.oracle.com/javase/7/docs/technotes/guides/vm/
>>>>>>> performance-
>>>>>>> enhancements-7.html
>>>>>>> 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
>>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>>
>>
>>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> 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/8ec5e201/attachment.html>