CS61C Machine Structures Lecture 12 MIPS Procedures II Logical Ops 2 13 2006 John Wawrzynek www cs berkeley edu johnw www inst eecs berkeley edu cs61c CS 61C L12 MIPS Procedures II Logical 1 Wawrzynek Spring 2006 UCB Review Functions called with jal return with jr ra The stack is your friend Use it to save anything you need Just be sure to leave it the way you found it Instructions we know so far Arithmetic add addi sub addu addiu subu Memory lw sw Decision beq bne slt slti sltu sltiu Unconditional 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 2 Wawrzynek Spring 2006 UCB Register Conventions 1 4 CalleR the calling function CalleE the function being called When callee returns from executing the caller needs to know which registers may have changed and which are guaranteed to be unchanged Register Conventions A set of generally accepted rules as to which registers will be unchanged after a procedure call jal and which may be changed CS 61C L12 MIPS Procedures II Logical 3 Wawrzynek Spring 2006 UCB Register Conventions 2 4 saved 0 No Change Always 0 s0 s7 Restore if you change Very important that s why they re called saved registers If the callee changes these in any way it must restore the original values before returning sp Restore if you change The stack pointer must point to the same place before and after the jal call or else the caller won t be able to restore values from the stack HINT All saved registers start with S CS 61C L12 MIPS Procedures II Logical 4 Wawrzynek Spring 2006 UCB Register Conventions 3 4 volatile ra Can Change The jal call itself will change this register Caller needs to save on stack if nested call v0 v1 Can Change These will contain the new returned values a0 a3 Can change These are volatile argument registers Caller needs to save if they ll need them after the call t0 t9 Can change That s why they re called temporary any procedure may change them at any time Caller needs to save if they ll need them afterwards CS 61C L12 MIPS Procedures II Logical 5 Wawrzynek Spring 2006 UCB Register Conventions 4 4 What do these conventions mean If function R calls function E then function R must save any temporary registers that it may be using onto the stack before making a jal call Function E must save any S saved registers it intends to use before garbling up their values Remember Caller callee need to save only temporary saved registers they are using not all registers CS 61C L12 MIPS Procedures II Logical 6 Wawrzynek Spring 2006 UCB Administrivia 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 22 CS 61C L12 MIPS Procedures II Logical 7 Wawrzynek Spring 2006 UCB Example Fibonacci Numbers 1 8 The Fibonacci numbers are defined as follows 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 8 Wawrzynek Spring 2006 UCB Example 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 9 Wawrzynek Spring 2006 UCB Example Fibonacci Numbers 3 8 Now let s translate this to MIPS You will need space for three words on the stack The function will use one s register s0 Write the Prologue fib addi sp sp 12 Space for three words sw ra 8 sp Save return address sw s0 4 sp Save s0 CS 61C L12 MIPS Procedures II Logical 10 Wawrzynek Spring 2006 UCB Example Fibonacci Numbers 4 8 Now write the Epilogue fin lw s0 4 sp Restore s0 lw ra 8 sp Restore return address addi sp sp 12 Pop the stack frame jr ra Return to caller CS 61C L12 MIPS Procedures II Logical 11 Wawrzynek Spring 2006 UCB Example Fibonacci Numbers 5 8 Finally write the body The C code is below Start by translating the lines indicated in the comments int fib int n if n 0 return 1 Translate Me if n 1 return 1 Translate Me return fib n 1 fib n 2 addi v0 zero 1 v0 1 beq a0 zero fin addi t0 zero 1 t0 1 beq a0 t0 fin Continued on next slide CS 61C L12 MIPS Procedures II Logical 12 Wawrzynek Spring 2006 UCB Example Fibonacci Numbers 6 8 Almost there but be careful this part is tricky int fib int n return fib n 1 fib n 2 addi a0 a0 1 a0 n 1 sw a0 0 sp Need a0 after jal jal fib fib n 1 lw a0 0 sp restore a0 addi a0 a0 1 a0 n 2 CS 61C L12 MIPS Procedures II Logical 13 Wawrzynek Spring 2006 UCB Example Fibonacci Numbers 7 8 Remember that v0 is caller saved int fib int n return fib n 1 fib n 2 add s0 v0 zero Place fib n 1 somewhere it won t get clobbered jal fib fib n 2 add v0 v0 s0 v0 fib n 1 fib n 2 To the epilogue and beyond CS 61C L12 MIPS Procedures II Logical 14 Wawrzynek Spring 2006 UCB Example Fibonacci Numbers 8 8 Here s the complete code for reference fib addi sp sp 12 sw ra 8 sp sw s0 4 sp lw a0 0 sp addi v0 zero 1 addi a0 a0 1 beq a0 zero fin add s0 v0 zero addi t0 zero 1 jal fib beq a0 t0 fin add v0 v0 s0 addi a0 a0 1 fin lw s0 4 sp sw a0 0 sp lw ra 8 sp jal fib addi sp sp 12 jr ra CS 61C L12 MIPS Procedures II Logical 15 Wawrzynek Spring 2006 UCB Bitwise 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 of register as a single quantity such as a signed or unsigned integer New Perspective View register as 32 raw bits rather than as a single 32 bit number Since registers are composed of 32 bits we may want to access individual bits or groups of bits rather than the whole Introduce two new classes of instructions Logical Shift Ops CS 61C L12 MIPS Procedures II Logical 16 Wawrzynek Spring 2006 UCB Logical Operators 1 3 Two basic logical operators AND outputs 1 only if both inputs are 1 OR outputs 1 if at least one input is 1 Truth Table standard table listing all possible combinations of inputs and …
View Full Document
Unlocking...