<div dir="ltr"><br><div class="gmail_extra"><br><div class="gmail_quote">On Sun, Mar 12, 2017 at 2:55 PM, Oliver Braunsdorf via llvm-dev <span dir="ltr"><<a href="mailto:llvm-dev@lists.llvm.org" target="_blank">llvm-dev@lists.llvm.org</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-">> Perhaps by "value" you mean points-to set?<br>
<br>
</span>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>
<span class="gmail-"><br>
> Either way, flow-sensitivity can only give you more precise -- but still<br>
> not necessarily exact -- answers.<br>
<br>
</span>I am aware of the inexactness of (flow-sensitive) alias analysis. Is<br>
there an exact way to accomplish this?<br></blockquote><div><br></div><div>No, even the non-flow-sensitive version of the problem is statically undecidable for may-alias, and not even recursively enumerable for must-alias.</div><div>This is true even when all paths through the program are executable.</div><div><br></div><div>If you leave out recursive data structures, it is simply NP complete, and thus, you could compute an exact answer, very expensively.</div><div><br></div><div>The TL;DR is that for most languages, there can be no exact aliasing computation, only approximations.</div><div>See, e.g,  <a href="http://dl.acm.org/citation.cfm?doid=161494.161501">http://dl.acm.org/citation.cfm?doid=161494.161501</a> and <a href="http://dl.acm.org/citation.cfm?id=186025.186041">http://dl.acm.org/citation.cfm?id=186025.186041</a></div><div><br></div><div>(btw, it gets worse.  If you disallow recursive data structures, and allow multiple levels of pointers, precise flow-sensitive may-alias is NP-hard even when restricted to intraprocedural and *no* dynamic memory allocation)</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div></div></div></div>