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

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>

We did some basic sanity checking that memory usage didn't go out of
control (it doesn't; at least with with a simple
preserves-all/preserves-none invalidation scheme and the current LTO
pipeline). Also, I did some basic sanity checking for compile time. The
simple preserves-all/preserves-none invalidation scheme seems marginally
slower, but no real conclusions (besides a simple sanity check) can be
drawn without the real analysis preservation semantics in place.

I'll start working on fixing the analysis managers. There seem to basically
be two parts (although they may need to be done simultaneously to make sure
all the pieces fit together):
- unify all the analysis managers into a single analysis manager for all
IRUnitT's (requires type-erasing the IRUnit)
- introduce the dependency tracking machinery

I think I gave a reasonable outline in the two posts above:
- the one starting with "To clarify, it seems like the current new PM is
essentially trying to solve the problem of maintaining/updating a mapping"
- the one starting with "Yeah, the mechanics of maintaining this fully
general mapping are straightforward in the abstract"

I'm happy to do a centralized writeup if anybody wants. Just let me know.

As far as changes to the code, the updates to the new PM passes should
hopefully be mechanical (despite there being many of them). However, from
what I can tell, fixing this problem will require touching most lines of
the analysis manager machinery so the diff will probably be a bit scary,
even though I think we can keep the same basic structure (i.e. a per-IRUnit
std::list holding one analysis result (at a stable address) per element,
combined with a DenseMap from (Analysis, IRUnit) to an element of the
per-IRUnit storage list (see AnalysisResultListMapT and AnalysisResultMapT
in include/llvm/IR/PassManager.h)).
The main changes to the analysis manager will be:
- type-erasing the IRUnit
- the elements of the AnalysisResultListMapT will need to keep track of any
dependents
- the analysis manager will need to update those dependencies as it is
re-entered by analyses getting results of other analyses
- the analysis manager will need to walk the dependencies to do transitive
invalidation

I think the most robust approach is for analysis dependencies to be
implicitly constructed by the analysis manager via tracking entry/exit from
get{,Cached}Result.
One alternative is for analyses to explicitly pass in their ID to getResult
to indicate the dependency, but that seems error-prone (and also verbose).
The issue is that we will need a getResult API that does not track
dependencies for use by transformation passes (since there is no dependency
to track in that case); so an innocuous copy-paste from a transform pass to
an analysis can result in a failure to track dependencies and risk of
use-after-free (we could fight this with the type system, but I think that
would get a bit verbose (I'm willing to try it though if people would
prefer))
One restriction of the implicit tracking approach is that it requires all
calls into the analysis manager to occur in the `run` method of the
analysis (so that the dependencies are implicitly tracked via re-entrance
to get{,Cached}Result); is this a reasonable restriction?


One annoying problem is that I think that the dependency links will need to
be bidirectional. To use the example analysis cache from my other post:
(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, [])

if we delete function @baz, then the dependent list  [(SomeFunctionAnalysis,
function @baz)] for `(SomeModuleAnalysis, module TheModule)` will now have
a stale pointer to function @baz. I think that in practice we can check to
see if `(SomeFunctionAnalysis, function @baz)` is in our hash table and if
it isn't then just ignore the dependency as "this dependent analysis
result
has already been freed". In the worst case (memory allocator reuses the
memory for another function) we may spuriously free an analysis result for
a different function. However it is still unsettling (and may actually be
UB in C++?).
Ideally we would track bidirectional links; that way when we remove an
analysis result we also have it remove itself from dependence lists of all
of its dependencies.

-- Sean Silva

On Fri, Jul 15, 2016 at 8:40 PM, Sean Silva <chisophugis at gmail.com>
wrote:
>
>
> 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/20160721/3d888b71/attachment-0001.html>

The more closely I look at this, the more it seems like there may be a
useful incremental step in the transition to the new PM: use the new PM
analysis machinery in the old PM. If this is possible, it will simplify the
old PM and (hopefully) allow an incremental transition to the new PM
instead of a flag day transition for the switch.

I.e., AFAICT, the new PM transition is essentially about 2 mostly
orthogonal aspects of running optimization pipelines:
1. Analysis computation and analysis result lifetime management (including
avoiding analysis recomputation)
2. Running transformation passes over their respective IRUnit's in some
order

These are conflated in the old PM. In reality, the only interaction between
them (with the new PM machinery for 1.) is a small number of places within
2. which need to call 'invalidate'.

I'm pretty sure that 2. is fairly similar in the new PM and old PM (the
main difference is that the notion of "adapters" is split out in the
new
PM). The analysis handling seems to be what makes the old PM so difficult
to understand (e.g. it is the cause of the multiple inheritance in the
implementation). Trying to unify analyses and transformations (and some
questionable (in hindsight) implementation decisions) seems to be the main
"problem" with the design of the old PM AFAICT (there are other
issues, but
they are more "nice to have").

