Processor and method for recovering global history shift register and return address stack thereof by determining a removal range of a branch recovery table

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 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;
• 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, wherein if the pipeline flush is triggered by an exception occurring at an exception stage of the instruction pipeline, the removal range is determined by:
• subtracting a number of the predetermined stage from a number of the exception stage and taking the result as a 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.

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

• a timer, keeping a timing value according to a clock signal of the instruction pipeline;
• 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, wherein each of the records comprises a timestamp, wherein the timestamp is the timing value outputted from the timer when the corresponding branch instruction enters the predetermined stage;
• 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;
• if the pipeline flush is triggered by an exception occurring at an exception stage of the instruction pipeline, the processor subtracts a number of the predetermined stage from a number of the exception stage and takes the result as a distance, and subtracts the distance from a present timing value of the timer and takes the result as a time limit, wherein the removal range comprises all records whose timestamps are greater than the time limit.

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

• a timer, keeping a timing value according to a clock signal of the instruction pipeline;
• 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, wherein each of the records comprises a timestamp, wherein the timestamp is the timing value outputted from the timer when the corresponding branch instruction enters the predetermined stage;
• whenever the processor pops out a first return address from the RAS, the processor pushes the first return address into the backup stack;
• 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;
• if the pipeline flush is triggered by an exception occurring at an exception stage of the instruction pipeline, the processor subtracts a number of the predetermined stage from a number of the exception stage and takes the result as a distance, and subtracts the distance from a present timing value of the timer and takes the result as a time limit, wherein the removal range comprises all records whose timestamps are greater than the time limit.