5.0 SIM5 – Adding Stack Operations 5.1 Stack Operation The operation of a memory stack is analogous to using a stack of dishes to store numbers. To store (push) a number on the stack, write the number on an extra dish and add the dish to the top of the stack of dishes. To fetch (pop) a number from the stack, remove the top dish from the stack and read the number. We will use register 7 (%r7) as a stack pointer (sp). To add something to the stack, decrement register 7 and then move a word from another register to the area in memory where %r7 now points. For example, to save register 5 on the stack: dec %r7 mvrm %r5,(%r7) To later retrieve the saved value: mvmr (%r7),%r5 inc %r7 Notice that we dec and then mov when we push an item on the stack, but we mov and then inc on a pop. In this way, we retrieve the correct value from the stack and leave the stack as we found it. When we save multiple items on the stack, the last item added to the stack is the first item removed from the stack (LIFO, Last In, First Out). For example, the following code saves registers %r3, %r4, and %r5 on the stack. dec %r7 mvrm %r3,(%r7) dec %r7 mvrm %r4,(%r7) dec %r7 mvrm %r5,(%r7) These three items are then removed in reverse order. Since %r5 was the last register pushed on the stack, it must be the first one "popped". mvmr (%r7),%r5 inc %r7 mvmr (%r7),%r4 inc %r7 mvmr (%r7),%r3 inc %r7 The SIM5 simulator initializes all of the processor registers to zero. Before anything is pushed on the stack, the memory and the stack pointer (%r7) appear as follows: addr value +------+ 999 | ???? | +------+ 998 | ???? | +------+ ... ... +------+ 001 | ???? | %r7 +------+ +-----+ 000 | ???? |<-----| 000 | +------+ +-----+ If %r3, %r4, and %r5 contain 3333, 4444, and 5555, memory and the stack pointer will appear as follows after the three registers are pushed on the stack. Notice that the stack pointer points to the last item pushed. addr cont +------+ 999 | 3333 | +------+ 998 | 4444 | +------+ 997 | 5555 |<--+ +------+ | 996 | ???? | | +------+ | ... ... | +------+ | 001 | ???? | | %r7 +------+ | +-----+ 000 | ???? | +--| 997 | +------+ +-----+ Because we display memory with the lowest address (000) at the bottom and the highest address (999) at the top, our stack is shown “up-side down” with the most recently added item (5555 in this case) at the “bottom”. After the three items are "popped" from the stack, %r7 will again point to address 000. 5.2 SIM5 PUSH AND POP INSTRUCTIONS Stack operations are so important that modern computer architectures include some form of push and pop operation codes. For SIM5, we will add these instructions to the single register (8x0r) instruction family: machine assembly name format format effect IN 800r in %rn R[r] = input device OUT 810r out %rn output device = R[r] ... ... ... ... ... PUSH 880r push %rn R[7] = R[7] + 1, M[R[r7]] = [R[r] POP 890r pop %rn R[r] = M[R[7]], R[7] = R[7] - 1 The new push and pop instructions simplify the code required to input 10 numbers and output them in reverse order. This program uses addresses 000 to 012 for code, and 990 to 999 for the ten items pushed on the stack. reverse10.sim5 – input 10 integers and output them in reverse order 000 5010 start: lda 10 for (%r0=10;%r0!=0;%r0--) { 001 8001 inloop: in %r1 %r1 = input() 002 8801 push %r1 push(%r1) 003 8401 dec %r0 004 7100 skeq %r0 005 6001 jmp inloop } 006 5010 lda 10 for (%r0=10;%r0!=0;%r0--) { 007 8801 outloop: pop %r1 %r1 = pop() 008 8101 out %r1 output(%r1) 009 8401 dec %r0 010 7100 skeq %r0 011 6001 jmp outloop } 012 0000 halt return; 000 .end start 5.3 SAVING THE LINK REGISTER In Section 4.4, we demonstrated how a subroutine could be called using the instruction “exch %r8,%r9”. This technique works well for “leaf” functions that do not call other functions. However, “interior” functions that call other functions need to preserve the return address saved in the link register, %r8, before calling a lower level function. In the following example, interior function square(n) saves %r8 on the stack before calling leaf function mult(n). square.sim5 – input an integer n and output n squared. 000 8001 main: in %r1 %r1 = input() 001 5006 lda square %r0=square(%r1) 002 9008 mvrr %r0,%r8 003 9389 exch %r8,%r9 004 8100 out %r0 output(%r0) 005 0000 halt return 006 8805 square: push %r8 save return address 007 9012 mvrr %r1,%r2 %r2=%r1 008 5013 lda mult %r0=mult(%r1,%r2) 009 9008 mvrr %r0,%r8 010 9389 exch %r8,%r9 011 8908 pop %r8 restore %r8 012 9389 exch %r8,%r9 return 013 8200 mult: clr %r0 r0 = 0; 014 7201 loop: skne %r1 if (r1==0) 015 9089 mvrr %r8,%r9 return; 016 9420 add %r2,%r0 r0 = r0 + r2; 017 8401 dec %r1 r1--; 018 6008 jmp loop goto loop; 000 .end start The calling sequence for either an interior function (square) or a leaf function (mult) follows the same sequence: lda functionname mvrr %r0,%r8 exch %r8,%r9 An interior function must (and a leaf function may) save the link register %r8 on the stack with an instruction such as: functionname: push %r8 If the called function has saved %r8 on the stack, then either of the following instructions can be used to return. pop %r8 pop %r9 mvrr %r8,%r9 A leaf function that does not push %r8 on the stack can use either of the following instructions to return: exch %r8,%r9 mvrr %r8,%r9 5.4 SIM5 CALL AND RET INSTRUCTIONS Since calling an interior function is a common programming practice, the following sequence of instructions is frequently seen: mvrr %rn,%r8 in the caller exch %r8,%r9 in the caller ... callee: push %r8 in the callee To save time and space, we can create a “call %rn“ instruction to replace this three instruction sequence. When we do this, there is no need to use %r8 at all. The call instruction can simply save %r9 on the stack and then move the value in %rn into %r9, the instruction pointer. We will arbitrarily place this instruction with the two-register instructions and use the operation code 960s where “s” is the source register containing the starting address of the function. Calling interior function square uses the sequence of two instructions: lda square %r0=square(%r1) call %r0 saving one instruction in the caller (main) and the push instruction in the callee (square). We can return from a called function with the instruction: pop %r9 However, for program clarity we will give this particular form of the pop instruction the symbolic name ret. (Either a ret instruction or a pop %r9 instruction would cause assembler to generate the machine language instruction 8909.) With the addition of call and ret, the SIM5 version of our simulated computer has added three machine language instructions (and four symbolic operation codes) to the SIM4 computer. machine assembly name format format effect PUSH 880s push %rn R[7] = R[7] + 1, M[R[r7]] = [R[r] POP 890r pop %rn R[r] = M[R[7]], R[7] = R[7] - 1 CALL 960s call %rn R[7] = R[7] + 1, M[R[r7]] = [R[r] RET 8909 ret R[9] = M[R[7]], R[7] = R[7] - 1 We can rewrite program square using the call and ret instructions to produce program square2. Since mult is a leaf function, we could have invoked it using the link register (%r8) and saved a memory reference (the push generated by call). However, using call and ret for all functions makes the code simpler and clearer and we recommend their use for all functions calls unless speed is critical. In comparison with the previous version, square.sim5, using call and ret has also made the program shorter by four instructions. #square2.sim5 – input an integer n and output n squared. 000 8001 main: in %r1 %r1 = input() 001 5005 lda square %r0=square(%r1) 002 9600 call %r0 003 8100 out %r0 output(%r0) 004 0000 halt return 005 9012 square: mvrr %r1,%r2 %r2=%r1 005 5009 lda mult %r0=mult(%r1,%r2) 007 9600 call %r0 008 8909 ret return 009 8200 mult: clr %r0 r0 = 0; 010 7201 loop: skne %r1 if (r1==0) 011 8909 ret return; 012 9420 addr %r2,%r0 r0 = r0 + r2; 013 8401 dec %r1 r1--; 014 6010 jmp loop goto loop; 000 .end start 5.5 RECURSION The stack instructions make it easy to write recursive functions (functions that, directly or indirectly, call themselves). The following shows the creation and execution of a C program that computes the sum of the integers from 1 to 10. cis-lclient15:~/2012/sim>nano recurse.c int recurse(int); int main() { int ten = 10; return recurse(ten); } int recurse(int num) { int temp = num; if (temp <= 0) return 0; else return recurse(temp-1) + temp; } cis-lclient15:~/2012/sim>gcc recurse.c cis-lclient15:~/2012/sim>./a.out cis-lclient15:~/2012/sim>echo $? 55 cis-lclient15:~/2012/sim> In function main(), the statement: return recurse(ten); invokes recurse() with num equal to 10. Function recurse() returns the value 55 to main() and main() returns the number 55 to the shell as its completion code. As shown above, this value is available as the shell variable $?. cis-lclient15:~/2012/sim>./a.out cis-lclient15:~/2012/sim>echo $? 55 Local variables such as temp in function recurse() are stored on the stack and space for such variables is reserved each time function recurse() is entered. As a result, the value of temp is preserved even after the recursive call to recurse(). return recurse(temp-1) + temp; (Each call to recurse() actually adds three items to the stack – a copy (num) of the input parameter, the return address to main(), and space for the local variable temp. Because num is copy of the input parameter (and not the original), recurse() is free to modify num and we could actually eliminate temp and use num instead). It is straightforward to convert the C code into a similar assembly and machine language program. recurse.sim5 – input an integer n and output 1+2+3+…+n. 000 5010 main: lda 10 %r1 = 10 001 9001 mvrr %r0,%r1 % 002 5006 lda recurse %r0=recurse(%r1) 003 9600 call %r0 004 8100 out %r0 output(%r0) 005 0000 halt return 006 8801 recurse: push %r1 temp=%r1 007 7201 skeq %r1 if (%r1 == 0) 008 6010 jmp notdone 009 8200 clr %r0 return 0 010 8909 ret 011 8401 notdone: dec %r1 %r1-- 012 5009 lda recurse %r0=recurse(%r1) 013 9600 call %r0 014 8901 pop %r1 return %r0+temp 015 9410 addr %r1,%r0 016 8909 ret 000 .end main We need to be a bit careful about %r0 because we are using it for two different purposes – to hold the function address during a call and to hold the value returned from the function. However, in this particular program, all of the calls occur before any of the returns so there is no conflict. In a more complex program, it might be a good idea to either (1) return function results in some other register such as %r1 or (2) immediately save the value returned in %r0 in some other register or on the stack. 5.6 SIM5 QUESTIONS AND PROBLEMS The following questions assume that you are designing a new and improved SIM6 instruction set. You should indicate whether your new instructions are backward compatible or not and justify your decision. Similarly, if your new instructions eliminate any functionality of SIM5 instructions, you should justify your decision 1. The skip instructions with format 7n0s have an unused digit (0) in the third position. Can you suggest one or two useful ways to use this digit to make the family more “powerful” without losing any currant functionality? 2. The single register instructions with format 8n0d or 8n0s also have an unused digit in the third position. Can make good use of this digit for any or all of the single register family. 3. The two instruction family (9nsd) has three open slots for new instructions. Which three instructions would you add (and why did you pick those three). 4. It would be convenient to have a call instruction with a one digit op code followed by a three digit address so that the address of the function is included in the call statement. This would allow the statements “lda mult, call %r0: to be replaced with “call mult”. Can you find several alternative ways to implement . call mult” by revising the SIM5 instruction set. Select the alternative that you think is “best” and explain why it is best. 5. Recall that the processor begins a memory fetch or store operation by sending memory a 3-digit address. To allow programs to be relocated more easily, consider adding a “base register” to SIM5 that adds a constant to the address used in a fetch or store operation. For example, if the base register contained the number 500, a program that attempted to load or store the word in addess 012 (the virtual address) would end up fetching or storing from address 5012 (the physical address). To implement this change in SIM5, we would add a variable “int base = 500;” and change every memory reference memory[exp] into memory[((exp)+base)%MEMSIZE]. a. If base were initialized to 500, what memory cells would recurse.sim5 use (1) for code and (2) for the stack? b. Would every program written for SIM1 through SIM5 still execute properly with base initialized to 500? c. Would all programs execute properly with base initialized to any value? d. Is there any way for a program to determine that it has been relocated (i.e., that base is not equal to zero). 6. Write a SIM5 assembly language main program main() which reads two integers into %r1 and %r2, calls the function %r0=max(%r1,%r2), and prints the result in %r0. 7. Write the SIM5 function %r0=max(%r1,%r2) which sets %r0 equal to the maximum of %r1 and %r2 8. Write a SIM5 assembly language program that inputs a number n and outputs factorial n or n!.The function main() should input a number, call function %r0=factor(%r1) and output the result. Recursive function factor() should call function mult() to do the multiplication. a. What is the largest value for n that produces a correct result. b. What is the smallest (positive) value for n that causes the program to “crash” (not produce any result, correct or not). 5.7 SIM5 PRACTICE QUIZ 1. The addition of the stack instructions (push, pop, call, and ret) can make assembly language debugging a challenge. Like any SIM5 program, each of the following programs will either (1) halt, (2) execute an illegal instruction, (3) pause at an input instruction waiting for data, or (4) terminate when MAXCNT instructions have been executed. If MAXCNT is very large, executing more than MAXCNT instructions is almost always the result of an infinite loop. Assuming each of the following programs begins execution at address 000, indicate how it will terminate (halt, illegal, waiting for data, or infinite loop) and specify the address (or range of addresses for infinite loops) of the relevant instruction. start: pop %r9 end start start: jsr %r7 end start start: jsr %r5 end start start: push %r9 push %r9 pop %r9 end start start: lda start jsr %r0 end start start: jsr sub sub: jsr start end start 3. Assume that recurse.sim5 initialized %r0 to 4 (instead of 10) and calls recurse(). Show the values that would be on the stack and the value of the stack pointer when recurse() is entered for the last time with %r1 equal to zero (and the last item pushed is the zero in %r1).