llvm dev - Mar 2017 - flow-sensitive alias analysis

Perhaps by "value" you mean points-to set?

Either way, flow-sensitivity can only give you more precise -- but still
not necessarily exact -- answers.

Yours,
Andrey
==Compiler Architect
NXP


On Fri, Mar 10, 2017 at 6:39 PM, Flamedoge via llvm-dev <
llvm-dev at lists.llvm.org> wrote:
> > For a given argument of a call instruction in the cfg: Where does the
> value of the argument come from at the call site?
>
> GVN may tell you the values. I'm not sure why you would need flow
> sensitive alias analysis for this.
>
> -Kevin
>
> On Fri, Mar 10, 2017 at 8:40 AM, Oliver Braunsdorf via llvm-dev <
> llvm-dev at lists.llvm.org> wrote:
>
>> Hi,
>>
>> I am looking for some flow-sensitive (context-insensitive) alias
>> analysis algorithm implemented in LLVM. (I use LLVM 3.9, hope to switch
>> to 4.0 soon.)
>> As far as I know, none of the built-in analysis (basicAA,
>> globals-modref, andersAA, etc.) is intended to be flow-sensitive. So I
>> searched and came across these two
>>
>> 1. https://github.com/unsw-corg/SVF by Yulei Sui (for LLVM 3.8)
>> 2. http://www.cs.ucsb.edu/~benh/research/downloads.html by Ben
Hardekopf
>> (for LLVM 2.5)
>>
>> Are there other implementations which use the AA-Interface?
>>
>> Giving a little context, I need some functionality in LLVM that answers
>> the following question.
>> For a given argument of a call instruction in the cfg: Where does the
>> value of the argument come from at the call site?
>>
>> So I guess I need a flow-sensitive alias analysis, right?
>> Could someone please guide me a little?
>>
>>
>> Thank you,
>>
>> Oliver
>> _______________________________________________
>> LLVM Developers mailing list
>> llvm-dev at lists.llvm.org
>> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>>
>
>
> _______________________________________________
> LLVM Developers mailing list
> llvm-dev at lists.llvm.org
> http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20170311/899c4af0/attachment.html>

> 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?

Thanks for your replies!
Oliver
> 
> Yours,
> Andrey
> ==> Compiler Architect
> NXP
> 
> 
> On Fri, Mar 10, 2017 at 6:39 PM, Flamedoge via llvm-dev
> <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
> 
>     > For a given argument of a call instruction in the cfg: Where does
the
>     value of the argument come from at the call site?
> 
>     GVN may tell you the values. I'm not sure why you would need flow
>     sensitive alias analysis for this.
> 
>     -Kevin
> 
>     On Fri, Mar 10, 2017 at 8:40 AM, Oliver Braunsdorf via llvm-dev
>     <llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>> wrote:
> 
>         Hi,
> 
>         I am looking for some flow-sensitive (context-insensitive) alias
>         analysis algorithm implemented in LLVM. (I use LLVM 3.9, hope to
>         switch
>         to 4.0 soon.)
>         As far as I know, none of the built-in analysis (basicAA,
>         globals-modref, andersAA, etc.) is intended to be
>         flow-sensitive. So I
>         searched and came across these two
> 
>         1. https://github.com/unsw-corg/SVF
>         <https://github.com/unsw-corg/SVF> by Yulei Sui (for LLVM
3.8)
>         2. http://www.cs.ucsb.edu/~benh/research/downloads.html
>         <http://www.cs.ucsb.edu/~benh/research/downloads.html> by Ben
>         Hardekopf
>         (for LLVM 2.5)
> 
>         Are there other implementations which use the AA-Interface?
> 
>         Giving a little context, I need some functionality in LLVM that
>         answers
>         the following question.
>         For a given argument of a call instruction in the cfg: Where
>         does the
>         value of the argument come from at the call site?
> 
>         So I guess I need a flow-sensitive alias analysis, right?
>         Could someone please guide me a little?
> 
> 
>         Thank you,
> 
>         Oliver
>         _______________________________________________
>         LLVM Developers mailing list
>         llvm-dev at lists.llvm.org <mailto:llvm-dev at
lists.llvm.org>
>         http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>         <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
> 
> 
>     _______________________________________________
>     LLVM Developers mailing list
>     llvm-dev at lists.llvm.org <mailto:llvm-dev at lists.llvm.org>
>     http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev
>     <http://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev>
> 
>

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>

> On 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?
Determining the exact behavior of a program (which would be necessary to know
the exact definition of a value) is undecidable (see halting problem etc.). So
all you can hope for are approximations.

- Matthias