From C to MIPS Machine Code: Branches, Instruction Formats and Addressing Modes

The idea: a program is just numbers in memory

A processor does not understand C, and it does not understand assembly text either. A compiler turns each C statement into a few simple MIPS instructions; an assembler turns each instruction into one 32-bit word, its machine code; the loader puts those words in memory. From then on the program is a list of numbers at 0x00400000, 0x00400004, … and the processor does only one thing over and over: fetch the word at the address in the program counter (PC), decode it, execute it, and move the PC on. This is the stored-program idea: code and data live in the same kind of memory, as the same kind of numbers.

The page runs one small program the whole time: a loop over int a[3] = {5, 0, 7} that replaces each 0 with 1 and adds up the other values in s, then stores s in sum. On the left is the C source, in the middle the memory (the program at 0x00400000 and the data at 0x10010000), on the right the encoder, which splits a word into its fields. A colour tag links every C line to the instructions it became.

From C control flow to branches

MIPS has no if and no while. It has a compare, slt (set on less than: rd = 1 if rs < rt, else 0), two conditional branches, beq and bne (branch if equal / not equal), and an unconditional jump j. Every C control structure is built from these (Demo: C becomes branches):

C	MIPS	Why
if (a[i] == 0) { then } else { else }	bne $t1, $0, else … then … j endif else: … endif:	the branch tests the opposite condition and jumps over the then-part; j jumps over the else-part
while (i < 3) { body }	while: slt $t2, $s1, $t3 beq $t2, $0, done … body … j while done:	slt turns < into 0 or 1; leave when it is 0; jump back after the body
for, do … while	the same pieces in another order	a for loop is a while with an init and an increment

Testing the opposite condition is the usual trick: when a[i] == 0 the code just falls through into the then-part, and only the other case needs a jump. Labels like else and done are names for addresses; they exist only in the assembly text. In the machine code they have become numbers.

Array access: base + offset

An array is consecutive words in memory. a[i] lives at the base address of a plus i × 4, because an int is 4 bytes and MIPS memory is byte-addressed. The compiler computes the address and then uses lw or sw:

sll  $t0, $s1, 2      # $t0 = i * 4   (shift left 2 = multiply by 4)
add  $t0, $t0, $s0    # $t0 = base of a + i * 4 = address of a[i]
lw   $t1, 0($t0)      # $t1 = a[i]

lw $t1, 0($t0) means "the word at $t0 + 0". The constant in front of the parentheses is a byte offset, so a variable at a fixed distance from a base needs no address computation at all: sum is the word right after a[2], so sum = s is just sw $s2, 12($s0). In Demo: the PC walks one loop pass the value 5 flies from a[0] into $t1.

Three instruction formats

Every MIPS instruction is exactly 32 bits, and there are only three ways to cut those bits into fields. The first 6 bits, the opcode (op), always say which format the rest is in: op = 0 is R-type, op = 2 or 3 is J-type, everything else is I-type.

Format	Fields (bits)	Used by
R (register)	op 6, rs 5, rt 5, rd 5, shamt 5, funct 6	add, sub, and, or, slt, sll, jr
I (immediate)	op 6, rs 5, rt 5, imm 16	addi, lui, lw, sw, beq, bne
J (jump)	op 6, addr 26	j, jal

All R-type instructions share op = 0; the 6-bit function field funct picks the operation (add = 32, slt = 42, sll = 0). shamt is the shift amount, used only by shifts. In an I-type instruction, rt is the destination for addi, lui and lw, but the source of the value for sw, and the second register compared for beq/bne.

Encoding bit by bit

Encoding is table lookup plus binary. Take add $t0, $t0, $s0 (Demo: encode add):

1. Look up the register numbers: $0 = 0, $t0–$t7 = 8–15, $s0–$s7 = 16–23. So rd = $t0 = 8, rs = $t0 = 8, rt = $s0 = 16. In the assembly the destination comes first; in the word it is the third register field.
2. Look up op and funct: 0 and 32. shamt = 0.
3. Write each field in binary with exactly its number of bits: 000000 01000 10000 01000 00000 100000.
4. Read the 32 bits 4 at a time as hex digits: 0000 0001 0001 0000 0100 0000 0010 0000 = 0x01104020.

