[llvm-dev] [PM] I think that the new PM needs to learn about inter-analysis dependencies...

[Hal Finkel via llvm-dev]

----- Original Message -----

> From: "Chandler Carruth" <chandlerc at gmail.com>
> To: "Sean Silva" <chisophugis at gmail.com>
> Cc: "Xinliang David Li" <davidxl at google.com>, "llvm-dev"
> <llvm-dev at lists.llvm.org>, "Davide Italiano"
> <dccitaliano at gmail.com>, "Tim Amini Golling"
> <mehdi.amini at apple.com>, "Hal Finkel" <hfinkel at anl.gov>, "Sanjoy
> Das" <sanjoy at playingwithpointers.com>, "Pete Cooper"
> <peter_cooper at apple.com>
> Sent: Wednesday, July 13, 2016 2:34:35 AM
> Subject: Re: [PM] I think that the new PM needs to learn about
> inter-analysis dependencies...

> On Wed, Jul 13, 2016 at 12:25 AM Sean Silva < chisophugis at gmail.com >
> wrote:

> > On Tue, Jul 12, 2016 at 11:39 PM, Chandler Carruth <
> > chandlerc at gmail.com > wrote:
> 

> > > On Tue, Jul 12, 2016 at 11:34 PM Sean Silva <
> > > chisophugis at gmail.com
> > > >
> > > wrote:
> > 
> 

> > > > On Tue, Jul 12, 2016 at 11:32 PM, Xinliang David Li <
> > > > davidxl at google.com > wrote:
> > > 
> > 
> 

> > > > > On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <
> > > > > chandlerc at gmail.com > wrote:
> > > > 
> > > 
> > 
> 

> > > > > > Yea, this is a nasty problem.
> > > > > 
> > > > 
> > > 
> > 
> 

> > > > > > One important thing to understand is that this is specific
> > > > > > to
> > > > > > analyses which hold references to other analyses. While
> > > > > > this
> > > > > > isn't
> > > > > > unheard of, it isn't as common as it could be. Still,
> > > > > > definitely
> > > > > > something we need to address.
> > > > > 
> > > > 
> > > 
> > 
> 
> > > > > We can call this type of dependencies (holding references)
> > > > > hard-dependency. The soft dependency refers to the case where
> > > > > analysis 'A' depends on 'B' during computation, but does not
> > > > > need
> > > > > 'B' once it is computed.
> > > > 
> > > 
> > 
> 

> > > > > There are actually quite a few examples of hard-dependency
> > > > > case.
> > > > > For
> > > > > instance LoopAccessInfo, LazyValueInfo etc which hold
> > > > > references
> > > > > to
> > > > > other analyses.
> > > > 
> > > 
> > 
> 

> > > > > Problem involving hard-dependency is actually easier to
> > > > > detect,
> > > > > as
> > > > > it
> > > > > is usually a compile time problem. Issues involving soft
> > > > > dependencies are more subtle and can lead to wrong code gen.
> > > > 
> > > 
> > 
> 
> > > > Did you mean to say that soft-dependency problems are easier to
> > > > detect? At least my intuition is that soft-dependency is easier
> > > > because there is no risk of dangling pointers to other
> > > > analyses.
> > > 
> > 
> 

> > > The issue is that the fact that there is *any* dependency isn't
> > > clear.
> > 
> 

> > > However, I think the only real problem here are these "hard
> > > dependencies" (I don't really like that term though). For others,
> > > only an analysis that is *explicitly* preserved survives. So I'm
> > > not
> > > worried about the fact that people have to remember this.
> > 
> 

> > > The question is how often there are cross-data-structure
> > > references.
> > > David mentions a few examples, and I'm sure there are more, but
> > > it
> > > isn't clear to me yet whether this is pervasive or occasional.
> > 
> 
> > I just did a quick run-through of PassRegistry.def and this is what
> > I
> > found:
> 

> > Module analyses: 0/5 hold pointers to other analyses
> 
> > CallGraph: No pointers to other analyses.
> 
> > LazyCallGraph: No pointers to other analyses.
> 
> > ProfileSummaryAnalysis: No pointers to other analyses.
> 
> > TargetLibraryAnalysis: No pointers to other analyses.
> 

> > VerifierAnalysis: No pointers to other analyses.
> 

