A variation of Knoop, Rüthing, and Steffen's Lazy Code Motion

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.