Svadev mailing list

[Tarek Chammah <tchammah AT uwaterloo.ca>]

On Sat, Feb 19, 2011 at 12:19 PM, John Criswell 
<criswell AT illinois.edu>
 wrote:
> 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.

Yeah that's not a problem.  Though I have 2.6 (with modifications)
currently I can port it to mainline.

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

Yes that was a concern.

> 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).

Okay thanks.  I had it output the .dot files, and corresponding .pngs
(attached), and things appear to look fine.

> 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).

Ok I think I understand now what's happening in this instance.  I was
dumping all the DSNodes within all the ECs.  If the dump prints the
leader of the EC this explanation works for G2 though I'm not sure why
the string constant information should be duplicated as it's the only
value in its EC.

>  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

Attachment: td.GlobalsGraph.dot
Description: Binary data

Attachment: td.GlobalsGraph.png
Description: PNG image

Attachment: td.main.dot
Description: Binary data

Attachment: td.main.png
Description: PNG image