Predicting a sequence of variable instruction lengths from previously identified length pattern indexed by an instruction fetch address

• US 6,125,441 A
• Filed: 12/18/1997
• Issued: 09/26/2000
• Est. Priority Date: 12/18/1997
• Status: Expired due to Term

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Green, Thomas S.
• Primary Examiner(s): Kim, Kenneth S.
• Application Number:
  US08/992,803
• Time in Patent Office: 1,013 Days
• Field of Search: 712/210, 712/213, 712/215, 712/204
• US Class Current: 712/210
• CPC Class Codes: G06F 9/30152 Determining start or end of instruction; determining instruction length
• CPC Class Codes: G06F 9/3816 Instruction alignment, e.g. cache line crossing
• CPC Class Codes: G06F 9/382 Pipelined decoding, e.g. using predecoding

Abstract

An instruction cache having a pattern detector for use in predicting the length of variable length instructions in a microprocessor. The instruction cache comprises an instruction length calculation unit and the pattern detector. The pattern detector is configured with a content addressable memory and update logic. The content addressable memory stores fetch addresses and instruction lengths calculated by the calculation unit. The content addressable memory compares particular fetch addresses that it receives with fetch addresses already stored and outputs corresponding predicted instruction length sequences. The content addressable memory may receive, compare, and store instruction lengths or instruction bytes in addition to, or in lieu of, fetch addresses. A neural network or other type of memory configuration may be used in place of the content addressable memory.

Claims

1. A microprocessor configured to execute variable length instructions comprising:

a cache array configured to receive a fetch address and in response output a corresponding plurality of instruction bytes;

an instruction length calculation unit coupled to said cache array and configured to receive said plurality of instruction bytes, wherein said calculation unit is configured to generate a particular instruction length corresponding to a particular instruction within said plurality of instruction bytes; and

a pattern detector coupled to said cache array and said calculation unit, wherein said pattern detector is configured to store a plurality of fetch addresses and a plurality of instruction length sequences, wherein each stored sequence corresponds to a particular stored fetch address, wherein said pattern decoder is configured to output a particular predicted instruction length sequence useable to align instructions for decoding in response to matching a newly received fetch address with a particular fetch address stored in the pattern detector.

2. The microprocessor as recited in claim 1 wherein said cache array is configured to store a number of start and end bits, and wherein said calculation unit is configured to receive said start and end bits and use said start and end bits to generate said particular instruction length.

3. The microprocessor as recited in claim 1 wherein said particular instruction length sequence is verified by an instruction alignment unit coupled to said pattern decoder and an instruction scanning unit.

4. The microprocessor as recited in claim 1 wherein said pattern detector and said calculation unit are part of an instruction cache.

5. The microprocessor as recited in claim 1 wherein said pattern detector is configured to clear stored instruction lengths upon receiving an instruction length misprediction signal.

6. The microprocessor as recited in claim 1 wherein said pattern detector is configured to clear only the mispredicted instruction length sequence upon receiving an instruction length misprediction signal.

7. The microprocessor as recited in claim 1 wherein said pattern detector is configured to store a new fetch address by overwriting the oldest stored fetch address if said pattern detector is full.

8. The microprocessor as recited in claim 1 wherein said pattern detector is configured to store a new fetch address over the stored fetch address having the oldest last access.

9. The superscalar microprocessor as recited in claim 1 wherein said pattern detector is configured as a content addressable memory.

10. The superscalar microprocessor as recited in claim 1 wherein said pattern detector is configured as a neural network.

11. The superscalar microprocessor as recited in claim 1 wherein said pattern detector is configured to receive and store instruction bytes.

12. The superscalar microprocessor as recited in claim 1 further comprising an opcode scan unit coupled to said cache array and said pattern detector, wherein said opcode scan unit is configured to receive and scan a plurality of instruction bytes corresponding to a particular fetch address.

13. The superscalar microprocessor as recited in claim 12 wherein said opcode scan unit is configured to prevent fetch addresses associated with instruction bytes having values indicative of conditional branch instructions from being stored in said pattern detector.

14. The superscalar microprocessor as recited in claim 1 wherein said pattern detector is configured to receive a conditional branch signal from a decode unit.

15. The superscalar microprocessor as recited in claim 14 wherein said pattern detector is configured to clear a particular stored fetch address in response to receiving said conditional branch signal.

16. A method for predicting instruction lengths for variable length instructions comprising:

reading a plurality of instruction bytes from a cache using fetch addresses;

generating instruction lengths for instructions within said pluralities of instruction bytes;

storing said fetch addresses and said instruction lengths;

comparing a particular fetch address with said stored fetch addresses;

generating a plurality of predicted instruction lengths by selecting stored instruction lengths corresponding to said particular fetch address; and

verifying said plurality of predicted instruction lengths.

17. The method as recited in claim 16 further comprising clearing a stored instruction length that corresponds to a fetch address that generated an instruction length misprediction.

18. The method as recited in claim 16 further comprising storing a plurality of instruction bytes.

19. The method as recited in claim 18 wherein said comparing further comprises comparing a particular set of instruction bytes with said plurality of stored instruction bytes.