Can branch predictors perfectly predict counting loops?

As far as I understand it, on the Mill the compiler converts each loop into a recursive function (which is a basic block). But that’s beside the point, as (as far as I understand it) the Mill’s predictor predicts that basic block A exits to basic block B. So, the cache loads basic block A, preloads basic block B, and the number of iterations are mostly meaningless to efficiency. Then again, I have slept many times since watching that talk.

Prediction offers little value in lengthy loops. Even in architectures with no form of prediction, there may be a miss on enter and another on exit, but for all the other iterations the loop body is already in the top level cache. At most a predictor can let fetch and decode proceed through the back branch without waiting for that branch to execute and the target resolve. That wait can be significant in very tight loops, but predictor hardware isn’t free and in cost conscious embedded usage predictors are an engineering choice.

This also applies to the Mill exit predictor. You are right that ours permits fetch-ahead without decode of the branch because the next ebb’s address is in the prediction, similarly to a BTB entry. The entry also contains a duration, in cycles, which tells the decode when to stop the current ebb and start on the new one. If the predicator was correct, the target ebb (and likely many more) is already in the TLC and the correct sequence of bundles passes through decode to issue with no bubbles.

That’s if no miss. When we execute the branch and discover that the prediction was wrong, or if we take a exit that wasn’t predicted, the hardware has already issued two cycles down the wrong path. Miss recovery has to unwind that, fetch the right target, and decode it, which takes 5 cycles if the target is in cache (legacy miss costs are usually around 20 cycles). A naive predictor will always miss at the bottom of a loop at the last iteration. If the loop has a low trip count the miss can be significant. To avoid it, a more sophisticated predictor uses prior branch history or iteration counts to switch the prediction on the last time through. We’ve tried both approaches, and found that which works best depends on the kind of apps being run, so that’s another configuration choice.

Could that be generalized to any arbitrary branch?

For example, consider this code:

int foo(int a) {
   // just whatever random code
   int b = a * a;
   int c = b * b;
   int d = a + b + c;

   // a branch that could be precalculated at the beginning of the function
   if (a) {
      return bar(d);
   } else {
      return baz(d);
   }
}

At the beginning of the function, we have enough information to know whether we will take that branch or not. A compiler could potentially introduce an instruction at the beginning to precalculate if the branch will be taken and notify the predictor, or there could be “delayed branch” instruction something like “branch in 4 cycles if a is non zero”.

This kind of code shows all the time in loops and precondition checking in functions.

• This reply was modified 12 months ago by  goldbug.
• This reply was modified 12 months ago by  goldbug.
• This reply was modified 12 months ago by  goldbug.

nihil novi
I had exactly the same idea, my obvious case was quicksort that switches to more regular quadratic algorithms for short arrays.
This way I have rediscovered Loop Termination Prediction, Count Register, Counted Loop Branch, etc.

Prediction offers little value in lengthy loops

Yes, but there is surprisingly high amount of relatively short loops.
And don’t forget, that vectorization makes loops shorter up to 32 times!

When we execute the branch and discover that the prediction was wrong, or if we take a exit that wasn’t predicted, the hardware has already issued two cycles down the wrong path. Miss recovery has to unwind that, fetch the right target, and decode it, which takes 5 cycles if the target is in cache

5 cycles on Mill is like 15 cycles on conventional processor – quite a big loss!

In essence you propose a deferred branch whose transfer is detached from the evaluation of the predicate, similar to the way Mill separates load issue from load retire.

IIRC Elbrus E2k uses this technique, it has Prepare Branch and Execute Branch instructions.

One is the time required to reset the fetch. If the target is not in the I0 microcache then reset would take roughly as long as mispredict recovery, i.e. five cycles in our test configs.

It looks like you should split speculative fetch and speculative code prefetch.

How often can we eval a predicate five cycles before the transfer? Not often I’d guess, but I have no numbers.

But you can start resetting the fetch earlier! Prepare Branch and the following instructions before Branch Execute are valid…

A semantic issue is how the DB interacts with other branches. Suppose a regular branch is executed between DB issue/eval and transfer? Who wins?

It doesn’t matter as long as it is consistent! We could treat it in the same way as delay slots, so the most “powerful” answer is:both of them, unfortunately it won’t work with Belt I suppose.

• This reply was modified 11 months, 4 weeks ago by  peceed.