Idea of Data Flow Analysis

We introduce the ide of data-flow analysis

  • a form of semantic analysis

Why it is useful

Automatically derive information about the program

Use this information for:

  • correctness checks (initialization, correct order of operations, absence of errors)
  • safely enabling optimizations

Type Checking versus Data-Flow Analysis

We have seen one kind of semantic analysis - type checking

  • points out type errors, wrong operand application

Example of code fragments

var y : Boolean
var x : Int
x = 0
y = x + 1

another example:

var x : Int
var y : Int
x = 0
y = x + 1

What was rule for type checking a sequence of statements?

Note how type checking rules ignore order of statements

  • Permute the statements - same environment, same type checking result
  • This type of analysis is called flow insensitive

Consider now a different problem: variable initialization

  • ensure that each local variable is initialized before its first use

Compare this method body:

  public void f() {
int x, y;
x = 0;
y = x + 1;
  public void g() {
int x, y;
y = x + 1;
x = 0;
  } variable x might not have been initialized

      y = x + 1;

Variable initialization is flow sensitive data-flow analysis

  • depends on the order of operations

Data-flow analysis is a good framework for checking such flow-sensitive properties

Control-Flow Graphs

Syntax trees are not best medium for analysis

  • evaluation order not obvious from tree
  • many kinds of statements - many cases to handle in analysis

Bytecode or machine code:

  • specific for architecture
  • many kinds of instructions
  • useful information on e.g. types is lost

We therefore introduce control-flow graph representation

  • good for analysis
  • also good for code generation

Example program:

int i = n;
while (i > 1) {
  if (i % 2 == 0) {
    i = i / 2;
  } else {
    i = 3*i + 1;

What is its control-flow graph?

How can we interpret control-flow graph?

  • running it with e.g. n=3

Running the program “abstractly”

  • show that x=0;y=x+1 initialized

Abstractly Interepreting the example CFG