inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 11 Introduction to MIPS Procedures I Lecturer PSOE Dan Garcia www cs berkeley edu ddgarcia Smart crumble w pressure A study showed that students with a high working memory short term HWM capacity prob most Cal students crack under pressure but LWM students didn t Under pressure HWM LWM www livescience com humanbiology 050209 under pressure html CS61C L11 Introduction to MIPS Procedures I 1 Garcia UCB Administrivia High pressure midterm evaluations Review Sun 2005 03 06 2pm 10 Evans Midterm Mon 2005 03 07 7 10pm 1 Le Conte Dan s before class graphics videos www siggraph org publications video review SVR html Project 1 out make sure to work on it this weekend due next Friday An easy HW4 will follow due Wed after CS61C L11 Introduction to MIPS Procedures I 2 Garcia UCB Example The C Switch Statement 3 3 Final compiled MIPS code bne s5 0 L1 add s0 s3 s4 j Exit L1 addi t0 s5 1 bne t0 0 L2 add s0 s1 s2 j Exit L2 addi t0 s5 2 bne t0 0 L3 sub s0 s1 s2 j Exit L3 addi t0 s5 3 bne t0 0 Exit sub s0 s3 s4 Exit branch k 0 k 0 so f i j end of case so Exit t0 k 1 branch k 1 k 1 so f g h end of case so Exit t0 k 2 branch k 2 k 2 so f g h end of case so Exit t0 k 3 branch k 3 k 3 so f i j Removing breaks does NOT translate to removing jumps in this code my bad CS61C L11 Introduction to MIPS Procedures I 4 Garcia UCB C functions main int i j k m i mult j k m mult i i What information must compiler programmer keep track of really dumb mult function int mult int mcand int mlier int product product 0 while mlier 0 product product mcand mlier mlier 1 return product What instructions can accomplish this CS61C L11 Introduction to MIPS Procedures I 5 Garcia UCB Function Call Bookkeeping Registers play a major role in keeping track of information for function calls Register conventions Return address ra Arguments a0 a1 a2 a3 Return value Local variables v0 v1 s0 s1 s7 The stack is also used more later CS61C L11 Introduction to MIPS Procedures I 6 Garcia UCB Instruction Support for Functions 1 6 C sum a b a b s0 s1 int sum int x int y return x y M address In MIPS all instructions I 1000 are 4 bytes and stored in 1004 P memory just like data So 1008 S 1012 here we show the 1016 addresses of where the 2000 programs are stored 2004 CS61C L11 Introduction to MIPS Procedures I 7 Garcia UCB Instruction Support for Functions 2 6 C sum a b a b s0 s1 int sum int x int y return x y M address I 1000 add a0 s0 zero x a P 1004 add a1 s1 zero y b 1008 addi ra zero 1016 ra 1016 S 1012 j sum jump to sum 1016 2000 sum add v0 a0 a1 2004 jr ra new instruction CS61C L11 Introduction to MIPS Procedures I 8 Garcia UCB Instruction Support for Functions 3 6 C sum a b a b s0 s1 int sum int x int y return x y M Question Why use jr here Why not simply use j I P Answer sum might be called by many functions so we can t return to a fixed S place The calling proc to sum must be able to say return here somehow 2000 sum add v0 a0 a1 2004 jr ra new instruction CS61C L11 Introduction to MIPS Procedures I 9 Garcia UCB Instruction Support for Functions 4 6 instruction to jump and save return Single address jump and link jal Before 1008 addi ra zero 1016 ra 1016 1012 j sum goto sum After 1008 jal sum ra 1012 goto sum Why have a jal Make the common case fast function calls are very common Also you don t have to know where the code is loaded into memory with jal CS61C L11 Introduction to MIPS Procedures I 10 Garcia UCB Instruction Support for Functions 5 6 Syntax for jal jump and link is same as for j jump jal label jal should really be called laj for link and jump Step 1 link Save address of next instruction into ra Why next instruction Why not current one Step 2 jump Jump to the given label CS61C L11 Introduction to MIPS Procedures I 11 Garcia UCB Instruction Support for Functions 6 6 Syntax for jr jump register jr register Instead of providing a label to jump to the jr instruction provides a register which contains an address to jump to Only useful if we know exact address to jump to Very useful for function calls jal stores return address in register ra jr ra jumps back to that address CS61C L11 Introduction to MIPS Procedures I 12 Garcia UCB Nested Procedures 1 2 int sumSquare int x int y return mult x x y Something called sumSquare now sumSquare is calling mult So there s a value in ra that sumSquare wants to jump back to but this will be overwritten by the call to mult Need to save sumSquare return address before call to mult CS61C L11 Introduction to MIPS Procedures I 13 Garcia UCB Nested Procedures 2 2 In general may need to save some other info in addition to ra When a C program is run there are 3 important memory areas allocated Static Variables declared once per program cease to exist only after execution completes E g C globals Heap Variables declared dynamically Stack Space to be used by procedure during execution this is where we can save register values CS61C L11 Introduction to MIPS Procedures I 14 Garcia UCB C memory Allocation Address review Stack Space for saved procedure information sp stack pointer 0 Heap Explicitly created space e g malloc C pointers Static Variables declared once per program Code Program CS61C L11 Introduction to MIPS Procedures I 15 Garcia UCB Using the Stack 1 2 So we have a register sp which always points to the last used space in the stack To use stack we decrement this pointer by the amount of space we need and then fill it with info So how do we compile this int sumSquare int x int y return mult x x y CS61C L11 Introduction to MIPS Procedures I 16 Garcia UCB Using the Stack 2 2 int Hand compile sumSquare int x int y return mult x x y sumSquare push addi sp sp 8 space on stack sw ra 4 sp save ret addr sw a1 0 sp save y add a1 a0 zero mult x x jal mult call mult lw a1 0 sp add v0 v0 a1 lw ra 4 sp pop addi sp sp 8 jr ra mult CS61C L11 Introduction to MIPS Procedures I 17 restore y mult …
View Full Document
Unlocking...