Intermediate Code Generation

Dr. Noman Islam

Introduction

• m x n compilers can be built by writing just m front ends and n back ends
• This chapter deals with intermediate representations, static type checking, and intermediate code generation
• Static checking includes type checking, which ensures that operators are applied to compatible operands
• High-level representations are close to the source language and low-level representations are close to the target machine.

• Syntax trees are high level; they depict the natural hierarchical structure of the source program and are well suited to tasks like static type checking.
• A low-level representation is suitable for machine-dependent tasks like register allocation and instruction selection.
• Three-address code can range from high- to low-level, depending on the choice of operators

​

Value Number method

• Often, the nodes of a syntax tree or DAG are stored in an array of records

​

Method for constructing the nodes of a graph

• Searching the entire array every time we are asked to locate one node is expensive, especially if the array holds expressions from an entire program.
• A more efficient approach is to use a hash table, in which the nodes are put into "buckets," each of which typically will have only a few nodes.

​

Three address code

• Source-language expression like x+y*z might be translated into the sequence of three-address instructions

​

Addresses and instructions

• Three-address code is built from two concepts: addresses and instructions
• An address can be one of the following:
• A name.
• A constant
• A compiler-generated temporary

Common three address instructions

• Assignment instructions of the form x = y op z
• Assignments of the form x = op y
• Copy instructions of the form x = y
• An unconditional jump goto L
• Conditional jumps of the form if x goto L and if False x goto L.
• Conditional jumps such as if x relop y goto L

• Procedure calls and returns are implemented using the following instructions: param x for parameters; call p , n and y = call p , n for procedure and function calls, respectively; and return y, where y, representing a returned value, is optional.
• Indexed copy instructions of the form x = y[i] and x[i] = y
• Address and pointer assignments of the form x = &y, x = *y, and *x = y.

Example

• Consider the statement

do i=i+1; while(a[i]<v) ;

​

Quadruples

• A quadruple (or just "quad!') has four fields, which we call op, arg1, arg2, and result
• The following are some exceptions to this rule:
• Instructions with unary operators like x = minus y or x = y do not use arg2. Note that for a copy statement like x = y, op is =, while for most other operations, the assignment operator is implied.
• Operators like param use neither arg2 nor result.
• Conditional and unconditional jumps put the target label in result

Example

• Three-address  code for  the  assignment  a =  b * - c + b * - c ; appears in Fig.

Triples

• A triple has only three fields, which we call op, arg1, and arg2. Note that the result field in Fig. is used primarily for temporary names
• Using triples, we refer to the result of an operation x op y by its position, rather than by an explicit temporary name.

​

• A ternary operation like x[i] = y requires two entries in the triple structure; for example, we can put x and i in one triple and y in the next. Similarly, x = y[i] can implemented by treating it as if it were the two instructions
• 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 computes a temporary t, then the instructions 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. 

Indirect triples

• Indirect triples consist of a listing of pointers to triples, rather than a listing of triples themselves. With indirect triples, an optimizing compiler can move an instruction by reordering the instruction list, without affecting the triples themselves. 

• Static single-assignment form (SSA) is an intermediate representation that facilitates certain code optimizations. Two distinctive aspects distinguish SSA from three-address code.
• The first is that all assignments in SSA are to variables with distinct names; hence the term static single-assignment

​

• The same variable may be defined in two different control-flow paths in a program. For example, the source program

​

if ( f l a g ) x = -1; e l s e x = 1;

y = x * a;

​

has two control-flow paths in which the variable x gets defined.

​

if ( f l a g ) xi = -1; e l s e x2 = 1; x 3 = ϕ ( x 1 , x 2 ) ;

​

​

Types and declarations

• The applications of types can be grouped under checking and translation:
• Type checking uses logical rules to reason about the behavior of a program at run time. Specifically, it ensures that the types of the operands match the type expected by an operator
• Translation Applications. From the type of a name, a compiler can determine the storage that will be needed for that name at run time

Type expressions

• Types have structure, which we shall represent using type expressions: a type expression is either a basic type or is formed by applying an operator called a type constructor to a type expression.

​

​

​

​

​

• Many type-checking rules have the form, "if two type expressions are equal t h e n return a certain type else error."