[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 #5 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #4)
> 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.

Some branch prediction algorithms have a global history buffer where every
branch is recorded and, in order for the predictor to function properly (stay
synchronized), there has to be some value entered into the global history for
each branch that's fetched even if those branches are not known to be correct
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.

It is actually reversion since the branch predictor is part of the instruction
fetch pipeline -- before the 6600 OoO engine has a chance to affect it. The
branch predictor (assuming we don't use a really simplistic one) updates it's
state every cycle -- even before it knows the fetched instruction words. When
there is a mispredicted branch, we need to reset the branch predictor to the
state it had when that branch was fetched so we can execute the proper sequence
of branch predictor steps.

> 
> 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 :)

As long as we do support dynamically loading new code by executing the icache
sync instruction -- the Vulkan driver (as well as Linux itself) critically
depends on that to be able to execute JIT compiled code.

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