CSE411

CSE411: Introduction to Compilers

Liveness Analysis

Jooyong Yi (UNIST)

2023 Spring
CSE411

Our Goal

       |--------------|       
IR  →  | Optimization | → Optimized IR
       |     Pass     |       
       |--------------|       
2023 Spring
CSE411

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
...                          ...
2023 Spring
CSE411

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;
2023 Spring
CSE411

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;
2023 Spring
CSE411

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;
2023 Spring
CSE411

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;
2023 Spring
CSE411

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;
2023 Spring
CSE411

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;
2023 Spring
CSE411

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;                    
2023 Spring
CSE411

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?
2023 Spring
CSE411

Control Flow Graph (CFG)

2023 Spring
CSE411

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
2023 Spring
CSE411

Liveness Analysis

2023 Spring
CSE411

Liveness Analysis

  • Backward analysis
2023 Spring
CSE411

Liveness Analysis

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

2023 Spring
CSE411

Liveness Analysis

  • May analysis
2023 Spring
CSE411

Data-Flow Analysis

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

Liveness Analysis as Data-Flow Analysis

    • represents the set of successors of .
2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

: at the 0-th iteration

node use def
2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def

2023 Spring
CSE411

Liveness Analysis as Data-Flow Analysis (with Loop)

node use def