Compiler Tutorial

Compiler Introduction Phase of Compiler Symbol Table Lexical Analyser Evoluation of Programming Language Regular Expression Finite Automata Syntax Analysis Derivation and Parse Tree Bottom – Up Parsing LR parser YACC in Compiler Design LALR 1 Parsing | Compiler Design

Misc

Parsing in Compiler Design Shift Reduce Parsing in Compiler Design Refractive Index and Its types 6 Phases of Compiler Compiler Construction Tools in Compiler Design

Data Flow Analysis in Compiler Design
2020-12-31 10:38:26

Data Flow Analysis in Compiler Design

Data Flow Analysis

All the optimization techniques we have learned earlier depend on data flow analysis. DFA is a technique used to know about how the data is flowing in any control-flow graph.

Example:

Forglobal common sub-expression elimination, we need to find the expression that computes the same value along with any available execution path of the program.

The Data-Flow Analysis Schema

In data flow analysis, a data flow value associates with every program point represents an abstraction for a set of all possible program states for that point.

The domain of this application is a set of possible data flow values.

IN[a]: The data flow value before the statement a.

OUT[a]: The data flow valueafter the statement a.

The main aim of the data flow problem is to find a set of constraints on the IN[a]'s and OUT[a]'s for statements a.

There are two sets of constraints: Transfer function and control-flow constraints.

Transfer Function

The semantic of the statement are the constraints for the data flow values before and after a statement.

For example, if variable x has the value y before executing any statement, say p = x. Then, after the statement's execution, the value for both x and p will be y.

The transfer function is the relationship between the data flow values before and after the assignment statement.

Transfer function comes in two ways:

  • Forward propagation along with execution path
  • Backward propagation up the execution path

Forward Propagation:

The following points should be considered:

  • In forward propagation, the transfer function for any statement s will be represented by Fs.
  • This transfer function takes the data flow values before the statement and produces the output or new data flow value after the statement.
  • So the new data flow values after the statement will be OUT[s] = Fs (IN[s]).

Backward propagation:

The following points should be considered:

  • Backward propagation is the converse of forward propagation.
  • This transfer function converts a data flow value after the statement to a new data flow value before the statement.
  • So the new data flow values will be IN[s] = Fs (OUT[s]).

Control-Flow Constraints

The second set of constraints is derived from the flow of control. If block B consists of statements S1, S2, ........, Sn, then the control flow value of Si will be equal to the control flow values into Si + 1. Which is:

IN [ Si +1 ] = OUT [ Si ], for all i = 1 , 2, .....,n – 1.

Reaching Definition

The most common and useful data flow scheme is Reaching Definition. A definition D reaches the point P along with path following D to P such that D is not killed along the path.

Data Flow Analysis in Compiler Design

Live-Variable Analysis

Here we know about the value of a variable at point p is used from point p to the end. It means that the variable is live at point p; otherwise variable is dead at point p.

This is used for register allocation for basic blocks.

Data Flow Analysis in Compiler Design

Available Expressions

An expression a + b is said to be available at point p if all the path from entry node p evaluates a + b. There should not be any other assignment to a or b.

We can say that block kills expression a + b if it assigns a or b and does not computes a + b.  

The main use of the available expression is to detect global common sub-expression.

Data Flow Analysis in Compiler Design