[libre-riscv-dev] [Bug 206] Implement branch prediction

[bugzilla-daemon at libre-riscv.org]

http://bugs.libre-riscv.org/show_bug.cgi?id=206

--- Comment #4 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to Jacob Lifshay from comment #3)
> (In reply to Luke Kenneth Casson Leighton from comment #2)
> > (In reply to Jacob Lifshay from comment #0)
> > 
> > > To avoid spectre-style data leaks where feasible, we should only send
> > > taken/not-taken data back to the branch predictor once all preceding
> > > branches are no longer speculative (tracked by dependency matrix).
> > 
> > that's going to be interesting.  all *preceding* branches.  do they
> > mean branches that are in play whilst *other* branches are still in play?
> > double-shadowing, in other words?
> 
> I meant where there could be a branch or trap before the current branch.
> Once the current branch is known to be executed, only then can it send
> taken/not-taken info back to the branch predictor.

ok, right.  so this is when the shadow on the current branch is still active.
when that shadow is released, the *only* reason it would be dropped is because
the result (direction) is then known.

(shadows switch off - prohibit - dangerous side-effect operations such as
"write to register" and "write to memory" - without preventing the operation
from being *calculated*. thus although execution resources might be wasted by
running them then cancelling them, at least no damage can occur)

> Before then, the branch
> predictor has to assume that the branch was predicted correctly.

ok i _think_ things are a little different (simpler) here, because the shadow
system is easily accessible (a single bit).  if that bit is still active,
there's no need for assumptions: you *know* that the branch prediction has not
been decided yet.


> Basically, it all boils down to the branch predictor can't get information
> from data that was calculated speculatively by the out-of-order engine until
> it's not speculative anymore.

yes.  ok.  and that's when that branch-shadow flag is dropped (with a
corresponding "success or cancel" flag which tells us if the branch was
correctly predicted or if it was wrong).

here's the relevant code:
https://git.libre-riscv.org/?p=soc.git;a=blob;f=src/scoreboard/shadow.py;h=12f20893b5accb78ac69a8c64aff8b97eb47f05c;hb=8ef8a90c823cd7edb4d85c8099e9a912adbe4ea4#l98

you can see there, the inputs on what's expected to occur (branch THEN
rather than ELSE) and on a later cycle, there are another two flags
indicating if the branch went on the THEN or the ELSE).


> Alternatively, as is done in BOOM, the branch predictor must revert all
> visible state to what it was before the first mispredicted branch or trap.

the augmented 6600 doesn't work like that: it's a lot simpler.  okok it *looks*
like "reversion" but actually it's much more straightforward: when a shadow is
enabled, "writes" are prohibited whilst "calculation" is allowed.

that's really all there is to it.  you can think of it as "reversion" but
that's a misleading misnomer, because due to the separation between the "write
commit" and "calculation" phases, there's nothing to actually "revert".

no changes hit the register file until that shadow decision says "yes go
ahead".

no writes to memory hit the register file until that shadow decision says "yes
go ahead".

and the shadow decision *only* gets made if there is a HUNDRED PERCENT
guarantee that the write is allowed to proceed, i.e. that there is no
*need* for "reversion".

so it... completely *avoids* reversion by stacking up the intermediate
data in the Function Unit "result" latches.

[the "register bypass" mechanism allows those results to be used as inputs
to other FUs so that there's no hold-up due to speculative chained
computations]


> Note that that is different from getting info from instruction fetch (such
> as: is an instruction a branch or something else), since those are assumed
> to not change without an icache flush.

it's reasonable and normal to assume that the icache is read-only, we're
not going to support self-modifying code.  it's too much :)

-- 
You are receiving this mail because:
You are on the CC list for the bug.