The Power of Assignment Motion

Abstract

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 which is always desirable, the more flexible EM requires temporaries to remove partial redundancies. Based on the observation that a simple program transformation enhances AM to subsume EM, we develop an algorithm that for the first time captures all second order effects between AM and EM transformations. Under usual structural restrictions, the worst case time complexity of our algorithm is essentially quadratic, a fact which explains the promising experience with our implementation. Topics: data flow analysis, program optimization, partially redundant assignment and expression elimination, code motion, assignment motion, bit-vector data flow analyses. 1 Motivation A major source for improving the runtime efficiency of a program is...