UNIT-5 CODE OPTIMIZATION

 Principal Sources of Optimization

 Peep-hole optimization

 Optimization of Basic Blocks

 DAG

 Global Data Flow Analysis

 Efficient Data Flow Algorithms

 CODE OPTIMIZATION: INTRODUCTION

 Program transformation technique, which tries to

improve the code by making it consume less resources
and deliver high speed.
 Three rules :

 [Link] output code must not, in any way, change the

meaning of the program.
 2. Optimization should increase the speed of the
program and if possible, the program should demand
less number of resources.
 [Link] should itself be fast and should not
delay the overall compiling process.

Types of Optimizations
[Link] independent optimizations:
Program transformations that improve the target code
without taking into consideration any properties of the
target machine.
2. Machine dependant optimizations:
Register allocation and utilization of special machine-
instruction sequences
• Consider only Machine-Independent Optimizations
• Techniques : Control-Flow and Data-Flow analysis.
• Control-Flow Analysis:
Identifies loops in the flow graph of a program since such
loops are usually good candidates for improvement.
• Data-Flow Analysis:
Collects information about the way variables are used in a
program.
 Properties of Optimizing Compilers:
 The source code should produce correct target code
 Dead code should be completely removed from source
language.
 While applying the optimizing transformations the semantic
of the source program should not be changed.
 Basic Blocks
sequence of consecutive statements in which flow of
control enters at the beginning and leaves at the end
without any halt or possibility of branching except at the
end.
 three-address statements forms a basic block:
t1 : = a * a
t2 : = a * b
t3 : = 2 * t2
t4 : = t1 + t3
t5 : = b * b
t6 : = t4 + t5
Basic Block Construction
Algorithm: Partition into basic blocks
Input: A sequence of three-address statements
Output: A list of basic blocks with each three-address
statement in exactly one block
Method:
1. We first determine the set of leaders, i.e., the first
statements of basic blocks.
The rules we use are of the following:
a. The first statement is a leader.
b. Any statement that is the target of a conditional or
unconditional goto is a leader.
c. Any statement that immediately follows a goto or
conditional goto statement is a leader.
2. For each leader, its basic block consists of the leader and all
statements up to but not including the next leader or the end
of the program.
Example Three Address Code:
begin (1) prod := 0-L
prod :=0; (2) i := 1
i:=1; (3) t1 := 4* iL
do begin (4) t2 := a[t1] /*compute a[i] */
prod :=prod+ a[i] * b[i]; (5) t3 := 4* i
i :=i+1; (6) t4 := b[t3] /*compute b[i] */
end (7) t5 := t2*t4
while i <= 20 (8) t6 := prod+t5
end (9) prod := t6
(10) t7 := i+1
(11) i := t7
(12)if i<=20 goto (3)
Flow Graphs
 Flow graph is a directed graph containing the flow-
of-control information for the set of basic blocks
making up a program.
 The nodes of the flow graph are basic blocks. It has a
distinguished initial node.
Three Address Code:
(1) prod := 0
(2) i := 1
(3) t1 := 4* i
(4) t2 := a[t1] /*compute a[i] */
(5) t3 := 4* i
(6) t4 := b[t3] /*compute b[i] */
(7) t5 := t2*t4
(8) t6 := prod+t5
(9) prod := t6
(10) t7 := i+1
(11) i := t7
(12)if i<=20 goto (3)
 PEEPHOLE OPTIMIZATION

 Peephole optimization is a type of Code

Optimization performed on a small part of the code.

 It is performed on the very small set of instructions in a

segment of code.

 The small set of instructions or small part of code on

which peephole optimization is performed is known
as peephole or window.
 PEEPHOLE OPTIMIZATION
 Peephole optimization is a simple effective technique for
locally improving the target code, which is done by examining
a sliding window of target instructions (called the peephole)
and replacing instruction sequences within the peephole by a
shorter or faster sequence, whenever possible.
 The peephole is a small, moving window on the target
program. The code in the peephole need not be contiguous,
although some implementations do require this.
 Some of the characteristic of peephole optimizations:
 Redundant-instruction elimination
 Eliminating unreachable code

 Flow-of-control optimizations

 Algebraic simplifications

 Use of machine idioms

 PEEPHOLE OPTIMIZATION
[Link] Redundant Loads and
Stores
 If we see the instruction sequence
LD R0 , a
ST a,R0 --------------------------------(5.1)
 We can delete instruction (2) because whenever (2) is
