problem with using DSA for a side-effect analysis

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|

problem with using DSA for a side-effect analysis

Zvonimir
Hi,

I am using DSA in the project I am working on. Currently, I am working
on automatic inference of function frame conditions to be used in the
modular verification tool for C I am developing. Here is a part of my
algorithm I am not exactly sure how to do:

Let's say function foo calls function bar, and they have corresponding
DSGraphs DSG_foo and DSG_bar.
Function bar modifies some memory locations that correspond to a set
of DS nodes M from DSG_bar. I would like to map this set M onto the
corresponding nodes (if they exist) in the DSG_foo, i.e. I would like
to find out which nodes in the DSG_foo are potentially modified by a
call to bar.

Currently I am using DSGraph::computeNodeMapping to do the task, but I
am not sure if that's the way to go....

Any suggestions would be greatly appreciated!

Thanks!
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: problem with using DSA for a side-effect analysis

Andrew Lenharth
On Thu, Apr 3, 2008 at 12:29 PM, Zvonimir Rakamaric <[hidden email]> wrote:
>  Currently I am using DSGraph::computeNodeMapping to do the task, but I
>  am not sure if that's the way to go....

I believe that is the correct function to use.

Andrew
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: problem with using DSA for a side-effect analysis

Vikram S. Adve-2
Andrew, there used to be some code to compute the ModRef behavior of  
functions using DS graphs.  Does that code  still exist in svn?  What  
Zvonimir is asking is essentially that, although perhaps he needs it  
as DS nodes explicitly rather than via the generic queries in the  
AliasAnalysis interface.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/



On Apr 3, 2008, at 12:45 PM, Andrew Lenharth wrote:

> On Thu, Apr 3, 2008 at 12:29 PM, Zvonimir Rakamaric <[hidden email]
> > wrote:
>> Currently I am using DSGraph::computeNodeMapping to do the task,  
>> but I
>> am not sure if that's the way to go....
>
> I believe that is the correct function to use.
>
> Andrew
> _______________________________________________
> LLVM Developers mailing list
> [hidden email]         http://llvm.cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev

_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: problem with using DSA for a side-effect analysis

Andrew Lenharth
The ModRef info is directly available through the alias analysis dsa
client, and certainly easier to use.

Andrew

On Thu, Apr 3, 2008 at 1:28 PM, Vikram S. Adve <[hidden email]> wrote:

> Andrew, there used to be some code to compute the ModRef behavior of
>  functions using DS graphs.  Does that code  still exist in svn?  What
>  Zvonimir is asking is essentially that, although perhaps he needs it
>  as DS nodes explicitly rather than via the generic queries in the
>  AliasAnalysis interface.
>
>  --Vikram
>  http://www.cs.uiuc.edu/~vadve
>  http://llvm.org/
>
>
>
>
>
>  On Apr 3, 2008, at 12:45 PM, Andrew Lenharth wrote:
>
>  > On Thu, Apr 3, 2008 at 12:29 PM, Zvonimir Rakamaric <[hidden email]
>  > > wrote:
>  >> Currently I am using DSGraph::computeNodeMapping to do the task,
>  >> but I
>  >> am not sure if that's the way to go....
>  >
>  > I believe that is the correct function to use.
>  >
>  > Andrew
>
>
> > _______________________________________________
>  > LLVM Developers mailing list
>  > [hidden email]         http://llvm.cs.uiuc.edu
>  > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
>  _______________________________________________
>  LLVM Developers mailing list
>  [hidden email]         http://llvm.cs.uiuc.edu
>  http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
>
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: problem with using DSA for a side-effect analysis

Zvonimir
In reply to this post by Zvonimir
Thanks guys!

I was looking into ModRef before, but I don't think that's exactly
what I need. ModRef API call getModRefInfo requires a Value to be
passed to it. However, some memory location M (which is a <DSNode,
offset> pair) visible to the caller can be modified in the callee
without any Value in the caller actually pointing to that location. I
also need to capture those...

I would need a call similar to getModRefInfo, just where second
parameter is not a Value, but a DSNodeHandle pointing to the memory
location in the caller whose ModRef status I would like to find out.
Do you maybe have anything similar to that?

-- Zvonimir


>  The ModRef info is directly available through the alias analysis dsa
>  client, and certainly easier to use.
>
>  Andrew
>
>  On Thu, Apr 3, 2008 at 1:28 PM, Vikram S. Adve <[hidden email]> wrote:
>  > Andrew, there used to be some code to compute the ModRef behavior of
>  >  functions using DS graphs.  Does that code  still exist in svn?  What
>  >  Zvonimir is asking is essentially that, although perhaps he needs it
>  >  as DS nodes explicitly rather than via the generic queries in the
>  >  AliasAnalysis interface.
>  >
>  >  --Vikram
>  >  http://www.cs.uiuc.edu/~vadve
>  >  http://llvm.org/
>  >
>  >
>  >
>  >
>  >
>  >  On Apr 3, 2008, at 12:45 PM, Andrew Lenharth wrote:
>  >
>  >  > On Thu, Apr 3, 2008 at 12:29 PM, Zvonimir Rakamaric <[hidden email]
>  >  > > wrote:
>  >  >> Currently I am using DSGraph::computeNodeMapping to do the task,
>  >  >> but I
>  >  >> am not sure if that's the way to go....
>  >  >
>  >  > I believe that is the correct function to use.
>  >  >
>  >  > Andrew
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: problem with using DSA for a side-effect analysis

