19

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?

  • 28
    "One byte less in the opcode" - is very important when you only have a few K of memory. – tum_ Nov 23 '19 at 13:59
  • 1
    Related: Why do x86 jump/call instructions use relative displacements instead of absolute destinations? on SO. Interesting to note that MIPS does have section-absolute j instructions but most modern ISAs use relative branches for everything except indirect branches. On x86 there's a choice between short rel8 vs. near rel16 or rel32 jumps/branches just to save code-size. – Peter Cordes Nov 23 '19 at 23:05
  • 1
    @tum_ : not only memory, but time. From my experience working with 8 bit microcontrollers and having to decode weird and very fast signals at the inputs, the biggest bottlenecks were always branches. Having a branch take one clock cycle more or less can make all the difference between a certain CPU at a certain clock setting being suitable to a task or not. – vsz Nov 25 '19 at 7:05
  • Most processors have relative jumps, absolute is less useful and less used. This is not limited to 8 bit instruction sets. – old_timer Feb 13 at 12:32
28

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 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 cycle. 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 source they are, with 116 instances, 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.

| improve this answer | |
  • I don't know this particular CPU, but in general, "branches" contain a simple integer offset (from the current instruction), but "jumps" tend to support the full range of possibilities for memory operand specification in the particular instruction set - indexed, indirect, base-and-displacement, etc. – another-dave Nov 23 '19 at 19:45
  • 2
    I wonder if the Z80 instruction set was designed at a time when the part was expected to use an 8-bit ALU? The Z80's instruction set would make sense with an 8-bit ALU, and the decision to use a 4-bit ALU would have made sense without the added Z80 instructions, but the usefulness of many Z80 features is undermined by the ALU. The performance of JR, Ix+d addressing modes, and LDIR/LDDR, etc. all incur a two-cycle penalty as a consequence of the four-bit ALU. – supercat Nov 23 '19 at 20:22
  • 1
    @another-dave Well, I guess one could argue a lot about the semantics, and many have done so. But in general, branching is used if there alternatives going from one point into different directions, like branches branching on a tree. A jump in contrast changes position without any doubt. Then again, this differentiation is only neccessary on designs doing so. As usual, names are what people are making of them. Hardware doesn't care for names. (and for the size argument, x86 uses JMP for everything from 8 bit REL to 32 bit absolute and 48 bit segmented, while on /370 everything is a branch. – Raffzahn Nov 23 '19 at 20:30
  • 1
    @Raffzahn: x86 doesn't have any absolute direct near branches, only absolute segmented jumps (to a new CS:[E]IP) can have an absolute target as part of the machine code. (And yes I omitted CS:RIP on purpose.) It's only 32-bit and 48-bit absolute segmented that exist (jmp ptr16:16 and ptr16:32) that exist, or near jmp rel32 in 32 and 64-bit mode. Not jmp abs32. felixcloutier.com/x86/jmp. I know this is off topic and wasn't the point of your last comment; yes x86 calls everything JMP. MIPS is interesting where jumps are section-absolute, branches are relative – Peter Cordes Nov 24 '19 at 2:54
  • 1
    I remember generating jump tables that could be invoked using rts. – Peter Smith Nov 25 '19 at 15:17
14

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.

| improve this answer | |
  • 1
    MIPS j instructions do work in this section-absolute way you're talking about as a hypothetical for 6502. (vs. relative bne etc). They replace the low 28 bits of the 32-bit PC, so they're absolute within a 256MB region. And yes, relative to the end of the jump = relative to the delay slot instruction address means it can jump into the next section. How to Calculate Jump Target Address and Branch Target Address?. But 256MiB is a lot less of a problem than 256B boundaries! And MIPS was designed to use virtual memory allowing easy choice of code address. – Peter Cordes Nov 24 '19 at 20:54
  • With a limited amount of memory space (64k addresses may sound a lot...), every byte was important and for that reason functions were kept small and efficient. In all the years I was writing assembly for the 6502 (and parts that used it as the core such as the CMD65151 communications processor) I never had the need for a conditional branch outside the relative address range. It was considered poor practice (function too large) if a conditional was outside this range at least in the places I worked at the time. – Peter Smith Dec 8 '19 at 14:42
  • "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 bye of the address, but that's relatively infrequent." Which isn't an inherent issue at all, but only due implementation. – Raffzahn Dec 9 '19 at 0:16
  • @PeterSmith True enough,but the designers did address this anyway in the Programming Manual §4.1.4, stating that "longer programs will occasionally find it necessary to conditionally branch to a location that is significantly further away than the branch command will directly reach" and giving a technique to facilitate such branches. – cjs Dec 9 '19 at 0:17
  • @Raffzahn It was indeed an inherent issue unless you ignore the fact that the primary design goal of the 6502 was to produce an inexpensive processor. Going to significant extra expense to add a 16-bit adder for this would have worked directly against that design goal by adding significant expense for very little benefit. – cjs Dec 9 '19 at 0:26
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.

| improve this answer | |
  • 1
    Except that the 6502 in question doesn't have any other relative instructions. Jumps and subroutine calls are all absolute, only branches are relative. – Raffzahn Dec 7 '19 at 20:38
  • @Raffzahn The relocation abilities provided by branch instructions alone are not useless without also having relative jumps and subroutine calls. It's perfectly reasonable to want to provide the ability to relocate individual subroutines (say, from ROM to RAM) without spending the additional cost required to provide general relocation facilities. – cjs Dec 10 '19 at 0:00
  • @CurtJ.Sampson Yes, it is and I love to use it - just this question is about the 6502 offering relative only for branches, but not any other execution transfer. Isn't it? – Raffzahn Dec 10 '19 at 0:11
  • @Raffzahn Right. And you can still get some reasonably useful relocation abilities by doing exactly that, without going to the extra expense of adding relative long branches. It could be that the original designers weren't thinking about relocatable code at all (they didn't mention it in the original Programming Manual), but I find that unlikely. – cjs Dec 10 '19 at 4:51
  • @CurtJ.Sampson Right, it seams rather unlikely that they didn't think about it, and Looking at the ISA structure, a long relative wouldn't have been a big issue, just adding a clock. It's all there. Similar there is no indirect JSR. What all of that has in common is it's only needed in systems which need to load and configure code at runtime. The 6500 was, like many early micros, targeted at what we call embedded today. Here all code gets static linked before burned into (EP)ROM. And lets be honest, the overwhelming number of 6500 usages ended up not in console but control. – Raffzahn Dec 10 '19 at 8:16
3

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.