15
$\begingroup$

Some CPUs have a flags register (ARM,x86,...), others don't (MIPS,...). What's the advantage of having a CMP instruction to update the flags register followed by a branch instruction instead of using a zero register and conditional branches to check for sign, overflow etc?

$\endgroup$
11
$\begingroup$

In modern micro-architectures with register renaming the implementation cost for flags or not flags is pretty similar. The main difference I can think of is that some flags indicate the characteristics of a value (Is the value negative? Is the value zero? Does the value have even or odd parity?), while some represent an event that occurred during a previous operation (did the add instruction have a carry out or an overflow?) This led to a less-than-ideal situation on the MIPS when you wanted to simulate 64-bit addition on the 32-bit architecture (or 128-bit addition on the 64-bit architecture.) On most architectures with a carry flag there is a special add-with-carry instruction, that includes the carry flag from the previous add instruction. This makes simulating multi-precision arithmetic relatively inexpensive on many architectures with flags registers.

On the flip side, testing an N-bit register for zero or not-zero is actually surprisingly expensive. To test an N-bit register for zero you need to perform an N-bit NOR operation, which requires $O(\log N)$ levels of logic to calculate. On architectures with flags registers the extra logic for the zero/not-zero calculation at the end of the ALU stage can cause the clock to run slower (or force the ALU to have two cycle operations.) For this reason, I think, some architectures, like SPARC had two versions of each arithmetic operation, one that set flags and one that didn't.

But MIPS doesn't save anything here. They just moved the problem somewhere else. On MIPS there is a branch-on-equal instruction. This means that the branch instruction must actually have an ALU stage (including something like a bitwise xor operation followed by a nor to reduce down to the single equal/not-equal bit) before determining which way the branch goes.

The DEC Alpha architecture tried to split the difference by using a trick. DEC Alpha had no flags registers, but also didn't have a branch-on-equal instruction. Instead the branch instructions all look at the state of a single general purpose register. There is branch-on-zero, branch-on-not-zero, branch-on-less-than-zero, etc. The trick is that you can give every general purpose register an extra 65th bit that tells you whether the other 64 bits are all zero or not. This makes it more like having a flags register: all the branch instructions look at a single bit (that is already calculated) to make their decision, but now you are back to figuring out how to calculate that extra zero indicator bit during a normal ALU cycle. (And you still can't do multi-precision arithmetic just by looking at the carry flag from the previous operation.)

$\endgroup$
  • 2
    $\begingroup$ The non-CC setting operations were (from what I understand) a compiler optimization, allowing the compiler to schedule CC-setting instructions early without the value being clobbered by latter instructions. The PowerPC750 placed the condition registers (8 4-bit registers) nearer the front end such that a taken branch hitting the branch target instruction cache and having the condition available early enough could resolve a taken branch without penalty. (AT&T's CRISP also exploited early branch resolution.) The small amount and specialization of CCs makes this more practical. $\endgroup$ – Paul A. Clayton Oct 2 '14 at 3:50
  • $\begingroup$ A detail : All flags calculations are not made equal. Imagine your CPU has the traditional NZVC flags. If all the ALU instructions are allowed to update the flags, you must place flag generation after the adder/subtractor and a few muxes. The Negative flag is easy, it is just the MSB, whereas the Zero flag is expensive and depends on every bit. Now, if you restricts flags to Compare (and bit test) instructions, the Zero flags can be calculated with parallel XORs on the source operands, without waiting for the subtraction' result. Calculating the Z flag after an addition is almost useless. $\endgroup$ – TEMLIB Oct 29 '14 at 23:47
7
$\begingroup$

1 From an ISA perspective

  1. Having test instructions which set only the flags is just a way to reduce the register pressure in register starved architectures. If you have enough registers, just modify one of them and ignore the result. The trick of having a register 0 with input value 0 is just an encoding trick convenient when you have enough registers that fixing one of them to 0 is better than increasing the number of instructions. It is then convenient to use it as a target as well (it reduces the number of false dependencies).

  2. Encoding again. If you encode the condition in jumps, you'll have jumps with 3 operands (the two to be compared and the jump target), two of which you'd like to be immediate values, one you'd like to be as big as possible (jumps have often their own encoding format so that the target can use as many bits as possible). Or you drop possibilities.

  3. Using flags gives you more opportunities to set them. It is not just the comparison operations which can set the flags, but whatever you want. (With the caveat that the more operations you have which set flags, the more careful you have to be to ensure that the last operation which set the flags is the one you want). If you have flags, you are able to test the number of conditions (often 16) multiplied by the number of instructions which are able to set the flags (If you are not using flags, you end up with about as many conditional jumps as you have things to test or there are things you don't allow to test as easily (carry or overflow for instance).

2 From an implementer perspective

  1. Testing flags is easy and can be done quickly. The more complex your test is, the more effect it will have on the cycle time (or the pipeline structure if you are pipelined). That's especially true for simpler implementations, when you get to a high end processor using all the tricks of the book, the effect is pretty minimal.

  2. Having flags means that a lot of instructions have multiple results (the natural result and each of the modified flags). And from a micro-architecture POV, multiple results are bad (you have to keep track of their association). When you have just one set of flags, that introduce dependencies (unneeded if the flag is not then used) you have to handle way or another. Again that's especially true for simpler implementations, when you get to an high end processor using all the tricks of the book, the additional difficulties are dwarfed by the rest of the processor.

$\endgroup$
2
$\begingroup$

On a 32-bit machine, an "add-with-carry" instruction used as part of a multi-precision addition sequence needs to accept 65 bits worth of operands and compute a 33 bits sum. The source-register specifications will identify where 64 operand bits should come from, and the destination-register specification will say where the lower 32 bits of the result should go, but what to do with the "add one extra" operand or the upper bit of the result? Being allowed to specify as part of the instruction where the extra operand should come from and where the extra result bit should go would be moderately useful, but it would generally not be so useful as to justify an extra field in the opcode. Having a fixed "location" to handle the carry flag can be little bit awkward from an instruction-scheduling perspective, but it's a lot cheaper than having additional operand fields, and is much more practical than most other ways of trying to handle multi-precision arithmetic.

If one were trying to design an instruction set to allow multi-precision arithmetic but each instruction were limited to two 32-bit operands and one 32-bit destination operand, one could implement a 64-bit "add" in four instructions: "set r5 to 1 if r0+r2 would carry or zero otherwise; compute r4=r1+r3; compute r5=r4+r5; compute r4=r0+r2", but going beyond that would require three instructions for each additional word. Having a carry flag available as a supplemental source and destination reduces the cost to one instruction per word.

Note, btw, that having an instruction bit control whether the instruction updates the flag register may facilitate out-of-order execution, since instructions which use or modify the flag bits must maintain their sequence relative to each other, but instructions which do neither may be freely rearranged. Given the sequence:

ldr  r0,[r1]
add  r0,r0,r2
eors r4,r5,r6

an execution unit could fairly easily recognize that the third instruction could execute without having to wait for data to be read from [r1], but if the second instruction had been adds r0,r0,r2 that would only be possible if the execution unit could ensure that by the time anything tried to use the flags, the zero flag would hold the value established in the third instruction but the carry flag would hold the value in the second.

$\endgroup$
  • 1
    $\begingroup$ "instruction bit control whether the instruction updates the flag register" : Available for example in PowerPC, SPARC. $\endgroup$ – TEMLIB Feb 9 '15 at 2:03
  • $\begingroup$ MIPS uses "r5=r1+r2; set r6 if r6 is less than r1; r7=r3+r4; r5=R5+R6;". Some SIMD extensions could use comparisons which set all bits to zero or one (i.e., zero or -1 twos complement integer) to find the carry and subtraction to apply the carry. $\endgroup$ – Paul A. Clayton Feb 9 '15 at 11:45
  • $\begingroup$ @PaulA.Clayton: I think you meant "if r5 is less than r1". How would MIPS handle longer math? Would it require three, more than three, or less than three instructions per word? $\endgroup$ – supercat Feb 9 '15 at 14:44
  • $\begingroup$ @supercat Yeah, that should have been "set r6 if r5 is less than r1"! $\endgroup$ – Paul A. Clayton Feb 9 '15 at 18:22
  • $\begingroup$ @PaulA.Clayton: How would one go about adding e.g. two 64-word (2048-bit) numbers on a 32-bit MIPS? Is there any efficient way to handle the carries in and out of the middle stages? $\endgroup$ – supercat Feb 9 '15 at 18:43
0
$\begingroup$

Simple answer ... quick cheap memory operation that requires absolutely no internal buss usage except the instruction itself. It can be used as a stack bool with out a stack or a process bit, with no memory.

$\endgroup$
  • 1
    $\begingroup$ This answer is rather light on detail. Long answers aren't necessarily required but something more fleshed-out would be a distinct improvement. $\endgroup$ – David Richerby Jul 21 '15 at 21:24
  • $\begingroup$ setting a flag or compare a flag value is a single instruction without any other information in the form of arguments that would be included in the assembly code. flags are also a result of uprocessor operation or test and can be efficiently used to branch. they are the actual bit that is toggled or set when two values are compared in registers. $\endgroup$ – SkipBerne Jul 22 '15 at 18:53

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.