CD Notes
Guide to machine code generation covering binary encoding, instruction formats, addressing mode encoding, relocation, and the final translation from assembly to executable machine code.
Overview
Machine code generation is the process of translating assembly-level instructions into binary machine code that the processor can directly execute. This is the very last step in the compilation pipeline, producing the actual bytes that the CPU fetches and decodes.
Instruction Encoding
| Prefix | Opcode | ModRM | SIB | Displace. | Immediate |
|---|---|---|---|---|---|
| 0-4 B | 1-3 B | 0-1B | 0-1B | 0,1,2,4 | 0,1,2,4 B |
| Cond | OpType | Op | Rn | Rd | Operand2 |
| 4 bits | 3 bits | 4 b | 4 b | 4 b | 12 bits |
Encoding Process
| Opcode | 8B (MOV r32, r/m32) |
| ModRM | 00 000 100 (Mod=00, Reg=EAX=000, R/M=100=SIB) |
| SIB | 10 001 011 (Scale=4=10, Index=ECX=001, Base=EBX=011) |
| Opcode | 83 (ADD r/m32, imm8) |
| ModRM | 11 000 000 (Mod=11=reg, Op=000=ADD, R/M=EAX=000) |
| Imm8 | 01 |
| Opcode | 89 (MOV r/m32, r32) |
| ModRM | 00 000 010 (Mod=00, Reg=EAX=000, R/M=EDX=010) |
| Opcode | 49 (DEC ECX, short form) |
| Opcode | 75 (JNZ rel8) |
| Offset | calculate backwards to loop |
| Final machine code | 8B 04 8B 83 C0 01 89 02 49 75 F6 |
Address Resolution
| Pass 1 | Assign addresses (location counter) |
| 0100 data1 | DD 42 ; now we know: data1 = 0x0100 |
| 0104 data2 | DD 58 ; data2 = 0x0104 |
| 0108 result | DD 0 ; result = 0x0108 |
| Pass 2 | Fill in addresses |
Relocation
Relocatable object file format
┌─────────────────────────────┐
│ Header │
│ - code size, data size │
│ - entry point │
├─────────────────────────────┤
│ Code Section (.text) │
│ Machine instructions with │
│ placeholder addresses │
├─────────────────────────────┤
│ Data Section (.data) │
│ Initialized global data │
├─────────────────────────────┤
│ Symbol Table │
│ - defined symbols + addr │
│ - undefined (external) │
├─────────────────────────────┤
│ Relocation Table │
│ - list of addresses that │
│ need adjustment │
│ - type of relocation │
└─────────────────────────────┘
Relocation types
R_386_32: Absolute 32-bit address
R_386_PC32: PC-relative 32-bit offset
R_X86_64_64: Absolute 64-bit address
Example
Source: CALL printf
Object: E8 00 00 00 00 (placeholder offset)
Relocation entry: offset=1, type=R_386_PC32, symbol=printf
After linking (printf at 0x8048400, call at 0x8048100):
Final: E8 FB 02 00 00 (offset = 0x8048400 - 0x8048105 = 0x2FB)
Position-Independent Code (PIC)
Backpatching for Branch Instructions
| Problem | Forward branches reference labels not yet seen. |
| Solution | Backpatching |
| L1 | x = 1 |
| L2 | ... |
| 0000 | CMP [a], [b] |
| 0006 | JG 0x0000 ← patch list for L1: [0007] |
| 000C | MOV [x], 0 |
| 0012 | JMP 0x0000 ← patch list for L2: [0013] |
| 0018: MOV [x], 1 ← L1 defined! Patch 0007 | offset to 0018 |
| 001E: ... ← L2 defined! Patch 0013 | offset to 001E |
| 0006 | JG 0x0018 (or relative: JG +0x0E) |
| 0012 | JMP 0x001E (or relative: JMP +0x08) |
Object File Formats
Common formats
┌──────────────────────────────────────────────┐
│ ELF (Executable and Linkable Format) - Linux │
│ PE/COFF - Windows │
│ Mach-O - macOS/iOS │
│ WASM - WebAssembly │
└──────────────────────────────────────────────┘
ELF structure
ELF Header (magic number, type, machine, entry point)
Program Header Table (segments for execution)
Section Header Table (sections for linking)
Sections: .text, .data, .bss, .rodata, .symtab, .rel.text
Code Emission Strategies
| Strategy 1 | Direct binary emission (JIT compilers) |
| Strategy 2 | Assembly text output (traditional compilers) |
| Strategy 3 | Object file emission (modern compilers like LLVM) |
| inst.setOpcode(X86 | :MOV32rr); |
| inst.addOperand(MCOperand | :createReg(X86::EAX)); |
| inst.addOperand(MCOperand | :createReg(X86::EBX)); |
Interview Questions
- Q: Why do x86 instructions have variable length while ARM has fixed length?
A: x86 evolved from 8-bit era prioritizing code density (shorter encodings for common ops). ARM chose fixed 32-bit for simpler decoding (instruction boundaries always at 4-byte multiples) enabling faster pipelining. The trade-off is code size vs decode simplicity.
- Q: What is the purpose of the relocation table?
A: It lists every location in the object file containing an address that depends on the final load address. The linker uses it to fix up these addresses when combining object files and assigning final addresses. Without it, separately compiled modules could never reference each other.
- Q: How does a JIT compiler handle machine code generation differently?
A: JIT compilers emit binary directly into executable memory (no assembly text or object files). They resolve addresses immediately (no relocation needed), can use runtime information for optimization, and must balance compilation speed with code quality since compilation happens during execution.
- Q: What is backpatching and why is it needed?
A: Backpatching handles forward references — when code references a label that hasn't been defined yet. The compiler emits a placeholder, records its location, and fills in the correct address when the label is finally encountered. This enables single-pass code generation for control flow structures.
- Q: How does position-independent code work and why is it needed?
A: PIC uses relative addresses (PC-relative or GOT-indirect) instead of absolute addresses, so it works correctly regardless of where it is loaded in memory. It is essential for shared libraries that are loaded at unpredictable addresses and must be shareable between processes.
Exam Focus
Revise definitions, diagrams, examples, and short-answer points for Machine Code Generation in Compilers.
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, machine, machine code generation in compilers
Related Compiler Design Topics