6 ms·

RISC-V designers optimized for C and found overflow flag isn't used much and got rid of it. It was the wrong choice: overflow flag is used a lot for JavaScript

RISC-V designers optimized for C and found overflow flag isn't used much and got rid of it. It was the wrong choice: overflow flag is used a lot for JavaScript and any language with arbitrary precision integer (including GMP, the topic of OP).

zozbot234 5y ago
They provide recommended insn sequences for overflow checking as commentary to the ISA specification, and this enables efficient implementation in hardware.
- throwaway81523 5y ago
  > They provide recommended insn sequences for overflow checking as commentary to the ISA specification, and this enables efficient implementation in hardware. I would like to see some benchmarks of this efficient implementation in hardware, even simulated hardware, compared against conventional architectures. Even for C, it's a recurring source of bugs and vulnerabilities that int overflow goes undetected. What we really need is an overflow trap like the one in IEEE floating point. RISC-V went the opposite direction.
- adrian_b 5y ago
  Any hardware adder provides almost for free the overflow detection output (at less than the cost of an extra bit, so less than 1/64 of a 64-bit adder). So anyone who thinks about an efficient hardware implementation would expose the overflow bit to the software. A hardware implementation that requires multiple additions to provide the complete result of a single addition can be called in many ways, but certainly not "efficient".
  - mlyle 5y ago
    > A hardware implementation that requires multiple additions to provide the complete result of a single addition can be called in many ways, but certainly not "efficient". 1. There's not multiple additions in the recommended sequences. Unsigned is add,bltu; Signed with one known sign is add, blt; Signed in general is add, slt, slti, bne. 2. These instruction sequences are specified so that an instruction decoder can treat these sequences following the add as a "very wide" instruction specifying to check an overflow flag, if a hardware implementation so chooses.
    - adrian_b 5y ago
      Even if a dedicated comparator can be a little cheaper than a full adder, all CPUs already have full adders/subtractors, so all the comparisons are done by subtraction in the same adder/subtractor. So your recommended sequence has 4 additions done in the adder/subtractor of the ALU, because all comparisons, including the compare-and-branch instructions, count as additions, from the point-of-view of the energy consumption and execution time.
      - mlyle 5y ago
        > So your recommended sequence has 4 additions done in the adder/subtractor of the ALU, because all comparisons, including the compare-and-branch instructions, count as additions, from the point-of-view of the energy consumption and execution time. For the signed overflow case, with compile-time unknown value added, if the processor doesn't do anything fancy to elide the recommended sequence (fusion or substitution of operation) only. Not for the other two cases, and not with fusion.
  - ansible 5y ago
    > Any hardware adder provides almost for free the overflow detection output (at less than the cost of an extra bit, so less than 1/64 of a 64-bit adder). So anyone who thinks about an efficient hardware implementation would expose the overflow bit to the software. Ah, but where you do put that bit that you got for free? A condition codes register, global to the processor / core state? That worked terrific for single-issue microcontrollers back in the 1980's. Now you need register renaming, and all the expensive logic around that to track which overflow bit is following which previous add operation. That's what's being done now for old ISAs, and it generally disliked for several reasons (complexity being chief among them). Well, you could stuff that bit into another general purpose register, but then you kind of want to specify 4 registers for the add command. Now where are the bits to encode a 4th register in a new instruction format. RISC-V has room to grow for extensions, but another 5 bits for another register is a big ask.
    - imtringued 5y ago
      I have no clue about flags but why not just store the flags with the register? Each register would have 32+r bits where r is the number of flags.
      - ansible 5y ago
        > I have no clue about flags but why not just store the flags with the register? Each register would have 32+r bits where r is the number of flags. That sort of design can be done, but that just pushes the problem around. Let's look at the original ARM 64 bit code: adds x12, x6, x10 adcs x13, x7, x11 The second add with carry uses the global carry bit, it isn't passed as an argument to the adcs instruction. So if you store the carry bit with the x12 register, you would then need to specify x12 in the adcs instruction on the next line. So you need a new instruction format for adcs that can specify four registers. You could change the semantics, where the add instructions use one register as the source and the destination, like on x86-64, but that's a whole 'nother discussion on why that is and isn't done on various architectures.
