System and method for extracting instruction boundaries in a fetched cacheline, given an arbitrary offset within the cacheline
A system and method are presented for pre-decoding (i.e., determining the address boundaries of) variable-length instructions within an instruction block fetched from memory. The instruction block represents the contents of consecutive addresses in memory, and is fetched in response to a microprocessor request for a specific instruction within the block. After pre-decoding, the instructions present in the block are placed into a cache for execution by the microprocessor. Conventional instruction pre-decoding methods apply only to instructions fetched from addresses at or beyond the address of the requested instruction. The remaining instructions in the block are therefore not utilized. The system and method disclosed herein permit backward pre-decoding of the instruction block, in which the address boundaries of instructions fetched from addresses prior to that of the requested instruction may also be determined. This capability results in more efficient use of the cache.
1. A system containing an N-word sequence of single-word and double-word instructions and an instruction decoder, wherein the double-word instructions comprise a marker bit pattern, and wherein the instruction decoder comprises logic for implementing a binary decision tree having a set of nodes arranged from a top-most node to a bottom-most node representing successively preceding memory address locations relative to an address location requested by a microprocessor, and wherein the logic is configured by the binary decision tree to determine if an instruction corresponding to an address location immediately preceding the address location requested by the microprocessor is a single-word instruction or a double-word instruction depending on whether tests performed on at least two nodes lower than the top-most node determines that the instructions corresponding to at least two successively preceding memory address locations contain the marker bit pattern.
2. The system as recited in claim 1 , wherein the instruction decoder is contained within the microprocessor and such that a unique combination of single-word and double-word instructions in the N-word sequence is executable by the microprocessor.
3. The system as recited in claim 1 , further comprising a memory and a cache, wherein the N-word instruction sequence is transferred from the memory to the cache in response to the microprocessor requesting a specific single-word or double-word instruction present within the N-word sequence.
4. The system as recited in claim 1 , wherein each word in the N-word sequence corresponds to one of a series of N consecutive memory addresses.
5. The system as recited in claim 1 , wherein the instruction decoder is further adapted to identify the corresponding address of at least one single-word or double-word instruction within each unique combination of single-word and double-word instructions in the N-word sequence.
6. The system as recited in claim 1 , wherein the instruction decoder is further adapted to identify the corresponding address of at least one single-word or double-word instruction within a unique combination of single-word and double-word instructions having addresses prior to that of the instruction requested by the microprocessor.
7. The system as recited in claim 2 , wherein the microprocessor further comprises a pipeline, into which single-word and double-word instructions from the N-word sequence pass in order to be executed by the microprocessor.
8. The system as recited in claim 1 , wherein the marker bit pattern is part of the op code of each double-word instruction.
9. The system as recited in claim 1 , wherein the instruction decoder is implemented using standard logic cells, and shares a common semiconductor substrate with the microprocessor within an integrated circuit.
10. A method for parsing a sequence of N words into a unique combination of single-word and double-word instructions, comprising:
detecting occurrences of a marker bit pattern present in the op code of each of the double-word instructions and absent from any of the single-word instructions;
creating a binary decision tree to associate with every possible N-word combination of single-word and double-word instructions a corresponding marker bit pattern; and
employing the binary decision tree to determine whether an instruction at a top node of the tree corresponding to a first preceding address location immediately preceding an address location requested by a microprocessor is a single-word or double-word instruction depending on whether at least two instructions below the top node of the tree corresponding to successive address locations immediately preceding the first preceding address location contains the marker bit pattern.
11. The method as recited in claim 10 , further comprising employing an instruction decoder within the microprocessor to parse the sequence of N words into a unique combination of single-word and double-word instructions, wherein the microprocessor is adapted to execute said single-word and double-word instructions.
12. The method as recited in claim 11 , further comprising transferring the sequence of N words from a memory to a cache in response to the microprocessor requesting a specific single-word or double-word instruction present within the sequence of N words.
13. The method as recited in claim 12 , wherein each word in the sequence of N words corresponds to one of N consecutive memory addresses.
14. The method as recited in claim 13 , further comprising identifying the corresponding address of at least one single-word or double-word instruction within each unique combination of single-word and double-word instructions present within the sequence of N words.
15. The method as recited in claim 14 , further comprising identifying the corresponding address of at least one single-word or double-word instruction within a unique combination of single-word and double-word instructions present within the sequence of N words and having addresses prior to that of the instruction requested by the microprocessor.
16. The method as recited in claim 14 , further comprising, after parsing the sequence of N words into a unique combination of single-word and double-word instructions, placing said single-word and double-word instructions into a pipeline in order to be executed by the microprocessor.
17. The method as recited in claim 10 , further comprising including the marker bit pattern within the op code of all double-word instructions and omitting it from all single-word instructions.
18. The method as recited in claim 10 , further comprising implementing the binary decision tree and marker bit pattern detection using standard logic within the microprocessor.
19. The method as recited in claim 10 , further comprising determining whether an instruction at a first node immediately beneath the top node of the tree corresponding to a second preceding address location immediately preceding the first preceding address is a single-word or double-word instruction depending on whether at least two instructions below the first node of the tree corresponding to successive address locations immediately preceding the second preceding address location contains the marker bit pattern.
20. A memory medium, comprising:
an N-word sequence of single-word and double-word instructions, wherein the op-code of the double-word instructions contain a marker bit pattern;
a binary decision tree, representing every possible combination of occurrences of the marker bit pattern for the N-word sequence, and identifying each combination associated with a unique sequence of single-word and double-word instructions; and
means for consulting the binary decision tree to determine whether an instruction at a top node of the tree corresponding to a first preceding address location immediately preceding an address location requested by a microprocessor is a single-word or double word instruction depending on whether at least two instructions below the top node of the tree corresponding to successive address locations immediately preceding the first preceding address location contains the marker bit pattern.
21. The memory medium as recited in claim 20 , wherein the N-word sequence of single-word and double-word instructions is contained within a memory coupled to a microprocessor and the binary decision tree is implemented by logic elements within the microprocessor, and wherein the microprocessor and memory occupy a monolithic substrate.
22. The memory medium as recited in claim 20 , further comprising consulting the binary decision tree to determine whether an instruction at a first node immediately beneath the top node of the tree corresponding to a second preceding address location immediately preceding the first preceding address is a single-word or double-word instruction depending on whether at least two instructions below the first node of the tree corresponding to successive address locations immediately preceding the second preceding address location contains the marker bit pattern.