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

[Hal Finkel via llvm-dev]

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