World Library  
Flag as Inappropriate
Email this Article

Global value numbering

Article Id: WHEBN0000547807
Reproduction Date:

Title: Global value numbering  
Author: World Heritage Encyclopedia
Language: English
Subject: Optimizing compiler, Common subexpression elimination, Compiler optimizations, Static single assignment form, Loop splitting
Collection: Compiler Optimizations
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Global value numbering

Global value numbering (GVN) is a compiler optimization based on the static single assignment form (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

Without copy propagation, 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.

References

  • G.A. Kildall, "A Unified Approach to Global Program Optimization." Proceedings of the First ACM Symposium on Principles of Programming Languages,194-206, 1973.
  • 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 Science Department, Rice University, 1996. (Author's Ph.D. thesis)
  • Muchnick, Steven S. Advanced Compiler Design and Implementation. Morgan Kaufmann. 1997.
  • P. Briggs, K.D. Cooper, L.T. Simpson,"Value Numbering." Software-Practice and Experience, 27:6, pages :701-724, 1997.
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.