Chapter 8: Code Generation

What is Code Generation?

In a compiler, the code generator is the final step. It takes the intermediate
representation (a simplified version of your program) and turns it into actual machine
instructions that the computer can understand and execute.

Think of it like this:

Step What happens

Source code (e.g., C++ or Java) → Front end (lexical, syntax, semantic analysis)

Intermediate representation (IR) → Simplified code (e.g., x = y + z)

Code generator → Translates IR into machine instructions

Target machine code → Executable program

Part 1: Issues in Designing a Code Generator

When building a code generator, we face three main challenges:

Challenge What it means

Instruction Choosing the right machine instruction for each operation (e.g., should we
selection use ADD or INC? )

Register Deciding which values to keep in registers (fast, small memory inside the CPU)
allocation instead of slow main memory.

Instruction Arranging instructions in the best order for speed (e.g., avoid unnecessary
ordering loads/stores).
 Most important rule: Correctness

 The generated code must work correctly for all inputs.

 It's better to produce slow correct code than fast wrong code.
 Therefore, the code generator should be easy to test and fix.

Part 2: Input to the Code Generator

The code generator receives two things:

1. Intermediate representation (IR) – a simplified version of your program (e.g., three-

address code like x = y + z).
2. Symbol table information – tells the generator where each variable is stored in
memory (addresses).

Types of Intermediate Representations

Type Description

Three-address code Each line has at most three operands: a = b + c (most common)

Virtual machine code e.g., Java bytecode (used by the Java Virtual Machine)

Postfix notation e.g., a b c + = (operators after operands)

Syntax trees / DAGs Graphical representations (like a tree structure)

Assumption about the front end

 The front end (earlier compiler phases) has already:

o Scanned, parsed, and translated the source into a low-level IR.
o Performed type checking and inserted type conversion operators (e.g., integer to float).
o Detected all syntactic and static semantic errors.
 Therefore, the code generator does not need to handle errors – it can assume the input
is correct.
 Part 3: The Target Program – What is a Target Machine?
The target machine is the computer hardware that will run your program. Different
machines are designed differently.

Three Common Machine Types

1. RISC (Reduced Instruction Set Computer)

 Many registers (fast storage inside CPU).

 Simple instructions (each instruction does one small thing).
 Example: ARM processors, MIPS.

2. CISC (Complex Instruction Set Computer)

 Few registers.
 Complex instructions (one instruction can do many things).
 Example: Intel x86 (the processor in most PCs).

3. Stack-based machine

 Operations are done by pushing values onto a stack (like a pile of plates) and then
popping them.
 Example: Java Virtual Machine (JVM), which interprets Java bytecode.

Note: Stack machines almost disappeared, but they came back with Java because they
are easy to implement across different computers.

Two Ways to Produce Output

Output type Pros Cons

Absolute machine Cannot split program into

Ready to run immediately
code separate files

Relocatable Allows separate compilation (you can Needs linking and loading
object code compile each function separately) before execution
 We will use a simple RISC-like machine with a few extra features. We will write
instructions in assembly language (text version of machine code).

Part 4: Basic Machine Instructions

We start by learning what each instruction does, using everyday language.

Load and Store Instructions

 LD = Load – copy a value from memory (RAM) into a register (fast CPU storage).
 ST = Store – copy a value from a register back into memory.

Think of registers as small handy boxes inside the CPU. Memory (RAM) is like a big
warehouse. It's faster to work with boxes than to go to the warehouse every time.

Example:

 LD R0, x – Take the value from memory location x and put it into register R0.
 ST x, R0 – Take the value from register R0 and put it into memory location x.

Computation Instructions

 ADD dst, src1, src2 – Add src1 and src2, put the result in dst.
 SUB dst, src1, src2 – Subtract src2 from src1, put the result in dst.
 MUL dst, src1, src2 – Multiply src1 and src2, put the result in dst.

Example: ADD R1, R2, R3 means R1 = R2 + R3.

Jump (Branch) Instructions

Jumps change the order of execution (like goto in programming languages).

 BR L – Unconditional jump – go to label L without any condition.

 Bcond r, L – Conditional jump – check register r and jump to L if condition is true.

Example: BLTZ r, L – Jump to L if the value in register r is less than zero (BLTZ =
Branch Less Than Zero).
 Part 5: Addressing Modes – Different Ways to Specify a
Location
An instruction needs to know where a value is. There are several ways to say "where".

1. Direct (variable name)

 LD R1, x – Load the value from memory location named x.

 x is like a variable in your program.

