Subjects | Gate Vidyalay

Category: Subjects

Three Address Code | Examples

Compiler Design

Three Address Code-

Three Address Code is a form of an intermediate code.

The characteristics of Three Address instructions are-

They are generated by the compiler for implementing Code Optimization.
They use maximum three addresses to represent any statement.
They are implemented as a record with the address fields.

General Form-

In general, Three Address instructions are represented as-

a = b op c

Here,

a, b and c are the operands.
Operands may be constants, names, or compiler generated temporaries.
op represents the operator.

Examples-

Examples of Three Address instructions are-

a = b + c
c = a x b

Common Three Address Instruction Forms-

The common forms of Three Address instructions are-

1. Assignment Statement-

x = y op z and x = op y

Here,

x, y and z are the operands.
op represents the operator.

It assigns the result obtained after solving the right side expression of the assignment operator to the left side operand.

2. Copy Statement-

x = y

Here,

x and y are the operands.
= is an assignment operator.

It copies and assigns the value of operand y to operand x.

3. Conditional Jump-

If x relop y goto X

Here,

x & y are the operands.
X is the tag or label of the target statement.
relop is a relational operator.

If the condition “x relop y” gets satisfied, then-

The control is sent directly to the location specified by label X.
All the statements in between are skipped.

If the condition “x relop y” fails, then-

The control is not sent to the location specified by label X.
The next statement appearing in the usual sequence is executed.

4. Unconditional Jump-

goto X

Here, X is the tag or label of the target statement.

On executing the statement,

The control is sent directly to the location specified by label X.
All the statements in between are skipped.

5. Procedure Call-

param x call p return y

Here, p is a function which takes x as a parameter and returns y.

PRACTICE PROBLEMS BASED ON THREE ADDRESS CODE-

To solve the problems, Learn about the Precedence Relations and Associativity of Operators.

Problem-01:

Write Three Address Code for the following expression-

a = b + c + d

Solution-

The given expression will be solved as-

Three Address Code for the given expression is-

(1) T1 = b + c

(2) T2 = T1 + d

(3) a = T2

Problem-02:

Write Three Address Code for the following expression-

-(a x b) + (c + d) – (a + b + c + d)

Solution-

Three Address Code for the given expression is-

(1) T1 = a x b

(2) T2 = uminus T1

(3) T3 = c + d

(4) T4 = T2 + T3

(5) T5 = a + b

(6) T6 = T3 + T5

(7) T7 = T4 – T6

Problem-03:

Write Three Address Code for the following expression-

If A < B then 1 else 0

Solution-

Three Address Code for the given expression is-

(1) If (A < B) goto (4)

(2) T1 = 0

(3) goto (5)

(4) T1 = 1

(5)

Problem-04:

Write Three Address Code for the following expression-

If A < B and C < D then t = 1 else t = 0

Solution-

Three Address Code for the given expression is-

(1) If (A < B) goto (3)

(2) goto (4)

(3) If (C < D) goto (6)

(4) t = 0

(5) goto (7)

(6) t = 1

(7)

Also Read- More Problems On Three Address Code

To gain better understanding about Three Address Code,

Watch this Video Lecture

Download Handwritten Notes Here-

Next Article- Quadruples, Triples & Indirect Triples

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Directed Acyclic Graphs | DAGs | Examples

Compiler Design

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.

Optimization Of Basic Blocks-

DAG is a very useful data structure for implementing transformations on Basic Blocks.

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.

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.

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.

Also Read- Code Optimization

PRACTICE PROBLEMS BASED ON DIRECTED ACYCLIC GRAPHS-

Problem-01:

Consider the following expression and construct a DAG for it-

( a + b ) x ( a + b + c )

Solution-

Three Address Code for the given expression is-

T1 = a + b

T2 = T1 + c

T3 = T1 x T2

Now, Directed Acyclic Graph is-

NOTE

From the constructed DAG, we observe-

The common sub-expression (a+b) has been expressed into a single node in the DAG.
The computation is carried out only once and stored in the identifier T1 and reused later.

This illustrates how the construction scheme of a DAG identifies the common sub-expression and helps in eliminating its re-computation later.

Problem-02:

Consider the following expression and construct a DAG for it-

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

Solution-

Directed Acyclic Graph for the given expression is-

Problem-03:

Consider the following block and construct a DAG for it-

(1) a = b x c

(2) d = b

(3) e = d x c

(4) b = e

(5) f = b + c

(6) g = f + d

Solution-

Directed Acyclic Graph for the given block is-

Problem-04:

Optimize the block in the Problem-03.

Solution-

Step-01:

Firstly, construct a DAG for the given block (already done above).

Step-02:

Now, the optimized block can be generated by traversing the DAG.

The common sub-expression e = d x c which is actually b x c (since d = b) is eliminated.
The dead code b = e is eliminated.

The optimized block is-

(1) a = b x c

(2) d = b

(3) f = a + c

(4) g = f + d

Problem-05:

Consider the following basic block-

B10:

S1 = 4 x I

S2 = addr(A) – 4

S3 = S2[S1]

S4 = 4 x I

S5 = addr(B) – 4

S6 = S5[S4]

S7 = S3 x S6

S8 = PROD + S7

PROD = S8

S9 = I + 1

I = S9

If I <= 20 goto L10

Draw a directed acyclic graph and identify local common sub-expressions.
After eliminating the common sub-expressions, re-write the basic block.

Solution-

Directed Acyclic Graph for the given basic block is-

In this code fragment,

4 x I is a common sub-expression. Hence, we can eliminate because S1 = S4.
We can optimize S8 = PROD + S7 and PROD = S8 as PROD = PROD + S7.
We can optimize S9 = I + 1 and I = S9 as I = I + 1.

After eliminating S4, S8 and S9, we get the following basic block-

B10:

S1 = 4 x I

S2 = addr(A) – 4

S3 = S2[S1]

S5 = addr(B) – 4

S6 = S5[S1]

S7 = S3 x S6

PROD = PROD + S7

I = I + 1

If I <= 20 goto L10

To gain better understanding about Directed Acyclic Graphs,

Watch this Video Lecture

Download Handwritten Notes Here-

Next Article- Misc Problems On Directed Acyclic Graphs

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.

Basic Blocks and Flow Graphs | Examples

Compiler Design

Basic Blocks-

Basic block is a set of statements that always executes in a sequence one after the other.

The characteristics of basic blocks are-

They do not contain any kind of jump statements in them.
There is no possibility of branching or getting halt in the middle.
All the statements execute in the same order they appear.
They do not lose lose the flow control of the program.

Example Of Basic Block-

Three Address Code for the expression a = b + c + d is-

Here,

All the statements execute in a sequence one after the other.
Thus, they form a basic block.

Also Read- Three Address Code

Example Of Not A Basic Block-

Three Address Code for the expression If A<B then 1 else 0 is-

Here,

The statements do not execute in a sequence one after the other.
Thus, they do not form a basic block.

Partitioning Intermediate Code Into Basic Blocks-

Any given code can be partitioned into basic blocks using the following rules-

Rule-01: Determining Leaders-

Following statements of the code are called as Leaders–

First statement of the code.
Statement that is a target of the conditional or unconditional goto statement.
Statement that appears immediately after a goto statement.

Rule-02: Determining Basic Blocks-

All the statements that follow the leader (including the leader) till the next leader appears form one basic block.
The first statement of the code is called as the first leader.
The block containing the first leader is called as Initial block.