What is Three-Address Code (3AC/TAC)

What’s Three-Address Code

The Three-Address Code (3AC, TAC) is an intermediate representation (IR) usually used in compilers and program analysis. As the name suggests, each instruction of 3AC involves three “addresses” at most, where “address” represents a variable or constant. The common forms include the following¹:

// assignment with binary operator(bop)
x = y bop z

// assignment with binary operator(uop)
x = uop y

// copy
x = y

// unconditional jump
goto label

// conditional jump 1
if x goto L

// conditional jump 2
// rop = relation operator
// e.g. >, <, >=, …
if x rop y goto L

// procedure call
call p

// return
return val

The implementation of 3AC

Based on the characteristics of 3AC, we can use a quadruple to represent each instruction with (destination, operator, operand1, operand2). Then the full IR of code is a quadruple array or a quadruple list².

The advantage of the quadruple list over a quadruple array is that we don’t need to pre-allocate the storage first (a high value will cause a waste of space but a low value will introduce reallocate overhead)².

Practical Example. LLVM IR

Previously we saw the abstract common form of 3AC instructions. When it comes to the implementation, different tools may use different syntaxes. Let’s take LLVM IR (it’s a 3AC!) as an example of a trivial C/C++ program (main.cpp).

int main() {
    int sum = 0;
    for (int i = 0; i < 10; i++) {
        sum += i;
    }
    return 0;
}

The LLVM IR of this small program can be exported with the following command.

$ clang -S -emit-llvm main.cpp

You will find the main.ll file in the same path. I have removed some parts of the code and added comments to help you understand it.

define noundef i32 @main() #0 {
  %1 = alloca i32
  %2 = alloca i32  ; %2 is sum
  %3 = alloca i32  ; %3 is i
  store i32 0, ptr %1
  store i32 0, ptr %2       ; sum = 0
  store i32 0, ptr %3       ; i = 0
  br label %4               ; jump to %4

4:                                                ; preds = %11, %0
  %5 = load i32, ptr %3           ; load i
  %6 = icmp slt i32 %5, 10        ; %6 = check if i < 10
  br i1 %6, label %7, label %14   ; conditional jump based on if %6 is true

7:                                                ; preds = %4
  %8 = load i32, ptr %3     ; i
  %9 = load i32, ptr %2     ; sum
  %10 = add nsw i32 %9, %8  ; temp = sum + i
  store i32 %10, ptr %2     ; sum = temp
  br label %11              ; jump to %11

11:                                               ; preds = %7
  %12 = load i32, ptr %3     ; i
  %13 = add nsw i32 %12, 1   ; temp = i++
  store i32 %13, ptr %3      ; i = temp
  br label %4,               ; jump to %4

14:                                               ; preds = %4
  ret i32 0                  ; return 0
}

Wrap-up

The 3AC is the foundation of many program analysis tools¹. For example, I was reading the ArkAnalyzer³ paper recently and found it uses 3AC as the IR). Compared to the AST, the advantage of 3AC is obvious: it’s more compact and uniform, and it also contains control-flow information. What’s more, it’s language-independent. That explains why it’s a good fit for program analysis. :)

Refs