On Copy Avoidance in Single Assignment Languages
Department of Computer Science
University of Arizona
Tucson, AZ 85721, U.S.A.
Copy avoidance refers to the safe replacement, at compile time, of copying operations by destructive updates in single-assignment languages. Conceptually, 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 first component, typically via dataflow analyses to detect when memory cells become dead and may be safely reused. In this paper, we examine 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 efficient polynomial-time approximation algorithm based on graph-matching techniques that produces optimal solutions for most commonly encountered cases of memory reuse.