12 ms·

The lack of condition codes is a big deal for anyone relying on overflow checked arithmetic, like modern safe languages that do this for all integer math by def

The lack of condition codes is a big deal for anyone relying on overflow checked arithmetic, like modern safe languages that do this for all integer math by default, or dynamic languages where it’s necessary for the JIT to speculate that the dynamic “number” type (which in those languages is either like a double or like a bigint semantically) is being used as an integer. RISC-V means three instructions instead of two in the best case. It requires five or more instead of two in bad cases. That’s extremely annoying since these code sequences will be emitted frequently if that’s how all math in the language works. Also worth noting, since this always comes up, that these things are super hard for a compiler to optimize away. JSC tries very aggressively but only succeeds a minority of the time (we have a backwards abstract interpreter based on how values are used, a forward interpreter that uses a simplified octagon domain to prove integer ranges, and a bunch of other things - and it’s not enough). So, even with very aggressive compilers you will often emit sequences to check overflow. It’s ideal if this is just a branch on a flag because this maximizes density. Density is especially important in JITs; more density means not just better perf but better memory usage since JITed instructions use dirty memory.

jhallenworld 6y ago
Maybe overflow checking could included as an ISA extension. If it is included, what is the least impactful design? Overflow is part of the result, so maybe include extra bits to each register that can be arithmetic destination. These bits are not included in moves, but could be tested with new instructions. Another way that avoids flags is new arithmetic instructions: add but jump on overflow. Maybe this is reduced to add and skip next instruction except for overflow, but maybe things are simplified if the only allowed next instruction is a jump, so the result is a single longer instruction.
- pizlonator 6y ago
  The best design is control bits which RISC-V doesn’t have but x86 and ARM do have. The best design is part of the core ISA and not and extension since overflow checking is fundamental to modern languages.
  - rwmj 6y ago
    You need to either write a paper about this or produce some evidence.
    - pizlonator 6y ago
      I don’t need to do anything. You’re welcome not to take my advice. :-) If you doubt that dynamic languages are using overflow checking in the way that I describe then it’s not because of lack of papers on the subject.
  - wbl 6y ago
    Control bits as in ARM and x86 force serialization of arithmetic due to the RW dependency in every instruction on that bit. There are some tricks but it still needs tracking. For higher order superscalar or out of order processors this gets annoying.
    - pizlonator 6y ago
      I think what you’re saying is basically true but it’s a trade against density. If you did overflow checks rarely then what you say is a very good point indeed. The key thing is just the frequency of this stuff in modern languages.
    - deleted 6y ago
      [deleted]
    - tom_mellior 6y ago
      ARM has separate instruction variants with and without setting of flags. Normally one uses the flag-less versions, so you don't have this problem.
    - CalChris 6y ago
      No. Control bits (status bits, flags, ...) get renamed just as registers get renamed. Basically, if there's a bottleneck to x86 code, Intel has run into it, profiled for it and generally optimized around it both in their microarchitectures and in the their C compiler.
- jhallenworld 6y ago
  After thinking about this some more: I think the extension instruction should work like "slt" (set on less than). So we have "sov"- set if add would overflow: add t2, t1, t0 sov t3, t1, t0 bnez t3, overflow Why this way? "extra bits on destination registers"- this is really flags. The flags have to be preserved during interrupts, so extending the registers is not so easy (I think it just reduces to classic flags). "add but jump on overflow" or "add and skip on no overflow"- I don't like this because you can not break it into separate operations without flags. I think you might have to add hidden flags in a real implementation. An add followed by an sov could be fused, but requires an expensive multi-register write. Fusing maybe could be more likely if the destination is always to a fixed destination register: add t2, t1, t0 sov tflags, t1, t0 bnez tflags, overflow
  - bshanks 6y ago
    If the destination of sov is specified to always be tflags, then you may as well combine add and sov into one instruction, with tflags implicit: addsov t2, t1, t0
