Method and system for promoting traces in an instruction processing circuit

1. A method for promoting a sequence of traces in an instruction processing circuit, each trace of the sequence of traces are retrieved from a plurality of sources in an order determined by a sequencer circuit, the method comprising:

obtaining, from the sequencer circuit, a current trace in the sequence of traces;

determining if the current trace is promotable based on a pre-determined criterion;

adding the current trace to a sequencing buffer and marking the current trace, by storing a first promotion flag thereof in the sequencing buffer, as promoted if the current trace is promotable;

adding the current trace to the sequencing buffer without marking the current trace as promoted if the current trace is not promotable;

obtaining, from the sequencer circuit and in response to adding the current trace to the sequencing buffer, a next trace following the current trace in the sequence of traces according to the order;

determining if the next trace is promotable based on the pre-determined criterion;

adding the next trace to the sequencing buffer without marking the next trace as promoted if both the current trace and the next trace are not promotable;

adding the next trace to the sequencing buffer and marking the next trace, by storing a second promotion flag thereof in the sequencing buffer, as promoted if the next trace is promotable;

adding the next trace to the sequencing buffer and marking the next trace, by storing a third promotion flag thereof in the sequencing buffer, as promoted if the current trace is promotable and the next trace is not promotable;

combining at least the current trace and the next trace from the sequencing buffer to build a multi-block trace in response to marking both the current trace and the next trace as promoted; and

executing the multi-block trace as an atomically executed unit.

2. The method of claim 1 wherein determining if the next trace is promotable based on the pre-determined criterion comprises determining the next trace as not promotable if the next trace is at least one selected from a group consisting of being non-speculatively executed and a single instruction trace.

3. The method of claim 1 , further comprising:

determining a bias of the next trace based on a branching history of the next trace,

wherein the bias corresponds to an number of times a branch instruction in the next trace has been branching to a same target address, and

wherein the pre-determined criterion comprises comparing the bias of the next trace to a promotion threshold.

4. The method of claim 1 , wherein the current trace comprises another multi-block trace.

5. The method of claim 1 , wherein the next trace comprises another multi-block trace.

6. The method of claim 1 , further comprising:

determining a bias of the current trace based on a branching history of the current trace,

wherein the bias corresponds to an number of times a branch instruction in the current trace has been branching to a same target address, and

wherein the pre-determined criterion comprises comparing the bias of the current trace to a promotion threshold.

7. The method of claim 6 , further comprising:

determining the promotion threshold based on efficiency for combining a portion of the sequence of traces for execution, and

wherein the promotion threshold is a dynamically alterable value.

8. A computer readable medium containing program instructions for promoting a sequence of traces in an instruction processing circuit, each trace of the sequence of traces are retrieved from a plurality of sources in an order determined by a sequencer circuit, the instructions when executed by a computer comprising functionality for:

obtaining, from the sequencer circuit, a current trace in the sequence of traces;

determining if the current trace is promotable based on a pre-determined criterion;

adding the current trace to a sequencing buffer and marking the current trace, by storing a first promotion flag thereof in the sequencing buffer, as promoted if the current trace is promotable;

adding the current trace to the sequencing buffer without marking the current trace as promoted if the current trace is not promotable;

obtaining, from the sequencer circuit and in response to adding the current trace to the sequencing buffer, a next trace following the current trace in the sequence of traces according to the order;

determining if the next trace is promotable based on the pre-determined criterion;

adding the next trace to the sequencing buffer without marking the next trace as promoted if both the current trace and the next trace are not promotable;

adding the next trace to the sequencing buffer and marking the next trace, by storing a second promotion flag thereof in the sequencing buffer, as promoted if the next trace is promotable;

adding the next trace to the sequencing buffer and marking the next trace, by storing a third promotion flag thereof in the sequencing buffer, as promoted if the current trace is promotable and the next trace is not promotable;

combining at least the current trace and the next trace from the sequencing buffer to build a multi-block trace in response to marking both the current trace and the next trace as promoted; and