kannanvijayan 5y ago
It kind of chafed when I excitedly read the ISA docs and found that overflow testing was cumbersome. That said, I think it's less of an issue these days for JS implementors in particular. It might have mattered more back in the day when pure JS carried a lot of numeric compute load and there weren't other options. These days it's better to stow that compute code in wasm and get predictable reliable performance and move on. The big pain points in perf optimization for JS is objects and their representation, functions and their various type-specializations. Another factor is that JS impls use int32s as their internal integer representation, so there should be some relatively straightforward approach involving lifting to int64s and testing the high half for overflow. Still kind of cumbersome. There are similar issues in existing ISAs. NaN-boxing for example uses high bits to store type info for boxed values. Unboxing boxed values on amd64 involves loading an 8-byte constant into a free register and then using that to mask out the type. The register usage is mandatory because you can't use 64-bit values as immediates. I remember trying to reduce code size and improve perf (and save a scratch register) by turning that into a left-shift right-shift sequence involving no constants, but that led to the code executing measurably slower as it introduced data dependencies.
- formerly_proven 5y ago
  > It kind of chafed when I excitedly read the ISA docs and found that overflow testing was cumbersome. It just feels backwards to me to increase the cost of these checks in a time where we have realized that unchecked arithmetic is not a good idea in general.
  - kannanvijayan 5y ago
    I think I agree it was a mistake/wart. I can understand the frustration of the GMP dev in the text - they get hit hard by this. The omission feels arbitary and capricious and a bit ideologically motivated. The defense of the choice seems like post-hoc rationalization. RiscV looks like a nice ISA otherwise. I wouldn't be surprised if it was eventually extended to add a set of variant instructions that wrote flags to an explicitly specified register.
roca 5y ago
Also Rust applications are increasingly going to be built with integer overflow checking enabled, e.g. Android's Rust components are going to ship with integer overflow checking. And unlike say GMP, that poses a potential code density problem because we're not talking about inner loops that can be effectively cached, it's code bloat smeared across the entire binary.
- rstuart4133 5y ago
  > it's code bloat smeared across the entire binary. That's probably not true in the usual case. Most arch's are 64 bit nowadays. If you are working on something that isn't 64 it you are doing embedded stuff, and different rules and coding standards apply (like using embedded assembler rather than pure C or Rust). In 64 bit environments only pointers are 64 bits by default, almost all integers remain 32 bit. Checking for a 32 bit overflow on a 64 bit RISC-V machine takes the same amount of instructions as everywhere else. Also, in C integers are very common because they are used as iterators (ie, stepping along things in for loops). But in Rust, iterators replace integers for this sort thing. There still is an integer under the hood of course, and perhaps it will be bounds checked. But that is bounds checked - not overflow checked. 2^32 is far larger than most data structures in use. Which means while there may be some code bloat, the lack full 64 integers in your average Rust problem means it's going to be pretty rare. Since I'm here, I'll comment on the article. It's true the lack of carry will make adds a little more difficult for multi precision libraries. But - I've written a multi precision library, and the adds are the least of your problems. Adds just generate 1 bit of carry. Multiplies generate an entire word of carry, and they almost a common as adds. Divides are no so common fortunately, but the execution time of just one divide will make all the overhead caused by a lack of carry look like insignificant noise. I'm no CPU architect, but I gather the lack of carry and overflow bits makes life a little easier for just about every instruction other than adc and jo. If that's true, I'd be very surprised if the cumulative effect of those little gains didn't completely overwhelm the wins adc and jo gets from having them. Have a look at the code generated by a compiler some time. You will have a hard time spotting the adc's and jo's because there are bugger all of them.
  - roca 5y ago
