Article

Free access

Global code motion/global value numbering

Author:

Cliff ClickAuthors Info & Claims

PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation

Pages 246 - 257

https://doi.org/10.1145/207110.207154

Published: 01 June 1995 Publication History

PDF eReader

References

[1]

A. Aho, R. Sethi, and J. Ullman. Compilers- Principles, Techniques, and Tools. Addison- Wesley, 1985.

Digital Library

Google Scholar

[2]

B. Alpern, M. N. Wegman, and F. K. Zadeck. Detecting equality of variables in programs. In Conference Record of the Fifteenth A CM Symposium on the Principles of Programming Languages, 1988.

Digital Library

Google Scholar

[3]

R.A. Ballance, A. B. Maccabe, and K. J. Ottenstein. The program dependence web: A representation supporting control-, data- and demanddriven interpretation of imperative languages. In Proceedings of the SIGPLAN '90 Cot~ference on Programming Languages Design and Implementation, June 1990.

Digital Library

Google Scholar

[4]

P. Briggs, Register Allocation via Graph Coloring. Ph.D. thesis, Rice University, 1992.

Digital Library

Google Scholar

[5]

P. Briggs. The Massively Scalar Compiler Project. Unpublished report. Preliminary version available via ftp://cs.rice, edu/public/preston/optimizer/ shared.ps. Rice University, July 1994.

Google Scholar

[6]

P. Briggs and K. Cooper. Effective partial redundancy elimination. In Proceedings of the SIGPLAN '94 Conference on Programming Languages Design and Implementation, June 1994.

Digital Library

Google Scholar

[7]

P. Briggs and T. Harvey. Iloc '93. Technical report CRPC-TR93323, Rice University, 1993.

Google Scholar

[8]

R. Cartwright and M. Felleisen. The semantics of program dependence. In Proceedings of the SIGPLAN '89 Conference on Programming Languages Design and Implementation, June 1989.

Digital Library

Google Scholar

[9]

G.J. Chaitin. Register allocation and spilling via graph coloring. In Proceedings of the SIGPLAN '82 Symposium on Compiler Construction, June 1982.

Digital Library

Google Scholar

[10]

C. Click, Combining Analyses, Combining Optimizations. Ph.D. thesis, Rice University, 1995.

Digital Library

Google Scholar

[11]

J. Cocke and J. T. Schwartz. Programming languages and their compilers. Courant institute of Mathematical Sciences, New York University, April 1970.

Digital Library

Google Scholar

[12]

R. Cytron, J. Ferrante, B. K. Rosen, M. N. Wegman, and F. K. Zadeck. An efficient method of computing static single assignment form. In Conference Record of the Sixteenth A CM Symposium on the Principles of Programming Languages, Jan. 1989.

Digital Library

Google Scholar

[13]

K.H. Drechsler and M. P. Stadel. A solution to a problem with Morel and Renvoise's "Global optimization by suppression of partial redundancies". A CM Transactions on Programming Languages and Systems, 10(4):635-640, Oct. 1988.

Digital Library

Google Scholar

[14]

G. E. Forstyhe, M. A. Malcom, and C. B. Moler. Computer Methods for Mathematical Computations. Prentice-Hall, Englewood Cliffs, New Jersey, 1977.

Digital Library

Google Scholar

[15]

J. Ferrante, K. J. Ottenstein, and J. D. Warren. The program dependence graph and its use in optimization. A CM Transactions on Programming Languages and Systems, 9(3):319-349, July, 1987.

Digital Library

Google Scholar

[16]

J. Knoop, O. Rtithing, and B. Steffen. Partial dead code elimination. In Proceedings of the SIGPLAN '94 Conference on Programming Languages Design and Implementation, June 1994.

Digital Library

Google Scholar

[17]

T. Lengauer and R. E. Tarjan. A fast algorithm for finding dominators in a flowgraph. A CM Transactions on Programming Languages and Systems, 1(1):121-I41, July, 1979.

