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;
}```

Test.java:9: 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) {
System.out.println(i);
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