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

Thu Jun 9 11:25:35 PDT 2016

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>