zozbot234 6y ago
The RISC-V spec includes recommended code sequences to check for overflow, so that the hardware can potentially use insn fusion as an optimization. The "bad" cases you mention can be a bit clunky, but they should also be rare.
- pizlonator 6y ago
  I’m aware of those sequences and it’s a myth that they will be rare. For dynamic languages they will be super common.
  - brandmeyer 6y ago
    We know the origins of that myth by examining the papers that the RISC-V designers wrote. They got a C compiler back-end working and didn't incorporate any other languages in their benchmarking corpus.
    - pizlonator 6y ago
      That’s my suspicion too! I don’t think these folks have seen what modern languages do.
    - convolvatron 6y ago
      C really did screw things up by just refusing to address overflow in any form, didn't it
      - brandmeyer 6y ago
        I don't think C screwed up. C's objective was to standardize a set of practices based on what the hardware of the day was capable of. If they had pessimized performance on one architecture because it failed to provide efficient checked overflow (or any other feature), then C would have never made it to standardization. ISO C is therefore a three-way compromise between three communities: Software authors, compiler authors, and CPU manufacturers. You will naturally end up with some decisions that dissatisfy some members of each.
rwmj 6y ago
The idea is that high end processors will recognise these sequences of instructions and optimize them (something called macro-op fusion). Whether this is a good idea is an open question because we don't yet have such high performance RISC-V chips, but that's what the RISC-V designers are thinking. At the same time it permits very simple implementations which wouldn't be possible if the base instruction set contained every pet instruction that someone thought was a good idea. Note macro op fusion is widely used for other architectures already, particularly ones like x86 where what the processor actually runs looks nothing like the machine code.
- deleted 6y ago
  [deleted]
- pizlonator 6y ago
  Two words: instruction density. It doesn’t matter if they’re fused or not if the reduced instruction density increases memory usage and puts more pressure on I$. Also, I don’t buy the whole fusion argument on the grounds that having to fuse super complex (5 instruction or more) sequences adds enough complexity that you’ve got opportunity cost. Much better for everyone if the CPU doesn’t have to do that fusion. That’s the whole point of good ISA design - to prevent the need for fusing in cases you’re doing something super common.
  - jhallenworld 6y ago
    You need the icache to be post-fusion..
    - bertr4nd 6y ago
      It’s not just the I$ though, it’s the MLC, LLC, and I-TLB. And instruction density at those levels actually matters quite a lot for big binaries (my experience in this regard is with HHVM at FB, but it’s certainly not unique).
      - jhallenworld 6y ago
tom_mellior 6y ago
> JSC [...] a forward interpreter that uses a simplified octagon domain to prove integer ranges Off-topic, but could you point me to more details on this? Someone (else?) recently mentioned octagon analysis in JSC in a HN thread. I grepped through the sources at the time but didn't find any indication that it exists. At least not under the name "octagon".
- pizlonator 6y ago
  I didn’t call it octagon when I wrote it because I didn’t know that I reinvented a shitty/awesome version (shitty because it misses optimization opportunities, awesome because by missing them it converges super fast while still nailing the hard bits). Look at DFGIntegerRangeOptimizationPhase.cpp
bertr4nd 6y ago
I’d be curious to see the instruction sequences for handling overflow without condition codes. I’m not even sure I see how to do it as efficiently as 3 or 5 instructions :-/
- pizlonator 6y ago
  One example of 3 is branching on 32-bit add overflow on a 64-bit cpu where you do a 32-bit add, a 64-bit add, and compare/branch on the result.
brandmeyer 6y ago
> Also worth noting, since this always comes up, that these things are super hard for a compiler to optimize away. JSC tries very aggressively but only succeeds a minority of the time (we have a backwards abstract interpreter based on how values are used, a forward interpreter that uses a simplified octagon domain to prove integer ranges, RISC-V has some closely-related sharp corners in indexed address arithmetic as well. Some choices for the type of the index variable perform much worse on rv64. Consider: an LP64 machine uses 32-bit integers for 'int' and 'unsigned', but 64-bit integers for `long`, `size_t`, `ptrdiff_t` and so on. If you use an array index variable of type `unsigned`, then the compiler must prove that wraparound doesn't happen. That's pretty weird considering that half the point of using unsigned is to elide such proofs of correctness. If it cannot prove the absence of unsigned wraparound, then it will be forced to emit zero-extension sequences prior to using the index variable to generate the addresses. ARMv8 side-steps the whole problem by providing indexed memory addressing modes that include the complete suite of zero and sign extension of a narrow-width index in the load or store instruction itself. So here we have an example of a three-way system engineering choice. - Provide a small amount of hardware that performs the operation on-demand. - Provide new and inventive forms of value-range analysis in the compiler. Despite decades of research into this problem, the world's best solutions still frequently saturate at "the entire width of the type the programmer requested". - Change the habits of the world's C programmers. RISC-V chose options 2 and 3.
- saagarjha 6y ago
  > If you use an array index variable of type `unsigned` This is usually why your array indexing should be done with an iterator or size_t :)
  - kllrnohj 6y ago
    size_t is unsigned.
    - saagarjha 6y ago
      Right, but you don't need to sign extend it.
