CSE411: Introduction to Compilers

Reaching Definitions

Jooyong Yi (UNIST)

Livness Analysis and Register Allocation

   IR1   --->  Liveness Analysis ---> Live Variables  -------|
    |                                                        | --> Register Allocation  -->  IR2
    |                                                        |
    ---------------------------------------------------------|

Static Analysis and Code Optimization

   IR1   --->  Static Analysis ---> Information  -------|
    |                                                   | --> Code Optimization  -->  IR2
    |                                                   |
    ----------------------------------------------------|

Liveness Analysis

               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                                                                                                 

• OUT[B] = IN[S]

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

  • : the set of successors of B.

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

Dataflow Analysis

Traverse the control flow graph (CFG) and gather information about what may happen at run time.

               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                                                                                                 

Knobs of Dataflow Analysis

Knobs of Dataflow Analysis

• In liveness analysis, in which direction is the information passed?
  • Forward
  • Backward

               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                                                                                                 

Knobs of Dataflow Analysis

• In liveness analysis, how do we merge the information of multiple paths?
  • Union
  • Intersection

Classifications of Data-Flow Analysis

Classifications of Data-Flow Analysis

Constant Propagation

  B1: x = 1
       ↓
  B2: y = x + 1

Constant Propagation

  B0: y < N  -------------       
        ↓                ↓
  B1: x = 1         B3: x = 0
        ↓                |
  B2: y = x + 1  <--------

Constant Propagation

  B1: x = 1
       ↓
  B2: y = x + 1

  B0: y < N  -------------       
        ↓                ↓
  B1: x = 1         B3: x = 0
        ↓                |
  B2: y = x + 1  <--------

• What information do we need at B2?

Constant Propagation

  B1: x = 1
       ↓
  B2: y = x + 1

  B0: y < N  -------------       
        ↓                ↓
  B1: x = 1         B3: x = 0
        ↓                |
  B2: y = x + 1  <--------

• What information do we need at B2?
  • Where is variable x defined?
  • Is x defined as a constant?

Reaching Definitions Analysis

  B1: x = 1
       ↓  RD(x) = {??}
  B2: y = x + 1

  B0: y < N  -------------------------       
        ↓                            ↓
  B1: x = 1                       B3: x = 0
        ↓   RD(x) = {??}             |
  B2: y = x + 1  <--------------------

Reaching Definitions Analysis

  B1: x = 1
       ↓  RD(x) = {B1}
  B2: y = x + 1

  B0: y < N  -----------------------------       
        ↓                                ↓
  B1: x = 1                       B3: x = 0
        ↓   RD(x) = {B1, B3}             |
  B2: y = x + 1  <------------------------

Reaching Definitions Analysis

  B1: x = 1
       ↓  RD(x) = {B1}
  B2: y = x + 1

  B0: y < N  -----------------------------       
        ↓                                ↓
  B1: x = 1                       B3: x = 0
        ↓   RD(x) = {B1, B3}             |
  B2: y = x + 1  <------------------------

Reaching Definitions Analysis

  B1: x = 1
       ↓  RD(x) = {B1}
  B2: y = x + 1

  B0: y < N  -----------------------------       
        ↓                                ↓
  B1: x = 1                       B3: x = 0
        ↓   RD(x) = {B1, B3}             |
  B2: y = x + 1  <------------------------

Reaching Definitions Analysis

  B1: x = 1
       ↓  RD(x) = {B1}
  B2: y = x + 1

  B0: y < N  -----------------------------       
        ↓                                ↓
  B1: x = 1                       B3: x = 0
        ↓   RD(x) = {B1, B3}             |
  B2: y = x + 1  <------------------------

• A definition of a variable x is an instruction that assigns a value to x.
• A definition reaches a program point
  • if there exists a path from to
  • and is not killed (redefined) along that path.

Components of Dataflow Analysis

• Dataflow values
  • Live Variable Analysis: returns the set of variables that are live at program point .
  • Reaching Definitions Analysis: returns the set of definitions that reach program point .

Components of Dataflow Analysis

• Transfer functions

    * Liveness Analysis                     

      (V - {y}) ∪ {x}
           ↑
      -------------
      | y = x + 1 |
      -------------
           ↑
           V

IN[I] = (OUT[I] - def[I]) ∪ use[I]           

• A transfer function can be defined for each instruction I.

Components of Dataflow Analysis

• Transfer functions

    * Liveness Analysis                     * Reaching Definitions Analysis

      (V - {y}) ∪ {x}                                       V
           ↑                                                ↓
      -------------                                  ----------------
      | y = x + 1 |                                  | d: y = x + 1 |          
      -------------                                  ----------------
           ↑                                                ↓
           V

IN[I] = (OUT[I] - def[I]) ∪ use[I]                      

Components of Dataflow Analysis

• Transfer functions

    * Liveness Analysis                     * Reaching Definitions Analysis

      (V - {y}) ∪ {x}                                       V
           ↑                                                ↓
      -------------                                  ----------------
      | y = x + 1 |                                  | d: y = x + 1 |          
      -------------                                  ----------------
           ↑                                                ↓
           V                                         (V - defs(y)) ∪ {d}

