[llvm-dev] [GSoC 2016] Capture Tracking Improvements - BackgroundInformation
Philip Reames via llvm-dev
llvm-dev at lists.llvm.org
Tue Jun 7 16:02:04 PDT 2016
(+CC LLVM dev - I'd dropped it in my original reply unintentionally and
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
> 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)?
>> -----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 -
>> 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:
>> 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.
>> On 06/02/2016 01:12 AM, Scott Egerton wrote:
>>> Hi Nuno,
>>> This is great, thank you.
>>> 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
>>>> analysis) for Java and other dynamic languages.
>>>> See e.g.:
>>>> -----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 -
>>>> 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,
More information about the llvm-dev