CS 61C L12 MIPS Procedures II / Logical (1) Wawrzynek Spring 2006 © UCB2/13/2006John Wawrzynek(www.cs.berkeley.edu/~johnw)www-inst.eecs.berkeley.edu/~cs61c/CS61C – Machine StructuresLecture 12 - MIPS Procedures II &Logical OpsCS 61C L12 MIPS Procedures II / Logical (2) Wawrzynek Spring 2006 © UCBReview° Functions called with jal, return with jr $ra.° The stack is your friend: Use it to saveanything you need. Just be sure to leave it theway you found it.° Instructions we know so farArithmetic: add, addi, sub, addu, addiu, subuMemory: lw, swDecision: beq, bne, slt, slti, sltu, sltiuUnconditional Branches (Jumps): j, jal, jr° Registers we know so far• All of them!• There are CONVENTIONS when calling procedures!CS 61C L12 MIPS Procedures II / Logical (3) Wawrzynek Spring 2006 © UCBRegister Conventions (1/4)° CalleR: the calling function° CalleE: the function being called° When callee returns from executing,the caller needs to know whichregisters may have changed and whichare guaranteed to be unchanged.° Register Conventions: A set ofgenerally accepted rules as to whichregisters will be unchanged after aprocedure call (jal) and which may bechanged.CS 61C L12 MIPS Procedures II / Logical (4) Wawrzynek Spring 2006 © UCBRegister Conventions (2/4) - saved°$0: No Change. Always 0.°$s0-$s7: Restore if you change. Veryimportant, that’s why they’re calledsaved registers. If the callee changesthese in any way, it must restore theoriginal values before returning.°$sp: Restore if you change. The stackpointer must point to the same placebefore and after the jal call, or elsethe caller won’t be able to restorevalues from the stack.° HINT -- All saved registers start with S!CS 61C L12 MIPS Procedures II / Logical (5) Wawrzynek Spring 2006 © UCBRegister Conventions (3/4) - volatile°$ra: Can Change. The jal call itselfwill change this register. Caller needsto save on stack if nested call.°$v0-$v1: Can Change. These willcontain the new returned values.°$a0-$a3: Can change. These arevolatile argument registers. Callerneeds to save if they’ll need them afterthe call.°$t0-$t9: Can change. That’s whythey’re called temporary: anyprocedure may change them at anytime. Caller needs to save if they’llneed them afterwards.CS 61C L12 MIPS Procedures II / Logical (6) Wawrzynek Spring 2006 © UCBRegister Conventions (4/4)° What do these conventions mean?• If function R calls function E, thenfunction R must save any temporaryregisters that it may be using onto thestack before making a jal call.• Function E must save any S (saved)registers it intends to use before garblingup their values• Remember: Caller/callee need to saveonly temporary/saved registers they areusing, not all registers.CS 61C L12 MIPS Procedures II / Logical (7) Wawrzynek Spring 2006 © UCBAdministrivia° Midterm Exam I• Friday 2/24 6-8pm, 1 Pimentel(2 weeks from today)• Review Session TBA° Project 2 due earlier that week• Tuesday 2/21 11:59pm° HW4 due next Wednesday° No HW due 2/22CS 61C L12 MIPS Procedures II / Logical (8) Wawrzynek Spring 2006 © UCBExample: Fibonacci Numbers 1/8° The Fibonacci numbers are defined asfollows: F(n) = F(n – 1) + F(n – 2),F(0) and F(1) are defined to be 1° In scheme, this could be written:(define (Fib n)(cond ((= n 0) 1) ((= n 1) 1)(else (+ (Fib (- n 1))(Fib (- n 2)))))CS 61C L12 MIPS Procedures II / Logical (9) Wawrzynek Spring 2006 © UCBExample: Fibonacci Numbers 2/8° Rewriting this in C we have:int fib(int n) {!if(n == 0) { return 1; }!if(n == 1) { return 1; }!return (fib(n - 1) + fib(n - 2));}CS 61C L12 MIPS Procedures II / Logical (10) Wawrzynek Spring 2006 © UCBfib:addi $sp, $sp, -12 # Space for three wordssw $ra, 8($sp) # Save return addresssw $s0, 4($sp) # Save s0° Now, let’s translate this to MIPS!° You will need space for three words on thestack° The function will use one $s register, $s0° Write the Prologue:Example: Fibonacci Numbers 3/8CS 61C L12 MIPS Procedures II / Logical (11) Wawrzynek Spring 2006 © UCBfin:lw $s0, 4($sp)lw $ra, 8($sp)addi $sp, $sp, 12jr $ra# Restore $s0# Restore return address# Pop the stack frame# Return to caller° Now write the Epilogue:Example: Fibonacci Numbers 4/8CS 61C L12 MIPS Procedures II / Logical (12) Wawrzynek Spring 2006 © UCBaddi $v0, $zero, 1beq $a0, $zero, finaddi $t0, $zero, 1beq $a0, $t0, finContinued on next slide. . .# $v0 = 1## $t0 = 1#° Finally, write the body. The C code is below. Startby translating the lines indicated in the commentsint fib(int n) {if(n == 0) { return 1; } /*Translate Me!*/if(n == 1) { return 1; } /*Translate Me!*/return (fib(n - 1) + fib(n - 2));}Example: Fibonacci Numbers 5/8CS 61C L12 MIPS Procedures II / Logical (13) Wawrzynek Spring 2006 © UCB# $a0 = n - 1# Need $a0 after jal# fib(n - 1)# restore $a0# $a0 = n - 2addi $a0, $a0, -1sw $a0, 0($sp)jal fiblw $a0, 0($sp)addi $a0, $a0, -1° Almost there, but be careful, this part is tricky!int fib(int n) {. . .return (fib(n - 1) + fib(n - 2));}Example: Fibonacci Numbers 6/8CS 61C L12 MIPS Procedures II / Logical (14) Wawrzynek Spring 2006 © UCBadd $s0, $v0, $zerojal fibadd $v0, $v0, $s0To the epilogue and beyond. . .# Place fib(n – 1)# somewhere it won’t get# clobbered# fib(n - 2)# $v0 = fib(n-1) + fib(n-2)° Remember that $v0 is caller saved!int fib(int n) {. . .return (fib(n - 1) + fib(n - 2));}Example: Fibonacci Numbers 7/8CS 61C L12 MIPS Procedures II / Logical (15) Wawrzynek Spring 2006 © UCB° Here’s the complete code for reference:Example: Fibonacci Numbers 8/8fib: addi $sp, $sp, -12sw $ra, 8($sp)sw $s0, 4($sp)addi $v0, $zero, 1beq $a0, $zero, finaddi $t0, $zero, 1beq $a0, $t0, finaddi $a0, $a0, -1sw $a0, 0($sp)jal fiblw $a0, 0($sp)addi $a0, $a0, -1add $s0, $v0, $zerojal fibadd $v0, $v0, $s0fin: lw $s0, 4($sp)lw $ra, 8($sp)addi $sp, $sp, 12jr $raCS 61C L12 MIPS Procedures II / Logical (16) Wawrzynek Spring 2006 © UCBBitwise Operations° Up until now, we’ve done arithmetic (add,sub,addi ), memory access (lw and sw),and branches and jumps.° All of these instructions view contents ofregister as a single quantity (such as asigned or unsigned integer)° New Perspective: View register as 32 rawbits rather than as a single 32-bit number° Since registers are composed of 32 bits, wemay want to access individual bits (orgroups of bits) rather than the whole.° Introduce two new classes of instructions:• Logical & Shift OpsCS 61C L12 MIPS Procedures II / Logical (17) Wawrzynek
View Full Document
Unlocking...