MIPS Instruction Set Architecture Fundamentals

The MIPS Instruction Set Architecture (ISA) is a fundamental concept for students delving into computer organization. It serves as a classic example of a Reduced Instruction Set Computer (RISC) architecture, widely used in embedded systems due to its simplicity and efficiency. This article provides a comprehensive overview of MIPS ISA fundamentals, covering its operations, data handling, procedure calls, and memory organization.

MIPS Instruction Set Architecture Fundamentals Explained

The MIPS ISA defines the set of instructions a MIPS processor can execute. Designed for simplicity and regularity, MIPS operations typically involve three operands: two sources and one destination. This consistent structure simplifies implementation and enables higher performance at a lower cost.

Core Arithmetic Operations

MIPS primarily supports basic arithmetic operations like addition (add) and subtraction (sub). For example, the C code f = (g + h) - (i + j); translates to MIPS as:

add $t0, $s1, $s2 # temp t0 = g + h
add $t1, $s3, $s4 # temp t1 = i + j
sub $s0, $t0, $t1 # f = t0 - t1

This demonstrates the use of temporary registers ($t0, $t1) for intermediate results and saved registers ($s0, $s1, etc.) for variables.

Register Operands: The Heart of MIPS

MIPS utilizes a 32 × 32-bit register file for frequently accessed data. These registers are much faster to access than main memory, making their efficient use crucial for performance. The MIPS architecture adheres to Design Principle 2: Smaller is faster, prioritizing a limited number of fast registers over millions of slower memory locations. Key register types include:

• $a0 – $a3: Used for passing procedure arguments (registers 4-7).
• $v0, $v1: Used for returning procedure results (registers 2 and 3).
• $t0 – $t9: Temporary registers that can be overwritten by a called procedure (callee).
• $s0 – $s7: Saved registers that must be preserved by a callee; if used, they must be saved and restored.
• $gp: Global pointer for static data (register 28).
• $sp: Stack pointer (register 29).
• $fp: Frame pointer (register 30).
• $ra: Return address register (register 31), holding the address of the instruction following a procedure call.
• $zero: A special register (register 0) that always holds the constant value 0 and cannot be overwritten. It's useful for operations like moving data between registers (e.g., add $t2, $s1, $zero).

Memory Operands and Data Transfer

Main memory is used for larger data structures like arrays, structures, and dynamic data. MIPS memory is byte-addressed, meaning each address identifies an 8-bit byte. Words (32-bit data) are aligned, requiring their addresses to be a multiple of 4. MIPS is also Big Endian, where the most-significant byte of a word is stored at the lowest address.

To perform arithmetic on data in memory, values must first be loaded into registers using lw (load word) and results stored back using sw (store word). For example:

• g = h + A[8]; where g is in $s1, h in $s2, and base address of A in $s3.

lw $t0, 32($s3) # load word A[8] into $t0 (index 8 * 4 bytes/word = offset 32)
add $s1, $s2, $t0 # $s1 = $s2 + $t0 (g = h + A[8])

Immediate Operands: Making the Common Case Fast

MIPS includes immediate operands to directly specify constant data within an instruction. This avoids the need for a separate load instruction. For instance, addi $s3, $s3, 4 adds the constant 4 to register $s3. This design adheres to Design Principle 3: Make the common case fast, as small constants are frequently used.

MIPS Data Representation: Signed, Unsigned, and Character Data

Understanding how MIPS represents numbers and characters is crucial for accurate programming.

Signed and Unsigned Integers

MIPS handles both signed and unsigned 32-bit binary integers:

• Unsigned Binary Integers: Represent values from 0 to +2^32 - 1 (0 to +4,294,967,295). All bits contribute positively to the value.
• 2s-Complement Signed Integers: Represent values from -2^31 to +2^31 - 1 (-2,147,483,648 to +2,147,483,647). The most significant bit (bit 31) acts as the sign bit (1 for negative, 0 for non-negative).
• Negating a 2s-complement number involves complementing all bits and adding 1.
• Sign Extension: When representing a smaller signed number with more bits, the sign bit is replicated to the left to preserve its numeric value. Unsigned values are extended with zeros.