Digital Library

Google Scholar

[18]

E. Morel and C. Renvoise. Global optimization by suppression of partial redundancies. Communications of the ACM, 22(2):96--103, Feb. 1979.

Digital Library

Google Scholar

[19]

B. K. Rosen., M. N. Wegman, and F. K. Zadeck, Global Value Numbers and Redundant Computations. In Conference Record of the Fifteenth A CM Symposium on the Principles of Programming Languages, Jan. 1988.

Digital Library

Google Scholar

[20]

T. Simpson, Global Value Numbering. Unpublished report. Available from ftp://cs.rice.edu/ public/preston/optimizer/gval.ps. Rice University, 1994.

Google Scholar

[21]

R. E. Tarjan. Testing flow graph reducibility. Journal of Computer and System Sciences, 9:355- 365, 1974.

Digital Library

Google Scholar

[22]

C. Vick, SSA-Based Reduction of Operator Strength. Masters thesis, Rice University, pages 11-15, 1994.

Google Scholar

[23]

D. Weise, R. Crew, M. Ernst, and B. Steensgaard. Value dependence graphs: Representation without taxation. In Proceedings of the 21st A CM SIGPLAN Symposium on the Principles of Programming Languages, 1994.

Digital Library

Google Scholar

[24]

M. N. Wegman and F. K. Zadeck. Constant propagation with conditional branches. A CM Transactions on Programming Languages and Systems, I3(2):181-210, April 1991.

Digital Library

Google Scholar

Cited By

View all

Bera RRanganathan ARakshit JMahto SNori AGaur JOlgun AKanellopoulos KSadrosadati MSubramoney SMutlu O(2024)Constable: Improving Performance and Power Efficiency by Safely Eliminating Load Instruction Execution2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00017(88-102)Online publication date: 29-Jun-2024
https://doi.org/10.1109/ISCA59077.2024.00017
Bračevac OWei GJia SAbeysinghe SJiang YBao YRompf T(2023)Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect DependenciesProceedings of the ACM on Programming Languages10.1145/36228137:OOPSLA2(400-430)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622813
Vukasovic MProkopec A(2023)Exploiting Partially Context-sensitive Profiles to Improve Performance of Hot CodeACM Transactions on Programming Languages and Systems10.1145/361293745:4(1-64)Online publication date: 13-Sep-2023
https://dl.acm.org/doi/10.1145/3612937
Show More Cited By

Index Terms

Global code motion/global value numbering

Recommendations

An efficient SSA-based algorithm for complete global value numbering
APLAS'07: Proceedings of the 5th Asian conference on Programming languages and systems

Global value numbering (GVN) is an important static analysis technique both for optimizing compilers and program verification tools. Existing complete GVN algorithms discovering all Herbrand equivalences are all inefficient. One reason of this is the ...
Partial redundancy elimination for global value numbering
Global L-neighborhood groups

This paper introduces and studies the notion of global L-neighborhood group which is defined as a group equipped with a global L-neighborhood structure in sense of Gahler et al. such that both the binary operation and the unary operation of the inverse ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PLDI '95: Proceedings of the ACM SIGPLAN 1995 conference on Programming language design and implementation

June 1995

335 pages

ISBN:0897916972

DOI:10.1145/207110

Chairman:
David W. Wall
Digital—Western Research Laboratory

ACM SIGPLAN Notices Volume 30, Issue 6
June 1995
327 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/223428
Editors:
Brent T. Hailpern
IBM T. J. Watson Research Center, Yorktown Heoghts, NY
,
Richard L. Wexelblat
IRS IS:AO, Washington, DC
Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1995

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI95

Sponsor:

SIGPLAN

PLDI95: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 18 - 21, 1995

California, La Jolla, USA

Acceptance Rates

PLDI '95 Paper Acceptance Rate 28 of 105 submissions, 27%;

