Electrical computers and digital processing systems: processing – Processing control – Branching
Reexamination Certificate
1998-12-09
2001-04-03
Ellis, Richard L. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Branching
C717S152000
Reexamination Certificate
active
06212630
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to microprocessors and programming language compilers, and more specifically relates to a technique for performing subroutine calls/returns and register saves/restores associated with the subroutine calls/returns at high speed.
2. Description of the Prior Art
As structured programming, such as C language, comes into wider use, machine instruction sequences executed by microprocessors (hereinafter simply referred to as “processors”) include more subroutines. Immediately after a subroutine is called, values in a plurality of registers used by the processor need to be saved into (pushed onto) a stack memory (a stack area in a data memory, hereinafter also simply referred to as “a stack”) . When controls return from the subroutine, the saved values need to be restored (popped) into the plurality of registers.
FIG. 1
is a list of machine instructions generated by a conventional programming language compiler (hereinafter simply referred to as “a compiler”). This list includes instructions for calling a subroutine and for returning from the subroutine.
FIG. 2
is a table showing operations of the machine instructions in this list.
FIG. 3
shows changes in the stack contents, the stack size, and the value of the stack pointer SP, when a conventional processor executes these machine instructions.
Here, the legends “PC”, “LR”, “Rn”, and “SP” respectively refer to the program counter used by the processor, the return register for storing the return address for a subroutine, the nth general register, and the stack pointer. The legend “Mem” refers to an external memory (including a stack) and the legends “op
1
” and “op
2
” respectively refer to a source operand and a destination operand. Each row in the operation column in the table shown in
FIG. 2
gives operations that can be performed in parallel in one machine cycle (hereinafter simply referred to as “cycle”) by the processor (including operations which can be performed at different timings in the same cycle). When executing the subroutine call instruction “call label”, for instance, the processor increments the program counter PC by four (and stores the value in the return register LR) and stores the call destination label in the program counter PC in one cycle.
FIG. 1
shows the following operations: the call of the subroutine “f” (step
3301
); the reserving of a stack immediately after the subroutine call (steps
3302
,
3304
,
3306
, and
3308
); the saving of registers (steps
3303
,
3305
, and
3307
); the release of the stack immediately before the return from the subroutine (steps
3309
,
3311
,
3313
, and
3315
); and the restoration of the registers to saved values and the return from the subroutine “f” (step
3316
).
Here, the reserving of a stack means that the stack is extended by a necessary amount before the stack is used (a value is stored on the stack). This is achieved by lowering the stack pointer SP. The release of a stack means that the stack is narrowed by the amount of stored data that has been used. This is achieved by raising the stack pointer SP. The saving of registers means that values stored in the registers are saved on a stack. The restoration of registers means that data saved on a stack is read and is restored in the original registers.
It should be noted here that the reserving of a stack can be a process associated with the saving of nondestructive registers (registers whose contents should remain unchanged before and after a subroutine is executed) (steps
3302
,
3304
, and
3306
) or a process for reserving local areas (stack areas for local variables which are valid only in subroutines) (step
3308
). Similarly, the release of a stack can be a process for releasing local areas or a process associated with the restoration of nondestructive registers (steps
3311
,
3313
, and
3315
).
FIGS. 4A and 4B
are timing charts which show the operation performed by the processor in each cycle in respectively the former half (steps
3301
-
3308
) and the latter half (steps
3309
-
3316
) of the machine instructions shown in FIG.
1
. As can be seen from these drawings, conventional techniques require eight cycles to branch to the subroutine “f”, to save two nondestructive registers R
2
and R
3
, to save the return register LR, and to reserve the local area in the former half. Similarly, eight cycles are required to release the local area, to restore the return register LR, to restore the nondestructive registers R
2
and R
3
, and to return from the subroutine “f” in the latter half.
In detail, a conventional compiler saves nondestructive registers or reserves a local area by generating a pair of instructions for reserving a stack and saving registers at the starting location of a subroutine, and by generating a pair or instructions for releasing the stack and restoring the registers at the ending location of the subroutine. This is repeated whenever necessary.
However, conventional compilers and processors do not have sufficient performance to satisfy the exacting requirements of recent appliances using processors, such as multi-functioning and high-speed processing. In particular, when a functional programming language, such as C language, is used for developing software for appliances using embedded processors and control devices that require real-time processing, it is very difficult for a conventional compiler and processor to deliver sufficient processing speed.
SUMMARY OF THE INVENTION
In view of the stated problems, it is the object of the present invention to provide a processor which executes processes associated with subroutines at high speed and a compiler for the processor. More specifically, the object of the present invention is to provide a processor which can execute routine operations associated with the branch to a subroutine and the return from the subroutine, such as those shown in
FIGS. 4A and 4B
, in less cycles and to provide a compiler for the processor.
To achieve the above object, the processor of the present invention which is connected to a data memory providing a stack area and to an instruction memory prestoring instructions, includes: a subroutine call unit for causing a branch to a subroutine in an execution sequence; a stack reserve unit for reserving a new stack area in the data memory; an instruction fetch unit for fetching an instruction from the instruction memory; and a first instruction execution unit for having, when the fetched instruction is a first instruction, the subroutine call unit cause the branch and the stack reserve unit reserve the new stack area in parallel. Also, the compiler of the present invention for converting a source program into machine instructions includes a subroutine call stack reserve instruction generation unit for generating a subroutine call stack reserve instruction when a subroutine call instruction is detected in the source program, where the subroutine call stack reserve instruction is a machine instruction for having a processor perform the following operations (a) and (b) in parallel: (a) a causing of a branch to a subroutine in an execution sequence; and (b) a reserving of a new stack area in a data memory. With the stated constructions, when the processor executes the first instruction, the branch to the subroutine and the reserving of the new stack area are performed in parallel in one cycle. As a result, the execution time necessary for these operations is shortened, in comparison with a conventional technique where these operations are performed sequentially.
Here, the processor may further include: a return address storage unit which includes an area for storing a return address, the return address being a return destination when the execution sequence is returned from the subroutine to a main routine that called the subroutine; and a return address writing unit for writing the return address in the return address storage unit, where when the fetched instruction is the first instruction, the first instruction execution unit has the
Takayama Shuichi
Tanaka Tetsuya
Ellis Richard L.
Matsushita Electric - Industrial Co., Ltd.
Price and Gess
LandOfFree
Microprocessor for overlapping stack frame allocation with... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Microprocessor for overlapping stack frame allocation with..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Microprocessor for overlapping stack frame allocation with... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2469041