executed, (1) will ensure that the value of a is already
in register RO.
 Note that if (2) had a label we could not be sure that
(1) was always executed immediately before (2)
and so we could not remove (2).
 PEEPHOLE OPTIMIZATION
2. Eliminating Unreachable Code
 An unlabeled instruction immediately following an
unconditional jump may be removed.
 This operation can be repeated to eliminate a sequence
of instructions.
 For example

In C, the source code might look like:

#define debug 0
---------------
if (debug)
{
print debugging information
}
 PEEPHOLE OPTIMIZATION
2. Eliminating Unreachable Code
 For example 2.
In C, the source code might look like:
#define debug 0
---------------
if (debug)
{
print debugging information
}
 Intermediate representation the if-statement may be
translated as:
if debug==1 goto L1
goto L2
L1 : print debugging information -----(a)
L2:
 PEEPHOLE OPTIMIZATION
2. Eliminating Unreachable Code
 To eliminate jumps over jumps.
if debug ≠ 1 goto L2
print debugging information
L2 : -----(b)
 Since debug is set to 0 at the beginning of the program,
constant propagation should replace (b) by
If 0 ≠ 1 goto L2
print debugging information
L2 : ------(c)
 As the argument of the first statement of (5.4) evaluates
to a constant true, it can be replaced by
goto L2.
 Then all the statements that is print debugging
information are unreachable and can be eliminated.
 PEEPHOLE OPTIMIZATION
[Link]-of-Control Optimizations
 The intermediate code generation algorithms frequently
produce jumps to jumps, jumps to conditional jumps, or
conditional jumps to jumps.
 These unnecessary jumps can be eliminated in either the
intermediate code or the target code by the following types of
peephole optimizations. We can replace the jump sequence

goto L1
---
L1: goto L2
by the sequence
qoto L2
---
L1: goto L2
 If there are now no jumps to L1, then it may be possible
to eliminate the statement L1 : goto L2 provided it is
preceded by an unconditional jump
 PEEPHOLE OPTIMIZATION
[Link]-of-Control Optimizations
 Similarly, the sequence

if a < b qoto L1
---
L1: goto L2
can be replaced by
if a < b qoto L2
---
L1: goto L2
 PEEPHOLE OPTIMIZATION
[Link]-of-Control Optimizations
 Finally, suppose there is only one jump to L1 and L1 is
preceded by an unconditional goto. Then the sequence
goto L1
---
L1: if a < b goto L2
L3: -------------(5.5)
may be replaced by
if a < b goto L2
goto L3
L3: ----------------(5.6)
 PEEPHOLE OPTIMIZATION
[Link] Simplification
x := x + 0
or
x ;= x * 1 ---------- (5.7)
 It can be eliminated easily through peephole optimization.

Reduction in Strength
 Replaces expensive operations by equivalent cheaper ones
on the target machine.
 x2 is replaced to x*x.

 Fixed-point multiplication or division is replaced with

shift operation.
 Floating-point division by a constant is replaced as
multiplication by a constant.
 Example: x / 2 = x * 0.5
 PEEPHOLE OPTIMIZATION
[Link] of Machine Idioms
 The target machine may have hardware instructions to
implement certain specific operations efficiently which
can reduce execution time significantly.
 For example, auto-increment and auto-decrement
addressing modes.
 The use of these modes greatly improves the quality of
code when pushing or popping a stack as in parameter
passing.
 Statements like x=x+1  x++

x= x -1  x - -
THE PRINCIPLE SOURCES OF OPTIMIZATION
 QUICKSORT: AN EXAMPLE PROGRAM