Overall Acceptance Rate 406 of 2,067 submissions, 20%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

91
Total Citations
View Citations
2,494
Total Downloads

Downloads (Last 12 months)444
Downloads (Last 6 weeks)73

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Bera RRanganathan ARakshit JMahto SNori AGaur JOlgun AKanellopoulos KSadrosadati MSubramoney SMutlu O(2024)Constable: Improving Performance and Power Efficiency by Safely Eliminating Load Instruction Execution2024 ACM/IEEE 51st Annual International Symposium on Computer Architecture (ISCA)10.1109/ISCA59077.2024.00017(88-102)Online publication date: 29-Jun-2024
https://doi.org/10.1109/ISCA59077.2024.00017
Bračevac OWei GJia SAbeysinghe SJiang YBao YRompf T(2023)Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect DependenciesProceedings of the ACM on Programming Languages10.1145/36228137:OOPSLA2(400-430)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622813
Vukasovic MProkopec A(2023)Exploiting Partially Context-sensitive Profiles to Improve Performance of Hot CodeACM Transactions on Programming Languages and Systems10.1145/361293745:4(1-64)Online publication date: 13-Sep-2023
https://dl.acm.org/doi/10.1145/3612937
Basso MProkopec ARosà ABinder W(2023)Optimization-Aware Compiler-Level Event ProfilingACM Transactions on Programming Languages and Systems10.1145/359147345:2(1-50)Online publication date: 26-Jun-2023
https://dl.acm.org/doi/10.1145/3591473
Rocha RSaumya CSundararajah KPetoumenos PKulkarni MO’Boyle MVerbrugge CLhoták OShen X(2023)HyBF: A Hybrid Branch Fusion Strategy for Code Size ReductionProceedings of the 32nd ACM SIGPLAN International Conference on Compiler Construction10.1145/3578360.3580267(156-167)Online publication date: 17-Feb-2023
https://dl.acm.org/doi/10.1145/3578360.3580267
Utting MWebb BHayes I(2023)Differential Testing of a Verification Framework for Compiler Optimizations (Case Study)2023 IEEE/ACM 11th International Conference on Formal Methods in Software Engineering (FormaliSE)10.1109/FormaliSE58978.2023.00015(66-75)Online publication date: May-2023
https://doi.org/10.1109/FormaliSE58978.2023.00015
Khan SChatterjee BPande SRauchwerger LCameron KNikolopoulos DPnevmatikatos D(2022)VICOProceedings of the 36th ACM International Conference on Supercomputing10.1145/3524059.3532393(1-14)Online publication date: 28-Jun-2022
https://dl.acm.org/doi/10.1145/3524059.3532393
Webb BUtting MHayes I(2021)A Formal Semantics of the GraalVM Intermediate RepresentationAutomated Technology for Verification and Analysis10.1007/978-3-030-88885-5_8(111-126)Online publication date: 12-Oct-2021
https://doi.org/10.1007/978-3-030-88885-5_8
Prokopec ADuboscq GLeopoldseder DWürthinger TKandemir MJimborean AMoseley T(2019)An optimization-driven incremental inline substitution algorithm for just-in-time compilersProceedings of the 2019 IEEE/ACM International Symposium on Code Generation and Optimization10.5555/3314872.3314893(164-179)Online publication date: 16-Feb-2019
https://dl.acm.org/doi/10.5555/3314872.3314893
Rodriguez-Cancio MCombemale BBaudry BPalumbo FBecchi MSchulz MSato K(2019)Approximate loop unrollingProceedings of the 16th ACM International Conference on Computing Frontiers10.1145/3310273.3323841(94-105)Online publication date: 30-Apr-2019
https://dl.acm.org/doi/10.1145/3310273.3323841
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

An efficient SSA-based algorithm for complete global value numbering

Partial redundancy elimination for global value numbering

Global L-neighborhood groups