Computer Systems
Topic – Subroutines and Stacks
Dr. Mian M. Hamayun
M.M. .ac.uk
Credits to:
&
Slide #2 of 43
Lecture Objectives
To introduce the fundamentals concepts of subroutines
and how they are implemented using stacks.
Slide #3 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 #4 of 43
Subroutines (Methods) – Example
Slide #5 of 43
Subroutines (Methods)
Slide #6 of 43
Subroutines (Methods)
Slide #7 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 #8 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 #9 of 43
Storing the Return Address
Idea #1: In each subroutine, its first byte is used to
store the return address
Slide #10 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 #11 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.
https://en.wikipedia.org/wiki/Fortran
https://en.wikipedia.org/wiki/ALGOL
Slide #12 of 43
What is a Stack?
Slide #13 of 43
How Stacks Work?
A stack can flexibly store a variable number of bytes
LIFO = Last In, First Out (aka FILO)
9
-6
10
2
a b c d
42 54 13 27
push a
42
9
-6
10
2
Slide #14 of 43
How Stacks Work?
A stack can flexibly store a variable number of bytes
LIFO = Last In, First Out (aka FILO)
42
9
-6
10
2
a b c d
42 54 13 27
push c
13
42
9
-6
10
2
Slide #15 of 43
How Stacks Work?
A stack can flexibly store a variable number of bytes
LIFO = Last In, First Out (aka FILO)
13
42
9
-6
10
2
a b c d
42 13 13 27
pop b
42
9
-6
10
2
Slide #16 of 43
How Stacks Work?
A stack can flexibly store a variable number of bytes
LIFO = Last In, First Out (aka FILO)
42
9
-6
10
2
a b c d
42 13 13 42
pop d
9
-6
10
2
Slide #17 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 #18 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 #19 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 #20 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 #21 of 43
Storing the Return Address
Idea #2: Store the return address on a stack.
Slide #22 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 #23 of 43
Saving Registers – Stack Frame
Slide #24 of 43
Saving Registers – Stack Frame
Slide #25 of 43
Toy CPU (For the Exercises)
Slide #26 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 #27 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 #28 of 43
Stacks for Calculation
Example:
Slide #29 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
8
3
6
10
Apply +
11
6
10
Slide #30 of 43
RPN for the Example
Slide #31 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 #32 of 43
Notation for Operand Stack
To show what an operation does to the stack:
e.g. subtraction
Slide #33 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)
https://en.wikipedia.org/wiki/Order_of_operations
https://www.theregister.co.uk/Print/2014/01/03/ten_classic_calcutors/
https://en.wikipedia.org/wiki/Forth_(programming_language
Slide #34 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 #35 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 #36 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 #37 of 43
Machine Instructions as Stack Operators
[Forget the Toy CPU – remember these mnemonics (JVM)]
Slide #38 of 43
Example of a Stack Machine (JVM mnemonics)
Slide #39 of 43
Bitwise Boolean Operations
Slide #40 of 43
Jumps
Unconditional jumps
Operand stack is not used!
Conditional jumps
Slide #41 of 43
Conditional Jumps with Other Comparisons
Slide #42 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 #43 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
https://en.wikipedia.org/wiki/Shunting-yard_algorithm
Slide 1
Slide 2
Slide 3
Slide 4
Slide 5
Slide 6
Slide 7
Slide 8
Slide 9
Slide 10
Slide 11
Slide 12
Slide 13
Slide 14
Slide 15
Slide 16
Slide 17
Slide 18
Slide 19
Slide 20
Slide 21
Slide 22
Slide 23
Slide 24
Slide 25
Slide 26
Slide 27
Slide 28
Slide 29
Slide 30
Slide 31
Slide 32
Slide 33
Slide 34
Slide 35
Slide 36
Slide 37
Slide 38
Slide 39
Slide 40
Slide 41
Slide 42
Slide 43