article

Free access

Partial dead code elimination

Authors:

Oliver Rüthing,

Bernhard SteffenAuthors Info & Claims

ACM SIGPLAN Notices, Volume 29, Issue 6

Pages 147 - 158

https://doi.org/10.1145/773473.178256

Published: 01 June 1994 Publication History

Abstract

A new aggressive algorithm for the elimination of partially dead code is presented, i.e., of code which is only dead on some program paths. Besides being more powerful than the usual approaches to dead code elimination, this algorithm is optimal in the following sense: partially dead code remaining in the resulting program cannot be eliminated without changing the branching structure or the semantics of the program, or without impairing some program executions.

Our approach is based on techniques for partial redundancy elimination. Besides some new technical problems there is a significant difference here: partial dead code elimination introduces second order effects, which we overcome by means of exhaustive motion and elimination steps. The optimality and the uniqueness of the program obtained is proved by means of a new technique which is universally applicable and particularly useful in the case of mutually interdependent program optimizations.

References

[1]

A. V. Aho, S. C. Johnson, and J. D. UUman. Code generation for expressions with common subexpressionso Journal of the ACM, 24(1):146- 160~ 1977.

Digital Library

[2]

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

Digital Library

[3]

D. Bernstein and Mo Rodeh. Global instruction scheduling for superscalar machines. In Proc. A CM SIGPLAN Conference on Programming Language Design and ImplementationS91, volume 26,6 of A CM SIGPLAN Notices, pages 241-255, Toronto, Ontario, June 1991.

Digital Library

[4]

P. Briggs and K. D. Cooper. Effective partial redundancy elimination. In Proc. A CM SIGPLAN Conference on Programming Language Design and Implementation'94, 1994.

Digital Library

[5]

R. Cytron, J. Ferrante, B. Rosen, M. Wegman, and F. K. Zadeck. Efficiently computing static single assignment form and the control dependency graph. A CM Transactions on Programming Languages and Systems, 13(4):451- 490, 1991.

Digital Library

[6]

D. M. Dhamdhere. A fast algorithm for code movement optimization. A CM SIGPLAN Notices, 23(10):172- 180, 1988.

Digital Library

[7]

D. M. Dhamdhere. Register assignment using code placement techniques. Journal of Computer Languages, 13(2):75- 93, 1988.

Digital Library

[8]

D. M. Dhamdhere. A usually linear algorithm for register assignment using edge placement of load and store instructions. Journal of Computer Languages, 15(2):83- 94, 1990.

Digital Library

[9]

D. M. Dhamdhere. Practical adaptation of the global optimization algorithm of Morel and Renvoise. A CM Transactions on Programming Languages and Systems, 13(2):291- 294, 1991. Technical Correspondence.

Digital Library

[10]

D.M. Dhamdhere, B. K. Rosen, and F. K. Zadeck. How to analyze large programs efficiently and informatively. In Proc. A CM SIGPLAN Conference on Programming Language Design and Implementation'92, volume 27,7 of A CM SIGPLAN Notices, pages 212- 223, San Francisco, CA, June 1992.

Digital Library

[11]

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, 1988. Technical Correspondence.

Digital Library

[12]

K.-H. Drechsler and M. Po Stadel. A variation of Knoop, Riithing and Steffen's lazy code motion. A CM SIGPLAN Notices, 28(5):29 - 38, 1993.

Digital Library

[13]

L. Feigen, D. Klappholz, R. Casazza, and X. Xue. The revival transformation~ In Conf. Record of the 21"d A CM Symposium on the Principles of Programming Languages, Portland, Oregon, 1994o

Digital Library

[14]

A. Geser, J~ Knoop, G. L/ittgen, O. Riithing, and B. Steffeno Chaotic fixed point iterations. MiP- Bericht 9403, Fakultiit flit Mathematik und Informatik, Universitiit Passau, Germany, 1994.

[15]

P. B. Gibbons and S. S. Muchnik. Efficient instruction scheduling for a pipline architecture. In Proc. A CM SIGPLAN Symposium on Compiler Construction'86, volume 21, 7 of A CM SIGPLAN Notices, pages 11-16, June 1986.

