Phần cứng - Chapter 10: The stack

Chapter 10 The StackStack data structureActivation records and function invocation (Chapter 14)Stack Data StructureLIFO (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)2PUSH & POPPOP, including underflow checkIf (( 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 checkIf (( TOS - MAX) == 0)R5 = 1 /* R5 gets error code */Else {TOS = TOS + 1;C[TOS] = r0; /*TOS gets value in R0*/R5 = 0;EMPTYTOSMAX3PUSH & POP in LC-2 - 1POP 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 successBASE .FILL xC000 ;Base has -x4000MAX .FILL xBFFC ;Max has -x40044PUSH & POP in LC-2 - 2PUSH 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 x0000Sv2 .FILL x00005PUSH & POP in LC-2 - 3success LD R1,Sv1 ;Restore reg values LD R2,Sv2 ; AND R5,R5,#0 ;R5 <-- success RET ;fail LD R1,Sv1 ;Restore reg values LD R2,Sv2 AND R5,R5,#0 ADD R5,R5,#1 ;R5 <-- fail RET6Activation RecordsA RecordA collection of contiguous memory locations treated as one entityThe struct construct in C/C++ describes a recordActivation RecordIs allocated for each function invocation in memoryThe 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 record7Activation Recordreturn addressreturn valuedynamic linkabxyzFormalparametersLocalvariablesfunction This (int a, int b){ int x, y, z; function body .. return z;}8Examplefunction This (int a, int b){ int x, y, z; y = That(a); .. return z;}function That (int a){ int x; body .. return x;}9Example - 2return addressreturn valuedynamic linkabxyzactivation recordof ThisR6return addressreturn valuedynamic linkabxyzreturn addressactivation recordof Thisx4050axreturn valueactivation recordof ThatR6x4050When This is executingAfter This calls That When That terminates10