<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Tue, Mar 14, 2017 at 2:58 AM, Oliver Braunsdorf <span dir="ltr"><<a href="mailto:oliver.braunsdorf@tu-ilmenau.de" target="_blank">oliver.braunsdorf@tu-ilmenau.de</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><span class="gmail-"><br>
><br>
> On Sun, Mar 12, 2017 at 2:55 PM, Oliver Braunsdorf via llvm-dev<br>
</span><div><div class="gmail-h5">> <<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.org</a> <mailto:<a href="mailto:llvm-dev@lists.llvm.org">llvm-dev@lists.llvm.<wbr>org</a>>> wrote:<br>
><br>
>     > Perhaps by "value" you mean points-to set?<br>
><br>
>     Thats right! I meant the points-to set. Sorry I didn't mention that.<br>
>     I want to track back the value of the parameter to its definition -- an<br>
>     "assignment" which could be indirect through a pointer to the value used<br>
>     as the function argument.<br>
><br>
>     > Either way, flow-sensitivity can only give you more precise -- but still<br>
>     > not necessarily exact -- answers.<br>
><br>
>     I am aware of the inexactness of (flow-sensitive) alias analysis. Is<br>
>     there an exact way to accomplish this?<br>
><br>
><br>
> No, even the non-flow-sensitive version of the problem is statically<br>
> undecidable for may-alias, and not even recursively enumerable for<br>
> must-alias.<br>
> This is true even when all paths through the program are executable.<br>
><br>
> If you leave out recursive data structures, it is simply NP complete,<br>
> and thus, you could compute an exact answer, very expensively.<br>
><br>
> The TL;DR is that for most languages, there can be no exact aliasing<br>
> computation, only approximations.<br>
> See, e.g,  <a href="http://dl.acm.org/citation.cfm?doid=161494.161501" rel="noreferrer" target="_blank">http://dl.acm.org/citation.<wbr>cfm?doid=161494.161501</a><br>
> and <a href="http://dl.acm.org/citation.cfm?id=186025.186041" rel="noreferrer" target="_blank">http://dl.acm.org/citation.<wbr>cfm?id=186025.186041</a><br>
><br>
> (btw, it gets worse.  If you disallow recursive data structures, and<br>
> allow multiple levels of pointers, precise flow-sensitive may-alias is<br>
> NP-hard even when restricted to intraprocedural and *no* dynamic memory<br>
> allocation)<br>
><br>
<br>
</div></div>Okay, so thats is what I expected...no exact static alias analysis in<br>
polynomial time.<br>
We can only get (over-)approxmations for the may-alias problem by the<br>
algorithms implemented in LLVM. Thats fine for me. But all those<br>
implementations are flow-insensitive.<br></blockquote><div><br></div><div>Yes, because flow-sensitivity doesn't really buy much for the cost.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
So my original question was: Are there implementations of flow-sensitive<br>
algorithms that are usable in LLVM (through AA-Interface,<br>
MemorySSA/<wbr>MemoryDependenceAnalysis)?<br></blockquote><div>Nope.</div><div> </div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
Because my assumption is: (sparse) flow-sensitive algorithms can have<br>
nearly the same time requirements as flow-insensitive ones but are a<br>
little more precise.<br></blockquote><div><br></div><div>This assumption is very wrong, AFAIK :)</div><div>The best known precise flow-insensitive algorithms easily handle pretty much any  scale these days.</div><div><br></div><div>GCC's points-to is field-sensitive precise flow-insensitive, and it pretty much never shows up on profiles.</div><div>By contrast, the best sparse known sparse flow-sensitive analysis varies (quite wildly, in fact), is usually between 10x and 100x slower.</div><div>This is true even when, for example, parallelized on GPU's (see, e.g., <a href="http://dl.acm.org/citation.cfm?id=2555296">http://dl.acm.org/citation.cfm?id=2555296</a>).</div><div><br></div><div>If you only care about certain pointers, you would be better off with a demand-driven technique.</div><div><br></div><div>See, e.g., "Demand-Driven pointer analysis with Strong updates using value-flow refinement" </div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<span class="gmail-HOEnZb"><font color="#888888"><br>
<br>
-Oliver<br>
</font></span></blockquote></div><br></div></div>