Architecture of an Assembler: Symbol resolution and backpatching

After code generation has constructed the initial binary stream, an assembler must resolve all symbolic references to their actual numeric addresses or offsets. This is the symbol resolution phase, which ensures correctness of jumps, calls, data accesses, and other references involving user-defined labels or externally declared symbols.

Due to forward references and the structure of assembly code, this phase is often coupled with backpatching—a corrective process used to insert previously unknown values into partially emitted machine code.

1. Purpose of Symbol Resolution

Assembly language allows symbols to stand in for:

• Labels (used for control flow or address targets)

• Variable and constant names

• External function references

• Sections and segments

These symbols must be translated into numeric values before the final machine code can be considered valid. The resolution process assigns each symbol a concrete address or offset based on its final location in memory or object file layout.

2. Symbol Table Construction

The assembler maintains a symbol table throughout the assembly process. This table includes:

• Name of the symbol (label, identifier, etc.)

• Section it belongs to (.text, .data, .bss, etc.)

• Offset or value, once known

• Type (local label, global, external, constant)

• Definition status (defined, undefined, multiple definitions)

• Relocation flags (if external or unresolved)

During the first pass, symbol entries are collected. Definitions update the table with offsets; references are stored as unresolved until the second pass.

3. Handling Forward References

A forward reference occurs when an instruction or data directive refers to a symbol defined later in the code. For example:

    jmp forward_label
    ...
forward_label:

In such cases, the assembler cannot encode the correct relative offset for jmp during its first encounter with the instruction. Instead, it must:

• Record the location of the placeholder (often with a dummy or zeroed value).

• Defer encoding until the symbol's address becomes known.

This is where backpatching becomes necessary.

4. Backpatching Explained

Backpatching is the act of returning to a location in the generated code and inserting the correct bytes once the target symbol’s address is resolved. This usually happens in the second pass or during a relocation step.

The assembler maintains a patch list for unresolved references. Each patch record includes:

• Location in the code buffer

• Size of the fixup (e.g., 1, 4, or 8 bytes)

• Type of reference (e.g., relative jump, absolute address)

• Target symbol name

• Offset adjustment (e.g., - instruction size for relative jumps)

Once the target is known, the assembler calculates the correct value, encodes it in little-endian form, and overwrites the placeholder.

5. Example: Backpatching a Relative Jump

Given:

    jmp skip
    nop
skip:
    mov eax, 0

The jmp instruction requires a relative offset from its own end to the label skip. During the first pass, the assembler:

• Emits the opcode and reserves 1 or 4 bytes (depending on form) for the offset.

• Notes the location and the target label (skip).

• Leaves the offset value empty or filled with zeros.

Later, when skip is reached and its final offset is determined, the assembler:

• Calculates target_address - (jmp_address + jmp_length)

• Converts this into a signed integer (e.g., -1)

• Backpatches the offset into the previously reserved location

6. External Symbol References

Symbols declared but not defined inside the current module (e.g., extern printf) cannot be resolved to concrete addresses by the assembler alone. In these cases:

• The assembler marks the symbol as external.

• Relocation records are generated for the linker to process later.

• The code may use placeholder values or section-relative addresses, depending on object format.

7. Error Handling in Resolution

If a symbol is:

• Used but never defined: the assembler reports an “undefined symbol” error.

• Defined multiple times: the assembler raises a “duplicate symbol” error unless allowed (e.g., weak aliases).

• Used in an invalid context (e.g., assigning a data label in code): an appropriate diagnostic is issued.

Robust assemblers detect these conditions early and provide location-aware error messages.

8. Two-Pass Assembly and Resolution Strategy

Traditional assemblers follow a two-pass strategy:

Pass 1:

• Parse source

• Collect symbols and layout sections

• Emit code with placeholders

• Record all references needing resolution

Pass 2:

• Resolve all symbols

• Finalize addresses

• Backpatch all unresolved references

• Produce binary output and relocation entries

More advanced assemblers may use single-pass plus backpatch queues or delayed emission strategies for efficiency.

9. Modern Enhancements Post-2020

Recent assembler implementations introduced advanced resolution features:

• Incremental backpatching during optimization or macro expansion

• Cross-section resolution, allowing early layout prediction for better jump encoding

• Symbol scoping enhancements, including nested label contexts

• Resolution caching during just-in-time assembly for virtual machines or runtime code emission

These enhancements improve assembly speed, output compactness, and make dynamic assemblers more robust.

10. Summary

Symbol resolution and backpatching ensure all symbolic references in assembly code are correctly bound to concrete values in the binary. Together, they bridge human-readable structure with strict machine code requirements. This phase guarantees correctness, enables flexibility in code layout, and prepares the assembled output for linkage and execution.