Would compare-and-branch have added an extra cycle on ARM-1?

Question

The ARM-1 was an early RISC CPU, designed in 1986 (and even more typical of early RISC design constraints than the year would suggest, since Acorn didn't have the budget to pay for the latest process technology, so it had similar constraints to previous RISC chips designed a few years earlier.)

It's not very RISC purist; the designers seem to have been happy to make an instruction do more than one thing, whenever this seemed likely to improve speed or code density. For example, every instruction (not just branch) is predicated on condition codes; every instruction can optionally shift the output; there are instructions to save and restore multiple registers.

One thing it doesn't have, is compare and branch in one instruction; you need to compare values first (setting a condition code), then branch on that condition code. This is admittedly similar to many early microprocessors, but to my way of thinking, it misses an opportunity when your instruction words are always 32 bits; that's plenty enough bits to specify a pair of registers to compare, and a branch displacement, in one instruction, which would save both cycles and code size.

So I'm wondering why they didn't do it that way. As above, it wasn't about philosophical purity.

One possibility that occurs to me: maybe with the then-available process technology, it wouldn't be possible to run a pair of values through the ALU, and also branch, in the same time; maybe the comparison would have added a cycle to the time taken for a conditional branch. In that case, squeezing them into one instruction, might have helped code density, but it would have done nothing for speed.

Is that the case? Or was there some other reason for the design as it was?

Answer 1

The ARM1 CPU core was tightly coupled to the memory interface - it was designed to be as efficient as possible when paired with FPM DRAM, and no consideration was given to performance with a cache or with another DRAM technology.

Compared to previous DRAM designs, the key innovation in FPM DRAM is that you can omit the RAS cycle if the next access is in the same DRAM page (i.e. you'd send the same values during the RAS cycle). On a typical FPM DRAM, you can do 4 fast page accesses in the time it takes you to do a single normal access; ARM1 has the SEQ signal to tell MEMC that the next access is sequential with the previous access, so that MEMC can allow it to use fast page accesses instead of a normal access whenever possible (and MEMC controls the clock, so it will stall the ARM1 if it crosses a page boundary).

A branch inherently forces the next instruction to be fetched using a normal access; in addition, on ARM1, it forces a pipeline bubble. Given this, a branch is only worthwhile compared to conditional execution if you need to skip at least 4 instructions to do your work with conditional execution - otherwise, conditional execution is faster, even though it executes 3 NOPs where a branch would not execute any.

Acorn had also decided to make the ARM1 strongly prefer position-independent code - which means that branches are PC-relative, and thus require an ALU operation to implement. Compares also need an ALU operation, and so a compare-and-branch would need to occupy the execute pipeline stage for two instructions worth of time, not just one.

Further, if you look at Ken Shirriff's post about the control PLA, you'll see that Acorn would have had to make the control PLA more complex to handle this - no instruction needs more than 4 rows in the PLA in the current setup, allowing you to use 2 bits to track your position in the PLA sequence, but a compare-and-branch could need 5 rows (because it combines the 2 rows of "data processing, register, shift by register" with the three rows of branch).

On the gain side, you're saving 4 bytes of memory as compared to two instructions. However, there's no time saving in the taken case (since the branch is already in the pipeline, ready to execute), and there's only a one-instruction saving in the not-taken case (since the branch doesn't take a pipeline slot any more, so you move straight to the next instruction). To implement this instruction without making the control PLA sequencing more complex for all instructions would need you to to prohibit the shifted register forms in the compare part (so either a straight register-register compare, or register-immediate, but not register-shifted register comparisons), and the instruction doesn't save enough to make it worth having a more complex control PLA just for this case.

The result is an instruction that has a very tiny value (saves 1 instruction's space and execution time in the not-taken case), but a lot of costs, for a case that we can assume didn't come up that often in Acorn's simulations (branch not taken, and branch target has enough instructions that you can't inline the branch target via conditional execution).

Finally, it's worth recalling that Acorn mostly programmed in assembly or BBC BASIC in the ARM1/ARM2/ARM3 era. They made heavy use of conditional execution, and did use tricks like executing a couple of instructions conditionally between the flag set and the branch, or having multiple branches with different conditions after a single compare. and to return from subroutine conditionally instead of branching, sometimes using multiple comparisons with conditional execution before the conditional return. All of these tricks don't work with a compare-and-branch, and thus make the pressure to have it go down.

Answer 2

Remember that classic AArch32 code has conditional execution of most instructions, which more or less demands a condition code register in simple implementations. Once the ARM designers had included those things, compare-and-branch instructions would likely have seemed like unnecessary complexity.

They seem to have fully apprehended the RISC principle of simple, fast instructions, but had no ideological attachment to RISC purism. They had a lot of experience with the 6502, a simple 8-bit chip which can be surprisingly fast if used skilfully and tried to apply the lessons they'd learned to the new architecture. That was always intended for commercial application; they were in Cambridge, but they weren't doing an academic project at all.

The ARM designers, primarily Sophie Wilson, were very used to writing tight 6502 code to fit into limited-size ROMs on BBC Micro family machines. They seem to have considered assembly language programming as more important than the designers of the seminal Stanford and Berkley RISCs. Acorn Computers used assembler extensively in the operating systems and BASIC interpreters of the early ARM systems. Those were mostly home/educational computers, very powerful for the era, but not compatible with much else. UNIX was available for some high-end ones, but was expensive and little-used.

ARM conditional execution is relatively easy for humans to use in short and medium-sized passages of assembler code. The conventional wisdom is that it proved much harder for compilers to use effectively, which is part of why it was omitted from AArch64. It was also left out of Thumb, simply because it consumes too much space in 16-bit instructions. Branch predictors were starting to appear when Thumb-1 was released in 1994, and definitely weren't used in the early ARMs.

More about supporting conditional execution (aka predicated execution) can be found in these lecture notes from CMU. Page 16 summarises its pros and cons, under present-day conditions:

Advantages

• Eliminates misprediction of hard-to-predict branches, by eliminating the branches.
• This is good if the (inevitable) useless instruction fetches cost less than a branch.
• Allows instructions to be re-ordered more easily.

Disadvantages

• Pointless for easily predicted branches.
• Doesn't adapt to run-time behaviour like a good branch predictor.
• Wastes time if the useless instruction fetches cost more than a branch.
• Costs valuable space in instructions.

I live in Cambridge, UK, where early ARM development was done, and people here who learned ARM programming in the 1980s and 1990s tend to regard AArch64 as "Not really ARM." This is because it discards so much of the classic ARM design and is much more like the classic American RISCs. Classic ARM was a style of its own, which happened to succeed.

Answer 3

Yes, it would add a cycle.

How do you branch on ARM?

add pc, pc, #8

That's a bit of an over-simplification, but the point is that ARM was meant to be purely orthogonal, that is, the program counter is "just another register" and branches pass through the arithmetic-logic unit (ALU) just like any other instruction.

Since the compare-operation also needs to pass through the ALU and there's only the one ALU, our hypothetical compare-with-branch would need two execute cycles; one to perform the compare (just a subtraction, discarding the result) and one to compute the new PC (just addition of the PC with some offset).

ARM does support this sort of behaviour and has to do this very thing with other instructions.

"A number of ARM instructions cannot be implemented in a single cycle given the limited resources of the ARM1 (i.e., a single ALU and a single shifter). Instructions such as a store STR (store register) requires calculating the effective address before it can store the data. To solve this problem, the ARM1 effectively runs the same instruction through the execute stage two to three times - in the first execute cycle is used to compute the address while the second execute stage the data store."

https://en.wikichip.org/wiki/acorn/microarchitectures/arm1#Multi-Cycle_Instruction

So it certainly could have been done but it would have cost an extra cycle anyway.

Answer 4

The CDC 6400 series of supercomputers, developed by Seymour Cray, are considered some of the earliest RISC-like architectures, having been released in 1964. These used compare-and-branch instructions. (See page 40 of this book.)

The Intel 8051 was a microcontroller of a similar generation (originally in NMOS circa 1980) that implemented a version of compare-and-branch. designed for loops that either increment or decrement and then test a register.

Although I’ve seen analysis of the ARM-1 chip, I don’t know what the specific trade-offs would have been. However, branching on a classic RISC architecture of the 1980s typically added a delay of one clock cycle anyway, and using compare-and-branch might have allowed the CPU to remove condition codes and predication, freeing up some transistors to accelerate branches. At that time, RAM speeds were still keeping up with CPUs, meaning there was only a small branch misprediction penalty, so there would not have been a need for complex branch prediction in lieu of conditional instructions.

I’ve only once or twice found a direct answer by someone who was there for a “Why didn’t they ...?” question. In this case, my understanding is that the drawback of condition codes, that they create false dependencies between instructions, only started to matter for superscalar CPUs (of which the CDC 6x00 series was also one of the first). An in-order CPU with only one ALU, like the ARM-1, would probably have seen no advantage to using compare-and-branch over control codes. By the time a superscalar “ARM” CPU came out, its ISA would no longer be backward-compatible with the ARM-1 anyway.

Answer 5

It's not very RISC purist; the designers seem to have been happy to make an instruction do more than one thing,

Erm, RISC isn't about doing only one thing, RISC is about not doing complex stuff. RISC is not about the instruction set, but simplifying the CPU, as a simple CPU can be speed up much better than a complex.

It is not doing away with powerful operations, but stripping the instruction set of all the stuff that makes CPU construction complex. Foremost of instructions that need long pipelines, like to wait for partial results of an operation, like fetching operands or storing results (or both). The goal is to have an instruction set that can, for the most part, executed with a simple 2-3 stage pipeline without need for logic to handle dependencies.

For example, every instruction (not just branch) is predicated on condition codes; every instruction can optionally shift the output;

All of that are not complex instruction, but application of the VLIW principle. VLIW can easy be seen as the pinnacle of RISC as it does even away with most of the decoding stage in favour of direct control of all available function units.

there are instructions to save and restore multiple registers.

While this is an instruction 'looping' around the registers, it's as well very essential for function and task switching, thus not burdening the transfer of register content with an equal number of instruction fetches makes a huge difference. Such is found in many RISC architectures. RISC is all about improving, not being stupid.

One thing it doesn't have, is compare and branch in one instruction; you need to compare values first (setting a condition code), then branch on that condition code. This is admittedly similar to many early microprocessors, but to my way of thinking, it misses an opportunity when your instruction words are always 32 bits; that's plenty enough bits to specify a pair of registers to compare, and a branch displacement, in one instruction, which would save both cycles and code size.

This is a very CISCy instruction - and an unnecessary one:

• It does not - and CAN not - save execution time, as the second part (branching) is dependent on the first part, so it always needs two cycles (at least)
• To get execution (somewhat) down, it would require another pipeline stage, a branching stage after the operation stage. Worst requirement one can do to a RISC design.
• It would not replace any existing branch or compare, but essentially duplicate those instructions. Rather bloaty, isn't it?
• It would need not only the opcode, registers to compare and target, but additional
  • 4 bits for the condition to check for and
  • 4 bit for an optional Link register
• There is no room
  • CMP already fills all 32 bit with useful values
  • B/BL also uses all 32 bits.

Any instruction of that type could, compared with the existing instructions only provide a reduced functionality for either function, while at the same time not eliminating additional branches for complex conditions, all of that at increased execution time.

In contrast, ARM's use of conditional operation does not only away with very common cases of chained operations but also transforms all basic program flow instructions (Jump/Call/Return) into conditional versions. Very lean.

As above, it wasn't about philosophical purity.

I beg to differ, the original ARM was very much a pure concept - maybe even more pure than many other RISC implementations.

One possibility that occurs to me: maybe with the then-available process technology, it wouldn't be possible to run a pair of values through the ALU, and also branch, in the same time; maybe the comparison would have added a cycle to the time taken for a conditional branch. In that case, squeezing them into one instruction, might have helped code density, but it would have done nothing for speed.

Is that the case? Or was there some other reason for the design as it was?

Compare-And-Branche are ta perfect example of CISC bells and whistles, all created to save a tiny bit of code at high implementation cost. Useful only in very limited cases and when memory was as small as in the 1960s. Exactly the kind of instructions RISC was about to cut away. So why on eath would anyone want to include them?