Optimization Notion - II 393
12.1.2 Different Forms of 3AC Statements
1 a = y op z op can be (operator)
• Arithmetic operator
• Assignment operator
• Increment/Decrement operator
• Relational operator
• Logical operator
• Conditional operator
• Bitwise operator
• Special operators
2 a = op y Unary Assignment operation
3 a=b Copy Assignment operation
4 goto L Unconditional jump
return L where L is label
5 if (x condition y) goto L Conditional jump
if (x condition y) goto L where L is label
else if (x condition y) goto L
switch goto L
6 param x Procedure call
call p, n
return z
7 a=b[i] Index assignment
8 x[i]=y Indexed assignment
9 x=&y Reference assignment
10 *x= y Pointer assignment
x=*y
12.1.3 Structure of Three Address Code (3AC)
There are 3 types of three address code structure.
• Quadruples
• Triples
• Indirect triples
394 Compiler Design
Three Types of 3AC
Quadruples 3AC Triples 3AC Indirect Triples 3AC
Definition: A structure which holds quad (4) fields such as op (operator), arg1(argument
1), arg2 (argument 2) and result is called quadruple.
Syntax:
op, arg1, arg2, result or op, operator1, operator2, result
Advantages:
• It is easy to rearrange the three address code for global optimization.
Disadvantages:
• It involves lots of temporary values for computations.
• The computation time and space utilization of symbol table is high.
EXAMPLE [Link]: Consider the expression and furnish quadruple for it.
a=b+c*d
Three address code (3AC):
1. t1 = c * d
2. t2 = b + t1
3. a = t2
Quadruples using 3AC:
Op arg1 arg2 result
* c d t1
+ b t1 t2
= t2 a
Note For the above expression, quadruples are written using 3AC because without
temporary variables the computed result cannot be stored in final result variable.
EXAMPLE [Link]: Consider the expression and furnish quadruple for it.
a = b *d
Three address code (3AC):
1. t1 = b * d
2. a = t1
Optimization Notion - II 395
Quadruples using 3AC:
Op arg1 arg2 result
* b d t1
= t1 a
EXAMPLE [Link]: Think about the expression given below and furnish quadruple
for it.
a = b + c * d/e
Three Address Code:
1. t1 = c * d
2. t2 = t1/e
3. t3 = b + t2
4. a = t3
Quadruples using 3AC:
Op arg1 arg2 result
* c d t1
/ t1 e t2
+ b t2 t3
= t3 a
EXAMPLE [Link]: Consider the expression and furnish quadruple for it.
a=b*c+b*d
Three Address Code:
1. t1 = b* c
2. t2 = b * d
3. t3 = t1 + t2
4. a = t3
Quadruples using 3AC:
Op arg1 arg2 result
* b c t1
* b d t2
+ t1 t2 t3
= t3 a
EXAMPLE [Link]: Consider the expression and furnish quadruple for it.
x = (-b + sqrt (b * b – 4 * a* c)) / (2 *a)
396 Compiler Design
Three Address Code:
1. t1 = b*b
2. t2 = 4 * a
3. t3 = t2 * c
4. t4 = t1 – t3
5. t5 = sqrt(t4)
6. t6 = 0 –b
7. t7 = t5 + t6
8. t8 = 2*a
9. t9= t7/ t8
10. x = t9
Quadruples using 3AC:
Op arg1 arg2 result
* b b t1
* 4 a t2
* t2 c t3
- t1 t3 t4
= t4 t5
- 0 b t6
+ t5 t6 t7
* 2 a t8
/ t7 t8 t9
= t9 x
EXAMPLE [Link]: Consider the expression and furnish quadruple for it.
x = (a + b) * (d – c)
Three Address Code:
1. t1 = a + b
2. t2 = d – c
3. t3 = t1 * t2
4. x = t3
Quadruples using 3AC:
Op arg1 arg2 result
+ a b t1
- d c t2
* t1 t2 t3
= t3 x
Optimization Notion - II 397
EXAMPLE [Link]: Consider the expression and furnish quadruple for it.
x = (a + b) * (c + d) ^ (a + b)
Three Address Code:
1. t1 = a + b
2. t2 = c + d
3. t3 = t1 * t2
4. t4 = t3 ^ t1
5. x = t4
Quadruples using 3AC:
Op arg1 arg2 result
+ a b t1
+ c d t2
* t1 t2 t3
^ t3 t1 t4
= t4 x
EXAMPLE [Link]: Consider the expression and furnish quadruple for it.
x=a+b*c–d/e*h
Three Address Code:
1. t1 = b * c
2. t2 = d/e
3. t3 = t2 * h
4. t4 = a + t1
5. t5 = t4 – t3
6. x = t5
Quadruples using 3AC:
Op arg1 arg2 result
+ b c t1
/ d e t2
* t2 h t3
+ a t1 t4
- t4 t3 t5
= t5 x
398 Compiler Design
Triples
Definition: A structure which holds tri (3) fields such as op (operator), arg1 (argument
1), arg2 (argument 2) is called a triple. The results of respective sub-expressions are
denoted by the position of expression.
Syntax:
Operator, operand1, operand2
Advantages
• The temporaries are indirectly involved.
Disadvantages
• It is difficult to rearrange the code.
Note For any given expression, triples are written without using three address code.
EXAMPLE [Link]: Consider the expression and come up with triples for it.
a=b+c*d
Triples:
Position Op arg1 arg2
0 * c d
1 + b 0
2 = 1
EXAMPLE [Link]: Consider the expression and come up with triples for it.
a = b *d
Triples:
Position Op arg1 arg2
0 * b d
1 = 0
EXAMPLE [Link]: Consider the expression and come up with triples for it.
a = b + c * d/e
Triples:
Position Op arg1 arg2
0 * c d
1 / 0 e
2 + b 1
3 = 2
Optimization Notion - II 399
EXAMPLE [Link]: Consider the expression and come up with triples for it.
a=b*c+b*d
Triples:
Position Op arg1 arg2
0 * b c
1 * b d
2 + 0 1
3 = 3
EXAMPLE [Link]: Consider the expression and come up with triples for it.
a = b * c / d + 3.2 * 2 / e
Triples:
Position Op arg1 arg2
0 * b c
1 / 0 d
2 * 3.2 2
3 / 2 5
4 + 1 3
5 = 4
EXAMPLE [Link]: Consider the expression and come up with triples for it.
result = ((a + (b – c) * d) ^ e + f)
Triples:
Position Op arg1 arg2
0 - b c
1 * 0 d
2 + a 1
3 ^ 2 e
4 + 3 f
5 = 4
EXAMPLE [Link]: Consider the expression and come up with triples for it.
a=x^y^z–m+n+p/q
400 Compiler Design
Triples:
Position Op arg1 arg2
0 / p q
1 - z m
2 + 1 n
3 + 2 1
4 ^ x y
5 ^ 4 3
6 = 5
EXAMPLE [Link]: Consider the expression and come up with triples for it.
A = X ^ Y * Z – M + N + P | Q | (R + S)
Triples:
Position Op arg1 arg2
0 + R S
1 * Y Z
2 - 1 M
3 + 2 N
4 + 3 P
5 ^ X 4
6 | 5 Q
7 | 6 0
8 = 7
EXAMPLE [Link]: Consider the expression and come up with triples for it.
a [i] = b
Triples:
Position Op arg1 arg2
0 [] = a i
1 assign 0 b
Optimization Notion - II 401
EXAMPLE [Link]: Consider the expression and come up with triples for it.
a = b[i]
Triples:
Position Op arg1 arg2
0 =[] b i
1 assign a 0
Indirect Triples
Definition: A structure which holds tri (3) fields such as op (operator), arg1 (argument
1), arg2 (argument 2). An enhancement of triples which uses pointers for position of
expression to store results instead of listing triples. The general form is shown below.
Statement Operator Operand 1 Operand 2
(0) (55) (55) * b 5
(1) (56) (56) + a (55)
(2) (57) (57) = c (56)
Advantages
• Temporaries are involved in the names of pointers.
• Rearrangement of code becomes easier.
Now, let us compare quadruples, triples and indirect triples.
S. No Quadruples Triples Indirect Triples
1. A three-address code A three address code can A three address code can
statement can be accessed be accessed by using the be accessed by using the
immediately from the value of statement. pointers instead of using
storage because of the the temporary values.
compiler-generated
temporaries.
2. Computation of values in Each computation of values Computation is easy
the symbol table provides requires us to change all because of its pointers. It
an extra degree references. enables the optimizers to
of indirection. freely re-position the sub-
expression.
3. It is difficult since its It utilizes lesser memory Utilization of memory
memory references change space than quadruples. space is high.
over computations. It
requires extra storage
space.