spacenick88 6y ago
I wonder how this interacts with branch prediction. Since overflows should happen very rarely I guess the branch on overflow should almost always predict as non taken. So wouldn't it be possible to have a "branch if add would overflow" instruction or even canonical sequence that a higher end CPU can completely speculate around and just use speculation rollback if it overflows? I think an important design point here is that the languages that need a lot of dynamic overflow checks are primarily used on beefier CPUs so if you can get around the code size issue, making it performant only on more capable designs is fine since the overflow check will be rare on simpler CPUs.
- pizlonator 6y ago
  I don’t think that beefier cpu and overflow checks are that related. I mean, you’re right, I just want to place some limits on how right you are. 1. Folks totally run JS and other crazy on small CPUs. 2. Other safe languages (rust and swift I think?) also use overflow checks. It’s probably a good thing if those languages get used more on small cpus. 3. The C code that normally runs on small cpus is hella vulnerable today and probably for a long time to come. Compiling with sanitizer flags that turn on overflow checks is a valuable (and oft requested) mitigation. So theres a future where most arithmetic is checked on all cpus and with all languages. And yeah, it’s true that the overflow check is well predicted. And yeah, it’s true that what arm and x86 do here isn’t the best thing ever, just better than risc-v.
  - spacenick88 6y ago
    Yeah I know about 1 e.g. also MicroPython, no idea if that's used outside DIY though. I agree about rust but I would think that with much stronger type safety and static compilation it should be able to remove a lot more of the overflow checks and most that remain would be needed in correct C too. At least that's what I learned from my compilers prof who worked on Ada compilers for many years and that should be quite similar. But maybe that's my biased hope as I really really hate working with dynamic languages.
  - spacenick88 6y ago
    Interestingly it seems rust only does full overflow checking in debug builds: https://huonw.github.io/blog/2016/04/myths-and-legends-about-integer-overflow-in-rust/ https://huonw.github.io/blog/2016/04/myths-and-legends-about...
bumblebritches5 6y ago
One thing that also sucks about RISC-V is that basic bitwise operators aren't in the core ISA; they're an extension.
avianes 6y ago
RISC-V spec is not yet finished. Currently only the most basic extensions are available. But nothing prevents RISC-V from introducing in the future an extension that extends the conditional code or an extension for integer/float overflow.

jhallenworld 6y ago

Maybe overflow checking could included as an ISA extension. If it is included, what is the least impactful design? Overflow is part of the result, so maybe include extra bits to each register that can be arithmetic destination. These bits are not included in moves, but could be tested with new instructions. Another way that avoids flags is new arithmetic instructions: add but jump on overflow. Maybe this is reduced to add and skip next instruction except for overflow, but maybe things are simplified if the only allowed next instruction is a jump, so the result is a single longer instruction.

pizlonator 6y ago
The best design is control bits which RISC-V doesn’t have but x86 and ARM do have. The best design is part of the core ISA and not and extension since overflow checking is fundamental to modern languages.
- rwmj 6y ago
  You need to either write a paper about this or produce some evidence.
  - pizlonator 6y ago
    I don’t need to do anything. You’re welcome not to take my advice. :-) If you doubt that dynamic languages are using overflow checking in the way that I describe then it’s not because of lack of papers on the subject.
- wbl 6y ago
  Control bits as in ARM and x86 force serialization of arithmetic due to the RW dependency in every instruction on that bit. There are some tricks but it still needs tracking. For higher order superscalar or out of order processors this gets annoying.
  - pizlonator 6y ago
    I think what you’re saying is basically true but it’s a trade against density. If you did overflow checks rarely then what you say is a very good point indeed. The key thing is just the frequency of this stuff in modern languages.
  - deleted 6y ago
    [deleted]
  - tom_mellior 6y ago
    ARM has separate instruction variants with and without setting of flags. Normally one uses the flag-less versions, so you don't have this problem.
  - CalChris 6y ago
    No. Control bits (status bits, flags, ...) get renamed just as registers get renamed. Basically, if there's a bottleneck to x86 code, Intel has run into it, profiled for it and generally optimized around it both in their microarchitectures and in the their C compiler.
