Optimization Passes for Machine Suif
Laurent Rolaz
What does the term
optimization mean ? it implies that the code produced is optimal. In
reality, the optimizer transforms the intermediate representation in a way that
is believed to improve the program. Typically, improvements focus on the
execution speed of the program. However, other improvements, such as reducing
memory requirements, are also possible. But there is no guarantee that the
resulting code cannot be improved. In fact, it is possible that the optimizer
will make the program worse. Therefore, many tradeoffs must be considered when
designing an optimizer. The fundamental responsibility of the optimizer is to
preserve the observable behavior of the program. In other words, the optimized
program must produce the same results as the unoptimized program for all
possible inputs.
A typical optimizer is organized as a sequence of passes (or optimizations).
Each pass tries to either improve the running time of the program or decrease
its space requirements. Some passes may be repeated in the optimization process.
Each optimization performs a specific task. The optimizations given in this page
are :
- Constant Propagation
- Partial Redundancy Elimination.
- If-Conversion.
Constant Propagation
The goal of constant propagation is to discover values that are constants on all possible executions of a program and to propagate these constants values as far through the program as possible. Expressions whose operands are all constants can be evaluated at compile time and the result propagated further.
Sparse Conditional Constant Propagation (SCCP) is an algorithm developed by Wegman and Zadeck. This variant of constant propagation is a powerful algorithm for determining constants in a single procedure. It can discovers all constants that can be found by evaluating all conditional branches with all constant operands. SCCP operates on particular form of the intermediate representation called the static single assignment form.
Download:
- Constant Propagation Pass (tar.gz) (downloaded 1351 times)
On-line Documentation:
- Implementation of Constant Propagation (pdf)
Partial Redundancy Elimination
Optimizing compiler often attempts to eliminate redundant computations either by removing instructions or by moving instructions to less frequently executed locations. The code removing optimization attempts to determine when two instructions compute the same value, and then decides if one of the instructions can be eliminated. The code motion optimization rely on data-flow analysis to determine the set of locations where each computation will produce the same value and to select the ones that are expected to be least frequently executed.
Lazy Code Motion (LCM) is an algorithm developed by Knoop, Rüthing and Steffen. It is a descendant of partial redundancy elimination that avoids unnecessary code motion.
Download:
- Partial Redundancy Elimination Pass (tar.gz) (downloaded 1203 times)
On-line Documentation:
- Implementation of Partial Redundancy Elimination (pdf)
If-Conversion
If-conversion is a transformation that consits in eliminating branch instructions by introducing conditional instructions. In our approach, partial predicate support is assumed through the select operation. Notice that there is no select opcode in suifvm, so this pass use the opcode ANY to model a select, and then the back-end for a specific architecture should implement these instructions by a specific select instruction. Our task was to develop an algorithm to perform a simple if-conversion to study the improvement of such a transformation. The literature is not plentiful on algorithm that perform if-conversion, so a sketch of solution is given.
Download:
- If-Conversion Pass (tar.gz) (downloaded 1200 times)
On-line Documentation:
- Implementation of If-Conversion (pdf)
A Possible Sequence of these Optimizations
About the author
Laurent Rolaz is the author of these optimization passes which have been written at LAP, EPFL during winter 2002-2003. This work is part of a diploma project.
| Comments
to the webadmin Modified 13-Dec-2007 9:40 (C) EPFL 2000-02 |
 |