void quicksort(int m, int n)
{ int i,j,v,x;
if (n <= m) return;
i = m-1; j = n; v = a[n]; /* fragment begins here */
while (1) {
do i = i+1; while (a[i]<v);
do j = j-1; while (a[j]>v);
if (i>=j) break;
x = a[i]; a[i] = a[j]; a[j] =x; // Swap a[i], a[j]
}
x = a[i]; a[i] = a[n]; a[n] =x; /* fragment ends here */
quicksort(m,j); quicksort(i+1,n);
}
1) i = m-1 16) t7 = 4*i
2) j = n 17) t8 = 4*j
3) t1 = 4*n 18) t9= a[t8]
4) v = a[t1] 19) a[t7] = t9
5) i = i+1 20) t10 = 4*j
6) t2 = 4*i 21) a[t10] =x
7) t3 = a[t2] 22) goto (5)
8) if t3 < v goto (5) 23) t11 = 4*i
9) j = j-1 24) x= a[t11]
10) t4 = 4*j 25) t12 = 4*i
11) t5= a[t4] 26) t13 = 4*n
12) if t5 > v goto (9) 27) t14= a[t13]
13) if i >= j goto (23) 28) a[t12] = t14
14) t6 = 4*i 29) t15 = 4*n
15) x = a[t6] 30) a[t15] = x
1) i = m-1 L 16) t7 = 4*i
2) j = n 17) t8 = 4*j
3) t1 = 4*n 18) t9= a[t8]
4) v = a[t1] 19) a[t7] = t9
5) i = i+1 L 20) t10 = 4*j
6) t2 = 4*i 21) a[t10] =x
7) t3 = a[t2] 22) goto (5)
8) if t3 < v goto (5) 23) t11 = 4*i L
9) j = j-1 L 24) x= a[t11]
10) t4 = 4*j 25) t12 = 4*i
11) t5= a[t4] 26) t13 = 4*n
12) if t5 > v goto (9) 27) t14= a[t13]
13) if i >= j goto (23) L 28) a[t12] = t14
14) t6 = 4*i L 29) t15 = 4*n
15) x = a[t6] 30) a[t15] = x
 THE PRINCIPAL SOURCES OF OPTIMIZATION
 We distinguish local transformations —involving
only statements in a single basic block—from global
transformations.
 A basic block computes a set of expressions

 A number of transformations can be applied to a basic

block without changing the expressions computed by
the block.
 Semantic Preserving Transformation:

1. Common Subexpression elimination;

2. Copy Propagation;
3. Dead-Code elimination;
4. Constant Folding.
 LOCAL OPTIMIZATION- COMMON
SUBEXPRESSION ELIMINATION
Local Common Subexpression
 If the transformation is applied on the same basic block

 Frequently a program will include calculations of the

same value.
 Example. Consider the basic block B5 . The
assignments to both t7 and t10 have common
subexpressions and can be eliminated.
 COMMON SUBEXPRESSION ELIMINATION
After Local Common Subexpression Elimination
B5 is transformed as :
 LOCAL OPTIMIZATION- COMMON
SUBEXPRESSION ELIMINATION
Local Common Subexpression
 Example. Consider the basic block B6 . The
assignments to both t12 and t15 have common
subexpressions and can be eliminated.
Before B6 IN B6 After B6
t11 = 4*i t11 = 4*i t11 = 4*i
x= a[t11] x= a[t11] x= a[t11]
t12 = 4*i t12 = 4*i t13 = 4*n
t13 = 4*n t13 = 4*n t14= a[t13]
t14= a[t13] t14= a[t13] a[t11] = t14
a[t12] = t14 a[t12] = t14 a[t13] = x
t15 = 4*n t15 = 4*n
a[t15] = x a[t15] = x
 COMMON SUBEXPRESSION
ELIMINATION
Global Common subexpression
Elimination
• After local common
subexpressions are
eliminated, B5 still evaluates
4*i and 4*j, .
t8 := 4*j ;
t9 := a[t8];
a[t8] :=x
in B5 can be replaced by
t9 := a[t4] ;
a[t4] := x
where t4 is evaluated
in B3
 LOCAL COMMON SUB EXPRESSION
ELIMINATION
BEFORE B5 AFTER LOCAL B5 AFTER GLOBAL B5
t6: = 4*i
x=a[t6] t6: = 4*i x=a[t4]
t7=4*i x=a[t6] t9=a[t4]
t8=4*j t8=4*j a[t6]=t9
t9=a[t8] t9=a[t8] a[t4]=x
a[t7]=t9 a[t6]=t9 goto B2
t10=4*j a[t8]=x
a[t10]=x goto B2
goto B2
 LOCAL COMMON SUB EXPRESSION
ELIMINATION
BEFORE B6 AFTER LOCAL B6 AFTER GLOBAL B6
t11: = 4*i t11: = 4*i x=t3
x=a[t11] x=a[t11] t14=a[t1]
t12=4*i t13=4*n a[t2]=t14
t13=4*n t14=a[t13] a[t1]=x
t14=a[t13] a[t11]=t14
a[t13]=x
a[t12]=t14
t15=4*n
a[t15]=x
 GLOBAL COMMON SUB EXPRESSION
ELIMINATION
BEFORE B5 AFTER B5
B5 B2
t6: = 4*i t6: = 4*i t2: = 4*i

