Copy propagation


Copy propagation

In compiler theory, copy propagation is the process of replacing the occurrences of targets of direct assignments with their values[1]. A direct assignment is an instruction of the form x = y, which simply assigns the value of y to x.

From the following code:

y = x
z = 3 + y

Copy propagation would yield:

z = 3 + x

Copy propagation often makes use of reaching definitions, use-def chains and def-use chains when computing which occurrences of the target may be safely replaced. If all upwards exposed uses of the target may be safely modified, the assignment operation may be eliminated.

Copy propagation is a useful "clean up" optimization frequently used after other optimizations have already been run. Some optimizations -- such as elimination of common sub expressions[1] -- require that copy propagation be run afterwards in order to achieve an increase in efficiency.

References

  1. ^ a b Aho, Alfred V.; Lam, Monica S.; Sethi, Ravi; Ullman, Jeffrey D.. Compilers, Principles, Techniques, & Tools Second edition. ISBN 0-321-48681-1. 

Further reading

Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Software propagation — is a general term for the copying duplication of software, and was explicitly defined in version 3 of the GNU General Public License. The term is deliberately intended to distinguish between the activities permitted by free software licenses and… …   Wikipedia

  • Blind carbon copy — For other uses see BCC. In the context of e mail, blind carbon copy (abbreviated BCC and sometimes referred to as Blind Courtesy Copy or Blank Carbon Copy) refers to the practice of sending a message to multiple recipients in such a way that what …   Wikipedia

  • Compiler optimization — is the process of tuning the output of a compiler to minimize or maximize some attributes of an executable computer program. The most common requirement is to minimize the time taken to execute a program; a less common one is to minimize the… …   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

  • VBCC — is the name of a portable and retargetable ISO/ANSI C compiler.It supports ISO C according to ISO/IEC 9899:1989 and a subset of the new standard ISO/IEC 9899:1999 (C99). It is divided into two parts. One is target independent and the other is… …   Wikipedia

  • Sun Studio (software) — infobox software name = Sun Studio developer = Sun Microsystems latest release version = Sun Studio 12 latest release date = June 04, 2007 latest preview version = [http://developers.sun.com/sunstudio/downloads/express/index.jsp Sun Studio… …   Wikipedia

  • Global value numbering — (GVN) is a compiler optimization based on the SSA intermediate representation. It sometimes helps eliminate redundant code that common subexpression elimination (CSE) does not. At the same time, however, CSE may eliminate code that GVN does not,… …   Wikipedia

  • Удаление мёртвого кода — В теории компиляторов удалением мёртвого кода (англ. dead code elimination, DCE) называется оптимизация, удаляющая мёртвый код. Мёртвым кодом (так же бесполезным кодом) называют код, исполнение которого не влияет на вывод программы, все… …   Википедия

  • Conficker — Common name Aliases Mal/Conficker A(Sophos) Win32/Conficker.A (CA) W32.Downadup (Symantec) W32/Downadup.A (F Secure) Conficker.A (Panda) Net Worm.Win32.Kido.bt ( …   Wikipedia

  • reproduction — I (New American Roget s College Thesaurus) Procreation Nouns 1. reproduction, sexual reproduction; [re]generation, propagation, multiplication, reenactment, repetition, procreation, fructification, breeding, begetting; ontogeny, oogamy; baby boom …   English dictionary for students