CS 230 – Introduction to Computers and Computer Systems
Module 2 – Assembly Language
CS 230 – Winter 2022 2-1
Copyright By PowCoder代写 加微信 powcoder
Overview l Assembly language: MIPS
l arithmetic operations (covered in Lecture 07) l data movement (covered in Lecture 07)
l conditional execution (covered in Lecture 08) l memory model (covered in Lecture 09)
l input and output (covered in Lecture 09) l arrays
l subroutines
CS 230 – Winter 2022 2-2
l Similar to arrays in high level languages
l way to store arbitrary but fixed length sequence of values (i.e. bit sequences)
l values in array called “elements” or “items”
l elementsappearinsequentialpositionsinmemory
l two components:
l addressoffirstelement
l numberofelements
l called “length”, “count”, or “size”
CS 230 – Winter 2022 2-3
MIPS Arrays l Use memory range as data area
l can iterate through addresses
l not possible with registers (no index)
l Direct access and iteration possible
l location of individual elements is a mathematical
calculation l “Raw” array
l no built-in boundary checking
CS 230 – Winter 2022 2-4
Example Array
• Consider this array
• start address: 0xA94
• length: 3
• 3 elements: 1210, 410, and 9210
CS 230 – Winter 2022
Array Emulator
• Command on uWaterloo servers
/u/cs230/pub/array yourprogram.mips
• sets up an array
• input a length and then that many numbers
• same as our examples
• start address in register $1 • length in register $2
CS 230 – Winter 2022 2-6
Practice: Accessing Elements
Using the array front end, put the first three values from the array into registers $3, $4, and $5. Then print the contents of $3, $4, and $5.
Recall that with array front end, the address of the first element of the arrange is automatically placed in $1, and the size of the array will be automatically placed into $2.
CS 230 – Winter 2022 2-7
Practice: Adding Elements
Using the array front end, add the elements of an array and place the result in $3.
CS 230 – Winter 2022 2-8
Practice: Elements Order
Using the array front end, check the elements of array to see if they are in ascending order.
• Assume that the array has at least two elements
• Put the value 0 in $3 if the array is in order
• Put the value 1 in $3 if the array is not in order
CS 230 – Winter 2022 2-9
Case Study: Selection Sort l Simple sorting algorithm
l not necessarily best or fastest, but simple l sweep through array
– find smallest element and move to front
– then restart sweep at next position
CS 230 – Winter 2022 2-10
Selection Sort – Python
l def SelectionSort(A, length): for i in range(0, length-1):
minpos = i
minimum = A[i]
for j in range(i+1, length):
if A[j] < minimum:
minpos = j
minimum = A[j]
temp = A[i]
A[i] = A[minpos]
A[minpos] = temp
CS 230 - Winter 2022 2-11
Selection Sort – MIPS
l Uselengthandi(simplifyassembly)
l in python: range (a,l): a, a+1, a+2,..., a+l-1
l Start of array in $1
l Length of array in $2
l Local variables:
l end of array in $8
l iin$9,jin$12
l minpos in $10, minimum in $11 l temps in $13, $14
CS 230 - Winter 2022 2-12
Selection Sort – MIPS l Set up array end for easier looping
addi $8, $0, 4 ; set up array end
mult $2, $8
add $8, $8, $1
CS 230 - Winter 2022 2-13
Selection Sort – Main Program
addi $9, $1, 0
oloop: addi $10, $9, 0
lw $11, 0($10)
addi $12, $9, 0
iloop: lw $13, 0($12)
slt $14, $13, $11
beq $14, $0, notmin
addi $11, $13, 0
addi $10, $12, 0
; initialize $9
; set minpos $10
; set minimum $11
; initialize $12
; set up compare value
; set new minimum
; set new minpos
notmin: addi $12, $12, 4
bne $12, $8, iloop ; loop over $12
lw $14, 0($9)
sw $14, 0($10)
sw $11, 0($9)
addi $9, $9, 4
bne $9, $8, oloop
; load front value
; store at minpos
; store min in front
; loop over $9
CS 230 - Winter 2022 2-14
Selection Sort – Lessons Learned l Manually keeping track of registers is difficult!
l Otherwise structure similar to Python program
CS 230 - Winter 2022 2-15
Subroutine
l Important technique to modularize programs
l separation of concerns, smaller coding units l reuse of code – call from anywhere
l Challenges
l call/return – how to redirect execution? l howdoIgetbacktowhereIcamefrom?
l nested call/return, recursion l argument and result passing
CS 230 - Winter 2022 2-16
l Jump And Link
l copy (current PC + 4) into register $31 l set PC tox(where x is a label)
l labelsmarkthestartoffunctions
l same type of labels we use for beq and bne
l x can also be an immediate (don’t do this)
CS 230 - Winter 2022 2-17
Indirect Calling
l Jump And Link Register
l copy (current PC + 4) into register $31 l set PC to contents of register $q
l loadaddressoflabelinto$qwithlis
l value in $q is called a function pointer
l allows functions to be passed as parameters
CS 230 - Winter 2022 2-18
l Jump Register
l setPCto$s
l usuallyjr$31
l register $31 holds return address
l register $31 begins with the outer return address l jr $31 to this address ends the program cleanly
CS 230 - Winter 2022 2-19
Calling and Returning Example function
addTwoNumbers:
add $2, $4, $5
Call that function
jal addTwoNumbers
Call that function indirectly
.word addTwoNumbers
Need more than this to handle the challenges
CS 230 - Winter 2022 2-20
Subroutine
l Subroutines can call subroutines
l including themselves - recursion
l How about registers that are in use?
l across subroutine calls
l registers ≠ local variables
l Save/restore current execution context l set of register values
l save where?
CS 230 - Winter 2022 2-21
Example: Print String l Print NUL-terminated string
l Use register conventions l $4...$7 for arguments
l $8...$15 for local variables l Simple
l do not need the stack yet
CS 230 - Winter 2022 2-22
Example: Print String
; pr_str: prints out a null-terminated string
; input: $4
; locals: $8, $9, $10
pr_str: lis $8
.word 0xffff000c
addi $9, $4, 0
loop: lw $10, 0($9)
; set $8 for output
; copy value into $9
; load character
beq $10, $0, end ; NUL? -> end
sw $10, 0($8) ; output character
addi $9, $9, 4 ; increment $9
beq $0, $0, loop ; loop
end: addi $10, $0, 0xA ; print LF
sw $10, 0($8)
jr $31 ; return
CS 230 – Winter 2022 2-23
Practice: Using pr_str Use the pr_str subroutine to print out the
values found at mystring1 and mystring2 The location of the string to be printed is passed
through an argument in $4.
CS 230 – Winter 2022 2-24
l Define memory area as stack
l last-in first-out queue
l convention: stack grows downward in memory
l Address “bottom” by stack pointer register l convention: register $29 on MIPS
l convention: $29 points to last used word l HOWEVER: in our MIPS simulator…
l use $30 instead
CS 230 – Winter 2022 2-25
Stack Save/Restore l Save register on stack – push
l decrement stack pointer to make room
l copy value to stack pointer memory location addi $30, $30, -4
sw $x, 0($30)
l Restore register from stack – pop
l copy value from stack pointer memory location
l increment stack pointer to free up space lw $x, 0($30)
addi $30, $30, 4
CS 230 – Winter 2022 2-26
Multiple Push/Pop l Save three registers on stack
addi $30, $30, -12
sw $3, 0($30)
sw $4, 4($30)
sw $5, 8($30)
l Restore the second one and discard the others lw $7, 4($30)
addi $30, $30, 12
l Remember: always release all stack memory!
l always add back same value to $30
CS 230 – Winter 2022 2-27
Argument Passing l Need to pass arguments and result
l Can use registers and/or stack
l need to agree between caller and callee
l MIPS convention
– first 4 arguments in registers
– remainder on the stack
CS 230 – Winter 2022 2-28
Register Conventions
l Which registers to save?
l Which registers to use for arguments/results?
l $1 – assembler temporary
l $2, $3 – function results and expressions l $4 – $7 – arguments
l $8 – $15, $24, $25 – temporary
l $16 – $23 – saved temporary
l $26 – $27 – OS kernel
CS 230 – Winter 2022 2-29
Who Saves What? l Caller vs. callee saves registers
l typical: more callers than callees
l calleesavesregistersproduceslesscode l saveregistersonlyifnecessary
l MIPS convention
l calleesaves$16-$23
l if you want to use one of these: save it first
l callermustsave$8-$15,$24,$25andothers
l if you call another function: save these first or lose them
l cleanupthestackbeforejr$31
CS 230 – Winter 2022 2-30
Local Variables l Default: make room on stack
l Usually no limits
l number of local variables
l size of local variables l “Automatic” variables
l memory reserved on routine entry l memory released on routine exit
CS 230 – Winter 2022 2-31
Practice: Sum of Cubes
Calculate the value x3 + y3, where the value of x will be in $1 to start, and the value of y will be $2 to start. Place the result in $3.
CS 230 – Winter 2022 2-32
l Subroutines can be both callers and callees
l Follow register conventions
l save input variable, because it is changed
l save return address as usual
CS 230 – Winter 2022 2-33
Hardware Support
l Often support from hardware / assembler
l reserving stack area, save registers l register windows (not on MIPS)
l multipleinstances(windows)ofcallee-savedregisters l “save”->usenextwindow
l fastbutlimitedtofixedsmallnumberofwindows
l e.g.Sparc:overlappingwindows
8x input, 8x local, 8x output
shift by 16, i.e., output becomes input
CS 230 – Winter 2022 2-34
Example: Print Integer l Extract digits
l check for negative number
l use modulo 10 and remainder to get digits l convert digits to ASCII
l Use stack to reorder digits
CS 230 – Winter 2022 2-35
Example: Print Integer – Part 1
; pr_int: prints out an integer value
; input: $4
; locals: $8, $9, $10, $11
.word 0xffff000c
addi $9, $4, 0
addi $11, $0, 0
slt $10, $9, $0
beq $10, $0, comp
addi $10, $0, 0x2D ; print minus sign
sw $10, 0($8)
sub $9, $0, $9 ; make $9 positive
; set up $8 for output
; set up value $9
; set up counter $11
; check for negative
CS 230 – Winter 2022 2-36
addi $11, $11, 1 ; increment counter
addi $10, $0, 10
div $9, $10 ; divide by 10
addi $30, $30, -4 ; remainder on stack
sw $10, 0($30)
mflo $9 ; result to $9
bne $9, $0, comp ; restart loop
Example: Print Integer – Part 2
CS 230 – Winter 2022 2-37
Example: Print Integer – Part 3
output: lw $10, 0($30) ; start from stack
addi $30, $30, 4
addi $10, $10, 0x30 ; convert to ASCII
sw $10, 0($8) ; output
addi $11, $11, -1 ; decrement counter
bne $11, $0, output ; restart loop
addi $10, $0, 0xA
sw $10, 0($8)
; print LF
CS 230 – Winter 2022
l Mathematical programming technique
l Divide larger problem into smaller similar ones
l Recursion mandates stack
l need memory area per subroutine
l Recursion fundamentally equivalent to l loop
l conditional branch
CS 230 – Winter 2022 2-39
Example: Factorial
l Assume input is in $4
l Output to $2
l Use recursion
l save only those registers necessary
l in particular, $2 is not saved during recursion l only modified on outbound path
CS 230 – Winter 2022 2-40
Example: Factorial
addi $2, $0, 1 ; basic result fac: slt$3,$0,$4 ;$4>0?
beq $3, $0, end ; else: finish
addi $30, $30, -8 ; save $31 & $4
sw $31, 4($30)
sw $4, 0($30)
addi $4, $4, -1
r: lw $31, 4($30)
lw $4, 0($30)
addi $30, $30, 8
mult $2, $4
end: jr $31
; decrement $4
; recursion
; restore $31 & $4
; multiply
; store result
CS 230 – Winter 2022 2-41
Example: Factorial l iteration easier…
l recursion only elegant in high-level languages? l context save/restore added by compiler
addi $2, $0, 1
slt $3, $0, $4
beq $3, $0, end
addi $3, $4, 0
loop: mult $2, $3
addi $3, $3, -1
bne $3, $0, loop
end: jr $31
; basic result
; $1 > 0 ?
; use $3 as temp
; store result
; decrement $3
; loop, if not 0
CS 230 – Winter 2022
Case Study: Fibonacci l Defined as:
l f(n) = f(n-1) + f(n-2) l f(1)=1
l In Python:
def fib(n):
ifn<2: #basecase
return fib(n - 1) + fib(n - 2)
CS 230 - Winter 2022 2-43
; input: $4
; output: $2
; locals: $8
fib: addi $2, $4, 0
addi $8, $0, 1
slt $8, $8, $4
beq $8, $0, end
; default output = input
; 1 < input
; else: finish
Fibonacci – MIPS
addi $30, $30, -8 ; save return & input
sw $31, 4($30)
sw $4, 0($30)
CS 230 - Winter 2022 2-44
Fibonacci – MIPS
addi $4, $4, -1
addi $30, $30, -4
sw $2, 0($30)
addi $4, $4, -1
lw $8, 0($30)
addi $30, $30, 4
add $2, $2, $8
lw $31, 4($30)
lw $4, 0($30)
addi $30, $30, 8
end: jr $31
; compute f(n-1)
; result in $2
; store result on stack
; compute f(n-2)
; result in $2
; restore f(n-1) as $8
; add f(n-1)+f(n-2)
; restore return & input
CS 230 - Winter 2022 2-45
Stack Frame
l Stack pointer: bottom of stack, first free field
l Stack pointer might vary during routine l set up stack for subroutine call
l At routine entry, frame pointer is set l e.g. to stack pointer at that time
l Frame pointer providers a constant base to l access local variables and arguments
l use offset in lw $t, i($fp) instruction
CS 230 - Winter 2022 2-46
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com