Hacker News Reader

Comment by Taniwha | Hacker News Reader

So this is one tiny corner of the ISA, not something that makes ALL instruction sequences longer - essentially RISCV has no condition codes (they're a bit of an architectural nightmare for everyone doing any more than the simplest CPUs, they make every instruction potentially have dependencies or anti-dependencies with every other).

It's a trade off - and the one that's been made is one that makes it possible to make ALL instructions a little faster at the expense of one particular case that isn't used much - that's how you do computer architecture, you look at the whole, not just one particular case

RISCV also specifies a 128-bit variant that is of course FASTER than these examples

View on HN

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).

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

> 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.

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".

> 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.

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.

> 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.

> 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.

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.

> 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.

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.

> 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.

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.

Shouldn't settle for less than interrupt on overflow tbh.

That would probably be the easiest to add, wouldn't it?

It should be, but they never do. It's really important for HPC workloads.

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.

Yeah but the code required for an overflow check is just one extra instruction (3 rather than 2)

For generalised signed addition, the overhead is 3 instructions per addition. It can be one in specific contexts where more is known about the operands (e.g. addition of immediates).

It’s always 1 in x64/ARM64 as they have built-in support for overflow.

you have to include the branch instruction too in any comparison

In x86 it is still one instruction: jc or jo after an addition.

And in RISC-V it's a "BLT sum,summand" after an unsigned addition, and a single branch instruction after a signed addition if you know the sign of one of them e.g. adding or subtracting a constant.

built-in support for overflow is not really builtin. There's only adc, but the C library has no such function, and compilers only got them added a few years ago. Almost nobody uses them, as they introduce a dependency. Most workaround that in much slower ways, worse than RISC-V

> 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.

It's a good observation that checking for 32-bit overflow is not too bad, but...

> In 64 bit ... almost all integers remain 32 bit.

I don't believe this is true for Rust, even if we exclude index integers in iterators because we think those overflow checks can be optimized out. Certainly in my Rust project (Pernosco) there is a lot of manipulation of 64-bit integer data.

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.

> 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?

Common Lisp supports multiple value returns, which C doesn't. Go sort of does, though.

Wasm supports multiple value returns.

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.

Return values are pushed onto the Wasm operand stack in left-to-right order. Engines use registers for params/returns up to a point in optimized code and then spill to the stack. So at the call site you can just drop the return values you don't want and should end up with machine code that does exactly what you want.

wasm functions must have a fixed number of results[1]. Lisp functions may have variadic results. A wasm function call must explicitly pop every result off of the stack[2].

These rules add significant overhead to implementing:

  (foo (bar))

Which calls foo with just the first result of bar, and the number of results yielded by bar is possibly unknown.

In psuedo-assembly for a register machine, implementing this is roughly:

  CALL bar
  MOVE ResultReg1 -> ArgumentReg1
  CALL foo

And this works regardless of how many values the function bar happens to return[3].

Any implementation that is correct for any number of results of "bar" will be slow for the common case of bar yielding one or two results.

1: https://webassembly.github.io/spec/core/syntax/types.html#sy...

2: https://webassembly.github.io/spec/core/exec/instructions.ht...

3: Showing only the caller side of things, when the caller doesn't care about extra values hides some complexity of implementation of returning values because you also need to be able to detect at run-time how many values were actually returned. e.g. SBCL on x86 uses a condition flag to indicate if there are multiple values, because branching on a condition flag lets you handle the only-1 value case efficiently.

Ok, I see. Yes, there is some overhead if you want not just multiple returns, but variadic returns. Most virtual machines and programming languages make this fairly inefficient because of fixed arity of returns. AFAICT, targeting anything other than machine code is going to cost you in this case.

There's a blog page somewhere that's a rant for implementing saturating and other arithmetic modes. Would be a really good idea.

Main one is interrupt on overflow.

I agree. A lot of software only wants protection against overflows but does not depend on them for functionality. If something wants to read out the carry bit, it should be explicit and although it is unfortunate, indicating that requires a full instruction.

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.

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?

This isn't an isolated case. RISC-V makes the same basic tradeoff (simplicity above all else) across the board. You can see this in the (lack of) addressing modes, compare-and-branch, etc.

Where this really bites you is in workloads dominated by tight loops (image processing, cryptography, HPC, etc). While a microarchitecture may be more efficient thanks to simpler instructions (ignoring the added complexity of compressed instructions and macro-fusion, the usual suggested fixes...), it's not going to be 2-3x faster, so it's never going to compensate for a 2-3x larger inner loop.

For those use cases you typically have specialised hardware or an FPGA.

So when h266 or whatever comes out you can't watch video anymore because your cpu can't decode it in software even if it tried?