2. Indexed (array access)

 LD R1, a(R2) – Load from memory location a + (value in R2).

 Useful for arrays: if R2 holds the index (multiplied by element size), you can access an
array element.

3. Indirect (pointer)

 LD R1, *R2 – First, look at the value in R2. Treat that value as an address. Then go to that
address and load the value from there.
 This is like pointer dereferencing in C (*p).

4. Indirect with offset

 LD R1, *100(R2) – First, add 100 to the value in R2. Then treat that as an address, and
load the value from there.

5. Immediate constant

 LD R1, #100– Load the number 100 directly into R1, not from memory.
 # means "immediate value" (constant).

Part 6: Examples – Seeing How Instructions Work

 Example 1: Simple assignment
Three-address code: x = y + z

Machine code (step by step):

1. LD R0, y → Copy y into register R0.

2. ADD R0, R0, z → Add z to R0 (now R0 holds y+z).
3. ST x, R0 → Store the result into memory for x.

Example 2: Using a register that already has a value (avoiding

redundancy)
Suppose we have two statements:
text
a = b + c
d = a + e

Naive translation (with redundant loads/stores):

Instruction Meaning

LD R0, b R0 = b

ADD R0, R0, c R0 = b + c

ST a, R0 a = R0

LD R0, a Redundant! - we just stored a into memory, now we load it back.

ADD R0, R0, e R0 = a + e

ST d, R0 d = R0

Better way: Keep a in the register and don't reload it.

Example 3: Using a special instruction

 Three-address code: a = a + 1

Instead of three instructions (load, add, store), use:

 INC a – Increment a directly in memory (if the machine has this instruction).

This is faster and simpler.

Part 7: How to Handle Arrays and Pointers (Step by Step)

Array access
Imagine an array a where each element is 8 bytes (e.g., 8-byte real numbers). Indexing
starts at 0.

Operation: b = a[i]

We must compute the byte offset: i × 8.

Machine code:

1. LD R1, i → R1 = i (the index)

2. MUL R1, R1, 8 → R1 = i × 8 (byte offset)
3. LD R2, a(R1) → R2 = value at address a + R1 (i.e., a[i])
4. ST b, R2 → b = a[i]

Operation: a[j] = c

Machine code:

1. LD R1, c → R1 = c (the value)

2. LD R2, j → R2 = j (the index)
3. MUL R2, R2, 8 → R2 = j × 8 (byte offset)
4. ST a(R2), R1 → store R1 into address a + R2 (i.e., a[j] = c)

Pointer indirection
Operation: x = *p (x takes the value that p points to)

Machine code:
1. LD R1, p → R1 = p (the address stored in p)
2. LD R2, 0(R1) → R2 = value at the address in R1 (i.e., *p)
3. ST x, R2 → x = *p

Operation: *p = y (store y into the location p points to)

Machine code:

1. LD R1, p → R1 = p (address)
2. LD R2, y → R2 = y (the value)
3. ST 0(R1), R2 → store R2 into the address in R1 (i.e., *p = y)

Conditional if-statement
Three-address code: if x < y goto L

Machine code:

1. LD R1, x
2. LD R2, y
3. SUB R1, R1, R2 → R1 = x - y
4. BLTZ R1, L → If R1 < 0 (i.e., x < y), jump to label L.

BLTZ = Branch if Less Than Zero.

Part 8: How Memory is Organized (Storage Management)

When a program runs, the computer's memory is divided into four areas:

Area What it holds Fixed or flexible?

Code The machine instructions (your program) Fixed size

Static
Global variables, constants Fixed size (known at compile time)
data

Objects allocated during execution (e.g., new in

Heap Grows and shrinks dynamically
C++, malloc)
 Area What it holds Fixed or flexible?

Grows and shrinks as functions are

Stack Local variables and call information for functions
called/returned

Three ways to allocate memory

1. Static allocation

 The compiler decides exact addresses for variables before the program runs.
 Used for: global variables, constants, FORTRAN variables.

2. Stack-based allocation

 When a function is called, memory is pushed onto a stack; when it returns, memory is
popped.
 Works like a stack of plates – last in, first out (LIFO).
 Used for: local variables in functions, procedure call information (return address, etc.).
 Supports recursion.

3. Heap-based allocation

 You can allocate and free memory at any time.

 Most flexible, but also most expensive (slower).
 Used for: dynamic data structures (linked lists, trees, objects in Java).

Part 9: Procedure Calls and Returns (Simplest Case – Static

Allocation)
We'll use static allocation (simplest) to explain how a function is called and returns.

Key concepts

 Each function has an activation record – a small area of memory that stores its local
variables and return address.
 The return address is the location in the program where execution should continue
