Computer Language

When designing a product, defining its specifications is crucial. This principle applies to computer hardware and software as well. The Instruction Set Architecture (ISA) serves as the specification for a computer's software interface. To understand how a computer is built and operates, we need to grasp the instructions that drive it. In this section, we will explore the MIPS assembly language and how to map high-level programming concepts to low-level machine instructions.

Basic Concepts

Commands in high-level programming languages, such as C, Java, or Python, are called statements. These statements are mapped to instructions in assembly language. For example, the C statement p = x + y * z can be translated into MIPS assembly as a series of instructions like add $s0, $s1, $s2. Typically, a single high-level statement translates into multiple low-level instructions.

An instruction is a primitive operation that the CPU executes. The collection of instructions that a CPU can execute is known as its Instruction Set. CPUs are compatible if they use the same instruction set.

In low-level programming, data is stored in hardware, so understanding the fundamental hardware structure and the instruction set, which forms the ISA (Instruction Set Architecture), is essential.

MIPS Assembly Language

MIPS is a family of processors, including models like the MIPS R2000/R3000 (32-bit), MIPS R4000 (64-bit), and MIPS R8000 (for graphics or scientific applications). Here, we introduce the MIPS R2000 instruction set.

The amount of data that a CPU can process in a single instruction is called the word size. The MIPS R2000 has a word size of 32 bits, meaning it can process 32 bits of data in a single instruction.

Instruction sets are divided into two categories: RISC (Reduced Instruction Set Computer) and CISC (Complex Instruction Set Computer). MIPS is a RISC architecture, meaning it has a small number of simple instructions, making it faster to execute instructions. In contrast, CISC architectures have a large number of complex instructions, offering more functionality but potentially increasing the complexity for programmers.

Stored Program Concept (Von Neumann Machine)

Modern computers are built on two fundamental principles: instructions are represented as binary numbers, and programs must be loaded into memory before execution. This concept is known as the stored program concept or the Von Neumann Machine. This allows instruction sets to be distributed in binary form, enabling compatibility across various computers that share the same instruction set architecture.

Instructions Structure

We should understand hardware information:

• Memory: Data and instructions are stored in memory.
• Registers: Temporary storage locations in the CPU.
• Instruction Format: How instructions are structured.
• Addressing Mode: How to access data in memory.

Basic Computer Structure

A basic computer structure comprises the control unit, datapath, memory, and I/O devices. The control unit and datapath together form the processor. Registers are stored in the datapath of the processor. Data is loaded from memory into the registers, operations are performed, and the results are stored back into memory.

The Control Unit directs the operation of the processor, while the Datapath performs arithmetic and logic operations via the ALU (Arithmetic Logic Unit) and stores intermediate data in Registers. Memory holds the program, data, and instructions. I/O Devices manage input, output, and storage.

Memory

Memory is a large array of bytes, each with a unique address, making it byte addressable (starting from 0). In practice, most data is stored in words (4 bytes), and the address points to the first byte of the word, making it word addressable.

For example:

• Address 0x0000 points to the first byte of the first word.
• Address 0x0004 points to the first byte of the second word.

If we use 32 bits to represent memory addresses, we can address up to (2^32) bytes of memory, which equals 4GB of memory.

In MIPS architecture, all byte addresses must be word-aligned, meaning the address must be a multiple of 4. This ensures that the CPU can access memory efficiently for each instruction.

Here is an illustration of byte and word addresses in memory:

In this example:

• Address 0x0000, 0x0004, and 0x0008 point to the first byte of each word and are word-aligned.

Byte-Order or Endianness

Endianness refers to the order in which bytes are stored in memory. There are two types of endianness:

1. Big-Endian: The most significant byte (MSB) is stored at the lowest memory address. MIPS uses big-endian format.
2. Little-Endian: The least significant byte (LSB) is stored at the lowest memory address.

Quick Quiz:

Registers

Registers are small, fast storage locations within the CPU that temporarily hold data such as operands, addresses, and results. Due to their limited number, registers offer quicker access than main memory (4 bytes per register). MIPS architecture features 32 general-purpose 32-bit registers and 32 floating-point registers ($f0,$f1, ..., $f31). Additionally, it includes special-purpose registers like the Program Counter (PC), Stack Pointer (SP), and Return Address (RA).

