Article

Free access

Partial dead code elimination

Authors:

Oliver Rüthing,

Bernhard SteffenAuthors Info & Claims

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

Pages 147 - 158

https://doi.org/10.1145/178243.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

Mao JDing HZhai JMa STsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Merlin: Multi-tier Optimization of eBPF Code for Performance and CompactnessProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651387(639-653)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651387
Fukuhara JTakimoto MGrosser TLee K(2022)Automated kernel fusion for GPU based on code motionProceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3519941.3535078(151-161)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3519941.3535078
Ge TMo ZWu KZhang XLu YGrosser TLee K(2022)RollBin: reducing code-size via loop rerolling at binary levelProceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3519941.3535072(99-110)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3519941.3535072
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

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 ...
Optimal code motion: theory and practice

An implementation-oriented algorithm for lazy code motion is presented that minimizes the number of computations in programs while suppressing any unnecessary code motion in order to avoid superfluous register pressure. In particular, this variant of 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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

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

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]

Sponsors

SIGPLAN: ACM Special Interest Group on Programming Languages

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 June 1994

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

PLDI94

Sponsor:

SIGPLAN

PLDI94: ACM SIGPLAN Conference on Programming Language Design and Implementation

June 20 - 24, 1994

Florida, Orlando, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

158
Total Citations
View Citations
2,012
Total Downloads

Downloads (Last 12 months)318
Downloads (Last 6 weeks)58

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Mao JDing HZhai JMa STsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)Merlin: Multi-tier Optimization of eBPF Code for Performance and CompactnessProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 310.1145/3620666.3651387(639-653)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620666.3651387
Fukuhara JTakimoto MGrosser TLee K(2022)Automated kernel fusion for GPU based on code motionProceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3519941.3535078(151-161)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3519941.3535078
Ge TMo ZWu KZhang XLu YGrosser TLee K(2022)RollBin: reducing code-size via loop rerolling at binary levelProceedings of the 23rd ACM SIGPLAN/SIGBED International Conference on Languages, Compilers, and Tools for Embedded Systems10.1145/3519941.3535072(99-110)Online publication date: 14-Jun-2022
https://dl.acm.org/doi/10.1145/3519941.3535072
Stirling SRocha RHazelwood KLeather HO'Boyle MPetoumenos PLee J(2022)F3MProceedings of the 20th IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO53902.2022.9741269(242-253)Online publication date: 2-Apr-2022
https://dl.acm.org/doi/10.1109/CGO53902.2022.9741269
Sesin IBolbakov R(2021)Comparative analysis of software optimization methods in context of branch predication on GPUsRussian Technological Journal10.32362/2500-316X-2021-9-6-7-159:6(7-15)Online publication date: 2-Dec-2021
https://doi.org/10.32362/2500-316X-2021-9-6-7-15
Rodríguez FCastro LAronis SBieniusa A(2021)Detecting oxbow code in Erlang codebases with the highest degree of certaintyProceedings of the 20th ACM SIGPLAN International Workshop on Erlang10.1145/3471871.3472961(28-40)Online publication date: 18-Aug-2021
https://dl.acm.org/doi/10.1145/3471871.3472961
Howar FJasper MMues MSchmidt DSteffen B(2021)The RERS challenge: towards controllable and scalable benchmark synthesisInternational Journal on Software Tools for Technology Transfer10.1007/s10009-021-00617-zOnline publication date: 24-Jun-2021
https://doi.org/10.1007/s10009-021-00617-z
Tsai CSon JJain BMcAvey JPopa RPorter DCapkun SRoesner F(2020)CivetProceedings of the 29th USENIX Conference on Security Symposium10.5555/3489212.3489241(505-522)Online publication date: 12-Aug-2020
https://dl.acm.org/doi/10.5555/3489212.3489241
Rocha RPetoumenos PWang ZCole MLeather HDonaldson ATorlak E(2020)Effective function merging in the SSA formProceedings of the 41st ACM SIGPLAN Conference on Programming Language Design and Implementation10.1145/3385412.3386030(854-868)Online publication date: 11-Jun-2020
https://dl.acm.org/doi/10.1145/3385412.3386030
Sui LDietrich JTahir AFourtounis GRothermel GBae D(2020)On the recall of static call graph construction in practiceProceedings of the ACM/IEEE 42nd International Conference on Software Engineering10.1145/3377811.3380441(1049-1060)Online publication date: 27-Jun-2020
https://dl.acm.org/doi/10.1145/3377811.3380441
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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 Table of Contents