Three-Address Code

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.

Address assignments.

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.
• $\bf id$.place is the name that holds the value of $\bf id$ which may be found by consulting the symbol table at $\bf id$.entry.

The function newtemp returns a sequence of distinct names and | | is used to denote the concatenation of strings.

Production	Semantic Rule
S $\longmapsto$ $\bf id$ : = E	S.code := E.code | | generate( $\bf id$.place, ':=', E.place)
E $\longmapsto$ E1 + E2	E.place := newtemp
	code := generate(E.place, ':=', E1.place, '+', E2.place)
	E.code := E1.code | | E2.code | | code
E $\longmapsto$ E1*E2	E.place := newtemp
	code := generate(E.place, ':=', E1.place, '*', E2.place)
	E.code := E1.code | | E2.code | | code
E $\longmapsto$ - E1	E.place := newtemp
	code := generate(E.place, ':=', ' $\bf unimus$', E1.place)
	E.code := E1.code | | code
E $\longmapsto$ (E1)	E.place := E1.place
	E.code := E1.code
E $\longmapsto$ $\bf id$	E.place := $\bf id$.place
	E.code := ''

Observe that

• The semantic rules for E $\longmapsto$ $\bf id$ 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 $\bf id$.place are symbol table pointers.