Reaching definitions
Encyclopedia : R : RE : REA : Reaching definitions
In compiler theory, reaching definitions is a data-flow analysis which statically determines which definitions may reach a given point in the code. Because of its simplicity, it is often used as the canonical example of a data-flow analysis in textbooks. The data-flow confluence operator used is set union, and the analysis is forward flow. Reaching definitions are used to compute use-def chains and def-use chains.
The data-flow equations used for a given basic block S in reaching definitions are:
[ _[S] = [S] \cup (_[S] - [S]) ] [ _[S] = \bigcup_ _[p] ]For a generic instruction, we define the GEN and KILL sets as follows:
[ [d : y leftarrow f(x_1,cdots,x_n)] = \ ] [ [d : y leftarrow f(x_1,cdots,x_n)] = [y] - \ ]Where DEFS[y] is the set of all definitions that assign to the variable y. Here d is a unique label attached to the assigning instruction. Thus, the domain of values in reaching definitions are these instruction labels.
Further reading
From Wikipedia, the Free Encyclopedia. Original article here. Support Wikipedia by contributing or donating.
All text is available under the terms of the GNU Free Documentation License See Wikipedia Copyrights for details.