Copy Elimination for Parallelizing Compilers
David J. Kolson6, Alexandru Nicolau6 and Nikil Dutt6
| (6) |
Dept. of Information and Computer Science, University of California, Irvine, Irvine, CA 92697, USA |
Abstract
Techniques for aggressive optimization and parallelization of applications can have the side-effect of introducing copy instructions,
register-to-register move instructions, into the generated code. This preserves program correctness while avoiding the need
for global search-and-update of registers. However, copy instructions only transfer data between registers while requiring
the use of system resources (ALUs) and are essentially overhead operations which can potentially limit performance. Conventional
copy propagation and copy removal techniques are not powerful enough to remove these copies as, during loop parallelization,
the lifetimes of the values copied may span over loop boundaries. In this paper, we present a technique for copy removal that
incrementally unrolls a loop body and re-allocates registers to values so that no copy operations are required. We also present
a heuristic version that limits the amount of unrolling and present experimentation that demonstrates the necessity of copy
removal in gaining improved code performance.
This work supported in part by ONR grant N000149311348 and ARPA grant MDA904-96-C-1472.
References secured to subscribers.