'Re: [Soot-list] Difference between slicing and reaching definition'

[prev in list] [next in list] [prev in thread] [next in thread] 

List:       soot-list
Subject:    Re: [Soot-list] Difference between slicing and reaching definition
From:       Elena Sherman <elenasherman () boisestate ! edu>
Date:       2013-06-22 17:07:14
Message-ID: CAB4=7K3uRPXJtBsKVHTMY_tpsXhSYt_X80rs+peX+PAbnvpKJQ () mail ! gmail ! com
[Download RAW message or body]

[Attachment #2 (multipart/alternative)]

Zeinab,

Consider the semantically equivalent example from the wiki page on slicing

1: int i=0;
2: int sum = 0;
3: int product = 1;
4: while(i < N) {
5:  sum = sum + i;
6:  product = product * i;
7:  i++;
  }
8: write(sum);
9: write(product);

Reaching definition analysis, i.e., reaching assignment analysis, for each
line in the program above produces the set of assignments that may reach
that line, which is computed by traversing the program's control flow graph
forward. So for the example above we get:

1: {}
2: {1:i=0}
3: {1:i=0, 2:sum=0}
4: {1:i=0, 2:sum=0, 3:product=1, 5:sum=sum+1, 6:product=product * i, 7:i++}
5: {1:i=0, 2:sum=0, 3:product=1, 5:sum=sum+1, 6:product=product * i, 7:i++}
6: {1:i=0, 3:product=1, 5:sum=sum+1, 6:product=product * i, 7:i++}
7: {1:i=0, 5:sum=sum+1, 6:product=product * i, 7:i++}
8: {1:i=0, 2:sum=0, 3:product=1, 5:sum=sum+1, 6:product=product * i, 7:i++}
9: {1:i=0, 2:sum=0, 3:product=1, 5:sum=sum+1, 6:product=product * i, 7:i++}

However if you do slicing for line 8 you will get the following set of
statements: {1:, 2:, 4:, 5:, 7:, 8:}, i.e.,

1: int i=0;
2: int sum = 0;

4: while(i < N) {
5:  sum = sum + i;

7:  i++;
  }
8: write(sum); // some algorithms will omit that line

Can we use the result of RD to get that slice? So if we extract only those
assignments that reached line 8 and also used in that line we get

8: {2:sum=0, 5:sum=sum+1}

Which is a strict subset of the slice statement. As we can see we need to
track not only data dependencies but also control dependencies, i.e., while
(i < N), to get all statements in the slice. Moreover, we also need to
propagate those dependencies, i.e., if 8: depends on 4: then we need to
infer that 8: also depends on 1: because 4: depends on it.

So the result of RD (plus the statement 8 itself) can be used as the
starting point for slicing computation. However, I don't believe this is
how it is done. You just traverse the control flow graph of the program
backward from the line of interest, i.e., line 8, looking for data and
control dependencies of the variables used on that line.

Can we use slicing information to get the set of RD for that statement?
Obviously not, i.e., slice does not contain many statements that RD
computes for line 8, e.g., {3:product=1, 6:product=product * i} are not in
the slice and there is no way to infer from the slice.

So we can use the result of RD to compute a slice, but we cannot use the
result of the slice to compute RD.

Hopefully it makes sense.

Elena

On Sat, Jun 22, 2013 at 4:42 AM, Zeinab Lashkaripour <lashkaripour@yahoo.com
> wrote:

> Is there no one to guide me?
> Still looking forward to hearing from you.
>
> Regards
>
>   ------------------------------
>  *From:* Zeinab Lashkaripour <lashkaripour@yahoo.com>
> *To:* "soot-list@sable.mcgill.ca" <soot-list@sable.mcgill.ca>
> *Sent:* Tuesday, June 18, 2013 12:56 AM
> *Subject:* [Soot-list] Difference between slicing and reaching definition
>
> Hi everyone,
>
> I have a question and would be very grateful if anyone guided me.
>
> Reaching definition is a type of DFA that we compute the definitions that
> can reach a point p in our program. On the other hand we have slicing that
> I think that it is some how on an upper level in comparison to DFA, but not
> sure? In slicing we extract the part of the program that is of our interest
> according to the slicing criterion.
>
> What is the difference between RD and slicing? In both conditions we
> extract the parts of the program that we need. Maybe the difference is in
> the fact that we only consider assignments in RD while in slicing its not
> like that?
> Do they have any similarities except the ones mentioned?
>
> Regards,
> Zeinab
>
> _______________________________________________
> Soot-list mailing list
> Soot-list@sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
>
>
> _______________________________________________
> Soot-list mailing list
> Soot-list@sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
>

[Attachment #5 (text/html)]

<div dir="ltr"><div>Zeinab,</div><div><br></div><div>Consider the semantically \
equivalent example from the wiki page on slicing</div><div><br></div><div>1: int \
i=0;</div><div>2: int sum = 0;</div><div>3: int product = 1;</div> <div>4: while(i \
&lt; N) {</div><div>5:  sum = sum + i;</div><div>6:  product = product * \
i;</div><div>7:  i++;</div><div>  }</div><div>8: write(sum);</div><div>9: \
write(product);</div><div><br></div><div>Reaching definition analysis, i.e., reaching \
assignment analysis, for each line in the program above produces the set of \
assignments that may reach that line, which is computed by traversing the \
program&#39;s control flow graph forward. So for the example above we get:</div> \
<div><br></div><div>1: {}</div><div>2: {1:i=0}</div><div>3: {1:i=0, \
2:sum=0}</div><div>4: {1:i=0, 2:sum=0, 3:product=1, 5:sum=sum+1, 6:product=product * \
i, 7:i++}</div><div>5: {1:i=0, 2:sum=0, 3:product=1, 5:sum=sum+1, 6:product=product * \
i, 7:i++}</div> <div>6: {1:i=0, 3:product=1, 5:sum=sum+1, 6:product=product * i, \
7:i++}</div><div>7: {1:i=0, 5:sum=sum+1, 6:product=product * i, 7:i++}</div><div>8: \
{1:i=0, 2:sum=0, 3:product=1, 5:sum=sum+1, 6:product=product * i, 7:i++}</div> \
<div>9: {1:i=0, 2:sum=0, 3:product=1, 5:sum=sum+1, 6:product=product * i, \
7:i++}</div><div><br></div><div>However if you do slicing for line 8 you will get the \
following set of statements: {1:, 2:, 4:, 5:, 7:, 8:}, i.e., </div> \
<div><br></div><div>1: int i=0;</div><div>2: int sum = 0;</div><div><br></div><div>4: \
while(i &lt; N) {</div><div>5:  sum = sum + i;</div><div><br></div><div>7:  \
i++;</div><div>  }</div><div>8: write(sum); // some algorithms will omit that \
line</div> <div><br></div><div><br></div><div>Can we use the result of RD to get that \
slice? So if we extract only those assignments that reached line 8 and also used in \
that line we get </div><div><br></div><div>8: {2:sum=0, 5:sum=sum+1}</div> \
<div><br></div><div>Which is a strict subset of the slice statement. As we can see we \
need to track not only data dependencies but also control dependencies, i.e., while \
(i &lt; N), to get all statements in the slice. Moreover, we also need to propagate \
those dependencies, i.e., if 8: depends on 4: then we need to infer that 8: also \
depends on 1: because 4: depends on it.</div> <div><br></div><div>So the result of RD \
(plus the statement 8 itself) can be used as the starting point for slicing \
computation. However, I don&#39;t believe this is how it is done. You just traverse \
the control flow graph of the program backward from the line of interest, i.e., line \
8, looking for data and control dependencies of the variables used on that \
line.</div> <div><br></div><div>Can we use slicing information to get the set of RD \
for that statement? Obviously not, i.e., slice does not contain many statements that \
RD computes for line 8, e.g., {3:product=1, 6:product=product * i} are not in the \
slice and there is no way to infer from the slice. </div> <div><br></div><div>So we \
can use the result of RD to compute a slice, but we cannot use the result of the \
slice to compute RD.</div><div><br></div><div>Hopefully it makes \
sense.</div><div><br></div><div>Elena</div></div> <div \
class="gmail_extra"><br><br><div class="gmail_quote">On Sat, Jun 22, 2013 at 4:42 AM, \
Zeinab Lashkaripour <span dir="ltr">&lt;<a href="mailto:lashkaripour@yahoo.com" \
target="_blank">lashkaripour@yahoo.com</a>&gt;</span> wrote:<br> <blockquote \
class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc \
solid;padding-left:1ex"><div><div style="font-size:12pt;font-family:times new \
roman,new york,times,serif"><div><span>Is there no one to guide me?</span></div> <div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"><span>Still looking forward to hearing from \
you.</span></div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"> <br><span></span></div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"><span>Regards<br></span></div><div><br></div>  <div \
style="font-family:times new roman,new york,times,serif;font-size:12pt">  <div \
style="font-family:times new roman,new york,times,serif;font-size:12pt"> <div \
dir="ltr"> <hr size="1">  <font face="Arial"> <b><span \
style="font-weight:bold">From:</span></b> Zeinab Lashkaripour &lt;<a \
href="mailto:lashkaripour@yahoo.com" \
target="_blank">lashkaripour@yahoo.com</a>&gt;<br> <b><span \
style="font-weight:bold">To:</span></b> &quot;<a \
href="mailto:soot-list@sable.mcgill.ca" \
target="_blank">soot-list@sable.mcgill.ca</a>&quot; &lt;<a \
href="mailto:soot-list@sable.mcgill.ca" \
target="_blank">soot-list@sable.mcgill.ca</a>&gt; <br>  <b><span \
style="font-weight:bold">Sent:</span></b> Tuesday, June 18, 2013 12:56 AM<br> \
<b><span style="font-weight:bold">Subject:</span></b> [Soot-list] Difference between \
slicing and reaching definition<br> </font> </div>  <div><br><div><div><div \
style="font-size:12pt;font-family:times new roman,new york,times,serif"><div>Hi \
everyone,</div><div><br></div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"> I have a question and would be very grateful if \
anyone guided me.</div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"><br></div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"> Reaching definition is a type of DFA that we compute \
the definitions that can reach a point p in our program. On the other hand we have \
slicing that I think that it is some how on an upper level in comparison to DFA, but \
not sure? In slicing we extract the part  of the program that is of our interest \
according to the slicing criterion.</div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"><br></div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif">  What is the difference between RD and slicing? In \
both conditions we extract the parts of the program that we need. Maybe the \
difference is in the fact that we only consider assignments in RD while in slicing \
its not like that?</div> <div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif">Do they have any similarities except the ones \
mentioned?<br></div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"> <br></div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif">Regards,</div><div \
style="font-style:normal;font-size:16px;background-color:transparent;font-family:times \
new roman,new york,times,serif"> \
Zeinab</div></div></div></div><br>_______________________________________________<br>Soot-list \
mailing list<br><a href="mailto:Soot-list@sable.mcgill.ca" \
target="_blank">Soot-list@sable.mcgill.ca</a><br><a \
href="http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list" \
target="_blank">http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list</a><br> \
<br><br></div> </div> </div>  \
</div></div><br>_______________________________________________<br> Soot-list mailing \
list<br> <a href="mailto:Soot-list@sable.mcgill.ca">Soot-list@sable.mcgill.ca</a><br>
<a href="http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list" \
target="_blank">http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list</a><br> \
<br></blockquote></div><br></div>

_______________________________________________
Soot-list mailing list
Soot-list@sable.mcgill.ca
http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list

[prev in list] [next in list] [prev in thread] [next in thread] 