Electrical computers and digital processing systems: processing – Processing control – Specialized instruction processing in support of testing,...
Reexamination Certificate
2000-09-22
2004-03-23
Tsai, Henry W. H. (Department: 2183)
Electrical computers and digital processing systems: processing
Processing control
Specialized instruction processing in support of testing,...
C712S242000
Reexamination Certificate
active
06711672
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to computer programs in general, and in particular, to a method and related system for implementing subroutine calls and returns in the context of binary translation of instructions in an original language into instructions in a target language, which may be the same as the original language.
2. Description of the Related Art
It is a well known fact that software constitutes a large fraction of the cost of computer systems. On the surface, this may seem surprising since, once developed, software can be installed and replicated without limit. The cost, however, stems from the difficulty of initial development, and the need for ongoing maintenance in the form of customization, defect elimination, and development of upgrade versions over the lifetime of the software. To give an indication of the magnitude of software engineering costs, consider that writing what is now considered a medium-sized software package may require hundreds of man-years of investment initially; moreover, following the first deployment, ongoing maintenance may demand comparable resources.
One of the hardest challenges in software engineering, be it initial development or subsequent maintenance, is the management of complexity. In particular, preventing a change or addition to one part of a system from having unforeseen and undesirable consequences in another part of the system can require significant effort. Consider, for example, that a large software system may contain millions of lines of program code, any one of which could potentially interact with any other, and it may be seen that the potential for errors is quite large. This is particularly true since no individual could write all the code, nor could any individual be familiar with all of it, once written. Early on, software developers and researchers recognized that in order to work effectively in such environments where individuals have only partial knowledge of the full system, systematic development techniques must be followed.
Perhaps the most widely employed development technique involves the decomposition of software into subroutines, also known as subprograms, functions, procedures, or methods. A subroutine comprises a number of program statements and optional data structures to perform a given task. The subroutine logically encapsulates the individual statements, allowing them to be invoked (“called”) as a group from elsewhere in the program. The effect of the subroutine invocation is to execute the statements encapsulated in the subroutine. When the last such statement completes, execution returns to the point in the program where the subroutine was invoked.
With subroutines, then, instead of solving a top-level problem directly, programmers partition it into a number of smaller problems, such that a solution to the top-level problem can be obtained by combining solutions to the smaller problems: Each smaller problem's solution is encapsulated into a subroutine, enabling the large problem's solution to be expressed as a sequence of subroutine invocations. Often, but not necessarily, the decomposition follows a hierarchical pattern in which higher-level subroutines are implemented in terms of lower-level subroutines, which in turn are implemented from even lower-level subroutines, until the point where the problems have been partitioned sufficiently that solutions can be expressed directly using primitive statements from the programming language.
The use of subroutines provides multiple advantages in software development. First, complexity is reduced locally: The number of logical steps required to solve a given problem can be kept small because the solution can be expressed in terms of higher-level operations implemented in subroutines instead of in terms of the low-level primitives defined directly by the programming language. Second, complexity is reduced globally: Because subroutines encapsulate groups of statements, programmers can often reason about the interaction of subroutines rather than the interaction of individual statements across the program. Without this encapsulation, it would be very difficult to implement large-scale software systems. Third, subroutines allow for code reuse: Once a solution to a sub-problem has been implemented and made available as a subroutine, it can be used as a building block for solving many different problems; this greatly reduces the time required to implement software, since it is not necessary to start from scratch each time. It also reduces the size of programs, since general-purpose subroutines need only be provided once even though they are used in multiple places.
From all of these reasons, and more, the use of subroutines has become fundamental to software engineering. As a result, during execution of programs written in this manner, computers will execute a large number of subroutine calls and returns.
Consider now how subroutines may be implemented on contemporary computers. In other words, consider programming language implementation.
Most of the time, programmers write software in high-level programming languages such as Cobol, Fortran, Modula-2, C, C++, or Java. All of these languages provide subroutines in some form. While the details vary in terms of both syntax and semantics (especially with respect to parameter passing), many similarities remain. In particular, all these languages provide a “last-in, first-out” (LIFO) ordering on subroutine calls and returns: the last subroutine to have been called will be the first one to return. For example, let A, B, and C denote subroutines and suppose that A calls B, and B calls C. If a “return-from-subroutine” statement is executed, it will terminate the execution of subroutine C (the one called most recently) and execution will continue in subroutine B at the point that immediately follows the invocation of C. Later, a return statement in B may terminate B's invocation and take execution back to subroutine A.
Because subroutine execution respects this LIFO order, an efficient implementation can be realized by using a push-down stack. With this well known implementation technique, a subroutine invocation, such as A calling B, is performed in two steps. First, the return address is pushed onto the stack. Second, the program counter is updated to indicate the first statement of subroutine B, that is, execution “jumps” to the beginning of B. The execution of B now proceeds without regard to where it was invoked from. Eventually, a return statement in B will be encountered or, equivalently, the last statement in B will complete. In either case, to return back to its caller, subroutine B need only perform a single step: it pops the top-most item from the stack, which will be the address to which it should return, and places this value in the program counter register. Now, instruction fetching and execution will continue from the point in the caller (A in the example) that follows the call to B.
The use of a stack provides a high degree of generality. A subroutine, such as B, can correctly return back to its caller A, even if B, during its execution, performs further subroutine invocations. For instance, if A calls B, then the stack will contain “A” when the execution of B commences. Now, if B later calls C, then the stack will contain two return addresses “A; B” where B is the most recent (top-most) item. When C returns, it will pop the topmost item from the stack (B) leaving just “A” on the stack. This is the same state as before the call of C in B, so following the invocation and completion of subroutine C, B can execute to completion and return back to A by popping the return address from the stack in the usual manner. (Merely for the sake of notational simplicity, one may equate return addresses with the caller subroutine; in actual implementations, the return addresses must indicate the precise statement within the caller to which execution should return. Often, but not necessarily, this return address will be represented as a memory addres
Pearce Jeffrey
Tsai Henry W. H.
VMware, Inc.
LandOfFree
Method and system for implementing subroutine calls and... 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 system for implementing subroutine calls and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and system for implementing subroutine calls and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3240138