OSDev.org

And what if stuff modifies i?

You also have the problem of telling the CPU where and how much to prefetch. You could add a prefetch instruction so the CPU doesn't have to worry about whether you change r2 before the jump, which would even let you prefetch basic blocks rather than just guessing the size, but...

The Mill does that in hardware, running ahead through the chain of basic blocks in parallel with execution, to prefetch them all (the way it does this is pretty cool, you should check out the talk). It predicts which branch will be taken from each BB, and caches that, as well as storing the cache back with the executable so it can be used later. Do that from the compiler alone!

Stores in general? It is better to analyse high level code and to find aliasing assignments. If it is impossible then additional information is required about the situation. How far potential aliases are one from another? What are the instructions in between?

There are two very large issues with the compiler doing all the work.

1. The compiler has an inherently limited view of the system state. Unless you feed in the entire system (or at least a large chunk of it), there will be unpredictable data sources. The CPU on the other hand knows what these data sources are as soon as they enter cache (which, due to prefetch, may be many cycles before they're used).

2. How would the compiler encode the variable likelyhood of a branch being taken? It would have to indicate a rather complex set of rules for the prefetch code... almost as if it was re-encoding the instruction.

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.

Please try again

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?

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

And yet, your example is still broken.

Not to mention the Mill prefetches entire functions at a time, even from cold code, so if it did mispredict loop exit (they don't specify a predictor algorithm because different models will probably use different algos) the penalty would be only 5 cycles (which can be helped with speculative execution).

How is your example better than that?

Because zero mispredictions are better than occasional mispredictions?

(Also, you just used a "no it isn't" as an argument from authority)

That depends on the cost of a misprediction vs the cost of your implementation.

So at least you agree that we're all comparing apples to oranges here with this sort of stuff.

My point was that this quote was wrong:

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

Hi,



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

I think the main thing here is that compilers are good at doing the expensive static optimisations before run-time, while CPUs are good at doing the dynamic optimisations during run-time. These are mutually beneficial, not exclusive.


Cheers,

Brendan

I haven't read this thread carefully.......
What is meant by a compiler the above sentence?
A CPU with an assembler but no compiler has a greater worth than that of a compiler that targets a non-existing CPU (Is that what you mean by a compiler with no CPU?).
I might have misunderstood your point.
A valid point against this could be that an assembler is theoretically a compiler that translates assembly language into machine code.

A loop predictor does not comprise anywhere near the amount of silicon to add an additional execution unit, or an additional retirement unit.



"Because the Pentium M did it that way, all Intel processors do it that way"?

Nehalem and above implement Macro-op fusion, in which "dec reg, jnz backwards", "cmp reg, const, jnz backwards" pairs can be fused into one micro-op. Especially in the former case, tell me why it would be difficult for the processor to correctly predict that every time? It would surprise me entirely if Intel weren't predicting that correctly.

Now: Please tell me how you would beat branch-history predictors while using equal silicon area. Remember, if you use register or memory bandwidth to do so, the predictor wins, because those are things which are hard to expand (i.e. every increase in them consumes large amounts of silicon area) compared to the small dedicated resources predictors take.