skip to main content
10.1145/2236576.2236583acmotherconferencesArticle/Chapter ViewAbstractPublication PagesscopesConference Proceedingsconference-collections
research-article

Dynamic method to evaluate code optimization effectiveness

Published: 15 May 2012 Publication History

Abstract

The identification of redundant computation is in general undecidable and prevents the obtainment of an ideal case as reference to the measurement of the remaining unexploited potential for redundancy removal and to the evaluation of code optimization effectiveness. This paper presents a methodology for optimization effectiveness analysis by observing the complete dynamic stream of executed instructions and memory references in the whole program execution, and by applying an extended value numbering algorithm to the execution trace. This method reduces the interprocedural analysis to the analysis of a large basic block and detects redundant memory and arithmetic operations that are visible only at the run-time. This way, the work extends the load-reuse analysis and provides both a more accurate approximation of the upper bound of exploitable optimization in the program and a reference point to evaluate optimization effectiveness. The results of applying this method to representative benchmark (SPECInt 2006) executables created with each compiler optimization level in GNU C/C++ Compiler are reported. The programs are run with a full-system simulator based on Power ISA 64-bit (version 2.06), and the whole application execution trace is collected. The proposed analysis reveals a significant amount of remaining unexploited redundancies even with the highest optimization level available. Sources of inefficiency and implications on exploring dynamic optimizations are discussed.

References

[1]
B. Alpern, M. N. Wegman, and F. K. Zadeck. Detecting equality of variables in programs. In Proceedings of the 15th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, POPL '88, pages 1--11, New York, NY, USA, 1988. ACM.
[2]
R. Bodík, R. Gupta, and M. L. Soffa. Load-reuse analysis: design and evaluation. In Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, PLDI '99, pages 64--76, New York, NY, USA, 1999. ACM.
[3]
P. Briggs, K. D. Cooper, and L. T. Simpson. Value numbering. Softw. Pract. Exper., 27: 701--724, June 1997.
[4]
L. Ceze, K. Strauss, G. Almasi, P. J. Bohrer, J. R. Brunheroto, C. Cascaval, J. G. Castanos, D. Lieber, Xavier, X. Martorell, J. E. Moreira, A. Sanomiya, and E. Schenfeld. Full circle: Simulating Linux clusters on Linux clusters. In In Proceedings of the Fourth LCI International Conference on Linux Clusters: The HPC Revolution 2003, 2003.
[5]
J. Cocke. Programming languages and their compilers: Preliminary notes. Courant Institute of Mathematical Sciences, New York University, 1969.
[6]
K. D. Cooper and J. Lu. Register promotion in C programs. In Proc. ACM SIGPLAN Conf. Programming Language Design and Implementation (PLDI-97, pages 308--319. ACM Press, 1997.
[7]
K. D. Cooper and L. Xu. Memory redundancy elimination to improve application energy efficiency. In Proceedings of the 16th International Workshop on Languages and Compilers for Parallel Computing (LCPC'03, 2003.
[8]
R. Jenkins. A hash function for hash table lookup, 2006.
[9]
A. J. Kleinosowski and D. J. Lilja. Minnespec: A new SPEC benchmark workload for simulation-based computer architecture research. IEEE Computer Architecture Letters, 1: 7--7, 2002.
[10]
J. Moreira, M. Brutman, J. Castaños, T. Engelsiepen, M. Giampapa, T. Gooding, R. Haskin, T. Inglett, D. Lieber, P. McCarthy, M. Mundy, J. Parker, and B. Wallenfelt. Designing a highly-scalable operating system: the Blue Gene/L story. In Proceedings of the 2006 ACM/IEEE conference on Supercomputing, SC '06, New York, NY, USA, 2006. ACM.
[11]
G. Ramalingam. The undecidability of aliasing. ACM Trans. Program. Lang. Syst., 16: 1467--1471, September 1994.
[12]
A. Sodani and G. S. Sohi. Dynamic instruction reuse. In Proceedings of the 24th annual international symposium on Computer architecture, ISCA '97, pages 194--205, New York, NY, USA, 1997. ACM.
[13]
A. Sodani and G. S. Sohi. An empirical analysis of instruction repetition. In Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, ASPLOS-VIII, pages 35--45, New York, NY, USA, 1998. ACM.
[14]
J. Yang and R. Gupta. Load redundancy removal through instruction reuse. In Proceedings of the Proceedings of the 2000 International Conference on Parallel Processing, ICPP '00, pages 61-, Washington, DC, USA, 2000. IEEE Computer Society.

Index Terms

  1. Dynamic method to evaluate code optimization effectiveness

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Other conferences
    SCOPES '12: Proceedings of the 15th International Workshop on Software and Compilers for Embedded Systems
    May 2012
    82 pages
    ISBN:9781450313360
    DOI:10.1145/2236576
    • General Chair:
    • Henk Corporaal,
    • Program Chair:
    • Sander Stuijk
    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

    • EDAA: European Design Automation Association

    In-Cooperation

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 15 May 2012

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. code optimization
    2. dynamic analysis
    3. effectiveness analysis
    4. value numbering

    Qualifiers

    • Research-article

    Conference

    Map2MPSoC/SCOPES'12
    Sponsor:
    • EDAA

    Acceptance Rates

    Overall Acceptance Rate 38 of 79 submissions, 48%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 132
      Total Downloads
    • Downloads (Last 12 months)2
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 20 Jan 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Media

    Figures

    Other

    Tables

    Share

    Share

    Share this Publication link

    Share on social media