Prediction
The main task of prediction is to know what code to prefetch in the instruction stream in the face of branches to avoid stalls. The Mill features precise prediction, that knows how much to prefetch from where, usually several branches ahread.
Exit Table
The data structure that enables those unique features is the exit table. It doesn't monitor whether to take each branch or not. I monitors at which branch control flow leaves an EBB. This of course drastically reduces the amount of branches that need to be tracked. And the aggressive Speculation possible on the Mill eliminates even more branches.
For this reason it becomes feasible to carry a lot more information for each exit, which wouldn't be possible for every branch. An exit entry holds:
- an offset to the target EBB entry address
- how many cache lines to load from there
- at which point in the last cache line the next exit is
- what kind of branch it is, a call, a return, an unconditional branch etc.
The exit table must be fast, but it doesn't need 100% coverage. A missing entry just means a stall, the same as a mispredict. It is a cost/benefit trade-off. For this reason the exit table is organized as a hash table of carefully chosen size.
Exit Chains
And this is how the prefetch gets ahead of the instruction stream: From any exit table entry, the address of the next exit can be constructed. This is used to get the next exit and so forth. Until the hardware either doesn't find and entry or comes accross one it already prefetched, which means there is a loop.
