4 ms·

I heard that one case where defining int-overflow as wrapping would be very bad for performance is pointer arithmetic - e.g. offset a pointer by i times sizeof

I heard that one case where defining int-overflow as wrapping would be very bad for performance is pointer arithmetic - e.g. offset a pointer by i times sizeof (type)). I think the x64 instruction "lea" accomplishes this. If this instruction is used, it is impossible to simulate 32-bit 2's complement overflow by just discarding the upper 32 bits of a 64-bit integer. So the UB that is associated with overflowing an int is required to efficiently compile loops that use a counter `int i` to index an array. There is a huge number of these loops in the wild. This problem might be just some unfortunate coincidence with how array indexing is defined in C. I don't understand this deeply, but just wanted to bring it up. I believe I read this on Fabian Giesen's blog.

simiones 6y ago
The part about lea doesn't seem especially convincing, it's not hard to imagine that pointer arithmetic could be defined such that overflow is still UB, while allowing regular signed integer arithmetic to overflow safely.
- jstimpfle 6y ago
  I can't say much about this. What I know is that in C, pointer arithmetic is defined in terms of "normal" arithmetic. p[i] is defined as *(p + i). And (p + i) means to offset p by (i * sizeof *p), and that multiplication is computed as the type of i (e.g. (32-bit) int or even smaller type)
  - simiones 6y ago
    That multiplication is entirely implicit, so there is no reason the compiler needs to handle it the same as it handles an explicit multiplication. Given that `p + i` is obviously not an integer addition and it already has much more UB then `i + j`, there is no reason why `i + j` having defined overflow rules needs to mean `p + i` also has them (just like `i + j` is safe for any small enough i and j, while p + i is only meaningful if points within the same object as p (to be fair, its not UB to compute p + i for any i, it's UB to use the value).
brandmeyer 6y ago
I think the nasty cases are in supporting subregister-sized arithmetic. ARMv8 can perform almost any integer operation on its registers either as 64-bit or 32-bit registers. The classic RISC machines could only perform full-register arithmetic. RISC-V has a small handful of instructions that can accelerate signed subregister arithmetic, but none that accelerate unsigned subregister arithmetic. So, if you need a 32-bit unsigned integer operation to guarantee wrap-around behavior on 64-bit RISC-V, the compiler may have to insert additional zero-extension instruction sequences if it cannot prove the absence of overflow.

simiones 6y ago

The part about lea doesn't seem especially convincing, it's not hard to imagine that pointer arithmetic could be defined such that overflow is still UB, while allowing regular signed integer arithmetic to overflow safely.

jstimpfle 6y ago
I can't say much about this. What I know is that in C, pointer arithmetic is defined in terms of "normal" arithmetic. p[i] is defined as *(p + i). And (p + i) means to offset p by (i * sizeof *p), and that multiplication is computed as the type of i (e.g. (32-bit) int or even smaller type)
- simiones 6y ago
  That multiplication is entirely implicit, so there is no reason the compiler needs to handle it the same as it handles an explicit multiplication. Given that `p + i` is obviously not an integer addition and it already has much more UB then `i + j`, there is no reason why `i + j` having defined overflow rules needs to mean `p + i` also has them (just like `i + j` is safe for any small enough i and j, while p + i is only meaningful if points within the same object as p (to be fair, its not UB to compute p + i for any i, it's UB to use the value).

brandmeyer 6y ago

I think the nasty cases are in supporting subregister-sized arithmetic. ARMv8 can perform almost any integer operation on its registers either as 64-bit or 32-bit registers. The classic RISC machines could only perform full-register arithmetic. RISC-V has a small handful of instructions that can accelerate signed subregister arithmetic, but none that accelerate unsigned subregister arithmetic. So, if you need a 32-bit unsigned integer operation to guarantee wrap-around behavior on 64-bit RISC-V, the compiler may have to insert additional zero-extension instruction sequences if it cannot prove the absence of overflow.