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

[Sean Silva via llvm-dev]

On Fri, Jul 15, 2016 at 8:39 PM, Sean Silva <chisophugis at gmail.com> wrote:

> It looks like there is really no sane fix within the current
> infrastructure. I've had to essentially trigger invalidation (except in the
> PreservedAnalyses::all() case) in the function pass manager and function to
> loop adapters.
>

invalidation of *everything* I mean.

-- Sean Silva


>
> So we basically need to get the analysis manager dependency tracking fixed.
>
> Davide and I will get measurements on the resident set impact of all this
> caching (even with the overconservative invalidation for now) to see the
> impact. If there is a big rss impact then we probably want to consider that
> problem at the same time as the rewrite of the analysis manager.
>
> -- Sean Silva
>
> 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). 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
>>>
>>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20160715/b6ae49a2/attachment.html>