DOC PREVIEW
UW CSE 378 - Program and Memory Layout

This preview shows page 1-2-3-4-5 out of 15 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 15 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

10/11/2005 CSE378 Procedures. 1Program and memory layout• By convention the layout is:– Note that only half of the addressingspace is taken by userOther half is O.S.StackReserved4 0000Program text1000 00007fff ffffStatic dataDynamic data10/11/2005 CSE378 Procedures. 2Procedures• Procedures/functions are the major program structuring mechanism• Calling and returning form a procedure requires a protocol between caller and callee• Protocol is based on conventions10/11/2005 CSE378 Procedures. 3Procedures/Functions -- Protocol• Each machine (compiler?) has its own set of protocol(s)• Protocol: combination of hardware/software– e.g., “jal” is hardware– use of register $29 as $sp is software• Protocol: sequence of steps to be followed at each call and each return– controlled by hardware and/or software• In RISC machines– hardware performs simple instructions– software (compiler/assembler) controls sequence of instructions10/11/2005 CSE378 Procedures. 4Program stack• Each executing program (process) has a stack• Stack = dynamic data structure accessed in a LIFO manner• Program stack automatically allocated by O.S.• At the start of the program, register $sp ($29 in MIPS) is automatically loaded to point to the first empty slot on top of stack– After that it will be your responsibility to manage $sp• By convention, stack grows towards lower addresses– to allocate new space (i.e., when you push), decrement $sp– to free space on top of stack (pop), increment $sp10/11/2005 CSE378 Procedures. 5Push operation• push adds an item on top of stack– one instruction to manipulate the data, e.g. “sw $6,0($sp)”– one instruction to adjust the stack pointer e.g., “subu $sp,$sp,4”before after46-72 ???46-72127???8($sp)4($sp)$sp12($sp)8($sp)4($sp)$sp127 $6 127 $610/11/2005 CSE378 Procedures. 6Pop operation• pop removes the item on top of stack and stores it in a register– one instruction to adjust the stack pointer e.g., “addu $sp,$sp,4”– one instruction to manipulate the data, e.g. “lw $8,0($sp)”afterbefore46-72 12746-72127 ???8($sp)4($sp)$sp12($sp)8($sp)4($sp)$sp127 $8 453 $8Now this has become “garbage”10/11/2005 CSE378 Procedures. 7Procedure call requirements (caller/callee)• Caller must pass the return address to the callee• Caller must pass the parameters to the callee• Caller must save what is in volatile (registers) that could be used by the callee• Callee must save the return address (in case it becomes a caller)• Callee must provide (stack) storage for its own use• Caller/callee should support recursive calls10/11/2005 CSE378 Procedures. 8Mechanism• Registers are used for– passing return address in $rajal target– passing a small number of parameters (up to 4 in $a0 to $a3)– keeping track of the stack ($sp)– returning function values (in $v0 and $v1)• Stack is used for– saving registers to be used by callee– saving info about the caller (return address)– passing parameters if needed– allocating local data for the called procedure10/11/2005 CSE378 Procedures. 9Procedure calls and register conventionsRegister Name Function Comment$0 Zero Always 0 No-op on write$1 $at Reserved for assembler Don’t use it$2-3 $v0-v1 Expr. Eval/funct. Return$4-7 $a0-a3 Proc./func. Call parameters$8-15 $t0-t7 Temporaries; volatile Not saved on proc. Calls$16-23 $s0-s7 Temporaries Should be saved on calls$24-25 $t8-t9 Temporaries; volatile Not saved on proc. Calls$26-27 $k0-k1 Reserved for O.S. Don’t use them$28 $gp Pointer to global static memory$29 $sp Stack pointer$30 $fp Frame pointer$31 $ra Proc./funct return address10/11/2005 CSE378 Procedures. 10Who does what on a call (one sample protocol)• Caller– Saves any volatile register ($t0-$t9) having contents that need to be kept– Puts up to 4 arguments in $a0-$a3– If more than 4 arguments, pushes the rest on the stack– calls with jal instruction• Callee– saves $ra on stack – saves any non-volatile register ($s0-s7) that it will use10/11/2005 CSE378 Procedures. 11Who does what on return• Callee– restores any non-volatile register ($s0-$s7) it has used– restores $ra– puts function results in $v0-$v1– adjusts $sp– returns to caller with “jr $ra”• Caller– restores any volatile register it had saved– examines $v0-$v1 if needed10/11/2005 CSE378 Procedures. 12Example of a call sequence• Assume 2 arguments in $t0 and $t3 and we want to save the contents of $t6 and $t7move $a0,$t0 #1st argument in $a0move $a1,$t3 #2nd argument in $a1subu $sp,$sp,8 #room for 2 temps on stacksw $t6,8($sp) #save $t6 on stacksw $t7,4($sp) #save $t7 on stackjal target• Assume the callee does not need to save registerstarget: sw $ra,0($sp) #save return addresssubu $sp,$sp,4 # on stack10/11/2005 CSE378 Procedures. 13Return from the previous sequence• The callee will have put the function results in $v0-$v1addu $sp,$sp,4 #poplw $ra,0($sp) #return address in $rajr $ra #to caller• The caller will restore $t6 and $t7 and adjust stacklw $t6,8($sp)lw $t7,4($sp)addu $sp,$sp,810/11/2005 CSE378 Procedures. 14Factorial, The Logic• Logic of call: – Put argument in register a0 li $a0,5– Call procedure jal fact– Grab result from v0 sw $v0, …• Logic of Operation– Make a place on the stack– Save the argument and return address– Decrement the argument– Check if recursion is done– If not, recurse again– If so, compute the result into $v0– Grab return address– Restore stack– Return$v0 = $a0*($a0-1)!10/11/2005 CSE378 Procedures. 15Factorial, The Codefact: subu $sp,$sp,8 #create 2 spaces on stacksw $ra, 8($sp) #push return addresssw $a0,4($sp) #push argumentaddi $a0,$a0,-1 #decrement argumentbeqz $a0,base #is recursion done?jal fact #recursej done #v0 contains a0!base: li $v0,1 #initialize v0done: lw $a0,4($sp) #get argument backmult $v0,$a0 #figure next termmflo $v0 #grab result & ready for returnlw $ra,8($sp) #restore the return addressaddiu $sp,$sp,8 #popjr $ra #return$v0 =


View Full Document

UW CSE 378 - Program and Memory Layout

Documents in this Course
Encoding

Encoding

20 pages

Load more
Download Program and Memory Layout
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Program and Memory Layout and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Program and Memory Layout 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?