Re: Branch prediction

>There are two sides to the branch prediction story: static
>(compile-time) prediction and dynamic prediction done by the
>prefetcher.


The x86 does not allow AFAIK static prediction. The PPC does.


>that). Of course, this means that your predictor should be really
>smart: these CPUs expect prediction accuracy well into the 90% range.


The scheme used by P6s and on (maybe Pentium MMX too? I don't
remember) is exceptionally smart. It works by bucketing jumps into 16
bins, according to a taken/not-taken bit pattern. E.g. bin 13 (1101)
means Taken, Taken, Not-Taken, Taken; it is actually able to guess all
pattern with periods up to six, a few longer patterns (up to 16), and
even to learn irregularities.


There's a description of it in Agner Fog's Pentium and Pentium Pro
optimization paper (www.agner.org/assem/)


There's a fundamental problem with every branch prediction system I
ran over. They do not work with indirect jump. Most processors
remember where the last jump landed, which might be decent for a lexer
but absolutely impractical for a bytecode interpreter; the solution
might be to tell the processor "hey, trust me, the jump is going to
land there" with a special instruction.


Paolo Bonzini

Return to the comp.compilers page.
Search the comp.compilers archives again.