Assembly Language
Chapter 10
And, Finally…
The Stack
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Stack: An Abstract Data Type
An important abstraction that you will encounter
in many applications.
We will describe three uses:
Interrupt-Driven I/O
The rest of the story…
Evaluating arithmetic expressions
Store intermediate results on stack instead of in registers
Data type conversion
2’s comp binary to ASCII strings
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Stacks
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 out.
This means of access is what defines a stack,
not the specific implementation.
Two main operations:
PUSH: add an item to the stack
POP: remove an item from the stack
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
A Physical Stack
Coin rest in the arm of an automobile
First quarter out is the last quarter in.
1995
1996
1998
1982
1995
1998
1982
1995
Initial State
After
One Push
After Three
More Pushes
After
One Pop
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
A Hardware Implementation
Data items move between registers
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
Yes
Empty:
TOP
#18
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
No
Empty:
TOP
#12
#5
#31
#18
/ / / / / /
No
Empty:
TOP
#31
#18
/ / / / / /
/ / / / / /
/ / / / / /
No
Empty:
TOP
Initial State
After
One Push
After Three
More Pushes
After
Two Pops
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
A Software Implementation
Data items don’t move in memory,
just our idea about there the TOP of the stack is.
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
TOP
/ / / / / /
/ / / / / /
/ / / / / /
#18
/ / / / / /
TOP
#12
#5
#31
#18
/ / / / / /
TOP
#12
#5
#31
#18
/ / / / / /
TOP
Initial State
After
One Push
After Three
More Pushes
After
Two Pops
x4000
x3FFF
x3FFC
x3FFE
R6
R6
R6
R6
By convention, R6 holds the Top of Stack (TOS) pointer.
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Basic Push and Pop Code
For our implementation, stack grows downward
(when item added, TOS moves closer to 0)
Push
ADD R6, R6, #-1 ; decrement stack ptr
STR R0, R6, #0 ; store data (R0)
Pop
LDR R0, R6, #0 ; load data from TOS
ADD R6, R6, #1 ; decrement stack ptr
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Pop with Underflow Detection
If we try to pop too many items off the stack,
an underflow condition occurs.
Check for underflow by checking TOS before removing data.
Return status code in R5 (0 for success, 1 for underflow)
POP LD R1, EMPTY ; EMPTY = -x4000
ADD R2, R6, R1 ; Compare stack pointer
BRz FAIL ; with x3FFF
LDR R0, R6, #0
ADD R6, R6, #1
AND R5, R5, #0 ; SUCCESS: R5 = 0
RET
FAIL AND R5, R5, #0 ; FAIL: R5 = 1
ADD R5, R5, #1
RET
EMPTY .FILL xC000
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Push with Overflow Detection
If we try to push too many items onto the stack,
an overflow condition occurs.
Check for underflow by checking TOS before adding data.
Return status code in R5 (0 for success, 1 for overflow)
PUSH LD R1, MAX ; MAX = -x3FFB
ADD R2, R6, R1 ; Compare stack pointer
BRz FAIL ; with x3FFF
ADD R6, R6, #-1
STR R0, R6, #0
AND R5, R5, #0 ; SUCCESS: R5 = 0
RET
FAIL AND R5, R5, #0 ; FAIL: R5 = 1
ADD R5, R5, #1
RET
MAX .FILL xC005
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Interrupt-Driven I/O (Part 2)
Interrupts were introduced in Chapter 8.
External device signals need to be serviced.
Processor saves state and starts service routine.
When finished, processor restores state and resumes program.
Chapter 8 didn’t explain how (2) and (3) occur,
because it involves a stack.
Now, we’re ready…
Interrupt is an unscripted subroutine call,
triggered by an external event.
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Processor State
What state is needed to completely capture the
state of a running process?
Processor Status Register
Privilege [15], Priority Level [10:8], Condition Codes [2:0]
Program Counter
Pointer to next instruction to be executed.
Registers
All temporary state of the process that’s not stored in memory.
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Where to Save Processor State?
Can’t use registers.
Programmer doesn’t know when interrupt might occur,
so she can’t prepare by saving critical registers.
When resuming, need to restore state exactly as it was.
Memory allocated by service routine?
Must save state before invoking routine,
so we wouldn’t know where.
Also, interrupts may be nested –
that is, an interrupt service routine might also get interrupted!
Use a stack!
Location of stack “hard-wired”.
Push state to save, pop to restore.
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Supervisor Stack
A special region of memory used as the stack
for interrupt service routines.
Initial Supervisor Stack Pointer (SSP) stored in Saved.SSP.
Another register for storing User Stack Pointer (USP):
Saved.USP.
Want to use R6 as stack pointer.
So that our PUSH/POP routines still work.
When switching from User mode to Supervisor mode
(as result of interrupt), save R6 to Saved.USP.
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Invoking the Service Routine – The Details
If Priv = 1 (user),
Saved.USP = R6, then R6 = Saved.SSP.
Push PSR and PC to Supervisor Stack.
Set PSR[15] = 0 (supervisor mode).
Set PSR[10:8] = priority of interrupt being serviced.
Set PSR[2:0] = 0.
Set MAR = x01vv, where vv = 8-bit interrupt vector
provided by interrupting device (e.g., keyboard = x80).
Load memory location (M[x01vv]) into MDR.
Set PC = MDR; now first instruction of ISR will be fetched.
Note: This all happens between
the STORE RESULT of the last user instruction and
the FETCH of the first ISR instruction.
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Returning from Interrupt
Special instruction – RTI – that restores state.
Pop PC from supervisor stack. (PC = M[R6]; R6 = R6 + 1)
Pop PSR from supervisor stack. (PSR = M[R6]; R6 = R6 + 1)
If PSR[15] = 1, R6 = Saved.USP.
(If going back to user mode, need to restore User Stack Pointer.)
RTI is a privileged instruction.
Can only be executed in Supervisor Mode.
If executed in User Mode, causes an exception.
(More about that later.)
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example (1)
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
/ / / / / /
x3006
PC
Program A
ADD
x3006
Executing ADD at location x3006 when Device B interrupts.
Saved.SSP
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example (2)
/ / / / / /
x3007
PSR for A
/ / / / / /
/ / / / / /
x6200
PC
R6
Program A
ADD
x3006
Saved.USP = R6. R6 = Saved.SSP.
Push PSR and PC onto stack, then transfer to
Device B service routine (at x6200).
x6200
ISR for
Device B
x6210
RTI
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example (3)
/ / / / / /
x3007
PSR for A
/ / / / / /
/ / / / / /
x6203
PC
R6
Program A
ADD
x3006
Executing AND at x6202 when Device C interrupts.
x6200
ISR for
Device B
AND
x6202
x6210
RTI
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example (4)
/ / / / / /
x3007
PSR for A
x6203
PSR for B
x6300
PC
R6
Program A
ADD
x3006
x6200
ISR for
Device B
AND
x6202
ISR for
Device C
Push PSR and PC onto stack, then transfer to
Device C service routine (at x6300).
x6300
x6315
RTI
x6210
RTI
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example (5)
/ / / / / /
x3007
PSR for A
x6203
PSR for B
x6203
PC
R6
Program A
ADD
x3006
x6200
ISR for
Device B
AND
x6202
ISR for
Device C
Execute RTI at x6315; pop PC and PSR from stack.
x6300
x6315
RTI
x6210
RTI
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example (6)
/ / / / / /
x3007
PSR for A
x6203
PSR for B
x3007
PC
Program A
ADD
x3006
x6200
ISR for
Device B
AND
x6202
ISR for
Device C
Execute RTI at x6210; pop PSR and PC from stack.
Restore R6. Continue Program A as if nothing happened.
x6300
x6315
RTI
x6210
RTI
Saved.SSP
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Exception: Internal Interrupt
When something unexpected happens
inside the processor, it may cause an exception.
Examples:
Privileged operation (e.g., RTI in user mode)
Executing an illegal opcode
Divide by zero
Accessing an illegal address (e.g., protected system memory)
Handled just like an interrupt
Vector is determined internally by type of exception
Priority is the same as running program
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Arithmetic Using a Stack
Instead of registers, some ISA’s use a stack for
source and destination operations: a zero-address machine.
Example:
ADD instruction pops two numbers from the stack,
adds them, and pushes the result to the stack.
Evaluating (A+B)·(C+D) using a stack:
(1) push A
(2) push B
(3) ADD
(4) push C
(5) push D
(6) ADD
(7) MULTIPLY
(8) pop result
Why use a stack?
Limited registers.
Convenient calling convention for subroutines.
Algorithm naturally expressed using FIFO data structure.
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example: OpAdd
POP two values, ADD, then PUSH result.
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Example: OpAdd
OpAdd JSR POP ; Get first operand.
ADD R5,R5,#0 ; Check for POP success.
BRp Exit ; If error, bail.
ADD R1,R0,#0 ; Make room for second.
JSR POP ; Get second operand.
ADD R5,R5,#0 ; Check for POP success.
BRp Restore1 ; If err, restore & bail.
ADD R0,R0,R1 ; Compute sum.
JSR RangeCheck ; Check size.
BRp Restore2 ; If err, restore & bail.
JSR PUSH ; Push sum onto stack.
RET
Restore2 ADD R6,R6,#-1 ; Decr stack ptr (undo POP)
Restore1 ADD R6,R6,#-1 ; Decr stack ptr
Exit RET
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Data Type Conversion
Keyboard input routines read ASCII characters,
not binary values.
Similarly, output routines write ASCII.
Consider this program:
TRAP x23 ; input from keybd
ADD R1, R0, #0 ; move to R1
TRAP x23 ; input from keybd
ADD R0, R1, R0 ; add two inputs
TRAP x21 ; display result
TRAP x25 ; HALT
User inputs 2 and 3 — what happens?
Result displayed: e
Why? ASCII ‘2’ (x32) + ASCII ‘3’ (x33) = ASCII ‘e’ (x65)
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
ASCII to Binary
Useful to deal with mult-digit decimal numbers
Assume we’ve read three ASCII digits (e.g., “259”)
into a memory buffer.
How do we convert this to a number
we can use?
Convert first character to digit (subtract x30)
and multiply by 100.
Convert second character to digit and
multiply by 10.
Convert third character to digit.
Add the three digits together.
x32
x35
x39
‘2’
‘5’
‘9’
ECE 206 – Fall 2001 – G. Byrd
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
Multiplication via a Lookup Table
How can we multiply a number by 100?
One approach:
Add number to itself 100 times.
Another approach:
Add 100 to itself