IN[I] = (OUT[I] - def[I]) ∪ use[I]                                 

Components of Dataflow Analysis

• Transfer functions

    * Liveness Analysis                     * Reaching Definitions Analysis

      (V - {y}) ∪ {x}                                       V
           ↑                                                ↓
      -------------                                  ----------------
      | y = x + 1 |                                  | d: y = x + 1 |          
      -------------                                  ----------------
           ↑                                                ↓
           V                                         (V - defs(y)) ∪ {d}

IN[I] = (OUT[I] - def[I]) ∪ use[I]           OUT[I] = (IN[I] - kill[I]) ∪ gen[I]

• gen[I]: the set of definitions generated in I.
• kill[I]: the set of definitions killed in I.

Components of Dataflow Analysis

• Join function (a.k.a., meet operator)

    * Liveness Analysis                     

      (V - {y}) ∪ {x}
           ↑
      -------------
      | y = x + 1 |  <----- V2
      -------------
           ↑
           V1

     OUT[B] = V1 ∪ V2

• OUT[B] = IN[S]

Components of Dataflow Analysis

• Join function (a.k.a., meet operator)

    * Liveness Analysis                     * Reaching Definitions Analysis

      (V - {y}) ∪ {x}                                       V1
           ↑                                                ↓
      -------------                                  ----------------
      | y = x + 1 |  <----- V2                       | d: y = x + 1 |  <----- V2         
      -------------                                  ----------------
           ↑                                                ↓
           V1                                        

    OUT[B] = V1 ∪ V2                            

Components of Dataflow Analysis

• Join function (a.k.a., meet operator)

    * Liveness Analysis                     * Reaching Definitions Analysis

      (V - {y}) ∪ {x}                                       V1
           ↑                                                ↓
      -------------                                  ----------------
      | y = x + 1 |  <----- V2                       | d: y = x + 1 |  <----- V2         
      -------------                                  ----------------
           ↑                                                ↓
           V1                                        

    OUT[B] = V1 ∪ V2                                 IN[B] = V1 ∪ V2

• IN[B] = OUT[P]

Reaching Definitions Analysis

• IN[B] = OUT[P]
• OUT[B] = (IN[B] - kill[B]) gen[B]

  • : the set of predecessors of B.

  • gen[B]: the set of definitions generated in B.

  • kill[B]: the set of definitions killed in B.

Example

• IN[B] = OUT[P]
• OUT[B] = (IN[B] - kill[B]) gen[B]
  • : the set of predecessors of B.

          1: a = 5
             ↓                                 |  n  |  gen(n) | kill(n) |  IN[n]  |  OUT[n] |
          2: c = 1                             |:---:|:-------:|:-------:|:-------:|:-------:|
          ↓                                    |  1  |   {1}   |   {5}   |    ∅    |   {1}   |
  ----->  3: c > a  -------------              |  2  |   {2}   |  {4,6}  |   {1}   |  {1,2}  |          
  |       ↓                     |              |  3  |    ∅    |    ∅    |  {1,2}  |  {1,2}  |          
  |       4: c = c + c          ↓              |  4  |   {4}   |  {2,6}  |  {1,2}  |  {1,4}  |          
  |-------|                 5: a = c - a       |  5  |   {5}   |   {1}   |    ??   |    ??   |          
                                ↓              |  6  |   {6}   |  {2,4}  |  {2,5}  |  {5,6}  |          
                            6: c = 0

Example

• IN[B] = OUT[P]
• OUT[B] = (IN[B] - kill[B]) gen[B]
  • : the set of predecessors of B.

          1: a = 5                                                            Iteration 1
             ↓                                 |  n  |  gen(n) | kill(n) |  IN[n]  |  OUT[n] |
          2: c = 1                             |:---:|:-------:|:-------:|:-------:|:-------:|
          ↓                                    |  1  |   {1}   |   {5}   |    ∅    |   {1}   |
  ----->  3: c > a  -------------              |  2  |   {2}   |  {4,6}  |   {1}   |  {1,2}  |          
  |       ↓                     |              |  3  |    ∅    |    ∅    |  {1,2}  |  {1,2}  |          
  |       4: c = c + c          ↓              |  4  |   {4}   |  {2,6}  |  {1,2}  |  {1,4}  |          
  |-------|                 5: a = c - a       |  5  |   {5}   |   {1}   |  {1,2}  |  {2,5}  |          
                                ↓              |  6  |   {6}   |  {2,4}  |  {2,5}  |  {5,6}  |          
                            6: c = 0

Example

