4
$\begingroup$

I was going through the concept of reaching definitions from the red dragon book.

The authors define reaching definitions as follows:

Definition: We say a definition $d$ reaches a point $p$ if there is a path from the point immediately following $d$ to $p$, such that $d$ is not "killed" along that path.

Then the authors consider a flow graph and explain the definition with an example as follows:

A flow graph

For example, both the definitions i:=m-1 and j:=n in block $B_1$ in Fig. above reach the beginning of block $B_2$, as does the definition j:=j-1, provided there are no assignments to or reads of j in $B_4$, $B_5$, or the portion of $B_3$ following that definition.

I can understand that in $B_4$, $B_5$, or the portion of $B_3$ following that definition j:=j-1 if there is an assignment to j then the definition $d_5$ is killed. But what problem shall be there if there is simply a read of the value j? How does it kill the definition $d_5$ and prevent it from reaching the top of $B_2$?

$\endgroup$

1 Answer 1

1
$\begingroup$

I can't find the errata sheet for the 1st edition (this came from the first ed, right? That diagram is so 1980's) but it sure looks like a mistake. The 2nd edition says

"We say a definition d reaches a point p if there is a path from the point immediately following d to p such that d is not "killed" along that path. We kill a definition of a variable x if there is any other definition of x anywhere along the path. ... A definition of a variable x is a statement that assigns, or may assign, a value to x"

So I agree with your doubts, pretty certainly a read can't kill (just reading a variable can't change program state).

$\endgroup$
1
  • $\begingroup$ Yes, this is from the first ed. $\endgroup$ Aug 11, 2021 at 18:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.