x=a[t6]
x=a[t6] t3=a[t2]
x=t3
t8=4*j B5 B3
a[t2]=t5
t9=a[t8]
t8=4*j
t9=a[t8]
t4=4*j
t5=a[t4] a[t4]=x
a[t6]=t9
a[t6]=t9 goto B2
a[t8]=x
goto B2
 GLOBAL COMMON SUB EXPRESSION
ELIMINATION
BEFORE B6 AFTER B6
t11: = 4*i B6
t11: = 4*i
B2
t2: = 4*i
x=t3
x=a[t11]
x=a[t11] t3=a[t2] t14=a[t1]
a[t2]=t14
t13=4*n B6 B1
t13: = 4*n t1: = 4*n a[t1]=x
t14=a[t13] t14=a[t11] v=a[t1]

a[t11]=t14
a[t13]=x
 COPY PROPAGATION
 Anidea behind this technique is to use g for f
whenever possible after the copy of
f := g
Copy Propagation applied to Block B5 yields:

Before After
x := t3 x := t3
a[t7] := t5 a[t7] := t5
a[t10] := x a[t10] := t3
Goto B2 Goto B2
COPY PROPAGATION-B6
Copy Propagation applied to Block B6 yields:

Before After
x=t3 x=t3
t14=a[t1] t14=a[t1]
a[t2]=t14 a[t2]=t14
a[t1]=t3
a[t1]=x
 DEAD-CODE ELIMINATION
A variable is live at a point in a program if its
value can be used subsequently, otherwise it is
dead.
 A piece of code is dead if data computed is
never used elsewhere.
 Dead-Code may appear as the result of
previous transformation.
 Dead-Code works well together with Copy
Propagation.
 DEAD-CODE ELIMINATION
 Example. Considering the Block B5 after Copy
Propagation we can see that x is never reused all over
the code. Thus, x is a dead variable and we can
eliminate the assignment x=t3 from B5.

Before After
x := t3
a[t7] := t5 a[t7] := t5
a[t10] := t3 a[t10] := t3
goto B2 goto B2
 DEAD-CODE ELIMINATION –B6

Before After
x=t3 t14=a[t1]
t14=a[t1] a[t2]=t14
a[t2]=t14 a[t1]=t3
a[t1]=t3
 DEAD CODE ELIMINATION
 Remove unreachable code

If (debug) print …

Many times,
debug := false
 CONSTANT FOLDING
 Constant Folding is the transformation that
substitutes an expression with a constant.
 Constant Folding is useful to discover Dead-
Code.
 Example. Consider the conditional statement:
if(x) goto L
 If, by Constant Folding, we discover that x is
always false we can eliminate both the if-test
and the jump to L.
 LOOP OPTIMIZATIONS
 The running time of a program can be improved
if we decrease the amount of instructions in an
inner loop.
 Three important techniques
 Code motion
 Induction-variable elimination
 Reduction in strength
 CODE MOTION
If the computation of an expression is loop-invariant
this transformation places such computation before
the loop.
before
while ( i <= limit – 2) do
after
t = limit – 2
While ( i <= t)
 REDUCTION IN STRENGTH
 Replacement of a computation with a less expensive
one.
Example.
 Consider the assignment t4=4*j in Block B3

 j is decremented by 1 each time, then t4=4*j -4 Thus,

we may replace t4=4*j by
t4=t4 -4
 Problem: We need to initialize t4 to t4 =4 *j before
entering the Block B3.
 Result. The substitution of a multiplication by a
subtraction will speed up the resulting code.
 REDUCTION IN STRENGTH
B2:
i=i+1
t2=4*i

B3:
j=j-1
t4=4*j
INDUCTION-VARIABLE ELIMINATION AN EXAMPLE (CONT..)
 OTHERS OPTIMIZATIONS
• Loop Unrolling
–Loop overhead can be reduced by reducing the number of
iterations and replicating the body of the loop.
Before After
int i=1; int i=1;
while(i<=100) while(i<=50)
{ {
a[i]=b[i]; a[i]=b[i];
i++; i++;
} a[i]=b[i];
i++;
}
LOOP FUSION / LOOP JAMMING
Several loops are merged to one loop.
Example

Before Fusing After Fusing

for i = 1 to 100 for i = 1 to 100

a(i) = 0; {
for i = 1 to 100 a(i) = 0;
b(i) = x(i) + y; b(i) = x(i) + y;
}
OPTIMIZATION OF BASIC BLOCKS-
DIRECTED ACYCLIC GRAPHS (DAG)

 Definitions
 In compiler design, a directed acyclic graph