An FPGA can be reprogrammed, and we do really do this for standards with better longevity than video standards (e.g. cryptographic ones like AES and SHA). For standards like video codecs, we just use GPUs instead, which I assume is what OP had in mind for "specialized hardware" (specialization can still be pretty general :-)).

Hardware video decoding is done by a single-purpose chip on the graphics card (or dedicated hardware inside the GPU), not via software running on the GPU. Adding support for a new video codec requires buying a new video card which supports that codec.

SystemC bloat will require you to upgrade to a bigger FPGA!

I'm not an expert on ISA and CPU internals, but an X86 instruction is not just "an instruction" anymore. Afaik, since the P6 arch Intel is using a fancy decoder to translate x86/-64 CISC into an internal RISC ISA (up to 4 u-ops per CISC instruction) and that internal ISA could be quite close to the RISC-V ISA for all I know.

Instruction decoding and memory ordering can be a bit of nightmare on CISC ISAs and fewer macro-instructions are not automatically a win. I guess we'll eventually see in benchmarks.

Even though Intel has had decades to refine their CPUs I'm quite excited to see where RISC-V is going.

As someone who is an expert on ISA and CPU internals, this meme of "X86 has an internal RISC" is an over-simplification that obscures reality. Yes, it decodes instructions into micro-ops. No, micro-ops are not "quite close to the RISC-V ISA".

Macro fusion definitely has a place in microarchitecture performance, especially when you have to deal with a legacy ISA. RISC-V makes the very unusual choice of depending on it for performance, when most ISAs prefer to fix the problem upstream.

Indeed. Also not an expert, but relying on macro-op fusion in hardware is tricky IIRC since different implementors will (likely) choose different macro-ops, resulting in strange performance differences between otherwise-identical chips.

Of course, you could start documenting "official" macro-ops that implementations should support, but at that point you're pretty much inventing a new ISA...

RISC-V does document "official" macro-ops that implementations are encouraged to support.

> "X86 has an internal RISC" is an over-simplification that obscures reality

Is it misleading though? I don't mind simplifications unless they are misleading. Would like to hear your criticisms of this meme.

X86 processors could have an internal VLIW for all we know. The instruction length would be very small by Itanium standards but still. It could be anything.

Seems to me that the parent comment was claiming to know.

> but an X86 instruction is not just "an instruction" anymore.

This is technically true but not really. Decoding into many instructions is mainly used for compatibility with the crufty parts of the x86 spec. In general, for anything other than rmw or locking a competent compiler or assembly writer will only very rarely emit instructions that compile to more than one uop. The way the frontend works, microcoded instructions are extraordinarily slow on real cpus.

Modern x86 is basically a risc with a very complex decode, few extra useful complex operations tacked on, and piles and piles of old moldy cruft that no-one should ever touch.

X86 doesn't have to go to microcode to have multiple uOPs for an instruction. Most uarchs can spit out three or four uOPs per instruction before having to resort to the microcode ROM. Basically instructions that would only need one microcode ROM row in a purely microcoded design can be spit out of the fast decoders.

Most commonly used x86_64 instructions decode to only 1 or 2 µops, thus often also just as "complex" as the original instructions.

> it's not going to be 2-3x faster, so it's never going to compensate for a 2-3x larger inner loop.

As someone else who replied said, I'm not a CPU architect, just software that works close to the metal. That means I pay attention to compiler output.

What you say is true in the very early says: compilers did indeed use the x86's addressing modes in all sorts of odd ways to squeeze as many calculations as possible into as few bytes as possible. Then it went in the reverse direction. You started seeing compilers emitting long series of simple instructions instead, seemingly deliberately avoiding those complex addressing modes. And now it's swung back again - I'm the complier using addressing modes to shift plus a couple of adds in one instruction is common again. I presume all these shifts were driven by speed of the resulting code.

I have no idea why one method was faster than the other - but clearly there is no hard and fast rule operating here. For some internal x86's implementations using complex addressing modes was a win. On some, for exactly the same instruction set, it wasn't. There is no cut and dried "best" way of doing it, rather it varies as the transistor and power budget changes.

One thing we do know about RISC-V is it is intended to cover a _lot_ transistor and power budgets. Where it's used now (low power / low transistor) is turned out their design decisions have turned out _very_ well, far better than x86.

More fascinatingly to me, today the biggest speed ups compilers get for super scalar arch's has nothing to do with the addressing modes so much attention is being focused on here. It comes from avoiding conditional jumps. The compilers will often emit code that evaluates both paths of the computation (thus burning 50% more ALU time on a calculating a result that will never be used), then choose the result they want with a cmov. In extreme cases, I've seen doing that sort of thing gain them a factor of 10, which is far more than playing tiddly winks with addressing modes will get you.

