09.5 Assembly Programming

Lecture from: 23.03.2023 | Video: YT

This lecture transitions us into the practical realm of Assembly Programming, specifically focusing on the LC-3 and MIPS architectures we’ve been studying. While Lecture 9a wrapped up our in-depth exploration of ISA and microarchitecture concepts, Lecture 9b aims to equip you with the foundational knowledge needed to write, debug, and understand assembly language programs. This lecture is particularly relevant for your lab exercises, providing hands-on guidance for assembly-level programming.

Agenda

Today’s lecture will cover key aspects of assembly programming, including:

Programming Constructs: Understanding the fundamental building blocks of programs: sequential, conditional, and iterative constructs.
Debugging: Principles and techniques for identifying and removing errors in assembly programs.
Conditional Statements and Loops in MIPS Assembly: Practical examples of implementing conditional logic and loops using MIPS assembly instructions.
Arrays in MIPS Assembly: How to work with arrays, including accessing and manipulating array elements at the assembly level.
Function Calls: Conventions and mechanisms for implementing function calls, arguments passing, and return values in assembly.
The Stack: The crucial role of the stack in managing function calls and local variables.

Recall: Von Neumann Model, LC-3, and Instruction Cycle

Before diving into assembly programming specifics, let’s briefly recall the key components of the Von Neumann model, the LC-3 architecture, and the Instruction Cycle, as these form the underlying foundation for understanding assembly-level program execution.

Von Neumann Model: The architecture with a unified memory space for instructions and data, sequential instruction execution, and core components like CPU, memory, and I/O.
LC-3: Our simplified example Von Neumann machine, providing a concrete platform for learning assembly programming concepts.
Instruction Cycle: The fetch-decode-evaluate address-fetch operands-execute-store result cycle that governs instruction processing in Von Neumann architectures.

Our First LC-3 Program: Adding Integers in a Loop

Let’s begin with a practical example: writing an LC-3 program to add 12 integers stored in memory.

Algorithm Flowchart

To approach this programming task systematically, we start with a flowchart outlining the algorithm:

Initialization:
- Initialize R1 to point to the starting address of the integers (0x3100).
- Initialize R3 to 0 (accumulator for the sum).
- Initialize R2 to 12 (counter for the number of integers).
Loop Condition Check:
- Check if R2 is equal to 0. If yes, the loop terminates (all integers added).
Loop Body (if R2 != 0):
- Load the integer at the address pointed to by R1 into R4 (R4 <- M[R1]).
- Add R4 to R3 (R3 <- R3 + R4).
- Increment R1 to point to the next integer’s address (Increment R1).
- Decrement R2 ( Decrement R2).
Loop Iteration: Repeat from step 2.
Output: (After loop termination) Output the result (sum) from R3 to the monitor.
Halt: Stop the program.

LC-3 Assembly Program

Translating the algorithm flowchart into LC-3 assembly code results in the following program:

This program effectively implements the algorithm using LC-3 assembly instructions, demonstrating the use of conditional branches (BRz, BRnzp) to create a loop.

TRAP Instructions: Interacting with the Operating System

The program utilizes TRAP instructions for input and output operations. TRAP instructions in LC-3 invoke Operating System (OS) service calls, allowing the program to interact with external devices like the keyboard and monitor.

TRAP 0x23: Reads a character from the keyboard and stores it in register R0.
TRAP 0x21: Outputs the character in register R0 to the monitor.
TRAP 0x25: Halts the program execution.

Debugging Assembly Programs: Techniques and Tools

Debugging is an essential skill for assembly programmers. It involves systematically identifying and removing errors in programs.

Debugging Process

The debugging process typically involves:

Tracing the Program: Following the sequence of executed instructions and observing the results of each instruction to understand the program’s behavior.
Modular Debugging: Partitioning the program into smaller modules or sections and testing/examining each part in isolation to pinpoint errors.

Interactive Debugging Operations

Interactive debuggers provide essential operations for analyzing and correcting machine code programs:

Deposit Values: Ability to manually set values in memory and registers to test specific code segments in isolation.
Execute Instruction Sequences:
- RUN Command: Execute the program until a HALT instruction or a predefined breakpoint is encountered.
- STEP N Command: Execute a fixed number (N) of instructions step-by-step to closely observe program flow.
Stop Execution (Breakpoints):
- SET BREAKPOINT Command: Halt program execution at a specific instruction address to examine the program state at that point.
Examine Memory and Registers: Inspect the contents of memory locations and registers at any point during program execution to track data flow and program state.

Example: Debugging a Buggy Multiply Program

Let’s consider a buggy LC-3 program designed to multiply two numbers (R4 and R5). The program produces an incorrect result (40 instead of 30 for 10 * 3). To debug this, we can:

Annotate Instructions: Add comments to each instruction to understand its intended purpose.
Examine Register Contents: Step through the program instruction by instruction, recording the values of relevant registers (PC, R2, R4, R5) after each instruction’s execution to track data flow and identify deviations from expected behavior.
Breakpoints: Use breakpoints to pause execution at specific points (e.g., at the beginning of the loop) to examine program state at key iterations.

By carefully tracing the register values and using breakpoints, we can pinpoint the error: the branch condition codes were set incorrectly, causing the loop to iterate one extra time. The conditional branch should have been BRp (branch if positive) instead of BRzp (branch if zero or positive) to ensure correct loop termination when R5 becomes zero.

Corner Cases and Thorough Testing

Debugging should also involve testing corner cases, unusual or boundary conditions that the programmer might overlook. In the multiply example, testing with R5 = 0 as input reveals another flaw in the program’s logic, highlighting the importance of comprehensive testing to uncover potential issues.

Conditional Statements and Loops in MIPS Assembly

Now, let’s shift our focus to implementing conditional statements and loops in MIPS assembly, demonstrating how these fundamental programming constructs are realized at the assembly level.

If Statement in MIPS Assembly

To implement an if statement in MIPS assembly, we use conditional branch instructions like bne (branch if not equal).

High-Level Code (C-like):

if (i == j)
  f = g + h;
f = f - i;

MIPS Assembly:

# $s0 = f, $s1 = g, $s2 = h, $s3 = i, $s4 = j
 
    bne $s3, $s4, L1    # Branch to L1 (else part) if i != j
    add $s0, $s1, $s2   # f = g + h (if part: executed if i == j)
L1: sub $s0, $s0, $s3   # f = f - i (executed unconditionally)

The bne instruction checks if registers $s3 (i) and $s4 (j) are not equal. If they are not equal, the program branches to label L1 (representing the “else” path, though in this simplified example, L1 simply continues execution). If they are equal, the add instruction (representing the “if” block) is executed.

If-Else Statement in MIPS Assembly

For if-else statements, we combine conditional branches with unconditional jumps (j instruction) to skip the “else” block when the “if” condition is true.

High-Level Code (C-like):

if (i == j)
  f = g + h;
else
  f = f - i;

MIPS Assembly:

# $s0 = f, $s1 = g, $s2 = h, $s3 = i, $s4 = j
 
    bne $s3, $s4, L1    # Branch to L1 (else part) if i != j
    add $s0, $s1, $s2   # f = g + h (if part: executed if i == j)
    j done              # Unconditional jump to skip else part
L1: sub $s0, $s0, $s3   # f = f - i (else part: executed if i != j)
done:                  # Label after if-else block

Here, if bne condition (i != j) is true, the program jumps to label L1 (the “else” block). If the condition is false (i == j), the “if” block (add) is executed, followed by an unconditional jump (j done) to skip the “else” block and proceed to the done label.

While Loop in MIPS Assembly

Implementing while loops in MIPS assembly typically involves a conditional branch to check the loop condition and an unconditional jump to reiterate the loop.

High-Level Code (C-like):

// determines the power of 2 equal to 128
int pow = 1;
int x = 0;
while (pow != 128) {
  pow = pow * 2;
  x = x + 1;
}

MIPS Assembly:

# $s0 = pow, $s1 = x
 
    addi $s0, $0, 1    # Initialize pow = 1
    add $s1, $0, $0     # Initialize x = 0
    addi $t0, $0, 128   # Load loop termination value (128) into $t0
while: beq $s0, $t0, done # Check loop condition: if pow == 128, exit loop
    sll $s0, $s0, 1    # pow = pow * 2 (shift left logical by 1)
    addi $s1, $s1, 1   # x = x + 1 
    j while             # Unconditional jump back to loop beginning
done:                  # Label after loop termination

The beq instruction checks the while loop condition (pow != 128). If pow equals 128, the program branches to done (exiting the loop). Otherwise, the loop body (multiply pow by 2, increment x) is executed, followed by an unconditional jump (j while) back to the beginning of the loop to re-evaluate the condition.

For Loop in MIPS Assembly

For loops, similar to while loops, are also implemented using conditional branches and jumps in MIPS assembly.

High-Level Code (C-like):

// add the numbers from 0 to 9
int sum = 0;
int i;
for (i = 0; i != 10; i = i+1) 
{
  sum = sum + i;
}

MIPS Assembly:

# $s0 = i, $s1 = sum
 
    addi $s1, $0, 0    # Initialize sum = 0
    add $s0, $0, $0     # Initialize i = 0
    addi $t0, $0, 10    # Load loop limit (10) into $t0
for: beq $s0, $t0, done # Check loop condition: if i == 10, exit loop
    add $s1, $s1, $s0   # sum = sum + i
    addi $s0, $s0, 1   # i = i + 1
    j for             # Unconditional jump back to loop beginning
done:                  # Label after loop termination

The MIPS assembly code for the for loop closely mirrors the while loop structure, using beq to check the loop termination condition (i != 10) and j for to jump back to the loop’s beginning.

For Loop Using SLT (Set Less Than)

The slt (set less than) instruction can be used to implement more complex loop conditions, such as “less than” comparisons.

High-Level Code (C-like):

// add the powers of 2 from 1 to 100
int sum = 0;
int i;
for (i = 1; i < 101; i = i*2) 
{
  sum = sum + i;
}

MIPS Assembly:

# $s0 = i, $s1 = sum
 
    addi $s1, $0, 0    # Initialize sum = 0
    addi $s0, $0, 1    # Initialize i = 1
    addi $t0, $0, 101   # Load loop limit (101) into $t0
loop: slt $t1, $s0, $t0 # $t1 = 1 if i < 101, else $t1 = 0 (set less than)
    beq $t1, $0, done # Branch to done if $t1 == 0 (i >= 101, loop exit)
    add $s1, $s1, $s0   # sum = sum + i
    sll $s0, $s0, 1    # i = i * 2 (shift left logical by 1)
    j loop             # Unconditional jump back to loop beginning
done:                  # Label after loop termination

The slt instruction sets register $t1 to 1 if $s0 (i) is less than $t0 (101), and 0 otherwise. The beq instruction then checks if $t1 is equal to 0, effectively implementing the “less than” loop condition.

Arrays in MIPS Assembly

Arrays in MIPS assembly require careful address calculation and register usage.

Accessing Arrays

Accessing array elements in MIPS involves:

Loading Base Address: The starting memory address of the array must be loaded into a register. Since MIPS does not have a single instruction to load a 32-bit immediate address, we use a combination of lui (load upper immediate) and ori (OR immediate) to construct the full 32-bit base address.
Calculating Element Address: To access a specific array element (e.g., array[index]), the element’s memory address is calculated by adding an offset to the base address. The offset is determined by the index and the size of each array element (word size in MIPS, which is 4 bytes).

Code Example: Array Manipulation in MIPS

This example demonstrates how to access and manipulate array elements in MIPS assembly:

High-Level Code (C-like):

int array[5];
array[0] = array[0] * 2;
array[1] = array[1] * 2;

MIPS Assembly:

# array base address = $s0
# Initialize $s0 to 0x12348000
lui $s0, 0x1234    # Load upper 16 bits of base address
ori $s0, $s0, 0x8000 # Load lower 16 bits of base address
 
lw $t1, 0($s0)     # Load array[0] into $t1 (offset 0)
sll $t1, $t1, 1     # $t1 = $t1 * 2 (shift left logical by 1)
sw $t1, 0($s0)     # Store modified value back to array[0]
 
lw $t1, 4($s0)     # Load array[1] into $t1 (offset 4 bytes = 1 word)
sll $t1, $t1, 1     # $t1 = $t1 * 2
sw $t1, 4($s0)     # Store modified value back to array[1]

The assembly code first initializes register $s0 to hold the base address of the array. Then, it demonstrates accessing array[0] and array[1] using the base+offset addressing mode (lw $t1, 0($s0) and lw $t1, 4($s0)), performing a multiplication by 2 (using sll), and storing the modified values back to memory (sw).

Function Calls in MIPS and LC-3: Conventions and Stack

Function calls are essential for modularity and code reuse. MIPS and LC-3, like most architectures, follow specific conventions for function calls to ensure proper program execution.

Function Call Conventions

