CSE411: Introduction to Compilers

Liveness Analysis

Jooyong Yi (UNIST)

Our Goal

       |--------------|       
IR  →  | Optimization | → Optimized IR
       |     Pass     |       
       |--------------|       

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
...                          ...

Liveness Analysis

• A variable is live at a program point if its current value may be read in the remaining execution.

x = i + j;
// x is live      
y = x + 1;      
// x is dead
x = j - k;      
exit;

Liveness Analysis

• A variable is live at a program point if its current value may be read in the remaining execution.

x = i + j;
// x is live. which x?      
y = x + 1;      
// x is dead. which x?
x = j - k;      
// x is live. which x?
z = x * x;      
// x is dead. which x?
exit;

Liveness Analysis

• A variable is live at a program point if its current value may be read in the remaining execution.

x = i + j;                   x1 = i1 + j1;
// x is live. which x?       // x1 is live.
y = x + 1;                   y1 = x1 + 1;
// x is dead. which x?   →   // x1 is dead
x = j - k;                   x2 = j1 - k1;
// x is live. which x?       // x2 is live
z = x * x;                   z1 = x2 * x2;
// x is dead. which x?       // x2 is dead
exit;

Static Single Assignment (SSA) Form

• Each variable has only one definition in the program text.

x = i + j;                   x1 = i1 + j1;
// x is live. which x?       // x1 is live.
y = x + 1;                   y1 = x1 + 1;
// x is dead. which x?   →   // x1 is dead
x = j - k;                   x2 = j1 - k1;
// x is live. which x?       // x2 is live
z = x * x;                   z1 = x2 * x2;
// x is dead. which x?       // x2 is dead
exit;                        exit;

Static Single Assignment (SSA) Form

• Each variable has only one definition in the program text.

   x = i + j;               x1 = i1 + j1;
   if x < y goto L;  →      if x1 < y1 goto L;
   y = x + 1;               y1 = x1 + 1;
   x = j - k;               x2 = j1 - k1;
L: z = x * x;            L: z1 = ??        // which x? 
   exit;                    exit;

Static Single Assignment (SSA) Form

• Each variable has only one definition in the program text.

   x = i + j;               x1 = i1 + j1;
   if x < y goto L;  →      if x1 < y1 goto L;
   y = x + 1;               y1 = x1 + 1;
   x = j - k;               x2 = j1 - k1;
L: z = x * x;            L: x3 = φ(x1, x2); // φ function 
   exit;                    z1 = x3 * x3;
                            exit;

Static Single Assignment (SSA) Form

• Each variable has only one definition in the program text.
• It is not a Dynamic Single Assignment Form.

   a = 0;                    a1 = 0;
L: b = a + 1;             L: a3 = φ(a1, a2);
   c = c + b;         →      b1 = φ(b0, b2);
   a = b * 2;                c2 = φ(c0, c1);
   if a < N goto L;          b2 = a3 + 1;
   exit;                     c1 = c2 + b2;
                             a2 = b2 * 2;
                             if a2 < N goto L;
                             exit;                    

Liveness Analysis

• A variable is live at a program point if its current value may be read in the remaining execution.

   x1 = i1 + j1;
   // x1 is live
   if x1 < y1 goto L;
   // x1 is live
   y1 = x1 + 1;
   // y1 is dead, x1 is live
   x2 = j1 - k1;
   // x1 and x2 are live
L: x3 = φ(x1, x2);
   // x3 is live
   z1 = x3 * x3;
   exit;

• Which representation (data structure) is better for liveness analysis?

Control Flow Graph (CFG)

Control Flow Graph (CFG)

• A CFG consists of the following:
  • A set of basic blocks
    • Basic block is a straight-line piece of code without any jumps.
  • A set of edges
    • Each edge connects between basic blocks.
  • A single entry basic block
  • A single exit baisc block

Liveness Analysis

Liveness Analysis

• Backward analysis

Liveness Analysis

• A variable is live at a program point if its current value may be read in the remaining execution.

Liveness Analysis

• May analysis

Data-Flow Analysis

• Liveness analysis is an instance of data-flow analysis.
• Data-flow analysis is a general framework for static analysis.

Liveness Analysis as Data-Flow Analysis

• • represents the set of successors of .

Liveness Analysis as Data-Flow Analysis

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)

: at the 0-th iteration

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)

Liveness Analysis as Data-Flow Analysis (with Loop)