after the function finishes.

What happens during a function call?

1. Save the return address (where the caller should resume after the function returns).
2. Jump to the called function.
3. When the function finishes, jump back to the saved return address.

Instructions used

 ST location, #value – Store #value into location.

 BR address – Jump to address.
 BR *location – Jump to the address stored in location (indirect jump).

Example step-by-step
Suppose we have this three-address code:
text
// code for main function c
action1
call p
action2
halt

// code for function p

action3
return

Our target machine instructions (with addresses):

Address Instruction Explanation

100 ACTION1 (some code for action1)

120 ST 364, #140 Save return address 140 into memory location 364
 Address Instruction Explanation

132 BR 200 Jump to address 200 (start of function p)

140 ACTION2 (code for action2 – after p returns)

160 HALT End of main

200 ACTION3 (code for action3 inside p)

220 BR *364 Jump to the address stored at 364 (which is 140)

300-363 (activation record for c) Unused in this example

364-451 (activation record for p) Location 364 holds the return address

What happens during execution:

1. Execute ACTION1 (at address 100).

2. At address 120: Save the number 140 (which is the address of the next instruction after
the call) into memory location 364.
3. At address 132: Jump to address 200 – start executing function p.
4. At address 200: Execute ACTION3.
5. At address 220: Jump to *364 – this means "jump to the address stored in location 364",
which is 140.
6. At address 140: Execute ACTION2.
7. At address 160: HALT (program ends).

Why #here + 20?

 #here means "the address of the current instruction".

 The two instructions (ST and BR) plus some constants take up 20 bytes (5 words × 4
bytes each).
 So #here + 20 is the address of the instruction after the BR – that's the return address.

Return instruction in callee:

 BR *364 – Load the address stored at location 364 and jump there.

Important notes:

 The return address is saved before the jump.

 The jump instruction uses indirect addressing (*364) to return.
 The activation records are statically allocated here (for simplicity).
 In real compilers, activation records are often on the stack for recursion.

Part 10: Summary – What You Need to Remember

1. Code generation turns intermediate code into machine instructions.
2. Correctness is more important than speed.
3. Target machines can be:
o RISC (many registers, simple instructions)
o CISC (few registers, complex instructions)
o Stack-based (Java Virtual Machine)
4. Output types:
o Absolute machine code (ready to run)
o Relocatable object code (needs linking)
5. Instructions we used:
o (load), ST (store)
LD
o ADD, SUB, MUL
o BR (unconditional jump), Bcond (conditional)
o INC (increment)
6. Addressing modes tell the CPU where to find data:
o Direct (variable name)
o Indexed (array access)
o Indirect (pointer)
o Indirect with offset
o Immediate (constant)
7. Memory organization: Code, Static data, Heap, Stack.
8. Storage allocation: Static, Stack, Heap.
9. Procedure calls:
o Save return address
o Jump to callee
o Return using indirect jump
Practice Questions (with simple answers)
Q1: What does LD R0, x do?
Answer: It loads the value from memory location x into register R0.

Q2: How do you implement a = b * c using machine instructions?

Answer:
text
LD R0, b
MUL R0, R0, c
ST a, R0

Q3: Why is the instruction INC a better than LD R0, a; ADD R0, R0, #1; ST a, R0 ?
Answer: It does the same job in one instruction instead of three, so it's faster and uses
less memory.

Q4: What is the difference between stack-based and heap-based allocation?

Answer: Stack allocation works like a pile of plates – last allocated, first freed. It is used
for local variables in functions. Heap allocation allows you to allocate and free at any
time, but is slower and more complex.

Q5: In the procedure call example, where is the return address stored?
Answer: In the first location of the called function's activation record (address 364 in the
example).

Q6: Why is the LD R0, a instruction redundant in the example a = b + c; d = a + e?

Answer: Because we already have a in register R0 after the store. Loading it again is
unnecessary.

Q7: Translate if p == 0 goto L into machine code. (Hint: compare with zero using
conditional branch.)
Answer:

LD R1, p
BLTZ R1, L // p < 0? Actually we need p == 0.
// A better way (if we have BEQZ):
BEQZ R1, L // Branch if R1 == 0

(Note: Our simple machine doesn't have BEQZ, but you can use SUB with zero and
check BLTZ/BGTZ creatively. For this course, just know the idea.)
 Q8: Explain the difference between static, stack, and heap allocation in one sentence
each.
Answer:

 Static: Memory allocated at compile time, fixed addresses.

 Stack: Memory allocated and freed in LIFO order when functions are called/returned.
 Heap: Memory allocated and freed at arbitrary times during program execution.