6.001 Recitation 23: Register Machines and Stack FramesRI: Gerald Dalley, [email protected], 8 May 2007http://people.csail.mit.edu/dalleyg/6.001/SP2007/Miscellany• apply: See the MIT Scheme documentation for a precise description.• Register machines: read the textbook and/or study the lecture notes. We will only have time to touchon a few key points in recitation.• Project 5: printf prints values to the screen. It does not return a value.Expression Types(const C): A constant value. It acts somewhat like quote. To get the numb er one, you would use (const 1).To get the list (1 2) you would use (const (1 2)).(reg R): Retrieve the value of a register R. To get the value of the register arg0, you would use (reg arg0).(label L): Retrieve the offset of the given label L. To get the value of label loop-top, you would use(label loop-top).(op O): Perform operation O on some values. Following the (op O), you should list the input arguments to theoperation, which may be constants, registers, or labels. An expression may only contain 1 operation(i.e. nested expressions are not allowed). In order to compute the result of adding 1 to the register arg0,you would use (op +) (reg arg0) (const 1). For this recitation, you may assume the following operationsare available: +, -, *, /, <, <=, =, >, and >= (nearly all real CPUs have these operations built-in).Some Special Registerspc: The program counter register pc tells the sequencer what instruction is currently being evaluated.cr: The condition register is used to determine whether to take branches. Use a (test expr) instruction toset its value.sp: Pointer to the top of the stack. The stack is a fixed-sized memory area for saving and restoring values.Instructions(assign reg expr): Sets register reg to be the result of expression expr. The assigned register doesn’t need atag because it is always a register being assigned. For example, to increment the result register:(assign result (op +) (reg result) (const 1)).(test expr): This is equivalent to assigning the cr. The cr register is used to determine whether to take abranch. For example, to set the cr based on whether the register x is less than 10:(test (op <) (reg x) (const 10))(goto expr): Sets the pc to be the result of expr, which is usually a label or a register. Effectively continuesthe execution at another point in the code. To jump to the label loop-top:(goto (label loop-top))(branch expr): If the value in the cr is true, ac ts like a goto. Otherwise it does nothing. To conditionallyjump to the label loop-done:(branch (label loop-done))(save reg): Place the value in a register reg on top of the stack. This will also increment the stack pointersp. If the stack has no space left, a “stack overflow” error is signalled. To place the value in the registerresult on the stack: (save result).(restore reg) Take the top value off the stack and put it in the register reg. This will also decrement thestack pointer sp. If the stack has nothing on it, a “stack underflow” error is signalled. To remove thetop element of the stack and place it in the register result: (restore result).1Writing CodeWrite double: code to compute 2x, given x in arg0, and leave the output in result.double( assign result ( op *) ( reg arg0 ) ( const 2))( goto ( reg c o n ti n u e ))Write func: code to compute x2+ y, given x in arg0, y in arg1, and leave the output in result.funcGeneral ContractsWhen we first started learning Scheme, we initially evaluated isolated expressions and then quickly startedworking with procedure abstractions. With our register machines, we also want to build abstractions. Sincethe register machine is much lower-level, it’s very important to clearly document the expectations and con-straints of our subroutines. One way to do so is to specify the contract:Input: Register(s) whose value is read and used before it is written.Output: Register(s) designated as output.Modifies: Register(s) whose value after the code block could differ from their original value.Interpreting Iterative CodeConsider the following code:foo( assign a ( co n st 1))( assign b ( co n st 1))bar( test ( op <=) ( reg n) ( co n st 2))( branch ( reg con t i nu e ))( assign tmp ( reg a ))( assign a ( reg b ))( assign b ( op +) ( reg tmp ) ( reg a))( assign n ( op -) ( reg n) ( cons t 1))( goto ( label bar ))What is the contract:• Input: M• Output: M• Modifies: MWhat does the code do?Implement an equivalent procedure in Scheme:2Subroutine Contracts• Input: What register(s) hold the input values and the return point?• Output: What register(s) will hold the output value (often result)?• Modifies: What non-output register(s) might be modified?• Stack: What happens to the stack?Subroutine Call ConventionsThere are actually a number of design decisions to make when creating conventions for how to call a sub-routine. For a given system, it’s highly beneficial to come up with a boilerplate subroutine contract that all(normal) subroutines ob ey. Here’s one such convention:• Making the call1. Save the registers you don’t want clobbered (including continue).2. Assign values to procedure input regs3. Assign the continue register to the return label.4. goto the start of the procedure.• At the call’s return label1. Use the output2. Restore the registers (in reverse order)Another “calling convention” might be to have the callee (the procedure being called) save and restoreeverything that is important that it might modify, have the caller put the return address on the top of thestack, and have the callee remove the return address from the stack but otherwise leave the stack unchanged.Other conventions are possible (and each convention c omes with its tradeoffs).A “call frame” is the section of the stack which corresponds to a procedure call.Iterative ExponentiationConsider an iterative implementation of exponentiation:( define ( expt b n)( define ( e x pt - it e r co u n ter p r o d uct )( if (= counter 0)product( expt - i te r (- counter 1)(* b prod u c t ))))( expt - i te r n 1))Write the register machine code implementation:What is the contract:• Input: M• Output: M• Modifies: M• Stack: M3Recursive ExponentiationConsider a recursive implementation of exponentiation:( define ( expt b n)( if (= n 0)1(* b ( expt b (- n 1)))))Write the register machine code implementation:What is the contract:• Input: M• Output: M• Modifies: M• Stack: MCan you think of any optimizations that would speed up
View Full Document
Unlocking...