Why are branches relative in many 8-bit CPUs?

Question

I was looking over an old article on the 6809 and was perusing the opcodes and noticed that the branch instructions came in two flavors, long and short. That sparked a memory about one of the 6502-series CPUs that added similar long-branches - 65CE02 perhaps?

So, why are branches in most 6502 systems based on 8-bit relative addresses instead of absolute? One byte less in the opcode, but it would seem that would be just as useful to JMP, but BRA was only added sometime later. Performance? Isn't the add into the PC the same as reading another address byte?

Answer 1

TL;DR:

It is all about making one of the most important instructions as performant as possible, while keeping everything manageable for tools at the time (plus a little bit of dogma). The branching is thus the most optimized instruction of the whole 6502 design.

In addition, long branches are not really in demand (*1). Of the 116 branches used in the original KIM 6530-003 ROM not a single one is followed by a JMP - which would be the case if any longer distance had to be covered. Same observation can be made by looking at many other contemporary sources (*2).

So why add 8 (9) opcodes for something as exotic and little of practical use?

---

The Long Read

Why were (are?) branches relative in most 8-bit CPUs?

Because it saves code space and covers the great majority of cases - long versions can easily be created by using the inverted case branching around a long jump (absolute or relative), thus halving the number of code positions needed (*3) at the expense of a few cycles in rare cases where a long distance is to be covered.

---

[Insert]

Generic Considerations About Jumping and Branching

Beside the semantic separation of branching as result of a decision and jumping as unconditional, design of an instruction set is always about waging alternatives and finding a middle ground.

Without any doubt, a system needs a way to set the PC to any location within the program address space. Usually called a Jump. Many systems offer in addition a Subroutine Call as special case with return address management, often accomplished by a specific Return instruction (*4).

In addition it does make quite sense to be able to easily change control instruction flow based on conditions (*5). In a simple and symmetric world, this could apply to all three mentioned variations (Jump, Call, Return).

A classic example would be the 8080 with having all of them as unconditional and conditional version. Nice and symmetric, but comes at a hefty cost of 27 opcodes. That's more than 10% of the instruction set.

Now, while conditional jumping is neat and may save code length, looking at real code shows that the vast amount of Calls and Returns are unconditional. So it might be acceptable to drop conditions from them and just go by having jumps conditional - and when needed, Call or Return can be prefixed by a jump using the inverse condition. This reduced the needed codepoints to only 11.

Looking even closer will reveal that the huge majority of conditional jumps only reach for quite short distances forth or back. Often just a single or a few instructions. Thus, kind of a short distance jump could be used to save in code size, an important measure. For most classic CPUs code length is also quite related to execution time (*6) thus a shorter distance encoding will speed up execution - as well as reducing penalty when prefixing non conditional instructions.

While there are CPUs having very short distance branches, given the 8 bit code nature, a +/- 7 bit offset seems like a good compromise here. And that's what did set the 6800 apart from its 8080 counterpart. Short branches that save on code in most cases (as well as code points), which can be used to synthesize other conditional instructions with an acceptable penalty.

Skips would be an even more generic approach, by skipping always the next instruction when its condition is met. Here no length is needed, thus they'd be single byte instructions needing only 8 (based on 8080) code points in total. Not only any conditional jump can be synthesized, but all instructions can be made conditional. On the backside, all conditional instructions would take additional time and as soon as more than one instruction is to be skipped, it gets quite costly. So trade off is speed (many standard cases) for simplicity and general usability.

The last resort could be adding conditions to every opcodes (like on ARM). It's like combining the original (8080) approach with the generic skip application - but now at great expense of most of the code space.

Long story short, optimized short and relative branches offer a trade off between all of this with an emphasis on most common use cases.

[Back to the Question]

---

So, why are branches in most 6502 systems based on 8-bit relative addresses instead of absolute?

I guess you mean as well 16 bit relative.

It's all about most-used case. Branches are for short distance decision making. Like testing if the upper half of a pointer needs to be incremented, a sign to be adjusted, or a compare is successful or not.

Adding another set of long relative would have added at least 8 long branch instructions, some more ROM space, but more important now always requiring an additional cycle to do the 16 bit calculation (plus the additional fetch).

Maybe most important for the 6502 philosophy, it would have added the need to make the 8/16 bit offset decision detectable for the (very primitive) single pass assembler they had in mind. The whole 6502 assembly syntax is made in a way that encoding can be determined in whole by only looking at the actual line processed. With two encoding variations for relative, it would have required either:

• a long opcode name variant like BEL, BNL, BCSL ... oops, breaking the 3 letter structure they wanted for their simple assembler. So this would end up with something quite ugly and hard to remember. Or
• some additional keyword like SHORT and LONG (*8), again breaking the syntax, or
• adding some 'special' symbol for either case, like BNE !$02 for short or alike.

In all cases the burden to decide which is right is put on the programmer to know ahead of time which to use. Of course, using

• a two pass Assembler

could have resolved that - for the cost of making the assembler a magnitude more complex and costly - hard to do on such simple system as they were thinking about at the time. The simple straight forward assembling was one of the major advantages compared to 'big' systems.

One byte less in the opcode,

That's the first and most important, as it saves a whole Byte from one of the most used instructions (see below) and a whole cycle of execution. And it's a cycle that gets more often than not saved at highly utilized code sections - like decisions when scanning a string, comparing a lot of alternatives in a case like structure, or some tight counting loop.

but it would seem that would be just as useful to JMP, but BRA was only added sometime later.

Admittedly the 6502 makers were somewhat into dogma(*9), thus branches had to be conditioned, while jumps are unconditioned (and absolute). So the handy BRA, which was already existing in the 6800, got left out for the 6502 (*10). Sometimes one gets quite stuck during design.

Performance?

Yup, exactly that. Branches are essential to any computing - which is, after all, about decision making on many levels - and most of them all the way down on signs, carry and equal or not.

Looking at contemporary sources shows that branches are among the most used instructions. Within the KIM 6530-003 source there are 116 branches ...

---

Give yourself some time to let that sink in:

One Hundred and Sixteen Branch Instruction within a 1 KiB ROM.

That is 232 ($E8) bytes in length. Almost a fourth of the whole ROM is filled with branches.

---

... the second most prevalent group, right after LDx (162, thereof 108 LDA) and STx (153, thereof 115 STA) and on par with JSR and far ahead of everything else (*11). The combination of being one of the most used instruction (*12) and its potential for optimization makes it the most desirable target for doing so.

In fact, the branch is eventually the most optimized instruction within the 6502. It's really worth to study its workings using the Visual 6502 emulator. Several special items have been added to make sure that its execution is down to the minimum number of cycles, that is two for not taken and three for taken, unless a page is crossed. The later optimization was for example not considered worthwhile for any of the indexed writes, were a page crossing could happen - here instructions always took the additional cycle.

Isn't the add into the PC the same as reading another address byte?

No, it's done in parallel, ahead of time (during PHI1) so no time is wasted to calculate it.

Branches are one of the niftiest parts in 6502 logic. I really suggest taking a few hours and go thru their details on Visual 6502 to understand.

---

*1 - This should be already clear from a design point of view: Code needing long conditional branches is usually not well structured to start with.

*2 - For example the much later (1978) and way bigger (8 KiB) MS-Basic 1.1, used for PET, OSI and Apple II, features only 23 cases of a jump following a branch - of ~140 jumps at all.

*3 - Since a long jump (usually) always exists, branches are needed only once (as short).

*4 - Some designs go for the bare minimum having only a single jump instruction, always delivering the previous PC (return address) in a special location (usually a register), and handling everything via this single instruction. Others have different jumps, but no return, and so on. But for this we stay with what's common on mainstream 8 bit.

*5 - It is quite possible to do computation without changing instruction flow (branching), not at least used by Raul Ronjas proof about the Z3 being a full figured computer. Still, it gets easily out of hand even with small programs and is as useful as a Turing machine for real life computing.

*6 - This is not only true for the 6502 being quite close in its execution time with the number of memory cycles, but as well for the Z80. Many of its really nice enhanced operations are not as great when it comes to execution time due the needed prefix adding 4 cycles just to mark them.

*7 - Quite handy when it comes to all the little cases were only a single instruction has to be bypassed, like increment of a multi byte pointer. With conditional jumps a 16 bit pointer some INC; JNC +n; INC, costing 5 byte code for absolute, 4 bytes with relative, but only 3 with skip.

*8 - Oops, did anyone say x86?

*9 - Like the infamous 'real' indexing argument over the 6800 way, that brought two 8 bit 'real' indices at the cost of no base register, making structure handling on the 6502 rather clumsy.

*10 - I wouldn't have minded if it had just be renamed to JMP or short, but then again, this would have collided with the single pass assembly they had in mind.

