<div dir="ltr">Sounds great! Hope the inter-procedure alias analysis can be added in next version, so next time i can call it directly ^_^</div><div class="gmail_extra"><br><div class="gmail_quote">On Thu, Jul 16, 2015 at 3:36 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:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="HOEnZb"><div class="h5">----- Original Message -----<br>
> From: "Chandler Carruth" <<a href="mailto:chandlerc@google.com">chandlerc@google.com</a>><br>
> To: "LLVM Developers Mailing List" <<a href="mailto:llvmdev@cs.uiuc.edu">llvmdev@cs.uiuc.edu</a>>, "Hal Finkel" <<a href="mailto:hfinkel@anl.gov">hfinkel@anl.gov</a>>, "Daniel Berlin"<br>
> <<a href="mailto:dannyb@google.com">dannyb@google.com</a>><br>
> Sent: Monday, July 13, 2015 9:59:10 PM<br>
> Subject: RFC: A plan for stateful alias analysis in LLVM<br>
><br>
><br>
><br>
> # Front matter # First, I want to emphasize that this is not a<br>
> short-term plan. This is a long-term plan. When I was looking at<br>
> refactoring the existing Alias Analysis infrastructure in LLVM in<br>
> ways that would break stateful AA, Hal Finkel asked me to figure out<br>
> how things would work with the new pass manager and make sure that<br>
> was sane.<br>
><br>
><br>
> This plan assumes the new pass manager. There is nothing deeply or<br>
> intrinsically tied to it, but the pieces will fit together naturally<br>
> there, and I don't see how to make them fit naturally in the<br>
> existing pass manager. I've not invested a lot of time in figuring<br>
> that out as it seems a sunk cost.<br>
><br>
><br>
> # Core ideas of what stateful AA should look like: #<br>
> 1) An alias analysis *is* an analysis pass, and if it needs to build<br>
> up state, it must do so for a "unit" of IR at a time (using the new<br>
> PM's terminology).<br>
> 2) Per-IR-unit invalidation from the pass manager is the primary<br>
> mechanism to clear out stale (and thus invalid) state from any alias<br>
> analysis. That means that most passes will not preserve AA by<br>
> default (unlike today).<br>
> 3) To be reasonably scalable, most alias analyses which retain state<br>
> will need to handle these invalidation events in a way that<br>
> gracefully degrades their results rather than wiping out all state.<br>
><br>
><br>
> I think everything in-tree but GlobalsModRef fits these requirements<br>
> already. Notably, this will work well for CFL, Andersen, or<br>
> generally any "intersection" based AA. A "union" based AA could work<br>
> here, but would have to do considerable work to be able to tolerate<br>
> updates that "invalidate" its state without simply forced<br>
> recomputation. I think this is a reasonable tradeoff as it preserves<br>
> our ability to experiment, while simplifying the update model.<br>
><br>
><br>
> The rest of this email contains much more detailed musing on this.<br>
> Feel free to stop reading when necessary.<br>
><br>
><br>
> The last section touches on the core functionality that would be<br>
> needed to support something like GlobalsModRef in its current form.<br>
> I'm much less confident in this part, so it's not part of my core<br>
> requirements above.<br>
><br>
><br>
> # Details about analysis passes and pass manager invalidation #<br>
> My thought is that an alias analysis pass in the new model would be<br>
> an analysis pass. It would produce an analysis result that contained<br>
> any state necessary to vend AA queries. This result would be cached<br>
> just like all the other analysis results are in the pass manager. It<br>
> would have the same invalidation rules too.<br>
><br>
><br>
> A really important consequence of this is that analysis results in<br>
> the new scheme get notified of invalidation events and can attempt<br>
> to update their internal state to *avoid* becoming invalid. AAs can<br>
> leverage this to do fast incremental updates to their internal<br>
> structures if appropriate.<br>
><br>
><br>
> An AA could even use ValueHandles now to automatically stay<br>
> up-to-date with a conservatively correct data structure, and just<br>
> drop all the invalidation requests. In fact, I suspect many stateful<br>
> AAs will take exactly this approach.<br>
><br>
><br>
> # How will users of AA information query it? #<br>
> This will work much like the normal analysis queries. I plan to<br>
> provide an alias analysis manager at each IR unit that will provide<br>
> a single query interface for code to use. This layer can then be<br>
> configured to query any AnalysisManager<T> for an IR unit T for the<br>
> relevant actual AliasAnalysis implementations.<br>
><br>
><br>
> The AA manager layer will be responsible for the delegation that is<br>
> currently done through chaining of AA implementations. It will also<br>
> be responsible for enforcing that queries at a particular layer<br>
> don't violate IR unit abstraction boundaries. For example, you<br>
> cannot query a FuntionAAManager for alias information of two Values<br>
> from two different functions.<br>
<br>
</div></div>One thing I'd like to clarify is what is responsible for 'requiring' the various alias-analysis pass, so that they'll be recomputed if they're invalidated. So if I have an AliasManager, and I've requested that it manage a BasicAA and an SCEVAA (for example), and something happens such that SCEVAA is invalidated, then before future AA queries are processed, the AliasManager is responsible for triggering the re-computation of SCEVAA as part of the chaining process (or before the first AA query). That's my expectation anyway; does that match this model?<br>
<br>
Thanks again,<br>
Hal<br>
<div class="HOEnZb"><div class="h5"><br>
><br>
><br>
> # Why GlobalsModRef doesn't fit, and what we could do about it #<br>
> There is a fundamental construct in GlobalsModRef that exists today,<br>
> and seems somewhat useful, but which doesn't fit the above: using a<br>
> global analysis of which memory locations are *not* escaped by any<br>
> function, in order to conclude that within a given function,<br>
> arguments, returns, and loads from globals cannot produce an<br>
> aliasing memory location. Thus, if you always directly index or<br>
> manipulate a global within a function, and it never escapes that<br>
> function (including through integer hacks), you know that some other<br>
> function can't produce an aliasing location by loading a pointer<br>
> from a global or receiving a pointer in an argument.<br>
><br>
><br>
> In *practice* this is actually totally reasonable. Passes don't run<br>
> around escaping pointers just because they feel like it. However, we<br>
> don't have a good way to really formally reason about such things.<br>
><br>
><br>
> My suggested way to reason about it is to define a new constraint on<br>
> transformation passes over an IR unit T (ie, Function, Module,<br>
> etc.). This constraint is that a pass may not *observably* escape a<br>
> pointer value P from the unit being transformed. Now, "observably"<br>
> is the key word here. The goal is to still allow fundamental<br>
> transformations like Reg2Mem and instrumentation passes. However,<br>
> the guarantee must be that the passes do not introduce new ways to<br>
> observe an escape of a pointer. Because any actual escapes cannot be<br>
> observed, it is safe for them to happen and for some other function<br>
> pass (for example) to transform based on the non-escaping property<br>
> computed prior to the transformation. I *think* this is a reasonable<br>
> model, but I've not really had enough time thinking about it to be<br>
> 100% certain.<br>
><br>
><br>
> With such a model, we could regain most of the power of GlobalsModRef<br>
> w.r.t. non-escaping pointers and interprocedural aliasing inference.<br>
> We would change it to be a two-pronged analysis. On one hand, a<br>
> local analysis would have to prove that one location came from a<br>
> module-level memory location (global) and the other location came<br>
> from some dynamic input to the function (argument, return, or a load<br>
> of memory that is def'ed outside the function), and then the other<br>
> hand would provide the interprocedural information about what global<br>
> memory locations were non-escaping.<br>
><br>
><br>
><br>
><br>
> Ok, those are all the thoughts I have currently about AA, and where<br>
> I'm headed. This should hopefully provide context for some of the<br>
> upcoming patches.<br>
><br>
><br>
> I'm also going to write a separate email about specific tactical<br>
> problems I've found with GlobalsModRef today (nothing to do with the<br>
> above theoretical problems) and how I plan to approach them.<br>
><br>
><br>
> Thanks,<br>
> -Chandler<br>
<br>
</div></div><span class="HOEnZb"><font color="#888888">--<br>
Hal Finkel<br>
Assistant Computational Scientist<br>
Leadership Computing Facility<br>
Argonne National Laboratory<br>
_______________________________________________<br>
LLVM Developers mailing list<br>
<a href="mailto:LLVMdev@cs.uiuc.edu">LLVMdev@cs.uiuc.edu</a>         <a href="http://llvm.cs.uiuc.edu" rel="noreferrer" target="_blank">http://llvm.cs.uiuc.edu</a><br>
<a href="http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev" rel="noreferrer" target="_blank">http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev</a><br>
</font></span></blockquote></div><br></div>