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

[Sean Silva via llvm-dev]

With D21921 and a couple other pending patches, we now have the full LTO pipeline converted to the new PM. I was trying it out on test-suite and SPEC2006. Yay!

This email is about one issue that I ran into testing the pipeline on test-suite. The issue arose in the wild as an interaction between lcssa and gvn. But the issue is extremely general.

What happened is that BasicAA uses TargetLibraryInfo. If it makes a change, then LCSSA marks BasicAA as preserved (if it made no change, it would preserve all). The new PM then invalidates everything not marked as preserved by LCSSA. So it does not invalidate BasicAA but it does invalidate TargetLibraryInfo. Now BasicAA is holding dangling pointers to TargetLibraryInfo. GVN then goes to query BasicAA and things explode.

I don't think this is going to be maintainable. Essentially, it requires all passes to be aware of the transitive dependencies of every analysis they preserve and manually preserve all dependencies. And if an analysis A starts using a new analysis B, then every pass that preserves a pass that transitively depends on A must be updated or else there are use-after-free bugs. Not to mention out-of-tree passes.

Perhaps the worst part is that without some sort of transitive preservation (or the opposite, transitive invalidation (with the transitivity in the opposite direction)) these sorts of bugs are a dynamic property of both the pass pipeline and the code being run on. For example, the reproducer I reduced for this particular bug involved a situation where:

1. A pass had to preserve BasicAA

2. lcssa would make a change and thus only preserve a subset of passes (if it made no changes it would have preserved all)

2. then LICM and MergedLoadStoreMotion had to run and make no changes (and hence preserve all).

3. then GVN had to run and query BasicAA

(presumably LICM or MergedLoadStoreMotion didn't make a query to BasicAA, or that query ended up not accessing the dangling TargetLibraryInfo).

How should we solve this? I see two potential solutions:

1. Analyses must somehow list the analyses they depend on (either by overriding "invalidate" to make sure that they invalidate them, or something "declarative" that would allow the AnalysisManager to walk the transitive dependencies).

2. The AnalysisManager must do a somewhat complicated dance to track when analyses call back into it in order to get other analyses.

Any other ideas? Any thoughts about how best to fix this?

For those interested, a reduced test case is

/home/sean/pg/release-asan/bin/opt -debug-pass-manager '-passes=require<aa>,invalidate<targetlibinfo>,gvn' -aa-pipeline=basic-aa $1 -disable-output

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

target triple = "x86_64-unknown-linux-gnu"

declare void @foo(i32)

define void @sendMTFValues(i32 *%arg) {

entry:

  call void @foo(i32 0)

  %0 = load i32, i32* %arg

  call void @foo(i32 %0)

  ret void

}

This was reduced out of 401.bzip2, but I saw many other failures in the test-suite due to this issue (for some reason they seem to manifest as the "!Scanned" assertion in AssumptionCache::scanFunction or a ValueHandle issue in AssumptionCache (nondeterministically)).

-- Sean Silva

[Hal Finkel via llvm-dev]

From: "Sean Silva" <chiso...@gmail.com>
To: "llvm-dev" <llvm...@lists.llvm.org>
Cc: "Chandler Carruth" <chan...@gmail.com>, "Davide Italiano" <dccit...@gmail.com>, "David Li" <dav...@google.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>
Sent: Tuesday, July 12, 2016 8:15:22 PM
Subject: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

With D21921 and a couple other pending patches, we now have the full LTO pipeline converted to the new PM. I was trying it out on test-suite and SPEC2006. Yay!

Nice :-)

This email is about one issue that I ran into testing the pipeline on test-suite. The issue arose in the wild as an interaction between lcssa and gvn. But the issue is extremely general.

What happened is that BasicAA uses TargetLibraryInfo. If it makes a change, then LCSSA marks BasicAA as preserved (if it made no change, it would preserve all). The new PM then invalidates everything not marked as preserved by LCSSA. So it does not invalidate BasicAA but it does invalidate TargetLibraryInfo. Now BasicAA is holding dangling pointers to TargetLibraryInfo. GVN then goes to query BasicAA and things explode.

I don't think this is going to be maintainable. Essentially, it requires all passes to be aware of the transitive dependencies of every analysis they preserve and manually preserve all dependencies. And if an analysis A starts using a new analysis B, then every pass that preserves a pass that transitively depends on A must be updated or else there are use-after-free bugs. Not to mention out-of-tree passes.

Perhaps the worst part is that without some sort of transitive preservation (or the opposite, transitive invalidation (with the transitivity in the opposite direction)) these sorts of bugs are a dynamic property of both the pass pipeline and the code being run on. For example, the reproducer I reduced for this particular bug involved a situation where:

1. A pass had to preserve BasicAA

2. lcssa would make a change and thus only preserve a subset of passes (if it made no changes it would have preserved all)

2. then LICM and MergedLoadStoreMotion had to run and make no changes (and hence preserve all).

3. then GVN had to run and query BasicAA

(presumably LICM or MergedLoadStoreMotion didn't make a query to BasicAA, or that query ended up not accessing the dangling TargetLibraryInfo).

How should we solve this? I see two potential solutions:

1. Analyses must somehow list the analyses they depend on (either by overriding "invalidate" to make sure that they invalidate them, or something "declarative" that would allow the AnalysisManager to walk the transitive dependencies).

2. The AnalysisManager must do a somewhat complicated dance to track when analyses call back into it in order to get other analyses.

Any other ideas? Any thoughts about how best to fix this?

I think that (2) is the right answer, but I'm not sure that the dance needs to be all that complicated. Each analysis can contain a list (small vector) of other analysis that depend on it, and the interface to get an analysis can take a pointer to add to this list. When an analysis is invalidated, the manager can queue the invalidation of the others in the list.

Thanks again,
Hal

For those interested, a reduced test case is

/home/sean/pg/release-asan/bin/opt -debug-pass-manager '-passes=require<aa>,invalidate<targetlibinfo>,gvn' -aa-pipeline=basic-aa $1 -disable-output

target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"

target triple = "x86_64-unknown-linux-gnu"

declare void @foo(i32)

define void @sendMTFValues(i32 *%arg) {

entry:

  call void @foo(i32 0)

  %0 = load i32, i32* %arg

  call void @foo(i32 %0)

  ret void

}

This was reduced out of 401.bzip2, but I saw many other failures in the test-suite due to this issue (for some reason they seem to manifest as the "!Scanned" assertion in AssumptionCache::scanFunction or a ValueHandle issue in AssumptionCache (nondeterministically)).

-- Sean Silva

--

Hal Finkel
Assistant Computational Scientist
Leadership Computing Facility
Argonne National Laboratory

[Chandler Carruth via llvm-dev]

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.

Some ideas about mitigating and fixing it below.

On Tue, Jul 12, 2016 at 6:15 PM Sean Silva <chiso...@gmail.com> wrote:

How should we solve this? I see two potential solutions:

1. Analyses must somehow list the analyses they depend on (either by overriding "invalidate" to make sure that they invalidate them, or something "declarative" that would allow the AnalysisManager to walk the transitive dependencies).

I think this is the right approach. I would personally start by overriding the invalidate callback everywhere that it is necessary, and see how bad that becomes.

If it becomes common and burdensome, then we can change the way invalidation works such that the analysis manager is aware of the preserved analysis set in more detail, and have it build up the necessary data structures to know in-advance whether it must make an explicit invalidate call.

However, I suspect this may not be *too* bad for two reasons:

a) As I mentioned above, I'm hoping there aren't *too* many handles between different analyses. But I've not done a careful examination, so we can check this.

b) For many analyses that might trigger this, I think we have a simpler option. If the analysis is *immutable* for any reason -- that is, it overrides its invalidate routine to always return "false" the way TargetLibraryInfo should (although I'm not sure it does currently), we shouldn't need to do this as it shouldn't be getting cleared out. Does this make sense? Do others see anything I'm missing with that approach?

2. The AnalysisManager must do a somewhat complicated dance to track when analyses call back into it in order to get other analyses.

I would really rather avoid this, as currently the analysis manager's logic here is very simple, and in many cases we only need the analyses to *compute* our result, not to embed it. I'm tihnking of stuff like Dominators is used to build LoopInfo, but there isn't a stale handle there.

There is another aspect of course in that if something is preserving LoopInfo, it really should be preserving Dominators too...

[Sean Silva via llvm-dev]

On Tue, Jul 12, 2016 at 9:00 PM, Hal Finkel <hfi...@anl.gov> wrote:

---

From: "Sean Silva" <chiso...@gmail.com>
To: "llvm-dev" <llvm...@lists.llvm.org>
Cc: "Chandler Carruth" <chan...@gmail.com>, "Davide Italiano" <dccit...@gmail.com>, "David Li" <dav...@google.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>
Sent: Tuesday, July 12, 2016 8:15:22 PM
Subject: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

With D21921 and a couple other pending patches, we now have the full LTO pipeline converted to the new PM. I was trying it out on test-suite and SPEC2006. Yay!

Nice :-)

This email is about one issue that I ran into testing the pipeline on test-suite. The issue arose in the wild as an interaction between lcssa and gvn. But the issue is extremely general.

What happened is that BasicAA uses TargetLibraryInfo. If it makes a change, then LCSSA marks BasicAA as preserved (if it made no change, it would preserve all). The new PM then invalidates everything not marked as preserved by LCSSA. So it does not invalidate BasicAA but it does invalidate TargetLibraryInfo. Now BasicAA is holding dangling pointers to TargetLibraryInfo. GVN then goes to query BasicAA and things explode.

I don't think this is going to be maintainable. Essentially, it requires all passes to be aware of the transitive dependencies of every analysis they preserve and manually preserve all dependencies. And if an analysis A starts using a new analysis B, then every pass that preserves a pass that transitively depends on A must be updated or else there are use-after-free bugs. Not to mention out-of-tree passes.

Perhaps the worst part is that without some sort of transitive preservation (or the opposite, transitive invalidation (with the transitivity in the opposite direction)) these sorts of bugs are a dynamic property of both the pass pipeline and the code being run on. For example, the reproducer I reduced for this particular bug involved a situation where:

1. A pass had to preserve BasicAA

2. lcssa would make a change and thus only preserve a subset of passes (if it made no changes it would have preserved all)

2. then LICM and MergedLoadStoreMotion had to run and make no changes (and hence preserve all).

3. then GVN had to run and query BasicAA

