skip to main content
10.1145/1454115.1454120acmconferencesArticle/Chapter ViewAbstractPublication PagespactConference Proceedingsconference-collections
research-article

Redundancy elimination revisited

Published: 25 October 2008 Publication History

Abstract

This work proposes and evaluates improvements to previously known algorithms for redundancy elimination.
Enhanced Scalar Replacement combines two classic techniques, scalar replacement and hash-based value numbering. The former detects redundant array references within and across loop iterations, while the latter detects a large class of redundancies, but only within a single loop iteration. By integrating the two techniques, ESR detects and eliminates a wider range of expression redundancies across loop iterations.
We also extend hash-based value numbering to perform reassociation. Classic redundancy elimination techniques operate on an intermediate representation of the program in which operand association and order is of fixed shape. This rigidity in code shape may sometimes obscure redundancies. Our optimizer attempts to shape the code by changing associativity, exposing more redundancies. Opportunities for ESR, in particular, are increased with reassociation.

References

[1]
Randy Allen and Ken Kennedy. Vector register allocation. IEEE Transactions on Computers, 41(10):1290--1317, 1992.
[2]
Randy Allen and Ken Kennedy. Optimizing Compilers for Modern Architectures: A Dependence-based Approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2002.
[3]
Rastislav Bodík and Sadun Anik. Path-sensitive value-flow analysis. In POPL '98: Proceedings of the 25th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, pages 237--251, New York, NY, USA, 1998. ACM Press.
[4]
Rastislav Bodik, Rajiv Gupta, and Mary Lou Soffa. Load-reuse analysis: Design and evaluation. In SIGPLAN Conference on Programming Language Design and Implementation, pages 64--76, 1999.
[5]
I. Bomze, M. Budinich, P. Pardalos, and M. Pelillo. The maximum clique problem. In D.-Z. Du and P. M. Pardalos, editors, Handbook of Combinatorial Optimization, volume 4. Kluwer Academic Publishers, Boston, MA, 1999.
[6]
Melvin A. Breuer. Generation of optimal code for expressions via factorization. Communications of the ACM, pages 333--340, June 1969.
[7]
Preston Briggs and Keith D. Cooper. Effective partial redundancy elimination. In PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, pages 159--170, New York, NY, USA, 1994. ACM.
[8]
Preston Briggs, Keith D. Cooper, and L. Taylor Simpson. Value numbering. Software -- Practice and Experience, 27(6):701--724, 1997.
[9]
David Callahan, Steve Carr, and Ken Kennedy. Improving register allocation for subscripted variables. SIGPLAN Notices, 25(6):53--65, June 1990. Proceedings of the ACM SIGPLAN '90 Conference on Programming Language Design and Implementation.
[10]
John Cocke and Jacob T. Schwartz. Programming languages and their compilers: Preliminary notes. Technical report, Courant Institute of Mathematical Sciences, New York University, 1970.
[11]
Steven J. Deitz, Bradford L. Chamberlain, and Lawrence Snyder. Eliminating redundancies in sum-of-product array computations. In ICS '01: Proceedings of the 15th international conference on Supercomputing, pages 65--77, New York, NY, USA, 2001. ACM Press.
[12]
Andrei P. Ershov. On programming of arithmetic operations. Communications of the ACM, 1(8):3--9, 1958.
[13]
Andrei P. Ershov. Programming Programme for the BESM Computer. Pergamon Press, 1959.
[14]
J. Felsenstein, S. Sawyer, and R. Kochin. An efficient method for matching nucleic acid sequences. Nucleic Acids Research, 10(1):133--139, 1982.
[15]
Dennis J. Frailey. Expression optimization using unary complement operators. SIGPLAN Notices, 5(7):67--85, July 1970.
[16]
Dan Gusfield. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, January 1997.
[17]
Hans Kellerer, Ulrich Pferschy, and David Pisinger. Knapsack Problems. Springer, Berlin, Germany, 2004.

Cited By

View all
  • (2023)R2U2 Version 3.0: Re-Imagining a Toolchain for Specification, Resource Estimation, and Optimized Observer Generation for Runtime Verification in Hardware and SoftwareComputer Aided Verification10.1007/978-3-031-37709-9_23(483-497)Online publication date: 17-Jul-2023
  • (2022)Scalar Replacement Considering Branch DivergenceJournal of Information Processing10.2197/ipsjjip.30.16430(164-178)Online publication date: 2022
  • (2020)What every scientific programmer should know about compiler optimizations?Proceedings of the 34th ACM International Conference on Supercomputing10.1145/3392717.3392754(1-12)Online publication date: 29-Jun-2020
  • Show More Cited By

Index Terms

  1. Redundancy elimination revisited

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    PACT '08: Proceedings of the 17th international conference on Parallel architectures and compilation techniques
    October 2008
    328 pages
    ISBN:9781605582825
    DOI:10.1145/1454115
    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]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 25 October 2008

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. expression optimization
    2. loop optimization
    3. reassociation
    4. redundancy elimination
    5. scalar replacement

    Qualifiers

    • Research-article

    Conference

    PACT '08
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 121 of 471 submissions, 26%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)20
    • Downloads (Last 6 weeks)2
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2023)R2U2 Version 3.0: Re-Imagining a Toolchain for Specification, Resource Estimation, and Optimized Observer Generation for Runtime Verification in Hardware and SoftwareComputer Aided Verification10.1007/978-3-031-37709-9_23(483-497)Online publication date: 17-Jul-2023
    • (2022)Scalar Replacement Considering Branch DivergenceJournal of Information Processing10.2197/ipsjjip.30.16430(164-178)Online publication date: 2022
    • (2020)What every scientific programmer should know about compiler optimizations?Proceedings of the 34th ACM International Conference on Supercomputing10.1145/3392717.3392754(1-12)Online publication date: 29-Jun-2020
    • (2020)Exploiting Computation Reuse for Stencil Accelerators2020 57th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC18072.2020.9218680(1-6)Online publication date: Jul-2020
    • (2020)Embedding Online Runtime Verification for Fault Disambiguation on Robonaut2Formal Modeling and Analysis of Timed Systems10.1007/978-3-030-57628-8_12(196-214)Online publication date: 25-Aug-2020
    • (2019)Redundant loadsProceedings of the 41st International Conference on Software Engineering10.1109/ICSE.2019.00103(982-993)Online publication date: 25-May-2019
    • (2017)Generalizations of the theory and deployment of triangular inequality for compiler-based strength reductionACM SIGPLAN Notices10.1145/3140587.306237752:6(33-48)Online publication date: 14-Jun-2017
    • (2017)GLORE: generalized loop redundancy elimination upon LER-notationProceedings of the ACM on Programming Languages10.1145/31338981:OOPSLA(1-28)Online publication date: 12-Oct-2017
    • (2017)REDSPYACM SIGARCH Computer Architecture News10.1145/3093337.303772945:1(47-61)Online publication date: 4-Apr-2017
    • (2017)REDSPYACM SIGPLAN Notices10.1145/3093336.303772952:4(47-61)Online publication date: 4-Apr-2017
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media