PROCESSOR AND METHOD FOR RECOVERING GLOBAL HISTORY SHIFT REGISTER AND RETURN ADDRESS STACK THEREOF

• US 20100161951A1
• Filed: 12/18/2008
• Published: 06/24/2010
• Est. Priority Date: 12/18/2008
• Status: Active Grant

• Current Assignee: Faraday Technology Corp.
• Original Assignee: Faraday Technology Corp.
• Inventors: Chou, Tzu-Min, Yang, Hui-Chin, Chung, Chung-Ping, Chang, Shun-Chieh, Kuo, Yuan-Jung, Chiou, Guan-Ying
• Granted Patent: US 8,078,851 B2
• Time in Patent Office: Days
• US Class Current: 712/240
• CPC Class Codes: G06F 9/30054 Unconditional branch instructions
• CPC Class Codes: G06F 9/323 for indirect branch instructions
• CPC Class Codes: G06F 9/3806 using address prediction, e.g. return stack, branch history buffer
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

A method for recovering global history shift register (GHSR) and return address stack (RAS) is provided, which is applicable to an instruction pipeline of a processor and includes the following steps. First, provide a branch recovery table (BRT) and a backup stack. Whenever a branch instruction enters a predetermined stage of the instruction pipeline, add a record in the BRT according to the branch instruction. Whenever a return address is popped from the RAS of the instruction pipeline, push the return address into the backup stack. When flushing the instruction pipeline, determine a removal range of the BRT according to the condition which triggers the pipeline flush. Recover the RAS according to the records in the removal range and the backup stack. Remove all records in the removal range. Recover the GHSR of the instruction pipeline according to the removed records.

Claims

1. A method for recovering a global history shift register (GHSR) of an instruction pipeline of a processor, the method comprising:

providing a branch recovery table (BRT);

adding a record to the BRT according to each of a plurality of branch instructions when said branch instruction enters a predetermined stage of the instruction pipeline;

determining a removal range of the BRT according to a condition which triggers a pipeline flush of the instruction pipeline;

removing all records in the removal range; and

recovering the GHSR of the instruction pipeline according to the removed records.

2. The method according to claim 1, further comprising:

removing an oldest record in the BRT when a target address of one of the branch instructions is confirmed.

3. The method according to claim 1, wherein if the pipeline flush is triggered by a prediction error of one of the branch instructions, the removal range comprises all records of the BRT.

4. The method according to claim 1, wherein if the pipeline flush is triggered by an exception occurring at an exception stage of the instruction pipeline, the removal range is determined according to a distance between the predetermined stage and the exception stage.

5. The method according to claim 1, wherein the step of recovering the GHSR comprises:

counting a quantity of the records in the removal range;

shifting back the GHSR for a number of bits, wherein the number of the bits is equal to the quantity of the records; and

when the pipeline flush is triggered by a prediction error of one of the branch instructions, inserting a correct branch direction of the branch instruction into the GHSR.

6. The method according to claim 1, wherein a length of the GHSR is longer than a length of the instruction pipeline, and is also longer than a bit number required by the instruction pipeline for branch prediction.

7. A method for recovering a return address stack (RAS) of an instruction pipeline of a processor, the method comprising:

providing a branch recovery table (BRT);

adding a record to the BRT according to one of a plurality of branch instructions, when said branch instruction enters a predetermined stage of the instruction pipeline;

providing a backup stack;

pushing a first return address into the backup stack whenever the first return address is popped out from the RAS of the instruction pipeline;

determining a removal range of the BRT according to a condition which triggers a pipeline flush of the instruction pipeline;

recovering the RAS according to the records in the removal range and the backup stack; and

removing all records in the removal range.

8. The method according to claim 7, wherein if the pipeline flush is triggered by a prediction error of one of the branch instructions, the removal range comprises all records of the BRT.

9. The method according to claim 7, wherein if the pipeline flush is triggered by an exception occurring at an exception stage of the instruction pipeline, the removal range is determined according to a distance between the predetermined stage and the exception stage.

10. The method according to claim 9, further comprising:

providing a timer for keeping a timing value according to a clock signal of the instruction pipeline, wherein each of the records comprises a timestamp and the timestamp is the timing value outputted from the timer when the corresponding branch instruction enters the predetermined stage.

