CODEWITHSUNDEEP
c++integer-overflowdevtoolset
Still-InBeta
Still-InBeta

Reputation: 383

Signed Integer value overflow in C++?

I have a legacy codebase which we are trying to migrate from devtoolset-4 to devtoolset-7. I noticed an interesting behaviour regarding overflow of signed integers (int64_t, to be specific).

There is a code snippet which is used to detect integer overflow while multiplying a big set of integers:

// a and b are int64_t
int64_t product = a * b; 
if (b != 0 && product / b != a) {
    // Overflow
}

This code was working fine with devtoolset-4. However, with devtoolset-7, overflow is never being detected.

For eg: When a = 83802282034166 and b = 98765432, the product becomes -5819501405344925872 (clearly the value has overflown).

But product / b results in value equal to a (83802282034166). Hence the if condition never becomes true. Its value should have been computed based on the overflown (negative) product value: -5819501405344925872 / 98765432 = -58922451788

Ironically, the Maths is correct but it is causing anomalous behaviour with regards to devtoolset-4.

I understand that signed integer overflow is an 'undefined behaviour' in C++ and so the compiler behaviour could change across implementations. But could someone help me make sense of the above behaviour?

Note: the g++ versions in devtoolset-4 and devtoolset-7 are g++ (GCC) 5.2 and g++ (GCC) 7.2.1, respectively.

Upvotes: 5

Views: 3010

Answers (7)

Stephen Newell
Stephen Newell

Reputation: 7838

Because signed overflow/underflow are classified as undefined behavior, compilers are allowed to cheat and assume it can't happen (this came up during a Cppcon talk a year or two ago, but I forget the talk off the top of my head). Because you're doing the arithmetic and then checking the result, the optimizer gets to optimize away part of the check.

This is untested code, but you probably want something like the following:

if(b != 0) {
    auto max_a = std::numeric_limits<int64_t>::max() / b;
    if(max_a < a) {
        throw std::runtime_error{"overflow"};
    }
}
return a * b;

Note that this code doesn't handle underflow; if a * b can be negative, this check won't work.

Per Godbolt, you can see your version has the check completely optimized away.

Upvotes: 4

Abdelrahman Nasr
Abdelrahman Nasr

Reputation: 1

you can read this documentation it might be useful to you as if any problem faced me in variables and data types i go directly to read it : http://www.cplusplus.com/doc/tutorial/variables/

Upvotes: 0

eerorika
eerorika

Reputation: 238341

With the knowledge thatproduct == a * b, the compiler/optimizer can take following optimization steps:

b != 0 && product / b != a
b != 0 && a * b / b != a
b != 0 && a * 1 != a
b != 0 && a != a
b != 0 && false
false

The optimizer can choose to remove the branch entirely.

I understand that signed integer overflow is an 'undefined behaviour' in C++ and so the compiler behaviour could change across implementations. But could someone help me make sense of the above behaviour?

You may know that signed integer overflow is UB, but I suppose you haven't yet grasped what UB really means. UB doesn't need to, and often doesn't make sense. This case seems straight forward though.

Upvotes: 4

Tomaz Canabrava
Tomaz Canabrava

Reputation: 2408

if you are worried about integer overflows it's not better to use a arbitrary precision integer library - with this you can increase your size types to 128bits and don't worry about it.

https://gmplib.org/

Upvotes: 0

Yakk - Adam Nevraumont
Yakk - Adam Nevraumont

Reputation: 275385

Signed integer overflow is undefined behavior in C++.

This means the optimizer can assume it never happens. a*b/b is a, period.

Modern compilers do static single assignment based optimization.

// a and b are int64_t
int64_t product = a * b;
if (b != 0 && product / b != a) {
  // Overflow
}

becomes:

const int64_t __X__ = a * b; 
const bool __Y__ = b != 0;
const int64_t __Z__ = __X__ / b;
const int64_t __Z__ = a*b / b;
const int64_t __Z__ = a;

if (__Y__ && __Z__ != a) {
  // Overflow
}

which evaluates to

if (__Y__ && false) {
  // Overflow
}

clearly, as __Z__ is a and a!=a is false.

int128_t big_product = a * b;

work with big_product and detect overflow there.

SSA permits the compiler to realize things like (a+1)>a is always true, which can simplify many loops and optimization cases. That fact relies on the fact that overflow of signed values is undefiend behavior.

Upvotes: 6

Raxvan
Raxvan

Reputation: 6505

Signed integer overflow is undefined behavior. This is different from unsigned int(all unsigned ints). More info on this here

As a side note, people noticed that using int instead of unsigned int increases performance (see here) since compiler don't deal with overflow behavior.

Upvotes: 0

Vittorio Romeo
Vittorio Romeo

Reputation: 93274

could someone help me make sense of the above behaviour?

Signed integer overflow has undefined behaviour in C++. This implies that you cannot reliably detect it, and that code which contains signed integer overflow can do anything.

If you want to detect whether an operation will result in a signed integer overflow or not, you need to do that before the overflow happens, preventing UB from taking place.

Upvotes: 0

Related Questions