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”
