CD Notes
Detailed exploration of register assignment techniques including local and global assignment, usage counts, register pairs, and hardware-specific constraints in compiler code generation.
Introduction
Register assignment is the step that maps virtual registers (or variables) to physical hardware registers. While register allocation decides WHICH variables get registers (vs being spilled), register assignment decides WHICH SPECIFIC register each variable occupies. This distinction matters for architectures with non-uniform register files.
Register Descriptors and Address Descriptors
| Register Descriptor | For each register, tracks what value it currently holds. |
| R0 | {t1}, // R0 holds t1 |
| R1 | {a, t3}, // R1 holds both a and t3 (they have same value) |
| R2 | {empty} // R2 is free |
| Address Descriptor | For each variable, tracks where its value can be found. |
| a | {R1, memory}, // a is in register R1 AND in its memory location |
| t1 | {R0}, // t1 is ONLY in R0 (not yet stored to memory) |
| t3 | {R1}, // t3 is in R1 |
| b | {memory} // b is only in memory |
| - If operand is in register | use it directly (no load needed) |
| - If result register holds a value needed later | spill first |
| - At block end | store all live variables back to memory |
Simple Register Assignment Algorithm
| For each three-address instruction | x = y OP z |
| Step 1 | Call getReg(x = y OP z) to determine registers Rx, Ry, Rz |
| Step 2 | If y is not in Ry: |
| Generate | LD Ry, y_location |
| Step 3 | If z is not in Rz: |
| Generate | LD Rz, z_location |
| Step 4 | Generate: OP Rx, Ry, Rz |
| Step 5 | Update descriptors: |
| - If Ry was holding only y and y has no further use | free Ry |
| Code | a = b + c |
| State initially | all in memory |
| Instruction 1 | a = b + c |
| getReg | Ry=R0, Rz=R1, Rx=R0 (reuse Ry since b dies) |
| Generate | LD R0, b |
| Descriptors | R0={a}, R1={c}, Addr[a]={R0} |
| Instruction 2 | d = a - e |
| getReg | Ry=R0(has a), Rz=R1, Rx=R1 (reuse c's register) |
| Generate | LD R1, e |
| Descriptors | R0={a}, R1={d}, Addr[d]={R1} |
| Instruction 3 | f = d * a |
| d in R1, a in R0 | no loads! |
| getReg | Rx=R1 (d dies after this use) |
| Generate | MUL R1, R1, R0 |
| Descriptors | R0={a}, R1={f} |
| Total | 2 loads avoided by keeping values in registers! |
Usage Count Method
| After line 2 | R0=t1, R1=t2, need register for line 3 |
| next_use of t1 | line 3 (distance 1) - also line 5 (distance 3) |
| next_use of t2 | line 4 (distance 2) |
| t2 used later | spill t2? No, t1 used sooner but also later... |
| Spill t2 (farther away) | keep t1 |
Global Register Assignment
| Strategy | Assign registers across basic blocks based on usage frequency. |
| Step 1 | Count variable usage (weighted by loop depth) |
| Step 2 | Sort variables by usage count |
| Step 3 | Assign registers to most-used variables globally |
| Step 4 | Remaining variables use load/store as needed |
| With 2 registers | assign R0=i (82), R1=temp (60) |
Hardware Constraints
Architecture-specific constraints that affect assignment
1. Register Pairs (MIPS mul, ARM ldrd):
Multiplication result in HI:LO pair
64-bit load needs consecutive even-odd pair
→ Allocator must assign adjacent register numbers
2. Special-purpose registers:
x86: ECX for shift count, EDX:EAX for multiply/divide
→ Certain operations REQUIRE specific registers
→ Insert MOV instructions to satisfy constraints
3. Aliasing (x86):
EAX = [AH:AL], AX = [AH:AL]
Using AL implicitly modifies EAX
→ Must track sub-register dependencies
4. Calling conventions:
Caller-saved: R0-R3 (ARM), RAX,RCX,RDX,R8-R11 (x64)
Callee-saved: R4-R11 (ARM), RBX,RBP,R12-R15 (x64)
→ Prefer caller-saved for temporaries within a function
Example - x86 division constraint
IR: q = a / b; r = a % b
Must use: EDX:EAX for dividend, result in EAX(quotient), EDX(remainder)
Generated code
MOV EAX, a ; load dividend into EAX
CDQ ; sign-extend into EDX:EAX
IDIV [b] ; divide, q in EAX, r in EDX
MOV [q], EAX
MOV [r], EDX
Register Assignment in SSA Form
| In SSA form, each variable defined once | simpler live ranges |
| Original | SSA form: |
| x₃ = φ(x₁, x₂) | try to assign same register to x₁, x₂, x₃ |
| Before | x₃ = φ(x₁, x₂) |
| After | // at end of block 1: MOV x₃, x₁ |
| // at end of block 2 | MOV x₃, x₂ |
| If x₁, x₂, x₃ get same register | MOVs eliminated! |
Spill Code Optimization
| // Just recompute | MOV R0, 16 |
| Before optimization | After optimization: |
| loop | LD R0, [x_spill] // hoist |
Interview Questions
- Q: What is the difference between register allocation and register assignment?
A: Allocation decides which variables reside in registers vs memory (how many registers needed, who gets spilled). Assignment maps allocated variables to specific physical registers (R0, R1, etc.). Some frameworks combine them; others separate them. The distinction matters when hardware has non-uniform registers.
- Q: Why might a compiler insert a MOV instruction between two registers?
A: Several reasons: (1) Satisfy a hardware constraint (division needs EDX:EAX), (2) Function call convention (argument must be in specific register), (3) Phi elimination in SSA (values from different paths must merge into one register), (4) Register coalescing failure (couldn't assign same register to source and destination).
- Q: How does the compiler handle register-register moves efficiently?
A: Register coalescing attempts to assign the same register to both source and destination of MOV, eliminating it entirely. If that increases interference too much (conservative coalescing), the MOV remains but is very cheap (1 cycle). Copy propagation in later passes may also eliminate some.
- Q: What is rematerialization and when is it profitable?
A: Rematerialization recomputes a spilled value instead of loading it from memory. It is profitable when the computation is cheaper than a memory load — constants (MOV R, #5), address computations (LEA R, [base+offset]), or simple expressions from values already in registers. It avoids the store entirely.
- Q: How do modern out-of-order CPUs affect register assignment strategy?
A: Out-of-order CPUs use register renaming internally, which eliminates false dependencies between reuses of the same architectural register. This means the compiler's assignment choices matter less for execution speed but still affect code size (some assignments enable shorter instruction encodings).
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Register Assignment Strategies in Code Generation.
Interview Use
Prepare one clear explanation, one practical example, and one common mistake for this Compiler Design topic.
Search Terms
compiler-design, compiler design, compiler, design, code, generation, register, assignment
Related Compiler Design Topics