On Copy Avoidance in Single Assignment Languages

Abstract: Copy avoidance refers to the safe replacement, at compile time, of copying operations by destructive updates in single-assignment languages. Con-ceptually, the problem can be divided into two components: identifying memory cells that can safely be reused at a program point via destructive updating; and deciding how to actually reuse such cells. Most of the work on this problem, to date, has focused on the rst component, typically via data ow analyses to detect when memory cells become dead and may be safely reused. In this paper, we ex-amine the second component of the problem. We give an abstract formulation of the memory reuse problem, show that optimal reuse is NP-complete in general, and give an ecient polynomial-time approximation algorithm based on graph-matching techniques that produces optimal solutions for most commonly encountered cases of memory reuse.