<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Wed, Jul 13, 2016 at 12:34 AM, Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_quote"><div><div class="h5"><div dir="ltr">On Wed, Jul 13, 2016 at 12:25 AM Sean Silva <<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>> wrote:<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Jul 12, 2016 at 11:39 PM, Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</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 dir="ltr"><div class="gmail_quote"><span><div dir="ltr">On Tue, Jul 12, 2016 at 11:34 PM Sean Silva <<a href="mailto:chisophugis@gmail.com" target="_blank">chisophugis@gmail.com</a>> wrote:<br></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 dir="ltr"><div class="gmail_extra"><div class="gmail_quote">On Tue, Jul 12, 2016 at 11:32 PM, Xinliang David Li <span dir="ltr"><<a href="mailto:davidxl@google.com" target="_blank">davidxl@google.com</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 dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote"><span>On Tue, Jul 12, 2016 at 10:57 PM, Chandler Carruth <span dir="ltr"><<a href="mailto:chandlerc@gmail.com" target="_blank">chandlerc@gmail.com</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 dir="ltr"><div class="gmail_quote"><div>Yea, this is a nasty problem.</div><div><br></div><div>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.</div></div></div></blockquote><div><br></div></span><div>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.</div><div><br></div><div>There are actually quite a few examples of hard-dependency case. For instance LoopAccessInfo, LazyValueInfo etc which hold references to other analyses.</div><div><br></div><div>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.</div></div></div></div></blockquote><div><br></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div>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.<br></div></div></div></div></blockquote><div><br></div></span><div>The issue is that the fact that there is *any* dependency isn't clear.</div><div><br></div><div>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.</div><div><br></div><div>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.</div></div></div></blockquote><div><br></div></div></div></div><div dir="ltr"><div class="gmail_extra"><div class="gmail_quote"><div><div><br>I just did a quick run-through of PassRegistry.def and this is what I found:</div><div><br></div><div>Module analyses: 0/5 hold pointers to other analyses</div><div>CallGraph: No pointers to other analyses.</div><div>LazyCallGraph: No pointers to other analyses.</div><div>ProfileSummaryAnalysis: No pointers to other analyses.</div><div>TargetLibraryAnalysis: No pointers to other analyses.<br></div><div>VerifierAnalysis: No pointers to other analyses.</div><div><br></div><div>Module alias analyses: 1/1 keeps pointer to other analysis.</div><div>GlobalsAA: Result keeps pointer to TLI (this is a function analysis).</div><div><br></div><div>Function analyses: 9/17 keep pointers to other analysis</div><div>AAManager: Its Result holds TLI pointer and pointers to individual AA result objects.</div><div>AssumptionAnalysis: No pointers to other analyses.<br></div><div>BlockFrequencyAnalysis: Its Result holds pointers to LoopInfo and BPI.<br></div><div>BranchProbabilityAnalysis: Stores no pointers to other analyses. (uses LoopInfo to "recalculate" though)<br></div><div>DominatorTreeAnalysis: Stores no pointers to other analyses.<br></div><div>PostDominatorTreeAnalysis: Stores no pointers to other analyses.</div><div>DemandedBitsAnalysis: Stores pointers to AssumptionCache and DominatorTree<br></div><div>DominanceFrontierAnalysis: Stores no pointers to other analyses. (uses DominatorTreeAnalysis for "recalculate" though).<br></div><div>LoopInfo: Uses DominatorTreeAnalysis for "recalculate" but stores no pointers.<br></div><div>LazyValueAnalysis: Stores pointers to AssumptionCache, TargetLibraryInfo, DominatorTree.<br></div><div>DependenceAnalysis: Stores pointers to AliasAnalysis, ScalarEvolution, LoopInfo</div><div>MemoryDependenceAnalysis: Stores pointers to AliasAnalysis, AssumptionCache, TargetLibraryInfo, DominatorTree<br></div><div>MemorySSAAnalysis: Stores pointers to AliasAnalysis, DominatorTree<br></div><div>RegionInfoAnalysis: Stores pointers to DomTree, PostDomTree, DomFrontier<br></div><div>ScalarEvolutionAnalysis: Stores pointers to TargetLibraryInfo, AssumptionCache, DominatorTree, LoopInfo</div><div>TargetLibraryAnalysis: Has no dependencies<br></div><div>TargetIRAnalysis: Has no dependencies.<br></div><div><br></div><div>Function alias analyses: 3/5 keep pointers to other analyses</div><div>BasicAA: Keeps pointers to TargetLibraryInfo, AssumptionCache, DominatorTree, LoopInfo</div><div>CFLAA: Keeps pointer to TargetLibraryInfo</div><div>SCEVAA: Keeps pointer to ScalarEvolution</div><div>ScopedNoAliasAA: No dependencies<br></div><div>TypeBasedAA: No dependencies<br></div><div><br></div><div><br></div><div>Total: 13/28 analyses (~50%) hold pointers to other analyses.</div><div>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.</div><div>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%)</div></div></div></div></div></blockquote><div><br></div></div></div><div>Interesting!</div><div><br></div><div>Most of these look like they hold a pointer to the root analysis as opposed to detailed objects *inside* the analysis?</div><div><br></div><div>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.... <span style="line-height:1.5">We could try to make this work "automatically" but I'm worried this would be challenging to get right. Open to suggestions of course.</span></div><div><br></div><div>Any other ideas about what would make sense to handle this?</div><div><br></div><div>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...</div></div></div></blockquote><div><br></div><div>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.</div><div><br></div><div>-- Sean Silva</div></div><br></div></div>