[llvm-dev] [GSoc 2016] Proposal - Capture Tracking Improvements

[Scott Egerton via llvm-dev]

Hi Phillip,

Thank you for the feedback. I will be updating this as I learn more.

Many thanks,
Scott

> -----Original Message-----
> From: Philip Reames [mailto:listmail at philipreames.com]
> Sent: 22 April 2016 17:32
> To: Scott Egerton; llvm-dev at lists.llvm.org
> Cc: mehdi.amini at apple.com
> Subject: Re: [GSoc 2016] Proposal - Capture Tracking Improvements
> 
> (I've copied the body of the text from the PDF into the email and am replying
> inline to particularly parts.)
> 
> On 04/16/2016 10:43 AM, Scott Egerton wrote:
> > Hello,
> >
> > Attached is the proposal that I have submitted. I would be grateful for any
> and all feedback provided.
> >
> > Many Thanks,
> > Scott
> >
> > C APTURE T RACKING I MPROVEMENTS
> > ABSTRACT
> > Capture tracking analysis is an analysis pass used to determine which
> > pointers are "captured". This means that a function has made a copy of
> > a pointer that has outlived the function that called it.
> Subtle but important clarification: "has outlived" to "may potentially outlive".
> As with most compiler analysis, we have to be conservative when we can't
> fully analyze.
> > This information is useful during the optimisation process. I believe
> > that this is used to improve memory management.
> Via aliasing primarily.  Yes.
> > The capture tracking analysis is currently inefficient and inaccurate
> > in cases due to the fact that it returns false positives and expensive
> > functions are unnecessarily repeated.
> We'll always have false positives.  The trick is to get a reasonably small
> number with a reasonable impact on compile time.  The universal problem
> balance in a compiler.
> > This is where I would make improvements. It could be improved in a
> > number of ways, as mentioned by Philip Reames on the mailing list. I
> > would like to use this opportunity to take my previous experience
> > within LLVM and apply it to other areas of LLVM.
> >
> > BENEFITS
> >
> > Improvements to pointer capture tracking would be greatly beneficial.
> > Changes such as the removal of false positives as well as the
> > reduction to the cost through the introduction of caching will be
> > made. Caching the results of certain functions, storing the result,
> > will cause performance increases, should the same data be requested
> > again as the result will already be stored. As a result of this, it
> > could become a more valuable tool to have within the LLVM suite. This
> > would also cause improvements to the code optimisation process and
> potentially increase the quality of code compiled with LLVM. It should also
> use up fewer resources during the analysis pass.
> >
> > DELIVERABLES
> >
> > There are cases where "potentially captured" is returned incorrectly.
> > As a starter task I would remove the known and unknown cases that
> > cause this to occur. This would serve as a good introduction to LLVM
> > compiler analysis and would be achievable in a short time span.
> > Approximately 2 weeks.
> It would be good to gather a concrete list of known false positives.  I can help
> with this, but I'd like you to do a first pass over the code and bug tracking
> system first.  Another approach is to instrument the analysis, print each
> potentially captured result, and scan through the output when compiling a
> largish piece of code.  Do you see a common pattern which looks worth
> analyzing further?
> 
> FYI, two weeks may be very optimistic.  I suspect you'll iterate on this a
> couple of times finding more and more cases each time. Getting each change
> implemented and reviewed will take a couple of days.  Thankfully, the
> analysis and review time should easily overlap.  We can also overlap this with
> the design work for the next part.
> > By making changes to the current design, this could be made to be more
> > cost effective than it currently is. I would do this by caching the
> > results as previously suggested. This will be used to invalidate results when
> required.
> > Approximately 6 weeks.
> You will definitely need a more concrete proposal for what caching and
> invalidation scheme you're using.  I'd suggest reviewing callers of
> PointerMayBeCaptured to get a sense for what's going on.  I can also help
> with this.  (We should setup a skype call or something if your proposal gets
> approved.)
> 
> Once we have a proposal, we'll share this before you start implementation.
> That will give us a chance to find design problems early.  :)
> > The analysis could be made more accurate in order to recognise object
> > sub- graphs which do not escape.
> > Approximately 5 weeks.
> I honestly doubt you'll get to this in the summer, but that's okay. Once we
> get closer to actually working on this, we'll need to drill in and make a more
> concrete proposal.  There's a bunch of algorithms which could be used here
> and picking one will take some thought.
> > 1 | S COTT E GERTONThis work will link in with other ongoing work
> > within LLVM and will assist other developers working on compiler
> > analysis. I believe that I may be able to complete this work within 11
> > weeks; however I have allocated the extra time to account for any issues I
> may encounter.
> I'm going to push strongly to have you contributing incrementally through the
> normal LLVM development process.  This will mean that if something runs
> long and you don't get to finish, most of the supporting work will already
> have landed.  (e.g. If we don't get to the object graph part, at least we'll have
> the caching improvements.)
> > BIOGRAPHICAL INFORMATION
> > I have been working on LLVM for the past year as an industrial
> > placement student within the MIPS compiler team and am keen to do
> more
> > LLVM work. I am a BSc Computer Science student at the University of
> > Hull and will begin my final year of study in September. In the past I
> > have worked on a University project which required me to be inventive
> with data structures in order to efficiently solve the given problem.
> > I thoroughly enjoyed this and would be grateful for another
> > opportunity to exercise my design skills.
> > Due to other commitments with my current industrial placement,
> > unfortunately I will be unable to work on this project during working
> > hours (9-5 GMT) until the first week of June. However, I am more than
> > happy to make up this time as the summer progresses.
> June is fine by me.  If anything, that works better for my schedule anyways.
> 
> Philip
>