(DAG) is on abstract syntax tree(AST) with a
unique node for each value.

 A directed acyclic graph(DAG) is a directed graph

that contains no cycles.
USE OF DAG FOR OPTIMIZING BASIC BLOCKS

 DAG is useful data structure for implementing

transformation on basic blocks.
 A basic block can optimized by the construction of
DAG.
 A DAG can be constructed for a block and
certain transformations such as common sub-
expression elimination and dead code elimination
applied for performance the local optimization.
 To apply the transformation on basic block, a
DAG is constructed from three address code.
APPLICATIONS OF DAG
 The DAG is Used In:
 Determine the common sub expression
(Expression computed more than one).

 Determine which names are used in block and

computed outside the block.

 Determine which statements of the block could

their computed value.
RULES OF THE CONSTRUCTING DAG
 Rule 1:
 In a DAG
 Leaf node represent identifiers, names or constants.
 Interior node represent operators.
 Rule 2:
 • While constructing DAG, there is a check made to find if
there is on existing node with the same children.
 A new node is created only when such a node doesn't exist.
This action allow us to detect common sub expression and
eliminate the re-computation of the same.
 Rule 3:
 The assignment of the from x:= must not be performed
until and unless it is a must.
 Problem 1:
 Construct DAG for the given expression

(a+b) * (a+b+c)
 Solution:

 Three address code for the given expression.

t1=a+b
 t2=t1+c

 t3=t1*t2

 The DAG is: Problems

EXPLANATION
 From the constructed DAG, we observed that the
common sub expression (a+b) is translated into a
single node in the DAG. The computation is
carried out only once and stored in the identifier
t1 and reused later.
 This illustrates how the DAG construction
scheme identifies the common sub expression and
helps in elimination its re-computation later.
 Problem : Construct DAG for the given
