Global value numbering

Global value numbering

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, so both are often found in modern compilers. Global value numbering is distinct from local value numbering in that the value-number mappings hold across basic block boundaries as well, and different algorithms are used to compute the mappings.

Global value numbering works by assigning a value number to variables and expressions. To those variables and expressions which are provably equivalent, the same value number is assigned. For instance, in the following code:

w := 3 x := 3 y := x + 4 z := w + 4

a good GVN routine would assign the same value number to w and x, and the same value number to y and z. For instance, the map [{w} mapsto 1, {x} mapsto 1, {y} mapsto 2, {z} mapsto 2] would constitute an optimal value-number mapping for this block. Using this information, the previous code fragment may be safely transformed into:

w := 3 x := w y := w + 4 z := y

Depending on the code following this fragment, copy propagation may be able to remove the assignments to x and to z

The reason that GVN is sometimes more powerful than CSE comes from the fact that CSE matches lexically identical expressions whereas the GVN tries to determine an underlying equivalence. For instance, in the code:

a := c × d e := c f := e × d

CSE would not eliminate the recomputation assigned to f, but even a poor GVN algorithm should discover and eliminate this redundancy.

SSA form is required to perform GVN so that false variable name-value name mappings are not created.


* Alpern, Bowen, Wegman, Mark N., and Zadeck, F. Kenneth. "Detecting Equality of Variables in Programs."Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages(POPL), ACM Press, San Diego, CA, USA, January 1988, pages 1-11.

* L. Taylor Simpson, "Value-Driven Redundancy Elimination." Technical Report 96-308, Computer ScienceDepartment, Rice University, 1996. (Author's Ph.D. thesis)

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

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Global Title — A Global Title (GT) is an address used in the SCCP protocol for routing signaling messages on telecommunications networks. In theory, a global title is a unique address which refers to only one destination, though in practice destinations can… …   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

  • Common subexpression elimination — In computer science, common subexpression elimination (CSE) is a compiler optimization that searches for instances of identical expressions (i.e., they all evaluate to the same value), and analyses whether it is worthwhile replacing them with a… …   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

  • Partial redundancy elimination — In compiler theory, Partial redundancy elimination (PRE) is a compiler optimization that eliminates expressions that are redundant on some but not necessarily all paths through a program. PRE is a form of common subexpression elimination (CSE).An …   Wikipedia

  • GNU Compiler Collection — Cc1 redirects here. For other uses of CC1 or CC 1, see CC1 (disambiguation). GNU Compiler Collection Developer(s) GNU Project Initial release May 23, 1987 ( …   Wikipedia

  • Avr-gcc — GNU Compiler Collection Entwickler: GCC Team Aktuelle Version: 4.4.0 (21. April 2009) …   Deutsch Wikipedia

  • EGCS — GNU Compiler Collection Entwickler: GCC Team Aktuelle Version: 4.4.0 (21. April 2009) …   Deutsch Wikipedia

  • GNU C-Compiler — GNU Compiler Collection Entwickler: GCC Team Aktuelle Version: 4.4.0 (21. April 2009) …   Deutsch Wikipedia

  • GNU C Compiler — GNU Compiler Collection Entwickler: GCC Team Aktuelle Version: 4.4.0 (21. April 2009) …   Deutsch Wikipedia

Share the article and excerpts

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