Digital Library

[16]

R. Giegerich, U. M5ncke, and R. Wilhelm. Invariance of approximative semantics with respect to program transformations. In Proc. of the third Conference of the European Co-operation in In/ormatics, Informatik-Fachberichte 50, pages 1-10. Springer, 1981.

Digital Library

[17]

M. S. Hecht. Flow Analysis of Computer Programs. Elsevier, North-Holland, 1977.

Digital Library

[18]

S. Horwitz, A. Demers, and T. Teitelbaum. An efficient general iterative algorithm for data flow analysis. Acta Informatica, 24:679- 694, 1987.

Digital Library

[19]

J. B. Kam and J. D. Ullman. Global data flow analysis and iterative algorithms. Journal of the ~4cM, ~2(1).l~S- 171, 107~.

Digital Library

[20]

K. Kennedy. Node listings applied to data flow analysis. In Conf. Record of the 2~a AGM Symposium on the Principles o/Programming Languages, pages 10- 21, Palo Alto, CA, 1975.

Digital Library

[21]

K. Kennedy. A survey of data flow analysis techniques. In S. S. Muchnick and N. D. Jones, editors, Program Flow Analysis: Theory and Applications, chapter 1, pages 5- 54. Prentice Hall, Englewood Cliffs, NJ, 1981.

[22]

J. Knoop, O. Riithing, and B. Steffen. Optimal code motion: Theory and practice. To appear in ACM Transactions on Programming Languages and Systems. Available as MIP-Bericht 9310, Fakult/it fiir Mathematik und Informatik, Universit/it Passau, Germany, 1993.35 pages.

Digital Library

[23]

J. Knoop, O. Riithing, and B. Steffen. Lazy code motion. In Proc. A CM SIGPLAN Conference on Programming Language Design and Implementation'92, volume 27,7 of A CM $IGPLAN Notices, pages 224- 234, San Francisco, CA, June 1992.

Digital Library

[24]

L. T. Kou. On live-dead analysis for global data flow problems. Journal of the A CM, 24(3):473- 483, July 1977.

Digital Library

[25]

R. J. Mintz, G. A. Fisher, and M. Sharir. The design of a global optimizer. In Proc. ACM SIC- PLAN Symposium on Compiler Construction'79, volume 1,/, 8 of A CM SIGPLAN Notices, pages 226- 234, Denver, Col., 1979.

Digital Library

[26]

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

Digital Library

[27]

B. K. Rosen, M. N. Wegman, and F. K. Zadeck. Global value numbers and redundant computations. In Conf. Record of the 15th A CM Symposium on the Principles of Programming Languages, pages 12- 27, San Diego, CA, 1988.

Digital Library

[28]

R. Sethi and J. D. Ullman. The generation of optimal code for arithmetic expressions. Journal of the A CM, 17(4):715-728, 1970.

Digital Library

[29]

R. E. Tarjan. Applications of path compression on balanced trees. Journal of the A CM, 26(4):690 - 715, 1979.

Digital Library

[30]

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

Digital Library

Cited By

Lee KRen MHoag EShrivastava ASui Y(2024)Optimistic and Scalable Global Function MergingProceedings of the 25th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3652032.3657575(46-57)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652032.3657575
Zhong LXiang CHuang HShen BMugnier EZhou Y(2024)Effective Bug Detection with Unused DefinitionsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629576(720-735)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3629576
Mahurkar AWang XZhang HRavindran B(2023)DynaCutProceedings of the 24th International Middleware Conference10.1145/3590140.3629121(275-287)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3590140.3629121
Show More Cited By

Index Terms

Partial dead code elimination
1. Software and its engineering
  1. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
2. Theory of computation
  1. Logic
  2. Semantics and reasoning
    1. Program constructs

Recommendations

Partial dead code elimination
PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation

A new aggressive algorithm for the elimination of partially dead code is presented, i.e., of code which is only dead on some program paths. Besides being more powerful than the usual approaches to dead code elimination, this algorithm is optimal in the ...
The power of assignment motion