Two 32-bit numbers can be multiplied into a 64-bit number. MIPS uses Hi and Lo special registers to store the high and low bits of the result, or the remainder and quotient of a division operation. For example, after a multiplication operation, the Hi register stores the upper 32 bits, while the Lo register stores the lower 32 bits.

The Program Counter (PC) is a 32-bit special register that holds the address of the next instruction to be executed, automatically incrementing after each instruction is fetched.

Most programs use more variables than there are registers available. Therefore, compilers store the most frequently used variables in registers and keep the rest in memory, using load and store instructions to transfer data between memory and registers. Spilling registers involves moving data from registers to memory to free up registers for other variables.

• Coprocessor 0 (CP0): Handles exceptions, controls the MMU (Memory Management Unit), and manages the TLB (Translation Lookaside Buffer).
• Coprocessor 1 (CP1): Floating Point Unit (FPU), Handles floating-point operations.

General Purpose Registers (GPRs)

Memory Management and Related Registers

A program in memory is divided into five address segments (from high to low addresses):

1. Stack: Contains local variables, function arguments, and return addresses. Grows from high to low addresses.
2. Heap: Used for dynamically allocated memory, like pointers. Grows from low to high addresses.
3. Static Data: Stores global variables that do not change during program execution.
4. Text (or Code): Contains the program instructions.

Procedure Frame (Activation Record): Each function call creates a new frame on the stack, storing the return address, arguments, local variables, and saved registers. The frame pointer ($fp) points to the base of the current frame, while the stack pointer ($sp) points to the top of the stack.

• Global Pointer ($gp): Points to the first variable address in the static data segment.
• Stack Pointer ($sp): Points to the top of the stack.
• Frame Pointer ($fp): Points to the base of the current procedure frame.

Translation and Execution of Programs

Computer hardware is designed to execute machine code, a sequence of binary instructions. High-level languages like C, Java, or Python are translated into machine code to be executed by the CPU. This translation process involves several steps, including compilation, assembly, linking, and loading.

Steps

High-level languages are translated into machine code through a series of steps:

1. High-Level Language (e.g., C, Java) Program -> Compiler -> Assembly Language Program: The source code is converted into assembly language.
2. Assembly Language Program -> Assembler -> Object Code: The assembly code is translated into machine code, also known as object code.
3. Object Code -> Linker -> Executable Code: The linker combines object code with required libraries and resolves address references to produce an executable file.
4. Executable Code -> Loader -> Memory -> Execution: The loader loads the executable code into memory, preparing it for execution by the CPU.

Example: Imagine you wrote a C program that adds two numbers. The compiler translates the C code into assembly language. The assembler converts this assembly language into object code. The linker combines this object code with necessary libraries (like printf) and resolves address references to produce the final executable. The loader then loads this executable into memory, where it can be executed by the CPU.

In some systems, these steps are optimized for speed. For instance, some systems produce pre-linked modules, or use a linking loader to combine linking and loading steps.

Program Translation and Execution

Loader

1. Read Executable Header: Determine the size of the text and data segments.
2. Allocate Memory: Allocate a large enough contiguous block of memory.
3. Copy Instructions and Data: Transfer executable instructions and data into memory.
4. Copy Arguments: Place program arguments into the stack.
5. Initialize Registers: Set up registers, with the stack pointer set to the available address.
6. Jump to Start-Up Routine: Transfer control to the start-up routine, which copies arguments from the stack to argument registers and then jumps to the main program. After the main program finishes, control returns to the start-up routine, which calls the exit system call.

All programs run as OS subroutines, ensuring system security by maintaining OS control.

Assembler Components

After reviewing the sources, here is the revised information on the components of an assembler:

1. Header: Contains metadata about the file, such as size and the location of various segments.
2. Text Segment: Contains the actual machine code instructions.
3. Static Data Segment: Holds global variables, constants, and static data.
4. Relocation Information: Identifies addresses that need to be updated when the program is loaded into memory.
5. Symbol Table: Stores information about symbols (labels and variables), including addresses for external references and unresolved references.
6. Debugging Information: Includes line number mappings and other data useful for debugging, linking the machine code back to the source code.