> > Module alias analyses: 1/1 keeps pointer to other analysis.
> 
> > GlobalsAA: Result keeps pointer to TLI (this is a function
> > analysis).
> 

> > Function analyses: 9/17 keep pointers to other analysis
> 
> > AAManager: Its Result holds TLI pointer and pointers to individual
> > AA
> > result objects.
> 
> > AssumptionAnalysis: No pointers to other analyses.
> 

> > BlockFrequencyAnalysis: Its Result holds pointers to LoopInfo and
> > BPI.
> 

> > BranchProbabilityAnalysis: Stores no pointers to other analyses.
> > (uses LoopInfo to "recalculate" though)
> 

> > DominatorTreeAnalysis: Stores no pointers to other analyses.
> 

> > PostDominatorTreeAnalysis: Stores no pointers to other analyses.
> 
> > DemandedBitsAnalysis: Stores pointers to AssumptionCache and
> > DominatorTree
> 

> > DominanceFrontierAnalysis: Stores no pointers to other analyses.
> > (uses DominatorTreeAnalysis for "recalculate" though).
> 

> > LoopInfo: Uses DominatorTreeAnalysis for "recalculate" but stores
> > no
> > pointers.
> 

> > LazyValueAnalysis: Stores pointers to AssumptionCache,
> > TargetLibraryInfo, DominatorTree.
> 

> > DependenceAnalysis: Stores pointers to AliasAnalysis,
> > ScalarEvolution, LoopInfo
> 
> > MemoryDependenceAnalysis: Stores pointers to AliasAnalysis,
> > AssumptionCache, TargetLibraryInfo, DominatorTree
> 

> > MemorySSAAnalysis: Stores pointers to AliasAnalysis, DominatorTree
> 

> > RegionInfoAnalysis: Stores pointers to DomTree, PostDomTree,
> > DomFrontier
> 

> > ScalarEvolutionAnalysis: Stores pointers to TargetLibraryInfo,
> > AssumptionCache, DominatorTree, LoopInfo
> 
> > TargetLibraryAnalysis: Has no dependencies
> 

> > TargetIRAnalysis: Has no dependencies.
> 

> > Function alias analyses: 3/5 keep pointers to other analyses
> 
> > BasicAA: Keeps pointers to TargetLibraryInfo, AssumptionCache,
> > DominatorTree, LoopInfo
> 
> > CFLAA: Keeps pointer to TargetLibraryInfo
> 
> > SCEVAA: Keeps pointer to ScalarEvolution
> 
> > ScopedNoAliasAA: No dependencies
> 

> > TypeBasedAA: No dependencies
> 

> > Total: 13/28 analyses (~50%) hold pointers to other analyses.
> 
> > Of the 15/28 analyses that don't hold pointers, 12/15 simply have
> > no
> > dependencies. Only 3/15 (BPI, LoopInfo, DominanceFrontier) have
> > dependencies that are used just for a "recalculate" step that
> > retains no pointers.
> 
> > So I think it is fair to say that analyses which hold pointers to
> > other analyses is not an exceptional case. In fact, analyses that
> > use other analyses just for a "recalculate" step seems to be the
> > exceptional case (only 3/28 or about 10%)
> 
> Interesting!

> Most of these look like they hold a pointer to the root analysis as
> opposed to detailed objects *inside* the analysis?

> It might make sense to try to handle this very specific pattern in a
> special way of overriding the invalidate routines is too error
> prone.... We could try to make this work "automatically" but I'm
> worried this would be challenging to get right. Open to suggestions
> of course.
I think that Sean laid out pretty clearly in response to my initial comment what would be required, in terms of infrastructure (type-erased invalidation objects and a registration scheme to cancel them). 

Regardless of how we move forward here, we should probably try to limit the scope of the problem by, as a matter of policy, only having passes that hold pointers to analysis-generated data structures (e.g. SCEV*) hold pointers to the analysis objects themselves (in between queries). 

> Any other ideas about what would make sense to handle this?

> Does it make sense to override the invalidate routines now and
> iterate from there?
I'm happy to see what this looks like. 

Thanks again, 
Hal 

> I feel like you've done a lot of the research necessary for this
> already...
-- 

Hal Finkel 
Assistant Computational Scientist 
Leadership Computing Facility 
Argonne National Laboratory 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160713/9db40def/attachment.html>