Supporting
procedures in Computer Hardware
Procedures
·
In Pascal referred to as subroutines, functions in C and methods in Java, are chunks of
code which are repeatedly used as the program executes.
·
Thus, using procedures acts as
o
Method of sharing code,
o
Reduce the size of program
·
Is a stored subroutine that performs a specific task based on the
parameters with which it is provided.
·
or function is 1 tool programmers use to
o
structure program, both to make them
easier to understand and
o
to allow code to be reused.
·
Allow the programmer to concentrate on
just one portion of the task at a time;
·
Like a spy who leaves
o
with a secret plan,
o
acquires resources,
o
performs the task,
o
covers his or her tracks,
o
and then returns to the point of origin
with the desired result.
o
A spy also operates on only a “need to
know” basis, so the spy can’t make assumptions about his employer.
·
Similarly, in the execution of a
procedure, the program must follow 7 steps call work:
1. set up parameters where the procedure
can access them
2. transfer control to procedure
3. acquire storage resources needed by
procedure
4. do the desired function/task
5. make result available to caller(where
the calling program can access it)
6. release storage resources
7. return control to point of call/origin,
since a procedure can be called from
several points in a program.
Why use procedures?
·
So far, our program is just one long run
of instructions
·
We can do a lot this way, but the
program gets too large to handle easily
·
Procedures allow the programmer to
organize the code into logical units
© 2006-09 Perkins, DW Johnson and
University of Washington 5
Used of procedures
·
A procedure provides a well defined and reusable
interface to a particular capability
» entry, exit, parameters clearly identified
·
Reduces the level of detail the
programmer needs to know to accomplish a task
·
Caller can ignore the internals of a
function
» messy details can be hidden from innocent eyes
»
internals can change without affecting caller
© 2006-09 Perkins, DW Johnson and
University of Washington
Registers
·
are a number of small, high-speed memory
·
The register can contain the address of a memory location where data is stored rather than the actual data itself.
·
So, we load the data into special
high-speed memory locations inside the processor itself called data or CPU registers.
Several classes of registers.
·
There
are several classes of registers according to the content:
·
Data
registers -
used to store integer numbers
·
Address
registers - hold
memory addresses and are used to access memory. In some CPUs, a special address register is an index register, although often these hold numbers
used to modify addresses rather than holding addresses.
·
General
Purpose registers (GPRs)
- store both data and addresses, i.e., they are combined Data/Address
registers.
·
Floating
Point registers (FPRs)
- used to store floating point numbers in many
architectures.
Registers vs.
Memory
·
Registers are faster to
access than memory
·
Operating on memory data
requires loads and stores
o
More instructions to be
executed
·
Compiler
must use registers for variables as much as possible
o
Only spill to memory for less frequently
used variables
o
Register optimization is
important!
·
Registers can hold variables to reduce
memory traffic and improve code density (since register named
with fewer bits than memory location)
·
Registers are easier for a compiler to
use
o
e.g., as a place for temporary storage
R
Resources
Involved
MIPS software follows the following
convention for procedure calling in allocating its 32 registers:
•
Registers used for procedure calling:
–
$a0 - $a3 : four argument registers in
which to pass parameters
–
$v0 - $v1 : two value registers in which
to return values
–
$ra : one return address register to
return to the point of origin
MIPS assembly language includes an
instruction just for the procedures: it jumps to an address and simultaneously
saves the address of the following instruction in register $ra. The jump-and-link instruction (jal) is
simply written
–
jal ProcedureAddress
•
Transferring the control to the callee:
–
jal ProcedureAddress
–
jump-and-link to the procedure address
–
the return address (PC+4) is saved in
$ra
–
Example: jal 20000
•
Callee returning the control to the
caller:
–
using jr $ra
–
instruction following jal is executed next
Notes
ü jump-and-link instruction
– an instruction that jumps to an address and simultaneously saves the address
of the following instruction in a register ( $ ra in MIPS)
ü return address
– a link to the calling site that allows a procedure to return to the proper
address in MIPS it is stored in register $ ra.
ü Caller
– the program that instigates a procedure and provides the necessary parameter
values.
ü Callee
– a procedure that executes a series of stored instructions based on parameter
provided by the caller and then returns control to the caller.
ü Register
is almost always called the program
counter or more sensible name is instruction
address register.
ü program counter(PC) – the
register containing the address of the instruction in the program being
executed.
Spilling registers to memory
·
a situation where any registers needed
by the caller must be restored to the values that they contained before the
procedures was invoked when we cover up
tracks after our mission is complete.
·
The ideal data structure for spilling
registers is a stack – a
last-in-first-out queue.
·
A stack needs a pointer to most recently
allocated address in the stack to show where the next procedure should place
the registers to be spilledor where old register values are found.
·
The stack pointer is adjusted by one
word for each register that is saved or restored
·
Transferring data to and from the stack
:
o
Placing data onto the stack is called a push, and
o
Removing data from the stack is called a
pop.
Notes
ü Stack
– a data structure for spilling registers organized as a last-in-first-out
queue.
ü Stack-pointer
– a value denoting the most recently allocated address in a stack that shows
where registers should be spilled or where old register values can be found. In
MIPS, it is register $ sp.
ü Push
– add element to stack.
ü Pop
– remove element from stack.
Nested Procedures
Nested
function (or nested procedure/subroutine)
is a function which is lexically (textually)
encapsulated within another function. It can only be called by the enclosing
function or by functions directly or indirectly nested within the same
enclosing function. In other words, the scope of
the nested function is limited by the enclosing function. The nesting is
theoretically possible to any level of depth, although only a few levels are
normally used in practice.
Purpose
·
Nested
functions are a form of information hiding and are useful for dividing procedural
tasks into sub tasks which are only meaningful locally;
·
it
avoids cluttering other parts of the program with functions, variables, etc.
unrelated to those parts.
·
Nested
functions therefore complement other structuring possibilities such as records
and objects.
Allocating
Space for New Data on the Heap
Notes :
ü These
address are only a software convention, and not part of the MIPS architecture.
Register
conventions, usage
Figure 2 MIPS register conventions.
A slightly different example of an R-format instruction involves substraction
sub $t1 $s1 $s2, which means that we add two numbers stored in C registers 1
and 2 (
$s1 and $s2), then put the
result in temporary register 1 ($t1). Here, $t1 has the address 9, and the
C-registers have the addresses 17 and18, as before. Note that the funct code for subtraction (34) is different
from that for addition (32), and that there is no shifting.
The
MIPS convention is to place the extra parameters on the stack just above the
frame pointer.
Communicating
with people
·
Byte-encoded character sets
o
ASCII: 128 characters
o
95 graphic, 33 control
o
Latin-1: 256 characters
Figure
3 ASCII representation of characters.
Note
that upper-and lowercase letters differ by exactly 32;this observation can lead
to shortcuts in checking or changing upper-and lowercase. Values not shown
include formatting characters. For example, 8 represents a backspace, 9
represents a tab character, and 13 a carriage return. Another useful value is 0
for null, the value the programming language C use end of a string.
Characters
and Strings in Java
Unicode is a universal
encoding of the alphabets of most human languages, Figure 2 is a list of
Unicode alphabets
Figure
4 Example
alphabets in Unicode. Unicode version 4.0 has more than 160 “blocks,”which is
their name for a collection of symbols.
Each block is a multiple of 16. For
example, Greek starts at 0370hex, and Cyrillic at 0400hex.
The first 3 columns show 48 blocks that correspond to human languages in
roughly Unicode numerical. The last column has 16 blocks that are multilingual
and are not in order.
A 16-bit encoding, called UTF-16, is the default.
Avariable-length encoding, called UTF-8 keeps the ASCII subset as 8 bits and
uses 16-32 bits for the other characters. UTF-32
bits per character.
Characters are normally combined into
strings, which have a variable number of characters. There are 3 choices for
representing a string;
1.
The
first position of the string is reserved to give the length of the string,
2.
An
accompanying variable has the length of the string(as in structure),
3.
The
last position of a string is indicated by the character used to mark the end of
a string.
C uses the third choice, terminating a
string with a byte whose value is 0 (named null in ASCII). Thus, the string
“Cal”is represented in C by the following 4 bytes, shown as decimal numbers:
67, 97, 108, 0. (As we shall see, Java uses the first option.)
Byte/Halfword
Operations
·
Could
use bitwise operations
·
MIPS
byte/halfword load/store
o
String
processing is a common case
lb rt, offset(rs) lh rt, offset(rs)
o
Sign extend to 32 bits in rt
lbu rt, offset(rs) lhu rt, offset(rs)
·
Zero
extend to 32 bits in rt
sb rt,
offset(rs) sh rt, offset(rs)
o
Store
just rightmost byte/halfword
Cha
String
Copy Example
·
C code (naïve):
o
Null-terminated string
void strcpy (char x[ ], char y[ ])
{
int i;
i
= 0;
while
((x[i]=y[i])!='\0')
i
+= 1;
}
·
Addresses
of x, y in $a0, $a1
·
i
in $s0
·
MIPS
code:
Chapterstrcpy:
addi $sp, $sp, -4 # adjust stack for 1 item
sw $s0, 0($sp) # save $s0
add $s0, $zero, $zero # i = 0
L1:
add $t1, $s0, $a1 #
addr of y[i] in $t1
lbu $t2, 0($t1) # $t2 = y[i]
add $t3, $s0, $a0 # addr of x[i] in $t3
sb $t2, 0($t3) # x[i] = y[i]
beq
$t2, $zero, L2 #
exit loop if y[i] == 0
addi
$s0, $s0, 1 #
i = i + 1
j L1 #
next iteration of loop
L2: lw $s0,
0($sp) #
restore saved $s0
addi $sp, $sp, 4 # pop 1 item from stack
jr
$ra #
and return
References
Written by,
Lai Wai Kuen
B031210027
No comments:
Post a Comment