aidenn0 5y ago
Over just the time I've been aware of things, there's been a constant positive feedback loop of "checked overflow isn't used by software, so CPU designers make it less performant" followed by "Checked overflow is less performant so software uses it less." I wish there was a way out. Language features are also often implemented at least partly because they can be done efficiently on the premiere hardware for the language. Then new hardware can make such features hard to implement. WASM implemented return values in a way that was different from register hardware, and it makes efficient codegen of Common Lisp more challenging. This was brought to the attention of the committee while WASM was still in flux, and they (perhaps rightfully) decided CL was insufficiently important to change things. I'm sure that people brought up the overflow situation to the RISC-V designers, and it was similarly dismissed. It's just unfortunate that legacy software is such a big driver of CPU features as that's a race towards lowest-common-denominator hardware.
- titzer 5y ago
  > WASM implemented return values in a way that was different from register hardware, and it makes efficient codegen of Common Lisp more challenging. This was brought to the attention of the committee while WASM was still in flux, and they (perhaps rightfully) decided CL was insufficiently important to change things. Can you refresh my memory here? What exactly is different about Wasm return values than any other function-oriented language?
  - throwaway81523 5y ago
    Common Lisp supports multiple value returns, which C doesn't. Go sort of does, though.
    - titzer 5y ago
      Wasm supports multiple value returns.
  - aidenn0 5y ago
    Common Lisp will often have auxiliary return values that are often not needed (e.g. the mathematical floor function returns the remainder as a second value). Unused extra values are silently discarded. So you can do, for example (+ (floor x y) z) without worrying about the second value to floor. A lisp compiler for a register machine will usually return the first N values in registers (for some small value of N), so the common case of using only the primary return value generates exactly the same code regardless of how many values are actually returned. I don't remember the details, but however wasm happens to implement multiple return values, you can't just pretend that a function that returns 2 values only returns one.
audunw 5y ago
Which is exactly the right trade-off for embedded CPUs, where RISC-V is most popular right now. If desktop/server-class RISC-V CPUs become more common, it's not unreasonable to think they'll add an extension that covers the needs of managed/higher-level languages like RISC-V. Even for server-class CPUs you could argue that you absolutely want this extension to be optional, as you can design more efficient CPUs for datacenters/supercomputers where you know what kind of code you'll be running.
- deleted 5y ago
  [deleted]
wyldfire 5y ago
Is it worth the encoding space to define new ALU instructions with overflow flag semantics? Or could there be an executive format that implies a different mode?

zozbot234 5y ago

They provide recommended insn sequences for overflow checking as commentary to the ISA specification, and this enables efficient implementation in hardware.

throwaway81523 5y ago
> They provide recommended insn sequences for overflow checking as commentary to the ISA specification, and this enables efficient implementation in hardware. I would like to see some benchmarks of this efficient implementation in hardware, even simulated hardware, compared against conventional architectures. Even for C, it's a recurring source of bugs and vulnerabilities that int overflow goes undetected. What we really need is an overflow trap like the one in IEEE floating point. RISC-V went the opposite direction.
adrian_b 5y ago
Any hardware adder provides almost for free the overflow detection output (at less than the cost of an extra bit, so less than 1/64 of a 64-bit adder). So anyone who thinks about an efficient hardware implementation would expose the overflow bit to the software. A hardware implementation that requires multiple additions to provide the complete result of a single addition can be called in many ways, but certainly not "efficient".
- mlyle 5y ago
  > A hardware implementation that requires multiple additions to provide the complete result of a single addition can be called in many ways, but certainly not "efficient". 1. There's not multiple additions in the recommended sequences. Unsigned is add,bltu; Signed with one known sign is add, blt; Signed in general is add, slt, slti, bne. 2. These instruction sequences are specified so that an instruction decoder can treat these sequences following the add as a "very wide" instruction specifying to check an overflow flag, if a hardware implementation so chooses.
  - adrian_b 5y ago
    Even if a dedicated comparator can be a little cheaper than a full adder, all CPUs already have full adders/subtractors, so all the comparisons are done by subtraction in the same adder/subtractor. So your recommended sequence has 4 additions done in the adder/subtractor of the ALU, because all comparisons, including the compare-and-branch instructions, count as additions, from the point-of-view of the energy consumption and execution time.
    - mlyle 5y ago
      > So your recommended sequence has 4 additions done in the adder/subtractor of the ALU, because all comparisons, including the compare-and-branch instructions, count as additions, from the point-of-view of the energy consumption and execution time. For the signed overflow case, with compile-time unknown value added, if the processor doesn't do anything fancy to elide the recommended sequence (fusion or substitution of operation) only. Not for the other two cases, and not with fusion.
