Intermediate code generation and symbol tables notes — Unit 4

The compiler must generate target code that manages memory during program execution. The RTE manages the layout of data in RAM when the compiled program runs.

⇒1.1 Storage Organization

When a program is loaded into OS memory, the space is divided into several logical areas:

• Code (Text): Stores the compiled machine instructions (Read-only).
• Static/Global: Stores global variables and constants. Size is known at compile-time.
• Heap: Dynamically allocated memory (via `malloc` or `new`). Grows upward.
• Stack: Stores local variables and function call data. Grows downward towards the Heap.

Every time a function is called, a block of memory called an Activation Record is pushed onto the Call Stack. When the function returns, it is popped off.

⇒2.1 Contents of an Activation Record

• Actual Parameters: The arguments passed to the function.
• Return Values: Space reserved for the function to write its result.
• Control Link: A pointer to the activation record of the caller function (used to restore the stack when returning).
• Access Link: A pointer used to access non-local variables in nested functions.
• Saved Machine Status: The Program Counter (PC) and Registers of the caller, so execution can resume exactly where it left off.
• Local Data: Local variables declared inside the function.

How are arguments mapped to parameters during a function call?

⇒3.1 Call by Value

The actual value of the argument is copied into the activation record. Changes made inside the function do NOT affect the original variable (Standard in C/Java primitives).

⇒3.2 Call by Reference

The memory address (pointer) of the argument is passed. Changes made inside the function DO affect the original variable.

⇒3.3 Call by Name

A historical mechanism (Algol 60). The argument is textually substituted into the function body, re-evaluating the expression every time it is used. Often implemented using hidden functions called 'Thunks'.

Instead of translating directly from the Parse Tree to Machine Code, compilers generate an Intermediate Representation (IR).

⇒4.1 Why use an IR?

• Portability: You can write one C Front-End that generates IR, and then write different Back-Ends (x86, ARM) that translate IR to machine code. You don't need a massive monolithic compiler for every language-to-hardware combination.
• Machine-Independent Optimization: Many optimizations (like eliminating dead code) can be done on the IR, reducing the workload for the backend.

The most common form of Intermediate Code. It breaks complex expressions into simple instructions.

⇒5.1 The Rule

Each instruction can have at most one operator on the right side. Complex expressions require the compiler to generate temporary variables.

// Source: x = a + b * c

// Three-Address Code:
t1 = b * c
t2 = a + t1
x = t2

TAC is an abstract concept. Inside the compiler's memory, it is represented as records.

⇒6.1 Quadruples

Records with 4 fields: `(Operator, Argument1, Argument2, Result)`. Every instruction explicitly names a temporary result variable.

⇒6.2 Triples

Records with 3 fields: `(Operator, Argument1, Argument2)`. Instead of naming a temporary variable, instructions refer directly to the index of previous instructions to get their results.

⇒6.3 Indirect Triples

Uses Triples, but maintains a separate array of pointers to the triples. Makes moving instructions around (for optimization) much faster.

High-level structures like `if`, `while`, and `for` do not exist in TAC. They are translated into conditional and unconditional `goto` jumps.

⇒7.1 Example Translation

// Source:
while (A < B) {
    x = y + 1;
}

// TAC Translation:
L1: if A >= B goto L2
    t1 = y + 1
    x = t1
    goto L1
L2: // next code

The compiler uses Backpatching during SDT to figure out what line numbers these `L1` and `L2` labels actually resolve to.