Intermediate-Code

Generation
 Introduction
In the analysis-synthesis model of a compiler, the front end analyzes a
source program and creates an intermediate representation, from
which the back end generates target code.
A compiler front end is organized as below
 Introduction
• In the process of translating a program in a given source language into code
for a given target machine, a compiler may construct a sequence of
intermediate representations.

• Syntax trees are high level and 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.
Variants of Syntax Trees
A directed acyclic graph (DAG) for an expression identifies the common
subexpressions of the expression.
DAG's can be constructed by using the same techniques that construct
syntax trees.
The difference is that a node N in a DAG has more than one parent if N
represents a common subexpression; in a syntax tree, the tree for the
common subexpression would be replicated as many times as the
subexpression appears in the original expression.
Variants of Syntax Trees
DAG for the expression a + a * (b - c) + (b - c) * d
Variants of Syntax Trees
Syntax-directed definition to produce syntax trees or DAG’s
Variants of Syntax Trees
Steps for constructing the above DAG
 The Value-Number Method for Constructing DAG's
• The nodes of a syntax tree or DAG are stored in an array of records.
• Each row of the array represents one record i.e.,one node. In each record,
the first field is an operation code, indicating the label of the node.
• Leaves have one additional field, which holds the lexical value and interior
nodes have two additional fields indicating the left and right children.
The Value-Number Method for Constructing DAG's
• In this array, we refer to nodes by giving the integer index of the
record for that node within the array. This integer is called the value
number for the node or for the expression represented by the node.
• Suppose that nodes are stored in an array and each node is referred
to by its value number.
• Let the signature of an interior node be the triple <op, l, r>, where op
is the label, l its left child's value number, and r its right child's value
number.
• A unary operator may be assumed to have r = 0.
The Value-Number Method for Constructing DAG's
Algorithm: The value-number method for constructing the nodes of a
DAG.
INPUT: Label op, node l, and node r.
OUTPUT: The value number of a node in the array with signature <op,l,
r>.
METHOD: Search the array for a node M with label op, left child l, and
right child r. If there is such a node, return the value number of M. If
not, create in the array a new node N with label op, left child l, and
right child r, and return its value number.
The Value-Number Method for Constructing DAG's
• An efficient approach to search in the entire array is to use a hash
table, in which the nodes are put into “buckets” , each of which
typically will have only a few nodes.
• To construct a hash table for the nodes of a DAG, we need a hash
function h that computes the index of the bucket for a signature
<op, l, r>, in a way that distributes the signatures across buckets.
• The bucket index h(op, l, r) is computed deterministically from op, l,
and r, so that we may repeat the calculation and always get to the
same bucket index for node <op, l, r>.
The Value-Number Method for Constructing DAG's
Three-Address Code
• In three-address code, there is at most one operator on the right side
of an instruction.
Eg:x+y*z

Three-address code for the above DAG is

Three-Address Code - addresses and instructions
Three-address code is built from two concepts: addresses and instructions.
An address can be one of the following:
▪ A name. For convenience, we allow source-program names to appear as
addresses in three-address code. In an implementation, a source name
is replaced by a pointer to its symbol-table entry, where all information
about the name is kept.
▪ A constant. In practice, a compiler must deal with many different types
of constants and variables
▪ A compiler-generated temporary.
Three-Address Code - addresses and instructions
Common three-address instruction forms:
1. Assignment instructions of the form x = y op z.
2. Assignments of the form x = op y
3. Copy instructions of the form x = y
4. An unconditional jump goto L.
5. Conditional jumps of the form if x goto L and ifFalse x goto L
6. Conditional jumps such as if x relop y goto L
7. Procedure calls and returns

8. Indexed copy instructions of the form x = y[i] and x[i]=y.

9. Address and pointer assignments of the form x = &y, x = *y, and * x =
y.
Eg: do i = i+1; while (a[i] < v);
Quadruples
• A quadruple has four fields, which we call op, arg1, arg2,and result.
Eg: a = b* -c+b*-c;
Triples
• A triple has only three fields, which we call op, arg1, and arg2.
• Using triples, we refer to the result of an operation x op y by its
position, rather than by an explicit temporary name.
 Indirect triples
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.
This problem does not occur with indirect triples.
Indirect triples consist of a listing of pointers to triples, rather than a listing
of triples themselves.
Static Single-Assignment Form
• Static single-assignment form (SSA) is an intermediate representation
that facilitates certain code optimizations.
• Two distinctive aspects distinguish SSA from three-address code.
-All assignments in SSA are to variables with distinct names;
• The same variable may be defined in two different control-flow paths
in a program.
Eg: if ( flag ) x = -1; else x = 1;
y = x * a;
SSA uses a notational convention called the ǿ-function to combine the
two definitions of x:
if ( flag ) x1 = -1; else x2 = 1;
x3 = ǿ (x1, x2);
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.
▪ Translation Applications: From the type of a name, a compiler can
determine the storage that will be needed for that name at run time.
Types and Declarations
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.
Eg: The array type int[2][3] can be read as “array of 2 arrays of 3
integers each" and written as a type expression
array(2, array(3, integer))
Types and Declarations
Definition of type expressions:
▪ A basic type is a type expression.
▪ A type name is a type expression.
▪ A type expression can be formed by applying the array type
constructor to a number and a type expression.
▪ A type expression can be formed by applying the record type
constructor.
▪ A type expression can be formed by using the type constructor →for
function types.
▪ If s and t are type expressions, then their Cartesian product s X t is a
type expression.
▪ Type expressions may contain variables whose values are type
expressions.
Types and Declarations
Type Equivalence:
When type expressions are represented by graphs, two types are
structurally
equivalent if and only if one of the following conditions is true:
▪ They are the same basic type.
▪ They are formed by applying the same constructor to structurally
equivalent types.
▪ One is a type name that denotes the other.
Types and Declarations
Declarations:
Types and Declarations
Storage Layout for Local Names:
From the type of a name, we can determine the amount of storage that
will be needed for the name at run time.
At compile time, we can use these amounts to assign each name a
relative address.
The type and relative address are saved in the symbol-table entry for
the name.
Data of varying length, such as strings, or data whose size cannot be
determined until run time, such as dynamic arrays, is handled by
reserving a known fixed amount of storage for a pointer to the data.
Types and Declarations
SDD for computing the types and their widths
Types and Declarations
Eg: int[2][3]
Types and Declarations
Sequences of Declarations:
The following translation scheme deals with a sequence of declarations
of the form T id, where T generates a type.
Types and Declarations
Fields in Records and Classes:
Record types will encode both the types and relative addresses of
theirfields, using a symbol table for the record type.
A record type has the form record(t), where record is the type
constructor, and t is a symbol-table object that holds information about
the fields of this record type.
The following translation scheme can be used to handle field names in
records.
Translation of Expressions
Operations Within Expressions:
Translation of Expressions
Eg: a = b +-c

