[llvm-dev] [PM] I think that the new PM needs to learn about inter-analysis dependencies...
Hal Finkel via llvm-dev
llvm-dev at lists.llvm.org
Thu Jul 14 19:58:58 PDT 2016
----- Original Message -----
> From: "Sean Silva" <chisophugis at gmail.com>
> To: "Hal Finkel" <hfinkel at anl.gov>
> 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>, "Sanjoy Das"
> <sanjoy at playingwithpointers.com>, "Pete Cooper"
> <peter_cooper at apple.com>, "Chandler Carruth" <chandlerc at gmail.com>
> Sent: Thursday, July 14, 2016 9:48:44 PM
> Subject: Re: [PM] I think that the new PM needs to learn about
> inter-analysis dependencies...
> On Thu, Jul 14, 2016 at 7:21 PM, Hal Finkel < hfinkel at anl.gov >
> wrote:
> > Hi Sean,
>
> > Thanks for writing all of this up. I'll go back to my previous
> > position: we need a general dependency graph built as the analysis
> > cache is used. It should have the following properties:
>
> > 1. When we call getResult or getCachedResult on an analysis
> > manager,
> > we record a dependency of the current pass on the returned result.
>
> > 2. This dependency needs to be stored such that it can be used to
> > invalidate the current result when the returned result is
> > invalidates and so that the dependency can be deleted when the
> > current result is invalidated.
>
> > As I understand the problem, this is a fully-general solution. I
> > see
> > no reason not to have a fully-general solution.
>
> Yeah, the mechanics of maintaining this fully general mapping are
> straightforward in the abstract (once we have a single analysis
> manager for all IRUnitT's). Essentially, the analysis manager
> maintains a stack of ( Analysis, IRUnit) that it is currently
> computing and pushes/pops the stack as it (re-)enters/exits
> get{,Cached}Result. If the stack is not empty (suppose top of stack
> is `(AnalysisFoo, IRUnitBar)`), then when we go to push
> `(AnalysisBaz, IRUnitQux)` we record a dependency that the result
> cached on key `(AnalysisBaz, IRUnitQux)` must be invalidated if the
> result cached on key `(AnalysisFoo, IRUnitBar)` is invalidated.
> The difficult part is what guarantees we provide about things being
> stale or not and how we invalidate when IRUnit's are deleted or
> created.
> For example, suppose a function pass DCE's a call which causes an SCC
> Foo of 3 functions to no longer be an SCC. When/how do analyses
> cached on Foo get invalidated? And is it valid to query them? One of
> the expected use cases (I'm told) for CGSCC passes is to propagate
> function-attribute like things, so these are being potentially
> queried by that same function pass.
I don't understand this example. Just because the function removes the call edge, theoretically breaking the SCC, will that automatically trigger an update of the CG data structure? I'd think that the CG itself won't be updated until the function pass is done (during which time the old CG will still be a valid over-approximation).
-Hal
> -- Sean Silva
> > Thanks again,
>
> > Hal
>
> > > From: "Sean Silva" < chisophugis at gmail.com >
> >
>
> > > To: "Chandler Carruth" < chandlerc 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: Thursday, July 14, 2016 4:11:58 AM
> >
>
> > > Subject: Re: [PM] I think that the new PM needs to learn about
> > > inter-analysis dependencies...
> >
>
> > > On Thu, Jul 14, 2016 at 12:51 AM, Sean Silva <
> > > chisophugis at gmail.com
> > > > wrote:
> >
>
> > > > On Wed, Jul 13, 2016 at 1:48 AM, Sean Silva <
> > > > chisophugis at gmail.com
> > > > >
> > > > wrote:
> > >
> >
>
> > > > > On Wed, Jul 13, 2016 at 12:34 AM, Chandler Carruth <
> > > > > chandlerc at gmail.com > wrote:
> > > >
> > >
> >
>
> > > > > > 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.
> > > > >
> > > >
> > >
> >
>
> > > > > > 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 feel like you've done a lot of the
> > > > > > research
> > > > > > necessary for this already...
> > > > >
> > > >
> > >
> >
>
> > > > > I'll keep pushing forward tomorrow with building test-suite
> > > > > successfully using the new PM for the LTO pipeline (I was
> > > > > doing
> > > > > some
> > > > > unrelated LLD stuff for most of today). It will be
> > > > > interesting
> > > > > to
> > > > > see how many `invalidate` overrides will be needed to avoid
> > > > > these
> > > > > issues for just the LTO pipeline on test-suite.
> > > >
> > >
> >
>
> > > > I spent the better part of today working on this and will
> > > > continue
> > > > tomorrow; this problem seems nastier than I thought. For some
> > > > reason
> > > > the LTO pipeline (or something about LTO) seems to hit on these
> > > > issues much more (I'm talking like 40k lines of ASan error
> > > > reports
> > > > from building test-suite with the LTO pipeline in the new PM;
> > > > per-TU
> > > > steps still using the old PM). Some notes:
> > >
> >
>
> > > > - BasicAA's dependence on domtree and loopinfo in the new PM
> > > > seems
> > > > to
> > > > account for quite a few of the problems.
> > >
> >
>
> > > > - BasicAA and other stuff are marked (by overriding
> > > > `invalidate`
> > > > to
> > > > return false) to never be invalidated because they are
> > > > "stateless".
> > > > However they still hold pointers and so they do need to be
> > > > invalidated.
> > >
> >
>
> > > > - CallGraph uses AssertingVH (PR28400) and so I needed a
> > > > workaround
> > > > similar to r274656 in various passes.
> > >
> >
>
> > > > - D21921 is holding up -- I haven't hit any issues with the
> > > > core
> > > > logic of that patch.
> > >
> >
>
> > > > - AAResults holds handles to various AA result objects. This
> > > > means
> > > > it
> > > > pretty much always needs to be invalidated unless you are sure
> > > > that
> > > > none of the AA's will get invalidated.
> > >
> >
>
> > > > The existing `invalidate` method doesn't have the right
> > > > semantics
> > > > for
> > > > even an error-prone solution :( We are going to need to make
> > > > some
> > > > significant changes to even get basic sanity I think. Perhaps
> > > > each
> > > > analysis can expose a "preserve" static function. E.g. instead
> > > > of
> > > > `PA.preserve<Foo>();` you have to do `Foo::setPreserved(PA);`.
> > >
> >
>
> > > > I'm actually not quite sure that that will even work. Once I
> > > > have
> > > > test-suite fully building successfully with the LTO pipeline in
> > > > the
> > > > new PM I'll be able to give a more confident answer (esp.
> > > > w.r.t.
> > > > the
> > > > manager for different IRUnitT's).
> > >
> >
>
> > > > But at this point I'm not confident running *any* pass pipeline
> > > > in
> > > > the new PM without at least assertions+ASan.
> > >
> >
>
> > > > We may want to have a proper design discussion around this
> > > > problem
> > > > though.
> > >
> >
>
> > > > Also I'd like to have test-suite working (by hook or by crook)
> > > > with
> > > > LTO in the new PM so we can get some numbers on the resident
> > > > set
> > > > impact of all this caching; if it is really problematic then we
> > > > may
> > > > need to start talking front-and-center about different
> > > > invalidation
> > > > policies for keeping this in check instead of leaving it as
> > > > something that we will be able to patch later.
> > >
> >
>
> > > > The more I think about it, the more I'm convinced that the real
> > > > "hard" problem that the new PM is exposing us to is having the
> > > > ability for any pass to ask for any analysis on any IRUnitT
> > > > (and
> > > > any
> > > > specific IRUnit of that IRUnitT) and have the result stored
> > > > somewhere and then invalidated. This means that
> > > > "getAnalysisUsage"
> > > > is not just a list of passes, but much more complicated and is
> > > > essentially a set of arbitrary pairs "(analysis, IRUnit)" (and
> > > > the
> > > > associated potential tangle of dependencies between the state
> > > > cached
> > > > on these tuples). With the old PM, you essentially are looking
> > > > at
> > > > a
> > > > problem of scheduling the lifetime of analyses of the same
> > > > IRUnit
> > > > intermingled with transformation passes on that same IRUnit, so
> > > > you
> > > > only have the "analysis" part of the tuple above, making things
> > > > much
> > > > simpler (and handling dependencies is much simpler too).
> > >
> >
>
> > > To clarify, it seems like the current new PM is essentially
> > > trying
> > > to
> > > solve the problem of maintaining/updating a mapping:
> >
>
> > > (Analysis, IRUnit) -> AnalysisResult
> >
>
> > > where the AnalysisResult's can have an arbitrary dependency on an
> > > arbitrary set of other AnalysisResult's currently maintained in
> > > this
> > > mapping. In order to invalidate any AnalysisResult you need to
> > > invalidate all AnalysisResult's that transitively depend on it.
> > > Therefore the right-hand side of this mapping needs to be
> > > something
> > > like `(AnalysisResult, SetOfDependents)`.
> >
>
> > > So the mapping is really `(Analysis, IRUnit) -> (AnalysisResult,
> > > SetOfDependents)`
> >
>
> > > Also, this mapping can be updated at any point during the
> > > execution
> > > of a transformation pass (and various other places) and must stay
> > > correct as the IR is changed (more on this below).
> >
>
> > > For example, you might have something like:
> >
>
> > > (DominatorTreeAnalysis, function @foo) -> (DominatorTree for
> > > @foo,
> > > [(DemandedBitsAnalysis, function @foo)])
> >
>
> > > (AssumptionAnalysis, function @foo) -> (AssumptionCache for @foo,
> > > [(DemandedBitsAnalysis, function @foo)])
> >
>
> > > (DemandedBitsAnalysis, function @foo) -> (DemandedBits for @foo,
> > > [])
> >
>
> > > (AssumptionAnalysis, function @bar) -> (AssumptionCache for @bar,
> > > [(SomeModuleAnalysis, module TheModule)])
> >
>
> > > (AssumptionAnalysis, function @baz) -> (AssumptionCache for @baz,
> > > [(SomeModuleAnalysis, module TheModule)])
> >
>
> > > (SomeModuleAnalysis, module TheModule) ->
> > > (SomeModuleAnalysisResult
> > > for TheModule, [(SomeFunctionAnalysis, function @baz)])
> >
>
> > > (SomeFunctionAnalysis, function @baz) ->
> > > (SomeFunctionAnalysisResult
> > > for @baz, [])
> >
>
> > > So for example, when a transformation pass invalidates
> > > `(AssumptionAnalysis, function @bar)`, we need to walk
> > > `(SomeModuleAnalysis, module TheModule)` and
> > > `(SomeFunctionAnalysis,
> > > function @baz)` to invalidate them.
> >
>
> > > Compare this with the old PM (although like I said we have
> > > outgrown
> > > this model). Essentially you take the previous mapping, and
> > > require
> > > IRUnit to be a constant at any given point in time. Hence the
> > > mapping is essentially
> >
>
> > > Analysis -> AnalysisResult
> >
>
> > > Since this is 1:1 there is no real distinction between the
> > > Analysis
> > > and the AnalysisResult (and as part of transitioning to the new
> > > PM
> > > this has had to be untangled).
> >
>
> > > This also makes the dependencies simpler since you just have a
> > > set
> > > of
> > > "what analyses have been run at this point". You just need to run
> > > the analyses individually and make sure they are in the right
> > > order.
> > > Also, getAnalysis just takes the Analysis to get the
> > > AnalysisResult
> > > which makes it simpler -- you just query which analyses are live.
> >
>
> > > Also, the mapping `(Analysis, IRUnit) -> (AnalysisResult,
> > > SetOfDependents)` that the new PM is essentially trying to keep
> > > is
> > > even more complicated because for e.g. Loop and CGSCC passes the
> > > IRUnit itself is an object created by an analysis and subject to
> > > invalidation of that analysis as the IR changes underneath it.
> >
>
> > > And then there is the question of at what points must this
> > > mapping
> > > be
> > > valid (i.e. no stale analysis results, no dangling pointers,
> > > etc.)
> > > and when the transitive invalidation walking happens. Evidently
> > > while a transformation pass is running, things might temporarily
> > > be
> > > stale; what are the "checkpoints" where the mapping is guaranteed
> > > to
> > > be valid? At the start of each transformation pass? At least
> > > Chandler's D21464 does not stick to this because the IRUnit's
> > > (SCC's) are only updated at the end of running potentially many
> > > function transformation passes. I.e. all but the first function
> > > transformation pass might observe stale IRUnit's (SCC's).
> >
>
> > > One other thing to note is that soft-dependencies (using David's
> > > terminology) don't require this kind of dependency tracking. An
> > > analysis result can be cached even though its soft-dependencies
> > > are
> > > not cached. And invalidation of soft-dependencies does not
> > > require
> > > invalidating the soft-dependents. Actually, this makes it the
> > > terminology "soft" and "hard' quite natural; "hard" requires an
> > > edge
> > > to track the dependency for invalidation purposes, "soft" does
> > > not.
> >
>
> > > This is all quite general. Perhaps too much. We clearly need to
> > > go
> > > beyond the old PM's model, but we may not need to go to the fully
> > > general case. Is there a good middle-ground that meets our needs?
> > > What restrictions would we be willing to live with in order to
> > > make
> > > it easier? The first one on my list is to not have the IRUnit's
> > > themselves depend on analyses. Like Chandler mentioned on D21921
> > > this has the effect of e.g. preventing caching across the
> > > intervening module pass in a case like
> > > `module(cgscc(require<foo-cgscc-analysis>),some-module-pass-that-makes-no-changes,cgscc(some-cgscc-pass-that-uses-foo-cgscc-analysis))`
> > > but that seems like a restriction we can live with.
> >
>
> > > Again, sorry for the braindump.
> >
>
> > > -- Sean Silva
> >
>
> > > > We've obviously outgrown this model with examples like LAA,
> > > > AssumptionCacheTracker, etc. that hack around this in the old
> > > > PM.
> > > > We
> > > > may want to have a fresh re-examination of what problems we are
> > > > exactly trying to solve.
> > >
> >
>
> > > > For me, my main concern now is what changes need to be made in
> > > > order
> > > > to feel confident running a pipeline in the new PM without
> > > > assertions+ASan.
> > >
> >
>
> > > > Sorry for the long post, just brain-dumping before heading
> > > > home.
> > >
> >
>
> > > > -- Sean Silva
> > >
> >
>
> > > > > -- Sean Silva
> > > >
> > >
> >
>
> > --
>
> > Hal Finkel
>
> > Assistant Computational Scientist
>
> > Leadership Computing Facility
>
> > Argonne National Laboratory
>
--
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/20160714/bae91680/attachment.html>
More information about the llvm-dev
mailing list