(presumably LICM or MergedLoadStoreMotion didn't make a query to BasicAA, or that query ended up not accessing the dangling TargetLibraryInfo).

How should we solve this? I see two potential solutions:

1. Analyses must somehow list the analyses they depend on (either by overriding "invalidate" to make sure that they invalidate them, or something "declarative" that would allow the AnalysisManager to walk the transitive dependencies).

2. The AnalysisManager must do a somewhat complicated dance to track when analyses call back into it in order to get other analyses.

Any other ideas? Any thoughts about how best to fix this?

I think that (2) is the right answer, but I'm not sure that the dance needs to be all that complicated. Each analysis can contain a list (small vector) of other analysis that depend on it, and the interface to get an analysis can take a pointer to add to this list. When an analysis is invalidated, the manager can queue the invalidation of the others in the list.

At least with the current arrangement, there is not just one AnalysisManager, but rather one per IRUnitT (with the <X>AnalysisManager<Y>Proxy analyses to go between them). So a pointer to the analysis is not enough; you also need a pointer to the AnalysisManager that is caching the result of that analysis. Since the invalidation method is actually typed to take the IRUnitT, you now need a way to store a reference to the other analysis manager in a type-erased way (since e.g. a function analysis can depend on a module analysis or vice versa).

It's sort of hairy and potentially requires quite a bit of storage (relative to the other PM data structures). E.g. a module analysis that queries various function analyses on each function will create O(NumFunctionPassesUsed * NumFunctionsInModule) back pointers to itself. Also, what happens if the module analysis is invalidated? Do we need to store even more pointers from the module analysis back to the function analyses so that it can "unregister" itself as a dependency?

Having a single AnalysisManager that stores analyses for all the different IRUnitT's might somewhat simplify this, but it would still be pretty complicated I think.

-- Sean Silva

[Chandler Carruth via llvm-dev]

On Tue, Jul 12, 2016 at 11:00 PM Sean Silva <chiso...@gmail.com> wrote:

On Tue, Jul 12, 2016 at 9:00 PM, Hal Finkel <hfi...@anl.gov> wrote:

I think that (2) is the right answer, but I'm not sure that the dance needs to be all that complicated. Each analysis can contain a list (small vector) of other analysis that depend on it, and the interface to get an analysis can take a pointer to add to this list. When an analysis is invalidated, the manager can queue the invalidation of the others in the list.

At least with the current arrangement, there is not just one AnalysisManager, but rather one per IRUnitT (with the <X>AnalysisManager<Y>Proxy analyses to go between them). So a pointer to the analysis is not enough; you also need a pointer to the AnalysisManager that is caching the result of that analysis. Since the invalidation method is actually typed to take the IRUnitT, you now need a way to store a reference to the other analysis manager in a type-erased way (since e.g. a function analysis can depend on a module analysis or vice versa).

It's sort of hairy and potentially requires quite a bit of storage (relative to the other PM data structures). E.g. a module analysis that queries various function analyses on each function will create O(NumFunctionPassesUsed * NumFunctionsInModule) back pointers to itself. Also, what happens if the module analysis is invalidated? Do we need to store even more pointers from the module analysis back to the function analyses so that it can "unregister" itself as a dependency?

Having a single AnalysisManager that stores analyses for all the different IRUnitT's might somewhat simplify this, but it would still be pretty complicated I think.

Yea, I largely agree. I'd try out overriding the invalidate method and triggering on the necessary set first, and see how that goes before we go down this road.

[Xinliang David Li via llvm-dev]

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chan...@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.

David

[Sean Silva via llvm-dev]

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

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chan...@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.

-- Sean Silva

[Chandler Carruth via llvm-dev]

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

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

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chan...@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.

And even then it isn't clear how onerous explicitly managing this in invalidate overrides will be.

[Sean Silva via llvm-dev]

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

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

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

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chan...@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%)

Since I like to visualize things, here is a quick graph of the dependencies between analyses which hold pointers to each other.

Edge A -> B indicates "A can/does hold a pointer to B".

dot file: http://reviews.llvm.org/P6603

rendering: http://reviews.llvm.org/F2161058

(I've been a bit loose with terminology here. A lot of the times that I say "analysis" I mean "the analysis' result object" or I use the name of the analysis interchangeably with the analysis result object)

-- Sean Silva

[Sean Silva via llvm-dev]

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chan...@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.

Some ideas about mitigating and fixing it below.

On Tue, Jul 12, 2016 at 6:15 PM Sean Silva <chiso...@gmail.com> wrote:

How should we solve this? I see two potential solutions:

1. Analyses must somehow list the analyses they depend on (either by overriding "invalidate" to make sure that they invalidate them, or something "declarative" that would allow the AnalysisManager to walk the transitive dependencies).

I think this is the right approach. I would personally start by overriding the invalidate callback everywhere that it is necessary, and see how bad that becomes.

If it becomes common and burdensome, then we can change the way invalidation works such that the analysis manager is aware of the preserved analysis set in more detail, and have it build up the necessary data structures to know in-advance whether it must make an explicit invalidate call.

However, I suspect this may not be *too* bad for two reasons:

a) As I mentioned above, I'm hoping there aren't *too* many handles between different analyses. But I've not done a careful examination, so we can check this.

I've replied to one of the posts downthread with some info about this.

 

b) For many analyses that might trigger this, I think we have a simpler option. If the analysis is *immutable* for any reason -- that is, it overrides its invalidate routine to always return "false" the way TargetLibraryInfo should (although I'm not sure it does currently),

TargetLibraryAnalysis has `run` overloaded for both Module and Function, but TargetLibraryInfo only has the "return false" invalidate override for Module. Probably just an oversight.

we shouldn't need to do this as it shouldn't be getting cleared out. Does this make sense? Do others see anything I'm missing with that approach?

That makes sense, but I think this only applies to a relatively small subset of analyses based on my run-through of PassRegistry.def. TargetLibraryAnalysis and TargetIRAnalysis I think are the only ones.

-- Sean Silva

[Chandler Carruth via llvm-dev]

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...

[Hal Finkel via llvm-dev]

Interesting. I'm not sure this is the right metric, however. There are lots of analyses that hold pointers to other analyses but don't need to. The analysis handle itself can be reacquired lazily if we care to do so. What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

FWIW, I still think this is common enough to design a solution that makes it easy to get this right.

 -Hal

Since I like to visualize things, here is a quick graph of the dependencies between analyses which hold pointers to each other.

Edge A -> B indicates "A can/does hold a pointer to B".

dot file: http://reviews.llvm.org/P6603

rendering: http://reviews.llvm.org/F2161058

(I've been a bit loose with terminology here. A lot of the times that I say "analysis" I mean "the analysis' result object" or I use the name of the analysis interchangeably with the analysis result object)

-- Sean Silva

 

And even then it isn't clear how onerous explicitly managing this in invalidate overrides will be.

 

-- Sean Silva

 

David

 

Some ideas about mitigating and fixing it below.

On Tue, Jul 12, 2016 at 6:15 PM Sean Silva <chiso...@gmail.com> wrote:

How should we solve this? I see two potential solutions:

1. Analyses must somehow list the analyses they depend on (either by overriding "invalidate" to make sure that they invalidate them, or something "declarative" that would allow the AnalysisManager to walk the transitive dependencies).

I think this is the right approach. I would personally start by overriding the invalidate callback everywhere that it is necessary, and see how bad that becomes.

If it becomes common and burdensome, then we can change the way invalidation works such that the analysis manager is aware of the preserved analysis set in more detail, and have it build up the necessary data structures to know in-advance whether it must make an explicit invalidate call.

However, I suspect this may not be *too* bad for two reasons:

a) As I mentioned above, I'm hoping there aren't *too* many handles between different analyses. But I've not done a careful examination, so we can check this.

b) For many analyses that might trigger this, I think we have a simpler option. If the analysis is *immutable* for any reason -- that is, it overrides its invalidate routine to always return "false" the way TargetLibraryInfo should (although I'm not sure it does currently), we shouldn't need to do this as it shouldn't be getting cleared out. Does this make sense? Do others see anything I'm missing with that approach?

2. The AnalysisManager must do a somewhat complicated dance to track when analyses call back into it in order to get other analyses.

I would really rather avoid this, as currently the analysis manager's logic here is very simple, and in many cases we only need the analyses to *compute* our result, not to embed it. I'm tihnking of stuff like Dominators is used to build LoopInfo, but there isn't a stale handle there.

There is another aspect of course in that if something is preserving LoopInfo, it really should be preserving Dominators too...

[Xinliang David Li via llvm-dev]

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

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

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chan...@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.

I meant it is harder to detect.  If 'A' soft-depends on 'B', when 'B' gets invalidated, but 'A' survives (can be used without compile time problem such as dangling pointer) -- we don't really  know if 'A' is in fact still in valid state -- as it may need to be recalculated too. 

David

[Hal Finkel via llvm-dev]

From: "Chandler Carruth" <chan...@gmail.com>
To: "Sean Silva" <chiso...@gmail.com>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>
Sent: Wednesday, July 13, 2016 2:34:35 AM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

I think that Sean laid out pretty clearly in response to my initial comment what would be required, in terms of infrastructure (type-erased invalidation objects and a registration scheme to cancel them).

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

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

Does it make sense to override the invalidate routines now and iterate from there?

I'm happy to see what this looks like.

Thanks again,
Hal

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

[Chandler Carruth via llvm-dev]

On Wed, Jul 13, 2016 at 12:39 AM Hal Finkel <hfi...@anl.gov> wrote:

Interesting. I'm not sure this is the right metric, however. There are lots of analyses that hold pointers to other analyses but don't need to. The analysis handle itself can be reacquired lazily if we care to do so. What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

Agreed. I suspect this is the dominant pattern.

FWIW, I still think this is common enough to design a solution that makes it easy to get this right.

I somewhat suspect that it would be better to pass these in along the query path rather than have results cache them. The reason is that if the user of the analysis is aware of the other analyses it depends on, it will also be aware of that cost and the reality of potentially wanting to preserve them.

I'd be interested in us spending some time trying to make this refactoring and at least understanding how hard it is before we engineer a solution that makes the analysis management more complex.

So as you seemed to agree in your other email (sorry for the heavily branching thread) perhaps we should start with the potentially error prone approach now, and see how much iteration can move toward "nothing to do" by lifting things into the query path rather than the result object.

[Hal Finkel via llvm-dev]

From: "Chandler Carruth" <chan...@gmail.com>
To: "Hal Finkel" <hfi...@anl.gov>, "Sean Silva" <chiso...@gmail.com>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>
Sent: Wednesday, July 13, 2016 3:05:26 AM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

On Wed, Jul 13, 2016 at 12:39 AM Hal Finkel <hfi...@anl.gov> wrote:

Interesting. I'm not sure this is the right metric, however. There are lots of analyses that hold pointers to other analyses but don't need to. The analysis handle itself can be reacquired lazily if we care to do so. What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

Agreed. I suspect this is the dominant pattern.

FWIW, I still think this is common enough to design a solution that makes it easy to get this right.

I somewhat suspect that it would be better to pass these in along the query path rather than have results cache them. The reason is that if the user of the analysis is aware of the other analyses it depends on, it will also be aware of that cost and the reality of potentially wanting to preserve them.

I'd be interested in us spending some time trying to make this refactoring and at least understanding how hard it is before we engineer a solution that makes the analysis management more complex.

I'm not too concerned about making analysis management more complex for this purpose; handling transitive analysis invalidation was always going to have been necessary.

So as you seemed to agree in your other email (sorry for the heavily branching thread) perhaps we should start with the potentially error prone approach now, and see how much iteration can move toward "nothing to do" by lifting things into the query path rather than the result object.

Yes, I'm happy to see where this goes. The more I think about it, the more I suspect that regardless of how easy the scheme is to use the main conceptual challenge will be remembering/knowing that it needs to be used.

 -Hal

[Chandler Carruth via llvm-dev]

On Wed, Jul 13, 2016 at 12:47 AM Xinliang David Li <dav...@google.com> wrote:

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

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

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chan...@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.

I meant it is harder to detect.  If 'A' soft-depends on 'B', when 'B' gets invalidated, but 'A' survives (can be used without compile time problem such as dangling pointer) -- we don't really  know if 'A' is in fact still in valid state -- as it may need to be recalculated too. 

The only way that 'A' is still around is if a pass *specifically* said it preserved 'A'. So I think it is reasonable to say that even if 'B' is gone, 'A' remains trustworthy here.

The issue with the "hard dependency" that Sean pointed out is that there are analyses which are trivial to update, but somewhat incidentally have references to other analyses stashed away that are no longer valid. This isn't actually a "hard dependency", in that there is no fundamental reason why this layering was enforced.

Yet another reason to prefer passing auxiliary analyses into the query path rather than modeling these as transitive invalidation is dramatically less invalidation.

[Sean Silva via llvm-dev]

Are you thinking of instead holding a pointer to the analysis manager?

 

What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like LAA holds Loop* too)

New updated rendering at http://reviews.llvm.org/F2161258 (DependenceAnalysis was missing some edges in my previous rendering and I didn't have and I've added LoopAccessAnalysis; I've updated http://reviews.llvm.org/P6603). Which other analyses vend data objects that others might hold pointers to?

-- Sean Silva

[Sean Silva via llvm-dev]

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.

-- Sean Silva

[Chandler Carruth via llvm-dev]

On Wed, Jul 13, 2016 at 1:40 AM Sean Silva <chiso...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 12:39 AM, Hal Finkel <hfi...@anl.gov> wrote:

Interesting. I'm not sure this is the right metric, however. There are lots of analyses that hold pointers to other analyses but don't need to. The analysis handle itself can be reacquired lazily if we care to do so.

Are you thinking of instead holding a pointer to the analysis manager?

I'm really concerned with using this approach as the common case. It triggers the run of the analyses at very strange points (mid-query of some other analysis) and forces us to pay the analysis manager lookup overhead on every query. For many analyses, this overhead is larger than the actual query.

There may be cases where this is the only sane way to manage things, but this should be the exception rather than the rule IMO.

 

 

What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like LAA holds Loop* too)

Note that Loop (and SCC) are somewhat special as they are IRUnitTs and might as a consequence be more reasonable to hold on to and expect definitive invalidation to occur. But I say "might". I think this will be case-by-case depending on how they're being used.

 

New updated rendering at http://reviews.llvm.org/F2161258 (DependenceAnalysis was missing some edges in my previous rendering and I didn't have and I've added LoopAccessAnalysis; I've updated http://reviews.llvm.org/P6603). Which other analyses vend data objects that others might hold pointers to?

SCEV, Loop, SCC, DomTreeNode, and Region leap immediately to mind. and 3 of those are what would be IRUnitTs (Region being the third, and its weird and likely won't be in the new PM ever).

[Sean Silva via llvm-dev]

On Wed, Jul 13, 2016 at 1:50 AM, Chandler Carruth <chan...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 1:40 AM Sean Silva <chiso...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 12:39 AM, Hal Finkel <hfi...@anl.gov> wrote:

Interesting. I'm not sure this is the right metric, however. There are lots of analyses that hold pointers to other analyses but don't need to. The analysis handle itself can be reacquired lazily if we care to do so.

Are you thinking of instead holding a pointer to the analysis manager?

I'm really concerned with using this approach as the common case. It triggers the run of the analyses at very strange points (mid-query of some other analysis) and forces us to pay the analysis manager lookup overhead on every query. For many analyses, this overhead is larger than the actual query.

Yeah, the overhead is my main concern. (also, this would be very difficult to coexist with the old PM so at least in the immediate future isn't an option)

 

There may be cases where this is the only sane way to manage things, but this should be the exception rather than the rule IMO.

 

 

What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like LAA holds Loop* too)

Note that Loop (and SCC) are somewhat special as they are IRUnitTs and might as a consequence be more reasonable to hold on to and expect definitive invalidation to occur. But I say "might". I think this will be case-by-case depending on how they're being used.

 

New updated rendering at http://reviews.llvm.org/F2161258 (DependenceAnalysis was missing some edges in my previous rendering and I didn't have and I've added LoopAccessAnalysis; I've updated http://reviews.llvm.org/P6603). Which other analyses vend data objects that others might hold pointers to?

SCEV, Loop, SCC, DomTreeNode, and Region leap immediately to mind. and 3 of those are what would be IRUnitTs (Region being the third, and its weird and likely won't be in the new PM ever).

Looking around a bit:

Looks like DomTreeNode isn't held by anything currently.

Pointers to Loop are only held by LAA as far as I can tell.

CallGraphSCC objects are only used by GlobalsAA but only for a "recalculate" step.

Region's data structures don't seem to be held by anything.

So it seems like LAA is the main offender in this regard.

-- Sean Silva

[Xinliang David Li via llvm-dev]

On Wed, Jul 13, 2016 at 1:33 AM, Chandler Carruth <chan...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 12:47 AM Xinliang David Li <dav...@google.com> wrote:

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

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

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chan...@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.

I meant it is harder to detect.  If 'A' soft-depends on 'B', when 'B' gets invalidated, but 'A' survives (can be used without compile time problem such as dangling pointer) -- we don't really  know if 'A' is in fact still in valid state -- as it may need to be recalculated too. 

The only way that 'A' is still around is if a pass *specifically* said it preserved 'A'. So I think it is reasonable to say that even if 'B' is gone, 'A' remains trustworthy here.

This can be problematic in other ways -- wrong assumption made by the pass writer, i.e. 'A' is preserved even though 'B' can be invalidated. But this is a different issue.

David

[Adam Nemet via llvm-dev]

I think one main reason that analysis passes used to do this was to work around limitations in the old PM.  Like LAA wasn’t a loop pass so as a function pass it did lazy computation for loops.  Thus it had to hold on to the input analyses to compute the per-loop analysis result.  I am hoping that this use case will go away with the new PM.  There may be a way to refactor LoopAccessInfo to reflect this, hopefully the old PM won’t stand in the way.

SCEV might pose another problem though.  Caching is per Value there, so that is probably a genuine use case when we need to keep input analysis alive until the main pass is alive.

A few more other thoughts on this topic.

Can we perhaps have a special reference type for passes to reference other passes, something like a CallbackVH for passes and them somehow disallow holding onto passes via a pointer?

There could also be a way to verify correctness.  We could force-invalidate all passes that the pass does not declare to depend on, then hopefully bugs will unconditionally present themselves independent of the pipeline.

Adam

-- Sean Silva

_______________________________________________
LLVM Developers mailing list
llvm...@lists.llvm.org
http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev

[Xinliang David Li via llvm-dev]

On Wed, Jul 13, 2016 at 10:07 AM, Adam Nemet <ane...@apple.com> wrote:

On Jul 13, 2016, at 2:02 AM, Sean Silva via llvm-dev <llvm...@lists.llvm.org> wrote:

On Wed, Jul 13, 2016 at 1:50 AM, Chandler Carruth <chan...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 1:40 AM Sean Silva <chiso...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 12:39 AM, Hal Finkel <hfi...@anl.gov> wrote:

Interesting. I'm not sure this is the right metric, however. There are lots of analyses that hold pointers to other analyses but don't need to. The analysis handle itself can be reacquired lazily if we care to do so.

Are you thinking of instead holding a pointer to the analysis manager?

I'm really concerned with using this approach as the common case. It triggers the run of the analyses at very strange points (mid-query of some other analysis) and forces us to pay the analysis manager lookup overhead on every query. For many analyses, this overhead is larger than the actual query.

Yeah, the overhead is my main concern. (also, this would be very difficult to coexist with the old PM so at least in the immediate future isn't an option)

 

There may be cases where this is the only sane way to manage things, but this should be the exception rather than the rule IMO.

 

 

What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like LAA holds Loop* too)

Note that Loop (and SCC) are somewhat special as they are IRUnitTs and might as a consequence be more reasonable to hold on to and expect definitive invalidation to occur. But I say "might". I think this will be case-by-case depending on how they're being used.

 

New updated rendering at http://reviews.llvm.org/F2161258 (DependenceAnalysis was missing some edges in my previous rendering and I didn't have and I've added LoopAccessAnalysis; I've updated http://reviews.llvm.org/P6603). Which other analyses vend data objects that others might hold pointers to?

SCEV, Loop, SCC, DomTreeNode, and Region leap immediately to mind. and 3 of those are what would be IRUnitTs (Region being the third, and its weird and likely won't be in the new PM ever).

Looking around a bit:

Looks like DomTreeNode isn't held by anything currently.

Pointers to Loop are only held by LAA as far as I can tell.

CallGraphSCC objects are only used by GlobalsAA but only for a "recalculate" step.

Region's data structures don't seem to be held by anything.

So it seems like LAA is the main offender in this regard.

I think one main reason that analysis passes used to do this was to work around limitations in the old PM.  Like LAA wasn’t a loop pass so as a function pass it did lazy computation for loops.  Thus it had to hold on to the input analyses to compute the per-loop analysis result.  I am hoping that this use case will go away with the new PM.  There may be a way to refactor LoopAccessInfo to reflect this, hopefully the old PM won’t stand in the way.

IIRC, This was handled in the original patch -- an AnalysisManager base class was introduced to abstract away access old PM and new PM for accessing analyses.

David

[Adam Nemet via llvm-dev]

On Jul 13, 2016, at 10:07 AM, Adam Nemet via llvm-dev <llvm...@lists.llvm.org> wrote:

On Jul 13, 2016, at 2:02 AM, Sean Silva via llvm-dev <llvm...@lists.llvm.org> wrote:

On Wed, Jul 13, 2016 at 1:50 AM, Chandler Carruth <chan...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 1:40 AM Sean Silva <chiso...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 12:39 AM, Hal Finkel <hfi...@anl.gov> wrote:

Interesting. I'm not sure this is the right metric, however. There are lots of analyses that hold pointers to other analyses but don't need to. The analysis handle itself can be reacquired lazily if we care to do so.

Are you thinking of instead holding a pointer to the analysis manager?

I'm really concerned with using this approach as the common case. It triggers the run of the analyses at very strange points (mid-query of some other analysis) and forces us to pay the analysis manager lookup overhead on every query. For many analyses, this overhead is larger than the actual query.

Yeah, the overhead is my main concern. (also, this would be very difficult to coexist with the old PM so at least in the immediate future isn't an option)

 

There may be cases where this is the only sane way to manage things, but this should be the exception rather than the rule IMO.

 

 

What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like LAA holds Loop* too)

Note that Loop (and SCC) are somewhat special as they are IRUnitTs and might as a consequence be more reasonable to hold on to and expect definitive invalidation to occur. But I say "might". I think this will be case-by-case depending on how they're being used.

 

New updated rendering at http://reviews.llvm.org/F2161258 (DependenceAnalysis was missing some edges in my previous rendering and I didn't have and I've added LoopAccessAnalysis; I've updated http://reviews.llvm.org/P6603). Which other analyses vend data objects that others might hold pointers to?

SCEV, Loop, SCC, DomTreeNode, and Region leap immediately to mind. and 3 of those are what would be IRUnitTs (Region being the third, and its weird and likely won't be in the new PM ever).

Looking around a bit:

Looks like DomTreeNode isn't held by anything currently.

Pointers to Loop are only held by LAA as far as I can tell.

CallGraphSCC objects are only used by GlobalsAA but only for a "recalculate" step.

Region's data structures don't seem to be held by anything.

So it seems like LAA is the main offender in this regard.

I think one main reason that analysis passes used to do this was to work around limitations in the old PM.  Like LAA wasn’t a loop pass so as a function pass it did lazy computation for loops.  Thus it had to hold on to the input analyses to compute the per-loop analysis result.  I am hoping that this use case will go away with the new PM.  There may be a way to refactor LoopAccessInfo to reflect this, hopefully the old PM won’t stand in the way.

r275322 removes the reference to AA from the analysis result since it’s only used at ctor time.  I think that we should be able to remove everything except for SCEV and Loop.

Adam

[Adam Nemet via llvm-dev]

On Jul 13, 2016, at 2:51 PM, Adam Nemet <ane...@apple.com> wrote:

On Jul 13, 2016, at 10:07 AM, Adam Nemet via llvm-dev <llvm...@lists.llvm.org> wrote:

On Jul 13, 2016, at 2:02 AM, Sean Silva via llvm-dev <llvm...@lists.llvm.org> wrote:

On Wed, Jul 13, 2016 at 1:50 AM, Chandler Carruth <chan...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 1:40 AM Sean Silva <chiso...@gmail.com> wrote:

On Wed, Jul 13, 2016 at 12:39 AM, Hal Finkel <hfi...@anl.gov> wrote:

Interesting. I'm not sure this is the right metric, however. There are lots of analyses that hold pointers to other analyses but don't need to. The analysis handle itself can be reacquired lazily if we care to do so.

Are you thinking of instead holding a pointer to the analysis manager?

I'm really concerned with using this approach as the common case. It triggers the run of the analyses at very strange points (mid-query of some other analysis) and forces us to pay the analysis manager lookup overhead on every query. For many analyses, this overhead is larger than the actual query.

Yeah, the overhead is my main concern. (also, this would be very difficult to coexist with the old PM so at least in the immediate future isn't an option)

 

There may be cases where this is the only sane way to manage things, but this should be the exception rather than the rule IMO.

 

 

What's truly problematic is holding pointers into another analysis's data structures. To be concrete, holding a pointer to ScalarEvolution is not a fundamental problem because we could make the analysis reacquire the pointer at the start of every query. Holding SCEV* is the problem.

Looks like SCEV* at least is held only by LoopAccessInfo. (Looks like LAA holds Loop* too)

Note that Loop (and SCC) are somewhat special as they are IRUnitTs and might as a consequence be more reasonable to hold on to and expect definitive invalidation to occur. But I say "might". I think this will be case-by-case depending on how they're being used.

 

New updated rendering at http://reviews.llvm.org/F2161258 (DependenceAnalysis was missing some edges in my previous rendering and I didn't have and I've added LoopAccessAnalysis; I've updated http://reviews.llvm.org/P6603). Which other analyses vend data objects that others might hold pointers to?

SCEV, Loop, SCC, DomTreeNode, and Region leap immediately to mind. and 3 of those are what would be IRUnitTs (Region being the third, and its weird and likely won't be in the new PM ever).

Looking around a bit:

Looks like DomTreeNode isn't held by anything currently.

Pointers to Loop are only held by LAA as far as I can tell.

CallGraphSCC objects are only used by GlobalsAA but only for a "recalculate" step.

Region's data structures don't seem to be held by anything.

So it seems like LAA is the main offender in this regard.

I think one main reason that analysis passes used to do this was to work around limitations in the old PM.  Like LAA wasn’t a loop pass so as a function pass it did lazy computation for loops.  Thus it had to hold on to the input analyses to compute the per-loop analysis result.  I am hoping that this use case will go away with the new PM.  There may be a way to refactor LoopAccessInfo to reflect this, hopefully the old PM won’t stand in the way.

r275322 removes the reference to AA from the analysis result since it’s only used at ctor time.  I think that we should be able to remove everything except for SCEV and Loop.

And the series ending at r275335 takes us there.

Adam

[Sean Silva via llvm-dev]

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

[Sean Silva via llvm-dev]

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

[Hal Finkel via llvm-dev]

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.

Thanks again,
Hal

---

From: "Sean Silva" <chiso...@gmail.com>
To: "Chandler Carruth" <chan...@gmail.com>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@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...

[Mehdi Amini via llvm-dev]

Sent from my iPhone

On Jul 14, 2016, at 7:21 PM, Hal Finkel <hfi...@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.

I share the same feeling.

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.

Because of the hard vs soft dependency, I'm not sure if this has to be implicit or if it'd be better made explicit though, i.e. with a separate API call.

-- 

Mehdi

[Hal Finkel via llvm-dev]

From: "Mehdi Amini" <mehdi...@apple.com>
To: "Hal Finkel" <hfi...@anl.gov>
Cc: "Sean Silva" <chiso...@gmail.com>, "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>, "Chandler Carruth" <chan...@gmail.com>
Sent: Thursday, July 14, 2016 9:37:38 PM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

Sent from my iPhone

On Jul 14, 2016, at 7:21 PM, Hal Finkel <hfi...@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.

I share the same feeling.

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.

Because of the hard vs soft dependency, I'm not sure if this has to be implicit or if it'd be better made explicit though, i.e. with a separate API call.

Can you explain? You still need to invalidate for soft dependencies.

 -Hal

[Sean Silva via llvm-dev]

On Thu, Jul 14, 2016 at 7:21 PM, Hal Finkel <hfi...@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

[Hal Finkel via llvm-dev]

From: "Sean Silva" <chiso...@gmail.com>
To: "Hal Finkel" <hfi...@anl.gov>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>, "Chandler Carruth" <chan...@gmail.com>
Sent: Thursday, July 14, 2016 9:48:44 PM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

On Thu, Jul 14, 2016 at 7:21 PM, Hal Finkel <hfi...@anl.gov> wrote:

Hi Sean,

Thanks for writing all of this up. I'll go back to my previous position: we need a general dependency graph built as the analysis cache is used. It should have the following properties:

 1. When we call getResult or getCachedResult on an analysis manager, we record a dependency of the current pass on the returned result.
 2. This dependency needs to be stored such that it can be used to invalidate the current result when the returned result is invalidates and so that the dependency can be deleted when the current result is invalidated.

As I understand the problem, this is a fully-general solution. I see no reason not to have a fully-general solution.

Yeah, the mechanics of maintaining this fully general mapping are straightforward in the abstract (once we have a single analysis manager for all IRUnitT's). Essentially, the analysis manager maintains a stack of (Analysis, IRUnit) that it is currently computing and pushes/pops the stack as it (re-)enters/exits get{,Cached}Result. If the stack is not empty (suppose top of stack is `(AnalysisFoo, IRUnitBar)`), then when we go to push `(AnalysisBaz, IRUnitQux)` we record a dependency that the result cached on key `(AnalysisBaz, IRUnitQux)` must be invalidated if the result cached on key `(AnalysisFoo, IRUnitBar)` is invalidated.

The difficult part is what guarantees we provide about things being stale or not and how we invalidate when IRUnit's are deleted or created.

For example, suppose a function pass DCE's a call which causes an SCC Foo of 3 functions to no longer be an SCC. When/how do analyses cached on Foo get invalidated? And is it valid to query them? One of the expected use cases (I'm told) for CGSCC passes is to propagate function-attribute like things, so these are being potentially queried by that same function pass.

I don't understand this example. Just because the function removes the call edge, theoretically breaking the SCC, will that automatically trigger an update of the CG data structure? I'd think that the CG itself won't be updated until the function pass is done (during which time the old CG will still be a valid over-approximation).

 -Hal

[Chandler Carruth via llvm-dev]

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.

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.

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.

[Sean Silva via llvm-dev]

On Thu, Jul 14, 2016 at 7:58 PM, Hal Finkel <hfi...@anl.gov> wrote:

---

From: "Sean Silva" <chiso...@gmail.com>
To: "Hal Finkel" <hfi...@anl.gov>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>, "Chandler Carruth" <chan...@gmail.com>
Sent: Thursday, July 14, 2016 9:48:44 PM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

On Thu, Jul 14, 2016 at 7:21 PM, Hal Finkel <hfi...@anl.gov> wrote:

Hi Sean,

Thanks for writing all of this up. I'll go back to my previous position: we need a general dependency graph built as the analysis cache is used. It should have the following properties:

 1. When we call getResult or getCachedResult on an analysis manager, we record a dependency of the current pass on the returned result.
 2. This dependency needs to be stored such that it can be used to invalidate the current result when the returned result is invalidates and so that the dependency can be deleted when the current result is invalidated.

As I understand the problem, this is a fully-general solution. I see no reason not to have a fully-general solution.

Yeah, the mechanics of maintaining this fully general mapping are straightforward in the abstract (once we have a single analysis manager for all IRUnitT's). Essentially, the analysis manager maintains a stack of (Analysis, IRUnit) that it is currently computing and pushes/pops the stack as it (re-)enters/exits get{,Cached}Result. If the stack is not empty (suppose top of stack is `(AnalysisFoo, IRUnitBar)`), then when we go to push `(AnalysisBaz, IRUnitQux)` we record a dependency that the result cached on key `(AnalysisBaz, IRUnitQux)` must be invalidated if the result cached on key `(AnalysisFoo, IRUnitBar)` is invalidated.

The difficult part is what guarantees we provide about things being stale or not and how we invalidate when IRUnit's are deleted or created.

For example, suppose a function pass DCE's a call which causes an SCC Foo of 3 functions to no longer be an SCC. When/how do analyses cached on Foo get invalidated? And is it valid to query them? One of the expected use cases (I'm told) for CGSCC passes is to propagate function-attribute like things, so these are being potentially queried by that same function pass.

I don't understand this example. Just because the function removes the call edge, theoretically breaking the SCC, will that automatically trigger an update of the CG data structure? I'd think that the CG itself won't be updated until the function pass is done (during which time the old CG will still be a valid over-approximation).

This is the kind of restriction I was talking about. I.e. the information computed by a CGSCC analysis must be such that queries to it remain a conservative approximation in the face of some specified set of transformations to functions in the SCC (such as deleting calls). Presumably function passes would then be required to adhere to these limitations (or else do invalidation manually).

-- Sean Silva

[Hal Finkel via llvm-dev]

---

From: "Sean Silva" <chiso...@gmail.com>
To: "Hal Finkel" <hfi...@anl.gov>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>, "Chandler Carruth" <chan...@gmail.com>
Sent: Thursday, July 14, 2016 10:04:37 PM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

On Thu, Jul 14, 2016 at 7:58 PM, Hal Finkel <hfi...@anl.gov> wrote:

---

From: "Sean Silva" <chiso...@gmail.com>
To: "Hal Finkel" <hfi...@anl.gov>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>, "Chandler Carruth" <chan...@gmail.com>
Sent: Thursday, July 14, 2016 9:48:44 PM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

On Thu, Jul 14, 2016 at 7:21 PM, Hal Finkel <hfi...@anl.gov> wrote:

Hi Sean,

Thanks for writing all of this up. I'll go back to my previous position: we need a general dependency graph built as the analysis cache is used. It should have the following properties:

 1. When we call getResult or getCachedResult on an analysis manager, we record a dependency of the current pass on the returned result.
 2. This dependency needs to be stored such that it can be used to invalidate the current result when the returned result is invalidates and so that the dependency can be deleted when the current result is invalidated.

As I understand the problem, this is a fully-general solution. I see no reason not to have a fully-general solution.

Yeah, the mechanics of maintaining this fully general mapping are straightforward in the abstract (once we have a single analysis manager for all IRUnitT's). Essentially, the analysis manager maintains a stack of (Analysis, IRUnit) that it is currently computing and pushes/pops the stack as it (re-)enters/exits get{,Cached}Result. If the stack is not empty (suppose top of stack is `(AnalysisFoo, IRUnitBar)`), then when we go to push `(AnalysisBaz, IRUnitQux)` we record a dependency that the result cached on key `(AnalysisBaz, IRUnitQux)` must be invalidated if the result cached on key `(AnalysisFoo, IRUnitBar)` is invalidated.

The difficult part is what guarantees we provide about things being stale or not and how we invalidate when IRUnit's are deleted or created.

For example, suppose a function pass DCE's a call which causes an SCC Foo of 3 functions to no longer be an SCC. When/how do analyses cached on Foo get invalidated? And is it valid to query them? One of the expected use cases (I'm told) for CGSCC passes is to propagate function-attribute like things, so these are being potentially queried by that same function pass.

I don't understand this example. Just because the function removes the call edge, theoretically breaking the SCC, will that automatically trigger an update of the CG data structure? I'd think that the CG itself won't be updated until the function pass is done (during which time the old CG will still be a valid over-approximation).

This is the kind of restriction I was talking about. I.e. the information computed by a CGSCC analysis must be such that queries to it remain a conservative approximation in the face of some specified set of transformations to functions in the SCC (such as deleting calls). Presumably function passes would then be required to adhere to these limitations (or else do invalidation manually).

This sounds reasonable to me.

 -Hal

[Sean Silva via llvm-dev]

On Thu, Jul 14, 2016 at 8:04 PM, Chandler Carruth <chan...@gmail.com> 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 is not enough for basic sanity, such as being able to pass an arbitrary pass pipeline to opt and know it isn't going to have a use-after-free bug due to analysis caching problems. Also presumably this checking would only be enabled with assertions.

By itself, this leaves us in a position where assertions+ASan is needed to have basic confidence when running a pipeline. That is not a world I want to live in.

 

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.

I believe this works as intended. Unfortunately I can't really see any use of the `invalidate` callback beyond this w.r.t. the problems we are discussion in this thread (I say this because I tried to fix the issues I was running into by using it).

-- Sean Silva

[Sean Silva via llvm-dev]

On Thu, Jul 14, 2016 at 7:43 PM, Hal Finkel <hfi...@anl.gov> wrote:

---

From: "Mehdi Amini" <mehdi...@apple.com>
To: "Hal Finkel" <hfi...@anl.gov>
Cc: "Sean Silva" <chiso...@gmail.com>, "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>, "Chandler Carruth" <chan...@gmail.com>
Sent: Thursday, July 14, 2016 9:37:38 PM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

Sent from my iPhone

On Jul 14, 2016, at 7:21 PM, Hal Finkel <hfi...@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.

I share the same feeling.

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.

Because of the hard vs soft dependency, I'm not sure if this has to be implicit or if it'd be better made explicit though, i.e. with a separate API call.

Can you explain? You still need to invalidate for soft dependencies.

You don't necessarily need too. For example, a pass may manually modify LoopInfo to keep it up to date but not update DominatorTree.

On the other hand, invalidation in the case of soft dependencies is still correct, so we may decide to not worry about the hard/soft distinction unless there are real compile time savings to be gotten by adding special handling for soft dependencies.

I.e. the PreservedAnalyses set is about what is preserved, not about what is invalidated. For a PreservedAnalyses set PA, the set that needs to be invalidated is something like:

union(transitiveHardDeps(x) for x in ~PA) & ~PA

I.e. in response to Mehdi's question, the soft case can be phrased as an explicit opt-out of dependency tracking.

-- Sean Silva

[Sean Silva via llvm-dev]

On Thu, Jul 14, 2016 at 8:41 PM, Sean Silva <chiso...@gmail.com> wrote:

On Thu, Jul 14, 2016 at 7:43 PM, Hal Finkel <hfi...@anl.gov> wrote:

---

From: "Mehdi Amini" <mehdi...@apple.com>
To: "Hal Finkel" <hfi...@anl.gov>
Cc: "Sean Silva" <chiso...@gmail.com>, "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>, "Chandler Carruth" <chan...@gmail.com>
Sent: Thursday, July 14, 2016 9:37:38 PM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

Sent from my iPhone

On Jul 14, 2016, at 7:21 PM, Hal Finkel <hfi...@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.

I share the same feeling.

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.

Because of the hard vs soft dependency, I'm not sure if this has to be implicit or if it'd be better made explicit though, i.e. with a separate API call.

Can you explain? You still need to invalidate for soft dependencies.

You don't necessarily need too. For example, a pass may manually modify LoopInfo to keep it up to date but not update DominatorTree.

On the other hand, invalidation in the case of soft dependencies is still correct, so we may decide to not worry about the hard/soft distinction unless there are real compile time savings to be gotten by adding special handling for soft dependencies.

I.e. the PreservedAnalyses set is about what is preserved, not about what is invalidated. For a PreservedAnalyses set PA, the set that needs to be invalidated is something like:

union(transitiveHardDeps(x) for x in ~PA) & ~PA

The `& ~PA` is spurious here. (I think when I started writing this I was thinking in terms of transitively following soft deps too or something like that)

Now that I think about it, we will probably want (for debugging / development) some sort of debug output along the lines of "your transformation pass marked analysis Foo as preserved, but it was still invalidated because analysis Bar was not preserved".

-- Sean Silva

[Adam Nemet via llvm-dev]

On Jul 14, 2016, at 8:04 PM, Chandler Carruth via llvm-dev <llvm...@lists.llvm.org> 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 I understood soft vs hard but I am not sure I understand these categories.  Can you please elaborate?  By query, do mean an API call on the analysis result?  It seems that analysis-dependencies corresponds to soft and hard is divided between the last two?  Also is data-structure-dep a subset of query-dep?

_______________________________________________

[Sean Silva via llvm-dev]

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.

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

[Sean Silva via llvm-dev]

On Fri, Jul 15, 2016 at 8:39 PM, Sean Silva <chiso...@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

[Sean Silva via llvm-dev]

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

[Sean Silva via llvm-dev]

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

[Sean Silva via llvm-dev]

I've started looking specifically at the existing code and how it needs to be changed. It seems like the concept-based polymorphism stuff in PassManagerInternal.h actually don't need to be changed that much. AnalysisPassConcept and AnalysisResultConcept need to be changed to take a type-erased IRUnit (e.g. a void* or something). AnalysisPassModel and AnalysisResultModel (which inherit from their respective abstract base classes I mentioned above) are already templated on the IRUnitT and so they can just cast the void* back to the right type.

Adding the dependency tracking seems like it will be mostly a data structure change with some isolated "algorithmic" changes to track/invalidate dependencies.

Most of the methods that need to know the specific IRUnitT type already take the IRUnit as an argument (e.g. getResult, getCachedResult, invalidate) and so it's actually somewhat natural for the analysis manager not be templated on IRUnitT (but rather to have just those methods be templated).

Also, up until now I hadn't noticed this weird "registerPass" thing on the analysis manager (AnalysisManagerBase to be specific). Effectively, it allows analyses to hold state (this is separate from analysis *results* which of course can hold state). But the state is effectively global to the AnalysisManager (and hence the pass pipeline, and hence (essentially) the context (since you can currently only run a single pass pipeline concurrently on a single LLVMContext)). The net result is that you can specify a context-global "configuration" for each analysis type (not to be confused with the analysis *result* type!). Right now, AAManager is the only thing that uses it though (the "configuration" is the AA pipeline).

btw, I've started to keep a log for this like I do for my projects at home: https://docs.google.com/document/d/1-nrq2y_hTiZhrsJDmH8TzFjFEeApfccs6wwGyaXjSkg/edit?usp=sharing

It's fairly stream-of-consciousness. My log style is mostly append-only (I rarely edit stuff from a previous day or from too long ago on the same day; if I do I usually don't overwrite and instead insert something like "(edit: I was actually totally wrong about this, see below)"). So if you want to follow this across multiple days just go to the end and scroll up until you see something that you've already looked at. (right now there is just one day though so there is not very much).

(some interesting things to search for are "interesting", "okay", "oh", and "?"; I tend to use these a lot)

I've gone back to google docs for this log since it is easier to share on the mailing list. Unfortunately google docs does not have an explicit notion of "cell" like Mathematica does, so I've tried to just insert lots of line breaks for things where there would have just been a cell boundary in Mathematica. (I use Mathematica for my logs at home).

-- Sean Silva

[Hal Finkel via llvm-dev]

From: "Sean Silva" <chiso...@gmail.com>
To: "Chandler Carruth" <chan...@gmail.com>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@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, 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?

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

[Hal Finkel via llvm-dev]

From: "Sean Silva" <chiso...@gmail.com>
To: "Chandler Carruth" <chan...@gmail.com>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>
Sent: Friday, July 22, 2016 3:55:52 AM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

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.

This makes sense to me.

We do currently have some "in between" passes, like LCSSA, which are transformations, but are required by other passes, and transform the IR but whose preservation represents properties of the IR. The particulars of how we handle LCSSA aside (e.g. I think we should preserve it more, perhaps everywhere), how are we planning on handling this class of things?

Thanks again,
Hal

[Sean Silva via llvm-dev]

The main thing I had in mind was that if an analysis happens to stash a pointer directly to the analysis manager, then it may call into the analysis manager in the query path. For example, you would have this situation if a module analysis has a query path that wants to lazily compute a function analysis (i.e. compute the function analysis outside of the `run` call).

 

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).

Yeah, it doesn't seem onerous to maintain the bidirectional tracking (I have a design mocked up in my log). The problem actually ends up being similar to use/user tracking we have in the IR data structures (although it's different enough that there isn't really any code to share).

-- Sean Silva

[Hal Finkel via llvm-dev]

Yes, I'm pretty sure that we want to support that (a module analysis lazily getting function-level analysis results on the functions in the module). To put it another way, we definitely want a module transformation to be able to do that, and if an analysis can't, that limits our ability to properly organize/reuse code.

We might have a slightly different interface for that, however, if it can't be implicit in that case.

 -Hal

[Sean Silva via llvm-dev]

Thankfully, the solution is straightforward enough. We just need a query API that takes an explicit dependency.

As a strawman design that we may want to move to long-term, we could make the FooAnalysis's `run` method take an AnalysisManagerRef<FooAnalysis>, which wraps the raw analysis manager (all of whose methods take an explicit dependency) and automatically passes in the dependency on FooAnalysis. Analysis would be free to hold the AnalysisManagerRef and query it at any time. It also removes the need for the analysis manager to track when it is re-entered.

This is probably not worth doing until we have more experience with this analysis management stuff (e.g. actually use it in production).

-- Sean Silva

[Sean Silva via llvm-dev]

On Mon, Jul 25, 2016 at 9:27 AM, Hal Finkel <hfi...@anl.gov> wrote:

---

From: "Sean Silva" <chiso...@gmail.com>
To: "Chandler Carruth" <chan...@gmail.com>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>
Sent: Friday, July 22, 2016 3:55:52 AM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

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.

This makes sense to me.

We do currently have some "in between" passes, like LCSSA, which are transformations, but are required by other passes, and transform the IR but whose preservation represents properties of the IR. The particulars of how we handle LCSSA aside (e.g. I think we should preserve it more, perhaps everywhere), how are we planning on handling this class of things?

The new PM doesn't currently have a concept like this. As you mentioned, it is a weird cross between a transformation and an analysis: it can be "invalidated" like an analysis, but "recomputing" it actually mutates the IR like a transformation.

I'd like to preface the below with the following:

No matter how we ultimately address this requirement, my preference is that we do so in a way that applies to the old PM. This is a case where the old PM supports a richer set of functionality than the new PM. By incrementally refactoring the old PM away from its use of this extra capability and towards whatever "new" way there is to do it, we will understand better what it is that we actually need.

(and sorry for the brain dump in the rest of this post)

I have not seen any mention of a solution to this problem besides "we shouldn't do that", which is sort of a cop-out. Here is a strawman proposal:

If it isn't too expensive, one simple alternative is to have passes just make a call to a utility function to put things in LCSSA if they need it (this utility would also have to invalidate analyses).

If that ends up being expensive, we can have a dummy "indicator" analysis IRIsInLCSSAForm which, if cached, means "don't bother to call the utility function". We could maybe just use the LCSSA pass directly to do the transformation. LCSSA could have IRIsInLCSSAForm as an member typedef `IndicatorT` so it can be accessed generically. We could then support an API like:

```

FooTransformation.cpp:

PreservedAnalyses FooTransformation::run(Function &F, AnalysisManager AM) {

  // Must be called before getting analyses, as it might invalidate some.

  canonicalizeIR<LCSSA>(F, AM);

  ...
}

include/IR/Canonicalization.h:

template <typename CanonicalizationT, typename IRUnitT>

void canonicalizeIR(IRUnitT &IR, AnalysisManager &AM) {

  using IndicatorT = typename CanonicalizationT::IndicatorAnalysis;

  if (AM.getCachedResult<IndicatorT>(IR))

    return;

  CanonicalizationT C;

  PreservedAnalysis PA = C.run(IR, AM);

  AM.invalidate(IR, PA);

  (void)AM.getResult<IndicatorT>(IR);
}

```

One place that talks about this problem of "requiring a transformation" is http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf on slide 17.

One reason it provides for "we shouldn't do that" is that if you think about these things as "canonicalize the IR into a specific form", then when you have N>1 such dependencies (like some passes do on LoopSimplify and LCSSA), one must have a subset of the requirements of the other. I.e. you can't have two canonicalizations that "fight" each other. Using an explicit mutation API like the strawman above is a bit less bulletproof than scheduling based on statically known interferences between canonicalizations (e.g. CanonicalizationA may invalidate CanonicalizationB, but not the reverse, so it would automatically know to run CanonicalizationA before CanonicalizationB), but given that we have relatively few "canonicalizations" (to give them a name) that use this feature of the old PM, it may be livable (at least in the middle-end, it seems like there is just LCSSA, LoopSimplify, BreakCriticalEdges, and LowerSwitch in calls to addPreservedID/addRequiredID).

I don't find the "Causes rampant re-running of invalidated analyses" argument in that slide convincing. If a pass needs the IR in LCSSA then it needs it. There isn't much we can do about that.

One invariant I'd like to preserve in the new pass manager is that whatever pipeline is provided on the opt command line, we end up running something "valid"; so a cop-out like "if a pass needs LCSSA, you need to make sure to add LCSSA at an appropriate place before it in the pipeline" is not something I think is reasonable (way too error-prone).

Small rant:

We already are in this error-prone situation in the new PM with the need to call `getCachedResult` to access analyses from a larger IRUnitT (e.g. the situation I explained in the post-commit thread of r274712); this means that when constructing a pass pipeline to pass to opt, you need to do various things to ensure your pipeline even makes sense:

1. You need to make sure to always add the `requires<foo>` at a higher level for any pass that needs it (how do you find out what each pass needs besides grepping the source?), otherwise you get an assertion failure / report_fatal_error

2. You need to make sure that no intervening transformation at the lower level invalidates the outer analysis before getting to your pass that needs it. E.g. `module(require<foo>,function(pass-that-invalidates-foo,pass-that-requires-foo)`.

I don't see the point of this restriction. In a hypothetical future where we run over inner IRUnit's in parallel we would need some awareness to avoid races when getting analyses for outer IRUnit's. But doing that serialization dynamically as the analysis is accessed (and perhaps even centralized in the analysis manager and pass management layers) seems better than just always computing it at a higher level and crossing your fingers that you got your pass pipeline right and the outer analysis doesn't get invalidated before it is needed.

-- Sean Silva

[Finkel, Hal J. via llvm-dev]

Sent from my Verizon Wireless 4G LTE DROID

On Jul 25, 2016 6:16 PM, Sean Silva <chiso...@gmail.com> wrote:

>

>

>

> On Mon, Jul 25, 2016 at 9:27 AM, Hal Finkel <hfi...@anl.gov> wrote:

>>

>>

>> ________________________________

>>>

>>> From: "Sean Silva" <chiso...@gmail.com>

>>> To: "Chandler Carruth" <chan...@gmail.com>

>>> Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>

>>> Sent: Friday, July 22, 2016 3:55:52 AM

>>> Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

>>>

>>> 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.

>>

>> This makes sense to me.

>>

>> We do currently have some "in between" passes, like LCSSA, which are transformations, but are required by other passes, and transform the IR but whose preservation represents properties of the IR. The particulars of how we handle LCSSA aside (e.g. I think we should preserve it more, perhaps everywhere), how are we planning on handling this class of things?

>

>

> The new PM doesn't currently have a concept like this. As you mentioned, it is a weird cross between a transformation and an analysis: it can be "invalidated" like an analysis, but "recomputing" it actually mutates the IR like a transformation.

>

> I'd like to preface the below with the following:

> No matter how we ultimately address this requirement, my preference is that we do so in a way that applies to the old PM. This is a case where the old PM supports a richer set of functionality than the new PM. By incrementally refactoring the old PM away from its use of this extra capability and towards whatever "new" way there is to do it, we will understand better what it is that we actually need.

>

> (and sorry for the brain dump in the rest of this post)

>

>

>

> I have not seen any mention of a solution to this problem besides "we shouldn't do that", which is sort of a cop-out. Here is a strawman proposal:

>

> If it isn't too expensive, one simple alternative is to have passes just make a call to a utility function to put things in LCSSA if they need it (this utility would also have to invalidate analyses).

> If that ends up being expensive, we can have a dummy "indicator" analysis IRIsInLCSSAForm which, if cached, means "don't bother to call the utility function". We could maybe just use the LCSSA pass directly to do the transformation. LCSSA could have IRIsInLCSSAForm as an member typedef `IndicatorT` so it can be accessed generically. We could then support an API like:

I think this idea makes sense. My understanding is: There is nothing that prevents an analysis results from exposing a utility that transforms IR, and the result can certainly cache whether or not this transformation has been performed.

>

> ```

> FooTransformation.cpp:

>

> PreservedAnalyses FooTransformation::run(Function &F, AnalysisManager AM) {

>   // Must be called before getting analyses, as it might invalidate some.

>   canonicalizeIR<LCSSA>(F, AM);

>

>   ...

> }

>

>

> include/IR/Canonicalization.h:

>

> template <typename CanonicalizationT, typename IRUnitT>

> void canonicalizeIR(IRUnitT &IR, AnalysisManager &AM) {

>   using IndicatorT = typename CanonicalizationT::IndicatorAnalysis;

>   if (AM.getCachedResult<IndicatorT>(IR))

>     return;

>   CanonicalizationT C;

>   PreservedAnalysis PA = C.run(IR, AM);

>   AM.invalidate(IR, PA);

>   (void)AM.getResult<IndicatorT>(IR);

> }

>

> ```

>

>

> One place that talks about this problem of "requiring a transformation" is http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf on slide 17.

>

> One reason it provides for "we shouldn't do that" is that if you think about these things as "canonicalize the IR into a specific form", then when you have N>1 such dependencies (like some passes do on LoopSimplify and LCSSA), one must have a subset of the requirements of the other. I.e. you can't have two canonicalizations that "fight" each other. Using an explicit mutation API like the strawman above is a bit less bulletproof than scheduling based on statically known interferences between canonicalizations (e.g. CanonicalizationA may invalidate CanonicalizationB, but not the reverse, so it would automatically know to run CanonicalizationA before CanonicalizationB), but given that we have relatively few "canonicalizations" (to give them a name) that use this feature of the old PM, it may be livable (at least in the middle-end, it seems like there is just LCSSA, LoopSimplify, BreakCriticalEdges, and LowerSwitch in calls to addPreservedID/addRequiredID).

>

> I don't find the "Causes rampant re-running of invalidated analyses" argument in that slide convincing. If a pass needs the IR in LCSSA then it needs it. There isn't much we can do about that.

>

>

>

>

> One invariant I'd like to preserve in the new pass manager is that whatever pipeline is provided on the opt command line, we end up running something "valid"; so a cop-out like "if a pass needs LCSSA, you need to make sure to add LCSSA at an appropriate place before it in the pipeline" is not something I think is reasonable (way too error-prone).

>

> Small rant:

>

> We already are in this error-prone situation in the new PM with the need to call `getCachedResult` to access analyses from a larger IRUnitT (e.g. the situation I explained in the post-commit thread of r274712);

Yea, I don't like this either. I think we both agree that we need a better solution to this. I think we should fix this now and then deal with potential concurrency issues when we actually have a design for that so we know what that means.

-Hal

[Chandler Carruth via llvm-dev]

Somewhat agreed, but I don't actually think this problem is as bad as it seems in practice.

We only have two places that do this (loop simplify and lcssa) and they both *can* be modeled as "check if it is form X, and if not, put it in form X" or as "check if it is form X, and if not, give up on transform". This has been discussed several times, and the direction things have been leaning for a long time has been:

- Make LCSSA increasingly fundamental to the IR and always present, *or* don't require LCSSA at all for transforms. Either of these solve the problem.

- Check for loop-simplified form if necessary, and skip the transformation if not present. Because simplified form is simple to check this seems to work well.

Anyways, I don't think we have to solve this problem 100% to make progress on the pass manager. AT no point have I felt particularly blocked on this.

 

>

> ```

> FooTransformation.cpp:

>

> PreservedAnalyses FooTransformation::run(Function &F, AnalysisManager AM) {

>   // Must be called before getting analyses, as it might invalidate some.

>   canonicalizeIR<LCSSA>(F, AM);

>

>   ...

> }

>

>

> include/IR/Canonicalization.h:

>

> template <typename CanonicalizationT, typename IRUnitT>

> void canonicalizeIR(IRUnitT &IR, AnalysisManager &AM) {

>   using IndicatorT = typename CanonicalizationT::IndicatorAnalysis;

>   if (AM.getCachedResult<IndicatorT>(IR))

>     return;

>   CanonicalizationT C;

>   PreservedAnalysis PA = C.run(IR, AM);

>   AM.invalidate(IR, PA);

>   (void)AM.getResult<IndicatorT>(IR);

> }

>

> ```

>

>

> One place that talks about this problem of "requiring a transformation" is http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf on slide 17.

>

> One reason it provides for "we shouldn't do that" is that if you think about these things as "canonicalize the IR into a specific form", then when you have N>1 such dependencies (like some passes do on LoopSimplify and LCSSA), one must have a subset of the requirements of the other. I.e. you can't have two canonicalizations that "fight" each other. Using an explicit mutation API like the strawman above is a bit less bulletproof than scheduling based on statically known interferences between canonicalizations (e.g. CanonicalizationA may invalidate CanonicalizationB, but not the reverse, so it would automatically know to run CanonicalizationA before CanonicalizationB), but given that we have relatively few "canonicalizations" (to give them a name) that use this feature of the old PM, it may be livable (at least in the middle-end, it seems like there is just LCSSA, LoopSimplify, BreakCriticalEdges, and LowerSwitch in calls to addPreservedID/addRequiredID).

>

> I don't find the "Causes rampant re-running of invalidated analyses" argument in that slide convincing. If a pass needs the IR in LCSSA then it needs it. There isn't much we can do about that.

>

>

>

>

> One invariant I'd like to preserve in the new pass manager is that whatever pipeline is provided on the opt command line, we end up running something "valid"; so a cop-out like "if a pass needs LCSSA, you need to make sure to add LCSSA at an appropriate place before it in the pipeline" is not something I think is reasonable (way too error-prone).

>

> Small rant:

>

> We already are in this error-prone situation in the new PM with the need to call `getCachedResult` to access analyses from a larger IRUnitT (e.g. the situation I explained in the post-commit thread of r274712);

Yea, I don't like this either. I think we both agree that we need a better solution to this. I think we should fix this now and then deal with potential concurrency issues when we actually have a design for that so we know what that means.

FWIW, I strongly disagree.

I think it would be better to iterate on this once we understand how the new pass manager works. I think exposing the fact that these things are cached is really important and useful, and it makes querying across IR unit boundaries significantly more clear at the call site.

[Sean Silva via llvm-dev]

Personally, I would find it very disturbing if a transformation ever just silently does nothing. Especially if it depends on whether some set of previous transformations makes particular changes.

When I talked to you in person at the social (last one or the one before IIRC), you also mentioned that you think that silently doing nothing is the solution to when an analysis on a larger IRUnit is not cached.

Anyways, I don't think we have to solve this problem 100% to make progress on the pass manager. AT no point have I felt particularly blocked on this.

 

>

> ```

> FooTransformation.cpp:

>

> PreservedAnalyses FooTransformation::run(Function &F, AnalysisManager AM) {

>   // Must be called before getting analyses, as it might invalidate some.

>   canonicalizeIR<LCSSA>(F, AM);

>

>   ...

> }

>

>

> include/IR/Canonicalization.h:

>

> template <typename CanonicalizationT, typename IRUnitT>

> void canonicalizeIR(IRUnitT &IR, AnalysisManager &AM) {

>   using IndicatorT = typename CanonicalizationT::IndicatorAnalysis;

>   if (AM.getCachedResult<IndicatorT>(IR))

>     return;

>   CanonicalizationT C;

>   PreservedAnalysis PA = C.run(IR, AM);

>   AM.invalidate(IR, PA);

>   (void)AM.getResult<IndicatorT>(IR);

> }

>

> ```

>

>

> One place that talks about this problem of "requiring a transformation" is http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf on slide 17.

>

> One reason it provides for "we shouldn't do that" is that if you think about these things as "canonicalize the IR into a specific form", then when you have N>1 such dependencies (like some passes do on LoopSimplify and LCSSA), one must have a subset of the requirements of the other. I.e. you can't have two canonicalizations that "fight" each other. Using an explicit mutation API like the strawman above is a bit less bulletproof than scheduling based on statically known interferences between canonicalizations (e.g. CanonicalizationA may invalidate CanonicalizationB, but not the reverse, so it would automatically know to run CanonicalizationA before CanonicalizationB), but given that we have relatively few "canonicalizations" (to give them a name) that use this feature of the old PM, it may be livable (at least in the middle-end, it seems like there is just LCSSA, LoopSimplify, BreakCriticalEdges, and LowerSwitch in calls to addPreservedID/addRequiredID).

>

> I don't find the "Causes rampant re-running of invalidated analyses" argument in that slide convincing. If a pass needs the IR in LCSSA then it needs it. There isn't much we can do about that.

>

>

>

>

> One invariant I'd like to preserve in the new pass manager is that whatever pipeline is provided on the opt command line, we end up running something "valid"; so a cop-out like "if a pass needs LCSSA, you need to make sure to add LCSSA at an appropriate place before it in the pipeline" is not something I think is reasonable (way too error-prone).

>

> Small rant:

>

> We already are in this error-prone situation in the new PM with the need to call `getCachedResult` to access analyses from a larger IRUnitT (e.g. the situation I explained in the post-commit thread of r274712);

Yea, I don't like this either. I think we both agree that we need a better solution to this. I think we should fix this now and then deal with potential concurrency issues when we actually have a design for that so we know what that means.

FWIW, I strongly disagree.

Thankfully at least right now we just flat-out assert/crash alerting to the issue. I don't want to live in a world where passes start to silently become no-ops (possibly in a way that only manifests if e.g. a particular other pass in the pipeline happens to make changes and hence invalidate a particular analysis).

That would mean living in a world where e.g. you do you build of test-suite with an experimental pipeline and halfway through get a message like "warning: licm is doing nothing" (if you even get that) and have to go and figure out which `require<...>` you need to put at a higher level, or figuring out which loop pass invalidated something that licm needed.

This is exactly the current situation, but instead of a message you just get an assertion failure / crash.

FWIW, I've been running realistic pipelines and actually using the new PM "for real" (e.g. bisecting a realistic pass pipeline on the opt command line to find where a bug is coming from, testing different optimization pipelines, etc.) and this is definitely one of the main issues.

I think once you start testing out the new PM "for real" you will change your position.

(Correct me if I'm wrong, but I have to assume that you haven't yet because you would have run into the showstopping bug that started this thread (filed as PR28622), or PR28400, or even simply PR28577.)

-- Sean Silva

[Sean Silva via llvm-dev]

I'm not quite sure what post to respond to for a status update, but I guess this one will do (and you can check my log for more info of course).

My current working branch for the analysis manager stuff is at https://github.com/chisophugis/llvm/commits/analysis-manager

(4ecf6115890bd01caa52c0b99424974e3469291e)

I described in my log a bit more my thought process and how to do this without having to churn every single new PM pass (search for "Okay, so now that I think about it, adding the dependency management is a second step after making the analysis manager work for all IRUnit’s."). Essentially, the first step is to still have AnalysisManager<Function>, AnalysisManager<Module>, etc. but the template argument is just a dummy. The real templating is on the methods, which can accept any IRUnit. The advantage of this is that it is source compatible with all the existing code using multiple manager, proxies, etc.

The code on my branch at least passes check-llvm. But of course the existing code doesn't test any of the situations where being able to handle multiple IRUnitT's in a single analysis manager would matter.

Tomorrow, I get to churn all the passes that have been ported so far, removing the proxies etc.

Another thing that just came to me: the current way things work with adaptors means that if a function transformation invalidates a module analysis, the module analysis won't be invalidated until after the ModuleToFunctionPassAdapter returns.

So we can end up running an arbitrary number of function transformations that query that stale module analysis. This is (I think?) mostly benign given our current set of module analyses (more info in the log; search for "We may be getting by simply because we seem to not have many module analyses"). But if we invalidate more "correctly" (after every transformation on any contained IRUnit), there's a potential quadratic compile time issue lurking here once have the unified analysis manager: we could easily end up invalidating/recomputing a module analysis once per function visitation.

For a pipeline that just does a lot of churn (e.g. function simplification passes we run as part of the regular O3 pipeline; that can delete most code in a function, change the cfg, etc.) it's not clear what useful properties we can guarantee will be preserved which would prevent us from invalidating pretty much all non-immutable outer analyses (module or (theoretically)CGSCC). So for any really nontrivial module analysis, we may end up having to change the interface of module passes to have some way to incrementally recompute themselves as function passes mutate the IR?

In some sense, Chandler's CGSCC patch https://reviews.llvm.org/D21464 is trying to do this for a specific module analysis (lazy call graph) and even for just that one (and lots of special handling in the adaptors etc.) it still only gets incrementally updated it after a potentially large set of function passes have run. And it's already quite tricky.

Broadly speaking, I can think of two major kinds of "solutions" to this problem:

- severely restrict the interaction of function transformations and module analyses in some way. Essentially, we could define a restricted class of module analyses that "are conservatively correct in the face of any transformation that can be made by a function transformation" (this includes immutable module analyses and IIRC things like GlobalsModRef). But the issue is a bit deeper, because it is really about transformations at any smaller IRUnitT. This includes CGSCC. And CGSCC can do substantial interprocedural transformation (e.g. delete a wholefunction IIRC?); we would then need to have another class of module analyses that are "conservatively correct in the face of CGSCC transformations" which seems quite restrictive.

-- alternatively or in addition, this can involve restricting what kind of information a function pass can get out of a module analysis

- provide some sort of update callback for the outer IRUnit analysis to update itself if the inner one is modified (not sure how practical this will be). E.g. `AM.invalidate<FooModuleAnalysis>(F);` doesn't actually invalidate FooModuleAnalysis, but rather invokes a callback for it to update itself (possibly as an opt-in for the module analysis).

-- The current analysis manager does have a `invalidate` hook that it will call, but the argument is always inherently the IRUnit that the analysis itself is cached on so it isn't useful for partial recomputation. We would need to extend that, which requires making the AnalysisResultConcept more complicated (and potentially having to have centralized awareness of all the different IRUnitT's, which until now are fairly decoupled in the new PM).

I'm curious what others' thoughts are on this issue.

-- Sean Silva

[Hal Finkel via llvm-dev]

Sure, but we need some solution in order to port our current set of passes to the new pipeline. It sounds like you're proposing that we make the passes that require LCSSA exit early if the IR is not in LCSSA form, and then add the LCSSA pass explicitly into the pipeline, or always do the work to actively put the IR into LCSSA form in each pass that requires it (unless someone is going to do the work now to make LCSSA preserved by all other relevant passes)? What do you feel is the preferred path forward here?

>

> ```

> FooTransformation.cpp:

>

> PreservedAnalyses FooTransformation::run(Function &F, AnalysisManager AM) {

>   // Must be called before getting analyses, as it might invalidate some.

>   canonicalizeIR<LCSSA>(F, AM);

>

>   ...

> }

>

>

> include/IR/Canonicalization.h:

>

> template <typename CanonicalizationT, typename IRUnitT>

> void canonicalizeIR(IRUnitT &IR, AnalysisManager &AM) {

>   using IndicatorT = typename CanonicalizationT::IndicatorAnalysis;

>   if (AM.getCachedResult<IndicatorT>(IR))

>     return;

>   CanonicalizationT C;

>   PreservedAnalysis PA = C.run(IR, AM);

>   AM.invalidate(IR, PA);

>   (void)AM.getResult<IndicatorT>(IR);

> }

>

> ```

>

>

> One place that talks about this problem of "requiring a transformation" is http://llvm.org/devmtg/2014-04/PDFs/Talks/Passes.pdf on slide 17.

>

> One reason it provides for "we shouldn't do that" is that if you think about these things as "canonicalize the IR into a specific form", then when you have N>1 such dependencies (like some passes do on LoopSimplify and LCSSA), one must have a subset of the requirements of the other. I.e. you can't have two canonicalizations that "fight" each other. Using an explicit mutation API like the strawman above is a bit less bulletproof than scheduling based on statically known interferences between canonicalizations (e.g. CanonicalizationA may invalidate CanonicalizationB, but not the reverse, so it would automatically know to run CanonicalizationA before CanonicalizationB), but given that we have relatively few "canonicalizations" (to give them a name) that use this feature of the old PM, it may be livable (at least in the middle-end, it seems like there is just LCSSA, LoopSimplify, BreakCriticalEdges, and LowerSwitch in calls to addPreservedID/addRequiredID).

>

> I don't find the "Causes rampant re-running of invalidated analyses" argument in that slide convincing. If a pass needs the IR in LCSSA then it needs it. There isn't much we can do about that.

>

>

>

>

> One invariant I'd like to preserve in the new pass manager is that whatever pipeline is provided on the opt command line, we end up running something "valid"; so a cop-out like "if a pass needs LCSSA, you need to make sure to add LCSSA at an appropriate place before it in the pipeline" is not something I think is reasonable (way too error-prone).

>

> Small rant:

>

> We already are in this error-prone situation in the new PM with the need to call `getCachedResult` to access analyses from a larger IRUnitT (e.g. the situation I explained in the post-commit thread of r274712);

Yea, I don't like this either. I think we both agree that we need a better solution to this. I think we should fix this now and then deal with potential concurrency issues when we actually have a design for that so we know what that means.

FWIW, I strongly disagree.

I think it would be better to iterate on this once we understand how the new pass manager works. I think exposing the fact that these things are cached is really important and useful, and it makes querying across IR unit boundaries significantly more clear at the call site.

To be clear, the current code looks like this:

LoopAccessInfo LoopAccessAnalysis::run(Loop &L, AnalysisManager<Loop> &AM) {
  const AnalysisManager<Function> &FAM =
      AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
  Function &F = *L.getHeader()->getParent();
  auto *SE = FAM.getCachedResult<ScalarEvolutionAnalysis>(F);
  auto *TLI = FAM.getCachedResult<TargetLibraryAnalysis>(F);
  auto *AA = FAM.getCachedResult<AAManager>(F);
  auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(F);
  auto *LI = FAM.getCachedResult<LoopAnalysis>(F);
  if (!SE)
    report_fatal_error(
        "ScalarEvolution must have been cached at a higher level");
  if (!AA)
    report_fatal_error("AliasAnalysis must have been cached at a higher level");
  if (!DT)
    report_fatal_error("DominatorTree must have been cached at a higher level");
  if (!LI)
    report_fatal_error("LoopInfo must have been cached at a higher level");
  auto *DI = UseDA ? FAM.getCachedResult<DependenceAnalysis>(F) : nullptr;
  return LoopAccessInfo(&L, SE, DI, TLI, AA, DT, LI);
}

I don't find this an acceptable design. These passes are required, and the pass manager should provide them in a reasonable way. Alternatively, the pass needs to exit early if its dependencies are not met.

 -Hal

[Hal Finkel via llvm-dev]

In some sense, this is always true, and it is not particularly disturbing. Optimizations enable other optimizations, and so on. I think you're referring here to a more-specific situation: transformations have hard dependencies on other transformations, and those dependencies are not declared, or automatically satisfied, making them hard to use and debug. i.e. composing an opt command line to replicate a problem will be somewhat-unfortunately subtle.

I'm happy to have a mode which crashes, for us, to help with test-case reduction, etc. I don't think we should have this by default, however. We can have warnings and collect statistics instead.

Thanks again,
Hal

FWIW, I've been running realistic pipelines and actually using the new PM "for real" (e.g. bisecting a realistic pass pipeline on the opt command line to find where a bug is coming from, testing different optimization pipelines, etc.) and this is definitely one of the main issues.

I think once you start testing out the new PM "for real" you will change your position.

(Correct me if I'm wrong, but I have to assume that you haven't yet because you would have run into the showstopping bug that started this thread (filed as PR28622), or PR28400, or even simply PR28577.)

-- Sean Silva

 

I think it would be better to iterate on this once we understand how the new pass manager works. I think exposing the fact that these things are cached is really important and useful, and it makes querying across IR unit boundaries significantly more clear at the call site.

[Hal Finkel via llvm-dev]

From: "Sean Silva" <chiso...@gmail.com>
To: "Chandler Carruth" <chan...@gmail.com>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@apple.com>
Sent: Tuesday, July 26, 2016 3:32:55 AM
Subject: Re: [PM] I think that the new PM needs to learn about inter-analysis dependencies...

I'm not quite sure what post to respond to for a status update, but I guess this one will do (and you can check my log for more info of course).

My current working branch for the analysis manager stuff is at https://github.com/chisophugis/llvm/commits/analysis-manager

(4ecf6115890bd01caa52c0b99424974e3469291e)

I described in my log a bit more my thought process and how to do this without having to churn every single new PM pass (search for "Okay, so now that I think about it, adding the dependency management is a second step after making the analysis manager work for all IRUnit’s."). Essentially, the first step is to still have AnalysisManager<Function>, AnalysisManager<Module>, etc. but the template argument is just a dummy. The real templating is on the methods, which can accept any IRUnit. The advantage of this is that it is source compatible with all the existing code using multiple manager, proxies, etc.

The code on my branch at least passes check-llvm. But of course the existing code doesn't test any of the situations where being able to handle multiple IRUnitT's in a single analysis manager would matter.

Tomorrow, I get to churn all the passes that have been ported so far, removing the proxies etc.

Another thing that just came to me: the current way things work with adaptors means that if a function transformation invalidates a module analysis, the module analysis won't be invalidated until after the ModuleToFunctionPassAdapter returns.

So we can end up running an arbitrary number of function transformations that query that stale module analysis. This is (I think?) mostly benign given our current set of module analyses (more info in the log; search for "We may be getting by simply because we seem to not have many module analyses"). But if we invalidate more "correctly" (after every transformation on any contained IRUnit), there's a potential quadratic compile time issue lurking here once have the unified analysis manager: we could easily end up invalidating/recomputing a module analysis once per function visitation.

For a pipeline that just does a lot of churn (e.g. function simplification passes we run as part of the regular O3 pipeline; that can delete most code in a function, change the cfg, etc.) it's not clear what useful properties we can guarantee will be preserved which would prevent us from invalidating pretty much all non-immutable outer analyses (module or (theoretically)CGSCC). So for any really nontrivial module analysis, we may end up having to change the interface of module passes to have some way to incrementally recompute themselves as function passes mutate the IR?

In some sense, Chandler's CGSCC patch https://reviews.llvm.org/D21464 is trying to do this for a specific module analysis (lazy call graph) and even for just that one (and lots of special handling in the adaptors etc.) it still only gets incrementally updated it after a potentially large set of function passes have run. And it's already quite tricky.

Broadly speaking, I can think of two major kinds of "solutions" to this problem:

- severely restrict the interaction of function transformations and module analyses in some way. Essentially, we could define a restricted class of module analyses that "are conservatively correct in the face of any transformation that can be made by a function transformation" (this includes immutable module analyses and IIRC things like GlobalsModRef). But the issue is a bit deeper, because it is really about transformations at any smaller IRUnitT. This includes CGSCC. And CGSCC can do substantial interprocedural transformation (e.g. delete a wholefunction IIRC?); we would then need to have another class of module analyses that are "conservatively correct in the face of CGSCC transformations" which seems quite restrictive.

-- alternatively or in addition, this can involve restricting what kind of information a function pass can get out of a module analysis

- provide some sort of update callback for the outer IRUnit analysis to update itself if the inner one is modified (not sure how practical this will be). E.g. `AM.invalidate<FooModuleAnalysis>(F);` doesn't actually invalidate FooModuleAnalysis, but rather invokes a callback for it to update itself (possibly as an opt-in for the module analysis).

-- The current analysis manager does have a `invalidate` hook that it will call, but the argument is always inherently the IRUnit that the analysis itself is cached on so it isn't useful for partial recomputation. We would need to extend that, which requires making the AnalysisResultConcept more complicated (and potentially having to have centralized awareness of all the different IRUnitT's, which until now are fairly decoupled in the new PM).

I think that one of these last two options seems best. We should support the module-level analysis incrementally updating itself.

However, I think that we should invalidate eagerly by default, even though that leads to a potential quadratic compile-time problem, and then make sure we fix passes in the pipeline not to invalidate the module-level passes we use. This particular problem is, as it were, by design.

Thanks again,
Hal

[Mikhail Zolotukhin via llvm-dev]

Recomputing LCSSA in every time might be very expensive and/or also error-prone. Many loop passes assume that *all* loops are in LCSSA form (I remember fixing a related bug in loop-unroll IIRC). Rebuilding LCSSA for all loops in a loop pass quickly leads to a non-linear behavior, and rebuilding it for only the current loop is sometimes not enough (and might be expensive too).

FWIW, I've been trying to improve this situation, so I'm willing to continue put my efforts into this area. Actually, I think we're almost at a state where all loop passes preserve it.

Michael

[Sean Silva via llvm-dev]

Actually, I think that some loop pass not being able to do anything because its input in LCSSA as a case that is less problematic. I think your argument is pretty solid that transformations interact in subtle ways already.

I'm more concerned with the "must be cached at a higher level" issue, as in my practical testing in the new PM this has led to substantial wastes of time. Essentially, what this leads to is that you write out a pipeline (e.g. insert a pass somewhere in the pipeline) and rebuild test-suite, a bunch of errors spew, then you have to go to the source code of the pass that is emitting the "must be cached at a higher level", see what else it needs, try adding that, and repeating. It's pretty miserable and wastes a lot of time.

(also, it doesn't help that the pass pipeline parser's diagnostics are currently at the level of "error parsing pass pipeline" with no other information; yeah, yeah, patches welcome etc. just haven't got around to it)

-- Sean Silva

[Sean Silva via llvm-dev]

Okay, did the big renaming and de-templating today (and removing the proxies).

check-llvm worked fine, except that this test caught a bug (yay!):

unittests/IR/PassManagerTest.cpp:326

After removing the proxies, the module pass is not invalidating the function passes (since the invalidation is on the module IRUnit). we now don't have a method for delegating the invalidation from outer IRUnit's to inner IRUnit's.

I'll try to add a mechanism for the analysis manager to do this itself if there's a straightforward way to do so. Not sure the best way. We can't just iterate over all the functions calling `invalidate`; a module pass may have e.g. deleted a function, so we would never call `invalidate` on the deleted function. A simple solution is to add another member to the analysis manager which tracks, for each IRUnitT, all IRUnit's that we have state cached for (so we can easily walk them).

Interestingly, it seems like the current state in trunk is that a module analysis can't preserve a specific function analysis. The only way that analysis invalidation can propagate downwards is by clearing the entire inner analysis manager.

So I think this means that the current state in trunk is that if a function transformation returns PreservedAnalyses::none(), it will invalidate all loop analyses for all functions.

(I think Chandler mentioned this issue in passing here: https://reviews.llvm.org/D21921#inline-187608)

(slightly more info in my log)

Anyway, for now, I'll try to do something that is as NFC as possible. Hopefully just tracking all the IRUnit's per IRUnitT will allow us to emulate the proxy-based invalidation fairly well.

It is probably relevant to discuss how we want to "properly" deal with this with the unified analysis manager for all IRUnitT's.

One solution is to have the pass managers (actually, the adaptors), push/pop a stack of the current IRUnit nest (e.g. the stack might contain at a given point in time something like `[Module foo, Function @bar]` or `[Module foo, SCC bar, Function @baz, Loop %qux]`).

The key information that is needed is for the analysis manager to be able to reconstruct a parent-child relationship of IRUnit's (which might contain parent-child links that are no longer obtainable from the parent IRUnit; e.g. when you go to invalidate analyses after running a module pass that deleted a function; the analysis manager must still track that relationship even if the module has already forgotten about the function). 

I don't see any reasonable way to do this without cooperation from the adaptors, because (like the example "IRUnit stacks" I showed above) the analysis manager would need a way to know whether to map back to a particular SCC or to a particular Module (or potentially both).

-- Sean Silva

[Sean Silva via llvm-dev]

I have the unified analysis manager implemented now and passing all tests at: https://github.com/chisophugis/llvm/commits/analysis-manager

One caveat:

It would be a layering violation for the analysis manager to know about Loop and SCC since those live in libAnalysis. So currently I have some stuff commented out for imitating the proxy downward invalidation for them. (and generally the proxy downward invalidation imitation stuff is somewhat ugly; it is in invalidatImpl: https://github.com/chisophugis/llvm/commit/23a65b884d3f15a928ceaef63a8293ab2eda2348#diff-c94a14214ca2d8403849baf9bb4d90e1R559).

It more or less imitates what the proxy was doing, albeit that it does it by iterating the map and invalidating any lower IRUnit's instead of just clearing the other analysis manager.

I'm happy to add an indirect interface to make it work with all the IRUnit's.

Down the road, if we have pass manager cooperation (such as the push/pop thing I mentioned for tracking outer/inner IRUnit relationships) we can make this much smarter and support IRUnit's more generically without a hardcoded list.

I'll start working on the inter-analysis dependency stuff tomorrow.

-- Sean Silva

[Philip Reames via llvm-dev]

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 audit. 

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 <chiso...@gmail.com> wrote:

On Thu, Jul 14, 2016 at 7:21 PM, Hal Finkel <hfi...@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" <chiso...@gmail.com>
To: "Chandler Carruth" <chan...@gmail.com>
Cc: "Xinliang David Li" <dav...@google.com>, "llvm-dev" <llvm...@lists.llvm.org>, "Davide Italiano" <dccit...@gmail.com>, "Tim Amini Golling" <mehdi...@apple.com>, "Hal Finkel" <hfi...@anl.gov>, "Sanjoy Das" <san...@playingwithpointers.com>, "Pete Cooper" <peter_...@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...

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

[Sean Silva via llvm-dev]

The unified analysis manager + dependency tracking patch is up: https://reviews.llvm.org/D23256

Please take a look.

-- Sean Silva

[Sean Silva via llvm-dev]

On Sun, Aug 7, 2016 at 4:55 PM, Philip Reames <list...@philipreames.com> wrote:

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. 

Chandler's suggestion here doesn't actually avoid the issue.

A simple proof that this approach cannot work is that the issue at hand is one of insufficient invalidation. The `invalidate` callback can only prevent invalidation, so Chandler's suggestion of overriding it can only prevent invalidation -- it cannot trigger additional invalidation and therefore cannot solve a problem of insufficient invalidation.

-- Sean Silva

[Jan Sjodin via llvm-dev]

When we talk about stale information, what does it mean exactly? This goes back to the point about how what guarantees are made about the analysis information, and when it is invalidated. If some information is wrong for the current IR (during a transform), but still fully correct with regards to the IR that was given to the analysis before the transform, this is information that some transforms actually need. The other case is if the analysis info directly points to the IR that is being modified, and some information is wrong for both the old and current IR, which could cause the transform to fail. What should the policy be for analyses, and how would someone writing a transform know when information becomes stale and how?

- Jan  

 

Thanks again,
Hal

---

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-cgsc c-analysis>),some-module-pass- that-makes-no-changes,cgscc(so me-cgscc-pass-that-uses-foo-cg scc-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...@lists.llvm.org
http://lists.llvm.org/cgi-bin/ mailman/listinfo/llvm-dev

[Sean Silva via llvm-dev]

On Tue, Aug 9, 2016 at 8:29 AM, Jan Sjodin <jan_s...@yahoo.com> wrote:

When we talk about stale information, what does it mean exactly? This goes back to the point about how what guarantees are made about the analysis information, and when it is invalidated. If some information is wrong for the current IR (during a transform), but still fully correct with regards to the IR that was given to the analysis before the transform, this is information that some transforms actually need. The other case is if the analysis info directly points to the IR that is being modified, and some information is wrong for both the old and current IR, which could cause the transform to fail. What should the policy be for analyses, and how would someone writing a transform know when information becomes stale and how?

Those are more subtle issues. The notion of "stale" we are talking about right now is literally just use-after-free. I.e. an analysis result A holds a pointer to an object that is freed when analysis result B is invalidated. When B is invalidated, A must be invalidated too.

-- Sean Silva