Java Program Translation

Here is an improved explanation of the Java program translation process with a diagram:

1. Source Code Compilation: The Java source code (.java files) is compiled into bytecode (.class files) by the Java compiler. These bytecode files are platform-independent and contain address references.
2. Loading and Linking: When a Java program is run, the Java Virtual Machine (JVM) loads the necessary .class files and links them. The JVM resolves the references to libraries and other classes as needed during this process.
3. Just-In-Time (JIT) Compilation: For improved performance, the JVM uses a Just-In-Time (JIT) compiler. The JIT compiler identifies "hot" methods that are frequently executed and compiles them into native machine code. This native code is then cached for future use, which reduces the overhead of interpretation.

The table provided for the arithmetic instructions is mostly correct, but there are a few inaccuracies and clarifications needed. Here is a revised version of the table:

Arithmetic Instructions

Perform binary operations. All instructions follow the format op dest, src1, src2, where op is the operation, dest is the destination register, and src1 and src2 are the source registers. Immediate and unsigned operations have similar formats with slight variations.

Example:

• C code: a = b + c + d; e = f - a;
• MIPS assembly:
  • add $t0, $s1, $s2 (b + c -> $t0)
  • add $t0, $t0, $s3 (b + c + d -> $t0)
  • sub $s4, $s5, $t0 (f - (b + c + d) -> $s4)

Steps in Arithmetic Instruction Execution:

1. Register Assignment: The compiler assigns registers to variables.
2. Translation: Convert high-level language statements to assembly instructions.
3. Optimization: The compiler optimizes the instructions for performance.

Data Transfer Instructions

Move data between memory and registers. The format is op dest, src, where op is the operation, dest is the destination register, and src is the source register or memory address.

Example:

• C code: A[12] = h + A[8]; ($s1 holds the base address of A,$s2 holds h)
• MIPS assembly:
  • lw $t0, 32($s1) (Load A[8] -> $t0)
  • add $t0, $s2, $t0 (h + A[8] -> $t0)
  • sw $t0, 48($s1) (Store h + A[8] -> A[12])

Flow Control Instructions

Control the flow of execution based on conditions. The format is op src1, src2, label, where op is the operation, src1 and src2 are source registers, and label is the target label.

Example - If-Else Statement:

• C code: if (x == y) z = 1; else z = 0;
• MIPS assembly:
  • beq $s0, $s1, L1 (Branch to L1 if x == y)
  • li $s2, 0 (z = 0)
  • j L2 (Jump to L2)
  • L1: li $s2, 1 (z = 1)
  • L2: ...

Example - Loop:

• C code: for (i = 0; i < 10; i++) sum += A[i];
• MIPS assembly:
  • li $s0, 0 (i = 0)
  • li $s1, 10 (Upper bound)
  • li $s2, 0 (sum = 0)
  • Loop: beq $s0, $s1, Exit (Check loop condition)
  • lw $t0, 4($s0) (Load A[i] -> $t0)
  • add $s2, $s2, $t0 (sum += A[i])
  • addi $s0, $s0, 1 (Increment i)
  • j Loop (Jump back to Loop)
  • Exit: ...

Basic Blocks

A basic block is a sequence of instructions with a single entry point and a single exit point, containing no branches except at the end, and no branch targets except at the beginning. When the compiler translates high-level code to assembly, it identifies basic blocks to optimize execution block by block.

MIPS does not provide blt, bgt, ble, and bge instructions. Instead, these comparisons are achieved by combining beq, bne, and slt (Set on Less Than) instructions to produce Pseudo-Instructions or Directive Instructions. Here is the mapping:

Explanation:

• slt $t0, $s0, $s1: Sets $t0 to 1 if $s0 < $s1, otherwise sets $t0 to 0.
• bne $t0, $zero, label: Branches to label if $t0 is not equal to 0.
• beq $t0, $zero, label: Branches to label if $t0 is equal to 0.