executing the multi-block trace as an atomically executed unit.

9. The computer readable medium of claim 8 wherein determining if the next trace is promotable based on the pre-determined criterion comprises determining the next trace as not promotable if the next trace is at least one selected from a group consisting of being non-speculatively executed and a single instruction trace.

10. The computer readable medium of claim 8 , the instructions when executed by the computer further comprising functionality for:

determining a bias of the next trace based on a branching history of the next trace,

wherein the bias corresponds to an number of times a branch instruction in the next trace has been branching to a same target address, and

wherein the pre-determined criterion comprises comparing the bias of the next trace to a promotion threshold.

11. The computer readable medium of claim 8 , wherein the current trace comprises another multi-block trace.

12. The computer readable medium of claim 8 , wherein the next trace comprises another multi-block trace.

13. The computer readable medium of claim 8 , the instructions when executed by the computer further comprising functionality for:

determining a bias of the current trace based on a branching history of the current trace,

wherein the bias corresponds to an number of times a branch instruction in the current trace has been branching to a same target address, and

wherein the pre-determined criterion comprises comparing the bias of the current trace to a promotion threshold.

14. The computer readable medium of claim 13 , the instructions when executed by the computer further comprising functionality for:

determining the promotion threshold based on efficiency for combining a portion of the sequence of traces for execution, and

wherein the promotion threshold is a dynamically alterable value.

15. A system for promoting a sequence of traces in an instruction processing circuit, the system comprising:

a sequencer circuit configure for:

identifying a current trace in the sequence of traces;

determining if the current trace is promotable based on a pre-determined criterion;

adding the current trace to a sequencer buffer and marking the current trace, by storing a first promotion flag thereof in the sequencing buffer, as promoted if the current trace is promotable;

adding the current trace to the sequencer buffer without marking the current trace as promoted if the current trace is not promotable;

identifying, in response to adding the current trace to the sequencer buffer, a next trace following the current trace in the sequence of traces;

determining if the next trace is promotable based on the pre-determined criterion;

adding the next trace to the sequencer buffer without marking the next trace as promoted if both the current trace and the next trace are not promotable;

adding the next trace to the sequencer buffer and marking the next trace, by storing a second promotion flag thereof in the sequencing buffer, as promoted if the next trace is promotable; and

adding the next trace to the sequencer buffer and marking the next trace, by storing a third promotion flag thereof in the sequencing buffer, as promoted if the current trace is promotable and the next trace is not promotable;

the sequencer buffer operatively coupled to the sequencer circuit and configured for storing the current trace and the next trace;

a multi-block builder circuit operatively coupled to the sequencer buffer and configured to combine at least the current trace and the next trace from the sequencer buffer to build a multi-block trace in response to marking both the current trace and the next trace as promoted; and

an execution unit configured to execute the multi-block trace as an atomically executed unit.

16. The system of claim 15 , the sequencer circuit further configured for:

determining a bias of the next trace based on a branching history of the next trace,

wherein the bias corresponds to an number of times a branch instruction in the next trace has been branching to a same target address, and

wherein the pre-determined criterion comprises comparing the bias of the next trace to a promotion threshold.

17. The system of claim 15 , the sequencer circuit further configured for:

determining a bias of the current trace based on a branching history of the current trace,

wherein the bias corresponds to an number of times a branch instruction in the current trace has been branching to a same target address, and

wherein the pre-determined criterion comprises comparing the bias of the current trace to a promotion threshold.

18. The system of claim 17 , the sequencer circuit further configured for:

determining the promotion threshold based on efficiency for combining a portion of the sequence of traces for execution, and

wherein the promotion threshold is a dynamically alterable value.

19. The system of claim 15 determining if the next trace is promotable based on the pre-determined criterion comprises determining the next trace as not promotable if the next trace is at least one selected from a group consisting of being non-speculatively executed and a single instruction trace.

20. The system of claim 19 , wherein the current trace comprises another multi-block trace.

21. The system of claim 19 , wherein the next trace comprises another multi-block trace.