Abstract:
A method for calling and returning from a computer subroutine is provided. The method allows a subroutine executing on a stack-oriented computer with segmented addressing, such as the Intel 80386, to be invoked by both an inter-segment call and an intra-segment call instruction. The method allows multiple subroutines in one code segment to share an inter-segment return instruction. The method further provides for the locating of that instruction so that the pushing of its offset onto the stack can be accomplished efficiently.

Description:
TECHNICAL FIELD 
     This invention relates to a method for calling and returning from a computer subroutine during execution of a computer program, and more specifically, a method for programming to handle both inter-segment and intra-segment subroutine linkage. 
     BACKGROUND OF THE INVENTION 
     A computer program is a collection of computer instructions ordered in a manner such that when the program is executed by the computer the computer will produce certain results. Computer programs can be very simple, containing only a few instructions. Conversely, computer programs can be very complex, containing millions of instructions. For example, a certain type of computer program called an operating system can be extremely complex and often contains over a million instructions. 
     Most computer programs need to perform a certain task at several different places in the program. For example, an operating system may need to perform the task of writing to a display at many different places in the program. The programmer could simply repeat the same set of instructions at each place in the program. Having the same instructions duplicated throughout the program is usually undesirable for several reasons. If a change is made to the set of instructions, then the set must be changed wherever it is repeated in the program. Such changes may be time-consuming and error-prone. Also, having the same instructions repeated several times tends to make the program large, resulting in a program that may not fit into the memory of the computer. 
     The concept of a &#34;subroutine&#34; developed early in the history of computers. A subroutine is a set of instructions that is stored only once in a program, but can be &#34;called&#34; from several different places in a program. When a subroutine is called, the computer starts executing the instructions in the subroutine. When a &#34;return&#34; instruction in the subroutine is executed, the computer then &#34;returns,&#34; that is, resumes execution of the program at the instruction after the call. In effect, the set of instructions is as if it was inserted into the program at the call. 
     Subroutines have several advantages over the duplicating of the set of instructions. Subroutines save space in the program, since the set of instructions is stored only once. Subroutines make it easier to organize complex programs. Subroutines make it easier to make changes to the set of instructions, since the changes need only be made once. 
     The state-of-the-art computers, such as those based on Intel 8086-family microprocessors, have special-purpose instructions to facilitate the calling of and returning from subroutines. Specifically, there are two instructions for calling and two instructions for returning. 
     The Intel 8086-family of microprocessors uses a segmented addressing architecture. One such microprocessor is the Intel 80386, which is manufactured by the Intel Corporation of Santa Clara, Calif. The design and operation of the Intel 80386 is described in detail in a publication entitled &#34;iAPX 386 Programmer&#39;s Reference Manual Including the iAPX 386 Numeric Supplement,&#34; which is available from Intel Corporation and is hereby incorporated by reference. The Intel 80386 has one call instruction and one return instruction that are for invoking an intra-segment (a near) subroutine and another call instruction and return instruction that are for invoking an inter-segment (a far) subroutine. 
     The addresses in the 8086-family comprise a segment and an offset. Each call and return must specify a segment and an offset. When a call or return is executed, the microprocessor combines the segment and the offset to form an address. The call instruction forms the address of the subroutine; the return instruction forms the address of the instruction to return to. The methods of calling and returning from subroutines is referred to as subroutine &#34;linkage.&#34; 
     The near call and return are designed to be used when the call instruction and called subroutine are within the same segment when executed, that is, the current code segment. The code segment (CS) register contains information pointing to the current code segment. When a near call is executed, the processor pushes onto the stack the offset in the current segment of the instruction after the call instruction. The processor then jumps to the subroutine, which is located at a specified offset in the current code segment. When the subroutine returns, it executes a near return instruction. When the near return instruction is executed, it pops the offset, which was pushed onto the stack by the near call instruction, from the stack. The processor then forms an address based on current code segment and the offset. This address is the address of the instruction after the near call instruction. The processor then proceeds to execute the instruction at that address. 
     The limitation of the near call and return instructions is that only subroutines within the same segment can be called. The far call and return instructions have no such limitation. 
     The far call and return instructions work similarly to their near counterparts, except that these instructions push and pop both a segment and offset component. The far call specifies both a segment and an offset for the subroutine. Consequently, the current setting of the CS register is saved on the stack in addition to the offset of the instruction after the call. When the far return instruction is executed, the processor pops the segment and offset values pushed by the corresponding call instruction, forms an address, and returns to that address. The far call can specify any address and, unlike the near call, is not limited to those addresses within the current code segment. 
     A typical subroutine is designed to be called either by a near call instruction or a far call instruction. If designed to be called by a near call instruction, then the subroutine executes a near return instruction, which pops only the offset, to return. If designed to be called by a far call instruction, then the subroutine executes a far return instruction, which pops both the segment and offset, to return. If a subroutine that is designed to be called by a far call is invoked by a near call, then the subroutine will not return to the instruction after the far call. This mixing of near call with far return or mixing of a far call with a near return will result in a program error. 
     Several methods have been used for allowing a subroutine to be invoked by both a near and a far call instruction. One of these methods of subroutine linkage uses different entry points when the subroutine is invoked by a near call and a far call. 
     It would be desirable to have an improved method for subroutine linkage so that a subroutine can be invoked by either a far call or a near call. 
     DISCLOSURE OF THE INVENTION 
     It is an object of the present invention to provide a method for linking subroutines so that the subroutines can be efficiently invoked by both far calls and near calls. 
     It is another object of the present invention to provide a method for linking subroutines such that the number of instructions executed is reduced. 
     These and other objects, which will become apparent as the invention is more fully described below, are obtained by providing an improved method of subroutine linkage. In a preferred embodiment, a subroutine is designed to be invoked by both a near call and a far call. The subroutine has a near entry point and a far entry point. When the subroutine is invoked through the near entry point, it executes a near return upon completion. When the subroutine is invoked through the far entry point, it first pushes an offset (stored in one byte) of a far return instruction onto the stack. It then starts executing at the near entry point. When the near return instruction is executed, it pops the offset pushed by the instruction executed at the far entry point. The processor then continues execution at the far return instruction, which the offset points to, to effect a return to the instruction after the far call. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIGS. 1A through 1D trace the execution of a near call and a near return of prior systems. 
     FIGS. 2A through 2D trace the execution of a far call and far return of prior systems. 
     FIGS. 3A through 3D trace the execution of a near call and near return. 
     FIGS. 4A through 4F trace the execution of a far call and far return. 
     FIGS. 5A through 5D trace the execution of a near call and near return of a preferred embodiment of the present invention. 
     FIGS. 6A through 6F trace the execution of a far call and far return of a preferred embodiment of the present invention. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     A preferred embodiment of the present invention provides a method for linking subroutines in a way that the subroutine may be invoked using both a far call and a near call. The description of the invention that follows uses the term &#34;address&#34; symbolically. One skilled in the art will appreciate that the instructions referred to may be multi-byte instructions. However, the addresses used refer to the logical addresses of the instructions. For example, the &#34;CALLN 500&#34; stored at logical address 150, is a multi-byte instruction. However, the next instruction is shown at address 151, instead of address 150 plus the number of bytes in the &#34;CALLN 500&#34; instruction. 
     An example of the subroutine linking used in prior systems is shown in FIGS. 1A through 1D and 2A through 2D. FIGS. 1A through 1D show the linking method for calling a near subroutine. The stack shows the state of the stack at various times during calling and returning from the subroutine. The Stack Segment (SS) register points to the segment that contains the stack, and the Stack Pointer (SP) register contains the offset in SS of the top of the stack. The code segment contains the program that calls the subroutine and the subroutine. The Code Segment (CS) register points to the segment that contains the code, and the Instruction Pointer (IP) register contains an offset into the code segment of the instruction currently being executed. One skilled in the art will appreciate that the various microprocessors in the 8086-family employ different techniques for mapping a value in a segment register to a segment address. However, a segment register points either directly or indirectly to a segment. The subroutine is stored at offset 500 through 512 in the code segment. The entry point of the subroutine being at offset 500. The near return (RETN) for the subroutine is stored at offset 512. The near call which invokes the subroutine is stored at offset 150 in the code segment. The call instruction is &#34;CALLN 500.&#34; The &#34;CALLN&#34; represents the operation code for the near call, and the &#34;500&#34; represents the entry point of the subroutine to be invoked. 
     FIG. 1A shows the state of stack, code segment, and associated registers (referred to as state of the processor in the following) just before the execution of the CALLN instruction at offset 150 in the code segment. FIG. 1B shows the state of the processor after execution of the CALLN instruction. When the CALLN was executed, the next address after the CALLN instruction, that is, offset 151 in the code segment, was pushed onto the stack. The IP register was set to 500, which is the entry point of the subroutine. 
     FIG. 1C shows the state of the processor just before the subroutine executes the near return (RETN) instruction. The IP register points to the RETN instruction. Although the subroutine may have pushed data on and popped data off the stack, the SP register points to the return offset in the code segment. The RETN instruction causes the stack to be popped and the IP register to be set to the popped value, offset 151 in this example. 
     FIG. 1D shows the state of the processor after the RETN instruction is executed. The stack no longer contains the offset and the IP register points to the instruction immediately following the CALLN instruction. 
     FIGS. 2A through 2D show an example of the linking method of prior systems for calling a far subroutine. The stack shows the state of the stack before the far call (CALLF) instruction is executed. The SS register points to the segment that contains the stack, and the SP register contains the offset in SS of the top of the stack. In this example, the code segment number 10 contains the program that calls the subroutine, and the code segment number 27 contains the subroutine. The CS register points to the code segment currently being executed. The IP register contains an offset into the current code segment of the instruction to be executed next. The subroutine is stored at offset 500 through 512 in the code segment number 27. The entry point of the subroutine is at offset 500 in code segment number 27. The far return (RETF) from the subroutine is stored at offset 512 in code segment number 27. The far call which invokes the subroutine is stored at offset 150 in code segment number 10. The call instruction is &#34;CALLF 27:500.&#34; The &#34;CALLF&#34; represents the operation code for the far call and the &#34;27:500&#34; represents the entry point of the subroutine to be invoked. The &#34;27&#34; is the code segment number of the segment where the subroutine is located. The &#34;500&#34;  contains the offset in code segment number 27 of the entry point to the subroutine. 
     FIG. 2A shows the state of the processor before the CALLF instruction is executed. As shown in FIG. 2B, the CALLF instruction causes the current code segment number 10 to be pushed onto the stack. The offset of the instruction after the CALLF, that is, offset 151 is also pushed onto the stack. The CALLF instruction causes the CS register to be set to 27, which is the segment number where the subroutine is located. The CALLF instruction also causes the IP register to be set to 500, which is the offset into code segment number 27 of the entry point of the subroutine. 
     FIG. 2C shows the state of the processor before the RETF instruction of the subroutine is executed. The RETF instruction causes the stack to be popped twice. The IP register is set to first popped value which is the offset in code segment number 10 at which the subroutine is to return to. The CS register is set to point to code segment number 10. This effects the return from the subroutine. FIG. 2D shows the state of the processor after the return from the subroutine. 
     FIGS. 3A through 3D show a method of near subroutine linkage. FIG. 3A shows a code segment which contains a subroutine. The subroutine has two instructions added to support subroutine linkage. One instruction is a RETF instruction and the other instruction is a PUSH instruction. The PUSH instruction pushes the offset of the RETF instruction onto the stack. As shown in FIG. 3A, the RETF instruction is stored two instructions before the entry point of the subroutine at offset 498, and the PUSH instruction is stored one instruction before the entry point at offset 499. 
     The instruction sequence shown in FIGS. 3A through 3D is identical to the sequence shown in FIGS. 1A through 1D. The advantages of including the RETF and the PUSH instructions before a subroutine can be illustrated by a far call invoking the subroutine. 
     FIGS. 4A through 4F trace the execution of a far call to the subroutine. The subroutine is stored in a different code segment than the location of the far call. In the example of FIG. 4A, the subroutine is the same as that shown in FIG. 3A, except that it is stored in a different code segment. The same two instructions, RETF and PUSH, are placed before the entry point at offset 500. The subroutine also has a RETN instruction at offset 512. The call instruction in code segment 10 is a far call that specifies an entry point of offset 499, rather than 500. The entry point at offset 499 is referred to as the far entry point. The entry point at offset 500 is referred to as the near entry point. 
     Tracing the execution of the far call and far return will show how the same subroutine can be invoked either by a far call or a near call and return to the proper address which is the address of the instruction after the calling instruction. FIG. 4A shows the state of the processor before the &#34;CALLF 27:499&#34; instruction is executed. The execution of the far call causes the return address, that is, the code segment number 10 and the offset 151, to be pushed onto the stack. The execution also causes the CS register to be set to 27 and the IP register to be set to 499. The offset 499 can be considered a secondary entry point into the subroutine. The 499 entry point is used by far calls. FIG. 4B shows the state of the processor after the CALLF instruction is executed. 
     FIG. 4C shows the state of the processor after the &#34;PUSH 498&#34; instruction is executed. The PUSH instruction pushes the offset 498 of the RETF instruction onto the stack and the IP register is set to point to the next instruction, which is at offset 500. 
     FIG. 4D shows the state of the processor before the RETN instruction is executed. The top of the stack contains the offset 498 of the RETF instruction. When the RETN instruction is executed, the offset 498 is popped from the stack and the IP register is set to that value. FIG. 4E shows the state of the processor after the RETN is executed. The IP register points to the RETF instruction. When the RETF instruction is executed, offset 151 and code segment number 10 are popped from the stack. The CS register is set to point to code segment number 10 and the IP register is set to point to the offset 151. FIG. 4F shows the state of the processor after the RETF is executed. The CS register points to code segment number 10, and the IP register points to the instruction after the CALLF instruction to complete the return from the subroutine. 
     The use by a far call instruction of the alternate entry point at offset 499 allows the offset of the RETF instruction to be pushed onto the stack. When the RETN instruction at the end of the subroutine is executed, the offset of the RETF instruction is popped from the stack and execution continues at the RETF instruction. The RETF instruction then causes the code segment number and offset of the return address to be popped from the stack to effect the far return. 
     FIGS. 5A through 5D and 6A through 6F show a preferred embodiment of the present invention. FIGS. 5A through 5D trace the execution of the near call and near return. Again, the execution is the same as shown in FIGS. 1A through 1D and 3A through 3D. The subroutine stored at offset 500 through 512 is the same. However, in the preferred embodiment, a RETF instruction and a &#34;PUSH 0&#34; instruction are included in the code segment. The RETF instruction is stored at offset 0 in the code segment and the &#34;PUSH 0&#34; instruction is stored at offset 499. 
     The execution of the call and return functions is similar to the embodiment shown in FIGS. 3A through 3D and 4A through 4F. An advantage of the preferred embodiment is that for certain computers, such as those based on the 8086-family, the &#34;PUSH 0&#34; instruction can be stored as a 2-byte instruction: 1-byte operation code and 1 byte of immediate data, the 0. Whereas PUSH instructions typically are a 6-byte instruction. Also the RETF instruction needs to be stored once for each code segment, rather than once for each subroutine. In other words, all the subroutines in a given code segment can share the same RETF instruction. One skilled in the art would appreciate that one byte of immediate data can refer to offsets less than 128 or greater than 65,407. 
     FIGS. 6A through 6F trace the execution of a far call and far return in the preferred embodiment. Tracing the execution of the far call and far return will show how the same subroutine can be invoked either by a far call or a near call and return to the proper address. FIG. 6A shows the state of the processor before the &#34;CALLF 27:499&#34; instruction is executed. The execution of the far call causes the return address, that is, the code segment number 10 and the offset 151, to be pushed onto the stack. The execution also causes the CS register to be set to 27 and the IP register to be set to 499. The offset 499 can be considered a secondary entry point into the subroutine. The 499 entry point is used by far calls. FIG. 6B shows the state of the processor after the CALLF instruction is executed. 
     FIG. 6C shows the state of the processor after the &#34;PUSH 0&#34; instruction is executed. The PUSH instruction pushes the offset 0, which is the offset of the RETF instruction, onto the stack and the IP register is set to point to the next instruction offset 500. 
     FIG. 6D shows the state of the processor before the RETN instruction is executed. The top of the stack contains offset 0, which is the offset of the RETF instruction. When the RETN instruction is executed, the offset 0 is popped from the stack and the IP register is set to that value. FIG. 6E shows the state of the processor after the RETN instruction is executed. The IP register points to the RETF instruction. When the RETF instruction is executed, offset 151 and code segment number 10 are popped from the stack. The CS register is set to point to code segment number 10 and the IP register is set to point to the offset 151. FIG. 6F shows the state of the processor after the RETF instruction is executed. The IP register points to the instruction after the CALLF instruction to complete the return from the subroutine. 
     Although the present invention has been described in terms of preferred embodiments, it is not intended that the invention be limited to these embodiments. Modifications within the spirit of the invention will be apparent to those skilled in the art. The scope of the present invention is defined by the claims that follow.