I have no idea how that will pan out for RISC-V. I don't think any one has done a super scalar implementation of it yet(?) But in the non-super scalar implementations the RISC-V instruction set choices have worked out very well so far. And when someone does do a super scalar implementation (and I'm sure there will be a lot of different implementations over time), it seems very possible x86's learnings on addressing mode use will be yesterdays news.

So do what Power does: most instructions that update the condition flags can do so optionally (except for instructions like stdcx. or cmpd where they're meaningless without it, and corner oddballs like andi.). For that matter, Power treats things like overflow and carry as separate from the condition register (they go in a special purpose register), so you can issue an instruction like addco. or just a regular add with no flags, and the condition register actually is divided into eight, so you can operate on separate fields without dependencies.

ARM also does something similar, many instructions has a flag bit specifying whether flags should be updated or not. It doesn't have the multiple flag registers of POWER though.

Which at least back in the day neither the IBM compilers nor GCC 2.x - 4.x made much use of. I've seen only a few handoptimzed assembler routines get decent use out of them. Easy to fuse pairs a probably a good compromise for carry calculation e.g. add + a carry instruction. That would get rid of one of the additional dependencies, but it would take a three operand addition or fusing two additions to get rid of the second RISC V specific dependency. And while GMP isn't unimportant it is still a niche use case that's probably not worth throwing that much hardware resources at to fix the ISA limitations in the uarch.

Which feature are you saying was not used much? Addition with carry; or addition without carry; or multiple flag registers?

IIRC few Power(PC) cores really split the condition register nibbles into 8 renamable registers and while Power(PC) includes everything (including at least two spare kitchen sinks) only a few instructions can pick which condition register nibble to update. Most integer instructions can only update cr0 and floating point instructions cr1. On the other hand you can do nice hacks with the cornucopia of bitwise available bitwise operations on condition register bits and it's one of the architectures where (floating point) comparisons return the full set of results (less, equal, greater, unordered).

On POWER, all the comparison instruction can store their result in any of the 8 sets of flags. The conditional branches can use any flag from any set.

The arithmetic instructions, e.g. addition or multiplication, do not encode a field for where to store the flags, so they use, like you said, an implicit destination, which is still different for integer and floating-point.

In large out-of-order CPUs, with flag register renaming, this is no longer so important, but in 1990, when POWER was introduced, the multiple sets of flags were a great advance, because they enabled the parallel execution of many instructions even in CPUs much simpler than today.

Besides POWER, the 64-bit ARMv8 also provides most of the 14 predicates that exist for a partial order relation. For some weird reason, the IEEE FP standard requires only 12 of the 14 predicates, so ARM implemented just those 12, even if they have 14 encodings, by using duplicate encodings for a pair of predicates.

I consider this stupid, because there would not have been any additional cost to gate correctly the missing predicate pair, even if it is indeed one that is only seldom needed (distinguishing between less-or-greater and equal-or-unordered).

> they're a bit of an architectural nightmare for everyone doing any more than the simplest CPUs, they make every instruction potentially have dependencies or anti-dependencies with every other

It's doesn't have to be _that_ bad. As long as condition flags are all written at once (or are essentially banked like PowerPC) the dependency issue can go away because they're renamed and their results aren't dependent on previous data.

Now, of course, instructions that only update some condition flags and preserve others are the devil.

It's not a tiny corner. People do arithmetic with carry all the time. Arbitrary precision arithmetic is more common than you think. Congratulations, RISC-V, you've not only slowed down every bignum implementation in existence, all those extra instructions to compute carry will blow the I$ faster, potentially slowing down any code that relies on a bignum implementation as well.

  > all those extra instructions to compute carry will blow the I$ faster

i think the idea is, as others have mentioned, the add/comp instructions are fused internally to a single instruction, so probably its not that bad for i$ as we might think?

> RISCV also specifies a 128-bit variant that is of course FASTER than these examples

Is it actually implemented on any hardware?

No. Mentioning it is only meant to distract.

Is there a semi competitive Risc-V core implemented anywhere?

It all seem hypothetical to me now, fast cores would fuse the instructions together so instruction count alone isn't adequate for the original evaluation of the ISA. Now I'm not sure that there are any that really do that..

SiFive have a new thing which is roughly as fast as a low-power CPU from Intel or Apple (e.g. IceStorm).

Obviously not really competitive, but I think they are still mostly making hardware so there is hardware at-all stage.

BOOM cores fuse ops already, so the cores don't have to be all that fast to start to see wins from it.

You can opt in to generating and propagating conditions and rename the predicates as well.

Reply on news.ycombinator.com