Article

Free access

Avoiding unconditional jumps by code replication

Authors:

Frank Mueller,

David B. WhalleyAuthors Info & Claims

PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation

Pages 322 - 330

https://doi.org/10.1145/143095.143144

Published: 01 July 1992 Publication History

PDF eReader

Abstract

This study evaluates a global optimization technique that avoids unconditional jumps by replicating code. When implemented in the back-end of an optimizing compiler, this technique can be generalized to work on almost all instances of unconditional jumps, including those generated from conditional statements and unstructured loops. The replication method is based on the idea of finding a replacement for each unconditional jump which minimizes the growth in code size. This is achieved by choosing the shortest sequence of instructions as a replacement. Measurements taken from a variety of programs showed that not only the number of executed instructions decreased, but also that the total cache work was reduced (except for small caches) despite increases in code size. Pipelined and superscalar machines may also benefit from an increase in the average basic block size.

References

[1]

M. E. Benitez, J. W. Davidson A Portable Global Optimizer and Linker, Proceedings of the SIGPLAN '88 Symposium on Programming Language Design and Implementation, Atlanta, GA, June 1988, pp. 329-338

Digital Library

Google Scholar

[2]

D. W. Clark, H. M. Levy, Measurement and Analysis of Instruction Use in the VAX-11/780, Proceedings of the 9th Annual Symposium on Computer Architecture, April 1982, pp. 9-17

Digital Library

Google Scholar

[3]

J. W. Davidson, A. M. Holler, A Study of a C Function Inliner, Software, Vol. 18, No. 8, August 1988, pp. 775-790

Digital Library

Google Scholar

[4]

J. W. Davidson, D. B. Whalley, Quick Compilers Using Peephole Optimizations, Software- Practice and Experience, Vol. 19, No. 1, January 1989, pp. 195-203

Digital Library

Google Scholar

[5]

J. W. Davidson, D. B. Whalley, Ease: An Environment for Architecture Study and Experimentation, Proceedings of the SIGMETRICS 1990 Conference on Measurement and Modeling of Computer Systems, May 1990, pp. 259-260

Digital Library

Google Scholar

[6]

R. W. Floyd, Algorithm 97: Shortest Path, Communications of the ACM, Vol. 5, No. 6, June 1962, p. 345

Digital Library

Google Scholar

[7]

M. C. Golumbic, V. Rainish, Instruction Scheduling beyond Basic Blocks, IBM Journal of Research Development, Vol. 34, No. 1, January 1990, pp. 93-97

Digital Library

Google Scholar

[8]

J. L. Hennessy, D. A. Patterson, Computer Architecture: A Quantitative Approach, Morgan Kaufmann, 1990

Digital Library

Google Scholar

[9]

W. W. Hwu, P. P. Chang, Inlining Function Expansion for Compiling C Programs, Proceedings of the ACM SIGPLAN 1989 Conference on Programming Language Design and Implementation, Vol. 24, No. 5, June 1989, pp. 246-257

Digital Library

Google Scholar

[10]

B. L. Peuto, L. J. Shustek, An Instruction Timing Model of CPU Performance, Proceedings of the 4th Annual Symposium on Computer Architecture, March 1977, pp. 165-178

Digital Library

Google Scholar

[11]

E. M. Riseman, C. C. Foster, The Inhibition of Potential Parallelism by Conditional Jumps, IEEE Transactions on Computers, Vol. 21, No. 12, December 1972, pp. 1405-1411

Digital Library

Google Scholar

[12]

A. J. Smith, Cache Memories, Computing Surveys, Vol. 14, No. 3, September 1982, pp. 473-530

Digital Library

Google Scholar

[13]

S. Warshall, A Theorem on Boolean Matrices, Journal of the ACM, No. 9, 1962, pp. 11-12

Digital Library

Google Scholar

Cited By

View all

Murtovi AGeorgakoudis GParasyris KLiao CLaguna ISteffen BGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Enhancing Performance through Control-Flow Unmerging and Loop Unrolling on GPUsProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444819(106-118)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444819
Leopoldseder DStadler LWürthinger TEisl JSimon DMössenböck H(2018)Dominance-based duplication simulation (DBDS): code duplication to enable compiler optimizationsProceedings of the 2018 International Symposium on Code Generation and Optimization - CGO 201810.1145/3179541.3168811(126-137)Online publication date: 2018
https://doi.org/10.1145/3179541.3168811
Leopoldseder DStadler LWürthinger TEisl JSimon DMössenböck HKnoop JSchordan MJohnson TO'Boyle M(2018)Dominance-based duplication simulation (DBDS): code duplication to enable compiler optimizationsProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168811(126-137)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168811
Show More Cited By

Index Terms

Avoiding unconditional jumps by code replication

Recommendations

Avoiding unconditional jumps by code replication

