Method apparatus for implementing multiple return sites

Details Method apparatus for implementing multiple return sites Method apparatus for implementing multiple return sites

1997-10-06

2003-04-22

Courtenay, III, St. John (Department: 2126)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

Least weight routing

C712S236000, C709S241000

Reexamination Certificate

active

06553426

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of Invention
The present invention relates generally to methods and apparatus for implementing multiple return points for a call to a function. More particularly, the present invention relates to method and apparatus for efficiently enabling addresses for multiple return points to be obtained.
2. Description of the Relevant Art
Computer systems are often linked across a network, e.g., local area networks, intranets, and internets, of computer systems such that they may share resources such as software, or program, code. Further, many programs, which include routines, are written such that a program calls “external” functions which may not be included within the program. In general, the functions may be shared by many routines, thereby allowing computer system resources to be used more efficiently.
When a routine is arranged to call functions, the functions that are called must eventually return into the routine. Further, the returns to the routine must be made to the appropriate locations within the routine. With reference to
FIG. 1
, the flow between a computer program and functions called by the program will be described. Computer code
104
includes a routine g( )
108
. Routine g( )
108
includes instructions which are executed. As shown, the instructions include repeated calls
112
to a function f( )
116
.
When function f( )
116
is called and executes “normally,” e.g., no exception is thrown, then function f( )
116
typically completes execution, and a return is made to routine g( )
108
a
computer routine. The location within routine g( )
108
a
computer routine to which function f( )
116
returns is dependent upon the call site, or the site within routine g( )
108
a
computer routine which called function f( )
116
. Specifically, if function f( )
116
executes as a result of call
112
a
, then function f( )
116
returns to return address
120
which, as will be appreciated by those skilled in the art, is located immediately after call
112
a
within routine g( )
108
a
computer routine. Similarly, if function f( )
116
executes when called by call
112
b
, then function f( )
116
returns to return address
124
. Once function f( )
116
returns to routine g( )
108
a
computer routine, routine g( )
108
a
generally continues to execute.
Many functions may have more than one return site, or point. By way of example, a function may have a normal, or expected, return point as well as an alternate return point. Alternate return points are often considered to be “abnormal” return points such as return points associated with thrown exceptions. The alternate return points are typically stored, or cataloged, within an overall program such that the return points may be readily identified as needed. By way of example, alternate return points may be needed by a program during the processing of an exception thrown by a function which does not handle exceptions.
One mechanism used to associate functions with alternate return points is a return point, or return address, table.
FIG. 2
a
is a diagrammatic representation of a return point table associated with a call stack. A call stack
204
includes a caller frame
208
which calls another frame, i.e., callee frame
212
. Callee
212
is associated with a function f( )
214
. As such, when caller
208
calls callee
212
, function f( )
214
begins to execute.
At the end of the execution of function f( )
214
, function f( )
214
and, hence, callee
212
returns to caller
208
. When the return to caller
208
is not a normal return, then the normal return address may be used as an index
216
into a return point table
220
to identify the proper alternative return point. For example, if the normal return address is “1234”, then return point table
220
may be searched to find “1234.” Once “1234” is found, then the alternate return point address associated with “1234” may be obtained. As shown, for a normal return address of “1234,” the corresponding alternate return point address is “1256.” Once obtained, the alternate return point address may then be used to ensure that callee
212
returns to caller
208
appropriately.
Although the use of a return point table, which is generally a look-up table or a hash table, is effective to identify a proper return point for a callee, the implementation of a table look-up is often slow. A faster process for implementing multiple return points involves eliminating table look-ups to identify return points. As will be appreciated by those skilled in the art, during the execution of a function, it is essentially “known” to the function whether the function should return using a normal return, or whether the function should return using an alternate return. Therefore, data pertaining to the alternate return address is available to be stored.
FIG. 2
b
is a diagrammatic representation of a routine which is arranged to store alternate return address data. A routine g( )
236
includes a call
238
to a function f( ). Regardless of whether call
238
to a function f( ) results in the need to return to an alternate address, call
238
would normally return to return address
240
. Return address
240
identifies stored alternate return address data
242
. The stored alternate return address data
242
is located within routine g( )
236
, a computer routine near call
238
to enable alternate return address data
242
to be readily accessed. In general, alternate return address data
242
is stored in the instruction stream itself. Since stored alternate return address data
242
may not represent a legal instruction, or may have undesirable side effects such as overwriting a value in a register or a memory cell, execution of routine g( ) may not continue at address
240
but must instead continue at next instruction
244
.
When call
238
returns normally, call
238
should return to next instruction
244
. As shown, within routine g( )
236
, next instruction
244
is offset from stored alternate return address data
242
by a distance D. Therefore, when call
238
returns normally, call
238
must return to a location that is specified by the location of return address
240
incremented by offset D, i.e., the location of next instruction
244
. Typically, as distance D has a value of four bytes, next instruction
244
is offset from the location of return address
240
by four bytes.
While accessing a stored alternate return address in a program is more time-efficient than implementing a table look-up when an alternate return address is needed, when an alternate return address is not needed, the ability to access a stored alternate return address often adversely affects the performance of the program. Adding an offset to the location of a return address in order to locate a subsequent instruction to be executed when a function call returns normally is often relatively slow, and may incur a performance penalty associated with computing the location of the subsequent instruction. In other words, the speed associated with a normal return may be compromised by the implementation of stored alternate return addresses. Further, branch prediction which is often used to generate a “best-guess” estimate for a normal return, or a return which is most likely to occur, may be compromised by the use of jumps, as will be appreciated by those skilled in the art.
Alternatively, “jumps” may be used to bypass the stored alternate address, as follows. Jumps, or branches, are often included in programs, or routines, to bypass sections of code which may be unnecessary in some situations. For example, jumps may be implemented in a routine to enable a stored alternate return address to be bypassed when a function call returns normally, as shown in
FIG. 2
c
. Within routine g( )
266
, a call
268
is made to a function f( ). When call
268
returns normally, the return is made to the location in routine g( )
266
specified by a return address
270
. The location corresponding to return address
270
is an instruction
272
to jump to a location L which is locate

Affiliated with

Also associated with

Rating

Method apparatus for implementing multiple return sites 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 apparatus for implementing multiple return sites, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method apparatus for implementing multiple return sites will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3024930