The 68060 had a branch predictor that improved the cycle count of branches that tended to go one way or the other. Apparently it did not handle branches that alternated or had some kind of pattern to when they were taken.
How did this branch predictor work? Is it the same as the 68040?
Attention: The part about the 4-Way Set-Associative Branch Cache has been rewritten, as my original explanation was complete bogus (*0).
What a big and and wide question.
Fast Answer: No CPU can handle alternating branches equally well.
Slow Answer: Work your way thru the 68060 User Manual. It's all there.
Short Answer: Having said that, your question already implies the answer. If a cache records previous taken decisions and predicts that the same will happen next time, then alternating branches are the perfect way to screw that bookkeeping.
Long Answer:
Already the 68040 includes a static branch 'prediction' based on the Taken strategy. This means, it assumes that branches are always taken. This already improves the 'prediction' from 30% to 70% (*1). It is the most simple modification for 'prediction', as it just means to modify fetch whenever a branch comes up. The 68040 goes even a step ahead and fetches both targets, but queues in only the taken target. Thus resulting in a mere 2 clock penalty to requeue the already fetched not-taken instruction if the branch is not taken(*2). I'm not sure how much this modifies the average, but it comes without any penalty.
The 68060 adds to this what they called a 'Branch Prediction Logic with a 256-Entry, 4-Way Set-Associative, Virtual-Mapped Branch Cache for Improved Branch Instruction Performance' (p1-4 68060UM) sounds big, isn't so much, but reveals much about it's working.
First, when looking at the cache cleared clock cycles (*3) it's obvious that the 'both targets' strategy got dropped (*4). Now, lets dig into the buzzword cloud above:
256-Entry - 256 Entries. Cool. Err, just what type of entry it is, is not described. It may be 256 entries, selected with the lower 8 address bits and that's it. So two branches (i.e. in a loop) will trash each other. Or do they also include the upper 24 bits for verification? Well, often not (*5). Who knows.
4-Way Set-Associative - This just tells us that there are 4 entries which are shared among the last four branches executed with the same index. This is helpful to cover a wider range of memory without wasting too many entries - and at the cost of a more complex detection logic and additional management. Also this means there are only 64 indices to be used (organised as 64x4).
Virtual-Mapped - Now, that's an important hint, as it reveals that the cache access is based on virtual addresses. Since the lower 8 bits of a virtual address and a real address are always the same (for MK68k anyway), the branch address must be recorded in the cache entry used to make this happen (*6).
Not told in the users manual is the prediction strategy really used. We know already that the 68040 used a BTFN strategy, and 68060 execution timings with cleared branch cache does hint a similar default setting. But what about a filled cache?
Well, lucky me I did find bit more information in a stack of old papers from HC06 in 1994 called 'The Superscalar Hardware Architecture of the MC68060' (they even put it online):
While we already discussed the associative part, the 4-state-model is an important hint how prediction works, and why it's still good, even when a branch sometimes goes astray. See below. The optimization part means that prediction already interacts with fetch as early as possible, so pipelines are filled according to the prediction. And BTFN as default makes life easy in unknown territory.
When thinking about a branch cache we usually imagine an entry for (hopefully) each branch, that records if it has been taken last time or not, so it can be used as assumption when it comes around again. This works eventually great on loops with many iterations. Sure there is (usually) a miss when entering and always a miss when leaving, but all additional iterations will benefit from the prediction (*7).
If we look at taken or not as a continuum with unconditional branches at one end and totally random branches at the other, we will find loops and alike near the unconditional end. The easy to predict ones. One bit will do a great job for most of the time. Totally random ones, which might conclude with the 'alternating' the question mentions, are by definition unpredictable. No logic can cover them. Especially not one to be implemented using precious chip space.
All static single bit caches will yield a false result when the condition changes. So on first sight this could be the answer to above question. Whenever the decision changes the prediction fails. And even worse, if this is just a one time occurrence, it'll fail next time again.
Studying above contiuum we will find that it also describes a grade from mostly taken one way and rarely another (with unconditional as the always extreme, proving the rule) down to random. Mostly does sounds like a good area to improve on, doesn't it? Think of a selection, picking out all blue pixels on the screen or selecting all Orks in an NPC table or alike. Most of the time the condition will not trigger, and when, it'll often just trigger once. So what about adding a counter how often it has been taken during the last flybys?
Instead of just one bit (with two states) for last time taken/not taken one could use two bits (the mentioned four states) and record multiple decisions of the same kind. Lets say we go:
00 Not taken once
01 Not taken more than once
10 Taken once
11 Taken more than once
The prediction is still based on a single bit (the leftmost in above list), thus equally fast, but instead of just setting or clearing the prediction bit we only do it if the other bit is also zero, otherwise we clear first the second bit. This bit works now like a one bit counter, avoiding that an outlier in combinations like NNTN or TTNT will trash the prediction on the long run.
As a drawback it will result in two misses when an always taken changes into a never taken or vice versa. Like when the search hits a group of Orks :) In reality, branches do flock like sheep, and in average code there are more branches that trigger only sometimes the other way than there are long streak triggered ones or truly random. Thus pushing up the hit counter from ~85% to ~90% Good job for a single bit, isn't it? (*8)
Answer: The 68060 is like any other CPU with prediction slowed by changing conditions (alternating branches as you call it), but not as much if they change only sometimes.
When reordering the encoding we also can easy establish a BTFN default handling when the cache is cleared:
00 Taken once
01 Taken more than once
10 Not taken once
11 Not taken more than once
Now a branch with an uninitialized entry works much like the 68040 does (*9).
Here again Motorola did go one step further and added an explicit BTFN strategy for all cache misses (instead of living with a false hit). I guess with all the transistors spend on the 4-way implementation these few additional gates was a low price payed for a good improvement.
BTW, this is more or less the same scheme the Pentium uses (with a few errors :)) - and CDC already used in the 1970s - as well as /370ish CPUs).
Now having the branch prediction working ahead of instruction execute adds a nice quirk to the 68060: When a TRAP is used with 'additional' parameters, that look like a branch, the TRAP will result in an access fault, as now the cache is screwed up (s8.4.7, p8-29). This will be flagged in the Fault Status Word, and clearing the cache is all the fault handler has to do before rescheduling the instruction (p8-25).
The basics described here are noted in the 68080UM, including the buzzword list (sans decoding), excluding the strategy details, so RTFM is always a good start.
*0 - My original description of the 4-Way Set-Associative Branch Cache has been critisised by a reader (@pipe) as wrong. Just to make prove how good I am, I started to search thru my old papers (and there are lots of them) to prove him wrong. And voila, I found a handout from HC06 in 1994 for a speech about 'The Superscalar Hardware Architecture of the MC68060' providing a slide with a little more information.
Drats, @pipe was right, Motorola did really spend 4 comparators plus LRU (or alike) logic and more to make it 4-way associative like said. Never thought they had gone that length.
At least that document also provided more information that supported the functional description I presented, even my assumption (due execution timing) of a BTFN default. Sigh.
*1 - Yes, it's not the simple 50% people often assume when asked about branch probability. In real code branches are more often taken than not. And it's not just a little, but rather significant. Only 30% of all branches (remember to include the unconditional) are not taken. Just think of loops, mostly branching back until a condition is reached, or code blocks that are only executed when a condition is met. The last one coresponds with modern block orientated programming and was maybe a bit different in ye old assembly days - when we where free to structure as we liked - but not much.
*2 - I'm not really sure, but it might perform overall better than a Back-Taken-Forward-Not strategy, as it always reduces the penalty for wrong 'prediction' to these two clock cycles, but the cost of always spending these cycles on forward. I would love to get more in depth numbers here.
BTFN assumes that backward branches are usually taken, thus the next instruction to be prepared is the one the branch points to - when it's negative - otherwise it just goes with the flow. Compared with an always taken strategy prediction raises in average code from 70% to 80% hit. Motorola PPC 603, of the same time, for example uses BTFN.
*3 - Backward Taken 3; Forward Taken 7; Backward Not Taken 7; Forward Not Taken 1
*4 - It wouldn't have made much sense anyway with the longer and different structured pipeline.
*5 - This would add another caveat for cache prediction: Aliasing error. Any access will find a corresponding entry reflecting the decision taken by any branch with the same lower 8 address bits. Not necessarily the droids we are looking for and a possible chance for a misprediction. But it saves a some chip real estate, so it was used in early mainframe designs.
*6 - Well, and adding the need for OS programmers to clear the branch prediction cache whenever the virtual address space is changed or modified. At least if they don't want to impale performance.
*7 - On first sight, a BTFN would do the same, even better as it only fails on the last iteration, but loop exits are not just a counter at the end, but also every intermediate conditional exit (when ...break). Here a cache wins over BTFN.
*8 - And no, larger counters as 1 bit would not improve the result any further, as any additional step does increase the number of (possible) initial faults, making any change in branch behaviour quite expensive. Expecialy hampering loops which soon would be better off with a BTFN than any cache.
*9 - Another reordering may also enable us to see it as saturating counter (one that doesn't run over):
00 Taken more than once
01 Taken once
10 Not taken once
11 Not taken more than once
Now it just counts +1 if a branch is not taken and -1 if it is taken. Not that a counter would really save gates or improve anything, but it makes a great addition to confuse students in CS classes.
(Edit: Wiki takes this even a step further by using the saturation counter metaphor and explaining it as a state machine. Yeah, it takes a lot of dedication to explain two bits (and 4 simple gates) in such a 'refined' way :))
