Run-Time Code Parallelization with Monitoring of Repetitive Instruction Sequences During Branch Mis-Prediction

Abstract

A processor includes an execution pipeline and monitoring circuity. The execution pipeline is configured to execute instructions of program code. The monitoring circuity is configured to monitor the instructions in a segment of a repetitive sequence of the instructions so as to construct a specification of register access by the monitored instructions, to parallelize execution of the repetitive sequence based on the corrected specification, and to terminate monitoring of the instructions and discard the specification in response to detecting a branch mis-prediction in the monitored instructions.

1 . A processor, comprising:
 an execution pipeline, which is configured to execute instructions of program code; and   monitoring circuity, which is configured to monitor the instructions in a segment of a repetitive sequence of the instructions so as to construct a specification of register access by the monitored instructions, to parallelize execution of the repetitive sequence based on the corrected specification, and to terminate monitoring of the instructions and discard the specification in response to detecting a branch mis-prediction in the monitored instructions.   
     
     
         2 . The processor according to  claim 1 , wherein the monitoring circuity is further configured to generate a flow-control trace traversed by the monitored instructions, and to correct the flow-control trace so as to compensate for the branch mis-prediction. 
     
     
         3 . The processor according to  claim 1 , wherein the monitoring circuity is configured to continue monitoring the instructions during parallelized execution. 
     
     
         4 . The processor according to  claim 1 , wherein the monitoring circuity is configured to continue to monitor the instructions and construct the specification after discarding the specification. 
     
     
         5 . The processor according to  claim 1 , wherein the monitoring circuity is configured to generate a flow-control trace of the monitored instructions based on an output of a fetch unit in the execution pipeline. 
     
     
         6 . The processor according to  claim 1 , wherein the monitoring circuity is configured to generate a flow-control trace of the monitored instructions based on an output of a decoding unit in the execution pipeline. 
     
     
         7 . The processor according to  claim 1 , wherein the monitoring circuity is configured to generate a flow-control trace of the monitored instructions based on outputs of both a fetch unit and a decoding unit in the execution pipeline. 
     
     
         8 . The processor according to  claim 1 , wherein the monitoring circuity is configured to record in the specification a location in the sequence of a last write operation to a register, based on an output of a fetch unit in the execution pipeline. 
     
     
         9 . The processor according to  claim 1 , wherein the monitoring circuity is configured to record in the specification a location in the sequence of a last write operation to a register, based on the instructions being executed in the execution pipeline. 
     
     
         10 . The processor according to  claim 1 , wherein the monitoring circuity is configured to record in the specification a location in the sequence of a last write operation to a register, based on the instructions that are committed and are not flushed due to the branch mis-prediction. 
     
     
         11 . The processor according to  claim 1 , wherein the monitoring circuity is configured to collect the register access only after evaluating respective branch conditions of conditional branch instructions of the sequence. 
     
     
         12 . The processor according to  claim 1 , wherein the monitoring circuity is configured to generate a flow-control trace for the monitored instructions, including for a branch instruction that is not known to a branch prediction unit of the processor. 
     
     
         13 . A processor, comprising:
 an execution pipeline, which is configured to execute instructions of program code; and   monitoring circuity, which is configured to monitor the instructions in a segment of a repetitive sequence of the instructions so as to construct a specification of register access by the monitored instructions, to parallelize execution of the repetitive sequence based on the corrected specification, and to retain the specification in the processor only provided that no branch mis-prediction is detected in the monitored instructions.   
     
     
         14 . A method, comprising:
 in a processor that executes instructions of program code, monitoring the instructions in a segment of a repetitive sequence of the instructions so as to construct a specification of register access by the monitored instructions;   parallelizing execution of the repetitive sequence based on the specification; and   in response to detecting a branch mis-prediction in the monitored instructions, terminating monitoring of the instructions and discarding the specification.   
     
     
         15 . The method according to  claim 14 , wherein monitoring the instructions further comprises generating a flow-control trace traversed by the monitored instructions, and comprising correcting the flow-control trace so as to compensate for the branch mis-prediction. 
     
     
         16 . The method according to  claim 14 , and comprising continuing monitoring the instructions during parallelized execution. 
     
     
         17 . The method according to  claim 14 , and comprising continuing to monitor the instructions and construct the specification after discarding the specification. 
     
     
         18 . The method according to  claim 14 , wherein monitoring the instructions comprises generating a flow-control trace of the monitored instructions based on an output of a fetch unit in an execution pipeline of the processor. 
     
     
         19 . The method according to  claim 14 , wherein monitoring the instructions comprises generating a flow-control trace of the monitored instructions based on an output of a decoding unit in an execution pipeline of the processor. 
     
     
         20 . The method according to  claim 14 , wherein monitoring the instructions comprises generating a flow-control trace of the monitored instructions based on outputs of both a fetch unit and a decoding unit in an execution pipeline of the processor. 
     
     
         21 . The method according to  claim 14 , wherein monitoring the instructions comprises recording in the specification a location in the sequence of a last write operation to a register, on an output of a fetch unit in an execution pipeline of the processor. 
     
     
         22 . The method according to  claim 14 , wherein monitoring the instructions comprises recording in the specification a location in the sequence of a last write operation to a register, based on the instructions being executed in an execution pipeline of the processor. 
     
     
         23 . The method according to  claim 14 , wherein monitoring the instructions comprises recording in the specification a location in the sequence of a last write operation to a register, based on the instructions that are committed and are not flushed due to the branch mis-prediction. 
     
     
         24 . The method according to  claim 14 , wherein monitoring the instructions comprises collecting the register access only after evaluating respective branch conditions of conditional branch instructions of the sequence. 
     
     
         25 . The method according to  claim 14 , wherein monitoring the instructions comprises generating a flow-control trace for the monitored instructions, including for a branch instruction that is not known to a branch prediction unit of the processor. 
     
     
         26 . A method, comprising:
 in a processor that executes instructions of program code, monitoring the instructions in a segment of a repetitive sequence of the instructions so as to construct a specification of register access by the monitored instructions;   parallelizing execution of the repetitive sequence based on the specification; and   retaining the specification in the processor only provided that no branch mis-prediction is detected in the monitored instructions.