Three-address code in Compiler Design - Deep Dive

Overview - Three-address code

What is it?

Three-address code is a simple, intermediate form of representing computer programs during compilation. It breaks down complex instructions into smaller steps, each with at most three parts: two operands and one result. This form makes it easier for the compiler to analyze and optimize the program before generating machine code. It acts as a bridge between high-level language and machine instructions.

Why it matters

Without three-address code, compilers would struggle to optimize and translate complex high-level instructions efficiently. It simplifies the program into manageable pieces, enabling better error checking, optimization, and easier translation to machine code. This improves the speed and quality of the final program, which affects everything from app performance to system reliability.

Where it fits

Before learning three-address code, you should understand basic programming concepts and how compilers translate code. After mastering it, you can study compiler optimization techniques and code generation, which build on this intermediate representation.

Mental Model

Core Idea

Three-address code breaks complex instructions into simple steps with at most two inputs and one output, making program translation and optimization easier.

Think of it like...

It's like breaking a complicated recipe into simple steps where each step uses only two ingredients to make one dish, so the cook can follow and improve the process easily.

┌───────────────┐
│ Three-Address │
│     Code      │
└──────┬────────┘
       │
       ▼
┌─────────────────────────────┐
│  result = operand1 op operand2│
│  (at most two inputs, one output) │
└─────────────────────────────┘

Build-Up - 7 Steps

1

Foundation

Understanding Intermediate Code

Concept: Introduce the idea of intermediate code as a step between source code and machine code.

When a program is compiled, it is first translated into an intermediate form before becoming machine code. This intermediate code is easier to analyze and optimize than the original source code or raw machine instructions.

Result

Learners understand that intermediate code simplifies the compilation process.

Knowing that compilers use an intermediate step helps explain why programs can be optimized and translated efficiently.

2

Foundation

Basic Structure of Three-Address Code

Concept: Explain the format of three-address code instructions with two operands and one result.

Each instruction in three-address code looks like: result = operand1 operator operand2. For example, t1 = a + b means add a and b, store in t1. This simple format breaks down complex expressions into small steps.

Result

Learners can identify and write simple three-address code instructions.

Understanding this format is key to seeing how complex operations are simplified.

3

Intermediate

Handling Complex Expressions Step-by-Step

🤔Before reading on: do you think a complex expression like (a + b) * (c - d) can be done in one step or multiple three-address code steps? Commit to your answer.

Concept: Show how complex expressions are broken into multiple three-address code instructions.

For (a + b) * (c - d), first compute t1 = a + b, then t2 = c - d, finally t3 = t1 * t2. Each step uses the three-address format, making the process clear and manageable.

Result

Learners see how to translate complex expressions into sequences of simple instructions.

Breaking down expressions step-by-step reveals how three-address code simplifies program analysis.

4

Intermediate

Representing Control Flow with Three-Address Code

🤔Before reading on: do you think three-address code can represent decisions like if-else or loops directly? Yes or no? Commit to your answer.

Concept: Introduce how control flow statements are represented using labels and conditional/unconditional jumps.

Three-address code uses labels like L1, L2 and jump instructions like if x < y goto L1 or goto L2 to represent decisions and loops. This allows the compiler to handle program flow clearly.

Result

Learners understand how control structures are translated into intermediate code.

Knowing how control flow is represented helps in understanding program execution and optimization.

5

Intermediate

Temporary Variables and Their Role

Concept: Explain the use of temporary variables to hold intermediate results.

Temporary variables like t1, t2 store results of intermediate calculations. They help keep the code simple and track values step-by-step without changing original variables.

Result

Learners grasp why temporary variables are essential in three-address code.

Recognizing the role of temporaries clarifies how compilers manage complex computations.

6

Advanced

Optimizing Three-Address Code

🤔Before reading on: do you think all three-address code instructions are necessary, or can some be removed or combined? Commit to your answer.

Concept: Introduce basic optimization techniques like eliminating redundant code and combining instructions.

Compilers analyze three-address code to remove unnecessary instructions, reuse temporary variables, and simplify expressions. For example, if a temporary variable is never used, its calculation can be skipped.

Result

Learners see how three-address code enables program optimization.

Understanding optimization at this level shows why intermediate code is crucial for efficient programs.

7

Expert

Three-Address Code in Modern Compiler Design

🤔Before reading on: do you think modern compilers still use simple three-address code, or have they moved to more complex representations? Commit to your answer.

Concept: Discuss the role of three-address code as a foundation for more advanced intermediate representations in modern compilers.

While modern compilers often use more complex forms like SSA (Static Single Assignment), three-address code remains a fundamental concept. It helps in understanding how instructions are broken down and optimized before final code generation.

Result