Caller Responsibilities:
- Pass Arguments: The calling function (caller) must pass arguments to the called function (callee) in designated registers or memory locations.
- Jump to Callee: The caller uses a jump instruction to transfer control to the callee’s code.
Callee Responsibilities:
- Perform Procedure: The callee executes its designated task.
- Return Result: The callee places the return value (if any) in a designated register.
- Return to Caller: The callee uses a jump instruction to return control back to the caller, specifically to the instruction after the function call.
- Preserve Caller’s State: The callee must ensure it does not overwrite registers or memory locations that the caller expects to remain unchanged after the function call. This is crucial for maintaining program correctness.

Call and Return Procedures in MIPS and LC-3

Call Procedure:
- MIPS: jal (Jump and Link) instruction is used to call a function. jal jumps to the callee’s address and automatically saves the return address (address of the instruction after jal) in the return address register ($ra).
- LC-3: JSR (Jump to Subroutine) and JSRR instructions are used for function calls, saving the return address in register R7.
Return from Procedure:
- MIPS: jr $ra (Jump Register) instruction is used to return from a function. jr $ra jumps to the address stored in the return address register ($ra), effectively returning control to the caller.
- LC-3: RET (Return from Subroutine) instruction is used, which is essentially a specialized jump register instruction that jumps to the address stored in R7.

Argument and Return Value Conventions

Argument Values (MIPS): Registers $a0 - $a3 are conventionally used to pass the first four arguments to a function.
Return Value (MIPS): Register $v0 is conventionally used to return a single value from a function.

Simple Function Call Example

A simple example illustrates the basic function call and return sequence in MIPS assembly:

High-Level Code (C-like):

int main() {
  simple(); 
  a = b + c; 
}
 
void simple() {
  return; 
}

MIPS Assembly:

0x00400200 main: jal simple   # Call simple function, save return address in $ra
0x00400204 add $s0,$s1,$s2 # Instruction after function call
 
...
 
0x00401020 simple: jr $ra    # Return from simple function (jump to address in $ra)

Code Example: Function Call with Arguments and Return Value

A more complete example demonstrates argument passing, return values, and the use of call and return instructions in MIPS assembly.

The Stack: Managing Register Saving and Function Calls

The Stack is a crucial memory area used to manage function calls, local variables, and register saving. It operates as a Last-In-First-Out (LIFO) queue.

Stack Pointer ($sp): A dedicated register that points to the “top” of the stack (the most recently added item). In MIPS, the stack grows downwards in memory.

Need for the Stack: Register Preservation

The stack is essential for handling situations where a function (callee) might overwrite registers that are also being used by the calling function (caller). To prevent data corruption, the stack is used to temporarily save register values before a function call and restore them upon function return.

Code Example: Stack Usage for Register Saving

This MIPS assembly code example demonstrates how the stack is used to save and restore registers ($s0, $t0, $t1) within a function (diffofsums) to adhere to function call conventions and avoid overwriting the caller’s register values.

Register Saving Conventions: Temporary vs. Saved Registers

MIPS, and many other ISAs, employ register saving conventions to optimize function calls and reduce unnecessary saving and restoring of registers.

Temporary Registers ($t0-$t9): These registers are designated as nonpreserved or caller-saved registers. The callee function is not obligated to save and restore these registers. The caller should not assume that the values in temporary registers will be preserved across function calls.
Saved Registers ($s0-$s7): These registers are designated as preserved or callee-saved registers. If a callee function intends to use saved registers, it must save their values onto the stack at the beginning of the function and restore them before returning to the caller. This ensures that the caller can rely on the values in saved registers remaining unchanged after a function call.

These conventions streamline function calls and improve code efficiency by reducing the overhead of unnecessary register saving and restoring. Programmers and compilers must adhere to these conventions to ensure correct program behavior, especially when dealing with function calls and register usage across function boundaries.

Lecture Summary

Today’s lecture provided a comprehensive introduction to Assembly Programming, covering:

Programming Constructs: Sequential, conditional, and iterative constructs as fundamental building blocks.
Debugging: Essential debugging principles and interactive debugging operations.
Conditional Statements and Loops in MIPS Assembly: Practical implementation examples using conditional branches.
Arrays in MIPS Assembly: Techniques for array access and manipulation.
Function Calls: Conventions for function calls, argument passing, return values, and the crucial role of the stack in register management.

CS Notes

Explorer