Chapter 6 Intermediate Code Generation
Update 11March08

Fig 6.1 Logical Structure of a compiler front end (with BackEnd)

This chapter deal with intermediate representations, static type checking, and intermediate code generation.
We will use syntax trees and "three-address code" of the general form
x = y op z using three addresses: two for the operands y and z and one for the result x.

6.2.1 Address and Instructions

An address can be one of the following:

  1. a name
  2. a constant
  3. a compiler-generated temporary

Common three-address instructions used in Text

  1. Assignment instructions x = y op z (op is binary operator)
  2. Assignment instruction x = op y (op is unary operator)
  3. Copy instructions
  4. Unconditional jump goto L
  5. Conditional jumps of form if x goto L and ifFalse x goto L
  6. Conditional jumps such as if x relop y goto L which applies a relational operators (<, ==, >=, etc)
  7. Procedure calls and returns implemented using the instructions: param x for parameters; call p,n and y = call p,n for proceudre and function calls, respectively; and return y, where y, representing a returned value, is optional.
  8. Indexed copy instructinos of the form x = y[i] and x[i] = y
  9. Addresses and pointer assigments of the form x = &y, x = *y and *x = y.

Example 6.5: Consider the statement do i = i+1; while (a[i] < v);

Fig 6.8 gives two ways of assigning labels - we will use the first one.

L: t1 = i+1
   i = t1
   t2 = i*8
   t3=a[t2]
   if t3 < v goto L
Symbolic Labels

Example 6.6 Three-address code for the assignment a = b * -c + b * -c has its syntax tree in Fig 6.11a and its three-address code in Fig 6.10a. Note: extensive use of temporariries (t1 through t5)

6.2.3 Triples
A triple has only three fields, we call op, arg1 and arg2.

p. 368 "A benefit of quadruples over triples can be seen in an optimizing compiler, where instructions are often moved around. With quadruples, if we move an instruction that computers a temporary t, then the instruction that use t require no change. With triples, the result of an operation is referred to by its position, so moving an instruction may require us to change all references to that result. This problem does not occur with indirect triples, which we consider next."

A compromise for the CS 524 course at SDSU is to avoid considerations of optimization, making our use of the Abstract Syntax Tree and triples a reasonable approach.

6.3 Types and Declarations The applications of types can be group under