CSE411: Introduction to Compilers

Liveness Analysis

Jooyong Yi (UNIST)

Register Allocation

• Two key questions
  • Q1: How to construct the interference graph?
  • Q2: How to assign the registers to the nodes in the interference graph?

Example

v3 = v1 + v2  
v4 = v1 + v3  
ret v4        

• v1 and v2 interfere with each other. Thus, reg(v1) reg(v2)
• v1 and v3 interfere with each other. Thus, reg(v1) reg(v3)

    v1 ------ v2
    | 
    |
    v3        v4

Example

v1 = ...
v2 = ...
// v1 and v2 will be used in the future.
v3 = v1 + v2  
v4 = v1 + v3  
ret v4        

• v1 and v2 interfere with each other. Thus, reg(v1) reg(v2)
• v1 and v3 interfere with each other. Thus, reg(v1) reg(v3)

    v1 ------ v2
    | 
    |
    v3        v4

Example

v1 = ...
v2 = ...
// v1 and v2 will be used in the future.
v3 = v1 + v2  
// v1 and v3 will be used in the future.
v4 = v1 + v3  
ret v4        

• v1 and v2 interfere with each other. Thus, reg(v1) reg(v2)
• v1 and v3 interfere with each other. Thus, reg(v1) reg(v3)

    v1 ------ v2
    | 
    |
    v3        v4

Live Variables

v1 = ...
v2 = ...
// v1 and v2 are live variables here.
v3 = v1 + v2  
// v1 and v3 are live variables here.
v4 = v1 + v3  
ret v4        

• v1 and v2 interfere with each other. Thus, reg(v1) reg(v2)
• v1 and v3 interfere with each other. Thus, reg(v1) reg(v3)

    v1 ------ v2
    | 
    |
    v3        v4

Live Variables

v1 = ...
v2 = ...
// v1 and v2 are live variables here.
v3 = v1 + v2  
// v1 and v3 are live variables here.
v4 = v1 + v3  
ret v4        

• A variable is live at a program point if its current value will be read in the remaining execution.
  • We will modify this definition slightly later.

Live Variable Analysis (Liveness Analysis)

• Live variable analysis computes the set of variables that are live at each program point.

Live Variable Analysis Example

          which variables are live? {??}
    B0: a = 0
        ↓ which variables are live?
    B1: c = 0
        ↓ which variables are live?
    B2: b = a + 1
        ↓ which variables are live?
    B3: c = c + b
        ↓ which variables are live?
    B4: a = b + 2  
        ↓ which variables are live?
    B5: return c                                                                                                      

Live Variable Analysis Example

          which variables are live?
    B0: a = 0
        ↓ which variables are live?
    B1: c = 0
        ↓ which variables are live?
    B2: b = a + 1
        ↓ which variables are live?
    B3: c = c + b
        ↓ which variables are live?
    B4: a = b + 2  
        ↓ which variables are live? {??}
    B5: return c                                                                                                      

Live Variable Analysis Example

          which variables are live?
    B0: a = 0
        ↓ which variables are live?
    B1: c = 0
        ↓ which variables are live?
    B2: b = a + 1
        ↓ which variables are live?
    B3: c = c + b
        ↓ which variables are live?
    B4: a = b + 2  
        ↓ which variables are live? {c}
    B5: return c                                                                                                      

Live Variable Analysis Example

          which variables are live?
    B0: a = 0
        ↓ which variables are live?
    B1: c = 0
        ↓ which variables are live?
    B2: b = a + 1
        ↓ which variables are live?
    B3: c = c + b
        ↓ which variables are live?
    B4: a = b + 2  
        ↓ which variables are live? {c}
    B5: return c                                                                                                      

• IN[B] = use[B]
  • IN[B]: the set of variables live at the beginning of B.
  • use[B]: the set of variables used in B.

Live Variable Analysis Example

          which variables are live?
    B0: a = 0
        ↓ which variables are live?
    B1: c = 0
        ↓ which variables are live?
    B2: b = a + 1
        ↓ which variables are live?
    B3: c = c + b
        ↓ which variables are live? {??}
    B4: a = b + 2  
        ↓ which variables are live? {c}
    B5: return c                                                                                                      

• IN[B] = use[B]
  • IN[B]: the set of variables live at the beginning of B.
  • use[B]: the set of variables used in B.

Live Variable Analysis Example

          which variables are live?
    B0: a = 0
        ↓ which variables are live?
    B1: c = 0
        ↓ which variables are live?
    B2: b = a + 1
        ↓ which variables are live?
    B3: c = c + b
        ↓ which variables are live? {b, c}
    B4: a = b + 2  
        ↓ which variables are live? {c}
    B5: return c                                                                                                      

• IN[B] = use[B] OUT[B]
  • IN[B]: the set of variables live at the beginning of B.
  • use[B]: the set of variables used in B.
  • OUT[B]: the set of variables live at the end of B.
• OUT[B] = IN[S]
  • S is the successor of B.

Live Variable Analysis Example

          which variables are live?
    B0: a = 0
        ↓ which variables are live?
    B1: c = 0
        ↓ which variables are live? {??}
    B2: b = a + 1
        ↓ which variables are live? {b, c}
    B3: c = c + b
        ↓ which variables are live? {b, c}
    B4: a = b + 2  
        ↓ which variables are live? {c}
    B5: return c                                                                                                      