- ansible 5y ago
  > Any hardware adder provides almost for free the overflow detection output (at less than the cost of an extra bit, so less than 1/64 of a 64-bit adder). So anyone who thinks about an efficient hardware implementation would expose the overflow bit to the software. Ah, but where you do put that bit that you got for free? A condition codes register, global to the processor / core state? That worked terrific for single-issue microcontrollers back in the 1980's. Now you need register renaming, and all the expensive logic around that to track which overflow bit is following which previous add operation. That's what's being done now for old ISAs, and it generally disliked for several reasons (complexity being chief among them). Well, you could stuff that bit into another general purpose register, but then you kind of want to specify 4 registers for the add command. Now where are the bits to encode a 4th register in a new instruction format. RISC-V has room to grow for extensions, but another 5 bits for another register is a big ask.
  - imtringued 5y ago
    I have no clue about flags but why not just store the flags with the register? Each register would have 32+r bits where r is the number of flags.
    - ansible 5y ago
      > I have no clue about flags but why not just store the flags with the register? Each register would have 32+r bits where r is the number of flags. That sort of design can be done, but that just pushes the problem around. Let's look at the original ARM 64 bit code: adds x12, x6, x10 adcs x13, x7, x11 The second add with carry uses the global carry bit, it isn't passed as an argument to the adcs instruction. So if you store the carry bit with the x12 register, you would then need to specify x12 in the adcs instruction on the next line. So you need a new instruction format for adcs that can specify four registers. You could change the semantics, where the add instructions use one register as the source and the destination, like on x86-64, but that's a whole 'nother discussion on why that is and isn't done on various architectures.

kannanvijayan 5y ago

It kind of chafed when I excitedly read the ISA docs and found that overflow testing was cumbersome. That said, I think it's less of an issue these days for JS implementors in particular. It might have mattered more back in the day when pure JS carried a lot of numeric compute load and there weren't other options. These days it's better to stow that compute code in wasm and get predictable reliable performance and move on. The big pain points in perf optimization for JS is objects and their representation, functions and their various type-specializations. Another factor is that JS impls use int32s as their internal integer representation, so there should be some relatively straightforward approach involving lifting to int64s and testing the high half for overflow. Still kind of cumbersome. There are similar issues in existing ISAs. NaN-boxing for example uses high bits to store type info for boxed values. Unboxing boxed values on amd64 involves loading an 8-byte constant into a free register and then using that to mask out the type. The register usage is mandatory because you can't use 64-bit values as immediates. I remember trying to reduce code size and improve perf (and save a scratch register) by turning that into a left-shift right-shift sequence involving no constants, but that led to the code executing measurably slower as it introduced data dependencies.

formerly_proven 5y ago
> It kind of chafed when I excitedly read the ISA docs and found that overflow testing was cumbersome. It just feels backwards to me to increase the cost of these checks in a time where we have realized that unchecked arithmetic is not a good idea in general.
- kannanvijayan 5y ago
  I think I agree it was a mistake/wart. I can understand the frustration of the GMP dev in the text - they get hit hard by this. The omission feels arbitary and capricious and a bit ideologically motivated. The defense of the choice seems like post-hoc rationalization. RiscV looks like a nice ISA otherwise. I wouldn't be surprised if it was eventually extended to add a set of variant instructions that wrote flags to an explicitly specified register.

roca 5y ago

Also Rust applications are increasingly going to be built with integer overflow checking enabled, e.g. Android's Rust components are going to ship with integer overflow checking. And unlike say GMP, that poses a potential code density problem because we're not talking about inner loops that can be effectively cached, it's code bloat smeared across the entire binary.

