Report Number: CSL-TR-99-782
Institution: Stanford University, Computer Systems Laboratory
Title: A Compiler for Creating Evolutionary Software and Application Experience
Author: Schmidt, Brian K.
Author: Lam, Monica S.
Date: April 1999
Abstract: Recent studies have shown that significant amounts of
value repetition occur in modern applications.
Due to global initialized data, immediate values, address
calculations, redundancy in external input, etc.;
the same value is used at the same program point as much as
80% of the time. Naturally, attention has begun to focus on
how compilers and specialized hardware can take advantage of this
value locality. Unfortunately, there is significant overhead
associated with dynamically recognizing predictable values
and optimizing for them; and all too, this cost dramatically
outweighs the benefits.
There are various levels at which value locality can be observed and
used for optimization, ranging from register value re-use to
function memorization. We are concerned with predictability of
program variable values across multiple runs of a given program.
In this paper we present a complete system that automatically
translates ordinary sequential programs into evolutionary
software, software that evolves to improve its performance
using execution information from previous runs. This concept
can have a significant impact on software engineering, as it
can be used to replace the manual performance tuning phase in the
application development lifecycle. Not only does it alleviate the
developer from a tedious and error-prone task, but it also has
the important side effect of keeping applications free from
obscure hand optimizations which muddle the code and make it
difficult to maintain or port. This concept can also be used
to produce efficient applications where static performance tuning
is not adequate.
Our system automatically identifies targets for program specializations
and instruments the code to gather high-level profiling information.
Upon completion, the program automatically re-compiles itself
when the new profile information suggests that it is profitable. The
programmer is completely unaware of this process, as the software
tailors itself to its environment. We have demonstrated the utility
of our system by using it to optimize graphics applications that
are built upon a general-purpose graphics library. While much of this
work is based on well-established techniques, this is the first
practical system which takes advantage of predictability in a way
such that the overhead does not overwhelm the benefit.