Compiler Design and Construction - Old Questions

9.  Explain the peephole optimization. Write a three address code for the expression r:= 7*3+9.

Peephole optimization is a simple and effective technique for locally improving target code. This technique is applied to improve the performance of the target program by examining the short sequence of target instructions (called the peephole) and replace these instructions replacing by shorter or faster sequence whenever possible. Peephole is a small, moving window on the target program.

Peephole Optimization Techniques are:

1. Redundant load and store elimination: In this technique the redundancy is eliminated. For e.g.

  Initial code:

    y = x + 5;

    i = y;

    z = i;

    w = z * 3;

  Optimized code:

    y = x + 5;

    i = y;

    w = y * 3; 

2. Constant folding: The code that can be simplified by user itself, is simplified. For e.g.

   Initial code:

        x = 2 * 3;

   Optimized code:

        x = 6;

3.  Strength Reduction: The operators that consume higher execution time are replaced by the operators consuming less execution time. For e.g.

   Initial code:

        y = x * 2;

   Optimized code:

        y = x + x; 

4. Algebraic Simplification: Peephole optimization is an effective technique for algebraic simplification. The statements such as x = x + 0 or x = x * 1 can eliminated by peephole optimization.

5. Machine idioms: The target instructions have equivalent machine instructions for performing some operations. Hence we can replace these target instructions by equivalent machine instructions in order to improve the efficiency. For e.g., some machine have auto-increment or auto-decrement addressing modes that are used to perform add or subtract operations.

Given expression

r:= 7*3+9

Three address code for given expression:

t1 = 7 * 3

t2 = t1 + 9

r = t2