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

Philip Reames via llvm-dev llvm-dev at lists.llvm.org
Sun Aug 7 16:55:28 PDT 2016

Skimming the thread, this post is the clearest path forward I've seen.  
Minor comments inline, but I generally like this framing.

On 07/14/2016 08:04 PM, Chandler Carruth via llvm-dev wrote:
> We need better terminology to talk about this. I propose:
> analysis-dependencies: analysis A uses result of analysis B when 
> *running* an analysis and not used by the result
> query-dependencies: result of analysis A uses result of analysis B 
> when evaluating a query
> data-structure-depnedencies: result of analysis A uses data structures 
> from the result of analysis B inside its own data structures
> I think these are much more precise than "hard" or "soft" and expose 
> more facets.
> For analysis-depnedencies, I continue to think they work correctly. If 
> a transformation claims it preserves an analysis, it must actually 
> know this to be true. I don't see any actual problems here in practice 
> today, and this isn't actually something changed in the new PM.
> For data-structure-dependencies, the investigation done by Sean seems 
> to clearly show these to be rare, and I think having their invalidate 
> methods be overridden to test that *all* of the data structures they 
> depend on are preserved is the correct approach.
This may end up being too error prone.  That seems to be Sean's concern 
down thread.  I am also worried about that, but assuming the number of 
such occurrences are low, it seems reasonable to start with this 
approach and revisit if needed.
> The primary issue seems to be with query-dependencies. These in turn 
> break down into two categories:
> 1) query-dependencies on "immutable" analysis results. These are 
> results that we *never* expect to be invalidated and we just want easy 
> access to. TargetLibraryInfo is the classic example here.
> 2) query-dependencies on normal analysis results. DominatorTree and 
> and AAResults are the primary examples here.
> I would like to have a simple way to handle #1 by ensuring 
> invalidation doesn't occur. I think this already works, but I'm 
> interested if there is actually an issue here.
> We *could* handle #2 much like data-structure-dependencies, but I hear 
> Hal and others that this would become burdensome. However, my 
> preference would be to instead handle #2 by making result APIs accept 
> direct handles to the analysis results they rely on.
> The reason for preferring this approach is because I think it makes 
> the relationship between these things much more clear to users of the 
> analyses.
+1 to this.  Having the query dependencies explicit at the call site 
would generally make the code much easier to understand and thus much 
more likely to be correct.  I recently ran across an issue in LVI under 
the old pass manager that looks highly suspicious, but because the code 
is quite complex (putting it mildly), I wasn't sure whether it was 
correct or not.  Having the additional analyzes passed in explicitly 
through the query would make many of these cases substantially easier to 
> I think the most annoying of these to handle are aggregation-style 
> analyses results like AAResults. There, I think it might make more 
> sense to handle them along the lines of data-structure-dependencies. I 
> don't think we have so many of those that this would be a significant 
> burden IMO.
> On Thu, Jul 14, 2016 at 7:48 PM Sean Silva <chisophugis at gmail.com 
> <mailto:chisophugis at gmail.com>> wrote:
>     On Thu, Jul 14, 2016 at 7:21 PM, Hal Finkel <hfinkel at anl.gov
>     <mailto: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.
>     -- Sean Silva
>         Thanks again,
>         Hal
>         ------------------------------------------------------------------------
>             *From: *"Sean Silva" <chisophugis at gmail.com
>             <mailto:chisophugis at gmail.com>>
>             *To: *"Chandler Carruth" <chandlerc at gmail.com
>             <mailto:chandlerc at gmail.com>>
>             *Cc: *"Xinliang David Li" <davidxl at google.com
>             <mailto:davidxl at google.com>>, "llvm-dev"
>             <llvm-dev at lists.llvm.org
>             <mailto:llvm-dev at lists.llvm.org>>, "Davide Italiano"
>             <dccitaliano at gmail.com <mailto:dccitaliano at gmail.com>>,
>             "Tim Amini Golling" <mehdi.amini at apple.com
>             <mailto:mehdi.amini at apple.com>>, "Hal Finkel"
>             <hfinkel at anl.gov <mailto:hfinkel at anl.gov>>, "Sanjoy Das"
>             <sanjoy at playingwithpointers.com
>             <mailto:sanjoy at playingwithpointers.com>>, "Pete Cooper"
>             <peter_cooper at apple.com <mailto: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 <mailto:chisophugis at gmail.com>> wrote:
>                 On Wed, Jul 13, 2016 at 1:48 AM, Sean Silva
>                 <chisophugis at gmail.com <mailto:chisophugis at gmail.com>>
>                 wrote:
>                     On Wed, Jul 13, 2016 at 12:34 AM, Chandler Carruth
>                     <chandlerc at gmail.com <mailto:chandlerc at gmail.com>>
>                     wrote:
>                         On Wed, Jul 13, 2016 at 12:25 AM Sean Silva
>                         <chisophugis at gmail.com
>                         <mailto:chisophugis at gmail.com>> wrote:
>                             On Tue, Jul 12, 2016 at 11:39 PM, Chandler
>                             Carruth <chandlerc at gmail.com
>                             <mailto:chandlerc at gmail.com>> wrote:
>                                 On Tue, Jul 12, 2016 at 11:34 PM Sean
>                                 Silva <chisophugis at gmail.com
>                                 <mailto:chisophugis at gmail.com>> wrote:
>                                     On Tue, Jul 12, 2016 at 11:32 PM,
>                                     Xinliang David Li
>                                     <davidxl at google.com
>                                     <mailto:davidxl at google.com>> wrote:
>                                         On Tue, Jul 12, 2016 at 10:57
>                                         PM, Chandler Carruth
>                                         <chandlerc at gmail.com
>                                         <mailto: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
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160807/653f9cf9/attachment-0001.html>

More information about the llvm-dev mailing list