*11 - The next most used group are compares (CMx), way down at 39 instances (38 of them being CMP) and absolute jumps (JMP ) at 31. It nicely reflects that most work of a CPU is about shoveling data and branching accordingly.

*12 - Of course, this is just quick static analysis, dynamic quantities will differ - then again, due to branches being part of each and every looping, they usually end up with an even bigger share.

Answer 2

On the 6502, the designers did this for efficiency. This is documented in the original MCS 6500 Microcomputer Family Programming Manual:

If one considers that the instruction JMP required three bytes, one for OP CODE, one for new program counter low (PCL) and one for new program counter high (PCH) it is seen that jump on carry set would also require three bytes. Because most programs for control require many continual jumps or branches, the MCS650X uses "relative" addressing for all conditional test instructions. To perform any branch, the program counter must be changed. In relative addressing, however, we add the value in the memory location following the OP CODE to the program counter. This allows us to specify a new program counter location with only two bytes, one for the OP CODE and one for the value to be added. (§4.1.1 p. 38)

This is obviously more space-efficient (one byte for the opcode and one byte for the 8-bit offset versus one byte for the opcode and two bytes for a 16-bit absolute address), but also (perhaps less obviously) more time-efficient when averaged out: a branch not taken is only two cycles (to read the opcode and offset) with the relative address, but still three cyles with an absolute address. (Taken is three cycles in both cases. The one exception is that a taken relative branch needs four cycles when it crosses a page boundary, due to the need for a second add for the carry from the low byte of the address, but that's relatively infrequent.)

It would be possible to try to achieve this with partial absolute addresses (e.g., by specifying only the lower eight bits of the absolute address and taking the upper eight bits from the PC, effectively using "the current page,"), but that gets pretty complex for the programmer because you'd need to know about the absolute location of your code to avoid accidental jumps to the wrong page.¹

Another reason for having some sort of relative jumps is to allow creation of more easily relocatable code. Code that uses only relative jumps can be copied to another location and "just work"; code with absolute jumps must have those patched up for the new jump target locations. While having a limited set of relative branch instructions doesn't let you relocate arbitrary code, it still makes it easy to relocate small routines, which is valuable. There are, for example, not-infrequent cases where using self-modifying code on the 6502 can increase both speed and memory efficiency. Self-modifying code can't be run from ROM, but if you can easily copy small routines from ROM to RAM that opens up this technique for code intended to be in ROM.

Relocatable code wasn't a major priority on the 6502 (though I have little doubt that the designers did have in mind some support for this from the start—whatever they could fit in without adding cost to the design), but it was for the 6809, where you noticed that they'd added long branches. The MC6809 data sheet says in its very first paragraph that it "supports modern programming techniques such as position independence," and later in the discussion of long and short relative branches, "Position-independent code can be easily generated through the use of relative branching" (p. 20). Somewhere there's a larger discussion of Motorola's vision of building ROMs for specific machines from a large library of relocatable code, but I don't have a reference for that at the moment.

---

¹ That's more complex than it sounds on some CPUs. Consider a branch in the last two bytes of a page on a 6502: that puts the PC on the next page before it's used to calculate the branch address. There are ways of working around this, too, such as considering addresses in the "other half" of the page to be in the previous or next page, as appropriate, but now you're piling complexity on complexity.

Answer 3

Another possible reason: with PC-relative addresses, you can easily relocate your program in the memory. Sometimes is a good idea to have a program you can load and run from any address (well, not really ANY, but you know...)

When you program like "jump 10 bytes forward", you can easily relocate. With "jump at $12A5", you have a fix memory location your program can be loaded into.

Answer 4

Much discussion here about the benefits and costs of short vs long addressing, but the posted question asks about relative vs not. A machine like the RCA 1802, for example, has both short and long branches, for the reasons well covered here already, but they are absolute, and not relative.

What this means is that where your code ends up in memory determines where the short branches can reach, and this is not usually known when you are initially writing the code. In other words, memory is organized as a series of short (256-byte) pages, and short branches can only operate within the page they are in. So, you write your code, as a part of a bunch of other code, but you have no idea whether it will run properly or not until you've mapped all of the code into memory. (Linked, etc.)

By using an adder inside the machine to implement relative branches, your smaller/faster code can be relatively ignorant of exactly where it resides in memory. This is an advantage, especially with unsophicated (or even no) development tools, appropriate for the time these machines were current.