Method and apparatus for flushing instructions from reservation stations

Abstract

A processor may include a reorder buffer, reservation stations, and execution units. The reorder buffer may be a circular buffer with a head pointer and a tail pointer, configured to assign indexes to instructions. Reservation stations may be configured to host instructions with the assigned indexes, while waiting to be issued to the execution units. Responsive to exception event, reservation stations may be configured to flush instructions that are younger, in program order, than the instruction executed with exception. Execution units may provide the reorder buffer index EX of the instruction executed with exception. The reorder buffer may provide the reorder buffer index TP stored in the tail pointer. Reservation stations may be configured to flush instructions with assigned indexes in the wrapped-around increasing interval from the index EX to the index TP.

I claim: 
     
         1 . A method comprising:
 allocating entries of a circular buffer, wherein each circular buffer entry is identified with an index from an interval of consecutive integers;   maintaining a pointer, wherein the pointer may point to a not allocated circular buffer entry, or to a circular buffer entry allocated before other allocated circular buffer entries, or to a circular buffer entry allocated after other allocated circular buffer entries;   comparing a first index of a first allocated circular buffer entry with a second index of a second allocated circular buffer entry;   comparing the pointer with the first index;   comparing the pointer with the second index;   if the first index is smaller than the second index and the pointer is smaller than or equal to both the first index and the second index, or the first index is smaller than the second index and the pointer is larger than or equal to both the first index and the second index, or the first index is larger than the second index and the pointer is smaller than or equal to the first index and the pointer is larger than or equal to the second index
 determining that the first allocated entry was allocated before the second allocated entry, 
   otherwise
 determining that the second allocated entry was allocated before the first allocated entry. 
   
     
     
         2 . The method in  claim 1 , further comprising
 maintaining a table with plurality of table entries, wherein each table entry comprises an index field configured to store an index of an allocated circular buffer entry.   
     
     
         3 . The method in  claim 2 , further comprising
 storing the second index of the second allocated circular buffer entry in an index field of a second table entry.   
     
     
         4 . The method in  claim 3 , further comprising
 flushing the second table entry in response to determining that the first allocated circular buffer entry was allocated before the second allocated circular buffer entry.   
     
     
         5 . The method in  claim 4 , wherein the circular buffer stores not committed instructions in a processor. 
     
     
         6 . The method in  claim 5 , wherein the table stores not executed instructions in the processor. 
     
     
         7 . The method in  claim 6 , wherein the first allocated circular buffer entry corresponds to an instruction executed with exception. 
     
     
         8 . An apparatus comprising
 a circular buffer comprising plurality of entries, wherein each circular buffer entry is identified with an index from an interval of consecutive integers;   a pointer configured to store an index of a not allocated circular buffer entry, or an index of a circular buffer entry allocated before other allocated circular buffer entries, or an index of a circular buffer entry allocated after other allocated circular buffer entries;   a circuitry configured to
 compare a first index of a first circular allocated buffer entry with a second index of a second allocated circular buffer entry; 
 compare the first index with the pointer; 
 compare the second index with the pointer; 
 if the first index is smaller than the second index and the pointer is smaller than or equal to both the first index and the second index, or the first index is smaller than the second index and the pointer is larger than or equal to both the first index and the second index, or the first index is larger than the second index and the pointer is smaller than or equal to the first index and the pointer is larger than or equal to the second index
 assert a signal to indicate that the first allocated circular buffer entry was allocated before the second allocated circular buffer entry 
 
 otherwise,
 deassert the signal to indicate that the second allocated circular buffer entry was allocated before the first allocated circular buffer entry. 
 
   
     
     
         9 . The apparatus in  claim 8 , further comprising
 a table with plurality of table entries, wherein each table entry comprises an index field configured to store an index of an allocated circular buffer entry.   
     
     
         10 . The apparatus in  claim 9 , wherein the second index of the second allocated circular buffer entry is stored in an index field of a second table entry. 
     
     
         11 . The apparatus in  claim 10 , wherein the circuitry is further configured to flush the second table entry in response to determining that the signal is asserted. 
     
     
         12 . The method in  claim 11 , wherein the circular buffer stores not committed instructions in a processor. 
     
     
         13 . The method in  claim 12 , wherein the table stores not executed instructions in the processor. 
     
     
         14 . The method in  claim 13 , wherein the first allocated circular buffer entry corresponds to an instruction executed with exception.