Assembly Language Fundamentals

An assembly language is a low-level programming notation in near one-to-one correspondence with a processor's machine instructions. Each line typically encodes exactly one machine instruction: an mnemonic (a short symbolic name such as `add`, `lw`, `beq`) followed by a fixed number of operands. Operands are drawn from three categories: registers (named storage locations inside the processor, such as `x1` or `t2`), immediates (numeric constants embedded directly in the instruction), and labels (symbolic names for addresses, resolved by the assembler rather than the programmer). In a RISC ISA the operand discipline is deliberately narrow. Arithmetic and logical instructions read and write only registers — never memory directly. Memory is touched exclusively through load and store instructions, which move a value between a register and a memory address computed from a base register plus an offset. This is the load-store architecture principle: it keeps the instruction formats few and uniform, which in turn keeps the hardware decoder and pipeline simple, a design tradeoff explored under RISC versus CISC Design Philosophies. Assembly syntax mirrors this directly — you will never see `add x5, 0(x6), x7` in a RISC assembly language, because arithmetic operands are always registers. A label is a textual name standing for an address — either the address of an instruction (a branch or jump target) or the address of a data item in memory. The programmer writes labels for readability; the assembler's job is to replace every label reference with the correct numeric address or offset once it knows where every label lives. This resolution step is what separates assembly language from raw machine code: the programmer writes `beq x0, x0, loop`, and the assembler computes exactly how many instructions backward `loop` sits and encodes that as a signed offset.

Turning symbolic assembly into machine code is the job of the assembler, and understanding its algorithm is the fastest way to understand assembly syntax itself — every syntactic rule exists to make some step of this algorithm well-defined.

Step 1 — Tokenize and parse. Each line is split into a mnemonic and its operands, with labels (if any) stripped off the front and comments discarded.

Step 2 — First pass: build the symbol table. The assembler walks the program once, tracking a location counter (the address the next instruction or data item will occupy). Every label definition (`loop:`) is recorded in a symbol table with its resolved address. No machine code is emitted yet, because a label used before it is defined — a forward reference — cannot be resolved until the whole program has been scanned.

Step 3 — Second pass: emit machine code. The assembler walks the program again. For each instruction it looks up the opcode's format, encodes each register operand into its bit field, and — for instructions referencing a label — computes the address or offset from the symbol table and encodes it as an immediate.

Step 4 (implicit) — Relocation/linking, when multiple files are assembled separately, adjusts addresses that depend on final placement in memory; this is outside the scope of a single assembler pass but is the natural next step after assembly. The reason a two-pass algorithm is necessary — not merely convenient — is the forward-reference problem: a branch to a label defined later in the file cannot be encoded correctly during a single left-to-right scan, because its address is not yet known. ``` // Two-pass assembler, simplified for a RISC-style ISA function ASSEMBLE(sourceLines): symbolTable = empty map // label -> address instructions = [] // parsed (mnemonic, operands, sourceLabel) tuples locationCounter = BASE_ADDRESS INSTR_SIZE = 4 // bytes; fixed-width RISC encoding // ---------- PASS 1: resolve labels ---------- for line in sourceLines: if line is blank or a pure comment: continue if line starts with "LABEL:": symbolTable[LABEL] = locationCounter line = rest of line after "LABEL:" if line is empty: continue // label-only line, no instruction parsed = PARSE(line) // mnemonic + operand list instructions.append(parsed) locationCounter += INSTR_SIZE // ---------- PASS 2: emit machine code ---------- machineCode = [] pc = BASE_ADDRESS for instr in instructions: fmt = FORMAT_OF(instr.mnemonic) // e.g. R-type, I-type, S-type, SB-type fields = { opcode: OPCODE(instr.mnemonic) } for operand in instr.operands: if operand is a register name: fields[nextRegisterField] = REGISTER_NUMBER(operand) // e.g. "t0" -> 5 else if operand is a numeric immediate: fields[immediateField] = operand else if operand is a label: target = symbolTable[operand] // error if undefined -> undefined symbol if fmt is branch-type: fields[immediateField] = (target - pc) // PC-relative offset else: fields[immediateField] = target // absolute address (jump/data) word = ENCODE(fmt, fields) // pack bit fields into a 32-bit instruction machineCode.append(word) pc += INSTR_SIZE return machineCode ``` The key subroutines — `FORMAT_OF`, `OPCODE`, `REGISTER_NUMBER`, `ENCODE` — are exactly the encoding tables covered under Instruction Formats and Encoding; assembly syntax is simply the human-facing name for each field those tables define numerically.

Reading assembly, then, is the reverse of the diagram above: given `add x5, x6, x7`, you know immediately which bit fields the assembler will fill and which the decoder will later read, without ever touching binary by hand.

Register naming conventions. RISC ISAs give registers both a numeric name (`x0`–`x31`) and a conventional symbolic name reflecting its intended role: `zero` (hardwired to 0), `ra` (return address), `sp` (stack pointer), `a0`–`a7` (arguments/return values), `t0`–`t6` (temporaries, not preserved across calls), `s0`–`s11` (saved registers, preserved across calls). These roles are a software convention enforced by compilers and calling code, not by the hardware — the processor treats `x5` and `t0` identically, since they are the same register.

Labels in data and code. A label can mark an instruction (`loop:`) or a data item in a `.data` section (`msg: .asciz "hi"`), and directives like `.word`, `.asciz`, `.space` tell the assembler how many bytes to reserve and how to initialize them, contributing to the location counter exactly as instructions do.