Signed vs. Unsigned Comparison

MIPS provides distinct instructions for signed and unsigned comparisons:

• slt rd, rs, rt: Sets rd to 1 if rs < rt (signed comparison), else 0.
• slti rt, rs, constant: Sets rt to 1 if rs < constant (signed immediate comparison), else 0.
• sltu rd, rs, rt: Sets rd to 1 if rs < rt (unsigned comparison), else 0.
• sltui rt, rs, constant: Sets rt to 1 if rs < constant (unsigned immediate comparison), else 0.

Consider $s0 = 1111...1111_2 (-1 signed, 4,294,967,295 unsigned) and $s1 = 0000...0001_2 (+1 signed/unsigned):

• slt $t0, $s0, $s1: Result is 1, because -1 < +1 (signed).
• sltu $t0, $s0, $s1: Result is 0, because 4,294,967,295 > +1 (unsigned).

Character Data

MIPS supports various character encodings:

• ASCII: 128 characters (7-bit encoding).
• Latin-1: 256 characters (8-bit encoding), extending ASCII.
• Unicode: A 32-bit character set supporting most of the world's alphabets and symbols, commonly used in Java and C++ wide characters, often encoded as UTF-8 or UTF-16 (variable-length encodings).

MIPS provides byte (lb, lbu, sb) and halfword (lh, lhu, sh) load/store instructions for handling character data. lb and lh sign-extend to 32 bits, while lbu and lhu zero-extend.

MIPS Instruction Formats and Machine Code

MIPS instructions are encoded as 32-bit machine code, represented in binary. The architecture features a small number of instruction formats, simplifying decoding and adhering to Design Principle 4: Good design demands good compromises.

R-format Instructions

Used for register-to-register operations (e.g., add, sub).

• op (6 bits): Operation code.
• rs (5 bits): First source register number.
• rt (5 bits): Second source register number.
• rd (5 bits): Destination register number.
• shamt (5 bits): Shift amount (0 for non-shift operations).
• funct (6 bits): Function code (extends opcode).

Example: add $t0, $s1, $s2 (where $s1 is reg 17, $s2 is reg 18, $t0 is reg 8, funct for add is 32).

op=0, rs=17, rt=18, rd=8, shamt=0, funct=32

I-format Instructions

Used for immediate arithmetic and load/store instructions.

• op (6 bits): Operation code.
• rs (5 bits): Base register for address or source register.
• rt (5 bits): Destination or source register.
• constant or address (16 bits): Immediate value or offset for memory access.

Example: addi $s3, $s3, 4

Hexadecimal Representation

Hexadecimal (base 16) is a compact way to represent bit strings, with each hex digit corresponding to 4 bits (e.g., eca8 6420_16 represents 1110 1100 1010 1000 0110 0100 0010 0000_2).

MIPS Logical Operations

MIPS provides instructions for bitwise manipulation, useful for masking, setting, or extracting bits within a word.

• Shift Left Logical (sll): Shifts bits left, filling with 0s. sll by i bits multiplies by 2^i.
• Shift Right Logical (srl): Shifts bits right, filling with 0s. srl by i bits divides by 2^i (unsigned only).
• Bitwise AND (and, andi): Clears specific bits to 0, useful for masking.
• Bitwise OR (or, ori): Sets specific bits to 1, useful for including bits.
• Bitwise NOT (nor): MIPS implements NOT through nor $t0, $t1, $zero, where a NOR b == NOT (a OR b).

MIPS Control Flow: Making Decisions

MIPS uses conditional and unconditional branch instructions to control program flow.

Conditional Branches

• beq rs, rt, Label: Branch if rs equals rt.
• bne rs, rt, Label: Branch if rs does not equal rt.

These instructions, combined with slt (set less than), allow for complex conditional logic found in if statements and loops. For efficiency, MIPS favors simple equality/inequality branches (Design Principle 3).

Unconditional Jumps

• j Label: Unconditional jump to a target address.

Basic Blocks

Compilers identify basic blocks – sequences of instructions without embedded branches (except at the end) or branch targets (except at the beginning) – for optimization. This can accelerate execution on advanced processors.

