Reaching definition

Reaching definition

In compiler theory, a reaching definition for a given instruction is another instruction, the target variable of which may reach the given instruction without an intervening assignment. For example, in the following code:

d1 : y := 3 d2 : x := y

d1 is a reaching definition at d2. In the following, example, however:

d1 : y := 3 d2 : y := 4 d3 : x := y

d1 is no longer a reaching definition at d3, because d2 kills its reach.

As analysis

The similarly-named 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:

* { m REACH}_{ m in} [S] = igcup_{p in pred [S] } { m REACH}_{ m out} [p]
* { m REACH}_{ m out} [S] = { m GEN} [S] cup ({ m REACH}_{ m in} [S] - { m KILL} [S] )

In other words, the set of reaching definitions going into S are all of the reaching definitions from S's predecessors, pred [S] . pred [S] consists of all of the basic blocks that come before S in the control flow graph. The reaching definitions coming out of S are all reaching definitions of its predecessors minus those reaching definitions whose variable is killed by S plus any new definitions generated within S.

For a generic instruction, we define the { m GEN} and { m KILL} sets as follows:

* { m GEN} [d : y leftarrow f(x_1,cdots,x_n)] = {d}
* { m KILL} [d : y leftarrow f(x_1,cdots,x_n)] = { m DEFS} [y] - {d}

where { m 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

*cite book
author=Aho, Alfred V.; Sethi, Ravi; & Ullman, Jeffrey D.
publisher=Addison Wesley
id=ISBN 0-201-10088-6

*cite book
author=Appel, Andrew W.
title=Modern Compiler Implementation in ML
publisher=Cambridge University Press
id=ISBN 0-521-58274-1

*cite book
author=Cooper, Keith D.; & Torczon, Linda.
title=Engineering a Compiler
publisher=Morgan Kaufmann
id=ISBN 1-55860-698-X

*cite book
author=Muchnick, Steven S.
title=Advanced Compiler Design and Implementation
publisher=Morgan Kaufmann
id=ISBN 1-55860-320-4

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Destruction by Definition — Studio album by The Suicide Machines Re …   Wikipedia

  • Data-flow analysis — is a technique for gathering information about the possible set of values calculated at various points in a computer program. A program s control flow graph (CFG) is used to determine those parts of a program to which a particular value assigned… …   Wikipedia

  • Static single assignment form — In compiler design, static single assignment form (often abbreviated as SSA form or SSA) is an intermediate representation (IR) in which every variable is assigned exactly once. Existing variables in the original IR are split into versions , new… …   Wikipedia

  • Program slicing — In computer programming, program slicing is the computation of a program slice. The program slice consists of the parts of a program that may affect the values computed at some point of interest, referred as a slicing criterion. Program slicing… …   Wikipedia

  • Constant folding — and constant propagation are related compiler optimizations used by many modern compilers. An advanced form of constant propagation known as sparse conditional constant propagation can more accurately propagate constants and simultaneously remove …   Wikipedia

  • Déplacement des invariants de boucle — En programmation informatique, les invariants de boucle sont des instructions ou des expressions d un langage de programmation impératif qui peut être déplacé hors du corps de la boucle sans affecter le résultat du programme. Le déplacement des… …   Wikipédia en Français

  • HALAKHAH — DEFINITION The word halakhah (from the root halakh, to go ), the legal side of Judaism (as distinct from aggadah, the name given to the nonlegal material, particularly of the rabbinic literature), embraces personal, social, national, and… …   Encyclopedia of Judaism

  • LEVIRATE MARRIAGE AND ḤALIẒAḤ. — Definition Levirate marriage (Heb. יִבּוּם; yibbum) is the marriage between a widow whose husband died without offspring (the yevamah) and the brother of the deceased (the yavam or levir), as prescribed in Deuteronomy 25:5–6: „ If brethren dwell… …   Encyclopedia of Judaism

  • Media and Publishing — ▪ 2007 Introduction The Frankfurt Book Fair enjoyed a record number of exhibitors, and the distribution of free newspapers surged. TV broadcasters experimented with ways of engaging their audience via the Internet; mobile TV grew; magazine… …   Universalium

  • Roman Catholicism — the faith, practice, and system of government of the Roman Catholic Church. [1815 25] * * * Largest single Christian denomination in the world, with some one billion members, or about 18% of the world s population. The Roman Catholic church has… …   Universalium

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”