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

[Nuno Lopes via 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
>>
>