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

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.


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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160609/a2b0076f/attachment.html>

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
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160609/73ad6a47/attachment-0001.html>

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