This study evaluates a global optimization technique that avoids unconditional jumps by replicating code. When implemented in the back-end of an optimizing compiler, this technique can be generalized to work on almost all instances of unconditional ...
A compilation technique for software pipelining of loops with conditional jumps

We describe a compilation algorithm for efficient software pipelining of general inner loops, where the number of iterations and the time taken by each iteration may be unpredictable, due to arbitrary if-then-else statements and conditional exit ...
Timing optimization via nest-loop pipelining considering code size

Embedded systems have strict timing and code size requirements. Software pipelining is one of the most important optimization techniques to improve the execution time of loops by increasing the parallelism among successive loop iterations. However, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PLDI '92: Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation

July 1992

352 pages

ISBN:0897914759

DOI:10.1145/143095

Chairman:
Stuart I. Feldman
Bell Communications Research, Morristown, NJ
,
Editor:
Richard L. Wexelblat

ACM SIGPLAN Notices Volume 27, Issue 7
July 1992
352 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/143103
Editor:
Richard Wexelblat
IDA/CDED, Alexandria, VA
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 July 1992

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PLDI92

Sponsor:

SIGPLAN

PLDI92: SIGPLAN 92 Conference on Programming Language Design and Implmentation

June 15 - 19, 1992

California, San Francisco, USA

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

45
Total Citations
View Citations
606
Total Downloads

Downloads (Last 12 months)120
Downloads (Last 6 weeks)19

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Murtovi AGeorgakoudis GParasyris KLiao CLaguna ISteffen BGrosser TDubach CSteuwer MXue JOttoni GQuintão Pereira F(2024)Enhancing Performance through Control-Flow Unmerging and Loop Unrolling on GPUsProceedings of the 2024 IEEE/ACM International Symposium on Code Generation and Optimization10.1109/CGO57630.2024.10444819(106-118)Online publication date: 2-Mar-2024
https://dl.acm.org/doi/10.1109/CGO57630.2024.10444819
Leopoldseder DStadler LWürthinger TEisl JSimon DMössenböck H(2018)Dominance-based duplication simulation (DBDS): code duplication to enable compiler optimizationsProceedings of the 2018 International Symposium on Code Generation and Optimization - CGO 201810.1145/3179541.3168811(126-137)Online publication date: 2018
https://doi.org/10.1145/3179541.3168811
Leopoldseder DStadler LWürthinger TEisl JSimon DMössenböck HKnoop JSchordan MJohnson TO'Boyle M(2018)Dominance-based duplication simulation (DBDS): code duplication to enable compiler optimizationsProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168811(126-137)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168811
Leopoldseder DMurphy G(2017)Simulation-based code duplication for enhancing compiler optimizationsProceedings Companion of the 2017 ACM SIGPLAN International Conference on Systems, Programming, Languages, and Applications: Software for Humanity10.1145/3135932.3135935(10-12)Online publication date: 22-Oct-2017
https://dl.acm.org/doi/10.1145/3135932.3135935
Dong YWang YLau MLin S(2010)Experiments on Test Case Reuse of Test Coverage CriteriaProceedings of the 2010 Symposia and Workshops on Ubiquitous, Autonomic and Trusted Computing10.1109/UIC-ATC.2010.71(277-281)Online publication date: 26-Oct-2010
https://dl.acm.org/doi/10.1109/UIC-ATC.2010.71
Dong YLau MLin S(2008)On Partitioning the Domain for Test Case Reusability (Short Paper)Proceedings of the 2008 The Eighth International Conference on Quality Software10.1109/QSIC.2008.51(264-269)Online publication date: 12-Aug-2008
https://dl.acm.org/doi/10.1109/QSIC.2008.51
Ceccato MTonella PMatteotti C(2008)Goto Elimination Strategies in the Migration of Legacy Code to JavaProceedings of the 2008 12th European Conference on Software Maintenance and Reengineering10.1109/CSMR.2008.4493300(53-62)Online publication date: 1-Apr-2008
https://dl.acm.org/doi/10.1109/CSMR.2008.4493300
Zhuang XZhang TPande S(2006)Using Branch Correlation to Identify Infeasible Paths for Anomaly DetectionProceedings of the 39th Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2006.48(113-122)Online publication date: 9-Dec-2006
https://dl.acm.org/doi/10.1109/MICRO.2006.48
Dall'Osso A(2006)Computer algebra systems as mathematical optimizing compilersScience of Computer Programming10.1016/j.scico.2005.06.00359:3(250-273)Online publication date: 1-Feb-2006
https://dl.acm.org/doi/10.1016/j.scico.2005.06.003
Zhao WKreahling WWhalley DHealy CMueller F(2006)Improving WCET by applying worst-case path optimizationsReal-Time Systems10.1007/s11241-006-8643-434:2(129-152)Online publication date: 1-Oct-2006
https://dl.acm.org/doi/10.1007/s11241-006-8643-4
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

Avoiding unconditional jumps by code replication

A compilation technique for software pipelining of loops with conditional jumps

Timing optimization via nest-loop pipelining considering code size