Live Variable Analysis in Dataflow Analysis

Live Variable Analysis

The variable x is live at the point p if the value of x at p could be used along some path in the flow graph, starting at p. otherwise x is dead at p

Sets of variables form the domain of dataflow values

Backward flow problem, with confluence operator U

IN[B] contains a set of variables, which are live at the starting of B

OUT[B] contains a set of variables, which are definitely assigned values in B, prior to any usage of that variable in B

USE[B] contains a set of variables, whose values may be used in B prior to any definition of the variable

Every statement uses some set of variables (read from them) and defines some set of variables (write to them)

For statement define:

                USE[S]: Set of variables used by ‘S’         

                DEF[S]: Set of variables defined by ‘S’

Example:

                a = b + c                USE = b,c             DEF = a

                a = a + 1                USE = a                 DEF = a

Equations to solve Live Variable Analysis

                OUT[B] = U         IN[S]

                                S is a successor of B

                IN[B] = USE[B] U (OUT[B] – DEF[B])

                IN[B] =f, for all B (initialization only)

Example:

Figure 23

Figure 24                              

Busy Expression:

An expression e is said to be a busy expression along some path pi… pj, only if an evaluation of e exists along some path pi…pj, and no definition of any operand exists before its evaluation along the path

Figure 25

Advantage of Busy Expression

Busy expressions are useful in performing code movement optimization.

Dataflow Equations:

All the equations which represent the expressions that appear in the flow graph, are termed as dataflow equations

The dataflow equations are advantageous for computing live variables, available expression and reaching definitions

The computation of dataflow equations is carried out with the help of forward substitution or backward substitution

Representing Dataflow Information

The information in the dataflow is represented by a set of properties or by using bit vector, where, each bit represents a property

Example:

                               a := b + c

                               d := c * d

                               e := a – c

                               f := d + e

the set of property for these statements can be

                               {b + c, c * d, d + e}

The bit vector can be represented as,

Figure 26

A more compressed form for representation of the dataflow information is obtained, through bit vector representation

Consider the given flow graph for the expressions (b + c, c * d, a –c, d + e)

Figure 27

Consider the given flow graph for the expressions (b + c, c * d, a – c, d + e)

Figure 28

Dataflow Equations for Programming Constructs

• The dataflow equation written in a form of equation such that, OUT[S] = GEN[S] U (IN[S] – KILL[S])
• S represents the statement for which the dataflow equation can be written
• OUT represents an output, i.e., the information generated at the end of the statement
• GEN represents the information generated within the statement
• IN represents the gathered information before entering in to the loop
• KILL represents the information that is killed with the control flow
• Hence, the above equation can be read as “the dataflow information at the end of the statement is either the information generated within the statement, or the information gathered before entering the loop and not killed when control flows through the statement”

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.