Accession Number:

ADA179451

Title:

Copy Elimination with Abstract Interpretation

Descriptive Note:

Corporate Author:

STANFORD UNIV CA CENTER FOR LARGE SCALE SCIENTIFIC COMPUTATION

Personal Author(s):

Report Date:

1987-02-01

Pagination or Media Count:

25.0

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.

Subject Categories:

  • Computer Programming and Software

Distribution Statement:

APPROVED FOR PUBLIC RELEASE