An I-type immediate is a 16-bit two's complement number, so it can be negative: addi $t0, $t0, -1 has imm = 0xFFFF. The hardware sign-extends it to 32 bits before using it. lui (load upper immediate) exists because 16 bits are not enough for an address: lui $s0, 0x1001 makes $s0 = 0x10010000 (Demo: encode sw shows the I-type with an offset of 12).

Branch offsets count words from PC + 4

A branch target is not stored as an address. The 16-bit imm of beq/bne is the distance to the target, counted in words (instructions), starting from the instruction after the branch:

target = PC + 4 + imm × 4          imm = (target − (PC + 4)) / 4

For beq $t2, $0, done at 0x00400014: PC + 4 = 0x00400018, done = 0x00400040, the difference is 40 bytes = 10 words, so imm = 10 and the word is 0x1140000A (Demo: encode beq). It counts words because every instruction address ends in binary 00: storing those two zeros would waste 2 of the 16 bits, and dropping them lets a branch reach ±32K instructions instead of ±32 KB. It starts at PC + 4 because the processor has already computed PC + 4 while fetching (it needs it anyway for the next instruction), so the adder for the target just adds to it. A backward branch has a negative imm: a branch to the instruction before it has imm = −2 = 0xFFFE.

The same distance trick makes code position independent: if the loader moves the whole program, every branch still works, because only the distances matter. That is also why the linker in Translating and Starting a MIPS Program needs to fix up j and jal but not branches.

Five addressing modes

An addressing mode is the rule for where an instruction finds its operands or its target. MIPS has five, and the format already tells you which one an instruction uses (Demos: encode beq, encode j; Step shows the mode of every instruction in the encoder panel):

Mode	Operand / address	Example on the page
register	all operands in registers	add $t0, $t0, $s0, slt, sll
immediate	a 16-bit constant inside the word	addi $s1, $s1, 1, lui $s0, 0x1001
base	memory address = rs + sign-extended imm	lw $t1, 0($t0), sw $s2, 12($s0)
PC-relative	target = PC + 4 + imm × 4	beq $t2, $0, done, bne $t1, $0, else
pseudo-direct	target = (PC + 4)[31:28] : addr : 00	j while, j endif

Pseudo-direct is "almost direct": the 26-bit addr field is the target's word address without its top 4 bits and its two zero bits. j while jumps to 0x00400010, so addr = 0x00400010 >> 2 = 0x0100004 and the word is 0x08100004 (Demo: encode j). A j can therefore reach any instruction in the same 256 MB region as itself; to go further, put the address in a register and use jr.

The stored program and the PC

Press Step and watch what the processor actually uses: not the assembly text, but the word at PC. It reads op (and funct) to know the instruction, takes the register numbers and the immediate from their fields, executes, and sets the PC: PC + 4 normally, the branch target when a branch is taken, the jump target for j. Branches and jumps are nothing more than instructions that write the PC. The whole run executes 36 instructions and ends with a = {5, 1, 7} and sum = 12 (Run to End).

Because instructions are just numbers, a program can load, copy or even create other programs: that is how compilers, loaders, debuggers and just-in-time compilers work, and why a buffer overflow that writes data over code or over a return address is dangerous. How the hardware decodes and executes these words is the subject of The Single-Cycle MIPS Processor and How a Program Runs on the MIPS Datapath; calls with jal and jr $ra are in MIPS Procedure Calls; where this level sits among all the others is in Levels of Abstraction in a Computer.

What the page leaves out

The page runs one fixed program, compiled by hand the way H&H does it; a real compiler would keep i × 4 in a register and add 4 each time, or unroll the loop. There are no branch delay slots (a real MIPS also executes the instruction after a branch or jump), no jal/jr calls, no pseudo-instructions such as la, li, blt or move (the assembler expands them into lui/ori, slt/bne and add), no $gp-relative data, and no exceptions for a misaligned address or an overflow. Only the registers the program uses are drawn, and the run simply stops when the PC passes the last instruction, where a real program would make an exit system call.

References

Harris and Harris, Digital Design and Computer Architecture, MIPS edition, Sections 6.3–6.5: Machine Language, Programming, Addressing Modes

Patterson and Hennessy, Computer Organization and Design, MIPS edition, Sections 2.5–2.10: Representing Instructions, Making Decisions, MIPS Addressing

MIPS32 Architecture (instruction set reference manuals)