expression (((a+a) + (a+a))+ ((a+a) + (a+a)))
 Solution: DAG for this Expression is-

 (a+a)

 (((a+a) + (a+a))+ ((a+a) + (a+a)))

 (((a+a) + (a+a))
Problem : Construct  Step 3:  Step 5:
DAG for the given
expression
a=b*c
d=b
e=d*c
b=e
f=b+c
g=f+d  Step 4:
 Solution:

 Step 1:  Step 6:

 Step 2:
Problem:Constru
ct DAG from
the basic
block.
1. t1 = 4*i
2. t2 = a[t1]
3. t3 = 4*i
4. t4 = b[t3]
5. t5 = t2*t4
6. t6 = prod + t5
7. t7 = i+1
8. i = t7
9. if i<=20 goto 1
Example:Constru
ct DAG from
the basic
block.
1. t1 = 4*i
2. t2 = a[t1]
3. t3 = 4*i
4. t4 = b[t3]
5. t5 = t2*t4
6. t6 = prod + t5
7. t7 = i+1
8. i = t7
9. if i<=20 goto 1
Example:Constru
ct DAG from
the basic
block.
1. t1 = 4*i
2. t2 = a[t1]
3. t3 = 4*i
4. t4 = b[t3]
5. t5 = t2*t4
6. t6 = prod + t5
7. t7 = i+1
8. i = t7
9. if i<=20 goto 1
Example:Constru
ct DAG from
the basic
block.
1. t1 = 4*i
2. t2 = a[t1]
3. t3 = 4*i
4. t4 = b[t3]
5. t5 = t2*t4
6. t6 = prod + t5
7. t7 = i+1
8. i = t7
9. if i<=20 goto 1
REPRESENTING ARRAY ACCESSES IN THE
DAG
x = a[i] is represented by creating a node with
 operator =[] and
 two children representing the initial value of array
a0 & the index i
 Variable x become a label of this node

 a[j] = y is represented by creating a node with

 operator []= and
 three children representing the initial value of array
a0 , j & y
 There is no Variable labeling this node
 GLOBAL DATA-FLOW ANALYSIS
 Data-flow information can be collected by setting up and
solving systems of equations that relate information at
various points in a program.

 Data Flow Equation is of the form

out[S] = gen[S] U (in[S] – kill[S])

“The information at the end of a statement is either

generated within the statement, or enters at the
beginning and is not killed as control flows through the
statement.”
 gen[S] - set of definitions “generated by S”.

 kill[S] - set of definitions “killed” by S.

 in[S] – set of definitions reaching Top of S

 out[S] - set of definitions that reach the bottom of S.

 GLOBAL DATA-FLOW ANALYSIS
 The details of how data-flow equations are set up and
solved depend on three factors.
1. The notions of generating and killing depend on the
desired information.
2. Since data flows along control paths, data-flow
analysis is affected by the control constructs in a
program.
3. There are subtleties that go along with such
statements as procedure calls, assignments through
pointer variables, and even assignments to array
variables.
 POINTS AND PATHS
 Within a basic block, the point is between two adjacent
statements, as well as the point before the first
statement and after the last.
A path from P1 to Pn is a
sequence of points P1,P2, … Pn
such that for each i between 1
and n-1, either
1. Pi is the point immediately preceding
a statement and Pi+1 is the point
immediately following that statement
in the same block, or
2. Pi is the end of some block and Pi+1 is
the beginning of a successor block.
 REACHING DEFINITIONS
 A definition of a variable x is a statement that assigns, or may
assign, a value to x.
 The most common forms of definition are assignments to x and
statements that read a value from an I/O device and store it in
x. These statements certainly define a value for x, and referred
as unambiguous definitions of x.
 There are certain other kinds of statements that may define a
value for x; they are called ambiguous definitions.
 Usual forms of ambiguous definitions of x are
 A call of a procedure with x as a parameter or a procedure that can
access x.
 An assignment through a pointer that could refer to x. For example,
the assignment *q:=y is a definition of x if it is possible that q points
to x
 A definition d reaches a point p if there is a path from the
point immediately following d to p, such that d is not "killed"
along that path.
DATA-FLOW EQUATIONS FOR
REACHING DEFINITIONS
DATA-FLOW EQUATIONS FOR
REACHING DEFINITIONS
DATA-FLOW EQUATIONS FOR
REACHING DEFINITIONS
DATA-FLOW EQUATIONS FOR
REACHING DEFINITIONS
 COMPUTATION OF IN AND OUT
 The in is an inherited attribute and out is a
synthesized attribute depending on in.
 in[S] - set of definitions reaching the beginning of
S, taking into account the flow of control
throughout the entire program, including
statements outside of S or within which S is
nested.
 out[S] is defined similarly for the end of s.
 REPRESENTATION OF SETS
 Sets of definitions, such as gen[S] and kill[S], can be
represented compactly using bit vectors.
 The bit vector representing a set of definitions will
have 1 in position i if and only if the definition
numbered i is in the set.
 A bit-vector representation for sets also allows set
operations to be implemented efficiently.
 The union and intersection of two sets can be
implemented by logical or and logical and,
respectively.
 The difference A-B of sets A and B can be
implemented by taking the complement of B and
then using logical and to compute A^ ¬ B
EFFICIENT DATA FLOW ALGORITHMS

 Two algorithms(DFA increases the speed)

 1. Depth-First Ordering in iterative Algorithms:

 Application of depth-first ordering to reduce the
number of 'passes that the iterative algorithm takes.

 2. Structure-based Data-Flow Analysis.

 Uses intervals or the T1and T2 transformations to
generalize the syntax-directed approach.
 [Link] Ordering in Iterative Algorithms
/ Depth-First Ordering in iterative
Algorithms
 Reaching definitions. Available expressions, or live
variables, any event of significance at a node will be
propagated to that node along an acyclic path.
 Iterative algorithms can be used to track their acyclic
nature.
ALGORITHM TO COMPUTE IN AND OUT
 /* initialize out on the assumption in[B] = ∅ for all B */
 (1) for each block B do out[B] := gen[B];
 (2) change := true; /* to get the while- loop going */
 (3) while change do begin
 (4) change := false;
 (5) for each block B do begin
 (6) in[B] := U out[P];
P a predecessor of B
 (7) oldout := out[B];
 (8) out[B] := gen[B] U (in[B] - Kill[B]);
 (9) if out[B] ≠ oldout then change :=true
 (10) end
 (11) end
 The order of visiting the edges in the above tree is:
 1 →3 → 4 → 6 → 7 → 8 →10 → 8 → 9 → 8 → 7 → 6
→ 4 → 5 →4 →3 → 1→ 2→1
 Algorithm : Structure- based reaching definitions.
 Input : A reducible flow graph G and sets of definitions
gen[B] and kill[B] for each block B of G.
 Output: in[B] for each block B Method:

 [Link] the (T1, T2) - decomposition for G

 [Link] each region R in the decomposition, from the

inside out, compute genR,B and killR,B for each block B
in R
 3. If U is the name of the region consisting of the entire
graph, then for each block B, set in[B] to the union, over
all predecessors P of block B, of gen U, P.