OSDev.org

You know what? Show us the code a compiler would output if it did branch prediction itself. Give us an example that's better than the CPU doing it.

(...)
for (int i = 0; i < 50; i++)
{
    (do stuff)
}
(...)

(...)
CLR r1
.loop:
CMP r1, 50-1
MOV r2, .endloop
(add n-2 parallel ops here)
MOVNBE r2, .loop
(add n-1 parallel ops here)

(do parts of stuff)

DJMP r2 ; fetching starts now
(do last few instructions of stuff to fill delay slot)
INC r1
.endloop: 
; jump will have taken effect here.
(...)

Rusky wrote:What other algorithm are you possibly going to use for detecting aliasing stores?

Combuster wrote:

You know what? Show us the code a compiler would output if it did branch prediction itself. Give us an example that's better than the CPU doing it.

Code: Select all

(...)
for (int i = 0; i < 50; i++)
{
    (do stuff)
}
(...)

Code: Select all

(...)
CLR r1
.loop:
CMP r1, 50-1
MOV r2, .endloop
(add n-2 parallel ops here)
MOVNBE r2, .loop
(add n-1 parallel ops here)

(do parts of stuff)

DJMP r2 ; fetching starts now
(do last few instructions of stuff to fill delay slot)
INC r1
.endloop: 
; jump will have taken effect here.
(...)

Owen wrote:BETTER. Trivial loop exit conditions are uninteresting and, well, trivial. Intel have been correctly predicting them for 15 years.

In fact your code is worse, because it wastes two registers and two instructions per cycle.

Now that we've got enough background, let's take a look at Intel's own description of the loop detector:

The Loop Detector analyzes branches to see if they have loop behavior. Loop behavior is defined as moving in one direction (taken or not-taken) a fixed number of times interspersed with a single movement in the opposite direction. When such a branch is detected, a set of counters are allocated in the predictor such that the behavior of the program can be predicted completely accurately for larger iteration counts than typically captured by global or local history predictors.

Combuster wrote:Because zero mispredictions are better than occasional mispredictions?

Combuster wrote:Bottom line: there's no such thing as the CPU being superior to the compiler.

Combuster wrote:Because you're trying to compare apples to oranges again? What is a CPU without compiler worth?

A CPU without a compiler is worth about the same as a compiler without a CPU.

Combuster wrote:

Owen wrote:BETTER. Trivial loop exit conditions are uninteresting and, well, trivial. Intel have been correctly predicting them for 15 years.

In fact your code is worse, because it wastes two registers and two instructions per cycle.

And you think it's fair to simply strip silicon somewhere and not giving it back at an equal rate in another part of the machine?

Combuster wrote:

Now that we've got enough background, let's take a look at Intel's own description of the loop detector:

The Loop Detector analyzes branches to see if they have loop behavior. Loop behavior is defined as moving in one direction (taken or not-taken) a fixed number of times interspersed with a single movement in the opposite direction. When such a branch is detected, a set of counters are allocated in the predictor such that the behavior of the program can be predicted completely accurately for larger iteration counts than typically captured by global or local history predictors.

Which means that it only works if the loop always has the same number of iterations, and always fails the first time