How does the 6502 implement its branch instructions?

Question

The 6502's decode ROM takes an input which tells it when to start the next instruction. In the case of something like an INX or LDA #7F, it is obvious that once the output from the ALU has been latched in the destination register, the ROM may issue the signal to start the next instruction.

As for the conditional branches, BEQ, BMI and so on either take 2 or 3 cycles depending on whether the branch is taken or not. That makes sense: in the case that the branch is taken, the ALU needs to update the PC. And otherwise of course, the next instruction may start early. But how is this behaviour implemented?

I can imagine one way to do it would be to have all the relevant flags serve as inputs to the decode ROM. Then BEQ and friends could be microprogrammed to work differently depending on which bits were set. But a look at the block diagram shows that's not how it works. And probably it would be a wasteful way to do it since so few instructions would need it.

Another way might be to send the branch offset and the low byte of the program counter to the ALU, and then conditionally write the addition/subtraction to the low byte of the program counter if the branch is taken (also taking care to handle the carry-out), or else issue the next instruction. But the datapaths on the block diagram do not show that the data really can move in this way.

And the block diagram, as far as I can see, also does not show that there is anything which takes the status flags as inputs. So I am confused about how this actually works!

Answer 1

Quick answer (I can update with a cycle-by-cycle description of what happens if you need it):

You can see exactly what happens in the 6502 using the in-browser simulation provided by visual6502.org in advanced mode. Enter a branch, and watch what the control lines do. You can even see where every signal is located on the chip.

The 6502 has a two-stage "pipeline" for instruction decoding, so the opcode for the next is already fetched in the last cycle of the current instruction.

This is how the 2 cycle variant of branch works: One cycle for opcode fetch, one cycle to fetch the offset, and if the branch is not taken, then the next opcode is just fetched normally.

For the 3-cycle variant, it's too late to change the next opcode fetch (because it was already scheduled by the "fetch offset" cycle). Also, the offset has to be fed into the ALU to get the next address. So if the branch is taken, you'll have one "empty" memory cycle for the location directly after the branch instruction.

There's also a 4-cycle variant, if the new PC location crosses a page boundary. The ALU is only 8 bit wide, so calculating the high byte of the PC using carry/borrow takes an additional cycle. Which means you have two "empty" fetches.

Flags etc. are input to the control logic, the block diagram only provides an overview. This visual6502 wiki page explains names of the most signals.

Answer 2

(Caveat, this is from far away memory)

In general your second assumption is right. But step by step:

I can imagine one way to do it would be to have all the relevant flags serve as inputs to the decode ROM. Then BEQ and friends could be microprogrammed to work differently depending on which bits were set.

Now, as the 6502 logic is more a highly (in hardware) optimized microprogramm than what CS classes usually tell, not everything is really in the ROM part, but also realized as dedicated circuitry. After all, this hybrid optimization is the true genius of the 6500.

In addition it's neccesarry to keep in mind that Mr. Hanson's diagram isn't a full schematic, but rather simplified to make it easily readable in the first place.

Signals like Carry are inputted into the block called Random Control Logic as they are not only needed for branches, but for example in each and every addressing to detect page overrun. Remember the additional clock the original 6500 needed when an index causes a carry into the upper 8 bit of a data address? Well, the 'microcode' within the Decode ROM always include this additional cycle, but with Carry cleared, the logic cancels this step out by advancing the micro programm counter (called Timing Generation Logic here) one ahead (No the wide arrows).

Another way might be to send the branch offset and the low byte of the program counter to the ALU, and then conditionally write the addition/subtraction to the low byte of the program counter if the branch is taken (also taking care to handle the carry-out), or else issue the next instruction.

Yup, that's basically the way it is done.

But the datapaths on the block diagram do not show that the data really can move in this way.

Sure they do. Note the way how there is a Pass Mosfets box between DB and SB (look right between PCH and S). This way the offset noted in the branch instruction is routed from the Input Latch (DL) via DB and SB over to the A-side (AI) of the AL, while PCL is transferred using ADL.

Yup, much like a diversion sign on the daily ride to work, which one doesn't note anymore :))

And the block diagram, as far as I can see, also does not show that there is anything which takes the status flags as inputs. So I am confused about how this actually works!

Part of the simplification. Note how three control signals directly go into Carry, while ACR from the ALU points rather unspecified in from above.

So, while the Hanson-Diagram does reveal a lot, and is for most parts correct, it's not an exact schematic, but intended to ilustrate certain features for his lectures and IEEE micro scripts. For example one of his publications (in 1995) is exactly about using D-flipflops as such pass thru blocks.