11. The method according to claim 10, wherein the step of determining the removal range according to the distance comprises:

subtracting a number of the predetermined stage from a number of the exception stage and taking the result as the distance; and

subtracting the distance from a present timing value of the timer and taking the result as a time limit, wherein the removal range comprises all records whose timestamps are greater than the time limit.

12. The method according to claim 7, wherein each of the records comprises a type of the corresponding branch instruction, and the method for recovering the RAS further comprises executing the following steps to each record in the removal range:

when the type of the corresponding branch instruction of the record is a call instruction, popping out a second return address from the RAS; and

when the type of the corresponding branch instruction of the record is a return instruction, popping out a third return address from the backup stack and pushing the third return address into the RAS.

13. A processor comprising an instruction pipeline, the instruction pipeline comprising:

a global history shift register (GHSR); and

a storage apparatus, coupled to the GHSR through the instruction pipeline and storing a branch recovery table (BRT), wherein

when each of a plurality of branch instructions enters a predetermined stage of the instruction pipeline, the processor adds a record in the BRT according to said branch instruction; and

when flushing the instruction pipeline, the processor determines a removal range of the BRT according to a condition which triggers the pipeline flush, removes all records in the removal range, and recovers the GHSR according to the removed records.

14. The processor according to claim 13, wherein when a target address of one of the branch instructions is confirmed by the processor, the processor removes an oldest record in the BRT.

15. The processor according to claim 13, wherein if the pipeline flush is triggered by a prediction error of one of the branch instructions, the removal range comprises all records of the BRT.

16. The processor according to claim 13, wherein if the pipeline flush is triggered by an exception occurring at an exception stage of the instruction pipeline, the processor determines the removal range according to a distance between the predetermined stage and the exception stage.

17. The processor according to claim 13, wherein

the processor counts a quantity of the records in the removal range, and shifts back the GHSR for a number of bits, the number of the bits is equal to the quantity of the records;

and

if the pipeline flush is raised by a prediction error of one of the branch instructions, the processor inserts a correct branch direction of the branch instruction into the GHSR.

18. The processor according to claim 13, wherein a length of the GHSR is longer than a length of the instruction pipeline, and is also longer than a bit number required by the instruction pipeline for branch prediction.

19. A processor, comprising an instruction pipeline, the instruction pipeline comprising:

a return address stack (RAS),

a backup stack, and

a storage apparatus, storing a branch recovery table (BRT);

wherein

the RAS, the backup stack, and the storage apparatus are coupled to each other through the instruction pipeline;

when each of a plurality of branch instructions enters a predetermined stage of the instruction pipeline, the processor adds a record in the BRT according to said branch instruction;

whenever the processor pops out a first return address from the RAS, the processor pushes the first return address into the backup stack; and

when flushing the instruction pipeline, the processor determines a removal range of the BRT according to a condition which triggers the pipeline flush, recovers the RAS according to the records in the removal range and the backup stack, and removes all records in the removal range.

20. The processor according to claim 19, wherein if the pipeline flush is triggered by a prediction error of one of the branch instructions, the removal range comprises all records of the BRT.

21. The processor according to claim 19, wherein if the pipeline flush is triggered by an exception occurring at an exception stage of the instruction pipeline, the processor determines the removal range according to a distance between the predetermined stage and the exception stage.

22. The processor according to claim 21, wherein the instruction pipeline further comprises a timer for keeping a timing value according to a clock signal of the instruction pipeline, each of the records comprises a timestamp, the timestamp is the timing value outputted from the timer when the corresponding branch instruction enters the predetermined stage.

23. The processor according to claim 22, wherein the processor subtracts a number of the predetermined stage from a number of the exception stage and takes the result as the distance, and subtracts the distance from a present timing value of the timer and takes the result as a time limit, the removal range comprises all records whose timestamps are greater than the time limit.

24. The processor according to claim 19, wherein each of the records comprises a type of the corresponding branch instruction, the processor checks each of the records in the removal range according to a sequence from the newest record to the oldest record;

when the type of the corresponding branch instruction of the record is a call instruction, the processor pops out a second return address from the RAS;

when the type of the corresponding branch instruction of the record is a return instruction, the processor pops out a third return address from the backup stack and pushes the third return address into the RAS.