MIPS Procedure Calling Conventions and Stack Management

Procedures (or functions) are a cornerstone of structured programming. MIPS defines specific steps and register usage for procedure calls.

Steps for Procedure Calling

1. Place parameters in argument registers ($a0-$a3).
2. Transfer control to the procedure using jal (jump and link).
3. Acquire storage for the procedure (on the stack).
4. Perform the procedure's operations.
5. Place the result in result registers ($v0, $v1).
6. Return to the place of call using jr $ra.

Procedure Call Instructions

• jal ProcedureLabel: Jump and Link. Stores the address of the instruction following jal into the return address register ($ra), then jumps to ProcedureLabel.
• jr $ra: Jump Register. Copies the value in $ra (the return address) to the Program Counter (PC), effectively returning control to the caller.

Leaf Procedures (No Nested Calls)

A leaf procedure does not call other procedures. Consider the C code int leaf_example (int g, h, i, j) { int f; f = (g + h) - (i + j); return f; }.

In MIPS, arguments g,h,i,j would be in $a0-$a3, f in a saved register like $s0, and the result in $v0. Since $s0 is used, it must be saved and restored from the stack by the callee.

leaf_example:
 addi $sp, $sp, -4 # Adjust stack for 1 item
 sw $s0, 0($sp) # Save $s0 on stack
 add $t0, $a0, $a1 # g + h
 add $t1, $a2, $a3 # i + j
 sub $s0, $t0, $t1 # f = (g+h) - (i+j)
 add $v0, $s0, $zero # Place result f in $v0
 lw $s0, 0($sp) # Restore $s0 from stack
 addi $sp, $sp, 4 # Restore stack pointer
 jr $ra # Return to caller

Non-Leaf Procedures (Nested Calls)

A non-leaf procedure calls other procedures. When a non-leaf procedure makes a nested call, the caller is responsible for saving its return address ($ra), and any arguments ($a0-$a3) or temporaries ($t0-$t9) that are needed after the nested call. These values are saved on the stack before the call and restored after.

Example: Recursive fact(n) function (n in $a0, result in $v0)

fact:
 addi $sp, $sp, -8 # Adjust stack for 2 items ($ra, $a0)
 sw $ra, 4($sp) # Save return address
 sw $a0, 0($sp) # Save argument n
 slti $t0, $a0, 1 # Test for n < 1
 beq $t0, $zero, L1 # If n < 1, branch to L1 (base case)
 addi $v0, $zero, 1 # Result is 1 (n=0 or negative)
 addi $sp, $sp, 8 # Pop 2 items from stack
 jr $ra # Return
L1:
 addi $a0, $a0, -1 # n = n - 1
 jal fact # Recursive call
 lw $a0, 0($sp) # Restore original n
 lw $ra, 4($sp) # Restore return address
 addi $sp, $sp, 8 # Pop 2 items from stack
 mul $v0, $a0, $v0 # Multiply to get result (n * fact(n-1))
 jr $ra # Return

Local Data on the Stack

Local data, such as C automatic variables, are allocated by the callee on the stack within a procedure frame (or activation record). The stack pointer ($sp) and frame pointer ($fp) manage this stack storage.

Memory Layout

MIPS memory is typically organized into segments:

• Text: Stores the program code (machine instructions).
• Static Data: Holds global variables, C static variables, constant arrays, and strings. The global pointer ($gp, register 28) is initialized to an address within this segment.
• Dynamic Data (Heap): Used for dynamically allocated data (e.g., malloc in C, new in Java).
• Stack: Used for automatic storage, local variables, return addresses, and saved registers during procedure calls. It grows downwards in memory.

MIPS Addressing Modes and Synchronization

MIPS employs various addressing modes to efficiently access data and instructions.

32-bit Constants

While most constants fit in 16 bits for addi and similar instructions, lui (load upper immediate) is used to load a 32-bit constant. lui rt, constant copies a 16-bit constant to the left 16 bits of rt and clears the right 16 bits to 0. It can be combined with ori to load a full 32-bit value.

Branch Addressing

