3
$\begingroup$

There is a branch mispredict and while executing the false code, an interrupt occurs (for example a keyboard interrupt). The EPC (register that holds the return address) now holds the wrong return address (after the interrupt handler has finished, it would return in code that wasn't even meant to be executed). How do CPUs deal with this problem?

$\endgroup$
5
$\begingroup$

All instructions in the processor are executed speculatively and every instruction that is fetched after a mispredict needs to be cancelled without allowing any of its effects to become externally visible. This is done with register renaming and a reorder buffer that commits instruction effects in-order. Instructions from asynchronous interrupt handlers are handled the same way, the main difference (and complexity) being how you refetch them after the mispredict causes them to get cancelled.

Example: you fetch the branch at the address $B$, mispredict its target as $M_0$, and start fetching $M_0, M_1, \cdots, M_n$. At this point the fetch unit realizes that an asynchronous interrupt, starting at address $I_0$, needs to be handled and proceeds to set $M_{n+1}$ as the predicted EPC, and fetch $I_0, I_1, \cdots, I_m$. (Note that we've only set the predicted EPC to $M_{n+1}$, not the "real" (externally visible) EPC.) Now the execution unit finally realizes that the branch at $B$ was mispredicted and that the correct branch target was $T_0$.

At this point we must mark all the instructions $M_0, M_1, \cdots, M_n, I_0, I_1, \cdots, I_m$ as "cancelled." Luckily none of them have been committed because they are all behind $B$ in the reorder buffer. Then the execution unit sends a signal to the fetch unit that the correct instruction after $B$ should have been $T_0$, rather than $M_0$.

At this point the fetch unit must realize that there was an asynchronous interrupt handler that had been fetched but not committed. It could do this, for example, by keeping a counter that is incremented the first time the first instruction of an asynchronous interrupt handler is fetched, and decremented when that instruction retires (is committed). So the fetch unit sets $T_0$ as the predicted EPC, starts fetching from $I_0$ again (a new copy of the instruction at $I_0$, let's call it $I_0'$), and proceeds with $I_1', I_2', \cdots, I_m'$. At some point the branch $B$ reaches the head of the reorder buffer and commits. That means that it records $T_0$ as the correct (externally visible) "next instruction pc".

$B$ is followed in the reorder buffer by a bunch of cancelled instructions, $M_0, M_1, \cdots, M_n, I_0, I_1, \cdots, I_m$, these are not committed, but any resources (e.g., physcial registers) allocated to them need to be returned to the free-register queue. Finally $I_0'$ reaches the head of the reorder buffer. It commits. As part of committing the externally visible "next instruction pc" is copied into the real (externally visible) EPC register.

TL;DR

Register renaming and the reorder buffer make handling mispredicted branches much easier.

$\endgroup$
  • $\begingroup$ Thanks for the answer! Do you have any sources on this? $\endgroup$ – model world Feb 7 '15 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.