inst eecs berkeley edu cs61c CS61C Machine Structures Lecture 8 MIPS Procedures 2007 7 9 Scott Beamer Instructor OpenDNS tries to make websurfing safer www nytimes com CS61C L8 MIPS Procedures 1 Beamer Summer 2007 UCB Review A Decision allows us to decide what to execute at run time rather than compile time C Decisions are made using conditional statements within if while do while for MIPS Decision making instructions are the conditional branches beq and bne In order to help the conditional branches make decisions concerning inequalities we introduce a single instruction Set on Less Than called slt slti sltu sltiu Unsigned add sub don t cause overflow New MIPS Instructions beq bne j sll srl slt slti sltu sltiu addu addiu subu CS61C L8 MIPS Procedures 2 Beamer Summer 2007 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 L8 MIPS Procedures 3 Beamer Summer 2007 UCB Function Call Bookkeeping Registers play a major role in keeping track of information for function calls Register conventions Return address Arguments ra a0 a1 a2 a3 Return value v0 v1 Local variables s0 s1 s7 The stack is also used more later CS61C L8 MIPS Procedures 4 Beamer Summer 2007 UCB Instruction Support for Functions 1 6 sum a b a b s0 s1 C int sum int x int y return x y M I P S address 1000 1004 1008 1012 1016 2000 2004 CS61C L8 MIPS Procedures 5 In MIPS all instructions are 4 bytes and stored in memory just like data So here we show the addresses of where the programs are stored Beamer Summer 2007 UCB Instruction Support for Functions 2 6 sum a b a b s0 s1 C int sum int x int y return x y M I P S address 1000 add 1004 add 1008 addi 1012 j 1016 a0 s0 zero x a a1 s1 zero y b ra zero 1016 ra 1016 sum jump to sum 2000 sum add v0 a0 a1 2004 jr ra new instruction CS61C L8 MIPS Procedures 6 Beamer Summer 2007 UCB Instruction Support for Functions 3 6 sum a b a b s0 s1 C 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 L8 MIPS Procedures 7 Beamer Summer 2007 UCB Instruction Support for Functions 4 6 Single instruction to jump and save return 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 L8 MIPS Procedures 8 Beamer Summer 2007 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 L8 MIPS Procedures 9 Beamer Summer 2007 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 L8 MIPS Procedures 10 Beamer Summer 2007 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 L8 MIPS Procedures 11 Beamer Summer 2007 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 L8 MIPS Procedures 12 Beamer Summer 2007 UCB C memory Allocation review Address sp stack pointer 0 Stack Space for saved procedure information Heap Explicitly created space e g malloc C pointers Static Variables declared once per program Code Program CS61C L8 MIPS Procedures 13 Beamer Summer 2007 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 L8 MIPS Procedures 14 Beamer Summer 2007 UCB Using the Stack 2 2 Hand compile int sumSquare int x int y return mult x x y sumSquare addi sp sp 8 space on stack push sw ra 4 sp save ret addr sw a1 0 sp save y add a1 a0 zero prep args 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 L8 MIPS Procedures 15 restore y mult y get ret addr restore stack Beamer Summer 2007 UCB Steps for Making a Procedure Call 1 Save necessary values onto stack 2 Assign argument s if any 3 jal call 4 Restore values from stack CS61C L8 MIPS Procedures 16 Beamer Summer 2007 UCB Rules for Procedures Called with a jal instruction returns with a jr ra Accepts up to 4 arguments in a0 a1 a2 and a3 Return value is always in v0 and if necessary in v1 Must follow register conventions even in functions that only you will call So what are they We ll see these in a few slides CS61C L8 MIPS Procedures 17 Beamer Summer 2007 UCB Basic Structure of a Function Prologue entry label addi sp sp framesize sw ra framesize 4 sp save ra save other regs if need be ra Body call other functions Epilogue memory restore other regs if need be lw ra framesize 4 sp restore ra addi sp sp framesize jr ra CS61C L8 MIPS Procedures 18 Beamer Summer 2007 UCB Administrivia Assignments Project …
View Full Document
Unlocking...