<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Jul 12, 2016 at 9:00 PM, Hal Finkel <span dir="ltr"><<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><br><hr><blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><b>From: </b>"Sean Silva" <<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>><br><b>To: </b>"llvm-dev" <<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</a>><br><b>Cc: </b>"Chandler Carruth" <<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>>, "Davide Italiano" <<a href="mailto:dccitaliano@gmail.com" target="_blank">dccitaliano@gmail.com</a>>, "David Li" <<a href="mailto:davidxl@google.com" target="_blank">davidxl@google.com</a>>, "Tim Amini Golling" <<a href="mailto:mehdi.amini@apple.com" target="_blank">mehdi.amini@apple.com</a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov" target="_blank">hfinkel@anl.gov</a>>, "Sanjoy Das" <<a href="mailto:sanjoy@playingwithpointers.com" target="_blank">sanjoy@playingwithpointers.com</a>>, "Pete Cooper" <<a href="mailto:peter_cooper@apple.com" target="_blank">peter_cooper@apple.com</a>><br><b>Sent: </b>Tuesday, July 12, 2016 8:15:22 PM<br><b>Subject: </b>[PM] I think that the new PM needs to learn about inter-analysis dependencies...<span class=""><br><br><div dir="ltr"><div>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!</div></div></span></blockquote>Nice :-)<span class=""><br><blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div dir="ltr"><div></div><div>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.</div><div><br></div><div>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.</div><div><br></div>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.<div><div><br></div><div>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:</div><div>1. A pass had to preserve BasicAA</div><div>2. lcssa would make a change and thus only preserve a subset of passes (if it made no changes it would have preserved all)</div><div>2. then LICM and MergedLoadStoreMotion had to run and make no changes (and hence preserve all).</div><div>3. then GVN had to run and query BasicAA</div><div><br></div><div>(presumably LICM or MergedLoadStoreMotion didn't make a query to BasicAA, or that query ended up not accessing the dangling TargetLibraryInfo).</div><div><br></div><div><br></div><div>How should we solve this? I see two potential solutions:</div><div>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).</div><div>2. The AnalysisManager must do a somewhat complicated dance to track when analyses call back into it in order to get other analyses.</div><div><br></div><div><br></div><div>Any other ideas? Any thoughts about how best to fix this?</div><div><br></div></div></div></blockquote></span>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.<br></div></div></blockquote><div><br></div><div>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).</div><div><br></div><div>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?</div><div><br></div><div>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.</div><div><br></div><div>-- Sean Silva<br></div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"><div><div style="font-family:arial,helvetica,sans-serif;font-size:10pt;color:rgb(0,0,0)"><br>Thanks again,<br>Hal<span class=""><br><blockquote style="border-left-width:2px;border-left-style:solid;border-left-color:rgb(16,16,255);margin-left:5px;padding-left:5px;color:rgb(0,0,0);font-weight:normal;font-style:normal;text-decoration:none;font-family:Helvetica,Arial,sans-serif;font-size:12pt"><div dir="ltr"><div><div></div><div><br></div><div><br></div><div>For those interested, a reduced test case is</div><div>/home/sean/pg/release-asan/bin/opt -debug-pass-manager '-passes=require<aa>,invalidate<targetlibinfo>,gvn' -aa-pipeline=basic-aa $1 -disable-output</div><div><br></div><div><div>target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"</div><div>target triple = "x86_64-unknown-linux-gnu"</div><div><br></div><div>declare void @foo(i32)</div><div><br></div><div>define void @sendMTFValues(i32 *%arg) {</div><div>entry:</div><div>  call void @foo(i32 0)</div><div>  %0 = load i32, i32* %arg</div><div>  call void @foo(i32 %0)</div><div>  ret void</div><div>}</div></div><div><br></div><div>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)).</div><div><br></div><div>-- Sean Silva</div><div><br></div><div><br></div><div><br></div></div></div>
</blockquote><br><br><br></span><span class=""><font color="#888888">-- <br><div><span name="x"></span>Hal Finkel<br>Assistant Computational Scientist<br>Leadership Computing Facility<br>Argonne National Laboratory<span name="x"></span><br></div></font></span></div></div></blockquote></div><br></div></div>