Reaching definitions are one of the most common and useful data flow patterns. Knowing exactly where each variable x can be defined in the program when the control flow reaches each point p , you can get a lot of information about this variable. In particular, the compiler can find out if x constant at point p , and the debugger can report the possible use of the non-initialized variable x at point p [1] .
Content
Meaning of the term
We say that the definition of d reaches point p if there is a path from the point immediately following d to point p such that d not destroyed along this path. We destroy the definition of x if there is another definition of x somewhere along the path. Intuitively, if the definition of d a variable x reaches a point p , then d may be the place where the value of x used in p determined the last time.
The definition of x is an instruction that assigns or can assign a value to x . The analysis of the program should be conservative: if we do not know whether the instruction s assigns the value of the variable x , then we should assume that it can do this, i.e. that the variable x after the instruction s can either have the original value that it had before the instruction s , or a new value created by s [1] .
Example
For example, consider the following code:
d1: y: = 3 d2: x: = y
where the definition of d1 reaches the definition of d2 . However, in the following example:
d1: y: = 3 d2: y: = 4 d3: x: = y
the definition of d1 does not reach the definition of d3 , because the definition of d2 destroys the definition of the variable y in d1 .
Notes
- β 1 2 Compilers: principles, technologies and tools, 2008 , p. 725.
Literature
- Alfred Aho, Monica Lam, Ravi Seti, Jeffrey Ullman. Compilers: principles, technologies and tools = Compilers: Principles, Techniques, and Tools. - 2nd edition. - M .: "Williams", 2008. - 1184 p. - 1,500 copies - ISBN 978-5-8459-1349-4 .