Logical Instructions

Shift instructions move bits left or right by a specified number of positions. The format is op dest, src, count, where op is the operation, dest is the destination register, src is the source register, and count is the number of positions to shift.

• shamt: Shift amount, the number of positions to shift.
• Shift Right Arithmetic (sra) preserves the sign bit during right shifts. For example, 1101 >> 1 becomes 1110.
• Every shift operation is like multiplying or dividing by 2. For example, x << 2 is equivalent to x * 4.

Note: SLA (Shift Left Arithmetic) is equal to SLL (Shift Left Logical) in MIPS, hence it is not a separate MIPS instruction.

AND, OR, NOR, and XOR instructions perform bitwise logical operations. The format is op dest, src1, src2, where op is the operation, dest is the destination register, and src1 and src2 are the source registers.

• XOR (Exclusive OR): Sets the destination bit to 1 if only one of the source bits is 1.

Bitwise Operations:

• AND: 0011 & 1010 = 0010 -> Mask bits in a word, i.e., select some bits, clear others to 0.
• OR: 0011 | 1010 = 1011 -> Include bits in a word, i.e., set some bits to 1, leave others unchanged.
• NOR: ~(0011 | 1010) = 0100 -> Negate the OR operation, i.e., set bits to 1 where both inputs are 0.
• XOR: 0011 ^ 1010 = 1001 -> Exclusive OR, i.e., set bits to 1 where only one input bit is 1.

Pseudo-Instructions (MIPS does not have direct instructions for these operations):

• not $d, $s: Equivalent to nor $d, $s, $zero or nor $d, $s, $s (logical NOT operation) -> not $s0, $s1

Example

• C code: p = (q & r) | (s << 2); ($s1 holds q, $s2 holds r, $s3 holds s)
• MIPS assembly:
  • and $t0, $s1, $s2 (q & r -> $t0)
  • sll $t1, $s3, 2 (s << 2 -> $t1)
  • or $s0, $t0, $t1 ((q & r) | (s << 2) -> $s0)

Quick Quiz:

• a. andn $t1, $s2, $s3 (ANDN: Set to 1 if $s2 AND NOT $s3)
• b. xnor $t1, $s2, $s3 (XNOR: Set to 1 if both are equal or NOT XOR)

nor $t1, $s3, $zero  # NOT $s3
and $t1, $s2, $t1    # $s2 AND NOT $s3

xor $t1, $s2, $s3    # $s2 XOR $s3
nor $t1, $t1, $zero  # NOT ($s2 XOR $s3)

Quick Quiz:

• a. A = B & C[0];
• b. A = A ? B : C[0];

lw $t0, 0($s1)  # Load C[0] into $t0
and $t1, $t2, $t0  # B & C[0] -> A

beq $t1, $zero, Else  # If A == 0, go to Else
add $t1, $zero, $t2  # A = B
beq $zero, $zero, End  # Skip Else
Else: lw $t1, 0($s1)  # Load C[0] into $t0
End:

xor $s0, $s0, $s1  # $s0 <- $s0 XOR $s1
xor $s1, $s0, $s1  # $s1 <- ($s0 XOR $s1) XOR $s1 = $s0
xor $s0, $s0, $s1  # $s0 <- ($s0 XOR $s1) XOR [($s0 XOR $s1) XOR $s1] = $s1

Constants

To add a constant loaded from memory to a register, use the lw instruction to load the constant into a register. For example, to add a constant 4 to register $s3:

.data
AddConstant4: .word 4 # Define the constant 4 in memory

.text
main:
    lw $t0, AddConstant4 # Load the constant 4 from memory into $t0
    add $s3, $s3, $t0    # Add the value in $t0 to $s3

This approach requires a memory access, which can be slow. To optimize, use immediate instructions to load constants directly into registers without memory access:

addi $s3, $s3, 4 # Add the constant 4 to $s3

Immediate instructions use a 16-bit immediate value, which is extended to 32 bits. The immediate value can be positive or negative with a range of $-2^{15}$ to $2^{15}-1$.

