9. Advanced Techniques

Previous Table of Contents Next


Chapter 8
Dominator-Based Optimization

The compiler now begins global optimization. Global optimization is divided into four components: VALUE, DEPEND, RESHAPE, and MOTION, executed in order (Figure 8.1). VALUE simulates the execution of the flow graph. If it can determine that the value or structure of an expression can be simplified, it replaces the expression with a simpler form. DEPEND performs loop restructuring using dependence-based optimizations. It relies on the simplifications performed by VALUE to make dependence analysis more accurate. After loop transformations have been performed, the RESHAPE phase is performed. RESHAPE includes all of the transformations in VALUE together with expression reshaping and strength reduction. RESHAPE prepares for the code motion performed in MOTION. MOTION performs code motion, including moving loads and stores to complete the global optimization portion of the compiler.

This chapter describes the VALUE and RESHAPE phases of the optimizer. VALUE limits its transformations so that DEPEND can operate more effectively. It does not do code motion, because the loop structure may change dramatically in DEPEND, and it does not do strength reduction, because DEPEND relies on the original form of expressions for analyzing subscripts.

RESHAPE includes all of VALUE. It adds strength reduction to modify multiplications in loops to repeated additions. It also applies the distributive and associative laws of arithmetic to integer operations. Several other simplifications are added to improve the flow graph as it is prepared for code motion.

VALUE performs the following transformations. Using the technique of static single assignment (SSA), they are inexpensive and suprisingly effective.

  The compiler can eliminate globally redundant expressions when there is an instance of the expression in a dominator block. This eliminates many of the redundant expressions in the procedure; however, it does not perform code motion. Later, the compiler uses a technique called elimination of partial redundancies to do code motion.


Figure 8.1  Structure of Global Optimizer

  The compiler performs global constant propagation and constant folding. This is performed in two ways. Initially the compiler performs some constant propagation during the construction of the SSA form at the same time that globally redundant expressions are eliminated. Later a full global constant propagation algorithm is performed. For dependence-based optimizations, it is vital that constants are propagated as thoroughly as possible.
  The compiler can perform transformations that are dependent on the branches previously taken in the procedure. During the construction of the SSA form, the compiler maintains a data structure representing knowledge concerning which branches have been taken. Using this information, the compiler can use the results of relational tests to simplify the program. For example, if a previous computation performed the same comparison and took the TRUE branch then this branch will also take the TRUE branch and thus part of the code may be eliminated.
  Dead code is eliminated. Instructions are dead if their evaluation does not contribute to any value seen outside the procedure being compiled.

After dependence-based transformations have been applied, two further dominator-based transformations are applied to prepare the program for partial redundancy elimination:

  The compiler performs strength reduction. The compiler must identify the variables that are incremented by a fixed amount each time through a loop. This information is then used to simplify expensive computations(such as integer multiply) within a loop by replacing the multiplication with an integer addition and updating the value from a previous time through the loop.
  The compiler reshapes integer expressions using the associative and distributive laws of arithmetic to divide an expression into parts that are unchanging in each of the enclosing loops, allowing the later code motion algorithms to move more expressions out of loops.


Previous Table of Contents Next


Building an Optimizing Compiler
Building an Optimizing Compiler
ISBN: 155558179X
EAN: 2147483647
Year: 1997
Pages: 18
Authors: Bob Morgan

flylib.com © 2008-2017.
If you may any questions please contact us: flylib@qtcs.net