Data processing: structural design – modeling – simulation – and em – Emulation – Compatibility emulation
Reexamination Certificate
1998-08-07
2001-06-05
Teska, Kevin J. (Department: 2123)
Data processing: structural design, modeling, simulation, and em
Emulation
Compatibility emulation
C703S026000, C717S152000
Reexamination Certificate
active
06243668
ABSTRACT:
BACKGROUND
The present invention relates generally to a computer software instruction set interpreter. More particularly, the present invention relates to an instruction set interpreter which utilizes a register stack to improve the performance of the interpreter.
As a general concept, computer equipment produced by one manufacturer can use a different instruction set architectures (ISA) and a different operating system than another manufacturer uses. For example, some Hewlett-Packard® equipment contains a PA RISC® ISA and a UNIX® operating system, and some APPLE® equipment contains a POWER PC® ISA and a MACINTOSH® operating system. Since the ISA for a specific system defines computer software instructions available to a programmer, program instructions written for the PA RISC® hardware could not automatically run on the POWER PC® hardware. Hereinafter, the term base ISA will be used to refer to an ISA like PA RISC®, for example, which differs from an ISA of a native machine using a native ISA such as POWER PC®.
Programmers typically do not write programs in a language that a system's ISA can readily understand; they write the programs in a high level language like C, C++, or Pascal. Additionally, since such programs usually consist of multiple modules, programmers can write the various modules in a different language. To run the program on a base machine with the base ISA architecture, the programmer can compile the program to convert the high level languages to ISA-level instructions. A final program combines all the compiled versions of the modules and any modules hand-written in machine code. If another machine utilizes a native ISA different from the base ISA, to run the base ISA instructions on the native machine they will need to be emulated on the native machine.
To run base ISA instructions on a native machine, recent implementations of instruction set interpreters (ISI) use a combination of two emulation techniques, pure interpretation and binary translation. Pure interpretation means that the base ISA instructions are fetched one instruction at a time, decoded, and executed. Binary translation means that the base ISA instructions are converted to sequences of native ISA instructions which reproduce the behavior of the base ISA code. The native code can be stored in a code cache memory so that a user can execute and later reuse the code.
The ISI must model a base ISA register state visible to the base ISA program by mapping the base ISA register state into a native ISA state. Existing ISI's use two types of mapping techniques, memory mapping and register mapping. The memory mapping technique consists of storing the base ISA register values in memory, and the register mapping technique consists of storing the base ISA register values in native ISA registers. Register mapping offers the highest level of performance, and can be used when executing in the code cache. If a portion of the program to be executed has been translated, the base ISA register state can be register mapped because the ISI's translator produces the native code stored in the code cache and dictates its own native ISA register usage conventions
A problem exists when executing ISI components written in a high level language like C, C++, or Pascal. Since the high level language compiler dictates register conventions, the base ISA register values must be memory-mapped when executing high level ISI components. Existing ISIs spill base ISA register values from native registers to memory when switching from the code cache to a high level component, and reload them from memory when switching back. Switches become a costly operations in terms of performance, however, because the acts of spilling and reloading require a large number of store and load instructions.
Another problem exists with a stack cutback operation, for example a system call longjmp( ) for the UNIX® type system, in a mixed-mode environment. The ISI can allow the emulated code to call native functions, or native functions to call emulated functions. An application that makes such calls is termed mixed-mode since both native and emulated modes of execution are occurring. Since the stack cutback can cross one or more mode boundaries, requiring the restoration of both the native state and the emulated state, stack cutback can become a complicated operation.
Some computer architectures provide a feature called a register stack. The register stack is a hardware array of registers originally designed to accelerate procedure calls for the high level languages such as C, C++, or Pascal. The procedure typically accepts input arguments, performs an action, and then returns output parameters which are the results. A first procedure, a caller, can access a contiguous subset of the register stack referred to as a frame. If the caller calls a second procedure, a callee, the caller can execute an instruction which slides the frame to a different subset of the register stack. Thus, the callee has access to a new set of registers, and the caller's registers are protected from accidental corruption because they are currently not accessible. If the caller needs to pass parameters to the callee, the caller can make the callee's frame overlap the caller's frame by a number of registers required to pass the parameters. Thus, the caller's output registers become the callee's input registers.
Additionally, a series of nested procedure calls can occur, i.e., the callee can call a third procedure, and the third procedure can call a fourth procedure which calls a fifth procedure, and so on. As new procedures are called, new registers need to be utilized or values in the previously used register could be overwritten and lost. Since the register stack contains a finite number of registers, however, when a series of nested procedure calls exceeds the capacity of the register stack, an overflow condition may occur. During the overflow condition a hardware can automatically spill or transfer the content of registers, beginning with register one (R
1
), for example, to an area of memory called a backing store. When a callee completes its procedure, the callee executes a return to slide the frame back to a previous state, thus re-exposing the preceding caller's registers. As the series of procedure calls return, an underflow condition occurs and the hardware can reload or transfer the contents from the backing store to the register stack.
Accordingly, in response to the problems discussed above, a primary object of the present invention is to provide an improved method for achieving switches to high level components which minimizes spills to memory and reloads from memory.
Another object of the present invention is to simplify stack cutback operations in the mixed-mode environment.
REFERENCES:
patent: 5875318 (1999-02-01), Langford
patent: 5953520 (1999-09-01), Mallick
patent: 6009261 (1999-12-01), Scalzi et al.
patent: 6031988 (2000-02-01), Nakashima
patent: 6041402 (2000-03-01), Cannon et al.
patent: 6044220 (2000-03-01), Bretetnitz et al.
patent: 6091897 (2000-07-01), Yates et al.
Ebcioglu et al., “DAISY: Dynamic Compilation for 100% Architectural Compatibility”, Proceedings of the 24th International Symposium on Computer Architecture, pp. 26-37, Jun. 1997.*
Ertl, A., “Stack Caching for Interpreters”, Proc. of the Conf. on Programming Language Design and Implementation, pp. 315-327, Jun. 1995.*
Cmelik et al., “Shade: A Fast Instruction-Set Simulator for Execution Profiling”, Proc. of the 1994 Conf. on Measurement and Modeling of Computer Systems, pp. 128-137, May 1994.*
Le, B., “An Out-of-Order Execution Technique for Runtime Binary Translators”, Proc. of the 8th Intern. Conf. on Architectural Support for Programming Languages and Operating Systems, pp. 151-158, Oct. 1998.
Istvan Anthony Fitzgerald
Le Bich-Cau
Hewlett--Packard Company
Sergent Douglas W.
Teska Kevin J.
LandOfFree
Instruction set interpreter which uses a register stack to... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Instruction set interpreter which uses a register stack to..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Instruction set interpreter which uses a register stack to... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2470616