UCCD1133
Introduction to Computer Organisation and Architecture
Chapter 4
Computer Architecture and Organisation Fundamental
Slides adapted from http://booksite.elsevier.com
Page <1>
Disclaimer
❑ This slide may contain copyrighted material of which has not been specifically authorized by the copyright owner. The use of copyrighted materials are solely for educational purpose. If you wish to use this copyrighted material for other purposes, you must first obtain permission from the original copyright owner.
Page <2>
Chapter 4 – 4
MIPS PROGRAMMING (PART 2)
ARRAYS, STACK, FUNCTION CALL & PSEUDOINSTRUCTIONS
Page <3>
Arrays
• Access large amounts of similar data
• Index: access each element
• Size: number of elements
• Example: 5-element array
• Base address = 0x12348000
(address of first element, array[0])
• First step in accessing an array: load base address into a register
0x12340010 0x1234800C 0x12348008 0x12348004 0x12348000
array[4]
array[3]
array[2]
array[1]
array[0]
Page <4>
Accessing Arrays
// C Code
int array[5];
array[0] = array[0] * 2;
array[1] = array[1] * 2;
Page <5>
Accessing Arrays
// C Code
int array[5];
array[0] = array[0] * 2;
array[1] = array[1] * 2;
# MIPS assembly code
# $s0 = array base address lui $s0, 0x1234
ori $s0, $s0, 0x8000
lw $t1, 0($s0) sll $t1, $t1, 1 sw $t1, 0($s0)
lw $t1, 4($s0)
sll $t1, $t1, 1
sw $t1, 4($s0)
Recall: Generating constants
# 0x1234 in upper half of $s0 # 0x8000 in lower half of $s0
# $t1 = array[0] #$t1=$t1*2 # array[0] = $t1
# $t1 = array[1] #$t1=$t1*2 # array[1] = $t1
Page <6>
Arrays using For Loops
// C Code
int array[1000]; int i;
for (i=0; i < 1000; i = i + 1) array[i] = array[i] * 8;
# MIPS assembly code
# $s0 = array base address, $s1 = i
Page <7>
Arrays using For Loops
# MIPS assembly code
# $s0 = array base address, $s1 = i
# initialization code
lui $s0, 0x23B8
ori $s0, $s0, 0xF000 addi $s1, $0, 0
addi $t2, $0, 1000
loop:
slt $t0, $s1, $t2 beq $t0, $0, done sll $t0, $s1, 2 add $t0, $t0, $s0 lw $t1, 0($t0) sll $t1, $t1, 3 sw $t1, 0($t0) addi $s1, $s1, 1
j loop
done:
# $s0 = 0x23B80000 #$s0= 0x23B8F000 #i=0
# $t2 = 1000
#i<1000?
# if not then done
# $t0 = i * 4 (byte offset) # address of array[i]
# $t1 = array[i]
# $t1 = array[i] * 8
# array[i] = array[i] * 8 # i= i+1
# repeat
Page <8>
Bytes and Characters
• English characters are often represented by bytes.
• The C language uses the type char to represent a byte or character.
• American Standard Code for Information Interchange (ASCII) assigns each text character a unique byte value.
• For example, S = 0x53, a = 0x61, A = 0x41
• Lower-case and upper-case differ by 0x20 (32)
• A series of characters is called a string.
Page <9>
Cast of Characters
Page <10>
The Stack
• Memory used to temporarily save local variables within a function.
• Follow last-in-first-out (LIFO) queue, but grows down.
• Expands: uses more memory when more space needed
• Contracts: uses less memory when the space is no longer needed
• The stack pointer, $sp, is a special MIPS register that points to the top of the stack (most recently allocated space)
Address Data 7FFFFFFC
7FFFFFF8 7FFFFFF4 7FFFFFF0
Address
7FFFFFFC 7FFFFFF8 7FFFFFF4 7FFFFFF0
Data
12345678
12345678
AABBCCDD
11223344
$sp
$sp
Page <11>
Function Calls
• A procedure or function is one tool programmers use to structure programs. • Easier to understand
• Allow code to be reused.
• Parameters act as an interface between the caller and callee, since they can pass values and return results.
• Caller: calling function (in this case, main) • Callee: called function (in this case, sum)
• Caller:
• passes arguments to callee • jumps to callee
• Callee:
• performs the function
• returns result to caller
• returns to point of call
• must not overwrite registers or
memory needed by caller
C Code
void main() {
int y;
y = sum(42, 7);
…
}
int sum(int a, int b)
{
return (a + b);
}
Page <12>
Function Calls
A function call must follow these six steps:
1. Put parameters in a place (registers) where the callee can access them.
2. Transfer control to the callee.
3. Acquire the storage resources needed for the callee.
4. Perform the desired task.
5. Put the result value in a place (registers) where the caller can access it.
6. Return to place of call.
Page <13>
MIPS Function Conventions
• Arguments: $a0 – $a3
• Four argument registers in which to pass parameters
• Return value: $v0
• Two value registers in which to return values
• Return address: $ra
• The return address register to return to the point of origin
• Call Function: jump and link (jal)
• A special instruction for function call
• Jumps to an address and simultaneously saves the address of the following instruction (PC + 4) in register $ra.
• Example: jal FunctionAddress
• Return from function: jump register (jr)
• Needed for function return or switch statements. • Example: jr $ra
Copies $ra to program counter. • Program Counter (PC)
• A special register to hold the address of the current instruction being executed. Page <14>
Example
C Code
int main() {
int y;
…
y = diffofsums(2, 3, 4, 5); // 4 arguments …
}
int diffofsums(int f, int g, int h, int i) {
}
int result;
result = (f + g) – (h + i); return result;
// return value
Page <15>
Example
MIPS assembly code
# $s0 = y
main: …
# argument 0 = 2
# argument 1 = 3
# argument 2 = 4
# argument 3 = 5
# call Function
addi $a0, $0, 2
addi $a1, $0, 3
addi $a2, $0, 4
addi $a3, $0, 5
jal diffofsums
add $s0, $v0, $0 # y = returned value
…
# $s0 = result diffofsums:
add $t0, $a0, $a1 add $t1, $a2, $a3 sub $s0, $t0, $t1 add $v0, $s0, $0 jr $ra
# $t0 = f + g
# $t1 = h + i
# result = (f + g) – (h + i) # put return value in $v0
# return to caller
Page <16>
Example
MIPS assembly code
# $s0 = result diffofsums:
add $t0, $a0, $a1 add $t1, $a2, $a3 sub $s0, $t0, $t1 add $v0, $s0, $0 jr $ra
# $t0 = f + g
# $t1 = h + i
# result = (f + g) – (h + i) # put return value in $v0
# return to caller
* However, note that
• diffofsums overwrote 3 registers: $t0, $t1, $s0
• Called functions must have no unintended side effects
• diffofsums can use stack to temporarily store registers
Page <17>
Storing Register Values on the Stack
# $s0 = result
diffofsums:
addi $sp, $sp, -12 # make space on stack # to store 3 registers
sw $s0, 8($sp) sw $t0, 4($sp) sw $t1, 0($sp) add $t0, $a0, $a1 add $t1, $a2, $a3 sub $s0, $t0, $t1 add $v0, $s0, $0 lw $t1, 0($sp) lw $t0, 4($sp) lw $s0, 8($sp) addi $sp, $sp, 12 jr $ra
# save $s0 on stack # save $t0 on stack # save $t1 on stack # $t0 = f + g
# $t1 = h + i
# result = (f + g) – (h + i) # put return value in $v0
# restore $t1 from stack
# restore $t0 from stack
# restore $s0 from stack
# deallocate stack space
# return to caller
Page <18>
The stack during diffofsums Call
Address Data Address Data Address Data
FC $sp FC FC $sp F8 F8 F8
F4 F4 F4
F0 F0 $sp F0
(a) (b) (c)
?
?
$s0
$t0
$t1
?
Page <19>
stack frame
Registers
Preserved
Callee-Saved
Nonpreserved
Caller-Saved
$s0-$s7
$t0-$t9
$ra
$a0-$a3
$sp
$v0-$v1
stack above $sp
stack below $sp
❑ The stack above $sp is preserved simply by making sure the callee does not write above $sp.
Page <20>
Recursive Function Call
• A function that does not call others is called a leaf function • Example: diffofsums.
• A function that does call others is called a nonleaf function.
• More complicated.
• Need to save non-preserved registers on the stack before they call another function.
• A recursive function is a nonleaf function that calls itself.
• Example: factorial
• Factorial(n) = n(n-1)(n-2)…21
Page <21>
Recursive Function Call
High-level code
int factorial(int n) {
if (n <= 1)
return 1;
else
return (n * factorial(n-1)); }
Page <22>
Recursive Function Call
MIPS assembly code
0x90 factorial: addi
0x94 sw
0x98 sw
0x9C addi $t0, $0, 2
0xA0 slt $t0,$a0,$t0#a<=1?
0xA4 beq $t0, $0, else 0xA8 addi $v0, $0, 1 0xAC addi $sp, $sp, 8 0xB0 jr $ra
0xB4 else: addi $a0, $a0, -1 0xB8 jal factorial 0xBC lw $ra, 0($sp) 0xC0 lw $a0, 4($sp) 0xC4 addi $sp, $sp, 8 0xC8 mul $v0, $a0, $v0 0xCC jr $ra
# no: go to else # yes: return 1 # restore $sp
# return #n=n-1
# recursive call # restore $ra
# restore $a0
# restore $sp
# n * factorial(n-1)
# return
$sp, $sp, -8 # make room $a0, 4($sp) # store $a0 $ra, 0($sp) # store $ra
Page <23>
Stack During Recursive Call
Address Data
FC
F8
F4
F0 F0 F0
Address Data $sp FC
Address Data
$sp FC $sp$v0=6
$sp $a0 = 3 $v0= 3×2
$sp $a0 = 2 $v0= 2×1
$sp $a0 = 1 $v0 = 1
$a0 (0x3)
$ra
$a0 (0x2)
$ra (0xBC)
$a0 (0x1)
$ra (0xBC)
$a0 (0x3)
$ra
$a0 (0x2)
$ra (0xBC)
$a0 (0x1)
$ra (0xBC)
F8
F4 $sp F4
F8
EC EC
$sp EC E8 E8 E4 $sp E4 E0 E0
DC DC
E8 E4 E0 DC
Page <24>
Function Call Summary
• Caller
• Put arguments in $a0-$a3
• Save any needed registers ($ra, maybe $t0-t9) • jal callee
• Restore registers
• Look for result in $v0
• Callee
• Save registers that might be disturbed ($s0-$s7) • Perform function
• Put result in $v0
• Restore registers
• jr $ra
Page <25>
Pseudoinstructions
❑ MIPS defines pseudointructions that are not actually part of the instruction set but are commonly used by programmers and compilers.
❑ When converted to machine code, pseudoinstructions are translated into one or more MIPS instructions.
Pseudoinstruction
MIPS Instructions
li $s0, 0x1234AA77
lui $s0, 0x1234
ori $s0, $s0, 0xAA77
clear $t0
add $t0, $0, $0
move $s1, $s2
add $s2, $s1, $0
nop
sll $0, $0, 0
Page <26>