CSE411: Introduction to Compilers

Data-Flow Analysis

Jooyong Yi (UNIST)

Classifications of Data-Flow Analysis

Classifications of Data-Flow Analysis

Classifications of Data-Flow Analysis

• Today
  • Available expressions
  • Anticipated expressions

Optimize This Code

z = a + b;
y = a * b;
while (y > a + b) {  -- Optimize -->
  a = a + 1;
  x = a + b;
}

Optimize This Code

1: z = a + b;                               t = a + b; z = t;
2: y = a * b;                               y = a * b;
3: while (y > a + b) {  -- Optimize -->     while (y > t) {
4:   a = a + 1;                               a = a + 1; 
5:   x = a + b;                               t = a + b; x = t;
6: }                                        }

Available Expressions

1: z = a + b;                               t = a + b; z = t;
2: y = a * b;                               y = a * b;
3: while (y > a + b) {  -- Optimize -->     while (y > t) {
4:   a = a + 1;                               a = a + 1; 
5:   x = a + b;                               t = a + b; x = t;
6: }                                        }

• At the entry point of line 3, the value of a + b is available.
  • We say that a + b is an available expression at the entry point of line 3.

Available Expressions

• An expression is available at a program point
  • if every path from the entry node of the given CFG to evaluates ,
  • and is not killed (or redefined) along that path.
    • e.g., a + b is killed if a or b is assigned a new value.

Available Expressions

Available Expressions

Available Expressions

• Abstract values:

Available Expressions

• Abstract values: a set of expressions available in the CFG.

Available Expressions

Available Expressions

• • : expressions generated in
  • : expressions killed in

Very Busy Expressions

Optimize This Code

1: x = input;
2: a = x - 1;
3: b = x - 2;
4: while (x > 0) {        -- Optimize -->
5:   output a * b - x;
6:   x = x - 1;
7: }
8: output a * b;

Optimize This Code

1: x = input;                               x = input;
2: a = x - 1;                               a = x - 1;
3: b = x - 2;                               b = x - 2; t = a * b;
4: while (x > 0) {        -- Optimize -->   while (x > 0) {
5:   output a * b - x;                         output t - x;
6:   x = x - 1;                                x = x - 1;
7: }                                        }
8: output a * b;                            output t;

Anticipated Expressions

1: x = input;                               x = input;
2: a = x - 1;                               a = x - 1;
3: b = x - 2;                               b = x - 2; t = a * b;
4: while (x > 0) {        -- Optimize -->   while (x > 0) {
5:   output a * b - x;                         output t - x;
6:   x = x - 1;                                x = x - 1;
7: }                                        }
8: output a * b;                            output t;

• At the exit point of line 3, the expression a * b is anticipated to be used in the future.
  • We say that a * b is an anticipated expression (or a very busy expression) at the exit point of line 3.

Anticipated Expressions

• An expression is anticipated at a program point
  • if all paths departing from eventually is used,
  • and is not killed (redefined) before reaching .

Anticipated Expressions

Anticipated Expressions

• • : expressions generated in
  • : expressions killed in

Reflection

• _____ analysis computes information about future behavior.
  (1) Forward
  (2) Backward

Reflection

• Backward analysis computes information about future behavior.
• Forward analysis computes information about past behavior.

Reflection

• _____ analysis computes over-approximate information.
  (1) May
  (2) Must

Reflection

• May analysis computes over-approximate information.
  • Information that is possibly true
• Must analysis computes over-approximate information.
  • Information that is definitely true

Reflection

• Ingredients of Data-flow analysis

  • Control flow graph (CFG)
  • Data-flow equations
  • Abstract Values
  • Fixed-point algorithm

• Does a fixed-point algorithm always converge?

  • Yes
  • No

Interval Analysis

... if (buf[i] > x) ...

• Abstract values:
  • The abstract size of the buffer
  • The abstract value of x

Interval Analysis

... if (buf[i] > x) ...

• Abstract values:
  • The interval to represent the size of the buffer
  • The interval to represent the abstract value of x

Interval Analysis

• At the exit of B3
  • The interval of :
    • [0,0] [0,1] [0,2]

Abstract Values of Interval Analysis

Abstract Values of Available Expression Analysis