jhallenworld 6y ago
After thinking about this some more: I think the extension instruction should work like "slt" (set on less than). So we have "sov"- set if add would overflow: add t2, t1, t0 sov t3, t1, t0 bnez t3, overflow Why this way? "extra bits on destination registers"- this is really flags. The flags have to be preserved during interrupts, so extending the registers is not so easy (I think it just reduces to classic flags). "add but jump on overflow" or "add and skip on no overflow"- I don't like this because you can not break it into separate operations without flags. I think you might have to add hidden flags in a real implementation. An add followed by an sov could be fused, but requires an expensive multi-register write. Fusing maybe could be more likely if the destination is always to a fixed destination register: add t2, t1, t0 sov tflags, t1, t0 bnez tflags, overflow
- bshanks 6y ago
  If the destination of sov is specified to always be tflags, then you may as well combine add and sov into one instruction, with tflags implicit: addsov t2, t1, t0

zozbot234 6y ago

The RISC-V spec includes recommended code sequences to check for overflow, so that the hardware can potentially use insn fusion as an optimization. The "bad" cases you mention can be a bit clunky, but they should also be rare.

pizlonator 6y ago
I’m aware of those sequences and it’s a myth that they will be rare. For dynamic languages they will be super common.
- brandmeyer 6y ago
  We know the origins of that myth by examining the papers that the RISC-V designers wrote. They got a C compiler back-end working and didn't incorporate any other languages in their benchmarking corpus.
  - pizlonator 6y ago
    That’s my suspicion too! I don’t think these folks have seen what modern languages do.
  - convolvatron 6y ago
    C really did screw things up by just refusing to address overflow in any form, didn't it
    - brandmeyer 6y ago
      I don't think C screwed up. C's objective was to standardize a set of practices based on what the hardware of the day was capable of. If they had pessimized performance on one architecture because it failed to provide efficient checked overflow (or any other feature), then C would have never made it to standardization. ISO C is therefore a three-way compromise between three communities: Software authors, compiler authors, and CPU manufacturers. You will naturally end up with some decisions that dissatisfy some members of each.

rwmj 6y ago

The idea is that high end processors will recognise these sequences of instructions and optimize them (something called macro-op fusion). Whether this is a good idea is an open question because we don't yet have such high performance RISC-V chips, but that's what the RISC-V designers are thinking. At the same time it permits very simple implementations which wouldn't be possible if the base instruction set contained every pet instruction that someone thought was a good idea. Note macro op fusion is widely used for other architectures already, particularly ones like x86 where what the processor actually runs looks nothing like the machine code.

deleted 6y ago
[deleted]
pizlonator 6y ago
Two words: instruction density. It doesn’t matter if they’re fused or not if the reduced instruction density increases memory usage and puts more pressure on I$. Also, I don’t buy the whole fusion argument on the grounds that having to fuse super complex (5 instruction or more) sequences adds enough complexity that you’ve got opportunity cost. Much better for everyone if the CPU doesn’t have to do that fusion. That’s the whole point of good ISA design - to prevent the need for fusing in cases you’re doing something super common.
- jhallenworld 6y ago
  You need the icache to be post-fusion..
  - bertr4nd 6y ago
    It’s not just the I$ though, it’s the MLC, LLC, and I-TLB. And instruction density at those levels actually matters quite a lot for big binaries (my experience in this regard is with HHVM at FB, but it’s certainly not unique).
    - jhallenworld 6y ago

tom_mellior 6y ago

> JSC [...] a forward interpreter that uses a simplified octagon domain to prove integer ranges Off-topic, but could you point me to more details on this? Someone (else?) recently mentioned octagon analysis in JSC in a HN thread. I grepped through the sources at the time but didn't find any indication that it exists. At least not under the name "octagon".

pizlonator 6y ago
I didn’t call it octagon when I wrote it because I didn’t know that I reinvented a shitty/awesome version (shitty because it misses optimization opportunities, awesome because by missing them it converges super fast while still nailing the hard bits). Look at DFGIntegerRangeOptimizationPhase.cpp

