Lecture Introduction to computing systems (from bits & gates to C & beyond) - Chapter 10: The stack. The main contents of the dissertation consist of three main parts: Stack data structure, interrupt I/O (again!), arithmetic using a stack. | Chapter 10 The Stack Stack data structure Activation records and function invocation (Chapter 14) Stack Data Structure LIFO (last in - first out) Operations: Push (enter item at top of stack) Pop (remove item from top of stack) Error conditions: Underflow (try to pop from empty stack) Overflow (try to push onto full stack) A register (eg. R6) holds address of top of stack (TOS) 10 - PUSH & POP POP, including underflow check If (( TOS - EMPTY) == 0) R5 = 1 /* R5 gets error code */ Else { R0 = C[TOS]; /*R0 gets value at TOS*/ TOS = TOS - 1; R5 = 0; PUSH, including overflow check If (( TOS - MAX) == 0) R5 = 1 /* R5 gets error code */ Else { TOS = TOS + 1; C[TOS] = r0; /*TOS gets value in R0*/ R5 = 0; EMPTY TOS MAX 10 - PUSH & POP in LC-2 - 1 POP ST R2,Sv2 ;save, needed by POP ST R1,Sv1 ;save, needed by POP LD R1,BASE ;BASE contains -x4000 ADD R1,R1,#1 ;R1 has -x3FFF ADD R2,R6,R1 ;Compare SP to 3FFF BRz fail ;Branch if stk empty LDR R0,R6,#0 ;The actual ‘pop’ ADD R6,R6,#-1 ;Adjust stack pointer BRnzp success BASE .FILL xC000 ;Base has -x4000 MAX .FILL xBFFC ;Max has -x4004 10 - PUSH & POP in LC-2 - 2 PUSH ST R2,Sv2 ;needed by PUSH ST R1,Sv1 ;needed by PUSH LD R1,MAX ;MAX has -4004 ADD R2,R6,R1 ;Compare SP to x4004 BRz fail ;Branch is stk full ADD R6,R6,#1 ;Adjust SP STR R0,R6,#0 ;The actual ‘push’ Sv1 .FILL x0000 Sv2 .FILL x0000 10 - PUSH & POP in LC-2 - 3 success LD R1,Sv1 ;Restore reg values LD R2,Sv2 ; AND R5,R5,#0 ;R5 10 - Activation Records A Record A collection of contiguous memory locations treated as one entity The struct construct in C/C++ describes a record Activation Record Is allocated for each function invocation in memory The area of memory where activation records are allocated is called the stack memory In LC-2, R6 is the stack pointer: it points to the top of the stack (TOS) Each element on the stack is an activation record | Chapter 10 The Stack Stack data structure Activation records and function invocation (Chapter 14) Stack Data Structure LIFO (last in - first out) Operations: Push (enter item at top of stack) Pop (remove item from top of stack) Error conditions: Underflow (try to pop from empty stack) Overflow (try to push onto full stack) A register (eg. R6) holds address of top of stack (TOS) 10 - PUSH & POP POP, including underflow check If (( TOS - EMPTY) == 0) R5 = 1 /* R5 gets error code */ Else { R0 = C[TOS]; /*R0 gets value at TOS*/ TOS = TOS - 1; R5 = 0; PUSH, including overflow check If (( TOS - MAX) == 0) R5 = 1 /* R5 gets error code */ Else { TOS = TOS + 1; C[TOS] = r0; /*TOS gets value in R0*/ R5 = 0; EMPTY TOS MAX 10 - PUSH & POP in LC-2 - 1 POP ST R2,Sv2 ;save, needed by POP ST R1,Sv1 ;save, needed by POP LD R1,BASE ;BASE contains -x4000 ADD R1,R1,#1 ;R1 has -x3FFF ADD R2,R6,R1 ;Compare SP to 3FFF BRz fail ;Branch if stk empty LDR R0,R6,#0 ;The actual ‘pop’ ADD R6,R6,#-1 ;Adjust