Learners appreciate the lasting importance of three-address code in compiler theory and practice.

Knowing the evolution from three-address code to advanced forms deepens understanding of compiler internals.

Under the Hood

Three-address code works by representing each operation as a simple instruction with at most two operands and one result. The compiler generates these instructions sequentially, using temporary variables to hold intermediate results. Control flow is managed by labels and jump instructions. This structure allows the compiler to analyze dependencies, optimize code, and translate instructions into machine code efficiently.

Why designed this way?

Three-address code was designed to simplify the complex expressions and control structures of high-level languages into uniform, easy-to-manage instructions. Earlier compiler designs struggled with direct translation to machine code due to complexity. This intermediate form balances simplicity and expressiveness, enabling better optimization and easier code generation.

┌───────────────┐
│ Source Code   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Three-Address │
│    Code       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Optimized     │
│ Three-Address │
│    Code       │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│ Machine Code  │
└───────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Do you think three-address code instructions always have exactly three addresses? Commit to yes or no.

Common Belief: Three-address code instructions always have exactly three addresses or operands.

Reality: Three-address code instructions have at most three addresses: two operands and one result. Some instructions, like jumps, may have fewer operands.

Why it matters: Believing all instructions have exactly three addresses can confuse learners about how control flow and simpler instructions are represented.

Quick: Do you think three-address code is the final machine code? Commit to yes or no.

Common Belief: Three-address code is the actual machine code executed by the computer.

Reality: Three-address code is an intermediate representation, not machine code. It must be further translated into machine instructions.

Why it matters: Confusing intermediate code with machine code can lead to misunderstanding the compilation process and the role of optimization.

Quick: Do you think three-address code can represent all programming language features directly? Commit to yes or no.

Common Belief: Three-address code can directly represent all high-level language features without any transformation.

Reality: Some high-level features require transformation or multiple instructions in three-address code to represent them accurately.

Why it matters: Assuming direct representation can cause confusion when complex features like function calls or objects are compiled.

Quick: Do you think modern compilers no longer use three-address code? Commit to yes or no.

Common Belief: Modern compilers have completely replaced three-address code with newer representations.

Reality: While modern compilers use advanced forms like SSA, three-address code concepts still underpin these representations and remain foundational.

Why it matters: Ignoring the relevance of three-address code can hinder understanding of modern compiler design and optimization.

Expert Zone

1

Three-address code instructions can be extended with additional fields like type information or debugging metadata without changing the core format.

2

The choice of temporary variable naming and reuse strategies can significantly impact optimization effectiveness and register allocation.

3

Control flow representation using labels and jumps in three-address code is a precursor to more advanced control flow graphs used in modern compilers.

When NOT to use

Three-address code is less suitable when very low-level machine-specific optimizations are needed or when compiling for architectures with complex instruction sets. In such cases, direct machine code generation or more detailed intermediate forms like SSA are preferred.

Production Patterns

In real-world compilers, three-address code is often generated early in the compilation pipeline, then transformed into SSA form for optimization. It is also used in educational compilers and tools for debugging and teaching compiler concepts.

Connections

Static Single Assignment (SSA) Form

Builds-on

Understanding three-address code helps grasp SSA form, which refines it by ensuring each variable is assigned exactly once, enabling powerful optimizations.

Assembly Language

Precedes

Three-address code serves as a bridge to assembly language, simplifying complex high-level instructions into manageable steps before final machine code translation.

Recipe Instructions in Cooking

Analogous process

Breaking down complex recipes into simple steps with limited ingredients mirrors how three-address code breaks complex operations into simple instructions, showing a universal approach to managing complexity.

Common Pitfalls

#1 Trying to write three-address code with complex expressions in one instruction.

Wrong approach:

t1 = a + b * c - d

Correct approach:

t2 = b * c
t1 = a + t2
t3 = t1 - d

Root cause:

Misunderstanding that three-address code requires breaking expressions into simple steps with at most two operands.

#2 Ignoring the need for labels and jumps to represent control flow.

Wrong approach:

if a < b then c = d + e

Correct approach:

if a < b goto L1
goto L2
L1: c = d + e
L2:

Root cause:

Assuming three-address code can represent control flow like high-level languages without explicit jumps and labels.

#3 Reusing temporary variables without care, causing incorrect results.

Wrong approach:

t1 = a + b
t1 = c - d
use t1 for both results

Correct approach:

t1 = a + b
t2 = c - d
use t1 and t2 separately

Root cause:

Not understanding that each temporary variable should hold one unique intermediate result.

Key Takeaways

Three-address code simplifies complex program instructions into small steps with at most two inputs and one output.

It acts as an intermediate language that helps compilers analyze, optimize, and translate programs efficiently.

Temporary variables and explicit control flow with labels and jumps are key features of three-address code.

Understanding three-address code is essential for grasping modern compiler design and optimization techniques.

While more advanced intermediate forms exist, three-address code remains a foundational concept in compiling.

Practice

1. What is the main purpose of three-address code in compiler design?

easy

A. To execute machine code directly on hardware

B. To break complex instructions into simpler steps with at most three parts

C. To store source code in a compressed format

D. To replace high-level language syntax with natural language

Solution

1. Step 1: Understand the role of intermediate code

   Intermediate code like three-address code simplifies complex instructions for easier processing.

2. Step 2: Identify the key feature of three-address code

   It breaks instructions into steps with at most three parts (two operands and one result).

3. Final Answer:

   To break complex instructions into simpler steps with at most three parts -> Option B

4. Quick Check:

   Three-address code = simple 3-part instructions [OK]

Hint: Three-address code simplifies instructions into three parts [OK]

Common Mistakes:

• Confusing three-address code with machine code
• Thinking it compresses source code
• Believing it replaces programming languages

2. Which of the following is a correct example of a three-address code instruction?

easy

A. if a > b goto L1 else goto L2

B. while (a < b) { a = a + 1; }

C. print(a, b, c)

D. t1 = a + b

Solution

1. Step 1: Identify the format of three-address code

   It typically has one operator and up to two operands, assigning result to a temporary variable.

2. Step 2: Check each option

   t1 = a + b matches the format: one operator (+), two operands (a, b), and a result (t1). Others are control flow or high-level statements.

3. Final Answer:

   t1 = a + b -> Option D

4. Quick Check:

   Three-address code = one operator, two operands, one result [OK]

Hint: Look for one operator and two operands with a result variable [OK]

Common Mistakes:

• Choosing control flow statements as three-address code
• Confusing function calls with three-address code
• Ignoring the assignment to a temporary variable

3. Given the three-address code:
t1 = a + b
t2 = t1 * c
d = t2 - e
What is the final value assigned to d in terms of a, b, c, e?

medium

A. (a + b) * c - e

B. a + b * c - e

C. a + (b * c) - e

D. (a + b) - (c * e)

Solution

1. Step 1: Evaluate intermediate expressions step-by-step

   t1 = a + b; then t2 = t1 * c = (a + b) * c; finally d = t2 - e = (a + b) * c - e.

2. Step 2: Substitute and simplify

   The final expression for d is (a + b) * c - e, matching (a + b) * c - e.

3. Final Answer:

   (a + b) * c - e -> Option A

4. Quick Check:

   Follow code stepwise = (a + b) * c - e [OK]

Hint: Follow temporary variables stepwise to build final expression [OK]

Common Mistakes:

• Ignoring parentheses changing operation order
• Multiplying b by c before adding a
• Mixing subtraction order

4. Identify the error in this three-address code snippet:
t1 = a + b
t2 = t1 *
d = t2 - e

medium

A. Missing operand after '*' operator in second line

B. Incorrect use of temporary variables

C. Assignment to 'd' should be before 't2'

D. No error, code is correct

Solution

1. Step 1: Examine the second line syntax

   The second line ends with '*' operator but lacks the second operand after '*', which is invalid.

2. Step 2: Confirm other lines are correct

   First and third lines have proper assignments and operands; only second line has syntax error.

3. Final Answer:

   Missing operand after '*' operator in second line -> Option A

4. Quick Check:

   Operator must have two operands [OK]

Hint: Check each operator has two operands in three-address code [OK]

Common Mistakes:

• Ignoring incomplete operator usage
• Thinking variable order causes error
• Assuming code is correct without checking syntax

5. How would you represent the high-level statement if (a < b) c = a + b; else c = a - b; in three-address code?

hard

A. if a < b then c = a + b else c = a - b

B. c = a + b if a < b else c = a - b

C. if a < b goto L1c = a - bgoto L2L1: c = a + bL2:

D. t1 = a < bc = t1 ? a + b : a - b

Solution

1. Step 1: Translate conditional jump

   Use 'if a < b goto L1' to jump to true branch, else execute false branch.

2. Step 2: Write false branch, jump over true branch

   False branch: c = a - b; then jump to L2 to skip true branch.

3. Step 3: Write true branch and label

   Label L1: c = a + b; Label L2 marks end of conditional.

4. Final Answer:

   if a < b goto L1
   c = a - b
   goto L2
   L1: c = a + b
   L2: -> Option C

5. Quick Check:

   Use labels and jumps for if-else in three-address code [OK]

Hint: Use labels and jumps to represent if-else in three-address code [OK]

Common Mistakes:

• Writing high-level if-else syntax directly
• Using ternary operator not valid in three-address code
• Missing jump to skip true branch after false branch