Article

Free access

Lazy code motion

Authors:

Oliver Rüthing,

Bernhard SteffenAuthors Info & Claims

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

Pages 224 - 234

https://doi.org/10.1145/143095.143136

Published: 01 July 1992 Publication History

Abstract

We present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. The point of our algorithm is the decomposition of the bi-directional structure of the known placement algorithms into a sequence of a backward and a forward analysis, which directly implies the efficiency result. Moreover, the new compositional structure opens the algorithm for modification: two further uni-directional analysis components exclude any unnecessary code motion. This laziness of our algorithm minimizes the register pressure, which has drastic effects on the run-time behaviour of the optimized programs in practice, where an economical use of registers is essential.

References

[1]

Aho, A. V., and Ullman, J.D. Node listings for reducible flow graphs. In Proceedings ?~h STOC, 1975, 177- 185.

[2]

Chow, F. A portable machine independent optimizer- Design and measurements. Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, Stanford, Calif., and Tech. Rep. 83-254, Computer Systems Lab., Stanford University, 1983.

[3]

Dhamdhere, D.M. Characterization of program loops in code optimization. Comp. Lang. 8, 2 (1983), 69- 76.

[4]

Dhamdhere, D.M. A fast algorithm for code movement optimization. S~GPLAN Not. 23, 10 (xgss), 172- is0

[5]

Dhamdhere, D.M. Practical adaptation of the global optimization algorithm of Morel and Renvoise. A CM Trans. Program. Lang. Syst. ~3, 2 (~99~), 29~- 294.

Digital Library

[6]

Drechsler, K. H., and Stadel, M.P. A solution to a problem with Morel and Renvoise's "Global optimization by suppression of partial redundancies". A CM Trans. Program. Lang. Syst. 10, 4 (1988), 635 - 640.

[7]

Graham, S. L., and Wegman, M. A fast and usually linear algorithm for global flow analysis. Journal of the ACM 23, 1 (1976), 172- 202.

Digital Library

[8]

Itecht, M.S. Flow analysis of computer programs. Elsevier, North-Holland, 1977.

[9]

Hecht, M. S., and Ullman, J.D. Analysis of a simple algorithm for global flow problems. In Proceedings 1st POPL, Boston, Massachusetts, 1973, 207- 217.

[10]

Hecht, M. S., and Ullman, J.D. A simple algorithm for global data flow analysis problems. In SIAM J. Comput. d, 4 (1977), 519- 532.

[11]

Joshi, S. M., and Dhamdhere, D.M. A composite hoisting-strength reduction transformation for global program optimization- part I. Internat. J. Computer Maih. 11, (1982), 21 - 41.

[12]

Joshi, S. M., and Dhamdhere, D.M. A composite hoisting-strength reduction transformation for global program optimization- part II. Internat. J. Computer Math. 11, (1982), 111- 126.

[13]

Kennedy, K. Node listings applied to data flow analysis. In Proceedings ~d POPL, Palo Alto, California, 1975, 10- 21.

[14]

Knoop, J., Riithing, O., and Steffen, B. Lazy strength reduction. To appear.

[15]

Knoop, J., and Steffen, B. The interprocedurM coincidence theorem. Aachener Informafik- Berichte Nr. 9127, Rheinisch-Westfiilische Technische Hochschule Aachen, Aachen, 1991.

[16]

Knoop, J., and Steffen, B. Efficient and optimal interprocedural bit-vector data flow analyses: A uniform interprocedural framework. To appear.

[17]

Kam, J. B., and Ullman, J.D. Global data flow analysis and iterative algorithms, journal o/the ACM 23, 1 (1976), 158- 171.

Digital Library

[18]

Kam, J. B., and Ullman, j.D. Monotone data flow analysis frameworks. Acta Informatica 7, (1977), 309- 317.

[19]

Morel, E. Data flow analysis and global optimization. In: Lorho, B. (Ed.). Methods and tools for compiler construction, Cambridge University Press, 1984.

[20]

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

[21]

Morel, E., and Renvoise, C. Interprocedural elimination of partial redundancies. In: Muchnick, St. S., and Jones, N. D. (Eds.). Program flow analysis: Theory and applications. Prentice Hall, Englewood Cliffs, NJ, 1981.

[22]

Rosen, B. K., Wegman, M. N., and Zadeck,F. K. Global value numbers and redundant computations. In Proceedings 15th POPL, San Diego, California, 1988, 12- 27.

[23]

Sorkin, A. Some comments on A solution to a problem with Morel and Renvoise's "Global optimization by suppression of partial redundancies''. A CM Trans. Program. Lang. $yst. 11,4 (1989), 666- 668.

[24]

Steffen, B. Data flow analysis as model checking. In Proceedings TACS'91, Sendai, Japan, Springer-Verlag, LNCS 526 (1991), 346 .-364.

[25]