rstuart4133 5y ago
> it's code bloat smeared across the entire binary. That's probably not true in the usual case. Most arch's are 64 bit nowadays. If you are working on something that isn't 64 it you are doing embedded stuff, and different rules and coding standards apply (like using embedded assembler rather than pure C or Rust). In 64 bit environments only pointers are 64 bits by default, almost all integers remain 32 bit. Checking for a 32 bit overflow on a 64 bit RISC-V machine takes the same amount of instructions as everywhere else. Also, in C integers are very common because they are used as iterators (ie, stepping along things in for loops). But in Rust, iterators replace integers for this sort thing. There still is an integer under the hood of course, and perhaps it will be bounds checked. But that is bounds checked - not overflow checked. 2^32 is far larger than most data structures in use. Which means while there may be some code bloat, the lack full 64 integers in your average Rust problem means it's going to be pretty rare. Since I'm here, I'll comment on the article. It's true the lack of carry will make adds a little more difficult for multi precision libraries. But - I've written a multi precision library, and the adds are the least of your problems. Adds just generate 1 bit of carry. Multiplies generate an entire word of carry, and they almost a common as adds. Divides are no so common fortunately, but the execution time of just one divide will make all the overhead caused by a lack of carry look like insignificant noise. I'm no CPU architect, but I gather the lack of carry and overflow bits makes life a little easier for just about every instruction other than adc and jo. If that's true, I'd be very surprised if the cumulative effect of those little gains didn't completely overwhelm the wins adc and jo gets from having them. Have a look at the code generated by a compiler some time. You will have a hard time spotting the adc's and jo's because there are bugger all of them.
- roca 5y ago

aidenn0 5y ago

Over just the time I've been aware of things, there's been a constant positive feedback loop of "checked overflow isn't used by software, so CPU designers make it less performant" followed by "Checked overflow is less performant so software uses it less." I wish there was a way out. Language features are also often implemented at least partly because they can be done efficiently on the premiere hardware for the language. Then new hardware can make such features hard to implement. WASM implemented return values in a way that was different from register hardware, and it makes efficient codegen of Common Lisp more challenging. This was brought to the attention of the committee while WASM was still in flux, and they (perhaps rightfully) decided CL was insufficiently important to change things. I'm sure that people brought up the overflow situation to the RISC-V designers, and it was similarly dismissed. It's just unfortunate that legacy software is such a big driver of CPU features as that's a race towards lowest-common-denominator hardware.

titzer 5y ago
> WASM implemented return values in a way that was different from register hardware, and it makes efficient codegen of Common Lisp more challenging. This was brought to the attention of the committee while WASM was still in flux, and they (perhaps rightfully) decided CL was insufficiently important to change things. Can you refresh my memory here? What exactly is different about Wasm return values than any other function-oriented language?
- throwaway81523 5y ago
  Common Lisp supports multiple value returns, which C doesn't. Go sort of does, though.
  - titzer 5y ago
    Wasm supports multiple value returns.
- aidenn0 5y ago
  Common Lisp will often have auxiliary return values that are often not needed (e.g. the mathematical floor function returns the remainder as a second value). Unused extra values are silently discarded. So you can do, for example (+ (floor x y) z) without worrying about the second value to floor. A lisp compiler for a register machine will usually return the first N values in registers (for some small value of N), so the common case of using only the primary return value generates exactly the same code regardless of how many values are actually returned. I don't remember the details, but however wasm happens to implement multiple return values, you can't just pretend that a function that returns 2 values only returns one.

audunw 5y ago

Which is exactly the right trade-off for embedded CPUs, where RISC-V is most popular right now. If desktop/server-class RISC-V CPUs become more common, it's not unreasonable to think they'll add an extension that covers the needs of managed/higher-level languages like RISC-V. Even for server-class CPUs you could argue that you absolutely want this extension to be optional, as you can design more efficient CPUs for datacenters/supercomputers where you know what kind of code you'll be running.

deleted 5y ago
[deleted]

wyldfire 5y ago

Is it worth the encoding space to define new ALU instructions with overflow flag semantics? Or could there be an executive format that implies a different mode?