Document Text Contents
Page 95
CHAPTER S
Stac ks and procedu res
8. 1 I NTRO DUCTION
This chapter first introduces the stack data structure, and then illustrates its
usage with a program to reverse a string using a stack. The techniques to
support procedure calls in MIPS assembly language are then studied.
Procedures allow programs to be broken into smaller more manageable units .
They are fundamental to the development of programs longer than a few
dozen statements. Procedures allow the reuse of the same group of statements
many times by referring to them by name rather than repeating the code. In
addition, procedures make large programs easier to read and understand.
Stack frames, needed to implement procedure calls, are discussed. Two
recursive programs are given that calculate Fibonacci's series and solve the
Towers of Hanoi problem, and example code from a real compiler is discussed.
8.2 T H E STAC K
A stack of data elements is a last in, first out data structure . Items are added
and removed from the top of the stack as shown in Figure 8 . 1 . This is
referred to as pushing and popping the stack. Because the stack is so
frequently used, a special register, the stack pointer $ sp, always holds the
address of the top of the stack. The MIPS stack is upside down - elements
are added at progressively lower memory addresses .
Pushing something on the stack is accomplished by two instructions.
sub $ sp , $ sp , 4
SW $ t Q , ( $ sp )
pushes the word in $ t 0 onto the stack. The sw instruction stores a word into
memory from a register (Figure 8 .2) . The stack pointer is usually incremented
BS
Page 96
86 STACKS AND PROCEDURES
Stack grows �
down from ---- 1---5--1
high memory
7
push 5
push 7
push 6 9�
Figure 8.1 Stack data structure .
Proce s sor
$ t 0 ITIIJ
$ t l
$ t 2 [ill]
I
sw, store word ,
copies a word from
a register into
memory
Figure 8.2 sw: store word instruction.
Memory
Ox l O O l O O O O
Ox1 0 0 1 0 0 0 1
Ox1 0 0 1 0 0 0 2
Ox1 0 0 1 0 0 0 3
Ox1 0 0 1 0 0 0 4
Ox1 0 0 1 0 0 0 5
Ox1 0 0 1 0 0 0 6
Ox1 0 0 1 0 0 0 7
Ox 1 0 0 1 0 0 0 8
Ox1 0 0 1 0 0 0 9
Oxl O O l O O OA
Oxl O O l O O O B
Ox O O l O O O C
Oxl O l O O O D
Oxl O O l O O E
Ox1 0 0 1 0 0 F
Ox1 0 0 1 0 0 1 0
Ox1 0 0 1 0 0 1 1
O x1 0 0 1 0 0 1 2
Ox1 0 0 1 0 0 1 3
Ox1 0 0 1 0 0 1 4
Ox1 0 0 1 0 0 1 5
Ox1 0 0 1 0 0 1 6
Ox1 0 0 1 0 0 1 7
�
�
�
�
I
�
Page 190
1 80 INDEX
reserved 20
return address 20
reloading assembly program 36
rem 78
return address 20 , 92
reverse . a 87-8
RISC chips, design 1 7- 1 8
rol 7 8
rotate left instruction 74
run button 35
Sequin, C. 1 7
SGI 1 8
shift 73, 74
shift amount 59
sign bit 1 2
single stepping 30, 3 6
source code format 25-9
comments 27-8
constants 29
labels 27, 28
operand field 27, 28
operation field 28
source register 59
SPIM 2 1 , 22, 23
stack 1 9, 20, 85-9 1 , 1 1 9
data structure 85 , 86
exam questions 1 32-9
program examples 88-9 1
return address 92
stack frames 93- 1 03
stack pointer 20, 85-7
store instructions 1 48
store word instruction 37, 85 , 86
storing characters 1 4- 1 5
string 25
string constant 29
structure 62
subroutine 3
SW 37, 85 , 86
syntax errors 36
sys c a l l 22 , 29
system call instruction 22, 29
tab 29
target address 59
target register 59
temp . a 4 1-2
temperature, conversion from Celsius to
Fahrenheit 4 1 -2
terminal button 3 5
testing code 3 2
text segment 1 9, 32, 34
Towers of Hanoi 1 1 2- 1 9
trap instructions 1 49
truth tables 74-5
two's complement representation for
negative numbers 1 2- 1 4, 1 6
addition rules 1 2
subtraction rules 1 2, 1 4
two's complement wheel 1 2, 1 3
unconditional jump
Unicode Standard
vcount 97
vowe l . a 95-7
word 1 4
X-Windows 3 1
xor 74
truth table 75
XSPIM 3 1
53 , 58
1 5
control buttons 32, 33
display of current state of
registers 33
starting 32-4
Page 191
Computer Arch itecture Assembly Language Programming
As the best way to gain an understand ng of
how a computer processor works at the lower
Programming
very d ifferent due
Dr John Waldron was a lecturer at
University from 1 99 1 . His first book,
City
l.angeV1n
Equation (with Wf Coffey and Yu P KafmYkov
was published in 1 996.
He is now an academic in the Department of
Computer Science, Trinity College , Dubli
Visit us on the World Wide Web at:
http:// pearso .com
•
Introduction to RISC Assembly Language
Programming
is based around the M I PS RISC processor,
a s imple, clean RISC processor whose
architecture and assembly language is easy
to learn and u nderstand
speeds up the learn ing process by enabl ing
the reader to start writ ing simple assembly
language programs early, while assuming no
prior knowledge of computer programming
l inks with an automatic program testing system,
allowing a lecturer to set programming questions
and mark the assignments automatical ly, or a
reader to test a M I PS assembly language
program against numerous test i nputs
uses the SP IM simulator, a freely avai lable virtual
machine that al lows users to write and s imulate
running M I PS R2000/R3000 assembly language
programs on PC, Macintosh or U N I X p latforms,
with excellent source-level debugging tools
contains a large number of example programs
and programming questions
is supported by relate� software freely available
via the Web:
dron/I ral/cahom
I S B N 0 - 2 0 1 - 3 9 8 2 8 - 1_
9 0 0 0 O >
9 7802 0 1 3 9 8 2 8 1
CHAPTER S
Stac ks and procedu res
8. 1 I NTRO DUCTION
This chapter first introduces the stack data structure, and then illustrates its
usage with a program to reverse a string using a stack. The techniques to
support procedure calls in MIPS assembly language are then studied.
Procedures allow programs to be broken into smaller more manageable units .
They are fundamental to the development of programs longer than a few
dozen statements. Procedures allow the reuse of the same group of statements
many times by referring to them by name rather than repeating the code. In
addition, procedures make large programs easier to read and understand.
Stack frames, needed to implement procedure calls, are discussed. Two
recursive programs are given that calculate Fibonacci's series and solve the
Towers of Hanoi problem, and example code from a real compiler is discussed.
8.2 T H E STAC K
A stack of data elements is a last in, first out data structure . Items are added
and removed from the top of the stack as shown in Figure 8 . 1 . This is
referred to as pushing and popping the stack. Because the stack is so
frequently used, a special register, the stack pointer $ sp, always holds the
address of the top of the stack. The MIPS stack is upside down - elements
are added at progressively lower memory addresses .
Pushing something on the stack is accomplished by two instructions.
sub $ sp , $ sp , 4
SW $ t Q , ( $ sp )
pushes the word in $ t 0 onto the stack. The sw instruction stores a word into
memory from a register (Figure 8 .2) . The stack pointer is usually incremented
BS
Page 96
86 STACKS AND PROCEDURES
Stack grows �
down from ---- 1---5--1
high memory
7
push 5
push 7
push 6 9�
Figure 8.1 Stack data structure .
Proce s sor
$ t 0 ITIIJ
$ t l
$ t 2 [ill]
I
sw, store word ,
copies a word from
a register into
memory
Figure 8.2 sw: store word instruction.
Memory
Ox l O O l O O O O
Ox1 0 0 1 0 0 0 1
Ox1 0 0 1 0 0 0 2
Ox1 0 0 1 0 0 0 3
Ox1 0 0 1 0 0 0 4
Ox1 0 0 1 0 0 0 5
Ox1 0 0 1 0 0 0 6
Ox1 0 0 1 0 0 0 7
Ox 1 0 0 1 0 0 0 8
Ox1 0 0 1 0 0 0 9
Oxl O O l O O OA
Oxl O O l O O O B
Ox O O l O O O C
Oxl O l O O O D
Oxl O O l O O E
Ox1 0 0 1 0 0 F
Ox1 0 0 1 0 0 1 0
Ox1 0 0 1 0 0 1 1
O x1 0 0 1 0 0 1 2
Ox1 0 0 1 0 0 1 3
Ox1 0 0 1 0 0 1 4
Ox1 0 0 1 0 0 1 5
Ox1 0 0 1 0 0 1 6
Ox1 0 0 1 0 0 1 7
�
�
�
�
I
�
Page 190
1 80 INDEX
reserved 20
return address 20
reloading assembly program 36
rem 78
return address 20 , 92
reverse . a 87-8
RISC chips, design 1 7- 1 8
rol 7 8
rotate left instruction 74
run button 35
Sequin, C. 1 7
SGI 1 8
shift 73, 74
shift amount 59
sign bit 1 2
single stepping 30, 3 6
source code format 25-9
comments 27-8
constants 29
labels 27, 28
operand field 27, 28
operation field 28
source register 59
SPIM 2 1 , 22, 23
stack 1 9, 20, 85-9 1 , 1 1 9
data structure 85 , 86
exam questions 1 32-9
program examples 88-9 1
return address 92
stack frames 93- 1 03
stack pointer 20, 85-7
store instructions 1 48
store word instruction 37, 85 , 86
storing characters 1 4- 1 5
string 25
string constant 29
structure 62
subroutine 3
SW 37, 85 , 86
syntax errors 36
sys c a l l 22 , 29
system call instruction 22, 29
tab 29
target address 59
target register 59
temp . a 4 1-2
temperature, conversion from Celsius to
Fahrenheit 4 1 -2
terminal button 3 5
testing code 3 2
text segment 1 9, 32, 34
Towers of Hanoi 1 1 2- 1 9
trap instructions 1 49
truth tables 74-5
two's complement representation for
negative numbers 1 2- 1 4, 1 6
addition rules 1 2
subtraction rules 1 2, 1 4
two's complement wheel 1 2, 1 3
unconditional jump
Unicode Standard
vcount 97
vowe l . a 95-7
word 1 4
X-Windows 3 1
xor 74
truth table 75
XSPIM 3 1
53 , 58
1 5
control buttons 32, 33
display of current state of
registers 33
starting 32-4
Page 191
Computer Arch itecture Assembly Language Programming
As the best way to gain an understand ng of
how a computer processor works at the lower
Programming
very d ifferent due
Dr John Waldron was a lecturer at
University from 1 99 1 . His first book,
City
l.angeV1n
Equation (with Wf Coffey and Yu P KafmYkov
was published in 1 996.
He is now an academic in the Department of
Computer Science, Trinity College , Dubli
Visit us on the World Wide Web at:
http:// pearso .com
•
Introduction to RISC Assembly Language
Programming
is based around the M I PS RISC processor,
a s imple, clean RISC processor whose
architecture and assembly language is easy
to learn and u nderstand
speeds up the learn ing process by enabl ing
the reader to start writ ing simple assembly
language programs early, while assuming no
prior knowledge of computer programming
l inks with an automatic program testing system,
allowing a lecturer to set programming questions
and mark the assignments automatical ly, or a
reader to test a M I PS assembly language
program against numerous test i nputs
uses the SP IM simulator, a freely avai lable virtual
machine that al lows users to write and s imulate
running M I PS R2000/R3000 assembly language
programs on PC, Macintosh or U N I X p latforms,
with excellent source-level debugging tools
contains a large number of example programs
and programming questions
is supported by relate� software freely available
via the Web:
dron/I ral/cahom
I S B N 0 - 2 0 1 - 3 9 8 2 8 - 1_
9 0 0 0 O >
9 7802 0 1 3 9 8 2 8 1