• IN[B] = use[B] OUT[B]
  • IN[B]: the set of variables live at the beginning of B.
  • use[B]: the set of variables used in B.
  • OUT[B]: the set of variables live at the end of B.
• OUT[B] = IN[S]
  • S is the successor of B.

Live Variable Analysis Example

          which variables are live?
    B0: a = 0
        ↓ which variables are live?
    B1: c = 0
        ↓ which variables are live? {a, c}
    B2: b = a + 1
        ↓ which variables are live? {b, c}
    B3: c = c + b
        ↓ which variables are live? {b, c}
    B4: a = b + 2  
        ↓ which variables are live? {c}
    B5: return c                                                                                                      

• IN[B] = use[B] (OUT[B] - def[B])
  • IN[B]: the set of variables live at the beginning of B.
  • use[B]: the set of variables used in B.
  • OUT[B]: the set of variables live at the end of B.
  • def[B]: the set of variables defined in B.
• OUT[B] = IN[S]
  • S is the successor of B.

Live Variable Analysis Example

          which variables are live? ∅
    B0: a = 0
        ↓ which variables are live? {a}
    B1: c = 0
        ↓ which variables are live? {a, c}
    B2: b = a + 1
        ↓ which variables are live? {b, c}
    B3: c = c + b
        ↓ which variables are live? {b, c}
    B4: a = b + 2  
        ↓ which variables are live? {c}
    B5: return c                                                                                                      

• IN[B] = use[B] (OUT[B] - def[B])
  • IN[B]: the set of variables live at the beginning of B.
  • use[B]: the set of variables used in B.
  • OUT[B]: the set of variables live at the end of B.
  • def[B]: the set of variables defined in B.
• OUT[B] = IN[S]
  • S is the successor of B.

Live Variable Analysis Example

               which variables are live? {??}
         B0: a = 0                                                  
             ↓ which variables are live? {??}                        
         B1: c = 0                                                  
             ↓ which variables are live? {??}
   ----- B2: a < N   <----------------------------------------------|      
   |         ↓ which variables are live? {a, c}                     |
   |     B3: b = a + 1                                              |
   |         ↓ which variables are live? {b, c}                     |
   |     B4: c = c + b                                              |
   |         ↓ which variables are live? {b}                        |
   |     B5: a = b + 2 ---------------------------------------------|
   |       
   |           which variables are live? {b}                              
   |---> B6: return b                                                                                                 

• IN[B] = use[B] (OUT[B] - def[B])
• OUT[B] = IN[S]
  • Problem: B2 has more than one successor.
  • OUT[B2] = ??

Live Variables

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

Live Variables

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

Live Variable Analysis Example

               which variables are live? {b}
         B0: a = 0                                                  
             ↓ which variables are live? {a, b}                        
         B1: c = 0                                                  
             ↓ which variables are live? {a, b, c}
   ----- B2: a < N   <----------------------------------------------|      
   |         ↓ which variables are live? {a, c}                     |
   |     B3: b = a + 1                                              |
   |         ↓ which variables are live? {b, c}                     |
   |     B4: c = c + b                                              |
   |         ↓ which variables are live? {b}                        |
   |     B5: a = b + 2 ---------------------------------------------|
   |       
   |           which variables are live? {b}                              
   |---> B6: return b                                                                                                 

• IN[B] = use[B] (OUT[B] - def[B])
• OUT[B] = IN[S]
  • : the set of successors of B.

Iterative Calculation

               which variables are live? {b}
         B0: a = 0                                                  
             ↓ which variables are live? {a, b}                        
         B1: c = 0                                                  
             ↓ which variables are live? {a, b, c}
   ----- B2: a < N   <-----------------------------------------------------|      
   |         ↓ which variables are live? {a} ∪ ({b, c}- {b}) = {a, c}      |
   |     B3: b = a + 1                                                     |
   |         ↓ which variables are live? {b, c} ∪ ({b, c} - {c}) = {b, c}  | 
   |     B4: c = c + b                                                     |
   |         ↓ which variables are live? {b} ∪ ({a,b,c} - {a}) = {b, c}    |
   |     B5: a = b + 2 ----------------------------------------------------|
   |       
   |           which variables are live? {b}                              
   |---> B6: return b                                                                                                 

• IN[B] = use[B] (OUT[B] - def[B])
• OUT[B] = IN[S]

Live Variable Calculation

for each B
  IN[B] := ∅; OUT[B] = ∅

repeat
   for each B
      IN_old[B] = IN[B]; OUT_old[B] = OUT[B];
      OUT[B] = ∪ {IN[S] | S ∈ Successor(B)};
      IN[B] = use[B] ∪ (OUT[B] - def[B]);
until IN[B] = IN_old[B] and OUT[B] = OUT_old[B] for all B;

Live Variable Analysis Summary

• IN[B] = use[B] (OUT[B] - def[B])

• OUT[B] = IN[S]

  • : the set of successors of B.

• use[B]: the set of variables used in B.

• def[B]: the set of variables defined in B.

• Update IN[B] and OUT[B] iteratively until they converge.