CSE411: Introduction to Compilers

Optimization

Jooyong Yi (UNIST)

Optimization Passes

       |--------------|         |--------------|         |--------------|
IR1 →  | Optimization | → IR2 → | Optimization | → IR3 → | Optimization | → ... 
       |    Pass 1    |         |    Pass 2    |         |    Pass 3    |
       |--------------|         |--------------|         |--------------|

Optimization Examples

Optimization Example

x = (2+3) * y; -- Optimization --> 

Optimization Example

x = (2+3) * y; -- Optimization --> x = 5 * y;

Constant Folding

• If operands are known at compile type, perform the operation statically.

x = (2+3) * y; -- Optimization --> x = 5 * y;

Constant Folding

    x = c1 ⊙ c2     c1 ⊙ c2 = c3
 --------------------------------  c1, c2, and c3 are constants
          x = c3

Optimization Example

x = 5;
y = x * 2;  -- Optimization --> 
z = a[y];

Optimization Example

x = 5;
y = x * 2;  -- Optimization --> y = 5 * 2;
z = a[y];                       z = a[y];

Optimization Example

x = 5;
y = x * 2;  -- Optimization --> y = 5 * 2;  -- Optimization --> z = a[10];
z = a[y];                       z = a[y];

Constant Propagation

• In y = x * 2, x is a constant. Thus, propagate the value of x to y = x * 2.
• If the value of a variable is known to be a constant, replace the use of the variable by that constant.

x = 5;
y = x * 2;  -- Optimization --> y = 5 * 2;  -- Optimization --> z = a[10];
z = a[y];                       z = a[y];

Optimization Example

i = j;
a = 4 * i;                 -- Optimization --> 
... i is not changed ...
c = 4 * i;

Optimization Example

i = j;                                           i = j;
a = 4 * i;                 -- Optimization -->   t = 4 * i; a = t;
... i is not changed ...                         ... i is not changed ...
c = 4 * i;                                       c = t;

Optimization Example

i = j;
a = 4 * i;
if (a > 0) {
    i = i + 1;  -- Optimization --> 
    b = 4 * i;
} 
c = 4 * i;

Optimization Example

i = j;                                  i = j;
a = 4 * i;                              t = 4 * i; a = t;
if (a > 0) {                            if (a > 0) {
    i = i + 1;  -- Optimization -->         i = i + 1;
    b = 4 * i;                              t = 4 * i; b = t;
}                                       }
c = 4 * i;                              c = t;

Common Subexpression Elimination

• 4 * i is a common subexpression
• Once 4 * i is computed, there is no need to re-compute it.
• If an expression is available at a point where it is evaluated, it need not be re-computed.

i = j;                                           i = j;
a = 4 * i;                 -- Optimization -->   t = 4 * i; a = t;
... i is not changed ...                         ... i is not changed ...
c = 4 * i;                                       c = t;

Optimization Example

i = j;                  i = j;
a = 4 * i;        -->   t = 4 * i; a = t;
if (a > 1) {            if (a > 1) {
    b = 10;                 b = 10;
}                       } 
c = 4 * i;              c = t;

Optimization Example

i = j;                  i = j;                   i = j;
a = 4 * i;        -->   t = 4 * i; a = t;   -->  t = 4 * i; a = t;
if (a > 1) {            if (a > 1) {             if (t > 1) {
    b = 10;                 b = 10;                 b = 10;
}                       }                        }
c = 4 * i;              c = t;                   c = t;

Copy Propagation

• After the copy statement a = t, replace all uses of a by t, unless a is re-defined.

a = t;          --> a = t;
if (a > 1) ...      if (t > 1) ...

Optimization Example

i = j;                  i = j;                   i = j;                 
a = 4 * i;        -->   t = 4 * i; a = t;   -->  t = 4 * i; a = t; -->  
if (a > 1) {            if (a > 1) {             if (t > 1) {           
    b = 10;                 b = 10;                 b = 10;             
}                       }                        }                      
c = 4 * i;              c = t;                   c = t;                 

Optimization Example

i = j;                  i = j;                   i = j;                 i = j;
a = 4 * i;        -->   t = 4 * i; a = t;   -->  t = 4 * i; a = t; -->  t = 4 * i;
if (a > 1) {            if (a > 1) {             if (t > 1) {           if (t > 1) {
    b = 10;                 b = 10;                 b = 10;               b = 10;
}                       }                        }                      }
c = 4 * i;              c = t;                   c = t;                 c = t;

Dead Code Elimination

• A variable is dead if it is never used after it is defined.
• A variable is live at a point in a program if its value is used eventually.
• Dead code
  • A statement that defines a variable that is dead.
  • Code that is never executed.

...                          ...
a = t;                -->    // a = t;
// a is never used
...                          ...

How to Perform Code Optimization?

Theory and Practice of Compilation

Theory and Practice of Compilation

Why Theory?

         |-------|            |--------|           |----------|        |-----------|
Source → | Lexer | → tokens → | Parser | → parse → | Semantic |→ AST → |   IR      | → IR1
Program  |       |            |        |   tree    | Analyzer |        | Generator |
         |-------|            |--------|           |----------|        |-----------|


       |--------------|         |--------------|         |--------------|          |-------------|
IR1 →  | Optimization | → IR2 → | Optimization | → IR3 → | Optimization | → ... →  |    Code     | → Target
       |    Pass 1    |         |    Pass 2    |         |    Pass 3    |          |  Generator  |   Program
       |--------------|         |--------------|         |--------------|          |-------------| 

• How do you know that the meaning of the target program is the same as the source program?