Time complexity. Assembling a program of $n$ lines takes $\Theta(n)$ time with a well-implemented two-pass assembler: each pass is a single linear scan, and symbol-table lookups/insertions run in expected $O(1)$ time using a hash map keyed by label name. Total time is therefore

If the symbol table were instead a sorted array requiring $O(\log n)$ lookup, or a linear list requiring $O(n)$ lookup per reference, total time would degrade to $\Theta(n \log n)$ or $\Theta(n^2)$ respectively — so the hash-map choice is what makes assembly linear-time in practice, and virtually all production assemblers use one.

Space complexity. The symbol table holds at most one entry per label, so it is $O(L)$ where $L \le n$ is the number of distinct labels; the output machine code is $\Theta(n)$ words for a fixed-width RISC encoding, since every instruction line produces exactly one instruction word.

Correctness — the forward-reference invariant. The central correctness argument is: by the time pass 2 encodes any instruction referencing label $\ell$, the symbol table already contains $\ell$'s final address. This holds because pass 1 completes in full — scanning every line and recording every label — before pass 2 begins; hence every label, whether defined before or after its use, is present in the table before any encoding happens. This is precisely why a single-pass assembler cannot correctly handle backward branches to not-yet-seen labels without a patch-up mechanism: it would need to guess or defer encoding, which the two-pass structure avoids entirely.

Correctness — fixed-width, load-store discipline. A second correctness property specific to RISC assembly is decodability: because every instruction is the same width (typically 32 bits) and every operand field sits in a fixed bit position determined solely by the instruction's format (R/I/S/SB/U/UJ-type), a decoder can extract any field via a fixed bit-mask without first knowing the opcode. This is why RISC assembly syntax is rigid — a fixed number of operands in a fixed order per mnemonic — since the syntax must correspond to a format the hardware can decode without variable-length lookahead, unlike variable-length CISC encodings.

Tradeoffs. Two-pass assembly costs a second full scan of the source, doubling constant-factor work compared to an (impossible-in-general) single pass; this is a negligible price for programs of realistic size and is universally accepted. The load-store discipline that keeps decoding simple also means RISC assembly programs are often longer, line-for-line, than CISC equivalents (an addition of a memory operand to a register requires an explicit `lw` first), trading code density for uniformity and pipelining ease.

Consider this short RISC-V-style assembly fragment that sums the integers from 1 to 5 into `x10`, using `x5` as loop counter and `x6` as the running sum: ``` addi x5, x0, 5 # x5 = 5 (loop counter, counts down) addi x6, x0, 0 # x6 = 0 (sum accumulator) loop: beq x5, x0, done # if x5 == 0, exit loop add x6, x6, x5 # sum += counter addi x5, x5, -1 # counter -= 1 beq x0, x0, loop # unconditional branch back to loop done: add x10, x6, x0 # x10 = sum (result) ```

Pass 1 (symbol table construction). Assume instructions start at address `0x00` and each is 4 bytes.

Symbol table after pass 1: `{ loop: 0x08, done: 0x18 }`.

Pass 2 (encoding the branches). RISC-V branch offsets are PC-relative, so:

• `beq x5, x0, done` at `pc = 0x08`: offset = `0x18 − 0x08 = 0x10` (encoded as `+16`, a forward reference).
• `beq x0, x0, loop` at `pc = 0x14`: offset = `0x08 − 0x14 = −0x0C` (encoded as `−12`, a backward reference).

Both were resolvable only because pass 1 had already recorded both labels before pass 2 began — the forward reference to `done` is the exact case a single-pass assembler cannot handle without extra machinery.

Execution trace. Now trace the processor state, one instruction at a time (register values in decimal):

The result `x10 = 15 = 1+2+3+4+5` confirms both the algebra and the branch resolution: the forward-referenced `done` label and the backward-referenced `loop` label both worked correctly, exactly as the symbol table predicted.

Assembly language's core idea — replacing binary opcodes with mnemonics, and addresses with symbolic labels — emerged directly from the earliest stored-program computers, where every instruction had previously been entered as raw binary or octal digits by hand. The move to symbolic assembly was one of the first and most consequential usability innovations in the history of computing, because it turned programming from an error-prone bit-manipulation task into a readable, checkable discipline, and it made possible the very idea of a program that translates another program — the assembler itself, and later the compiler.

Every compiler backend — GCC, LLVM/Clang, and the code generators inside JIT compilers such as those in the JVM or V8 — ultimately emits assembly or an equivalent in-memory instruction representation before final machine-code generation; understanding assembly syntax is what lets engineers read and debug that output. Operating system kernels (Linux, seL4, FreeRTOS) contain hand-written assembly at boundaries the compiler cannot reach: context switches, interrupt vector entry points, and the very first bootstrap instructions executed after reset. Embedded systems and microcontroller firmware, where every instruction and every byte of memory is scarce, still rely on assembly for the tightest inner loops and for interfacing with memory-mapped hardware registers. Debuggers and disassemblers (GDB, objdump, IDA Pro, Ghidra) present machine code back to engineers as assembly, meaning the ability to read symbolic RISC instructions is a prerequisite for security research, reverse engineering, and low-level performance debugging. Instructional RISC ISAs — MIPS, RISC-V, and ARM's AArch64 — are taught precisely because their clean, load-store assembly syntax makes the connection to Instruction Formats and Encoding and eventual Addressing Modes and Procedure Calls and the Stack conventions explicit and traceable by hand, exactly as demonstrated in the worked example above.

Ask the tutor: How does the assembler decide whether a label reference should be encoded as a PC-relative offset or an absolute address?