Algebraic Simplification and Reduction in Strength
Introduction: In Optimization of Basic Blocks we discussed algebraic identities that could be used to simplify DAG's. These algebraic identities can also be used by a peephole optimizer to eliminate three-address statements such as
x = x 0
x = x * 1
in the peephole.
Similarly, reduction-in-strength transformations can be applied in the peephole to replace expensive operations by equivalent cheaper ones on the target machine. Certain machine instructions are considerably cheaper than others and can often be used as special cases of more expensive operators. For example, x2 is invariably cheaper to implement as x * x than as a call to an exponentiation routine. Fixed-point multiplication or division by a power of two is cheaper to implement as a shift. Floating-point division by a constant can be approximated as multiplication by a constant, which may be cheaper.
Use of Machine Idioms: The target machine may have hardware instructions to implement certain specificoperations efficiently. Detecting situations that permit the use of theseinstructions can reduce execution time significantly. For example, some machineshave auto-increment and auto-decrement addressing modes. These addor subtract one from an operand before or after using its value. The use of themodes greatly improves the quality of code when pushing or popping a stack,as in parameter passing. These modes can also be used in code for statementslike x = x 1.