• For logical instructions like andi, the immediate value is zero-extended.
• For arithmetic instructions like addi, the immediate value is sign-extended, where positive values are padded with zeros and negative values are padded with ones.

MIPS provides lui (Load Upper Immediate) to load the upper 16 bits of a 32-bit constant into a register. For example, to load the constant 0x1234 into register $t0:

lui $t0, 0x1234 # Load the upper 16 bits of 0x1234 into $t0

To load the constant 0x12345678 into register $t0, you need two instructions, where ori (OR Immediate) loads the lower 16 bits:

lui $t0, 0x1234       # Load upper 16 bits
ori $t0, $t0, 0x5678  # Load lower 16 bits

lui $s0, 0x003D       # Load the upper 16 bits: 0000 0000 0011 1101 
ori $s0, $s0, 0x0900  # Load the lower 16 bits: 0000 1001 0000 0000

Quick Quiz:

• a. $t0 = 0x55555555, $t1 = 0x12345678
• b. $t0 = 0xBEADFEED, $t1 = 0xDEADFADE

1. What is the value of $t2 after the following instructions?

sll $t2, $t0, 4 
or $t2, $t2, $t1

2. What is the value of $t3 after the following instructions?

sll $t2, $t0, 4
andi $t3, $t2, -1 # -1 = 0xFFFFFFFF

Assembly and Machine Code

In MIPS assembly, there are three types of instruction formats: R-type, I-type, and J-type.

Instruction Formats

• R-type: op rs rt rd shamt funct
• I-type: op rs rt address/immediate
• J-type: op 26-bit address

A Field is a part of a continuous sequence of bits in a machine instruction that represents a register, immediate value, or address.

See: Opcode (opens in a new tab)

Steps to Translate Instructions to Machine Code:

1. Determine the instruction format (R-type, I-type, or J-type).
2. Draw the corresponding machine instruction format.
3. Look up the table for opcode, funct code, and register numbers.

Opcode vs. Funct:

• Opcode: Specifies the operation type (e.g., arithmetic, logical, memory access).
• Funct: Specifies the exact operation within the opcode category (e.g., add, sub, and, or).

OPCode Table

Function Code Table

Register Table

Example:

For the add instruction:

• R-type: add $t1, $t2, $t3
  • op = 000000 (All R-type instructions use a 000000 opcode)
  • rs = $t2 = 01010
  • rt = $t3 = 01011
  • rd = $t1 = 01001
  • shamt = 00000 (not used)
  • funct = 100000 (add)

The machine code for add $t1, $t2, $t3 is:

000000 01010 01011 01001 00000 100000

Machine Language refers to instructions in numerical format that a computer's CPU can execute directly. A sequence of these instructions is called Machine Code.

In MIPS assembly, the order of register fields in machine code is different from the assembly code. In assembly, the format is op rd rs rt, while in machine code, the format is op rs rt rd.

Jump and Branch Addressing

MIPS differentiates between jump and branch instructions based on their address fields:

• Jump instructions use a 26-bit address field.
• Branch instructions use a 16-bit address field and employ PC-relative addressing, where the address is relative to the program counter (PC). The PC holds the address of the current instruction, allowing the CPU to branch within the range (-2^15) to (2^15-1) words or (-2^17) to (2^17-1) bytes from the current instruction, which is (131072) in decimal and (0x20000) in hexadecimal.

Example

Assembly Code:

Loop: 
    sll $t1, $s3, 2
    add $t1, $t1, $s6
    lw $t0, 0($t1)
    bne $t0, $s5, Exit
    addi $s3, $s3, 1
    j Loop
Exit:

Machine Code (Decimal):

80000: 0 0 19 9 2 0    # sll $t1, $s3, 2
80004: 0 9 22 9 0 32   # add $t1, $t1, $s6
80008: 35 9 8 0        # lw $t0, 0($t1)
80012: 5 8 21 2        # bne $t0, $s5, Exit
80016: 8 19 19 1       # addi $s3, $s3, 1
80020: 2 20000         # j Loop
80024: ...

Assuming the loop starts at memory location 80000 in decimal.

