INTERMEDIATED CODE

GENERATION

[Link] Rao [Link] VVIT, Nambur 1

INTRODUCTION TO INTERMEDIATE CODE GENERATION:-
The front end translates a source program into an intermediate representation from which
the back end generates target code. Benefits of using a machine-independent intermediate
form are:
[Link] is facilitated. That is, a compiler for a different machine can be created by attaching
a back end for the new machine to an existing front end.
2. A machine-independent code optimizer can be applied to the
intermediate representation.

[Link] Rao [Link] VVIT, Nambur 2

Representations of Intermediate code:
Three ways of intermediate representation:
1) Abstract Syntax Tree( AST )
a) Syntax Tree
b) Directed Acyclic Graph ( DAG )

2) Postfix notation
3) Three Address Code( 3AC / TAC )
a) Quadruples
b) Triples
c) Indirect Triples

[Link] Rao [Link] VVIT, Nambur 3

i) Abstract Syntax Tree
A syntax tree depicts the natural hierarchical structure of a source
program. Syntax trees are called as Abstract Syntax Trees because-

• They are abstract representation of the parse trees.

• They do not provide every characteristic information
from the real syntax.
• For example- no rule nodes, no parenthesis etc.

[Link] Rao [Link] VVIT, Nambur 4

Abstract Syntax tree for the expression x*y-5+z:-

[Link] Rao [Link] VVIT, Nambur 5

[Link] Rao [Link] VVIT, Nambur 6
[Link] Rao [Link] VVIT, Nambur 7
Constructed Syntax tree for x*y-5+z:-

[Link] Rao [Link] VVIT, Nambur 8

ii) Postfix Notation:

[Link] Rao [Link] VVIT, Nambur 9

Construction of Syntax tree using Postfix notation:-

[Link] Rao [Link] VVIT, Nambur 10

[Link] Rao [Link] VVIT, Nambur 11
[Link] Rao [Link] VVIT, Nambur 12
[Link] Rao [Link] VVIT, Nambur 13
 iii) Three-Address Code ( TAC ):
Three-address code is a sequence of statements of the general form
x : = y op z

Where x, y and z are names, constants, or compiler-generated temporaries; op stands for any
operator, such as a fixed- or floating-point arithmetic operator, or a logical operator on boolean
valued data. Thus a source language expression like

x+ y*z
Might be translated into a sequence
t1 : = y * z
t2 : = x + t1
Where t1 and t2 are compiler-generated temporary names.

Each three address code instruction has atmost three operands.

It is a combination of assignment and a binary operator.
[Link] Rao [Link] VVIT, Nambur 14
In three address code there is atmost one operator on the right hand side of an instruction.
Implementation of Three Address Code -
The commonly used representations for implementing Three Address Code are-

1. Quadruples
2. Triples
3. Indirect Triples

[Link] Rao [Link] VVIT, Nambur 15

1. Quadruples representation-
In quadruples representation, each instruction is splitted into the following 4
different fields-
op, arg1, arg2, result
Here-
• The op field is used for storing the internal code of the operator.
• The arg1 and arg2 fields are used for storing the two operands used.
• The result field is used for storing the result of the expression.

[Link] Rao [Link] VVIT, Nambur 16

 Exceptions
There are following exceptions-
Exception-01:
To represent the statement x = op y, we place-
▪ op in the operator field
▪ y in the arg1 field
▪ x in the result field
▪ arg2 field remains unused

[Link] Rao [Link] VVIT, Nambur 17

Exception-02:
To represent the statement like param t1, we place-
▪ param in the operator field
▪ t1 in the arg1 field
▪ Neither arg2 field nor result field is used
Exception-03:
To represent the unconditional and conditional jump statements, we place label of
the target in the result field.

[Link] Rao [Link] VVIT, Nambur 18

2. Triples Representation-
In triples representation,
• References to the instructions are made.
• Temporary variables are not used.

3. Indirect Triples Representation-

• This representation is an enhancement over triples representation.
• It uses an additional instruction array to list the pointers to the triples in the desired order.
• Thus, instead of position, pointers are used to store the results.
• It allows the optimizers to easily re-position the sub-expression for producing the optimized
code. [Link] Rao [Link] VVIT, Nambur 19
PRACTICE PROBLEMS BASED ON
QUADRUPLES, TRIPLES &
INDIRECT TRIPLES-

[Link] Rao [Link] VVIT, Nambur 20

Problem 1:
Translate the following expression to quadruple, triple and indirect triple-
a+bxc/e↑f+bxc

Solution-

Three Address Code for the given expression is-

T1 = e ↑ f
T2 = b x c
T3 = T2 / T1
T4 = b x a
T5 = a + T3
T6 = T5 + T4
[Link] Rao [Link] VVIT, Nambur 21
Now, we write the required representations-
[Link] Rao [Link] VVIT, Nambur 22
[Link] Rao [Link] VVIT, Nambur 23
Problem 2:
Translate the following expression to quadruple, triple and indirect triple-
a=bx–c+bx–c

Solution-

Three Address Code for the given expression is-

