Svadev mailing list

[John Criswell <criswell AT illinois.edu>]

On 2/18/11 11:04 PM, Tarek Chammah wrote:
> Hi Arushi,
>
> buildDSNodeEquivs is actually not my method.  It is from the SAFECode
> project that John pointed me to.  It ensures DSA TD points-to

FWIW, buildDSNodeEquivs is not from SAFECode.  It is from the Expression 
Merger code that Will wrote for Capsaicin (an internal research project 
whose source code we have not released yet).

Tarek, just so you know, I'd like to make the buildDSNodeEquivs 
functionality a separate DSA pass that clients can use to more easily 
interpret the DSA results.  If you'd like to do that and contribute it 
to the project, please let me know.  I will probably do it myself 
eventually if no one else does, but I'm working on other things at the 
moment and haven't had time to do it.

Now on to the question...

> information is correct interprocedurally by matching up DSNodes
> between the callers and callees and placing them into equivalence
> classes where everything within an EC is assumed to alias.  You
> probably have it as part of the code on your local machine.  Though I
> think its results are suspect due to the repeated DSNode information
> within an EC.  That is my issue.

Ah.  I think I understand what your concern is now, Tarek.  You are 
worried that what you are seeing below when you print out the DSNodes 
means that a single SSA value has been mapped to multiple DSNodes.  Is 
this correct?

The strings below are not printing out the mapping between SSA values 
and DSNodes.  That information is not even contained within DSNode 
objects.  Rather, each DSGraph object has an object called the 
ScalarMap.  The ScalarMap tracks the mapping of SSA values to DSNodes.  
If you want to see which SSA values points to which DSNode, you'll need 
to print out the DSGraphs by using opt's -analyze option when running 
DSA (it should create one GraphViz .dot file for every DSGraph).

Looking at the code that prints DSNodes, I believe it looks to see if 
the DSNode represents one or more global variables and prints the leader 
of the global EC for that SSA value (remember that DSA puts globals into 
equivalence classes to reduce the size of the ScalarMap in each 
DSGraph).  So, I believe what the @G2 in the DSNodes is saying is that 
the DSNode represents the global variable G2 (i.e., the DSNode 
represents the global value pointed to by @G2) and that G2's global EC 
contains 1 global.

Arushi, does the above sound correct?

So, in short, if you want to see if buildDSNodeEquivs is working 
properly, print the DSGraphs to understand what SSA values are pointing 
to which DSNodes and then see if the right DSNodes are put into the same 
equivalence classes by buildsDSNodeEquivs.  Don't look at DSNodes to see 
which SSA values are pointing to them because the DSNode doesn't have 
that information.

-- John T.

> Regards,
>
> Tarek
>
>
> On Fri, Feb 18, 2011 at 11:13 PM, Arushi 
> Aggarwal<arushi987 AT gmail.com>
>   wrote:
> > Hi,
> > I am not sure what your buildDSNodeEquivs method is. If you can tell me that
> > I can try
> > looking at this.
> > Arushi
> >
> > On Fri, Feb 18, 2011 at 10:10 PM, Tarek 
> > Chammah<tchammah AT uwaterloo.ca>
> > wrote:
> > > Hi, this issue is possibly a blocker for me.  I'm utilizing DSA to
> > > garner points-to information.  After the top down pass is run and the
> > > buildDSNodeEquivs method is executed to place DSNodes between callers
> > > and callees into their equivalence classes I get rather strange
> > > output.  Using a simple test I dump the nodes in the resulting
> > > equivalence classes.  What I get is a pair of distinct nodes in the
> > > ECs that contain the same program variable/value location information.
> > >   I don't understand why this information is repeated.
> > >
> > > Eg. I get this, two ECs each containing a pair with repeated
> > > information (about G2 and the string constant):
> > > Node0x1008870 [shape=record,shape=Mrecord,label="{i32: 
> > > GR\n@G2
> > >  + 1
> > > EC\n|{<s0>|<s1>|<s2>|<s3>}}"];
> > > Node0xff4950 [shape=record,shape=Mrecord,label="{i32: 
> > > GR\n@G2
> > >  + 1
> > > EC\n|{<s0>|<s1>|<s2>|<s3>}}"];
> > >
> > > Node0x1008af0 [shape=record,shape=Mrecord,label="{i8 array:
> > > GR\n@.str\n|{<s0>}}"];
> > > Node0xff4d50 [shape=record,shape=Mrecord,label="{i8 array:
> > > GR\n@.str\n|{<s0>}}"];
> > >
> > > For this sample program:
> > > #include<stdio.h>
> > >
> > > int G1 = 4, G2 = 3;
> > > int *XX, *YY;
> > >
> > > int main() {
> > >        XX =&G1;
> > >        YY = XX;
> > >        YY =&G2;
> > >        XX =&G2;
> > >        if (*XX>*YY) printf("Not possible!\n");
> > >        return 0;
> > > }
> > >
> > >
> > > Thanks,
> > >
> > > Tarek
> _______________________________________________
> svadev mailing list
> svadev AT cs.uiuc.edu
> http://lists.cs.uiuc.edu/mailman/listinfo/svadev