IMO it is an anti-pattern to think of analyses as "passes". There are
just
"analyses" and "transformations" and they are two separate
things. In fact,
the `run` method on analyses should probably be called `computeResult` or
something like that to avoid confusion. And the `run` method on
transformations could just as easily be called `performTransformation`.


I remember asking and getting and answer from Chandler (
http://lists.llvm.org/pipermail/llvm-commits/Week-of-Mon-20150907/299083.html)
about how to coexist the old and new PM compatibly so individual passes
would be able to work for both and we wouldn't need to have a flag day. I
wasn't able to find the discussions that Chandler cited, but I suspect that
the answer is that we didn't have enough analyses ported at that point to
consider sharing the analysis management between the old and new PM.


If this works out it may be the evolutionary path we have all been wanting
for this pass manager transition. Fingers crossed. Hopefully I'm not
overlooking some major issue.

Anyway... back to working on the analysis manager dependency tracking.

-- Sean Silva

On Thu, Jul 21, 2016 at 1:59 AM, Sean Silva <chisophugis at gmail.com>
wrote:
> We did some basic sanity checking that memory usage didn't go out of
> control (it doesn't; at least with with a simple
> preserves-all/preserves-none invalidation scheme and the current LTO
> pipeline). Also, I did some basic sanity checking for compile time. The
> simple preserves-all/preserves-none invalidation scheme seems marginally
> slower, but no real conclusions (besides a simple sanity check) can be
> drawn without the real analysis preservation semantics in place.
>
> I'll start working on fixing the analysis managers. There seem to
> basically be two parts (although they may need to be done simultaneously to
> make sure all the pieces fit together):
> - unify all the analysis managers into a single analysis manager for all
> IRUnitT's (requires type-erasing the IRUnit)
> - introduce the dependency tracking machinery
>
> I think I gave a reasonable outline in the two posts above:
> - the one starting with "To clarify, it seems like the current new PM
is
> essentially trying to solve the problem of maintaining/updating a
mapping"
> - the one starting with "Yeah, the mechanics of maintaining this fully
> general mapping are straightforward in the abstract"
>
> I'm happy to do a centralized writeup if anybody wants. Just let me
know.
>
> As far as changes to the code, the updates to the new PM passes should
> hopefully be mechanical (despite there being many of them). However, from
> what I can tell, fixing this problem will require touching most lines of
> the analysis manager machinery so the diff will probably be a bit scary,
> even though I think we can keep the same basic structure (i.e. a per-IRUnit
> std::list holding one analysis result (at a stable address) per element,
> combined with a DenseMap from (Analysis, IRUnit) to an element of the
> per-IRUnit storage list (see AnalysisResultListMapT and AnalysisResultMapT
> in include/llvm/IR/PassManager.h)).
> The main changes to the analysis manager will be:
> - type-erasing the IRUnit
> - the elements of the AnalysisResultListMapT will need to keep track of
> any dependents
> - the analysis manager will need to update those dependencies as it is
> re-entered by analyses getting results of other analyses
> - the analysis manager will need to walk the dependencies to do transitive
> invalidation
>
> I think the most robust approach is for analysis dependencies to be
> implicitly constructed by the analysis manager via tracking entry/exit from
> get{,Cached}Result.
> One alternative is for analyses to explicitly pass in their ID to
> getResult to indicate the dependency, but that seems error-prone (and also
> verbose). The issue is that we will need a getResult API that does not
> track dependencies for use by transformation passes (since there is no
> dependency to track in that case); so an innocuous copy-paste from a
> transform pass to an analysis can result in a failure to track dependencies
> and risk of use-after-free (we could fight this with the type system, but I
> think that would get a bit verbose (I'm willing to try it though if
people
> would prefer))
> One restriction of the implicit tracking approach is that it requires all
> calls into the analysis manager to occur in the `run` method of the
> analysis (so that the dependencies are implicitly tracked via re-entrance
> to get{,Cached}Result); is this a reasonable restriction?
>
>
> One annoying problem is that I think that the dependency links will need
> to be bidirectional. To use the example analysis cache from my other post:
> (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, [])
>
> if we delete function @baz, then the dependent list 
[(SomeFunctionAnalysis,
> function @baz)] for `(SomeModuleAnalysis, module TheModule)` will now
> have a stale pointer to function @baz. I think that in practice we can
> check to see if `(SomeFunctionAnalysis, function @baz)` is in our hash
> table and if it isn't then just ignore the dependency as "this
dependent
> analysis result has already been freed". In the worst case (memory
> allocator reuses the memory for another function) we may spuriously free an
> analysis result for a different function. However it is still unsettling
> (and may actually be UB in C++?).
> Ideally we would track bidirectional links; that way when we remove an
> analysis result we also have it remove itself from dependence lists of all
> of its dependencies.
>
> -- Sean Silva
>
> On Fri, Jul 15, 2016 at 8:40 PM, Sean Silva <chisophugis at
gmail.com> wrote:
>
>>
>>
>> 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/20160722/33b430ea/attachment.html>

