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

Thu Jun 9 10:43:49 PDT 2016

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>