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

Related Topics

Compiler Design Tutorial

Our compiler design tutorial will provide all the information about compiler from basic to advanced level. This compiler tutorial will help the student for their semester as well as for...

3 minutes read.

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...

3 minutes read.

CLR Parsing Compiler Design

CLR Parsing CLR parsing refers to the canonical lookahead. We will use the canonical collection of LR(1) items for the construction of the CLR(1) parsing table. Generally, CLR(1) parsing has more...

6 minutes read.

Syntax-Directed Translation

Syntax-Directed Translation A context-free-grammar with some additional rules is known as a syntax-directed definition. In SDT, attributes are associated with grammar symbols and rules are associated with productions. The attributes can...

3 minutes read.

Switch Case Statement Compiler Design

Case Statement The “case” or “switch” statement is available in various languages. The following is the syntax for the case statement: switch (E)  {             case V1: S1             case V2: S2 ...

1 minute read.

SLR 1 Parsing Compiler Design

SLR(1) Parsing It is a simple LR parsing. Most of the function of this parsing is the same as LR(0) parsing. The parsing table for both the parser vary. The SLR(1)...

5 minutes read.

Regular Expression | Compiler Design

Regular Expression A regular expression is a set of patterns that can match a character or string. It can also match alternative characters or strings. The grammar defined by the regular...

3 minutes read.

Target Machine

Target Machine A target machine is a byte-addressable machine. This machine has n general-purpose registers, R0, R1,.....Rn-1. A Simple Target Machine Model has three-address instruction. A full-edged assembly language would have...

3 minutes read.

Finite State Machine

Finite State Machine A finite state machine is a simple machine to recognize patterns. It takes a string of symbols as the input and changes its state to another state, but...

3 minutes read.

Evolution of Programming Languages in Compiler Design

The Evolution of Programming Languages The first computer came in the 1940s and was programmed in a binary language that told the computer what operations are to be performed and in...

4 minutes read.

Storage Allocation

Storage Allocation The storage allocation represents memory management. The allocation of memory can be done in the following ways: Static AllocationStack AllocationHeap Management Static Allocation: It is a procedure used for the allocation of...

1 minute read.

Lexical Analysis in Compiler Design

Lexical Analysis It is the first phase of the compiler. As we know, it is also known as a scanner. The input for lexical analysis is source code. After taking source...

2 minutes read.

Phases of Compiler

Phases of Compiler The compilation process of a compiler goes through various phases. Each phase of the compiler takes the output from the previous as an input. Here we will see all...

2 minutes read.

S-attributed and L-attributed SDTs

S-attributed and L-attributed SDTs STD stands for Syntax Directed Translation. When we associate some informal notations called semantic rules and the grammar, they are known as STD. So we can say...

2 minutes read.

LALR 1 Parsing | Compiler Design

LALR (1) Parsing The LALR parsing refers to the "lookahead LR" that has many lesser steps than typical parsers based on LR(1) items. For constructing the LALR(1) parsing table, the canonical...

6 minutes read.

Boolean Expression in Compiler Design

Boolean Expression The translation of conditional statements such as if-else statements and while-do statements is associated with Boolean expression's translation. The main use of the Boolean expression is the following: Boolean expressions...

3 minutes read.

Basic Blocks and Flow Graphs in Compiler Design

Basic Blocks and Flow Graphs In this section, we are going to learn how to work with basic block and flow graphs in compiler design. Basic Block The basic block is a set...

3 minutes read.

Run-Time Storage Management

Run-Time Storage Management Every executing program has its own logical address space. Logical address space is partitioned into: Code: It is responsible for storing the executable target code. Static: It is used to...

3 minutes read.

Symbol Table Compiler Design

Symbol Table It is an important data structure used by the compiler. It stores information about various entities such as object, class, variable names, functions name, interfaces, procedure, literals, string etc.  The...

3 minutes read.

Ambiguity Elimination Compiler Design

Ambiguity Elimination Ambiguity elimination makes the sentence clear and readable. A sentence is grammatically ambiguous if it can produce more than one parse tree for a particular grammar. In this article,...

3 minutes read.