llvm dev - Jul 2016 - [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!

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160712/033907ac/attachment.html>

----- Original Message -----
> From: "Sean Silva" <chisophugis at gmail.com>
> To: "llvm-dev" <llvm-dev at lists.llvm.org>
> Cc: "Chandler Carruth" <chandlerc at gmail.com>,
"Davide Italiano"
> <dccitaliano at gmail.com>, "David Li" <davidxl at
google.com>, "Tim Amini
> Golling" <mehdi.amini at apple.com>, "Hal Finkel"
<hfinkel at anl.gov>,
> "Sanjoy Das" <sanjoy at playingwithpointers.com>,
"Pete Cooper"
> <peter_cooper at apple.com>
> Sent: 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 
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160712/e4b3972a/attachment.html>

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 <chisophugis at 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...
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160713/7abe809b/attachment.html>

On Tue, Jul 12, 2016 at 9:00 PM, Hal Finkel <hfinkel at anl.gov> wrote:
>
> ------------------------------
>
> *From: *"Sean Silva" <chisophugis at gmail.com>
> *To: *"llvm-dev" <llvm-dev at lists.llvm.org>
> *Cc: *"Chandler Carruth" <chandlerc at gmail.com>,
"Davide Italiano" <
> dccitaliano at gmail.com>, "David Li" <davidxl at
google.com>, "Tim Amini
> Golling" <mehdi.amini at apple.com>, "Hal Finkel"
<hfinkel at anl.gov>, "Sanjoy
> Das" <sanjoy at playingwithpointers.com>, "Pete
Cooper" <
> peter_cooper at apple.com>
> *Sent: *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

>
> 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
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160712/8a824a21/attachment.html>

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chandlerc at
gmail.com>
wrote:
> Yea, this is a nasty problem.
>
> One important thing to understand is that this is specific to analyses
> which hold references to other analyses. While this isn't unheard of,
it
> isn't as common as it could be. Still, definitely something we need to
> address.
>
We can call this type of dependencies (holding references) hard-dependency.
The soft dependency refers to the case where analysis 'A' depends on
'B'
during computation, but does not need 'B' once it is computed.

There are actually quite a few examples of hard-dependency case. For
instance LoopAccessInfo, LazyValueInfo etc which hold references to other
analyses.

Problem involving hard-dependency is actually easier to detect, as it is
usually a compile time problem. Issues involving soft dependencies are more
subtle and can lead to wrong code gen.

David


>
> Some ideas about mitigating and fixing it below.
>
> On Tue, Jul 12, 2016 at 6:15 PM Sean Silva <chisophugis at 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...
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160712/5234bf09/attachment.html>

On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <chandlerc at
gmail.com>
wrote:
> Yea, this is a nasty problem.
>
> One important thing to understand is that this is specific to analyses
> which hold references to other analyses. While this isn't unheard of,
it
> isn't as common as it could be. Still, definitely something we need to
> address.
>
> Some ideas about mitigating and fixing it below.
>
> On Tue, Jul 12, 2016 at 6:15 PM Sean Silva <chisophugis at 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

>
> 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...
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20160713/4f62474c/attachment.html>