Quadrupules,Triples,Indirect Triples

Implementations of three-Address Statements

 

A three-address statement is an abstract form of intermediate code. In a compiler, these statements can be implemented as records with fields for the operator and the operands. Three such representations are quadruples, triples, and indirect triples.

Quadruples

A quadruple is a record structure with four fields, which we call op, arg l, arg 2, and result. The op field contains an internal code for the operator. The three-address statement x:= y op z is represented by placing y in arg 1. z in arg 2. and x in result. Statements with unary operators like x: = – y or x: = y do not use arg 2. Operators like param use neither arg2 nor result. Conditional and unconditional jumps put the target label in result. The quadruples in Fig. H.S(a) are for the assignment a: = b+ – c + b i – c. They are obtained from the three-address code in Fig. 8.5(a). The contents of fields arg 1, arg 2, and result are normally pointers to the symbol-table entries for the names represented by these fields. If so, temporary names must be entered into the symbol table as they are created.

Triples

To avoid entering temporary names into the symbol table. we might refer to a temporary value bi the position of the statement that computes it. If we do so, three-address statements can be represented by records with only three fields: op, arg 1 and arg2, as in Fig. 8.8(b). The fields arg l and arg2, for the arguments of op, are either pointers to the symbol table (for programmer- defined names or constants) or pointers into the triple structure (for temporary values). Since three fields are used, this intermediate code format is known as triples.’ Except for the treatment of programmer-defined names, triples correspond to the representation of a syntax tree or dag by an array of nodes, as in Fig. 8.4.

 fig8.8(a)Qudraples    

 

op

Arg1

Arg2

Result

 (0)

uminus

  c

 

  t1

 (1)

   *

  b

  t1

   t2

 (2)

uminus

  c

 

   t3

 (3)

   *

  b

  t3

   t4

 (4)

   +

  t2

  t4

   t5

 (5)

   :=

  t5

 

    a

 

op

Arg1

Arg2

 (0)

uminus

  c

 

 (1)

   *

  b

  (0)

 (2)

uminus

  c

 

 (3)

   *

  b

  (2)

 (4)

   +

  (1)

  (3)

 (5)

   :=

   a

  (4)

                                                                                                                                                fig8.8(b) Triples        

 

            Parenthesized numbers represent pointers into the triple structure, while symbol-table pointers are represented by the names themselves. In practice, the information needed to interpret the different kinds of entries in the arg 1 and arg2 fields can be encoded into the op field or some additional fields. The triples in Fig. 8.8(b) correspond to the quadruples in Fig. 8.8(a). Note that the copy statement a:= t5 is encoded in the triple representation by placing a in the arg 1 field and using the operator assign. A ternary operation like x[ i ]: = y requires two entries in the triple structure, as shown in Fig. 8.9(a), while x: = y[i] is naturally represented as two operations in Fig. 8.9(b).

 

 

 

Indirect Triples

Another implementation of three-address code that has been considered is that of listing pointers to triples, rather than listing the triples themselves. This implementation is naturally called indirect triples. For example, let us use an array statement to list pointers to triples in the desired order. Then the triples in Fig. 8.8(b) might be represented as in Fig. 8.10.

Comparison of Representations: The Use of Indirection

 

The difference between triples and quadruples may be regarded as a matter of how much indirection is present in the representation. When we ultimately produce target code, each name, temporary or programmer-defined, will be assigned some run-time memory location. This location will be placed in the symbol-table entry for the datum. Using the quadruple notation, a three- address statement defining or using a temporary can immediately access the location for that temporary via the symbol table.

            A more important benefit of quadruples appears in an optimizing compiler, where statements are often moved around. Using the quadruple notation, the symbol table interposes an extra degree of indirection between the computation of a value and its use. If we move a statement computing x, the statements using x require no change. However, in the triples declaration. moving a statement that defines a temporary value requires us to change all references to that statement in the arg 1 and arg2 arrays. This problem makes triples difficult to use in an optimizing compiler.

            Indirect triples present no such problem. A statement can be moved by reordering the statement list. Since pointers to temporary values refer to the r>p-arg 1-arg2 array(s), which are not changed, none of those pointers need be changed. Thus, indirect triples look very much like quadruples as far as their utility is concerned. The two notations require about the same amount of space and they are equally efficient for reordering of code. ~s with ordinary triples. Allocation of storage to those temporaries needing it must be deferred in the code generation phase. However, indirect triples can save some space compared with quadruples if the same temporary value is used more than once. The reason is that two or more entries in the statement array can point to the same line of the op-arg1-arg2 structure.

 

Source:

http://www.mec.ac.in/resources/notes/notes/compiler/module5/intermediate.htm

 

 


Dear Guest,
Spend a minute to Register in a few simple steps, for complete access to the Social Learning Platform with Community Learning Features and Learning Resources.
If you are part of the Learning Community already, Login now!
0
Your rating: None

Posted by



Thu, 05/28/2009 - 14:18

Share

Collaborate