Steffen, B., Knoop, J., and Riithing, O. The value flow graph: A program representation for optimal program transformations. In Proceedings 3~d E$OP, Copenhagen, Denmark, Springer-Verlag, LNCS 432 (1990), 389 .-405.

[26]

Steffen, B., Knoop, J., and Riithing, O. Efficient code motion and an adaption to strength reduction. In Proceedings ~ta TAP- SOFT, Brighton, United Kingdom, Springer- Verlag, LNCS 494 (1991), 394- 415.

[27]

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

[28]

Tarjan, R.E. A unified approach to path problems. Journal of the A CM 28, 3 (1981), 577- 593.

[29]

Tarjan, R.E. Fast algorithms for solving path problems. Journal of the A CM 28, 3 (:1981), 594- 614.

[30]

Ullman, J.D. Fast algorithms for the elimination of common subexpressions. Acia Informaiica 2, 3 (1973), 191- 213.

Cited By

Ferrara PArceri VCortesi A(2024)Challenges of software verification: the past, the present, the futureInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-024-00765-y26:4(421-430)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s10009-024-00765-y
Yanase YSumikawa Y(2023)Lazy Demand-driven Partial Redundancy EliminationJournal of Information Processing10.2197/ipsjjip.31.45931(459-468)Online publication date: 2023
https://doi.org/10.2197/ipsjjip.31.459
Bračevac OWei GJia SAbeysinghe SJiang YBao YRompf T(2023)Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect DependenciesProceedings of the ACM on Programming Languages10.1145/36228137:OOPSLA2(400-430)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622813
Show More Cited By

Index Terms

Lazy code motion
1. Software and its engineering
  1. Software creation and management
    1. Designing software
      1. Software implementation planning
        Software design techniques
    2. Software development process management
  2. Software notations and tools
    1. Compilers
    2. General programming languages
      1. Language features
2. Theory of computation
  1. Semantics and reasoning
    1. Program constructs

Recommendations

Lazy code motion

We present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. The point of our algorithm is the decomposition of the bi-directional structure of ...
Lazy code motion
20 Years of the ACM SIGPLAN Conference on Programming Language Design and Implementation 1979-1999: A Selection

We present a bit-vector algorithm for the optimal and economical placement of computations within flow graphs, which is as efficient as standard uni-directional analyses. The point of our algorithm is the decomposition of the bi-directional structure of ...
Lazy-Merge: A Novel Implementation for Indexed Parallel $K$-Way In-Place Merging

Merging sorted segments is a core topic of fundamental computer science that has many different applications, such as $n$ -body simulation. In this research, we propose Lazy-Merge, a novel implementation of sequential in-place $k$ -way merging algorithms, that ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

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

Copyright © 1992 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 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

236
Total Citations
View Citations
2,206
Total Downloads

Downloads (Last 12 months)413
Downloads (Last 6 weeks)131

Reflects downloads up to 01 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Ferrara PArceri VCortesi A(2024)Challenges of software verification: the past, the present, the futureInternational Journal on Software Tools for Technology Transfer (STTT)10.1007/s10009-024-00765-y26:4(421-430)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1007/s10009-024-00765-y
Yanase YSumikawa Y(2023)Lazy Demand-driven Partial Redundancy EliminationJournal of Information Processing10.2197/ipsjjip.31.45931(459-468)Online publication date: 2023
https://doi.org/10.2197/ipsjjip.31.459
Bračevac OWei GJia SAbeysinghe SJiang YBao YRompf T(2023)Graph IRs for Impure Higher-Order Languages: Making Aggressive Optimizations Affordable with Precise Effect DependenciesProceedings of the ACM on Programming Languages10.1145/36228137:OOPSLA2(400-430)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622813
Gourdin LBonneau BBoulmé SMonniaux DBérard A(2023)Formally Verifying Optimizations with Block SimulationsProceedings of the ACM on Programming Languages10.1145/36227997:OOPSLA2(59-88)Online publication date: 16-Oct-2023
https://dl.acm.org/doi/10.1145/3622799
Gourdin LJul ERacordon D(2023)Lazy Code Transformations in a Formally Verified CompilerProceedings of the 18th ACM International Workshop on Implementation, Compilation, Optimization of OO Languages, Programs and Systems10.1145/3605158.3605848(3-14)Online publication date: 17-Jul-2023
https://dl.acm.org/doi/10.1145/3605158.3605848
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
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
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
Jaiswal SKhedker UChakraborty S(2020)Bidirectionality in flow-sensitive demand-driven analysisScience of Computer Programming10.1016/j.scico.2020.102391(102391)Online publication date: Jan-2020
https://doi.org/10.1016/j.scico.2020.102391
Barua PZhao JSarkar V(2020)OmpMemOpt: Optimized Memory Movement for Heterogeneous ComputingEuro-Par 2020: Parallel Processing10.1007/978-3-030-57675-2_13(200-216)Online publication date: 24-Aug-2020
https://dl.acm.org/doi/10.1007/978-3-030-57675-2_13
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 Table of Contents