Intermediate Code
Generation
Intermediate Code Generation
Intermediate languages
Declarations
Expressions
Statements
Intermediate Representations
Graphical representations (e.g. AST)
Postfix notation: operations on values stored
on operand stack (similar to JVM bytecode)
Three-address code: (e.g. triples and quads)
x := y op z
Two-address code:
x := op y
which is the same as x := x op y
Example
i := 2 * n + k
while i do
i := i - k
t1 := 2
t2 := t1 * n
t3 := t2 + k
i := t3
L1: if i = 0 goto L2
t4 := i - k
i := t4
goto L1
L2:
Intermediate Languages
Syntax tree
a := b * - c + b * - c
:=
a +
* *
b - b -
Postfix notation c c
a b c - * b c - * + :=
Three-address code
The postfix notation
If E is a variable or constant, then the postfix
notation for E is E itself
If E is an expression of the form E1 op E2 then postfix
notation for E is E1’ E2’ op, here E1’ and E2’ are the
postfix notations for E1and E2, respectively
the form (E), then the postfix notation for E is the
same as the postfix notation for E.
For unary operation –E the postfix is E-
postfix notation for 9- (5+2) is 952+-
Postfix Notation
a := b * -c + b * -c
a b c uminus * b c uminus * + assign
Postfix notation represents
operations on a stack
Pro: easy to generate
Cons: stack operations are more
difficult to optimize
Directed Acyclic Graphs for
Expressions
DAG has leaves
corresponding to
atomic operands and
interior codes
corresponding to
operators
Difference is that a
node N in a DAG has the DAG for the
more than one parent if expression a + a *
N (b - c) + (b - c) * d
Abstract Syntax Trees
[Link]
a * (b + c) [Link] * [Link]
a ( [Link] )
[Link] + [Link]
b c
*
Pro: easy restructuring of code
and/or expressions for a +
intermediate code optimization
Cons: memory intensive b c
Abstract Syntax Trees versus
DAGs
a := b * -c + b * -c
:= :=
a + a +
* * *
b uminus b uminus b uminus
c c c
Tree DAG
Directed Acyclic Graphs for
Expressions
Directed Acyclic Graphs for
Expressions
Three-Address Code
x := y op z
where x, y, z are names, constants, or temporaries
a := b * -c + b * -c
x+y*z
t1 := -c
t1 := y * z t2 := b * t1
t2 := x + t1 t3 := -c
t4 := b * t3
t5 := t2 + t4
a := t5
Three-Address Code
a := b * -c + b * -c
t1 := - c t1 := - c
t2 := b * t1 t2 := b * t1
t3 := - c t5 := t2 + t2
t4 := b * t3 a := t5
t5 := t2 + t4
a := t5
Linearized representation Linearized representation
of a syntax tree of a syntax DAG
Types of Three-Address Code
Assignment statement x := y op z
Assignment statement x := op y
Copy statement x := y
Unconditional jump goto L
Conditional jump if x relop y goto L
Procedural call param x
call p
return y
Types of Three-Address Code
Indexed assignment x := y[i]
x[i] := y
Address and pointer assignment
x := &y
x := *y
*x := y
Implementation of Three-Address
Code
Quadruples
For statement a=-c*b + -c*b
op arg1 arg2 result
(0) - c t1
(1) * b t1 t2
(2) - c t3
(3) * b t3 t4
(4) + t2 t4 t5
(5) := t5 a
Implementation of Three-
Address Statements: Quads
Quads (quadruples) for statement u:= (d+h) /n+-c*k
# Op Arg1 Arg2 Res
(0) + d h t1
(1) / n t1 t2
(2) - c t3
(3) * k t3 t4
(4) + t2 t4 t5
(5) := t5 u
Pro: easy to rearrange code for global optimization
Cons: lots of temporaries
Implementation of Three-Address
Code
Triples
For statement a=-c*b + -c*b
op arg1 arg2
(0) - c
(1) * b (0)
(2) - c
(3) * b (2)
(4) + (1) (3)
(5) := a (4)
Implementation of Three-
Address Statements: Triples
Triples u:= (d+h) /n+-c*k
# Op Arg1 Arg2
(0) + d h
(1) / n (0)
(2) - c
(3) * k (2)
(4) + (1) (3)
(5) := u (4)
Pro: temporaries are implicit
Cons: difficult to rearrange code
Implementation of Three-Address Code
Indirect Triples
For a=-c*b + -c*b
statement op arg1 arg2
(0) (14) (14) - c
(1) (15) (15) * b (14)
(2) (16) (16) - c
(3) (17) (17) * b (16)
(4) (18) (18) + (15) (17)
(5) (19) (19) := a (18)
Implementation of Three-
Address Stmts: Indirect Triples
# Stmt # Op Arg1 Arg2
(0) (14) (14) plus d h
(1) (15) (15) / n (14)
(2) (16) (16) minus c
(3) (17) (17) * k (16)
(4) (18) (18) + (15) (17)
(5) (19) (19) := u (18)
Program Triple container
Pro: temporaries are implicit & easier to rearrange code
Comparison
Qualdruples
direct access of the location for temporaries
easier for optimization
Triples
space efficiency
Indirect Triples
easier for optimization
space efficiency
New Names and Labels
Function newtemp returns a new name for
each call
Function newlabel returns a new label for
each call
Assignments
S id “:=” E {emit([Link] ‘:=’ [Link]);}
E E1 “+” E2 {[Link] := newtemp;
emit([Link] ‘:=’ [Link] ‘+’ [Link]);}
E E1 “*” E2 {[Link] := newtemp;
emit([Link] ‘:=’ [Link] ‘*’ [Link]);}
E “-” E1 {[Link] := newtemp;
emit([Link] ‘:=’ ‘-’ [Link]);}
E “(” E1 “)” {[Link] := [Link]}
E id {[Link] := [Link]}
Type Conversion
E E1 + E2
{[Link] := newtemp;
if [Link] = int and [Link] = int then begin
emit([Link] ‘:=’ [Link] ‘int+’ [Link]); [Link] := int;
end else if [Link] = real and [Link] = real then begin
emit([Link] ‘:=’ [Link] ‘real+’ [Link]);
[Link] := real;
end else if [Link] = int and [Link] = real then begin
u := newtemp; emit(u ‘:=’ ‘inttoreal’ [Link]);
emit([Link] ‘:=’ u ‘real+’ [Link]); [Link] := real;
end else if …
Flow-of-Control Statements
S if E then S1
| if E then S1 else S2
| while E do S1
| switch E begin
case V1: S1
case V2: S2
…
case Vn-1: Sn-1
default: Sn
Boolean Expressions
E E1 or E2
{[Link] := [Link]; [Link] := newlabel;
[Link] := [Link]; [Link] := [Link];
[Link] := [Link] || gen([Link] ‘:’) || [Link]; }
E E1 and E2
{[Link] := newlabel; [Link] := [Link];
[Link] := [Link]; [Link] := [Link];
[Link] := [Link] || gen([Link] ‘:’) || [Link]; }
E not E1
{[Link] := [Link]; [Link] := [Link];
Boolean Expressions
E “(” E1 “)”
{ [Link] := [Link]; [Link] := [Link];
[Link] := [Link]; }
E id1 relop id2
{ [Link] :=
gen(‘if’ [Link] [Link] [Link] ‘goto’ [Link])
|| gen(‘goto’ [Link]); }
E true
{ [Link] := gen(‘goto’ [Link]); }
E false
{ [Link] := gen(‘goto’ [Link]); }