Assignment motion (AM) and expression motion (EM) are the basis of powerful and at the first sight incomparable techniques for removing partially redundant code from a program. Whereas AM aims at the elimination of complete assignments, a transformation ...
Partial redundancy elimination in SSA form

The SSAPRE algorithm for performing partial redundancy elimination based entirely on SSA form is presented. The algorithm is formulated based on a new conceptual framework, the factored redundancy graph, for analyzing redundancy, and representes the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 29, Issue 6

June 1994

360 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/773473

Guest Editor:
Brent T. Hailpern

Issue’s Table of Contents

PLDI '94: Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation
August 1994
360 pages
ISBN:089791662X
DOI:10.1145/178243
Chairmen:
Vivek Sarkar
IBM Santa Teresa Lab.
,
Barbara Ryder
Rutgers Univ., New Brunswick, NJ
,
Mary Lou Soffa
Univ. of Pittsburgh, Pittsburgh, PA

Copyright © 1994 ACM.

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 1994

Published in SIGPLAN Volume 29, Issue 6

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

158
Total Citations
View Citations
1,927
Total Downloads

Downloads (Last 12 months)261
Downloads (Last 6 weeks)43

Reflects downloads up to 04 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Lee KRen MHoag EShrivastava ASui Y(2024)Optimistic and Scalable Global Function MergingProceedings of the 25th ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3652032.3657575(46-57)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3652032.3657575
Zhong LXiang CHuang HShen BMugnier EZhou Y(2024)Effective Bug Detection with Unused DefinitionsProceedings of the Nineteenth European Conference on Computer Systems10.1145/3627703.3629576(720-735)Online publication date: 22-Apr-2024
https://dl.acm.org/doi/10.1145/3627703.3629576
Mahurkar AWang XZhang HRavindran B(2023)DynaCutProceedings of the 24th International Middleware Conference10.1145/3590140.3629121(275-287)Online publication date: 27-Nov-2023
https://dl.acm.org/doi/10.1145/3590140.3629121
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
Sano TSumikawa Y(2023)Global Store Statement Aggregation2023 IEEE 14th International Symposium on Parallel Architectures, Algorithms and Programming (PAAP)10.1109/PAAP60200.2023.10391749(1-6)Online publication date: 24-Nov-2023
https://doi.org/10.1109/PAAP60200.2023.10391749
Carayon AMartinie CPalanque P(2023)Task Models as a Mean to Identify and Justify Automations in Development Tasks2023 ACM/IEEE International Conference on Model Driven Engineering Languages and Systems Companion (MODELS-C)10.1109/MODELS-C59198.2023.00122(757-764)Online publication date: 1-Oct-2023
https://doi.org/10.1109/MODELS-C59198.2023.00122
Chatterjee PKalita PLahiri SMuduli SSingh VTakhar GRoy S(2023)An Integrated Program Analysis Framework for Graduate Courses in Programming Languages and Software Engineering2023 38th IEEE/ACM International Conference on Automated Software Engineering (ASE)10.1109/ASE56229.2023.00101(598-610)Online publication date: 11-Sep-2023
https://doi.org/10.1109/ASE56229.2023.00101
Zhuang YLin THuang Y(2023)The algorithm and implementation of an extension to LLVM for solving the blocking between instruction sink and division-modulo combineConnection Science10.1080/09540091.2023.227321935:1Online publication date: 30-Oct-2023
https://doi.org/10.1080/09540091.2023.2273219
Ayers HLaufer EMure PPark JRodelo ERossman TPronin ALevis PVan Why JGrosser TLee K(2022)Tighten rust’s belt: shrinking embedded Rust binariesProceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3519941.3535075(121-132)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3519941.3535075
Mantovani AFioraldi ABalzarotti D(2022)Fuzzing with Data Dependency Information2022 IEEE 7th European Symposium on Security and Privacy (EuroS&P)10.1109/EuroSP53844.2022.00026(286-302)Online publication date: Jun-2022
https://doi.org/10.1109/EuroSP53844.2022.00026
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

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

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents