Computer Systems
Topic – Subroutines and Stacks
Dr. Mian M. Hamayun
M.M.Hamayun@cs.bham.ac.uk
Credits to:
Ata Kaban & Steve Vickers
Lecture Objectives
To introduce the fundamentals concepts of subroutines and how they are implemented using stacks.
Slide #2 of 43
Lecture Outline
How a Subroutine Works? Call / Return Instructions
Introduction to Stacks Saving Registers Stacks for Calculation
Reverse Polish Notation
Bitwise Boolean Operations
Conditional & Unconditional Jumps Summary
Slide #3 of 43
Subroutines (Methods) – Example
Slide #4 of 43
Subroutines (Methods)
Slide #5 of 43
Subroutines (Methods)
Slide #6 of 43
Subroutines (Methods)
Could jump to 94 for subroutine, but how to know where to jump back afterwards?
Must store the return address somewhere.
Slide #7 of 43
Call / Return Instructions
Two new operations:
call operand : Like jump, but stores current PC value
(the return address) somewhere suitable.
ret : Read return address from where it was stored, and load it into PC.
Slide #8 of 43
Storing the Return Address
Idea #1: In each subroutine, its first byte is used to store the return address
Slide #9 of 43
Disadvantage of Idea #1
Can only store one return address
Consequence: subroutine cannot call itself
If it were to call itself it would need to store 2 return addresses
Slide #10 of 43
History: 2 Early Programming Languages
FORTRAN (“FORmula TRANslation”)
Used jumps (GOTO), conditional jumps
Banned recursion (i.e. for a method to call itself) to allow idea 1.
Algol (“Algorithmic language”)
structured programming (if .. then .. else, etc.) Allowed recursion
Initially, FORTRAN was more successful, but modern languages (e.g. C, Java) took forward the ideas from Algol.
Slide #11 of 43
What is a Stack?
Slide #12 of 43
How Stacks Work?
A stack can flexibly store a variable number of bytes LIFO = Last In, First Out (aka FILO)
a
b
c
d
42
54
13
27
42
9
-6
10
2
9
-6
10
2
push a
Slide #13 of 43
How Stacks Work?
A stack can flexibly store a variable number of bytes LIFO = Last In, First Out (aka FILO)
a
b
c
d
42
54
13
27
13
42
9
-6
10
2
42
9
-6
10
2
push c
Slide #14 of 43
How Stacks Work?
A stack can flexibly store a variable number of bytes LIFO = Last In, First Out (aka FILO)
a
b
c
d
42
13
13
27
42
9
-6
10
2
13
42
9
-6
10
2
pop b
Slide #15 of 43
How Stacks Work?
A stack can flexibly store a variable number of bytes LIFO = Last In, First Out (aka FILO)
a
b
c
d
42
13
13
42
9
-6
10
2
42
9
-6
10
2
pop d
Slide #16 of 43
In Memory
Give CPU another register
sp (stack pointer) – shows where top is
Don’t need to know where bottom is!
Provided that we are careful: only pop when you know you’ve pushed
Slide #17 of 43
In Memory
To push a value X:
Write the value to memory at address sp Add 1 to sp
To pop a value:
Subtract 1 from sp
Read value from memory at address sp
Slide #18 of 43
In Memory – Push a Value
To push a value X:
Write the value to memory at address sp Add 1 to sp
Slide #19 of 43
In Memory – Pop a Value
To pop a value:
Subtract 1 from sp
Read value from memory at address sp
The value read is Y.
Still in memory but will be overwritten by a later push operation.
Slide #20 of 43
Storing the Return Address
Idea #2: Store the return address on a stack.
Slide #21 of 43
Why should we Save Registers?
Subroutine may need to use registers for its calculations.
But previous register values are needed on return!
Common pattern for subroutines: Start by pushing all registers
Pop them back before return
Return address & saved registers = stack frame Java method-calls develop this idea.
Slide #22 of 43
Saving Registers – Stack Frame
Slide #23 of 43
Saving Registers – Stack Frame
Slide #24 of 43
Toy CPU (For the Exercises)
Slide #25 of 43
Exercise #1 (Home Work)
Write mnemonics and machine code (for the Toy CPU) for the following tasks:
a) A subroutine, starting at location 10 (hex) that sums memory locations, then stores the result after them. Assume that the calling routine initialized the register b with the address of the memory location of the summands, and the register c with the number of them. Don’t forget the return instruction.
b) A main routine, starting at location 00, that calls the subroutine twice: once for summing 4 locations starting at 2A, and once for summing 6 locations starting at 38.
Slide #26 of 43
Exercise #2 (Home Work)
Your answer to Ex. 1(a) will have used the a, b and c registers in its own calculations. Suppose this is inconvenient for the main program and it would be better not to lose the values that those three registers had when the subroutine was stored.
Rewrite the subroutine so that it pushes the three registers at the start, saving their values on the stack, and then pops them back at the end so that the calling routine gets them back unchanged. Make sure you pop them in the right order!
Slide #27 of 43
Stacks for Calculation
Example:
Slide #28 of 43
Reverse Polish Notation (RPN)
Order of operations is as written
No brackets needed
Powerful use of stack (= operand stack) to store intermediate results
If its a Number or Variable: push it on the stack
If its an Operation: apply to the top elements on stack
& push result back on the stack
11
6
10
8
3
6
10
Apply +
Slide #29 of 43
RPN for the Example
Slide #30 of 43
How to use RPN along with a Stack?
Suppose that x has value 3, and y has value 4
Now, evaluate the expression. (Top of stack is on right.)
Slide #31 of 43
Notation for Operand Stack
To show what an operation does to the stack: e.g. subtraction
Slide #32 of 43
More on Reverse Polish Notation
Any expression can be converted to Reverse Polish Notation and then its easy to execute with a stack.
Applications
Humans use reverse Polish directly (See Details)
e.g. some pocket calculators – HP in 1970s (HP-41C) https://www.theregister.co.uk/Print/2014/01/03/ten_classic_calcutors/
Forth programming language has two stacks:
Operand stacks for calculations
Return stack for module calls
More details: https://en.wikipedia.org/wiki/Forth_(programming_language)
Slide #33 of 43
Applications of Reverse Polish Notation
Compile to a reverse Polish form that is then executed. e.g. Postscript format, for printable files
► executed by printers e.g. Java byte code
► uses operand stacks for calculations
In Java, each method call has its own operand stack.
Slide #34 of 43
Stack instead of Registers (Stack Machines)
Use 2 stacks
return stack for subroutine return
operand stack for Reverse Polish calculations
Don’t need a,b,c registers Advantages
► More space for calculations
► Opcodes don’t need to specify registers Disadvantages
► Harder to know where things are on the stack
Slide #35 of 43
What is an Operand?
Underlying meaning:
Whatever an operator operates on?
Two meanings here (don’t confuse them):
1) Extra bytes after the instruction opcode in memory,
e.g.
ld a 42
2) Entries in the operand stack.
Slide #36 of 43
Machine Instructions as Stack Operators
[Forget the Toy CPU – remember these mnemonics (JVM)]
Slide #37 of 43
Example of a Stack Machine (JVM mnemonics)
Slide #38 of 43
Bitwise Boolean Operations
Slide #39 of 43
Jumps
Unconditional jumps Operand stack is not used!
Conditional jumps
Slide #40 of 43
Conditional Jumps with Other Comparisons
Slide #41 of 43
Summary
We have now seen:
What is a subroutine and how it is implemented.
What is a stack and how it is used for implementing subroutines.
What is the importance of saving registers and how these can be used to perform computations.
What is reverse polish notation and how it is used to to do calculations using an operand stack.
What is a stack machine and how it operates using a stack instead of registers.
What are Bitwise Boolean operations and Jump instructions.
Slide #42 of 43
Notes on Exercises 3 & 4
You will need to use an algorithm to convert math expressions from the usual “infix” notation to reverse- Polish. This algo is called Dijkstra’s Shunting-Yard Algorithm.
You can also read the Wikipedia page on this algo https://en.wikipedia.org/wiki/Shunting-yard_algorithm
Slide #43 of 43