T1 = uminus c
T2 = b x T1
T3 = uminus c
T4 = b x T3
T5 = T2 + T4
a = T5
Now, we write the required representations-
[Link] Rao [Link] VVIT, Nambur 24
[Link] Rao [Link] VVIT, Nambur 25
[Link] Rao [Link] VVIT, Nambur 26
[Link] Rao [Link] VVIT, Nambur 27
[Link] Rao [Link] VVIT, Nambur 28
[Link] Rao [Link] VVIT, Nambur 29
[Link] Rao [Link] VVIT, Nambur 30
[Link] Rao [Link] VVIT, Nambur 31
[Link] Rao [Link] VVIT, Nambur 32
[Link] Rao [Link] VVIT, Nambur 33
[Link] Rao [Link] VVIT, Nambur 34
[Link] Rao [Link] VVIT, Nambur 35
[Link] Rao [Link] VVIT, Nambur 36
[Link] Rao [Link] VVIT, Nambur 37
[Link] Rao [Link] VVIT, Nambur 38
[Link] Rao [Link] VVIT, Nambur 39
[Link] Rao [Link] VVIT, Nambur 40
Problem 5:-

[Link] Rao [Link] VVIT, Nambur 41

Problem 6:-

[Link] Rao [Link] VVIT, Nambur 42

Problem 7:-

[Link] Rao [Link] VVIT, Nambur 43

Problem 8:-

[Link] Rao [Link] VVIT, Nambur 44

[Link] Rao [Link] VVIT, Nambur 45
[Link] Rao [Link] VVIT, Nambur 46
[Link] Rao [Link] VVIT, Nambur 47
[Link] Rao [Link] VVIT, Nambur 48
[Link] Rao [Link] VVIT, Nambur 49
[Link] Rao [Link] VVIT, Nambur 50
[Link] Rao [Link] VVIT, Nambur 51
Conversions between primitive types in Java

[Link] Rao [Link] VVIT, Nambur 52

Introducing type conversions into expression
evaluation

[Link] Rao [Link] VVIT, Nambur 53

Directed Acyclic Graph-
• Directed Acyclic Graph (DAG) is a special kind of Abstract Syntax Tree.
• Each node of it contains a unique value.
• It does not contain any cycles in it, hence called Acyclic.
• A DAG is constructed for optimizing the basic block.
• A DAG is usually constructed using Three Address Code.
• Transformations such as dead code elimination and common sub expression
elimination are then applied.
Properties-
• Reachability relation forms a partial order in DAGs.
• Both transitive closure & transitive reduction are uniquely defined for DAGs.
• Topological Orderings are defined for DAGs.
[Link] Rao [Link] VVIT, Nambur 54
Applications:-
• DAGs are used for the following purposes-
• To determine the expressions which have been computed more than
once (called common sub-expressions).
• To determine the names whose computation has been done outside
the block but used inside the block.
• To determine the statements of the block whose computed value can
be made available outside the block.
• To simplify the list of Quadruples by not executing the assignment
instructions x:=y unless they are necessary and eliminating the
common sub-expressions.

[Link] Rao [Link] VVIT, Nambur 55

Construction of DAGs-
Following rules are used for the construction of DAGs-
Rule-01:

In a DAG,
Interior nodes always represent the operators.
Exterior nodes (leaf nodes) always represent the names, identifiers or constants.

Rule-02:

While constructing a DAG,

A check is made to find if there exists any node with the same value.
A new node is created only when there does not exist any node with the same value.
This action helps in detecting the common sub-expressions and avoiding the re-computation of the same.

Rule-03:

The assignment instructions of the form x:=y are not performed unless they are necessary.
[Link] Rao [Link] VVIT, Nambur 56
Problem-01:
Consider the following expression and construct a DAG for
it-( a + b ) x ( a + b + c )

[Link] Rao [Link] VVIT, Nambur 57

Problem-02:

Consider the following expression and construct a DAG for it-

(((a+a)+(a+a))+((a+a)+(a+a)))

[Link] Rao [Link] VVIT, Nambur 58

[Link] Rao [Link] VVIT, Nambur 59
Backpatching in Compiler Design
• The problem in generating three address codes in a single pass is that we may not
know the labels that control must go to at the time jump statements are generated.
• So to get around this problem a series of branching statements with the targets of
the jumps temporarily left unspecified is generated.
• Back Patching is putting the address instead of labels when the proper label is
determined.
• Back patching Algorithms perform three types of operations
✓1) makelist (i) – creates a new list containing only i, an index into the array of
quadruples and returns pointer to the list it has made.
✓2) Merge (i, j) – concatenates the lists pointed to by i and j, and returns a pointer
to the concatenated list.
✓3) Backpatch (p, i) – inserts i as the target label for each of the statements on the
list pointed to by p. [Link] Rao [Link] VVIT, Nambur 60
Example: x<100|| y>200 && x!=y

Before applying backpatching After applying backpatching

[Link] Rao [Link] VVIT, Nambur 61

Back patching for Boolean Expressions
• We now construct a translation scheme suitable for generating code for boolean
expressions during bottom-up parsing.

[Link] Rao [Link] VVIT, Nambur 62

Translation Rules

[Link] Rao [Link] VVIT, Nambur 63

[Link] Rao [Link] VVIT, Nambur 64
[Link] Rao [Link] VVIT, Nambur 65
[Link] Rao [Link] VVIT, Nambur 66
[Link] Rao [Link] VVIT, Nambur 67
[Link] Rao [Link] VVIT, Nambur 68
[Link] Rao [Link] VVIT, Nambur 69
[Link] Rao [Link] VVIT, Nambur 70
[Link] Rao [Link] VVIT, Nambur 71