CSS Prepare

optional · CSS study notes

Code Generation

Definition

Code generation is the final compiler phase, translating optimized intermediate code into the actual target machine code (or assembly).

Key Points

  • Issues in design of a code generator:
    • Input form (must handle whichever IR the earlier phases produce)
    • Target program form (assembly vs relocatable machine code vs absolute machine code)
    • Instruction selection (choosing efficient instruction sequences for IR operations)
    • Register allocation and assignment
    • Choice of evaluation order (affects efficiency)
  • The Target Machine: code generator must understand the machine's instruction set, addressing modes, and register set to produce efficient, correct code.
  • Run-Time Storage Management: organizes memory into regions — code, static data, stack (for function calls/activation records), and heap (for dynamic allocation) — code generator must emit correct addressing for each region.
  • Register Allocation: deciding which values are kept in the limited set of hardware registers at each point, to minimize slow memory accesses.
    • Register allocation: deciding which variables go into registers
    • Register assignment: deciding which specific register a variable uses
    • Common techniques: graph coloring, linear scan.

Example

For t1 = b * c; t2 = a + t1, a simple code generator might produce:

MOV R1, b
MUL R1, c        ; R1 = b*c (t1)
MOV R2, a
ADD R2, R1        ; R2 = a+t1 (t2)

📌 CSS Frequency: Moderate-high — often a conceptual question on "issues in code generator design" or a short trace from TAC to assembly-like code.

Model Answer (short)

"Code generation converts optimized intermediate code into target machine code, and its design must address instruction selection, register allocation/assignment, evaluation order, and the target machine's instruction set and addressing modes. Run-time storage management organizes memory into code, static, stack, and heap regions, which the code generator must reference correctly; register allocation, often via graph coloring, aims to keep frequently used values in fast registers rather than slower memory."

📜 Past-Paper Questions & MCQs (CSS 2016–2026)

2019 · Paper-I · Q8(a) · 10 marks

Q. Write down the major steps involved in code generation.

Ans. The code generator turns the optimised intermediate representation (IR) into target machine code.

  • 1. Input analysis: read the IR (three-address code or syntax tree) together with the symbol table.
  • 2. Instruction selection: choose target instructions that implement each IR operation, using addressing modes and special instructions well.
  • 3. Register allocation and assignment: decide which values stay in registers (the fast storage) and which go to memory, and spill values when registers run out.
  • 4. Instruction ordering (scheduling): arrange instructions to avoid pipeline stalls and use delay slots.
  • 5. Memory and address management: map variables to addresses or stack offsets, and handle procedure calls, parameters and activation records.
  • 6. Peephole optimisation: clean up the generated code.
  • 7. Output: emit assembly or machine code, which is then assembled, linked and loaded.

2026 · Paper-I · Q7(c) · 8 marks

Q. For the three-address code t1 = a + b, t2 = t1 + c, t3 = t2 + d, with only two registers, how should the compiler allocate registers to minimise memory spills?

Ans.

  • Observation: each temporary is used exactly once, by the very next instruction, and then it is dead. At any moment at most two values are live (the running result and one new operand), so two registers are enough with no spills.
  • Allocation: keep the running result in R1 (acting as an accumulator) and load each new operand into R2.
LD  R1, a
LD  R2, b
ADD R1, R1, R2        ; R1 = t1
LD  R2, c             ; R2 is free again (b is dead)
ADD R1, R1, R2        ; R1 = t2   (t1 is dead)
LD  R2, d
ADD R1, R1, R2        ; R1 = t3
ST  t3, R1            ; only if t3 is needed in memory
  • Technique: use liveness (next-use) information. Reuse a register as soon as its value is dead, and prefer to spill the value whose next use is farthest away. Graph colouring with 2 colours models it, and the interference graph here can be coloured with 2 colours.

2025 · Paper-I · Q8(b) · 6 marks

Q. What is instruction scheduling? Explain its role during the code generation process.

Ans.

  • Instruction scheduling reorders the generated machine instructions, without changing the program's result, to reduce pipeline stalls and make the best use of the processor.
  • Role in code generation:
    • hides latency: independent instructions are placed between a load and its use
    • reduces data and control hazards in pipelined and superscalar CPUs
    • fills branch delay slots and uses parallel functional units
  • Constraint: the order must respect data dependences (read-after-write, write-after-read, write-after-write).
  • Example: LD R1, a; ADD R2, R1, R3; LD R4, b becomes LD R1, a; LD R4, b; ADD R2, R1, R3, which hides the load delay.
  • Interaction: it is done together with register allocation, since scheduling can increase register pressure.

MCQs

2025 P-I · Q14. Which optimisation method involves minimising the memory access count in a program?

  • (A) Constant folding
  • (B) Register allocation ✅
  • (C) Instruction scheduling
  • (D) None of these
  • Answer: (B) Register allocation.
  • Why: keeping frequently used values in CPU registers avoids slow memory loads and stores. Constant folding computes constants at compile time, and instruction scheduling reorders instructions to avoid pipeline stalls.