📄 http:^^www.cs.wisc.edu^~cs354-2^cs354^lec.notes^procedures.html
字号:
Date: Tue, 05 Nov 1996 20:50:00 GMTServer: NCSA/1.5Content-type: text/htmlLast-modified: Wed, 16 Oct 1996 15:43:09 GMTContent-length: 21536<html><head><title> Lecture notes - Chapter 9 - Procedures</title></head><BODY><h1> Chapter 9 -- Procedures</h1><pre>All about Procedures--------------------an introduction to procedureswhy have procedures? -- reuse of code simplifies program writing -- modular code facilitates modification -- allows different programmers to write different parts of the same program -- etc.Assembly languages typically provide little or no support for procedure implementation.So, we get to build a mechanism for implementing procedures outof what we already know. First, some terms and what we need.In Pascal: begin . . . x := larger(a, b); CALL . . . end. HEADER PARAMETERS function larger (one, two: integer): integer; begin if ( one > two ) then larger := one BODY else larger := two end;In C: { . . . x = larger(a, b); CALL . . . } HEADER PARAMETERS int larger (int one, int two) { if ( one > two ) larger = one; BODY else larger = two; } Steps in the execution of the procedure: 1. save return address 2. procedure call 3. execute procedure 4. return what is return address? instruction following call what is procedure call? jump or branch to first instruction in the procedure what is return? jump or branch to return addressMAL implementation of SAL procedure call: la $5, rtn1 b proc1 # one procedure call rtn1: # next instruction here . . . la $5, rtn2 b proc1 # another procedure call rtn2: # next instruction here . . . proc1: # 1st instruction of procedure here . . . jr $5jr is a new instruction -- It does an unconditional branch (jump, actually) to the address contained in the register specified. MIPS R2000 (MAL, actually) provides a convenient instruction for procedurecalls. jal procname does 2 things 1. it places the address of the instruction following it into register $ra ($31). (The choice of 31 is arbitrary, but fixed.) 2. it branches (jumps) to the address given by the label (procname).the example re-written: jal proc1 . . . jal proc1 . . . proc1: # 1st instruction of procedure here . . . jr $ra # $ra is the alias for $31 one problem with this scheme. What happens if a procedurecalls itself (recursion), or if a procedure calls anotherprocedure (nesting) (using jal)? The value in register $31 gets overwritten with each jal instruction. Return addresses are lost. This is an unrecoverable error!What is needed to handle this problem is to have a way tosave return addresses as they are generated. For a recursivesubroutine, it is not known ahead of time how many timesthe subroutine will be called. This data is generateddynamically; while the program is running.The best way to save dynamically generated data is on a stack.SYSTEM STACK------------ A stack is so frequently used in implementing procedure call/return, that many computer systems predefine a stack, the SYSTEM STACK. STATIC -- can be defined when program is written (compile time) DYNAMIC -- is defined when a program is executed (run time) in this case, it is the amount of storage that cannot be determined until run time. The size of the system stack is very large. In theory, it should be infinitely large. In practice, it must have a size limit. address | | 0 | your | | program | | here | | | | | | | | | | | | system | / \ very | stack | | grows towards smaller addresses large | here | | addresses terminology: Some people say that this stack grows DOWN in memory. This means that the stack grows towards smaller memory addresses. Their picture would show address 0 at the bottom (unlike my picture). DOWN and UP are vague terms, unless you know what the picture looks like. The MIPS system stack is defined to grow towards smaller addresses, and the stack pointer points to an empty location at the top of the stack. The stack pointer is register $29, also called $sp, and it is defined before program execution begins. push, in MAL: sw $?, ($sp) # the ? is replaced by whateger register sub $sp, $sp, 4 # contains the data to be pushed. OR sub $sp, $sp, 4 sw $?, 4($sp) pop, in MAL: add $sp, $sp, 4 # the ? is replace by a register number lw $?, ($sp) OR lw $?, 4($sp) add $sp, $sp, 4 NOTE: if $sp ($29) is used for any other purpose, then the stack pointer is lost. An example of using the system stack to save return addresses: jal doit . . . jal doit . . .doit: sw $ra, ($sp) # save return address sub $sp, $sp, 4 . . . jal another # this would overwrite the return # address if it had not been saved. . . . add $sp, $sp, 4 # restore return address lw $ra, ($sp) jr $ra about STACK FRAMES (ACTIVATION RECORDS)---------------------------------------from a compiler's point of view, there are a bunch of thingsthat should go on the stack relating to procedure call/return.They include: return address (register) parameters other various registersEach procedure has different requirements for numbers of parameters, their size, and how many registers (which ones) will need to be saved on the stack. So, we compose a STACK FRAME or ACTIVATION RECORD that is specific to a procedure.Space for a stack frame gets placed on the stack each timea procedure is called, and taken off the stack each time areturn occurs. These stack frames are pushed/poppedDYNAMICALLY (while the program is running).example: jal A jal B . .A: jal C jal D jr $raB: jal D jr $raC: jal E jr $raD: jr $raE: jr $ra show stack for a trace through this calling sequence The code (skeleton) for one of these procedures:A: jal C jal D jr $raA: sub $sp, $sp, 20 # allocate frame for A sw $ra, 16($sp) # save A's return address jal C jal D lw $ra, 16($sp) # restore A's return address add $sp, $sp, 20 # remove A's frame from stack jr $ra # return from ASome notes on this:-- the allocation and removal of a frame should be done within the body of the procedure. That way, the compiler does not need to know the size of a procedure's frame.-- Accesses to A's frame are done via offsets from the stack pointer. parameter passing.------------------parameter = argumentJust as there is little/no support for implementing proceduresin many assembly languages, there is little/no support for passingparameters to those procedures.Remember, when it comes to the implementation, -- convention -- its up to the programmer to follow the conventionsPassing parameters means getting data into a place set asidefor the parameters. Both the calling program and the procedureneed to know where the parameters are. The calling program places them there, and possibly uses values returned by the procedure. The procedure uses the parameters.a note on parameter passing -- a HLL specifies rules for passing parameters. There are basically 2 types of parameters. Note that a language can offer 1 or both types. call by value -- what C has. In Pascal, these are parameters declared without the var in front of the variable name. Fortran doesn't have this type of parameter. The parameter passed may not be modified by the procedure. This can be implemented by passing a copy of the value. What call by value really implies is that the procedure can modify the value (copy) passed to it, but that the value is not changed outside the scope of the procedure. call by reference -- what Fortran has. In Pascal, these are "var type" parameters. The parameter passed to the subroutine can be modified, and the modification is seen outside the scope of the subroutine. It is sort of like having access to global variable.There are many ways of implementing these 2 variable types.If call by value is the only parameter type allowed, howcan we implement a reference type parameter? Pass the address of the variable as the parameter. Then access to the variable is made through its address. This is what is done in C. Simplest mechanism -- registers-------------------------------the calling program puts the parameter(s) into specific registers,and the procedure uses them. example: . . . add $4, $20, $0 # put parameter in register 4 jal decrement move $20, $4 # recopy parameter to its correct place. . . . decrement: add $4, $4, -1 jr $raNotes: -- This is a trivial example, since the procedure is 1 line long. -- Why not just use $20 within the procedure? 1. convention -- parameters are passed in specific registers.⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -