Dataflow Properties in Compiler Design

Dataflow Analysis

The dataflow is a property, which represents information regarding usefulness of the data items for the purpose of optimization

Dataflow properties include:

                                Available expressions

                                Reaching definitions

                                Live variables

                                Busy expressions

Dataflow Properties:

Definition point is a program point containing the definition

Reference point is a program point, at which a reference is made to a data item

Evaluation point is a program point where certain evaluation expression is specified

Figure1

Available Expressions:

An expression (x + y) is accessible at the program point w, only if all the paths are reaching to w

The expression (x + y) is accessible, if no definitions of any expressions operand (here either x or y) follows its last evaluation down the path. Neither of them gets modified before use

Figure2

Advantages of available expressions:

Available expressions are mainly used to find common sub expressions

Use of available expressions

Figure3

Example: Available expressions

Figure4

Assign a number to each expression

 

GEN and KILL Sets

GEN Set:

A current basic block or instruction is said to be in the GEN set if it creates the definition

In any case, the must be in the output

KILL Set:

A current basic block or instruction is said to be in the KILL set if it redefines a variable in the expression

After that, the expression is becomes invalid

Algorithm for Available Expression

Assign a number to each expression

Calculate GEN and KILL sets for each instruction

Calculate aggregate GEN and KILL sets for each basic block

Initialize available set at each basic block to be the entire set

                1             

a = b + c

                                GEN = { b + c }

                d = e + f

2

                                GEN = { e + f}

                                KILL = {any expr with d}

                f = a + c

                3

                                GEN = {a + c}

                                KILL = {any expr with f}

Figure 5

GEN and KILL Sets:

                a = b + c

                1

                                GEN = {1}

                                KILL ={3, 4, 5, 7}

                d = e + f

                2

                                GEN = {2}

                                KILL = {5, 7}

                f = a + c

                3

                                GEN = {3}

                                KILL = {2, 6}

FIGURE6

Aggregate GEN and KILL Sets:

The propagation of all the GEN and KILL sets from top of the basic block to the bottom of the basic block is carried out

Figure7

Aggregate GEN Set

The current expression’s GEN set must reside in the OUTGEN set

The OUTGEN set must contain the expression which is in the INGEN set and which is not killed

Figure8

Figure9

Aggregate KILL Set:

The current expression’s KILL set should be in the OUTKILL set

Any set in the INKILL should be in OUTKILL

Figure10

Figure11

Aggregate GEN and KILL Sets

Figure12

Figure 13

Propagate Available Expression Set

An expression would be available at the end, if it is generated in the GEN set should be in the OUT set

Figure 14

Any expression available at the input (in the IN set) and not killed, should be available at the end

Figure15

Expression is available only if it is available in all input paths

IN = ∩OUT

OUT = GEN U (IN – KILL)

FIGURE16

Figure17

Figure18

Share on Google Plus

About Data Sciences by Venu

Hi, My name is Venugopala Chary and I'm Currently working as Associate Professor in Reputed Engineerng College, Hyderabad. I have B.Tech and M.tech in regular from JNTU Hyderabad. I have 11 Years of Teaching Experience for both B.Tech and M.Tech Courses.