----- Original Message -----
> 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 21, 2016 3:59:28 AM
> Subject: Re: [PM] I think that the new PM needs to learn about
> inter-analysis dependencies...
> We did some basic sanity checking that memory usage didn't go out of
> control (it doesn't; at least with with a simple
> preserves-all/preserves-none invalidation scheme and the current LTO
> pipeline). Also, I did some basic sanity checking for compile time.
> The simple preserves-all/preserves-none invalidation scheme seems
> marginally slower, but no real conclusions (besides a simple sanity
> check) can be drawn without the real analysis preservation semantics
> in place.
> I'll start working on fixing the analysis managers. There seem to
> basically be two parts (although they may need to be done
> simultaneously to make sure all the pieces fit together):
> - unify all the analysis managers into a single analysis manager for
> all IRUnitT's (requires type-erasing the IRUnit)
> - introduce the dependency tracking machinery
> I think I gave a reasonable outline in the two posts above:
> - the one starting with " To clarify, it seems like the current new
> PM is essentially trying to solve the problem of
> maintaining/updating a mapping"
> - the one starting with " Yeah, the mechanics of maintaining this
> fully general mapping are straightforward in the abstract"
> I'm happy to do a centralized writeup if anybody wants. Just let me
> know.
> As far as changes to the code, t he updates to the new PM passes
> should hopefully be mechanical (despite there being many of them).
> However, from what I can tell, fixing this problem will require
> touching most lines of the analysis manager machinery so the diff
> will probably be a bit scary, even though I think we can keep the
> same basic structure (i.e. a per-IRUnit std::list holding one
> analysis result (at a stable address) per element, combined with a
> DenseMap from (Analysis, IRUnit) to an element of the per-IRUnit
> storage list (see AnalysisResultListMapT and AnalysisResultMapT in
> include/llvm/IR/PassManager.h)).
> The main changes to the analysis manager will be:
> - type-erasing the IRUnit
> - the elements of the AnalysisResultListMapT will need to keep track
> of any dependents
> - the analysis manager will need to update those dependencies as it
> is re-entered by analyses getting results of other analyses
> - the analysis manager will need to walk the dependencies to do
> transitive invalidation
> I think the most robust approach is for analysis dependencies to be
> implicitly constructed by the analysis manager via tracking
> entry/exit from get{,Cached}Result.
> One alternative is for analyses to explicitly pass in their ID to
> getResult to indicate the dependency, but that seems error-prone
> (and also verbose). The issue is that we will need a getResult API
> that does not track dependencies for use by transformation passes
> (since there is no dependency to track in that case); so an
> innocuous copy-paste from a transform pass to an analysis can result
> in a failure to track dependencies and risk of use-after-free (we
> could fight this with the type system, but I think that would get a
> bit verbose (I'm willing to try it though if people would prefer))
> One restriction of the implicit tracking approach is that it requires
> all calls into the analysis manager to occur in the `run` method of
> the analysis (so that the dependencies are implicitly tracked via
> re-entrance to get{,Cached}Result); is this a reasonable
> restriction?
What's the potential use case for getting an analysis outside of something
in, or called by, run()?
> One annoying problem is that I think that the dependency links will
> need to be bidirectional. To use the example analysis cache from my
> other post:
> (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, [])
> if we delete function @baz, then the dependent list
> [(SomeFunctionAnalysis, function @baz)] for ` (SomeModuleAnalysis,
> module TheModule)` will now have a stale pointer to function @baz. I
> think that in practice we can check to see if `
> (SomeFunctionAnalysis, function @baz)` is in our hash table and if
> it isn't then just ignore the dependency as "this dependent
analysis
> result has already been freed". In the worst case (memory allocator
> reuses the memory for another function) we may spuriously free an
> analysis result for a different function. However it is still
> unsettling (and may actually be UB in C++?).
> Ideally we would track bidirectional links; that way when we remove
> an analysis result we also have it remove itself from dependence
> lists of all of its dependencies.
I think that bidirectional tracking is preferable. I don't see how to avoid
UB otherwise, and spuriously freeing things based on allocator address reuse
will likely lead to non-deterministic behavior (e.g. because a re-run analysis
might be more accurate than a preserved one).

Thanks again, 
Hal 
> -- Sean Silva
> On Fri, Jul 15, 2016 at 8:40 PM, Sean Silva < chisophugis at gmail.com
>
> wrote:
> > 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
> > > > 
> > > 
> > 
> 
-- 

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/20160725/79a29c82/attachment-0001.html>