• IN[B] = OUT[P]
• OUT[B] = (IN[B] - kill[B]) gen[B]
  • : the set of predecessors of B.

          1: a = 5                                                            Iteration 1         Iteration 2
             ↓                                 |  n  |  gen(n) | kill(n) |  IN[n]  |  OUT[n] |  IN[n]  |  OUT[n] |
          2: c = 1                             |:---:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
          ↓                                    |  1  |   {1}   |   {5}   |    ∅    |   {1}   |    ∅    |   {1}   |
  ----->  3: c > a  -------------              |  2  |   {2}   |  {4,6}  |   {1}   |  {1,2}  |   {1}   |  {1,2}  |        
  |       ↓                     |              |  3  |    ∅    |    ∅    |  {1,2}  |  {1,2}  |    ??   |    ??   |      
  |       4: c = c + c          ↓              |  4  |   {4}   |  {2,6}  |  {1,2}  |  {1,4}  | {1,2,4} |  {1,4}  |        
  |-------|                 5: a = c - a       |  5  |   {5}   |   {1}   |  {1,2}  |  {2,5}  | {1,2,4} | {2,4,5} |         
                                ↓              |  6  |   {6}   |  {2,4}  |  {2,5}  |  {5,6}  | {2,4,5} |  {5,6}  |         
                            6: c = 0

Example

• IN[B] = OUT[P]
• OUT[B] = (IN[B] - kill[B]) gen[B]
  • : the set of predecessors of B.

          1: a = 5                                                            Iteration 1         Iteration 2
             ↓                                 |  n  |  gen(n) | kill(n) |  IN[n]  |  OUT[n] |  IN[n]  |  OUT[n] |
          2: c = 1                             |:---:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
          ↓                                    |  1  |   {1}   |   {5}   |    ∅    |   {1}   |    ∅    |   {1}   |
  ----->  3: c > a  -------------              |  2  |   {2}   |  {4,6}  |   {1}   |  {1,2}  |   {1}   |  {1,2}  |        
  |       ↓                     |              |  3  |    ∅    |    ∅    |  {1,2}  |  {1,2}  | {1,2,4} | {1,2,4} |      
  |       4: c = c + c          ↓              |  4  |   {4}   |  {2,6}  |  {1,2}  |  {1,4}  | {1,2,4} |  {1,4}  |        
  |-------|                 5: a = c - a       |  5  |   {5}   |   {1}   |  {1,2}  |  {2,5}  | {1,2,4} | {2,4,5} |         
                                ↓              |  6  |   {6}   |  {2,4}  |  {2,5}  |  {5,6}  | {2,4,5} |  {5,6}  |         
                            6: c = 0

Example

• IN[B] = OUT[P]
• OUT[B] = (IN[B] - kill[B]) gen[B]
  • : the set of predecessors of B.

          1: a = 5                                                            Iteration 1         Iteration 2
             ↓                                 |  n  |  gen(n) | kill(n) |  IN[n]  |  OUT[n] |  IN[n]  |  OUT[n] |
          2: c = 1                             |:---:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
          ↓                                    |  1  |   {1}   |   {5}   |    ∅    |   {1}   |    ∅    |   {1}   |
  ----->  3: c > a  -------------              |  2  |   {2}   |  {4,6}  |   {1}   |  {1,2}  |   {1}   |  {1,2}  |        
  |       ↓                     |              |  3  |    ∅    |    ∅    |  {1,2}  |  {1,2}  | {1,2,4} | {1,2,4} |      
  |       4: c = c + c          ↓              |  4  |   {4}   |  {2,6}  |  {1,2}  |  {1,4}  | {1,2,4} |  {1,4}  |        
  |-------|                 5: a = c - a       |  5  |   {5}   |   {1}   |  {1,2}  |  {2,5}  | {1,2,4} | {2,4,5} |         
                                ↓              |  6  |   {6}   |  {2,4}  |  {2,5}  |  {5,6}  | {2,4,5} |  {5,6}  |         
                            6: c = 0

Example

• IN[B] = OUT[P]
• OUT[B] = (IN[B] - kill[B]) gen[B]
  • : the set of predecessors of B.

          1: a = 5                                                            Iteration 1         Iteration 2         Iteration 3
             ↓                                 |  n  |  gen(n) | kill(n) |  IN[n]  |  OUT[n] |  IN[n]  |  OUT[n] |  IN[n]  |  OUT[n] |
          2: c = 1                             |:---:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|
          ↓                                    |  1  |   {1}   |   {5}   |    ∅    |   {1}   |    ∅    |   {1}   |    ∅    |   {1}   |
  ----->  3: c > a  -------------              |  2  |   {2}   |  {4,6}  |   {1}   |  {1,2}  |   {1}   |  {1,2}  |   {1}   |  {1,2}  |
  |       ↓                     |              |  3  |    ∅    |    ∅    |  {1,2}  |  {1,2}  | {1,2,4} | {1,2,4} | {1,2,4} | {1,2,4} | 
  |       4: c = c + c          ↓              |  4  |   {4}   |  {2,6}  |  {1,2}  |  {1,4}  | {1,2,4} |  {1,4}  | {1,2,4} |  {1,4}  |  
  |-------|                 5: a = c - a       |  5  |   {5}   |   {1}   |  {1,2}  |  {2,5}  | {1,2,4} | {2,4,5} | {1,2,4} | {2,4,5} |  
                                ↓              |  6  |   {6}   |  {2,4}  |  {2,5}  |  {5,6}  | {2,4,5} |  {5,6}  | {2,4,5} |  {5,6}  |  
                            6: c = 0