bertr4nd 6y ago

I’d be curious to see the instruction sequences for handling overflow without condition codes. I’m not even sure I see how to do it as efficiently as 3 or 5 instructions :-/

pizlonator 6y ago
One example of 3 is branching on 32-bit add overflow on a 64-bit cpu where you do a 32-bit add, a 64-bit add, and compare/branch on the result.

brandmeyer 6y ago

> Also worth noting, since this always comes up, that these things are super hard for a compiler to optimize away. JSC tries very aggressively but only succeeds a minority of the time (we have a backwards abstract interpreter based on how values are used, a forward interpreter that uses a simplified octagon domain to prove integer ranges, RISC-V has some closely-related sharp corners in indexed address arithmetic as well. Some choices for the type of the index variable perform much worse on rv64. Consider: an LP64 machine uses 32-bit integers for 'int' and 'unsigned', but 64-bit integers for `long`, `size_t`, `ptrdiff_t` and so on. If you use an array index variable of type `unsigned`, then the compiler must prove that wraparound doesn't happen. That's pretty weird considering that half the point of using unsigned is to elide such proofs of correctness. If it cannot prove the absence of unsigned wraparound, then it will be forced to emit zero-extension sequences prior to using the index variable to generate the addresses. ARMv8 side-steps the whole problem by providing indexed memory addressing modes that include the complete suite of zero and sign extension of a narrow-width index in the load or store instruction itself. So here we have an example of a three-way system engineering choice. - Provide a small amount of hardware that performs the operation on-demand. - Provide new and inventive forms of value-range analysis in the compiler. Despite decades of research into this problem, the world's best solutions still frequently saturate at "the entire width of the type the programmer requested". - Change the habits of the world's C programmers. RISC-V chose options 2 and 3.

saagarjha 6y ago
> If you use an array index variable of type `unsigned` This is usually why your array indexing should be done with an iterator or size_t :)
- kllrnohj 6y ago
  size_t is unsigned.
  - saagarjha 6y ago
    Right, but you don't need to sign extend it.

spacenick88 6y ago

I wonder how this interacts with branch prediction. Since overflows should happen very rarely I guess the branch on overflow should almost always predict as non taken. So wouldn't it be possible to have a "branch if add would overflow" instruction or even canonical sequence that a higher end CPU can completely speculate around and just use speculation rollback if it overflows? I think an important design point here is that the languages that need a lot of dynamic overflow checks are primarily used on beefier CPUs so if you can get around the code size issue, making it performant only on more capable designs is fine since the overflow check will be rare on simpler CPUs.

pizlonator 6y ago
I don’t think that beefier cpu and overflow checks are that related. I mean, you’re right, I just want to place some limits on how right you are. 1. Folks totally run JS and other crazy on small CPUs. 2. Other safe languages (rust and swift I think?) also use overflow checks. It’s probably a good thing if those languages get used more on small cpus. 3. The C code that normally runs on small cpus is hella vulnerable today and probably for a long time to come. Compiling with sanitizer flags that turn on overflow checks is a valuable (and oft requested) mitigation. So theres a future where most arithmetic is checked on all cpus and with all languages. And yeah, it’s true that the overflow check is well predicted. And yeah, it’s true that what arm and x86 do here isn’t the best thing ever, just better than risc-v.
- spacenick88 6y ago
  Yeah I know about 1 e.g. also MicroPython, no idea if that's used outside DIY though. I agree about rust but I would think that with much stronger type safety and static compilation it should be able to remove a lot more of the overflow checks and most that remain would be needed in correct C too. At least that's what I learned from my compilers prof who worked on Ada compilers for many years and that should be quite similar. But maybe that's my biased hope as I really really hate working with dynamic languages.
- spacenick88 6y ago
  Interestingly it seems rust only does full overflow checking in debug builds: https://huonw.github.io/blog/2016/04/myths-and-legends-about-integer-overflow-in-rust/ https://huonw.github.io/blog/2016/04/myths-and-legends-about...

bumblebritches5 6y ago

One thing that also sucks about RISC-V is that basic bitwise operators aren't in the core ISA; they're an extension.

avianes 6y ago

RISC-V spec is not yet finished. Currently only the most basic extensions are available. But nothing prevents RISC-V from introducing in the future an extension that extends the conditional code or an extension for integer/float overflow.