Abstract:
The invention provides a method and system for operating a pipelined microprocessor more quickly, by detecting instructions that load from identical memory locations as were recently stored to, without having to actually compute the referenced external memory addresses. The microprocessor examines the symbolic structure of instructions as they are encountered, so as to be able to detect identical memory locations by examination of their symbolic structure. For example, in a preferred embodiment, instructions that store to and load from an identical offset from an identical register are determined to be referencing the identical memory location, without having to actually compute the complete physical target address.

Description:
RELATED APPLICATIONS 
   This application claims priority to copending provisional application No. 60/114,295 entitled “Symbolic Store-Load Bypass”, filed Dec. 31, 1998, by the same inventor. 
   The inventions described herein can be used in combination or conjunction with inventions described in the following patent applications (2):
         Application Ser. No. 60/114,296, Express Mail Mailing No. EE506030698US, filed Dec. 31, 1998, in the name of Anatoly Gelman, titled “Call Return Branch Production Buffer,” assigned to the same assignee, and all pending cases claiming priority thereof; and   Application Ser. No. 60/114,297, Express Mail Mailing No. EE506030684US, filed Dec. 31, 1998, in the name of Anatoly Gelman and Russell Schapp, titled “Block-Based Branch Table Buffer,” assigned to the same assignee, and all pending cases claiming priority thereof.       

   These applications are hereby incorporated by reference as if fully set forth herein. These applications are collective referred to herein as “incorporated disclosures”. 
   BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   This invention relates to microprocessor design. 
   2. Related Art 
   In microprocessors employing pipelined architecture, it is desirable to be in the process of executing as many instructions as possible, so that each element of the pipeline is maintained busy. However, some instructions, such as instructions that load data from external memory or store data into external memory, must generally be executed in their original sequence order, so as to avoid the external memory ever being in an incorrect state. Moreover, when such instructions refer to identical external memory locations, there is no particular need to wait for the actual external memory operations to complete, as the identical data is already available for the processor to operate with. 
   One problem in the known art is that determining whether two different instructions refer to the identical location in external memory generally requires computing the actual external memory address referenced by each of the two different instructions. This prolongs when the determination can be made, because it requires time (and typically, a pipeline stage) to actually compute the referenced external memory addresses. 
   Accordingly, it would be advantageous to provide a technique for operating a pipelined microprocessor more quickly, by detecting instructions that load from identical memory locations as were recently stored to, without having to actually compute the referenced external memory addresses. In a preferred embodiment, the microprocessor examines the symbolic structure of instructions as they are encountered, so as to be able to detect identical memory locations by examination of their symbolic structure. For example, instructions that store to and load from an identical offset from an identical register are determined to be referencing the identical memory location, without having to actually compute the complete physical target address. 
   SUMMARY OF THE INVENTION 
   The invention provides a method and system for operating a pipelined microprocessor more quickly, by detecting instructions that load from identical memory locations as were recently stored to, without having to actually compute the referenced external memory addresses. The microprocessor examines the symbolic structure of instructions as they are encountered, so as to be able to detect identical memory locations by examination of their symbolic structure. For example, in a preferred embodiment, instructions that store to and load from an identical offset from an identical register are determined to be referencing the identical memory location, without having to actually compute the complete physical target address. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
       FIG. 1  shows a block diagram of a system in a pipelined microprocessor for detecting identical locations referenced by different load and store instructions. 
       FIG. 2  shows a process flow diagram of a method for operating a system in a pipelined microprocessor for detecting identical locations referenced by different load and store instructions. 
   

   DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT 
   In the following description, a preferred embodiment of the invention is described with regard to preferred process steps and data structures. Embodiments of the invention can be implemented using circuits in a microprocessor or other device, adapted to particular process steps and data structures described herein. Implementation of the process steps and data structures described herein would not require undue experimentation or further invention. 
   System Elements 
     FIG. 1  shows a block diagram in a pipelined microprocessor for detecting identical locations referenced by different load and store instructions. 
   A microprocessor  100  includes a sequence of pipeline stages, including an instruction fetch state  110 , an instruction decode state  120 , an address computation state  130  and an instruction execution state  140 . In a preferred embodiment, the pipeline stages of the microprocessor  100  operate concurrently on sequences of instructions  151  in a pipelined manner. Pipeline operation is known in the art of microprocessor design. 
   In operation, the microprocessor  100  is coupled to an instruction memory  150  which includes a plurality of instructions  151 , at least some of which are memory load or store instructions. In a preferred embodiment, the instruction memory  150  includes a random access memory. Memory caching operations can be performed either by the instruction memory  150 , input and output elements of the microprocessor  100 , or both. Memory caching operations, as well as other aspects of reading and writing memory locations, are known in the art of computer memories and so are not further described herein. 
   The microprocessor  100  reads a sequence of instructions  151  from the instruction memory  150  using the instruction fetch stage  110  (and including any associated memory read or write elements in the microprocessor  100 ). In a preferred embodiment, the input instruction buffer  110  includes a plurality of instructions  151  from the instruction memory  150 , but there is no particular requirement therefor. 
   The instruction fetch stage  110  couples the instructions to the instruction decode state  120 . 
   The instruction decode stage  120  parses the instructions  151  to determine what types of instructions  151  they are (such as instructions  151  that load data from external memory or store data to external memory). As part of the parsing instructions  151 , and in addition to determine what operations the instructions  151  command the microprocessor  100  to perform, the instruction decode stage  120  determines the syntax of any addresses in the external memory that the instructions  151  refer to as operands. 
   For example, an instruction that loads data from external memory has a format that refers to the specific location in external memory from which to load the data. The format can include a base address value and an offset address value, which are to be added to compute the effective reference address of the instruction  151 . The base address value can be a constant value or specify a value found in an internal register of the microprocessor  100 . Similarly, the offset address value can be a constant value or specify a value found in an internal register of the microprocessor. 
   Similarly, an instruction that stores data to external memory has a format that refers to the specific location in external memory into which to store the data. The format can similarly include a base address value and an offset address value, which are used to compute the effective reference address of the instruction  151 . 
   The instruction decode stage  120  couples the parts of the instruction  151 , including information about the base address value and the offset address value, to the address computation stage  130 . 
   The address computation stage  130  receives the base address value and the offset address value, and computes the effective reference address of the instruction  151 . 
   The instruction decode stage  120  couples the parts of the instruction  151 , including information about what operations the instructions  151  command the microprocessor  100  to perform, and what the syntax of any addresses the instructions  151  refer to as operands, to the instruction execution stage  140 . The address computation stage  130  couples the effective reference address of the instruction  151 , to the instruction execution stage  140 . 
   The instruction decode stage  120  includes a symbolic load-store bypass element  121 . The bypass element  121  examines the parts of the instruction  151 , including information about what operations the instructions  151  command the microprocessor  100  to perform. If these operations are to load data from external memory, or to store data to external memory, the bypass element  121  further examines the syntax of any addresses  151  refer to as operands. 
   If the operand addresses the instructions  151  refer to include identical base address values and offset address values, the bypass element  121  generates a bypass signal indicating that the instructions  151  refer to the same location in external memory. 
   When the bypass signal is generating, the address computation stage  130 , does not have to compute the actual effective address for the microprocessor  100  to act on the knowledge that the instructions  151  refer to identical locations in external memory. 
   For example, suppose that a first instruction  151  to store data refers to a location in external memory determined as (contents of register A)+(fixed offset value B), and a second instruction  151  to load data refers to the same location in external memory determined as (contents of register A)+(fixed offset value B), where A and B are identical. In this case, the microprocessor  100  can proceed with the knowledge that the first (store) instruction  151  and the second (load instruction)  151  refer to the same location. Since the second (load) instruction  151  is going to read the same data from external memory that the first (store) instruction  151  put there, the microprocessor  100  can proceed by using that data from an internal register, rather than waiting for external memory to complete actual store and load operations. 
   Although the actual first (store) instruction  151  would be physically performed and completed by external memory, the microprocessor  100  can proceed without physically performing the second (load) instruction  151 . Instead, the microprocessor  100  can use the identical data from its internal register, thus removing a relative delay in microprocessor  100  operation. 
   Method of Operation 
     FIG. 2  shows a process flow diagram of a method for operating a system in a pipelined microprocessor for detecting identical locations referenced by different load and store instructions. 
   A method  200  is performed by the microprocessor  100 , including its sequence of pipeline stages. In a preferred embodiment, as many steps of the method  200  are performed concurrently in a pipelined manner. Pipeline operation is known in the art of microprocessor design. 
   At a flow point  210 , microprocessor  100  is coupled to an instruction memory  150 , which includes a plurality of instructions  151 , and is ready to perform those instructions  151 . At least some of those instructions  151  are memory load or store instructions. 
   At a flow point  211 , the microprocessor reads a sequence of instructions  151  from the memory  150  using the instruction fetch stage  110  (and including any associated memory read or write elements in the microprocessor  100 ). 
   At a step  212 , the instruction fetch stage  110  couples the instructions  151  to the instruction decode stage  120 . 
   At a step  213 ( a ), the instruction decode stage  120  parses the instructions  151  to determine whether they are instructions  151  that load data from external memory or store data to external memory. 
   At a step  213 ( b ), the instruction decode stage  120  determines the syntax of any addresses in the external memory that the instructions  151  refer to as operands. 
   At a step  214 , the bypass element  121  examines the parts of the instruction  151 , including information about what operations the instructions  151  command the microprocessor  100  to perform. If these operations are to load data from external memory, or to store data to external memory, the method continues with the step  215 . If these operations are otherwise, the method continues with the step  221 . 
   In a step  215 , a record of the symbolic operands of the store operations to external memory is stored in a table that is indexed by the instruction ID. 
   In a step  216 , each load instruction&#39;s operands are compared against both the store instructions being issued in the ongoing clock cycle and those of all unretired store instructions. By storing the record of these operations for comparison, there is a much higher probability of detecting a useful bypass in subsequent steps where the bypass element  121  further examines the syntax of any addresses the instructions  151  refer to as operands. 
   At a step  217 , the bypass element  121  determines whether the operand addresses that the instructions  151  refer to include identical base address values and offset address values. If so, the bypass element  121  generates a bypass signal indicating that the instructions  151  refer to the same location in external memory. If not, the bypass element  121  does not generate a bypass signal. (In alternative embodiments, the bypass element  121  may generate an inverse bypass signal). If the bypass element  121  generates a bypass signal, the method  200  proceeds with the step  220 . If not, the method  200  proceeds with the step  221 . 
   At a flow point  220 , the bypass signal having been generated, the microprocessor  100  can act on the knowledge that the instructions  151  refer to identical locations in external memory. For example, if a first (store) instruction  151  and a second (load) instruction  151  refer to identical locations in external memory, the microprocessor  100  can proceed by using data to be transferred by those instructions  151  from an internal register. The microprocessor  100  does not have to wait for external memory to complete actual store and load operations. 
   At a step  221 , the instruction decode stage  120  couples the parts of the instruction  151 , including information about the base address value and the offset address value to the address computation stage  130 . 
   At a step  222 , the address computation stage  130  receives the base address value and the offset address value, and computes the effective reference address of the instruction  151 . 
   At a step  223 , the instruction decode stage  120  couples the parts of the instruction  151 , including information about what operations the instructions  151  command the microprocessor  100  to perform, and what the syntax of any address the instructions  151  refer to as operands, to the instruction execution stage  140 . 
   At a step  224 , the address computation stage  130  couples the effective reference address of the instruction  151 , to the instruction execution stage  140 . 
   At a step  225 , the first (store) instruction  151  is physically performed and completed by external memory. 
   At a step  226 ( a ), if the bypass signal was generated, the microprocessor  100  proceeds without physically performing the second (load) instruction  151 . Instead, the microprocessor  100  can use the identical data from it&#39;s internal register, thus removing a relative delay in microprocessor  100  operation. 
   Alternatively, at a step  226 ( b ), if the bypass signal was not generated, or in if an inverse bypass signal was generated, second (load) instruction  151  is physically performed and completed by external memory. 
   Alternative Embodiment 
   Although preferred embodiments are disclosed herein, many variations are possible which remain within the concept, scope and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.