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

[Scott Egerton via llvm-dev]

Thank you for this write up, it is very useful

Many thanks,
Scott

On Tue, 2016-06-07 at 16:02 -0700, Philip Reames 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.)
> > 
> > 
> > 
> > 
> > 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.c
> > > om>
> > > 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/perf
> > > > > ormance-
> > > > > 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
> > > 
> > 
>