Tag: indirect triples

Quadruples, Triples and Indirect Triples

Three Address Code-

 

Before you go through this article, make sure that you have gone through the previous article on Three Address Code.

 

We have discussed-

  • Three Address Code is a form of an intermediate code.
  • It is generated by the compiler for implementing Code Optimization.
  • It uses maximum three addresses to represent any statement.

 

In this article, we will discuss Implementation of Three Address Code.

 

Implementation-

 

Three Address Code is implemented as a record with the address fields.

 

The commonly used representations for implementing Three Address Code are-

 

 

  1. Quadruples
  2. Triples
  3. Indirect Triples

 

1. Quadruples-

 

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.

 

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

 

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.

 

2. Triples-

 

In triples representation,

  • References to the instructions are made.
  • Temporary variables are not used.

 

3. Indirect Triples-

 

  • 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.

 

PRACTICE PROBLEMS BASED ON QUADRUPLES, TRIPLES & INDIRECT TRIPLES-

 

Problem-01:

 

Translate the following expression to quadruple, triple and indirect triple-

a + b x c / e ↑ f + b x c

 

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

 

Now, we write the required representations-

 

Quadruple Representation-

 

Location Op Arg1 Arg2 Result
(0) e f T1
(1) x b c T2
(2) / T2 T1 T3
(3) x b a T4
(4) + a T3 T5
(5) + T5 T4 T6

 

Triple Representation-

 

Location Op Arg1 Arg2
(0) e f
(1) x b c
(2) / (1) (0)
(3) x b a
(4) + a (2)
(5) + (4) (3)

 

Indirect Triple Representation-

 

Statement
35 (0)
36 (1)
37 (2)
38 (3)
39 (4)
40 (5)

 

Location Op Arg1 Arg2
(0) e f
(1) x b e
(2) / (1) (0)
(3) x b a
(4) + a (2)
(5) + (4) (3)

 

Problem-02:

 

Translate the following expression to quadruple, triple and indirect triple-

a = b x – c + b x – 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-

 

Quadruple Representation-

 

Location Op Arg1 Arg2 Result
(1) uminus c T1
(2) x b T1 T2
(3) uminus c T3
(4) x b T3 T4
(5) + T2 T4 T5
(6) = T5 a

 

Triple Representation-

 

Location Op Arg1 Arg2
(1) uminus c
(2) x b (1)
(3) uminus c
(4) x b (3)
(5) + (2) (4)
(6) = a (5)

 

Indirect Triple Representation-

 

Statement
35 (1)
36 (2)
37 (3)
38 (4)
39 (5)
40 (6)

 

Location Op Arg1 Arg2
(1) uminus c
(2) x b (1)
(3) uminus c
(4) x b (3)
(5) + (2) (4)
(6) = a (5)

 

To gain better understanding about Quadruples, Triples and Indirect Triples,

Watch this Video Lecture

 

Download Handwritten Notes Here-

 

 

Next Article- Basic Blocks and Flow Graphs

 

Get more notes and other study material of Compiler Design.

Watch video lectures by visiting our YouTube channel LearnVidFun.