Abstract
Morel and Renvoise discussed in 1979 a universal method for global code optimization in a compiler. By suppressing partial redundancies their method achieves several optimization techniques - such as moving loop invariant computations out of a loop or deleting redundant computations - at once. Their algorithm moves computations to earlier places in execution paths to eliminate partial redundancies. The movement is controlled by some heuristics.The heuristics and algorithms used by Morel and Renvoise sometimes cause difficulties for practical use. Subsequent papers partly circumvented these difficulties by slightly modifying the heuristics and the algorithms. Knoop, Rüthing, and Steffen published in their paper Lazy Code Motion an optimal algorithm for the elimination of partial redundancies which entirely prevents these difficulties. This paper presents a variant of their algorithm which is better prepared for practical use.
- 1. Dhamdhere, D. M. A Fast Algorithm for Code Movement Optimisation. SIGPLAN Notices 23, 10 (1988), 172-180. Google ScholarDigital Library
- 2. Dhamdhere, D. M. Practical adaption of the global optimization algorithm of Morel and Renvoise. ACM Trans. Program. Lang. Syst. 13, 2 (1991), 291-294. Google ScholarDigital Library
- 3. Drechsler, K.-H., Stadel, M. P. A solution to a problem with Morel and Renvoise's "global optimization by suppression of partial redundancies". ACM Trans. Program. Lang. Syst. 10, 4 (1988), 635-640. Google ScholarDigital Library
- 4. Knoop, J., Rüthing, O., Steffen, B. Lazy code motion. SIGPLAN Notices 27, 7, (1992), 224-234. Google ScholarDigital Library
- 5. Morel, E., and Renvoise, C. Global optimization by suppression of partial redundancies. Commun. ACM 22, 2 (1979), 96-103, 111-126. Google ScholarDigital Library
Index Terms
- A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion
Recommendations
Verified validation of lazy code motion
PLDI '09: Proceedings of the 30th ACM SIGPLAN Conference on Programming Language Design and ImplementationTranslation validation establishes a posteriori the correctness of a run of a compilation pass or other program transformation. In this paper, we develop an efficient translation validation algorithm for the Lazy Code Motion (LCM) optimization. LCM is ...
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 ...
Archeology of Code Duplication: Recovering Duplication Chains from Small Duplication Fragments
SYNASC '05: Proceedings of the Seventh International Symposium on Symbolic and Numeric Algorithms for Scientific ComputingCode duplication is a common problem, and a well-known sign of bad design. As a result of that, in the last decade, the issue of detecting code duplication led to various solutions and tools that can automatically find duplicated blocks of code. However,...
Comments