Branch instructions (beq, bne) use PC-relative addressing. The target address is calculated as PC + (offset × 4), where the 16-bit offset allows branching forward or backward relative to the current Program Counter (PC). If a branch target is too far, the assembler can rewrite the code using an inverted conditional branch followed by an unconditional jump.

Jump Addressing

Jump instructions (j, jal) use (pseudo)direct jump addressing. The target address is formed by concatenating the upper 4 bits of the PC with the 26-bit address field (shifted left by 2 bits, effectively multiplying by 4) to form a 32-bit absolute address within the text segment.

Synchronization in MIPS

For parallel processors sharing memory, synchronization is vital to prevent data races. MIPS provides hardware support for atomic read/write operations through a pair of instructions:

• ll rt, offset(rs): Load Linked. Loads a word from memory and sets a link to that location.
• sc rt, offset(rs): Store Conditional. Attempts to store a word. It succeeds (returns 1 in rt) only if the memory location has not been modified since the corresponding ll instruction. If it fails (returns 0), the operation must be retried.

This pair is crucial for implementing synchronization primitives like locks.

MIPS Pseudoinstructions and the Compilation Process

Assemblers offer pseudoinstructions – convenient aliases that translate into one or more actual machine instructions. For example:

• move $t0, $t1 translates to add $t0, $zero, $t1.
• blt $t0, $t1, L (branch if less than) translates to slt $at, $t0, $t1 followed by bne $at, $zero, L (using the assembler temporary register $at).

Translation and Startup

The process of transforming source code into an executable program involves several steps:

1. Compilation/Assembly: The compiler (or assembler) translates source code into machine instructions, creating an object module. This module contains translated instructions (text segment), static data, relocation information, a symbol table, and debug information.
2. Linking: A linker combines multiple object modules (and libraries) into a single executable image. It merges segments, resolves labels by determining their absolute addresses, and patches location-dependent references. Static linking incorporates all referenced library procedures into the executable.
3. Loading: A loader takes the executable image from disk and loads it into memory. It creates the virtual address space, copies text and initialized data, sets up arguments on the stack, initializes registers (including $sp, $fp, $gp), and jumps to a startup routine that calls main.
4. Dynamic Linking: An alternative to static linking, dynamic linking links library procedures only when they are called during runtime. This avoids image bloat and allows automatic updates to library versions. It often uses an indirection table and a stub for lazy linkage.

FAQ: MIPS Instruction Set Architecture for Students

What are the main design principles of MIPS ISA?

MIPS ISA follows four core design principles: Simplicity favors regularity (consistent instruction format), Smaller is faster (fewer, faster registers), Make the common case fast (immediate operands, simple branches), and Good design demands good compromises (balancing instruction formats for decoding ease).

How does MIPS handle procedure calls and returns?

MIPS handles procedure calls by placing arguments in $a0-$a3, transferring control with jal (which saves the return address in $ra), and returning with jr $ra. For non-leaf procedures, callers must save $ra, arguments, and temporaries on the stack before nested calls.

What is the difference between signed and unsigned comparison in MIPS?

Signed comparison instructions (slt, slti) interpret operands as two's complement signed integers. Unsigned comparison instructions (sltu, sltui) interpret operands as non-negative binary numbers. This distinction is crucial for correctly comparing values that might exceed the positive range of signed integers.

Why does MIPS use $zero register?

The $zero register (register 0) always holds the constant value 0. It's highly useful for common operations like moving a register's content to another (e.g., add $t0, $s1, $zero effectively moves $s1 to $t0), and for conditional checks in branches (e.g., beq $t0, $zero, Label).

What are MIPS addressing modes and how do they work?

MIPS uses several addressing modes: Register Addressing (operands are registers), Immediate Addressing (an operand is a constant within the instruction), Base/Displacement Addressing (for memory access, an offset is added to a base register's content), PC-Relative Addressing (for branches, target is relative to the Program Counter), and Pseudodirect Addressing (for jumps, using a portion of the PC and an instruction field for the target address). These modes define how the processor finds operands or target locations. For more details on computer addressing, you can refer to the Addressing mode Wikipedia article.