1Chapter 10The Stack andMore...Based on slides © McGraw-HillAdditional material © 2004/2005 Lewis/Martin 10-2CSE 240Next SemesterYes• CSE 121/131: Programming Languages and Techniques II• CSE 260: Math. Foundations of CS• CSE 371/372: Digital Systems Organization and DesignMaybe• CSE 112: Networked Life• CSE 313: Computational Linear Algebra (Math 114)• CSE 341: Intro. to Compilers and Interpreters (120/121, 260,time change!)• CSE 377: Virt. World Design (no freshman, strong programming)• CSE 391: Introduction to Artificial Intelligence (121, 262?)• CSE 399/001: Computer Vision (anal. geom, lin. alg., Math 114,115, 240,or perm)Probably not• CSE 320: Introduction to Algorithms (262 or A- in 260)• CSE 398: Quantum Computing and Information Science (260,261?,262,Math 240, and permission)• CSE 455: Internet and Web Systems (120/121, 330, 380)10-3CSE 240To Muddle (According to Webster)Main Entry: 1 mud·dlePronunciation: 'm&-d&lFunction: verbInflected Form(s): mud·dled; mud·dling /'m&d-li[ng], 'm&-d&l-i[ng]/Etymology: probably from obsolete Dutch moddelen, from Middle Dutch,from modde mud; akin to Middle Low German muddetransitive senses1 : to make turbid or muddy2 : to befog or stupefy especially with liquor3 : to mix confusedly4 : to make a mess of : BUNGLEintransitive senses : to think or act in a confused aimless way- mud·dler /'m&d-l&r, 'm&-d&l-&r/ noun10-4CSE 240Review: Using MemoryMemory• Just a big “array”• “Indexed” by address• Accessed with loads and storesLD/LDR/LDI• Read a word out of memory• Use different addressing modeST/STR/STI• Place a word in memory• Use different addressing modex00A0x5007x0201x0203x3002Value. . .x5007x0201x0203x3002x0000x0001x0002x0003x0004xFFFCxFFFDxFFFExFFFFAddressMemory210-5CSE 240Review: Using Memory (cont.)Problem• What if the memory you want to access is far away?• LD/ST won’t work (PC-relative)• LDR/STR won’t work alone (need to get address in register)Solution• Place address of far away value nearby• Load address, then load/store from thatx0000xFE00x0000. . .x8000x0000x3020x3021x3022xFE00xFE01.ORIG x3000. . .LD R3, SOMELABLDR R2, R3, #0. . .SOMELAB .FILL xFE00. . ..ORIG x3000. . .LDI R2, SOMELAB. . .SOMELAB .FILL xFE00. . .=At x3021xFE00x800010-6CSE 240Review: Using Memory (cont.);; Input key ASCIIUP_KEY .FILL x0077 ; Up - WDOWN_KEY .FILL x0073 ; Down - SLEFT_KEY .FILL x0061 ; Left - ARIGHT_KEY .FILL x0064 ; Right - DROT_LEFT_KEY .FILL x006B ; Rotate Left (Counterclockwise) - KROT_RIGHT_KEY .FILL x006C ; Rotate Right (Clockwise) - LQUIT_KEY .FILL x002A ; Quit - *LD R2, UP_KEY ; load ASCII of ‘w’ into R2Constant “local variables”10-7CSE 240Review: Using Memory (Summary)Addresses• Labels allow programmer to refer to addresses• Memory and registers may contain addresses• It’s up to programmer to know difference• It’s up to programmer to use appropriate load/store instructionsBottom line• Don’t be a muddler!• Without mastery, C programming not possible• Without C programming, CSE 381 hurts!!!• Working on tutors!!!10-8CSE 240Problems?What’s the problem with. . . recursion?Main . . .JSR FooNext . . .Foo ST R7, SaveR7AND R0, R0, #0. . .JSR FooAfter . . .LD R7, SaveR7RETSave7 .FILL #0• First call to Foo (SaveR7contains address of Next)• Second call to Foo (SaveR7contains address of After)• First return from Foo (returnsto After)• Second return from Foo(returns to After again!!!)310-9CSE 240RecursionNeed• Per-subroutine-invocation data space (activation record)Approach• Allocate new activation record on a stack whenever a subroutineis called• Subroutine uses its own activation record to hold invocation-specific data (e.g., local variables, saved registers)Note• Given that Breakout is recursive, we will need activation records10-10CSE 240Big PictureEach subroutine invocation gets its own activation record. . . but how?Main . . .JSR FooNext . . .Foo ST R7, SaveR7AND R0, R0, #0ST R0, Counter. . .JSR FooAfter . . .LD R7, SaveR7RETSaveR7 .FILL #0Counter .FILL #0. . .MainSaveR7: NextCounter: 0FooSaveR7: AfterCounter: 6Foo10-11CSE 240Stacks (Review)A LIFO (last-in first-out) storage structure• The first thing you put in is the last thing you take out• The last thing you put in is the first thing you take outTwo main operationsPUSH: add an item to the stackPOP: remove an item from the stack10-12CSE 240A Physical StackCoin holderLast quarter in is the first quarter out (LIFO)1995 1996199819821995199819821995Initial State AfterOne PushAfter Three More PushesAfterOne Pop410-13CSE 240A Software StackData items don't move in memory, just our idea aboutwhere TOP of the stack is/ / / / / // / / / / // / / / / // / / / / // / / / / /TOPInitial State#18/ / / / / // / / / / // / / / / // / / / / /TOPAfterOne Push#18#31#5#12/ / / / / /TOPAfter Three More Pushes#18#31#5#12/ / / / / /TOPAfterTwo Popsx3FFF x4000 x4003 x4001R6 R6 R6 R6By convention, R6 holds the Top of Stack (TOS) pointer10-14CSE 240Basic Push and Pop CodePush ADD R6, R6, #1 ; increment stack ptr STR R0, R6, #0 ; store data (R0)Pop LDR R0, R6, #0 ; load data from TOS ADD R6, R6, #-1 ; decrement stack ptrNote• Stacks can grow in either direction (toward higher address ortoward lower addresses)10-15CSE 240Activation Records in a StackMain . . .JSR FooNext . . .Foo ADD R6,R6,#-3ST R7,R6,#0ST R0,R6,#1AND R0, R0, #0ST R0, R6,#2. . .JSR FooAfter . . .LD R0,R6,#1LD R7, R6,#0ADD R6,R6,#3RetR6 (x4FFF)Next70Foo(SaveR7)(SaveR0)(Counter)After05Foo(SaveR7)(SaveR0)(Counter)MainR6 (x4FFC)R6 (x4FF9)R6 (x4FFC)R6 (x4FFF)Allocate activation recordUse activation recordDeallocate activation