Next: Boolean Expressions and Control Flow Up: Compiler Theory: Intermediate Code Generation Previous: Abstract Stack Machines

THREE-ADDRESS CODES are a form of IR similar to assembler for an imaginary machine. Each three address code instruction has the form

x := y op z

• x,y,z are names (identifiers), constants, or temporaries (names generated by the compiler)
• op is an operator, from a limited set defined by the IR.
Observe that
• Complicated arithmetic expressions are represented as a sequence of 3-address statements, using temporaries for intermediate values. For instance the expression x + y + z becomes
t1 := y + z
t2 := x + t1

• Three address code is a linearized representation of a syntax tree, where the names of the temporaries correspond to the nodes.
• The use of names for intermediate values allows three-address code to be easily rearranged which is convenient for optimization. Postfix notation does not have this feature.
• The reason for the term three-address code is that each statement usually contain three addresses, two for the operands and one for the result.

THREE-ADDRESS STATEMENTS are similar to assembly code. We will consider the following statements.

Assignments.
Two possible forms:
• x:= y op z where op is a binary arithmetic or logical operation,
• x:= op y where op is a unary operation (minus, negation, conversion operator)
Copy statements.
They have the form x := y.
Inconditional jumps.
They have the form
goto L

where L is a symbolic label of a statement.
inconditional jumps.
They have the form
if x relop y goto L

where statement L is executed if x and y are in relation relop.
Procedure calls.
They have the form
param x1
param x2

param xn
call p, n

corresponding to the procdure call p(x1, x2, ..., xn)
Return statement.
They have the form return y where y representing a returned value is optional.
Indexed assignments.
They have the form x := y[i] or x[i] := y.
They have the form x := &y which sets x to the location of y.
Pointer assignments.
They have the form
• x := *y where y is a pointer and which sets x to the value pointed to by y
• *x := y which changes the location of the value pointed to by x.

SYNTAX-DIRECTED TRANSLATION INTO 3-ADDRESS CODE. We give below a S-definition generating 3-address code from assignments. We use the following attributes

• S.code represents the 3-address code for the assignment S,
• E.place is the name that will hold the value of E,
• E.code represents the sequence of 3-address statements evaluating E.
• .place is the name that holds the value of which may be found by consulting the symbol table at .entry.
The function newtemp returns a sequence of distinct names and | | is used to denote the concatenation of strings.
 Production Semantic Rule S : = E S.code := E.code | | generate( .place, ':=', E.place) E E1 + E2 E.place := newtemp code := generate(E.place, ':=', E1.place, '+', E2.place) E.code := E1.code | | E2.code | | code E E1*E2 E.place := newtemp code := generate(E.place, ':=', E1.place, '*', E2.place) E.code := E1.code | | E2.code | | code E - E1 E.place := newtemp code := generate(E.place, ':=', ' ', E1.place) E.code := E1.code | | code E (E1) E.place := E1.place E.code := E1.code E E.place := .place E.code := ''
Observe that
• The semantic rules for E means that in this case we do not generate a new temporary for E, instead use the name of the identifier.
• Attributes E.place and .place are symbol table pointers.

Next: Boolean Expressions and Control Flow Up: Compiler Theory: Intermediate Code Generation Previous: Abstract Stack Machines
Marc Moreno Maza
2004-12-02