Copy Elimination with Abstract Interpretation
Abstract
Copy elimination is an important optimization for implementing functional languages. Though it is related to the problem of copy propagation that has been considered in many compilers and also to storage compaction, the term is used in a more general context where structured values can be updated and the computation tree can be reordered. Because of these two additional possibilities, copy elimination is a hard problem, being undecidable in general. We propose an optimization approach based on abstract interpretation which uses fixpoint iteration for computing address expressions. These address expressions supply the final target for a computation, eliminating the need to copy values through intermediate results. Our work is in the context of a single assignment language called SAL. Our implementation has an operational model for computing address expressions by using reduction rules. Using this, we show that copies present in divide and conquer algorithms like bitonic sort and quicksort can be removed. We evaluate the effectiveness of these optimizations, showing that in many cases, we can come to the efficiency of an imperative language. We present some data on optimising some small tough benchmarks.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1987
- Accession Number
- ADA179451
Entities
People
- John L. Hennessy
- K. Gopinath
Organizations
- Stanford University