Recovery from Branch Misprediction

Branch Prediction can predict wrong. In that case all work done on the wrong branch has to be undone:

• Speculatively executed instructions have to be flushed -> They are not committed yet
• Speculative state is either in the
  • Merged Register File
  • Reorder Buffer
• Recovery is split in front end recovery and back end recovery

Front end recovery #

(Fetch and Decode I think?)

1. Flushing intermediate buffers
2. Restoring history of the branch predictor
3. Update the program counter

Back end recovery #

1. removing instructions residing in any buffer:
   • Memory disambiguation
   • Issue queue
   • Reorder buffer
2. restore renaming table
3. Physical registers and issue queue entries should be reclaimed

Recovery on ROB / RRF architecture #

• Do not recover as soon as misprediction is detected, but let every instruction up until and including the brach instruction commit.

  -> At this point the RRF represents the state after the brach (which is correct)

  -> ROB is set to point to the RRF for all registers (any intermediate speculative registers are cleared by that)

Recovery on MRF architecture #

• Here the processor does not wait until a misspredicted brach commits.

• Processor keeps a log of the changes of the Register Map Table

• Each write to a logical register will be logged; two options:

  1. Log the phyiscal register assigned to this instruction
  2. Log the physical register assigned to the previous writer

• In case of branch misprediction, traverse the log to revcover the correct state

  • Traversing the log may take a long time
  • Some processors periodically store snapshots of the state to only have to traverse back from the closest checkpoint instead of the whole log

• Register map table has to be corrected as well as wrongfully allocated physical registers