Hardware Reference
In-Depth Information
The column on the left shows the positive integers 0 to 7 in increasing order. The
column on the right shows the two's complement signed integers
4 to +3. The
answer to the question ''Is 011 greater than 100?'' depends on whether or not the
numbers are regarded as being signed. Most ISAs have instructions to handle both
orderings.
−
A
procedure
is a group of instructions that performs some task and that can be
invoked (called) from several places in the program. The term
subroutine
is often
used instead of procedure, especially when referring to assembly-language pro-
grams. In C, procedures are called
functions
, even though they are not necessarily
functions in the mathematical sense. In Java, the term used is
method
. When the
procedure has finished its task, it must return to the statement after the call. There-
fore, the return address must be transmitted to the procedure or saved somewhere
so that it can be located when it is time to return.
The return address may be placed in any of three places: memory, a register, or
the stack. Far and away the worst solution is putting it in a single, fixed memory
location. In this scheme, if the procedure called another procedure, the second call
would cause the return address from the first one to be lost.
A slight improvement is having the procedure-call instruction store the return
address in the first word of the procedure, with the first executable instruction
being in the second word. The procedure can then return by branching indirectly
to the first word or, if the hardware puts the opcode for branch in the first word
along with the return address, branching directly to it. The procedure may call
other procedures, because each procedure has space for one return address. If the
procedure calls itself, this scheme fails, because the first return address will be
destroyed by the second call. The ability for a procedure to call itself, called
recursion
, is exceedingly important for both theorists and practical programmers.
Furthermore, if procedure
A
calls procedure
B
, and procedure
B
calls procedure
C
,
and procedure
C
calls procedure
A
(indirect or daisy-chain recursion), this scheme
also fails. This scheme for storing the return address in the first word of a proce-
dure was used on the CDC 6600, the fastest computer in the world during much of
the 1960s. The main language used on the 6600 was FORTRAN, which forbade
recursion, so it worked then. But it was, and still is, a terrible idea.
A bigger improvement is to have the procedure-call instruction put the return
address in a register, leaving the responsibility for storing it in a safe place to the
procedure. If the procedure is recursive, it will have to put the return address in a
different place each time it is called.
The best thing for the procedure-call instruction to do with the return address is
to push it onto a stack. When the procedure has finished, it pops the return address
off the stack and stuffs it into the program counter. If this form of procedure call is
available, recursion does not cause any special problems; the return address will