How much overhead does this process add?
The process is nowhere near as bad as you made it out to be, more on that next, but there is a more general misconception that I think underlies this question: it presumes that "taking time" while processing an instruction adds overall overhead. That is mostly not the case, as making a pipeline longer affects primarily branch mispredictions (and other restarts) but not the throughput under normal conditions, and usually not even the latency of individual instructions (unless it's a specific part of the pipeline that got longer). Making the pipeline longer is not free, but the cost shows up only in limited circumstances, not everywhere all the time.
But to perform the algorithm I described, you basically have to do register allocation in the CPU, right?
Yes, but since this happens as the code is running we have some advantages. For example, we do not need to come up with register names that would be valid statically. We're not statically rewriting the code. It's more like this:
- Decode an instruction.
- For every source operand, replace it with the newest physical register corresponding to that ISA-level register.
- Allocate a physical register the destination operand, update the rename map accordingly.
There is no analysis of arbitrary blocks of code as a whole, it's nothing like what a compiler does, renaming is local, perhaps myopic.. But that's not a limitation, it's actually better that way: this allows a destination to be renamed differently across different iterations of a loop, enabling parallelism across the iterations of the loop. Renaming multiple instructions at once involves something that you might call analysis of the code, but only of a limited number instructions (eg 4, or however wide the renamer is) and only in a local context to "chain" the new name of a destination into the operands of the next instructions that are renamed within the same cycle.
Allocating a register is not a super heavy operation, the "free list" might be represented as a bitvector of available physical registers (with one pulled out using a priority decoder) or as a circular array (small RAM and two indices), either way it's not that big of a deal. Back in university I went with the bitvector approach, it seems that RISCV-BOOM does as well, such low level details are fairly scarce though.
Freeing physical registers can in the simplest case be done based on this principle: when the destination of an instruction is renamed, also record with it the previous name of the destination register. When this instruction retires, that previous name can be freed, since it corresponds to a register that no newer instruction can read (all newer instructions would read the new name). Back in university, that is the technique I used, and it seems that BOOM does too.
In practice there are several reasons why more complicated techniques are used. The register reclamation algorithm that I sketched is extremely conservative (there are more aggressive techniques), and does not work if multiple ISA-level registers can be renamed to the same physical register (which happens as a result of move-elimination aka zero-latency copying, and as a result of memory bypassing). You can read about some more advanced techniques in eg "Cost Effective Physical Register Sharing".
I'm not sure how reasonable it is to compare a modern pipeline with a hypothetical variant of that pipeline sans renaming (since that invalidates the design), but if I do it anyway, it may add a couple of stages:
- Maybe a front-end stage specifically for Rename, but it depends. There should be some tendency towards extra front-end stages on average, since it adds logic, but whether that results in an extra stage depends on the specifics of the design. It may be possible to spread the renaming logic over stages that were already present (decode, enqueue-to-backend).
- Maybe an extra back-end stage to read from an increasingly large physical register file. The bigger it is, the longer that will take. In the classic RISC pipeline there was no separate "register read" stage, but at least one separate stage for that is present in many modern pipelines. Note that even here, adding an extra pipeline stage is still not free but it also does not make instructions slower as such. The extra steps between the reservation station(s) and the actual execution units means that the "wakeup" logic has to(if we want dependent instructions to be able to execute back-to-back, and I do, because lacking that ability would actually add overhead to many instructions) wake up (make available for select/issue) instructions some cycles before its operands are available (in contrast with the classic Tomasulo algorithm where we wait until the operands have been broadcasted over the result bus), which is less bad than it looks since most instructions have a known fixed latency (so we can predict when their result will be available), but certainly an extra source of complications.
So to recap:
How much overhead does this process add?
I still don't know exactly how to answer that, but it's not as bad you probably thought.