t1 = minus c
t2 = b + t1
a = t2
Translation of Expressions
Incremental Translation:
In the incremental approach, gen not only constructs a three-address
instruction, it appends the instruction to the sequence of instructions
generated so far.
Translation of Expressions
Addressing Array Elements:
Array elements are numbered 0,1,…., n-1, for an array with n elements.
If the width of each array element is w, then the ith element of array A
begins in location base + i x w
The relative address of A[i1][i2] can then be calculated by the formula
base + i1 x w1 + i2 x w2
Alternatively, the relative address of an array reference can be
calculated in terms of the numbers of elements nj along dimension j of
the array and the width w = wk of a single element of the array. In two
dimensions (i.e., k = 2 and w = w2), the location for A[i1][i2] is given by
base + (i1 x n2 + i2) x w
Translation of Expressions
• Compile-time pre calculation can also be applied to address
calculations for elements of multidimensional arrays
• Compile-time pre calculation is not possible when the array’s size is
dynamic.
• The above address calculations are based on row-major layout for
arrays
Translation of Expressions
Translation of Array References
• Let L generate an array name followed by a sequence of index
expressions:
• The following translation scheme generates three-address code for
expressions with array references
Translation of Array References
Translation of Array References
Eg: Let a denote a 2 x 3 array of integers, and let c, i, and j all denote
integers. Then, the type of a is array(2, array(3, integer)).
Its width w is 24, assuming that the width of an integer is 4. The type of
a[i] is array(3, integer), of width w1 = 12. The type of a[i][j] is integer.
Translation of Array References
Type Checking
Rules for Type Checking
Type checking can take on two forms: synthesis and inference.
Type synthesis builds up the type of an expression from the types of its
subexpressions.
A typical rule for type synthesis has the form

Type inference determines the type of a language construct from the

way it is used. A typical rule for type inference has the form
Type Checking
Type Conversions
▪ Type conversion rules vary from language to language.
▪ Conversion from one type to another is said to be implicit if it is done
automatically by the compiler. Implicit type conversions, also called
coercions, are limited in many languages to widening conversions.
▪ Conversion is said to be explicit if the programmer must write
something to cause the conversion. Explicit conversions are also
called casts.
Type Checking
Overloading of Functions and Operators
An overloaded symbol has different meanings depending on its
context.
Overloading is resolved when a unique meaning is determined for each
occurrence of a name.
The following is a type-synthesis rule for overloaded functions:
Type Checking
Type Inference and Polymorphic Functions
Type Checking
Type Inference and Polymorphic Functions
Type Checking
An Algorithm for Unification
Control Flow
In programming languages, boolean expressions are often used to
1. Alter the flow of control
2. Compute logical values
Boolean expressions can be generated by the following grammar:

In short-circuit (or jumping) code, the boolean operators &&, ||, and !
translate into jumps.
Eg: if ( x < 100 || x > 200 && x != y ) x = 0;
Control Flow
Flow-of-Control Statements
Control Flow
Control Flow
Control-Flow Translation of Boolean Expressions
Avoiding Redundant Gotos
Avoiding Redundant Gotos
Backpatching
Backpatching is an approach in which lists of jumps are passed as
synthesized attributes.
Specifically, when a jump is generated, the target of the jump is
temporarily left unspecified.
Each such jump is put on a list of jumps whose labels are to be filled in
when the proper label can be determined.
All of the jumps on a list have the same target label.
▪ One-Pass Code Generation Using Backpatching
▪ Backpatching for Boolean Expressions
▪ Flow-of-Control Statements
▪ Break-, Continue-, and Goto-Statements
Switch-Statements
Translation of Switch-Statements
The intended translation of a switch is code to:
1. Evaluate the expression E.
2. Find the value Vj in the list of cases that is the same as the value of
the expression. Recall that the default value matches the expression if
none of the values explicitly mentioned in cases does.
3. Execute the statement Sj associated with the value found.
Switch-Statements
Syntax-Directed Translation of Switch-Statements