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

Tue Jun 7 18:27:53 PDT 2016

> 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