To relatively address the Loop and Exit labels in branch instructions, we need to calculate the offset from the current instruction. Positive values are forward, and negative values are backward. In this example, when the branch condition is met, the program jumps to Exit, which is 2 instructions ahead (in machine code) from the current instruction. Hence, the 16-bit address field in the bne instruction is +2.

For addressing in the j instruction, the 26-bit address field is sufficient. MIPS systems have 2^32 bytes of memory (4GB) divided into 16 blocks of 256MB each. All programs should reside within a block. For instructions in the same block, the first 4 bits of the address remain the same. As all instructions are 4 bytes aligned, the last 2 bits of the address are always 0. Thus, the 26-bit (32 - 4 - 2) address field is enough to address instructions within the same block.

For instance, (80000)₁₀ in 32-bit binary is (0000 0000 0000 0001 0011 1000 0100 0000)₂. Removing the last 2 bits and the first 4 bits, we get (0000 0000 0000 0100 1110 0010 00)₂ = (20000)₁₀.

Long Distance Branch Addressing

In MIPS, branch instructions like beq and bne use PC-relative addressing, allowing them to jump within a range of (-2^15) to (2^15-1) words from the current instruction. This range is generally sufficient, but if the branch target is outside this range, the assembler handles it by transforming the branch into a combination of an inverted branch followed by a jump instruction.

Example:

beq $s0, $s1, Label

If Label is too far for the beq instruction to reach, the assembler converts it to:

bne $s0, $s1, Next
j Label
Next:

Explanation:

• bne $s0, $s1, Next: This instruction branches to Next if $s0 is not equal to $s1, effectively inverting the original branch condition.
• j Label: If $s0 equals $s1, the beq condition is satisfied, so the program continues to this j instruction, which can reach the distant Label.
• Next:: The point to continue execution if the branch was not taken.

Reassembly

Steps to Translate Machine Code back to Assembly:

1. Identify the instruction format by looking at the first 6 bits (opcode).
2. Split the instruction into fields based on the format.
3. Look up the opcode, funct code, and register numbers in the table.

Example:

• Bits: 0000 0000 1010 1111 1000 0000 0010 0000
• Opcode: 000000 (R-type)
• rs: 00101, rt: 01111, rd: 10000, shamt: 00000, funct: 100000
• add $s0, $a1, $t7

Quick Quiz: a. Op=0, rs=1, rt=2, rd=3, shamt=0, funct=32 b. Op =0x2B, rs=0x10, rt=0x5, const=0x4

here: beq $s0, $s2, there
     ...
there: add $s0, $s0, $s0

here: bne $s0, $s2, skip
      j there
skip: ...
there: add $s0, $s0, $s0

Procedure Call

Steps for Procedure Call: Assume we have two procedures A and B where A calls B.

1. Set Arguments: A places arguments in registers $a0 to $a3.
2. Jump and Link: A executes jal B, saving the return address in $ra.
3. Save Registers: B saves necessary registers.
4. Execute B: B performs its tasks.
5. Set Return Values: B places return values in $v0 and $v1.
6. Restore Registers: B restores saved registers.
7. Return to Caller: B executes jr $ra to return to A.

Review

• $a0-$a3: Argument registers for passing parameters.
• $v0-$v1: Value registers for returning results.
• $ra: Return address register for storing the address to return to after a procedure call.
• jal: Jump and link instruction to call a procedure and store the return address in $ra, where the link is the address of the next instruction after the jal, i.e. PC + 4.
• jr: Jump register instruction to return to the address stored in a register.

Caller place arguments in $a0-$a3 and call the procedure using jal. The Callee saves the return address in $ra, performs its tasks, and returns the result in $v0-$v1. The Caller can access the result from $v0-$v1 after the procedure call.

$sp (stack pointer) is used to store Callee's registers and local variables. The stack grows downwards, and $sp points to the last used memory location. Thus, when data is pushed onto the stack, $sp is decremented, and vice versa.

int leaf_example (int g, h, i, j) {
    int f;
    f = (g + h) - (i + j);
    return f;
}