Vikram S. Adve-2
What I was hoping is that the internal implementation of the ModRef API in DSAA has that kind of information.  It needs to do exactly what you described with computeNodeMapping to implement the AliasAnalysis interface.

Andrew, my question was whether the ModRef info is computed by the -dsaa implementation.  If so, that code might be reusable (either directly, by exposing it through a separate interface) or indirectly (by duplicating) for what Zvonimir wants.

On Apr 3, 2008, at 4:53 PM, Zvonimir Rakamaric wrote:

Thanks guys!

I was looking into ModRef before, but I don't think that's exactly
what I need. ModRef API call getModRefInfo requires a Value to be
passed to it. However, some memory location M (which is a <DSNode,
offset> pair) visible to the caller can be modified in the callee
without any Value in the caller actually pointing to that location. I
also need to capture those...

I would need a call similar to getModRefInfo, just where second
parameter is not a Value, but a DSNodeHandle pointing to the memory
location in the caller whose ModRef status I would like to find out.
Do you maybe have anything similar to that?

-- Zvonimir


The ModRef info is directly available through the alias analysis dsa
client, and certainly easier to use.

Andrew

On Thu, Apr 3, 2008 at 1:28 PM, Vikram S. Adve <[hidden email]> wrote:
Andrew, there used to be some code to compute the ModRef behavior of
functions using DS graphs.  Does that code  still exist in svn?  What
Zvonimir is asking is essentially that, although perhaps he needs it
as DS nodes explicitly rather than via the generic queries in the
AliasAnalysis interface.

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/





On Apr 3, 2008, at 12:45 PM, Andrew Lenharth wrote:

On Thu, Apr 3, 2008 at 12:29 PM, Zvonimir Rakamaric <[hidden email]
wrote:
Currently I am using DSGraph::computeNodeMapping to do the task,
but I
am not sure if that's the way to go....

I believe that is the correct function to use.

Andrew
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev


_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: problem with using DSA for a side-effect analysis

Andrew Lenharth
In reply to this post by Zvonimir
On Thu, Apr 3, 2008 at 4:53 PM, Zvonimir Rakamaric <[hidden email]> wrote:

> Thanks guys!
>
>  I was looking into ModRef before, but I don't think that's exactly
>  what I need. ModRef API call getModRefInfo requires a Value to be
>  passed to it. However, some memory location M (which is a <DSNode,
>  offset> pair) visible to the caller can be modified in the callee
>  without any Value in the caller actually pointing to that location. I
>  also need to capture those...
>
>  I would need a call similar to getModRefInfo, just where second
>  parameter is not a Value, but a DSNodeHandle pointing to the memory
>  location in the caller whose ModRef status I would like to find out.
>  Do you maybe have anything similar to that?

I haven't looked at the dsaaa implementation for quite a while, but
that would be the place to start.  If the DSNodeHandle corrosponds to
anything in the current function, you could just use that as a value,
but it won't always.  Eitherway, seeing how DSAaa does this would be
the best code to start from.

Andrew
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: problem with using DSA for a side-effect analysis

Zvonimir
On Fri, Apr 4, 2008 at 2:38 AM, Andrew Lenharth <[hidden email]> wrote:

> On Thu, Apr 3, 2008 at 4:53 PM, Zvonimir Rakamaric <[hidden email]> wrote:
>  > Thanks guys!
>  >
>  >  I was looking into ModRef before, but I don't think that's exactly
>  >  what I need. ModRef API call getModRefInfo requires a Value to be
>  >  passed to it. However, some memory location M (which is a <DSNode,
>  >  offset> pair) visible to the caller can be modified in the callee
>  >  without any Value in the caller actually pointing to that location. I
>  >  also need to capture those...
>  >
>  >  I would need a call similar to getModRefInfo, just where second
>  >  parameter is not a Value, but a DSNodeHandle pointing to the memory
>  >  location in the caller whose ModRef status I would like to find out.
>  >  Do you maybe have anything similar to that?
>
>  I haven't looked at the dsaaa implementation for quite a while, but
>  that would be the place to start.  If the DSNodeHandle corrosponds to
>  anything in the current function, you could just use that as a value,
>  but it won't always.  Eitherway, seeing how DSAaa does this would be
>  the best code to start from.

Thanks!
I already had most of the code for it already written, staring at the
DSAaa helped me to fix a couple of problems. It seems to be working
perfectly now...
Btw, apart from the difference I already mentioned, DSAaa modref is
also not so good fit for me because it is not field-sensitive...

-- Zvonimir
_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
Reply | Threaded
Open this post in threaded view
|

Re: problem with using DSA for a side-effect analysis

Vikram S. Adve-2
> Thanks!
> I already had most of the code for it already written, staring at the
> DSAaa helped me to fix a couple of problems. It seems to be working
> perfectly now...
> Btw, apart from the difference I already mentioned, DSAaa modref is
> also not so good fit for me because it is not field-sensitive...

This is actually relatively easy to fix, at least for the nodes that  
are type-homogeneous.  You just need to change the R/W flags to be one  
flag per field instead of one flag per node, and make the  
corresponding changes to compute them (on loads and stores), and  
propagate them (on node merges).

--Vikram
http://www.cs.uiuc.edu/~vadve
http://llvm.org/



_______________________________________________
LLVM Developers mailing list
[hidden email]         http://llvm.cs.uiuc.edu
http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev