Global data flow analysis

• To efficiently optimize the code compiler collects all the information about the program and distribute this information to each block of the flow graph. This process is known as data-flow graph analysis.
• Certain optimization can only be achieved by examining the entire program. It can't be achieve by examining just a portion of the program.
• For this kind of optimization user defined chaining is one particular problem.
• Here using the value of the variable, we try to find out that which definition of a variable is applicable in a statement.

Based on the local information a compiler can perform some optimizations. For example, consider the following code:

1. x = a + b;  
2.    x = 6 * 3  

• In this code, the first assignment of x is useless. The value computer for x is never used in the program.
• At compile time the expression 6*3 will be computed, simplifying the second assignment statement to x = 18;

Some optimization needs more global information. For example, consider the following code:

1. a = 1;  
2.    b = 2;  
3.    c = 3;  
4.    if (....) x = a + 5;  
5.    else x = b + 4;  
6.    c = x + 1;  

In this code, at line 3 the initial assignment is useless and x +1 expression can be simplified as 7.

But it is less obvious that how a compiler can discover these facts by looking only at one or two consecutive statements. A more global analysis is required so that the compiler knows the following things at each point in the program:

• Which variables are guaranteed to have constant values
• Which variables will be used before being redefined

Data flow analysis is used to discover this kind of property. The data flow analysis can be performed on the program's control flow graph (CFG).

The control flow graph of a program is used to determine those parts of a program to which a particular value assigned to a variable might propagate.