Static Program Analysis to Enhance Profile Independence in Instruction-Level Parallelism Compilation( PostScript version, PDF version)
Brian L. Deitrich
PhD thesis, Department of Electrical and Computer Engineering, University of Illinois, Urbana, IL, May, 1998
An instruction-level parallelism (ILP) compiler uses aggressive optimizations
to reduce a program's running time. These optimizations have been shown
to be effective when profile information is available. Unfortunately,
it is not always possible for users to profile their programs. In addition,
even if profiling is performed, two other problems can work against the
compiler. First, the conditional branch behavior seen for real executions
may differ from the behavior seen during profiling; second, important code
sections for real executions may be unexercised during profiling.
The objective of this dissertation is to provide a groundwork for an ILP
compiler to effectively deal with all three of these issues through the
use of static program analysis. For the case when no profiling is
performed, this dissertation improves the state of the art in static
branch prediction, and investigates the problems associated with
static loop-trip-count prediction and static frequency generation. For the
case of differing branch behavior, this dissertation proposes the use of
the speculative hedge heuristic during acyclic scheduling. Speculative
hedge minimizes its dependence on profile information through the use of
static analysis, and similar techniques should be developed for other
compiler heuristics. Finally, for the case when important code sections
are unexercised, this dissertation proposes the use of loop grouping.
Loop grouping is a new technique that identifies loops that iterate
with the same loop control in multiple locations of the source code.
These groups are used to statically predict loop behavior for loops
that are untouched during program profiling. In this way, the compiler
can extract information obtained during profiling and apply it to
unexercised code. This allows much stronger predictions to be made
about unexercised loops, potentially leading to better performance.
[ IMPACT Main Page |
Team Members |
Publications |
Software |
FAQ ]