Abstract:
A three-stage hybrid stack model includes two separate stages of registers, or in other words, two register stacks. Below the two register stages is a memory stage, or memory stack. As operands are pushed onto the top register stack, operands residing in registers are moved down to accommodate the new operands. A second register stack, or transfer register stack receives overflow from the top register stack and supplies operands to the top register stack when the top register stack is underflowed. A third stage made up of memory locations is used to store overflow from the transfer register stack. The memory stack also supplies operands to the transfer register stack as needed.

Description:
TECHNICAL FIELD  
       [0001]     The invention relates to stack models. More particularly, the invention relates to a hybrid memory/register stack model applicable to stack caching.  
       BACKGROUND  
       [0002]     There are two common ways to run programs written in a high-level language. One method is to compile the source code to create executable machine code, and then execute the machine code. Another method is to pass the source code through an interpreter. An interpreter translates the high-level instructions in the source code into an intermediate form, which it then executes. Interpreters are valuable in building a virtual machine using a stack-based language despite the fact that compiled programs typically run faster than interpreted programs. The advantage of an interpreter, however, is that it does not need to go through the compilation stage during which machine instructions are generated.  
         [0003]     The compiler used in a virtual machine (e.g. Java Virtual Machine) environment, also known as a Just-In-Time compiler, is used to compile bytecode into machine instructions. Similarly, the interpreter used in a virtual machine is a bytecode interpreter. It is used to interpret bytecode into machine instructions. Compared to the Just-In-Time compiler, the bytecode interpreter has a smaller footprint, along with the additional benefits of simplicity and portability.  
         [0004]     On a register-based computer architecture, the classic approach to implementing an interpreter using a stack-based language is to use a memory data structure to imitate a stack. When virtual machine instructions use operands, those operands are retrieved from memory. Accessing memory is substantially more time consuming than accessing registers. Thus, the cost of accessing memory for each operand can be significant and may create a performance bottleneck in the system.  
         [0005]     One solution to the performance bottleneck is stack caching. Stack caching involves keeping source and destination operands of instructions in registers so as to reduce memory accesses during program interpretation. Stacks exhibit a last-in-first-out (LIFO) behavior when pushing and popping operands to and from the stack. Thus, in a stack-programming model, the top part of an operand stack contains the most recently used operands.  
         [0006]     In stack caching, the operand stack spans a set of registers and memory locations, and is, therefore, often referred to as a hybrid stack. Given that the top of the operand stack contains the most recently used operands, the top part of the operand stack is comprised of registers. The lower part of the operand stack is made up of memory locations. The upper portion of the hybrid stack containing registers is referred to as the register stack while the lower portion of the hybrid stack containing the memory locations is called the memory stack. When combined, the register stack and the memory stack form the overall hybrid stack model.  
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0007]     The invention is illustrated by way of example, and not by way of limitation, in the figures of the accompanying drawings in which like reference numerals refer to similar elements.  
         [0008]      FIG. 1  is a block diagram of a three-stage hybrid stack.  
         [0009]      FIG. 2   a  illustrates the moving of operands in a hybrid stack model.  
         [0010]      FIG. 2   b  illustrates the moving of operands in a hybrid stack model.  
         [0011]      FIG. 3   a  is a block flow diagram of one embodiment of the invention.  
         [0012]      FIG. 3   b  is block flow diagram of one embodiment of the invention.  
     
    
     DETAILED DESCRIPTION  
       [0013]     In the following description, for purposes of explanation, numerous specific details are set forth in order to provide a thorough understanding of the invention. It will be apparent, however, to one skilled in the art that the invention can be practiced without these specific details. In other instances, structures and devices are shown in block diagram form in order to avoid obscuring the invention.  
         [0014]     The three-stage hybrid stack model described herein can be used in an implementation of a virtual machine. One example is Intel Corporation&#39;s Java virtual machine, Xorp, for its Xscale® microarchitecture. In another embodiment, the three-stage hybrid stack model could be used in a stack model CPU, or stack machine, to implement a stack architecture more efficiently.  
         [0015]     In a one embodiment, the three-stage hybrid stack model is used in an implementation of an interpreter in a virtual machine. The invention improves the efficiency of stack caching by introducing a transfer register stack, which reduces memory accesses during interpretations. In another embodiment, the three-stage hybrid stack model is used in a compiler.  
         [0016]      FIG. 1  is a block diagram of a three-stage hybrid stack model according to one embodiment of the invention.  FIGS. 3   a  and  3   b  are block flow diagrams of a three-stage hybrid stack model according to one embodiment of the invention. Operands are pushed ( 390 ) onto the top of the first register stack (head register stack, or RS H )  103  and, more specifically, onto register  110 . In order to accommodate a new operand in register  110 , any existing operand in register  110  is moved downward to the next register  112 . If there is an operand residing in register  112 , it must be moved downward in a similar manner to accommodate the operand being moved from register  110 . This process of moving operands downward ( 382 ) to accommodate new operands continues down the length of the register stack in a cascading fashion until reaching the final register  118  in the head register stack.  
         [0017]     In one embodiment, operands are pushed ( 380 ) from head register stack  103  onto a transfer register stack  104  when head register stack  103  becomes full ( 350 ). More specifically, an operand in register  118  is pushed onto transfer register stack (or RS T )  104  and into register  120 .  
         [0018]     Transfer register stack  104  receives operands into its registers beginning with register  120 , when the overall number of operands in the hybrid stack exceeds the number of registers in the head register stack. Thus, transfer register stack  104  is used to cache operands pushed from head register stack  103  when head register stack  103  is full. Transfer register stack  104  also supplies operands to the head register stack when operands are popped off RS H .  
         [0019]     In order to accommodate pushing a new operand onto transfer register stack  104 , any operand residing in register  120  is moved down to register  122 . Any operand residing in register  122  is similarly moved down to accommodate the operand being moved from register  120 . This process of moving operands downward ( 372 ) continues down the length of transfer register stack  104  as operands are pushed onto the transfer register stack.  
         [0020]     In one embodiment, if both head register stack  103  and transfer register stack  104  are full ( 360 ), operands are spilled ( 370 ) from transfer register stack  104  into memory stack (MS)  105 . Storing operands in the memory stack can involve a cascade of shift operations in memory stack  105 . However, in one embodiment, operands are stored in the memory stack by way of a memory store followed by updating a stack pointer. This process is shown in  FIG. 2   a.    
         [0021]     When the transfer register stack overflows, the operand residing in register  214  is spilled into the memory stack. A stack pointer, sp  251 , keeps track of the location of the top of the memory stack. As seen in  FIG. 2   a , stack pointer  251  shows memory slot  220  as the top of the memory stack before a new stack operand is received. Once a new stack operand is received, and assuming the transfer register stack is full, the operand in register  214  is spilled into memory. A new memory slot  218  is created to receive the spilled operand. Upon receiving the new operand into memory slot  218 , the stack pointer is updated to sp&#39;  253  so that it points to memory slot  218 . In this way, the updated stack pointer always points to the top of the memory stack.  
         [0022]     In one embodiment, operands are popped off head register stack  103  as needed for program execution ( 310 ). If the current length of the overall hybrid stack is longer than the length of head register stack  103 , then operands are popped into head register stack  103  from transfer register stack  104  ( 320 ). The popping of operands into head register stack  103  is done in proportion to the number of operands being popped off head register stack  103  for program execution. In other words, operands are popped into head register stack  103  when it is less than full or when it has fewer than a threshold number of operands.  
         [0023]     As operands are popped off head register stack  103  for program execution, any remaining operands in head register stack  103  are moved upward in the stack from bottom to top ( 312 ). As operands are moved from bottom to top, new operands are popped into the bottom of head register stack  103  from transfer register stack  104 . In this way, transfer register stack  104  serves to maintain a threshold number of operands in head register stack  103 .  
         [0024]     It is not necessary for transfer register stack  104  to be kept full in the same way that head register stack  103  is kept full. The purpose of transfer register stack  104  is to supply head register stack  103  with operands such that head register stack  103  maintains a threshold number of operands.  
         [0025]     As operands are popped off transfer register stack  104  and into head register stack  103 , remaining operands in transfer register stack  104  are moved upward from bottom to top ( 332 ). In one embodiment, operands are loaded into transfer register stack  104  from memory stack  105  when transfer register stack  104  is empty ( 330 ,  340 ). In another embodiment, operands are loaded from memory stack  105  into transfer register stack  104  when it is not empty. The number of operands being loaded into transfer register stack  104  can be fixed or it can be variable. In one embodiment, operands are loaded one by one in proportion to the rate at which operands are being popped off transfer register stack  104 . In another embodiment, multiple operands are loaded from memory stack  105  into the transfer register stack concurrently. Any number of operands can be loaded-up to the number of registers in transfer register stack  104 . In one embodiment, the number of operands being loaded from memory stack  105  is equal to the number of registers in transfer register stack minus the number of registers in the transfer register stack that are already occupied.  
         [0026]      FIG. 2   b  illustrates how an operand is loaded from the memory stack into the transfer register stack. The stack pointer, sp  255 , points to the top of memory stack at memory slot  220 . To accommodate the operand from memory slot  220  into the transfer register stack, existing operands in the transfer register stack are moved upward. The operand in register  212  of  FIG. 2   b  is moved into the empty register  210 . The operand in register  212  is moved into register  212 . With register  214  now empty, the operand from memory slot  220  in the memory stack is loaded into register  214 . Once the operand in memory slot  220  has been loaded, the stack pointer is updated to sp&#39;  257  and points to memory slot  222 , which is now the top of the memory stack.  
         [0027]     Reference in the specification to “one embodiment” or “an embodiment” means that a particular feature, structure, or characteristic described in connection with the embodiment is included in at least one embodiment of the invention. The appearances of the phrase “in one embodiment” in various places in the specification are not necessarily all referring to the same embodiment.  
         [0028]     In the foregoing specification, the invention has been described with reference to specific embodiments thereof. It will, however, be evident that various modifications and changes can be made thereto without departing from the broader spirit and scope of the invention. The specification and drawings are, accordingly, to be regarded in an illustrative rather than a restrictive sense.