Reexamination Certificate
1997-09-30
2001-09-25
Cabeca, John W. (Department: 2755)
C712S228000
Reexamination Certificate
active
06293712
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to conventions for compiling, linking and executing a computer program on an operating system. Specifically, the present invention relates to the conventions for call stack unwinding and exception handling within a computer system.
BACKGROUND OF THE INVENTION
Computer programs are typically composed of a number of procedures, each of which may be called upon to perform a certain function, or process certain data, upon execution of the computer program. In conventional programming languages, procedures called when the computer program executes may each be represented by a “stack frame” in a defined region of a program's address space, the defined region being termed the “stack region”.
Referring to
FIG. 1
, there is shown a schematic representation of a stack region
10
defined in a program's address space. The stack region
10
accommodates a call stack comprising N stack frames
12
, each stack frame
12
representing and including data concerning a specific called procedure. A stack frame
12
is created and placed in the call stack when an associated procedure is called, and then removed (or “popped”) from the call stack when the procedure is exited. Accordingly, the call stack represents a structure of nested procedures which are extant within a computer system at any given moment. For example, in the situation illustrated in
FIG. 1
, the procedure associated with stack frame (N−1) would have called the procedure associated with stack frame (N).
Each stack frame
12
may include a frame marker
14
, an activation record
16
, and saved registers
18
. The frame marker
14
is located at the top of the stack frame
12
, and may include “bookkeeping” information, such as a pointer to the immediately preceding stack frame (i.e. a Previous Stack Pointer (PSP)) and a pointer to the return point in the calling procedure (i.e. a Return Pointer (RP)). The activation record
16
includes information concerning the local state that must be stored in memory by the associated procedure, including local variables and tempories. Each stack frame
12
also includes space to save registers that must be saved across procedure calls.
Stack unwinding is the process of tracing backwards through the activation records contained in a call stack. Debuggers and exception handling mechanisms require the ability to “unwind” the call stack, or trace back through a series of stack frames, from the stack frame for the most recently called procedure to that for the outermost procedure of a program. For example, a debugger may need to unwind the call stack to print a stack trace, while an exception handling mechanism may need to remove a number of stack frames from the call stack, and to transfer control to an exception handling routine which is located down the stack. As the stack is unwound, values of preserved registers, saved by each procedure, are recovered so as to allow the debugger or exception handler access to correct values for local variables.
Complex Instruction Set Computing (CISC) and Reduced Instruction Set Computing (RISC) architectures have fundamentally differing approaches to stack frames. CISC architectures typically provide special instruction-set support for the stack mechanism, with a single instruction to allocate a stack frame and to create a frame marker when a procedure is called, and another single instruction to return from a procedure call and to remove the relevant stack frame from the call stack.
The advent of RISC architectures allowed the allocation, creation, return and removal steps to be divided into a number of higher resolution sub-operations, which can be eliminated when unnecessary. For example, where it is known that the size of the stack frame is not varied by the associated procedure, there is no need to save the Previous Stack Pointer (PSP), and both save and retrieve operations with respect to the PSP can be eliminated.
However, in RISC architecture environments, the debugger may now need additional information to perform a stack unwind operation in view of the non-uniform content and formats of stack frames. For example, for any given stack frame, a PSP may or may not be included in the relevant frame marker. If the PSP is saved, the debugger can immediately locate the previous stack frame; if not, the debugger needs to determine the size of the stack frame and then calculate the location of the preceding stack frame. An exception handler may also require additional information regarding what registers have been saved in a stack frame, and when and where these registers were saved.
In order provide this additional information required in RISC architectures, a stack unwind table may be generated by a compiler. Such a stack unwind table includes static information that is required for unwinding the stack. It is desirable that a stack unwind table be as compact as possible, and also facilitate optimization techniques to be applied to procedure code without compromising the ability to unwind the stack.
SUMMARY OF THE INVENTION
According to a first aspect of the invention, there is provided a computer-implemented method of constructing a stack unwind data structure. The method commences with a determination as to whether a specific procedure complies with a default condition for a certain characteristic. If the procedure does not comply with, or varies from, the default condition for this predetermined characteristic, then an unwind record relating it to the predetermined characteristic is generated and included in the stack unwind data structure. Alternatively, should the procedure comply with, or correspond to, the predetermined characteristic, then an unwind record is not generated, and not included in the stack unwind data structure. The above operations are, in one exemplary embodiment, performed during compilation of a program.
According to a second aspect of the invention, there is provided a computer-implemented method of performing a stack unwind operation utilizing a stack unwind data structure. The method of performing the stack unwind requires first determining whether an entry for a specific procedure is included in the stack unwind data structure. Should such entry be included within the stack unwind data structure, then a determination is made to whether a record relating to a first predetermined characteristic is included within the entry. Should no such record be included within the entry, then a first default condition is attributed to the predetermined characteristic. Further, should no entry for the procedure be included within the stack wind data structure, then a default condition is attributed to a further predetermined characteristic.
According to a third aspect of the invention, there is provided a computer-readable medium having a sequence of instructions stored thereon which, when executed by a processor, cause the processor to perform the steps outlined above.
Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.
REFERENCES:
patent: 5327566 (1994-07-01), Forsyth
patent: 5428779 (1995-06-01), Allegrucci et al.
patent: 5530870 (1996-06-01), De Bruler
patent: 5535397 (1996-07-01), Durante et al.
patent: 5564031 (1996-10-01), Amerson et al.
patent: 5628016 (1997-05-01), Kukol
patent: 5640582 (1997-06-01), Hayes et al.
“RISC systems”,Microprocessors and Microsystems, Daniel Tabak, vol. 12, No. 4, May 1988, pp. 179-185.
“A Simple Interprocedural Register Allocation Algorithm and Its Effectiveness for LISP”,amc Transactions on Programming Languages and Systems,Peter A. Steenkiste and John L. Hennessy, vol. 11, No. 1, Jan. 1989, pp. 1-32.
“A VLSI RISC”,Computer,David A. Patterson and Carol H. Sequin, vol. 15, No. 9, Sep. 1982, pp. 1-21.
“Hewlett-Packard, Chapter 7 Stack Unwinding from Chapter 6 Millicode Calls”, PA-RISC Procedure Calling Conventions Reference Manual (Palo Alto CA: Hewlett-Packard, 1986).
“The 32-bit PA-RISC Run-Time Architecture Document”, HP-UX 10.20, Version
Blakely , Sokoloff, Taylor & Zafman LLP
Cabeca John W.
Institute for the Development of Emerging Architectures LLC
Opie George Lawrence
LandOfFree
Method and apparatus for constructing a stack unwind data... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for constructing a stack unwind data..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for constructing a stack unwind data... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2538434