Three address code

From Wikipedia, the free encyclopedia

In computer science, three-address code (often abbreviated to TAC or 3AC) is a form of representing intermediate code used by compilers to aid in the implementation of code-improving transformations. Each instruction in three-address code can be described as a 4-tuple: (operator, operand1, operand2, result).

Each statement has the general form of:

$x := y \, \operatorname{op} \, z\,$

where x, y and z are variables, constants or temporary variables generated by the compiler. op represents any operator, e.g. an arithmetic operator.

Expressions containing more than one fundamental operation, such as:

$p := x + y \times z\,$

are not representable in three-address code as a single instruction. Instead, they are decomposed into an equivalent series of instructions, such as

$t_1 := y \times z\,$

$p := x + t_1\,$

The term three-address code is still used even if some instructions use more or fewer than two operands. The key features of three-address code are that every instruction implements exactly one fundamental operation, and that the source and destination may refer to any available register.

A refinement of three-address code is static single assignment form (SSA).

[edit] Example

int main(void)
{
    int i;
    int b[10];
    for (i = 0; i < 10; ++i) {
        b[i] = i*i; 
    }
}

The preceding C program, translated into three-address code, might look something like the following:

      i := 0                  ; assignment
L1:   if i < 10 goto L2       ; conditional jump
      goto L3                 ; unconditional jump
L2:   t0 := i*i
      t1 := &b                ; address-of operation
      t2 := t1 + i            ; t2 holds the address of b[i]
      *t2 := t0               ; store through pointer
      i := i + 1
      goto L1
L3: