32 ms·

Fairly lame article (not wrong, but stuff people following the topic have seen before), and I'd still like to hear about integer overflow detection. If the flo

Fairly lame article (not wrong, but stuff people following the topic have seen before), and I'd still like to hear about integer overflow detection. If the floating point extension is able to do IEEE 754 condition codes including overflow detection, why can't the integer unit do something similar?

FullyFunctional 5y ago
This comes up a lot and I'm sympathetic to your plea, really (I enjoy fantasizing about a different reality where CPUs weren't just "machines to run C programs"), but in computer architecture, what really matters for one application or a class of applications might not be important when viewed across millions of programs. The fact is that integer operations and floating point are two completely different beasts, so much so that we have different benchmark suites for each. Integer operations are critically latency sensitive and bagging on extra semantics doesn't come for free and for most code this would be a tax. The "overflow bit" represents an implicit result that would have to be threaded around (I'm assuming that you aren't asking for exceptions which literally nobody wants). For FP we do that, but the cost and latency of FP ops is already high so it doesn't hurt quite as much. The RISC-V spec [1] (which I assume you have seen) already discusses all these trade offs: "We did not include special instruction-set support for overflow checks on integer arithmetic operations in the base instruction set, as many overflow checks can be cheaply implemented using RISC-V branches. Overflow checking for unsigned addition requires only a single additional branch instruction after the addition: add t0, t1, t2 bltu t0, t1, overflow For signed addition, if one operand’s sign is known, overflow checking requires only a single branch after the addition: addi t0, t1, +imm blt t0, t1, overflow This covers the common case of addition with an immediate operand. For general signed addition, three additional instructions after the addition are required, leveraging the observation that the sum should be less than one of the operands if and only if the other operand is negative. add t0, t1, t2 slti t3, t2, 0 slt t4, t0, t1 bne t3, t4, overflow In RV64I, checks of 32-bit signed additions can be optimized further by comparing the results of ADD and ADDW on the operands." I do think that it might have been worth adding an single instruction version for the last one (excluding the branch), but I'm not aware of it getting accepted. [1] https://github.com/riscv/riscv-isa-manual https://github.com/riscv/riscv-isa-manual
- adrian_b 5y ago
  Generating the overflow bit and storing it adds a completely negligible cost to a 64-bit adder, so touting this as a cost saving measure is just a lie, even if indeed this claim has always been present in the RISC-V documentation. Most real cases of overflow checking are of the last type. Tripling the number of instructions over a bad ISA that lacks overflow exceptions, like unfortunately almost all currently popular ISAs are, or quadrupling the number of instructions over a traditional ISA with overflow exceptions is a totally unacceptable cost. The claim that providing overflow exceptions for integer addition might be too expensive can be easily countered by the fact that generating exceptions on each instruction is not the only way to guarantee that overflows do not happen. It is enough to store 2 overflow flags, 1 flag with the result of the last operation and 1 sticky flag that is set by any overflow and is reset only by a special instruction. Having the sticky flag allows zero-overhead overflow checking for most arithmetic instructions, because it can be tested only once after many operations, e.g. at a function exit. The cost of implementing the 2 overflow bits is absolutely negligible, 2 gates and 2 flip-flops. Much more extra hardware is needed for decoding a few additional instructions for flag testing and clearing, but even that is a negligible cost compared with a typical complete RISC-V implementation. Not providing such a means of reliable and cheap overflow detection is just stupid and it is an example of hardware design disconnected from the software design for the same device. The early RISC theory was to select the features that need to be implemented in hardware by carefully examining the code generated by compilers for representative useful programs. The choices made for the RISC-V ISA, e.g. the omission of both the most frequently required addressing modes and of the overflow checking. proves that the ISA designers either have never applied the RISC methodology, or they have studied only examples of toy programs, which are allowed to provide erroneous results.
  - ajb 5y ago
    The extra expense is not the generation of the overflow bit, but the infrastructure needed to support a flags register, or for every instruction to be able to generate an exception. On a simple processor like a microcontroller this doesn't cost much, but it's severely hampers a superscalar or out of order processor, as it can't work out very easily which instructions can be run in parallel or out of order. The clean solution from a micro architectural point of view would be to have an overflow bit (or whatever flags you wanted) in every integer register. But that's an expense most don't want to pay.

FullyFunctional 5y ago

This comes up a lot and I'm sympathetic to your plea, really (I enjoy fantasizing about a different reality where CPUs weren't just "machines to run C programs"), but in computer architecture, what really matters for one application or a class of applications might not be important when viewed across millions of programs. The fact is that integer operations and floating point are two completely different beasts, so much so that we have different benchmark suites for each. Integer operations are critically latency sensitive and bagging on extra semantics doesn't come for free and for most code this would be a tax. The "overflow bit" represents an implicit result that would have to be threaded around (I'm assuming that you aren't asking for exceptions which literally nobody wants). For FP we do that, but the cost and latency of FP ops is already high so it doesn't hurt quite as much. The RISC-V spec [1] (which I assume you have seen) already discusses all these trade offs: "We did not include special instruction-set support for overflow checks on integer arithmetic operations in the base instruction set, as many overflow checks can be cheaply implemented using RISC-V branches. Overflow checking for unsigned addition requires only a single additional branch instruction after the addition: add t0, t1, t2 bltu t0, t1, overflow For signed addition, if one operand’s sign is known, overflow checking requires only a single branch after the addition: addi t0, t1, +imm blt t0, t1, overflow This covers the common case of addition with an immediate operand. For general signed addition, three additional instructions after the addition are required, leveraging the observation that the sum should be less than one of the operands if and only if the other operand is negative. add t0, t1, t2 slti t3, t2, 0 slt t4, t0, t1 bne t3, t4, overflow In RV64I, checks of 32-bit signed additions can be optimized further by comparing the results of ADD and ADDW on the operands." I do think that it might have been worth adding an single instruction version for the last one (excluding the branch), but I'm not aware of it getting accepted. [1] https://github.com/riscv/riscv-isa-manual https://github.com/riscv/riscv-isa-manual

adrian_b 5y ago
Generating the overflow bit and storing it adds a completely negligible cost to a 64-bit adder, so touting this as a cost saving measure is just a lie, even if indeed this claim has always been present in the RISC-V documentation. Most real cases of overflow checking are of the last type. Tripling the number of instructions over a bad ISA that lacks overflow exceptions, like unfortunately almost all currently popular ISAs are, or quadrupling the number of instructions over a traditional ISA with overflow exceptions is a totally unacceptable cost. The claim that providing overflow exceptions for integer addition might be too expensive can be easily countered by the fact that generating exceptions on each instruction is not the only way to guarantee that overflows do not happen. It is enough to store 2 overflow flags, 1 flag with the result of the last operation and 1 sticky flag that is set by any overflow and is reset only by a special instruction. Having the sticky flag allows zero-overhead overflow checking for most arithmetic instructions, because it can be tested only once after many operations, e.g. at a function exit. The cost of implementing the 2 overflow bits is absolutely negligible, 2 gates and 2 flip-flops. Much more extra hardware is needed for decoding a few additional instructions for flag testing and clearing, but even that is a negligible cost compared with a typical complete RISC-V implementation. Not providing such a means of reliable and cheap overflow detection is just stupid and it is an example of hardware design disconnected from the software design for the same device. The early RISC theory was to select the features that need to be implemented in hardware by carefully examining the code generated by compilers for representative useful programs. The choices made for the RISC-V ISA, e.g. the omission of both the most frequently required addressing modes and of the overflow checking. proves that the ISA designers either have never applied the RISC methodology, or they have studied only examples of toy programs, which are allowed to provide erroneous results.
- ajb 5y ago
  The extra expense is not the generation of the overflow bit, but the infrastructure needed to support a flags register, or for every instruction to be able to generate an exception. On a simple processor like a microcontroller this doesn't cost much, but it's severely hampers a superscalar or out of order processor, as it can't work out very easily which instructions can be run in parallel or out of order. The clean solution from a micro architectural point of view would be to have an overflow bit (or whatever flags you wanted) in every integer register. But that's an expense most don't want to pay.