CSE411: Introduction to Compilers

Dataflow Analysis

Jooyong Yi (UNIST)

Classifications of Data-Flow Analysis

Classifications of Data-Flow Analysis

Common-Subexpression Elimination

  B1: c = a + b                             B1: c = a + b
       ↓                      --> 
  B2: x = a + b + 2                         B2: x = c + 2

• What information do we need?

Common-Subexpression Elimination

  B1: c = a + b                             B1: c = a + b
       ↓                      -->                 ↓
  B2: x = a + b                             B2: x = c
       ↓                                          ↓
  B3: y = x + 1                             B3: y = x + 1

• What information do we need?
  • Which sub-expressions are already computed and available at each program point?

Available Expressions Analysis

• An expression is available at a program point if it has been computed and its value is not changed before that point.

  B1: c = a + b
       ↓  AE = {a + b}
  B2: x = a + b

Available Expressions Analysis

• An expression is available at a program point if it has been computed and its value is not changed before that point.

  B1: c = a + b
       ↓  AE = {a + b}
  B2: a = 1
       ↓  AE = {??}
  B3: x = a + b

Available Expressions Analysis

• An expression is available at a program point if it has been computed and its value is not changed before that point.

  B1: c = a + b
       ↓  AE = {a + b}
  B2: a = 1
       ↓  AE = {}
  B3: x = a + b

Available Expressions Analysis

• An expression is available at a program point if it has been computed and its value is not changed before that point.

  B0: y < N  -------------------------       
        ↓                            ↓
  B1: c = a + b                    B4: d = a + b
        ↓                            ↓
  B2: w = x + y                    B5: w = x - y 
        ↓   AE = {??}                |
  B3: z = a + b  <--------------------
        ↓
  B6: v = z + x + y

Available Expressions Analysis

• An expression is available at a program point if it has been computed and its value is not changed before that point.

  B0: y < N  -------------------------       
        ↓                            ↓
  B1: c = a + b                    B4: d = a + b
        ↓                            ↓
  B2: w = x + y                    B5: w = x - y 
        ↓   AE = {a+b}               |
  B3: z = a + b  <--------------------
        ↓
  B6: v = z + x + y

Available Expressions Analysis

Available Expressions Analysis

Available Expressions Analysis

• Dataflow values
• Transfer function
• Join function

Available Expressions Analysis

• Dataflow values
  • returns the set of available expressions that reach program point .
• Transfer function
• Join function

Available Expressions Analysis

• Dataflow values
  • returns the set of available expressions that reach program point .
• Transfer function
• Join function
  • IN[B] = OUT[P]

Available Expressions Analysis

• Transfer function
  • OUT[I] = (IN[I] - kill[I]) ∪ gen[I]

Available Expressions Analysis

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

Classifications of Data-Flow Analysis

Very Busy Expressions Analysis

Very Busy Expressions Analysis

• Dataflow values
  • returns the set of very busy expressions that reach program point .
• Transfer function
  • IN[B] = (OUT[B] - kill[B]) gen[B]
• Join function
  • OUT[B] = IN[S]

Using Very Busy Expressions Analysis

                                                                 0: t = a * b
          ↓ VBE = {a * b}                                        ↓
  ----->  1: c > a  -------------                        ----->  1: c > a  -------------
  |       ↓                     |              --->      |       ↓                     |
  |       2: c = a * b          ↓                        |       2: c = t              ↓              
  |-------|                 3: d = a * b                 |-------|                 3: d = t