Comment by brandmeyer | Hacker News Reader

Comment by brandmeyer | Hacker News Reader

Parent Full thread

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

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

size_t is unsigned.

Right, but you don't need to sign extend it.

Eh? The problem with using unsigned is identical to using size_t. size_t doesn't have any special carveouts that eg. say that wrapping is undefined behavior. It's defined as an unsigned integer type. Meaning it has unsigned integer type behaviors.

unsigned is 32-bit, which means you need to have it overflow in the lower 32 bits since you're working on it through a 64-bit register. If you use a full size_t then this check is not necessary.

You have a typo: size_t doesn't need zero extension. RISC-V does have 32-bit signed integer arithmetic that unconditionally sign-extends the result from bit 31. So using a signed integer as a counter (bad practice IMO, but widely recommended in style guides) doesn't need anything extra at all.

Uh, wrong subthread?

(jumping up the thread to try and hop over some confusion...)

The problem isn't with unsigned types generally. Its with subregister unsigned types. So, size_t and uintptr_t are fine. uint32_t, uint16_t, uint8_t (on LP64 ABIs) are pessimized and demand zero-extension instructions (or proofs that they can be safely elided) prior to causing side-effects. uint64_t on a LP128 ABI would also be problematic.

signed 32-bit int is also fine... because RISC-V specifically has a suite of arithmetic instructions that unconditionally sign-extend from bit 31. Even without those, it would still be fine because the carve-out for undefined behavior is wide enough for INT_MAX+1 to remain positive. Same thing for all of the other narrow-width signed integer types. If you increment SHRT_MAX and then use it to index memory, its perfectly legal undefined behavior to access base + SHRT_MAX+1 instead of base + SHRT_MIN.

However, that's not legal for the unsigned types. They are all mandated to wrap in 2's complement. base + UINT_MAX+1 must access base + 0 when the index is `unsigned int`, even on a 64-bit machine.

> base + UINT_MAX+1 must access base + 0 when the index is `unsigned int`, even on a 64-bit machine.

Ironically, given the topic, that's actually not true, because `base + UINT_MAX+1` is `(base + UINT_MAX)+1` (with a pointer, not a unsigned int, as the temporary value). That should probably be `base + (UINT_MAX+1)`.

This whole spiel is only relevant when the programmer specifies an array index in a distinct variable.

Nitpick: s/LP64 machine/LP64 C implementation/

But isn't size_t (or ptrdiff_t) the preferred indexing type in C for this reason (among others)? Sometimes you of course do want wrap around modulo semantics but that's much rarer, right?

The problem is that providing extra bits for "sign-extension mode" and "read 32b or 64b" blows through the opcode space very quickly.

Reply on news.ycombinator.com