Universal branch identifier for invalidation of speculative instructions
View Patent ↗A system for speculative branch predictions. An embodiment of the system includes branch prediction logic, fetch logic, and branch identification logic. The branch prediction logic is configured to predict a branch path for a branch in an instruction stream. The fetch logic is coupled to the branch prediction logic. The fetch logic is configured to speculatively fetch an instruction corresponding to the predicted branch path. The branch identification logic is coupled to the branch prediction logic and the fetch logic. The branch identification logic is configured to mark the speculatively fetched instruction with a branch identifier using a universal branch identification format. The universal branch identification format includes a bit value at a bit position corresponding to the predicted branch path.
1. A system for speculative branch predictions, the system comprising:
branch prediction logic to predict a branch path for a branch in an instruction stream;
fetch logic coupled to the branch prediction logic, the fetch logic to speculatively fetch an instruction corresponding to the predicted branch path;
branch identification logic coupled to the branch prediction logic and the fetch logic, the branch identification logic to mark the speculatively fetched instruction with a branch identifier using a universal branch identification format, the universal branch identification format comprising a bit value at a bit position corresponding to the predicted branch path;
branch invalidation logic coupled to the branch identification logic, the branch invalidation logic to invalidate the speculatively fetched instruction in response to an invalidation command comprising the bit value at the bit position corresponding to the predicted branch path, the invalidation command comprising a thread identifier to designate a thread of a multi-threaded process, the designated thread corresponding to the predicted branch path; and a computer readable storage medium comprising a hardware storage device for holding the speculatively fetched instruction.
2. The system according to claim 1 , the branch invalidation logic coupled to an execution unit comprising comparison logic, the comparison logic to compare the invalidation command to a plurality of branch identifiers associated with a plurality of in-flight instructions to determine whether to invalidate any of the plurality of in-flight instructions.
3. The system according to claim 1 , the invalidation command further comprising a format of (pos, val), where pos designates the bit position corresponding to the predicted branch path, and val designates the bit value corresponding to the predicted branch path.
4. The system according to claim 1 , the invalidation command associated with an occurrence of a mispredicted branch.
5. The system according to claim 1 , the universal branch identification format further comprising a second bit value at a second bit position corresponding to a predicted parent branch path of a parent branch in the instruction stream.
6. The system according to claim 1 , further comprising a branch checkpoint register, the branch checkpoint register comprising a plurality of entries corresponding to a plurality of bit positions, including the bit position corresponding to the predicted branch path.
7. The system according to claim 1 , the branch identification logic further configured to randomly assign the bit position to the predicted branch path.
8. The system according to claim 1 , the branch identification logic further configured to implement a first find assignment routine to assign the bit position to the predicted branch path.
9. The system according to claim 1 , the universal branch identification format comprising n bit positions, including the bit position corresponding to the predicted branch path, where n designates a limit of fetched, unresolved brandies in the instruction stream.
10. The system according to claim 9 , the n bit positions partitioned into groups, each group corresponding to a unique thread.
11. The system according to claim 1 , the universal branch identification format comprising n bit positions, including the bit position corresponding to the predicted branch path, where 2n designates a limit of identifiable branch paths.
12. The system according to claim 11 , the branch identification logic further configured to assign a second bit value to designate a second predicted branch path, the second bit value at the same bit position corresponding to the predicted branch path.
13. The system according to claim 12 , the branch identification logic further configured to invert the bit value to assign the second bit value at the same position for the second predicted branch path.
14. A method for speculative branch predictions executable with a computer processor, the method comprising:
predicting a branch path for a branch in an instruction stream;
fetching an instruction corresponding to the predicted branch path;
using the processor to mark the speculatively fetched instruction with a branch identifier using a universal branch identification format, the universal branch identification format comprising a bit value at a bit position corresponding to the predicted branch path; and
invalidating the speculatively fetched instruction in response to an occurrence of an exception.
15. The method according to claim 14 , further comprising invalidating the speculatively fetched instruction in response to an invalidation command comprising the bit value at the bit position corresponding to the predicted branch path.
16. The method according to claim 15 , further comprising comparing the invalidation command to a plurality of branch identifiers associated with a plurality of in-flight instructions to determine whether to invalidate any of the plurality of in-flight instructions.
17. The method according to claim 15 , further comprising invalidating the speculatively fetched instruction in response to an occurrence of a mispredicted branch.
18. The method according to claim 14 , the universal branch identification format comprising a plurality of bit positions, including the bit position corresponding to the predicted branch path, each of the plurality of bit positions corresponding to at least one of a plurality of predicted branch paths of the instruction stream.
19. The method according to claim 18 , further comprising storing an instruction identification table comprising a plurality of speculatively fetched instructions and a corresponding plurality of branch identifiers.
20. A computer readable storage medium embodying a program of machine-readable instructions, executable by a digital processor, to perform operations to facilitate speculative instruction invalidation, the operations comprising:
fetch an instruction corresponding to a predicted branch path in an instruction stream;
mark the speculatively fetched instruction with a branch identifier using a universal branch identification format, the universal branch identification format comprising a bit value at a bit position corresponding to the predicted branch path;
invalidate the speculatively fetched instruction in response to an invalidation command comprising the bit value at the bit position corresponding to the predicted branch path; and
invalidate the speculatively fetched instruction in response to an occurrence of an exception.
21. The computer readable storage medium according to claim 20 , the operations further comprising an operation to compare the invalidation command to a plurality of branch identifiers associated with a plurality of in-flight instructions to determine whether to invalidate any of the plurality of in-flight instructions.
22. The computer readable storage medium according to claim 20 , the operations further comprising an operation to generate the invalidation command in response to an occurrence of a mispredicted branch.
23. The computer readable storage medium according to claim 20 , the operations further comprising an operation to generate the invalidation command in response to the occurrence of the exception.
24. The computer readable storage medium according to claim 20 , the operations further comprising an operation to store an instruction identification table comprising a plurality of speculatively fetched instructions and a corresponding plurality of branch identifiers.
25. A system for speculative branch predictions, the system comprising:
branch prediction logic to predict a branch path for a branch in an instruction stream;
fetch logic coupled to the branch prediction logic, the fetch logic to speculatively fetch an instruction corresponding to the predicted branch path;
branch identification logic coupled to the branch prediction logic and the fetch logic, the branch identification logic to mark the speculatively fetched instruction with a branch identifier using a universal branch identification format, the universal branch identification format comprising a bit value at a bit position corresponding to the predicted branch path;
branch invalidation logic coupled to the branch identification logic, the branch invalidation logic to invalidate the speculatively fetched instruction in response to an invalidation command comprising the bit value at the bit position corresponding to the predicted branch path, the invalidation command associated with an occurrence of an exception, the invalidated speculatively fetched instruction subsequent to an instruction associated with the occurrence of the exception; and a computer readable storage medium comprising a hardware storage device for holding the speculatively fetched instruction.
26. The system according to claim 25 , the universal branch identification format further comprising a second bit value at a second bit position corresponding to a predicted parent branch path of a parent branch in the instruction stream.
27. The system according to claim 25 , further comprising a branch checkpoint register, the branch checkpoint register comprising a plurality of entries corresponding to a plurality of bit positions, including the bit position corresponding to the predicted branch path.
28. The system according to claim 25 , the branch identification logic further configured to randomly assign the bit position to the predicted branch path.
29. The system according to claim 25 , the branch identification logic further configured to implement a first find assignment routine to assign the bit position to the predicted branch path.
30. The computer readable storage medium according to claim 20 , the universal branch identification format further comprising a second bit value at a second bit position corresponding to a predicted parent branch path of a parent branch in the instruction stream.
31. The computer readable storage medium according to claim 20 , wherein the machine-readable instructions are operable such that a branch checkpoint register comprises a plurality of entries corresponding to a plurality of bit positions, including the bit position corresponding to the predicted branch path.
32. The computer readable storage medium according to claim 20 , wherein the machine-readable instructions are operable such that the bit position is randomly assigned to the predicted branch path.
33. The computer readable storage medium according to claim 20 , wherein the machine-readable instructions are operable such that a first find assignment routine is implemented to assign the bit position to the predicted branch path.