leaf_example:
    addi $sp, $sp, -4        # Save $s0 on stack
    sw $s0, 0($sp)           # Save $s0 on stack
    add $t0, $a0, $a1        # $t0 = g + h
    add $t1, $a2, $a3        # $t1 = i + j
    sub $s0, $t0, $t1        # $s0 = (g + h) - (i + j)
    add $v0, $s0, $zero      # Set return value in $v0
    lw $s0, 0($sp)           # Restore $s0
    addi $sp, $sp, 4         # Restore stack pointer
    jr $ra                   # Return to caller

Parallelism and Synchronization

Data Race occurs when multiple threads concurrently access shared data, with at least one write operation, leading to unpredictable results. For instance:

To ensure mutual exclusion, where only one processor can access a critical section at a time, locks can be used.

Processors with an atomic swap operation allow programmers to create locks with proper semantics. An atomic swap ensures that the processor reads a location and sets it to a locked value in a single bus operation, preventing other processors from accessing the location until the operation is complete.

MIPS does not include an atomic swap instruction but provides Load Linked (LL) and Store Conditional (SC) instructions to simulate this behavior.

Atomic Exchange Example ($s1 and s4):

try: add $t0, $zero, $s4 # copy value of s4 to t0
     ll $t1, 0($s1)      # load linked value from s1 to t1
     sc $t0, 0($s1)      # 1 if load linked value is still in s1 (equal to t1), 0 otherwise
     beq $t0, $zero, try # if sc failed, try again
     add $s4, $zero, $t1 # succeeded, copy t1 value to s4

try:  MOV R3, R4
      MOV R6, R7
      LL R2, 0(R2)
      LL R5, 0(R1)
      SC R3, 0(R1)
      SC R6, 0(R1)
      BEQZ R3, try
      MOV R4, R2
      MOV R7, R5

try:
      MOV R3, R4
      LL R8, 0(R2)
      SC R3, 0(R2)
      BEQZ R3, try
      MOV R4, R8
try2: 
      MOV R6, R7
      LL R5, 0(R1)
      SC R6, 0(R1)
      BEQZ R6, try2
      MOV R7, R5

MIPS Addressing Modes

Data Addressing Modes

1. Immediate Addressing: The operand is in the instruction 16-bit immediate field.
   • Example: addi, andi, ori
2. Register Addressing: The operand is in a register.
   • Example: add, sub, and, or
3. Base or Displacement Addressing: The operand is at the memory location specified by a base register and a 16-bit constant in the instruction.
   • Example: lw, sw, lb, sb Instruction Addressing Modes
4. PC-relative Addressing: The target address is calculated relative to the current PC and a 16-bit constant in the instruction.
   • Example: beq, bne
5. Pseudodirect Addressing: The target address is calculated by shifting the 26-bit constant in the instruction left by 2 bits and combining it with the upper 4 bits of the current PC. The lower 2 bits are always 00.
   • Example: j, jal

Design Principles

1. Simplicity Favors Regularity: 1. Make all instructions the same length. 2. 3 operand instructions. 3. Register fields in the same place.
2. Smaller is Faster: 1. Only 32 registers so CPU can access them quickly. 2. Lower energy consumption.
3. Good Design Demands Good Compromise: Use 3 instruction formats (R, I, J) to provide longer immediate values and jump addresses.
4. Make the Common Case Fast: 1. PC-relative addressing for branches. 2. Immediate addressing for constants.

RISC vs. CISC

Different Types of Instruction Sets

1. Accumulator:

   • Only one operand.
   • The other operand is implicitly the accumulator.
   • Accumulator-based instructions have less memory efficiency.

2. Memory-Memory:

   • Every instruction has three operands.
   • All operands can be in memory.
   • Memory-based instructions are not efficient due to their extensive use of memory.

3. Stack:

   • Zero operand (implicitly zero-operand instructions).
   • Operations occur at the top of the stack.
   • Push and pop operations are used to manage the stack.
   • Each instruction implicitly accesses the top elements of the stack.

4. Load-Store:

   • Each instruction has three operands.
   • Operands are from registers.
   • Separate load and store operations are used for memory access.
   • The result of the operation is stored in the registers.

ARM vs. MIPS