Abstract:
Various embodiments include methods and related media for performing operations including a return operation. One such method includes testing a content of a return value register and setting status flags. Testing the content of the return value register and setting the status flags are performed in response to a single instruction.

Description:
RELATED APPLICATIONS 
     This application is a continuation of U.S. patent application Ser. No. 11/149,611, filed on Jun. 10, 2005, which is incorporated herein by reference in its entirety. 
    
    
     FIELD 
     This invention relates to subprogram return operations in microprocessors. 
     BACKGROUND 
     Programs frequently feature subroutines which perform a specific task. After the task is performed, program flow returns from the subroutine to the main program. One common mechanism for performing a subroutine return involves conditionally or unconditionally moving the contents of a return address register into a program counter and then continuing program execution. A return value register may also be updated with a constant literal that may represent a Boolean value. Another approach to subprogram returns is to “pop” a return address from the stack and into the program counter and continue program execution from there. This operation may also pop any spooled-out register file contents from the stack into the register file. 
     These methods for performing subroutine returns take several cycles to execute. In  FIG. 1 , when a traditional return (“RET”) instruction is executed in a typical pipelined CPU, five cycles  10  are required to execute the instruction. In  FIG. 2 , a typical pipelined CPU contains a Program Counter (“PC”)  42  and an instruction memory  44 . The CPU has four different pipeline registers  46 ,  52 ,  56 , and  60  separating the different pipeline stages. The Instruction Decode stage (between registers  46  and  52 ) contains both a control/decode unit (“CU”)  48  for decoding the current instruction and generating control signals and a register file  50 . The Execution Stage (between registers  52  and  56 ) contains an Arithmetic Logic Unit (“ALU”)  54 . The Memory Stage (between registers  56  and  60 ) contains a data memory  58 .) With continued reference to  FIG. 1 , during cycle  1 , in the Instruction Fetch (“IF”) stage  12 , the RET instruction is fetched (block  22 ). In cycle  2 , in the Instruction Decode (“ID”) stage  14 , correct control signals are generated and the return address register is read from the register file (block  24 ). In cycle  3 , in the Execution (“EX”) stage  16 , the return address register content is written through the Arithmetic Logic Unit (“ALU”) with no change (block  26 ). During cycle  4 , in the Memory (“MEM”) stage  18 , the return address register content is written past the data memory. Finally, in cycle  5 , in the Writeback (“WB”)  20  stage, the return address register content is written to the Program Counter (“PC”) and the pipeline is flushed (block  30 ). Once the pipeline is flushed, the pipeline does not contain any instructions until the instruction at the return address is read from program memory. Therefore, several clock cycles are wasted in the pipeline flush process. 
     A similar issue exists for a return instruction (“RETMEM”) popping the return address register from a stack in memory. As shown in  FIG. 3 , in cycle  1 , in the IF stage, the RETMEM instruction is fetched (block  32 ). During cycle  2 , in the ID stage, the correct control signals are generated. In cycle  3 , during the EX stage, the control signals to the data memory are routed past the ALU (block  36 ). In cycle  4 , in the MEM stage, the return address is read from data memory (block  38 ). Finally, in cycle  5 , in the WB stage, the return address read from memory is written to PC and the pipeline is flushed (block  40 ). As with the return instruction discussed in  FIG. 1 , several cycles are wasted after the pipeline flush. 
     It would be advantageous to provide a more efficient subroutine return operation. 
     SUMMARY 
     In an exemplary embodiment, an instruction is fetched which requires a return operation and sets status flags based on the contents of a return value register. The status flags are set in parallel with at least one other operation required to process the return instruction. The status flags are set before one of the following occurs: i) contents of a return address register are moved into a program counter; or ii) a return address is popped from a stack and into the program counter. In another embodiment, a processor-readable storage medium causes a processor to perform this subroutine return operation. 
     In yet another exemplary embodiment of the invention, a subroutine return operation places a return address into a program counter. A test operation is executed on a return value register; the test operation is performed in parallel with at least one other operation required to process the return operation. The program flow is changed to a target address. Each of the above-mentioned steps is performed in response to a single instruction. In one embodiment, a processor-readable storage medium stores an instruction that causes a processor to perform this subroutine return operation. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  is a chart showing how a return instruction is executed in the prior art. 
         FIG. 2  is a block diagram of a pipelined CPU in the prior art. 
         FIG. 3  is a chart showing how a return instruction popping the return address register from a stack in memory is executed in the prior art. 
         FIG. 4  is a block diagram of a pipelined CPU in an exemplary embodiment of the present invention. 
         FIG. 5  is a chart showing an exemplary execution of a return instruction in an embodiment of the present invention. 
         FIG. 6  is a chart showing an exemplary execution of a return instruction popping the return address register from a stack in memory is executed in an embodiment of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     A more efficient subroutine return operation is provided in which status flags are updated (in the processor&#39;s status register) according to a test of the return value register during the subroutine return operation. (In the prior art, test operations, for instance, a test of the return value register, are performed in response to a separate instruction.) In one embodiment, the status flags are set in parallel with operations to execute single instructions such as conditional return instructions as well as single instructions incorporating a return operation. The instructions are stored in a processor-readable medium, which includes any medium that can store or transfer information, such as an electronic circuit, a semiconductor memory device, a ROM, a flash memory, a floppy diskette, a compact disc, an optical disc, etc. 
     These instructions can be executed by existing hardware. In  FIG. 4 , an exemplary CPU for executing these instructions includes a PC  62  and instruction memory  64 . The CPU contains four pipeline registers (IF/ID  66 , ID/EX  70 , EX/MEM  74 , and MEM/WB  78 ) separating the different stages. The ID stage, between registers  66  and  70 , contains a control/decode unit  68  for decoding the current instruction and generating the correct control signals. The ID stage also contains a register file  132 . The EX stage, between registers  70  and  74 , contains an ALU  72  and a flag register  84 . The MEM stage, between registers  74  and  78 , contains data memory  76 . When an address has reached the WB stage (after register  78 ), the pipeline has been flushed and the fetch address is written to PC  62 . A multiplexer  118  determines which address is written into the register file or the program counter (this is discussed in greater detail, below). In other embodiments, the processor may have different features, such as data forwarding; as noted above, the CPU described in  FIG. 4  is exemplary and is not the only processor which can execute the more efficient subroutine return operation described herein. 
     In one embodiment of the invention, test operations are performed in parallel with other operations during execution of instructions with the more efficient subroutine return operation. In one embodiment, shown in  FIG. 5 , when a return (“return_with_test”) instruction is executed, during cycle  1  in the IF stage, the return_with_test instruction is fetched (block  86 ). In cycle  2 , the return_with_test has entered the ID stage; the correct control signals are generated and the return address register is read from the register file (block  88 ). In cycle  3 , the return_with_test is kept in the ID stage an additional cycle (in one embodiment, this may be done in the decode stage by splitting the instruction into two “micro-operations”: one micro-operation performs the test operation, the other micro-operation performs the return operation); in this second cycle, the return value register is read from the register file and control signals to instruct the ALU to perform the test operation are generated (block  90 ). In cycle  3  in the EX stage, the return address content is written through the ALU with no change (block  92 ). During cycle  4  in the EX stage, the ALU sets the flags corresponding to the test of the value register (block  94 ). (In this embodiment, the status flags are set according to a comparison of the return value register&#39;s contents with zero. Status flags used in this embodiment indicate overflow (“V”), a negative value (“N”), a zero result (“Z”), and a carry after an arithmetic or logic operation (“C”). Different status flags may be used in other embodiments and/or status flags may be set differently in other embodiments.) During cycle  4  in the MEM stage, the return address register content is written past the data memory (block  96 ). During cycle  5 , in the WB stage, the return address register content is written to the PC and the pipeline is flushed (block  98 ). A test operation has been performed using cycles that would otherwise be unused due to the pipeline flush. 
     In another embodiment, a test operation may be performed during execution of a return instruction (“pop_with_test”) popping the return address register from a stack in memory. In  FIG. 6 , in cycle  1  in the IF stage, the pop_with_test instruction is fetched (block  100 ). During cycle  2 , in the ID stage, the correct control signals are generated (block  102 ). In cycle  3 , the pop_with_test is kept in the ID an additional cycle (in one embodiment, the instruction is decoded into two micro-operations (the subroutine return operation and the test operation) in the ID stage); the return value register is read from the register file and control signals to instruct the ALU to perform the test operation are generated (block  104 ). In cycle  3 , in the EX stage, the control signals to data memory are routed past the ALU (block  106 ). In cycle  4 , in the EX stage, the ALU sets the flags corresponding to the test of the return value register (block  108 ). During the same cycle, in the MEM stage, the return address is read from data memory (block  110 ). In cycle  5 , in the WB stage, the return address read from memory is written to PC and the pipeline is flushed (block  112 ). 
     Other embodiments of the invention may vary from the embodiments discussed above. These embodiments may require fewer or additional clock cycles to execute instructions. Other embodiments may require different hardware to execute the instructions. Still other embodiments may be incorporated into different subprogram return operations and instructions. 
       FIGS. 5 and 6  are exemplary embodiments of “return_with_test” and “pop_with_test” instructions, respectively. In the “return_with_test” instruction, a “return” is performed together with testing the value in the return value register. The “test” tests the specified register and sets the condition code flags accordingly. The “pop_with_test” instruction performs a “pop” (loading a word from the stack into a specified register or a program counter; popping to PC flushes the pipeline and starts fetching instructions from the address loaded from the stack) together with testing the value in the return value register. 
     Various signals are required from the control/decode unit. Returning to  FIG. 4 , the following signals required in one embodiment are: 
     pcmux_sel  114 —Selector signal used to choose if the program counter is going to be updated with the sequential program address or the address given by the return instruction. 
     wbmux_sel  116 —Selector signal used by the writeback stage to determine which address is to be written into the register file or into the program counter. If signal is logic “0,” the address comes from the ALU result from the EX/MEM pipeline stage. If the signal is logic “1,” the address comes from the data memory. 
     as_ctrl  120 —Control signal used to choose if the adder in the ALU will perform subtraction or addition on the operands from the register file. 
     zeromux_sel  122 —Signal used to force input operand B to the ALU to integer value zero. 
     readreg 1   124 —Register file register number for operand  1 . 
     readreg 2   126 —Register file register for operand  2 . 
     loadflag  128 —Control signal to allow the status register to update the flag settings. 
     writeaddr 130 —Register file register number for the register where the result is written back. 
     The following table lists exemplary outputs from the control/decode unit in the cycles of the RET instruction. The registers identified in the table are: 
     R 12 —the Return Value Register. Test operations are performed on this register. 
     LR—the Link Register. Keeps the address to return to after the subprogram has completed. LR may also be referred to as the Return Address Register (RAR) 
     PC—the Program Counter. Holds the address of the currently executing instruction. 
     The following table lists exemplary outputs from the control/decode unit in the cycles of the return_with_test instruction. 
     
       
         
               
               
               
             
           
               
                   
               
               
                 Cycle 
                 Control signal output 
                 Textual instruction 
               
               
                   
               
             
             
               
                 1 
                 pcmux_sel = 1 
                 Write the contents of LR 
               
               
                   
                 wbmux_sel = 0 
                 into the PC register so that 
               
               
                   
                 as_ctrl = add 
                 instruction fetch will 
               
               
                   
                 zeromux_sel = 0 
                 restart from this address. 
               
               
                   
                 readreg1 = X (don&#39;t care value) 
               
               
                   
                 readreg2 = LR 
               
               
                   
                 loadflag = 0 
               
               
                   
                 writeadr = X (don&#39;t care value) 
               
               
                 2 
                 pcmux_sel = 0 
                 Test the contents of the 
               
               
                   
                 wbmux_sel = X (don&#39;t care 
                 Return Value Register by 
               
               
                   
                 value) 
                 comparing it with the 
               
               
                   
                 as_ctrl = sub 
                 value 0. Write the 
               
               
                   
                 zeromux_sel = 0 
                 resulting flags into the 
               
               
                   
                 readreg1 = X (don&#39;t care value) 
                 Flag Register. 
               
               
                   
                 readreg2 = Return Value 
               
               
                   
                 Register 
               
               
                   
                 loadflag = 1 
               
               
                   
                 writeadr = X (don&#39;t care value) 
               
               
                   
               
             
          
         
       
     
     The following table lists exemplary outputs from the control/decode unit in the cycles of the pop_with_test instruction. 
     
       
         
               
               
               
             
           
               
                   
               
               
                 Cycle 
                 Control signal output 
                 Textual instruction 
               
               
                   
               
             
             
               
                 1 
                 pcmux_sel = 1 
                 Write the contents of the 
               
               
                   
                 wbmux_sel = 1 
                 return address read from 
               
               
                   
                 as_ctrl = add 
                 memory into the PC 
               
               
                   
                 zeromux_sel = 0 
                 register so that instruction 
               
               
                   
                 readreg1 = X (don&#39;t care 
                 fetch will restart from this 
               
               
                   
                 value) 
                 address. The return 
               
               
                   
                 readreg2 = Pointer Register 
                 address resides in a 
               
               
                   
                 loadflag = 0 
                 memory address pointed 
               
               
                   
                 writeadr = X (don&#39;t care 
                 to by the pointer register. 
               
               
                   
                 value) 
               
               
                 2 
                 pcmux_sel = 0 
                 Test the contents of the 
               
               
                   
                 wbmux_sel = X (don&#39;t care 
                 Return Value Register by 
               
               
                   
                 value) 
                 comparing it with the 
               
               
                   
                 as_ctrl = sub 
                 value 0. Write the 
               
               
                   
                 zeromux_sel = 0 
                 resulting flags into the 
               
               
                   
                 readreg1 = X (don&#39;t care 
                 Flag Register. 
               
               
                   
                 value) 
               
               
                   
                 readreg2 = Return Value 
               
               
                   
                 Register 
               
               
                   
                 loadflag = 1 
               
               
                   
                 writeadr = X (don&#39;t care 
               
               
                   
                 value) 
               
               
                   
               
             
          
         
       
     
     The “return_with_test” and “pop_with_test” instructions can be executed as part of other instructions. For instance, the “return_with_test” instruction can be executed as part of a conditional return instruction, in which there is a return from the subroutine if a specified condition is true. Values are moved into the return register, the return value is tested, and flags are set. A specific example of this instruction is the “ret{cond 4 }” instruction in the ATMEL AVR 32  instruction set. The following pseudocode describes the ret{cond 4 } instruction (SP is the stack pointer register): 
     
       
         
               
             
           
               
                   
               
             
             
               
                 Operation: 
               
               
                   I. If (cond4) 
               
               
                     If (Rs != {LR, SP, PC}) 
               
               
                       R12 ← Rs; 
               
               
                     else if (Rs == LR) 
               
               
                       R12 ← −1; 
               
               
                     else if (Rs == SP) 
               
               
                       R12 ← 0; 
               
               
                     else 
               
               
                       R12 ← 1; 
               
               
                     Test R12 and set flags; 
               
               
                     PC ← LR; 
               
               
                 Syntax: 
               
               
                 I. ret{cond4} Rs 
               
               
                 Operands: 
               
               
                 I. cond4 ε {eq, ne, cc/hs, cs/lo, ge, lt, mi, pl, ls, gt, le, hi, vs, vc, qs, al} 
               
               
                 s ε {0, 1, ... , 15} 
               
               
                 Status Flags: 
               
               
                 Flags are set as result of the operation CP R12, 0. 
               
               
                 V: V ← 0 
               
               
                 N: N ← RES[31] 
               
               
                 Z: Z ← (RES[31:0] == 0) 
               
               
                 C: C ← 0 
               
               
                   
               
             
          
         
       
     
     The following table explains some of the mnemonics used above and the pseudocode for the “Load Multiple Registers” instruction, below: 
                                             Mnemonic   Meaning                           eq   Equal           ne   Not equal           cc/hs   Higher or same           cs/lo   Lower           ge   Greater than or equal           lt   Less than           mi   Minus/negative           pl   Plus/positive           ls   Lower or same           gt   Greater than           le   Less than or equal           hi   Higher           vs   Overflow           vc   No overflow           qs   Saturation           al   Always                        
The operation CP R 12 , 0 is a comparison or subtraction operation without operation. In this particular case, the result of the operation 32  R 12 −0.
 
     Another instruction in which the “return_with_test” operation may be employed is the “Load Multiple Registers” instruction from the AVR 32  instruction set. This instruction loads consecutive words pointed to by the register pointer into the register specified in the instruction. The PC can be loaded, resulting in a jump to the loaded target address. If the PC is loaded, the return value in R 12  is tested and the flags are updated. The return value optionally may be set to −1, 0, or 1. The following pseudocode describes this instruction (SP is a stack pointer): 
     
       
         
               
               
               
             
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 I. 
                 Loadaddress ← Rp; 
               
               
                   
                   
                 if Reglist16[PC] == 1 then 
               
               
                   
                   
                   if Rp == PC then 
               
               
                   
                   
                     Loadaddress ← SP; 
               
               
                   
                   
                   PC ← * (Loadaddress++); 
               
               
                   
                   
                   if Rp == PC then 
               
               
                   
                   
                     if Reglist16[LR,R12] == B′00 
               
               
                   
                   
                       R12 ← 0; 
               
               
                   
                   
                     else if Reglist16[LR,R12] == B′01 
               
               
                   
                   
                       R12 ← 1; 
               
               
                   
                   
                     else 
               
               
                   
                   
                       R12 ← −1; 
               
               
                   
                   
                     Test R12 and update flags; 
               
               
                   
                   
                   else 
               
               
                   
                   
                     Test R12 and update flags; 
               
               
                   
                   
                     if Reglist16[LR] == 1 
               
               
                   
                   
                       LR ← *(Loadaddress++); 
               
               
                   
                   
                     if Reglist16[SP] == 1 
               
               
                   
                   
                       SP ← *(Loadaddress++); 
               
               
                   
                   
                     if Reglist16[R12] == 1 
               
               
                   
                   
                       R12 ← *(Loadaddress++); 
               
               
                   
                   
                 else 
               
               
                   
                   
                   if Reglist16[LR] == 1 
               
               
                   
                   
                     LR ← *(Loadaddress++); 
               
               
                   
                   
                   if Reglist16[SP] == 1 
               
               
                   
                   
                     SP ← *(Loadaddress++); 
               
               
                   
                   
                   if Reglist16[R12] == 1 
               
               
                   
                   
                     R12 ← *(Loadaddress++); 
               
               
                   
                   
                 for (i = 11 to 0) 
               
               
                   
                   
                   if Reglist16[i] == 1 then 
               
               
                   
                   
                     Ri ← *(Loadaddress++); 
               
               
                   
                   
                 if Opcode[++] == 1 then 
               
               
                   
                   
                   if Rp == PC then 
               
               
                   
                   
                   SP ← Loadaddress; 
               
               
                   
                   
                 else 
               
               
                   
                   
                   Rp Loadaddress; 
               
             
          
           
               
                   
                 Syntax: 
               
               
                   
                 I. ldm Rp{++}, Reglist16 
               
               
                   
                 Operands: 
               
               
                   
                 I. Reglist16 ε {R0, R1, R2, ... , R12, LR, SP, PC} 
               
               
                   
                 p ε {0, 1, ... , 15} 
               
               
                   
                 Status Flags: 
               
               
                   
                 Flags are only updated if Reglist16[PC] == 1. 
               
               
                   
                 They are set as the result of the operation CP R12, 0. 
               
               
                   
                 V: V ← 0 
               
               
                   
                 N: N ← RES [31] 
               
               
                   
                 Z: Z ← (RES[31:0] == 0) 
               
               
                   
                 C: C ← 0 
               
               
                   
                   
               
             
          
         
       
     
     Similar instructions employing the “pop_with_test” operation may be employed in which words pointed to by SP are loaded into registers specified in the instruction. 
     An instruction in which the “pop_with_test” operation may be employed is the Pop Multiple Registers from Stack (“POPM”) instruction from the AVR 32  instruction set. This instruction loads the consecutive words pointed to by SP into the registers specified in the instruction. 
     While specific examples have been cited above showing how the subroutine return operation may be employed in different instructions, other embodiments may incorporate the subroutine operation into different instructions. 
     One advantage of the more efficient subroutine return operations is the reduction in code size, since an explicit “test return register” instruction can be eliminated since the test operation may be performed implicitly by the return operation. Another advantage is that execution time is reduced since the return register test is performed in parallel with the fetching of the instruction to which the program will return. 
     The instructions and operations described above may be employed in both RISC and CISC machines. 
     Although the present invention has been described in terms of specific exemplary embodiments, one skilled in the art will recognize variations and additions to the embodiments may be made without departing from the principles of the present invention. For instance, return operations may require more or fewer cycles to be executed, or the return operations may be part of different instructions, or the processors executing the return operations may have different architectures. In another embodiment, more hardware may be added so the return operations could be completed in one cycle (i.e., the two micro-operations performed in response to a single instruction are completed in one cycle).