Making sure the Branch Target Buffer stays accurate

Question

As i've been told , a Branch Target Buffer (BTB) acts a lot like a cache for Branches , keeping a map of where branches are in the address space.

If implemented well , it should allow the processor to detect branches before even decoding them , redirecting the PC to the presumed target ( with the help of the branch predictor proper).

But the BTB is presumed to be accurate about where the branches are. You don't want the processor to jump when encountering an ADD instruction for example , meaning the instruction PC has to be an exact match with what is in the BTB.

Here's my question :

Most Processors support self modifying code (for better or for worse). This means that a branch instruction in main memory has the potential to be overwritten by data or another instruction. If said branch is already present in the BTB , this could result in BTB information being stale. In such a case , the processor might jump in response to a non-existent branch , resulting in an incorrect program result.

My initial solution to this was to just compare every memory write against what is present in the BTB. But this would be inefficient (requiring additional ports and potentially slowing down the machine) and most memory writes to not overwrite branch instructions or instructions at all for that matter.

Is there a better way to do this? something i've missed ?

I've looked around already , but couldn't find any information .

Answer 1

The BTB is not really presumed to be accurate. It cannot be accurate. Even putting SMC aside, indirect and other variable-target jumps cannot have their target predicted perfectly. That is not a correctness problem though, the control flow instructions can be executed and at that point it becomes possible to verify the actual target and do the usual front-end-redirect and pipeline flush if the target does not match.

But that does not solve the SMC problem in general. If you need to make SMC work as if the processor is strictly serial, some extra checks are necessary. The checks can be quite conservative and still perform well when SMC isn't happening, which is usually the main case. For example, you can check whether a write is to a code page, and insert an appropriate flush (after the write) if it does. Of course such a coarse test is easily fooled by just marking a data page executable, even if it is never jumped into, needlessly degrading performance. An other strategy might be to check, at retirement of any instruction, whether its page is marked dirty (this makes SMC have a "long shadow", any modification "ruins" a code page until its dirty bit is reset). More precise mechanisms are possible.