Search
Signed integer overflow undefined behavior or not?
Nov 13, 2015
Ali Çehreli
Nov 13, 2015
Nov 13, 2015
Don
Nov 13, 2015
Kagamin
Nov 13, 2015
John Colvin
Nov 13, 2015
Nov 13, 2015
Don
Nov 13, 2015
John Colvin
Nov 13, 2015
Kagamin
Nov 13, 2015
Matthias Bentrup
Nov 13, 2015
John Colvin
Nov 13, 2015
Walter Bright
Nov 13, 2015
Walter Bright
Nov 13, 2015
Ali Çehreli
Nov 13, 2015
Nov 13, 2015
Ali Çehreli
Nov 13, 2015
Iain Buclaw
Nov 13, 2015
Walter Bright
Nov 13, 2015
```I searched but I could not find a definitive answer. I am pretty sure this thread will turn into yet another about what it should be, but I need an answer soon before updating my book to be review by Russel Winder, who will not give it a good mark before I get this part right. :)

"If both operands are of integral types and an overflow or underflow occurs in the computation, wrapping will happen. That is, uint.max + 1 == uint.min and uint.min - 1 == uint.max."

Since it does not say "unsigned integral type", one might think it includes signed integral types as well. However, the rest of that quote is about the "wrap" behaviour of unsigned types and the fact that it conveniently uses an unsigned type in the only example makes me think that the spec means unsigned types there.

So the question is, do we support twos complement only, hence signed overflow is defined as wrap, or do we consider it as undefined behaviour?

Ali

P.S. The quote above has a misconception, which I've become aware of just recently myself: Contrary to what it may convey, underflow is not "having a value less than .min". For integral types, that is still called overflow[1]. Underflow is for floating point types only and it means "smaller in magnitude (that is, closer to zero) than the smallest value representable as a normal floating point number"[2]. So, underflow would not take a floating point to -.infinity; rather, towards less than .min_normal.

[1] https://en.wikipedia.org/wiki/Arithmetic_overflow (Note "greater in magnitude" there; it covers negative values as well.)

[2] https://en.wikipedia.org/wiki/Arithmetic_underflow
```
```Signed overflow are defined as well, as wraparound.
```
```On 11/12/2015 4:43 PM, Ali Çehreli wrote:
> So the question is, do we support twos complement only, hence signed overflow is
> defined as wrap,

Yes. I see no reason to support 1's complement.

It's worth checking how LDC and GDC deal with this deep in their optimizer - is it considering it undefined behavior?

```
```On 11/12/2015 10:00 PM, Walter Bright wrote:
> On 11/12/2015 4:43 PM, Ali Çehreli wrote:
>> So the question is, do we support twos complement only, hence signed
>> overflow is
>> defined as wrap,
>
> Yes. I see no reason to support 1's complement.

It's official! :)

> It's worth checking how LDC and GDC deal with this deep in their
> optimizer - is it considering it undefined behavior?

Since it's UB in C and C++, I've heard that both clang and gcc do remove code branches if they can prove that there will be signed overflow. I don't know how or whether that optimization is turned off for D.

Ali

```
```On Friday, 13 November 2015 at 06:46:37 UTC, Ali Çehreli wrote:
> Since it's UB in C and C++, I've heard that both clang and gcc do remove code branches if they can prove that there will be signed overflow. I don't know how or whether that optimization is turned off for D.
>
> Ali

Clang does it, but LLVM IR defines flags for overflow behavior and it is up to the frontend to choose which one it want to use.
```
```On Friday, 13 November 2015 at 06:46:37 UTC, Ali Çehreli wrote:
> Since it's UB in C and C++, I've heard that both clang and gcc do remove code branches if they can prove that there will be signed overflow. I don't know how or whether that optimization is turned off for D.

The question you want to ask is probably if modular arithmetics is legal D code for all integers, signed and unsigned. Can the programmer assume that wrapping is legal D code?

If so, then D does not have any kind of integer overflow at all, by definition.

```
```On 11/13/2015 12:30 AM, Ola Fosheim Grøstad wrote:
> On Friday, 13 November 2015 at 06:46:37 UTC, Ali Çehreli wrote:
>> Since it's UB in C and C++, I've heard that both clang and gcc do
>> remove code branches if they can prove that there will be signed
>> overflow. I don't know how or whether that optimization is turned off
>> for D.
>
> The question you want to ask is probably if modular arithmetics is legal
> D code for all integers, signed and unsigned. Can the programmer assume
> that wrapping is legal D code?

I understood Walter's response to be so.

> If so, then D does not have any kind of integer overflow at all, by
> definition.

On the other hand, in order to define the wrapping behavior at all, one must speak of overflow first. Wrapping is the solution for the condition of overflow, which D must have to begin with, no? :)

Ali

```
```On Friday, 13 November 2015 at 05:47:03 UTC, deadalnix wrote:
> Signed overflow are defined as well, as wraparound.

Can we please, please, please not have that as official policy without carefully thinking through the implications?

It is undefined behaviour in C and C++, so we are not constrained by backwards compatibility with existing code.

I have never seen an example where signed integer overflow happened, which was not a bug. In my opinion, making it legal is an own goal, an unforced error.

Suppose we made it an error. We'd be in a much better position than C. We could easily add a check for integer overflow into CTFE. We could allow compilers and static analysis tools to implement runtime checks for integer overflow, as well.
Are we certain that we want to disallow this?

At the very least, we should change the terminology on that page. The word "overflow" should not be used when referring to both signed and unsigned types. On that page, it is describing two very different phenomena, and gives the impression that it was written by somebody who does not understand what they are talking about.
The usage of the word "wraps" is sloppy.

That page should state something like:
For any unsigned integral type T, all arithmetic is performed modulo (T.max + 1).
Thus, for example, uint.max + 1 == 0.
There is no reason to mention the highly misleading word "overflow".

For a signed integral type T, T.max + 1 is not representable in type T.
Then, we have a choice of either declaring it to be an error, as C does; or stating that the low bits of the infinitely-precise result will be interpreted as a two's complement value. For example, T.max + 1 will be negative.

(Note that unlike the unsigned case, there is no simple explanation of what happens).

```
```On 13 Nov 2015 7:05 am, "Walter Bright via Digitalmars-d" < digitalmars-d@puremagic.com> wrote:
>
> On 11/12/2015 4:43 PM, Ali Çehreli wrote:
>>
>> So the question is, do we support twos complement only, hence signed
overflow is
>> defined as wrap,
>
>
> Yes. I see no reason to support 1's complement.
>
> It's worth checking how LDC and GDC deal with this deep in their
optimizer - is it considering it undefined behavior?
>

We are not.  For gdc, the fwrapv flag is enabled by default.

```
```On Friday, 13 November 2015 at 08:51:27 UTC, Ali Çehreli wrote:
> I understood Walter's response to be so.

That's my interpretation of what Walter has said before too. So a D compiler cannot prevent compilation of a statically detected wrapping (overflow). As a result D-integers are circular enumerations.

> On the other hand, in order to define the wrapping behavior at all, one must speak of overflow first.

For educational purposes, probably :-)

> Wrapping is the solution for the condition of overflow, which D must have to begin with, no? :)

For definition, not really. Signed integers are often defined as three functions (other definitions are possible):

Zero: 0
Successor of X: S
Predecessor of X: P

For a 2 bit signed modular arithmetics you would get the complete normalized set:

PP0, P0, 0, S0

with the defined rewrites

SPX = X
PSX = X
PPP0 = S0
SS0 = PP0

(implies PPPPX = X and SSSSX = X)

then you define the operators on the set (+,- etc) using relations such as PSX = X etc.

```
« First   ‹ Prev
1 2 3