Compiler Design Unit 3

UNIT III
INTERMEDIATE CODE
GENERATION
Mrs.D.Jena Catherine Bel,
Assistant Professor, CSE
Velammal Engineering College

DAG – Construction
• A dag for a basic block has following labels on the nodes
• leaves are labeled by unique identifiers, either variable
names or constants
• interior nodes are labeled by an operator symbol
• nodes are also optionally given a sequence of identifiers for
labels
Mrs.D.Jena
Catherine
Bel
2

• Algorithm for constructing a DAG
• Input : A basic block.
• Output : DAG with
i). Label for each node; identifier for leaf node, operator for interior node.
ii). For each node a list of attached identifiers.
Do the steps (1) to (3) for each statement in the given basic block.
The statements may be of the form (i). A := B op C, (ii). A := op B, (iii) A := B.
• Step 1:
• If NODE (B) is undefined create leaf labeled B and let the NODE (B) be this node.
• In case (i), do the same for C.
• Step 2:
• In case(i)
• determine whether there is a node labeled ‘op’ with left NODE(B), right NODE(C)
• If not create such a node. Let ‘n’ be the node found or created.
In case (ii), find whether a node labeled ‘op’ with only one child NODE(B) is available or not.
• If not create such a node and let ‘n’ be the node found or created.
• In case (iii), let ‘n’ be the NODE (B).
• Step 3:
• Append A to the list of attached identifiers for node found in step 2. Finally set NODE (A) to n.
Mrs.D.Jena
Catherine
Bel
3

• Example: Consider the following 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) prod := t6
(8) t7 := i+1
(9) i:= t7
(10) if i<=20 goto (3)
•
Mrs.D.Jena
Catherine
Bel
4

t1
*
4 I
DAGconstruction
DAGfor the statement1
n3
n1 n2
t2
[ ]
a 4
t1
*
I
n5
n4 n1
n3
n2
For the first two
statements
Mrs.D.Jena
Catherine
Bel
5

• For first three statements
t2
[]
a 4
t1,t3
*
I
n5
n4 n1
n3
n2
Mrs.D.Jena
Catherine
Bel
6

• First four statements
t2
[ ]
a 4
t1, t3
*
I
t4
[ ]
n5
n4 n1
n3
n2
n6
n7
b
Mrs.D.Jena
Catherine
Bel
7

prod0
4
b
a 20
t4
t5
t6, prod
t7, i
(1)
t1, t3
t2
+
<=
[]
*
[]
*
+
i0
Mrs.D.Jena
Catherine
Bel
8

Application of DAG
•Automatic detection of common sub expressions.
•The values, which can be used outside the block can also be identified;
•Reconstruction of the simplified list of quadruples after eliminating
common sub expressions and assignments like A := B unless absolutely
necessary.
•
Mrs.D.Jena
Catherine
Bel
9

CODE GENERATION FROM DAG
Advantage
• Rearrange the order of the final computation sequence
to obtain an optimal code
Consider the Basic block for T4 := (A+B) – (E – (C + D))
T1 := A + B
T2 := C + D
T3 := E - T2
T4 := T1 - T3
T4
T1
T3
T2
Mrs.D.Jena
Catherine
Bel
10

• Corresponding object code is
MOV A, R0
ADD B, R0
MOV C, R1
ADD D, R1
MOV R0, T1
MOV E, R0
SUB R1, R0
MOV T1, R1
SUB R0, R1
MOV R1, T4
Mrs.D.Jena
Catherine
Bel
11

• Algorithm to find out the optimal ordering
While unlisted interior nodes remain do
Begin
Select an unlisted node n, all whose parents have been listed;
list n;
While the left most child “m” of “n” has no unlisted parents and is
not a leaf do begin
list m;
n := m;
End;
End;
Mrs.D.Jena
Catherine
Bel
12

• The algorithm produces the optimal order in reverse. The optimal
order produced for the above DAG is as follows.
T2 := C + D
T3 := E - T2
T1 := A + B
T4 := T1 - T3
The generated code is given below.
MOV C, R0
ADD D, R0
MOV E, R1
SUB R0, R1
MOV A, R0
ADD B, R0
SUB R1, R0
MOV R0, T4
Mrs.D.Jena
Catherine
Bel
13

CODE GENERATION FROM LABELED TREE
• In labeling algorithm
• labels each node of the tree with an integer
• denotes the fewest number of registers required to evaluate the tree with no stores of
intermediate results (no need of temporary names).
Begin /* labeling algorithm */
If “n” is a leaf
then if “n” is the left most child of its parent then LABEL(n) := 1
else LABEL(n) := 0;
else begin
let n1, n2, … nk be the children of n ordered by their LABELs so that LABEL(n1) >=
LABEL(n2) >=… >= LABEL(nk);
LABEL(n) := max ( LABEL(ni) + i – 1 )
1<i<l
end;
End
If nodes are binary
Max (l1 , l2) if l1 ≠ l2
l1 + 1 if l1 = l2
Label (n) =
Mrs.D.Jena
Catherine
Bel
14

CODE GENERATION FROM LABELED
TREE
T1 := A + B
T2 := C + D
T3 := E - T2
T4 := T1 - T3
Mrs.D.Jena
Catherine
Bel
15

TREE
• Algorithm for code generation from a labeled tree
• Uses a recursive procedure named GENCODE(n), which
generates the code to evaluate the node n into a register.
• RSTACK is the register stack used by the procedure, which is initially
having all the available registers.
• TSTACK is the stack of temporary names used by the GENCODE
procedure.
• The notation X STACK is used to pop the top stack and assign
the value popped to X.
• The notation STACK X denotes push X onto STACK. TOP(STACK)
refers the value on the top of the stack.
Mrs.D.Jena
Catherine
Bel
16

TREE
• Procedure GENCODE (n)
Begin
/* case 0 */
if “n” is a left leaf representing the operand NAME and “n” is the left most child of its parent then
print ‘MOV’ || NAME || ‘,’ || TOP(RSTACK);
if “n” is an interior node with operator OP and children n1 and n2 then
• if LABEL(n2) = 0 then begin /* case 1 */
let NAME be the operand represented by n2;
GENCODE (n1);
print OP || NAME || ‘,’ || TOP(RSTACK)
end
else if 1 <= LABEL(n1) < LABEL(n2) and LABEL(n1) < r then
begin /* case 2 */
SWAP (RSTACK);
GENCODE (n2);
R =pop( RSTACK); /* n2 is evaluated in register R */
GENCODE (n1);
print OP || R || ‘,’ || TOP(RSTACK);
push(RSTACK , R);
SWAP (RSTACK);
end
Mrs.D.Jena
Catherine
Bel
17

TREE
else if 1 <= LABEL(n2) <= LABEL(n1) and LABEL(n2) < r then
begin /* case 3 */
GENCODE (n1);
R =pop( RSTACK); /* n1 is evaluated in register R */
GENCODE (n2);
print OP || TOP(RSTACK) ||’,’ || R
• push(RSTACK, R);
• end
else begin/*case 4, both labels are >total no. of registers */
GENCODE (n2);
T=pop( TSTACK);
print ‘MOV’ || TOP(RSTACK) ||’,’ || T
GENCODE (n1);
push(TSTACK, T);
print OP || T ||’,’ || TOP(RSTACK)
end;
end;
•
Mrs.D.Jena
Catherine
Bel
18

TREE
.
GENCODE(T4) (case2) [R0 R1]
GENCODE(T3) (case3) [R1 R0]
GENCODE(E) (case0) [R1 R0]
Print MOV E, R1
GENCODE(T2) (case1) [R0]
GENCODE(C) (case0) [R0]
Print MOV C, R0
Print ADD D, R0
Print SUB R0, R1
GENCODE(T1) (case1) [R0]
GENCODE(A) (case 0) [R0]
Print MOV A, R0
Print ADD B, R0
Print SUB R1, R0
Mrs.D.Jena
Catherine
Bel
19

Compiler Design Unit 3

Recommended

More Related Content

What's hot (20)

Similar to Compiler Design Unit 3 (20)

More from Jena Catherine Bel D (10)

Recently uploaded (20)

Compiler Design Unit 3