On Sun, Mar 12, 2017 at 2:55 PM, Oliver Braunsdorf via llvm-dev < llvm-dev at lists.llvm.org> wrote:> > Perhaps by "value" you mean points-to set? > > Thats right! I meant the points-to set. Sorry I didn't mention that. > I want to track back the value of the parameter to its definition -- an > "assignment" which could be indirect through a pointer to the value used > as the function argument. > > > Either way, flow-sensitivity can only give you more precise -- but still > > not necessarily exact -- answers. > > I am aware of the inexactness of (flow-sensitive) alias analysis. Is > there an exact way to accomplish this? >No, even the non-flow-sensitive version of the problem is statically undecidable for may-alias, and not even recursively enumerable for must-alias. This is true even when all paths through the program are executable. If you leave out recursive data structures, it is simply NP complete, and thus, you could compute an exact answer, very expensively. The TL;DR is that for most languages, there can be no exact aliasing computation, only approximations. See, e.g, http://dl.acm.org/citation.cfm?doid=161494.161501 and http://dl.acm.org/citation.cfm?id=186025.186041 (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) -------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170312/eb9b389a/attachment.html>
Oliver Braunsdorf via llvm-dev
2017-Mar-14 09:58 UTC
[llvm-dev] flow-sensitive alias analysis
> > On Sun, Mar 12, 2017 at 2:55 PM, Oliver Braunsdorf via llvm-dev > <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > > > Perhaps by "value" you mean points-to set? > > Thats right! I meant the points-to set. Sorry I didn't mention that. > I want to track back the value of the parameter to its definition -- an > "assignment" which could be indirect through a pointer to the value used > as the function argument. > > > Either way, flow-sensitivity can only give you more precise -- but still > > not necessarily exact -- answers. > > I am aware of the inexactness of (flow-sensitive) alias analysis. Is > there an exact way to accomplish this? > > > No, even the non-flow-sensitive version of the problem is statically > undecidable for may-alias, and not even recursively enumerable for > must-alias. > This is true even when all paths through the program are executable. > > If you leave out recursive data structures, it is simply NP complete, > and thus, you could compute an exact answer, very expensively. > > The TL;DR is that for most languages, there can be no exact aliasing > computation, only approximations. > See, e.g, http://dl.acm.org/citation.cfm?doid=161494.161501 > and http://dl.acm.org/citation.cfm?id=186025.186041 > > (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) >Okay, so thats is what I expected...no exact static alias analysis in polynomial time. We can only get (over-)approxmations for the may-alias problem by the algorithms implemented in LLVM. Thats fine for me. But all those implementations are flow-insensitive. So my original question was: Are there implementations of flow-sensitive algorithms that are usable in LLVM (through AA-Interface, MemorySSA/MemoryDependenceAnalysis)? Because my assumption is: (sparse) flow-sensitive algorithms can have nearly the same time requirements as flow-insensitive ones but are a little more precise. -Oliver
On Tue, Mar 14, 2017 at 2:58 AM, Oliver Braunsdorf < oliver.braunsdorf at tu-ilmenau.de> wrote:> > > > > On Sun, Mar 12, 2017 at 2:55 PM, Oliver Braunsdorf via llvm-dev > > <llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>> wrote: > > > > > Perhaps by "value" you mean points-to set? > > > > Thats right! I meant the points-to set. Sorry I didn't mention that. > > I want to track back the value of the parameter to its definition -- > an > > "assignment" which could be indirect through a pointer to the value > used > > as the function argument. > > > > > Either way, flow-sensitivity can only give you more precise -- but > still > > > not necessarily exact -- answers. > > > > I am aware of the inexactness of (flow-sensitive) alias analysis. Is > > there an exact way to accomplish this? > > > > > > No, even the non-flow-sensitive version of the problem is statically > > undecidable for may-alias, and not even recursively enumerable for > > must-alias. > > This is true even when all paths through the program are executable. > > > > If you leave out recursive data structures, it is simply NP complete, > > and thus, you could compute an exact answer, very expensively. > > > > The TL;DR is that for most languages, there can be no exact aliasing > > computation, only approximations. > > See, e.g, http://dl.acm.org/citation.cfm?doid=161494.161501 > > and http://dl.acm.org/citation.cfm?id=186025.186041 > > > > (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) > > > > Okay, so thats is what I expected...no exact static alias analysis in > polynomial time. > We can only get (over-)approxmations for the may-alias problem by the > algorithms implemented in LLVM. Thats fine for me. But all those > implementations are flow-insensitive. >Yes, because flow-sensitivity doesn't really buy much for the cost.> So my original question was: Are there implementations of flow-sensitive > algorithms that are usable in LLVM (through AA-Interface, > MemorySSA/MemoryDependenceAnalysis)? >Nope.> Because my assumption is: (sparse) flow-sensitive algorithms can have > nearly the same time requirements as flow-insensitive ones but are a > little more precise. >This assumption is very wrong, AFAIK :) The best known precise flow-insensitive algorithms easily handle pretty much any scale these days. GCC's points-to is field-sensitive precise flow-insensitive, and it pretty much never shows up on profiles. By contrast, the best sparse known sparse flow-sensitive analysis varies (quite wildly, in fact), is usually between 10x and 100x slower. This is true even when, for example, parallelized on GPU's (see, e.g., http://dl.acm.org/citation.cfm?id=2555296). If you only care about certain pointers, you would be better off with a demand-driven technique. See, e.g., "Demand-Driven pointer analysis with Strong updates using value-flow refinement"> > -Oliver >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20170314/71236363/attachment.html>