[Soot-list] Difference between slicing and reaching definition

[Elena Sherman]

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 at yahoo.com
> wrote:

> Is there no one to guide me?
> Still looking forward to hearing from you.
>
> Regards
>
>   ------------------------------
>  *From:* Zeinab Lashkaripour <lashkaripour at yahoo.com>
> *To:* "soot-list at sable.mcgill.ca" <soot-list at 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 at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
>
>
> _______________________________________________
> Soot-list mailing list
> Soot-list at sable.mcgill.ca
> http://mailman.cs.mcgill.ca/mailman/listinfo/soot-list
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.mcgill.ca/pipermail/soot-list/attachments/20130622/5fb06bcd/attachment.html