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

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

(+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.
>
> 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
>>
>

> On 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.
>> 
>> 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.)
Thanks for all the write-up, I found it very helpful. Especially since coming
from a C/C++ background the distinction captured/escaped wasn't clear to me.

It seems that we indeed assume that "capture" implies
"escape" in LLVM (conservatively).
I observed that it matters frequently when you have load/store from/to a global
variable, and you can't know it does not "escape" because it is
"captured" somehow. The alias analysis has to conservatively consider
these load/store as "may alias" with any other pointer load/store.

-- 
Mehdi


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

Great, thanks Philip!
Nuno

-----Original Message-----
From: Philip Reames [mailto:listmail at philipreames.com] 
Sent: 08 June 2016 00:02
Subject: Re: [llvm-dev] [GSoC 2016] Capture Tracking Improvements -
BackgroundInformation

(+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.
>
> 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/performanc
>>>> e-
>>>> 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
>>
>

Thank you for this write up, it is very useful

Many thanks,
Scott

On Tue, 2016-06-07 at 16:02 -0700, Philip Reames 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.
> > 
> > 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.c
> > > om>
> > > 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/perf
> > > > > ormance-
> > > > > 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
> > > 
> > 
>

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>