Invalid signed integer overflow in saturated_arithmetic.h

[GoogleCodeExporter]

What steps will reproduce the problem?

I don't have a handy model to reproduce the problem, but the following should 
expose it: create two variables (x, y) with domains [kint64min, kint64max], 
then their difference z = x - y and try to register constraint z > 10. This 
constraint is assumed to be always true and, thus, ignored by the solver.

I myself got this problem with a more complicated model, where the real domains 
of x and y were not known in advance and had to be set at "infinity" values.

I also attached a file to isolate the problem. Read below for the explanation.

What is the expected output? What do you see instead?

The constraint should be handled by the solver properly.

What version of the product are you using? On what operating system?

Should be true for the current version of or-tools, GCC 4.7 (at least)

Please provide any additional information below.

The problem is within saturated_arithmetic.h, function CapWithSignOf. Signed 
integer overflow is undefined as by C++ standard, so some compilers make use of 
this during optimization. In this case, GCC (4.7 and possibly others) during 
the VRP optimization completely ignores "sign_bit". Thus, CapWithSignOf always 
returns kint64max, ignoring the sign of x.

This doesn't happen in clang, it seems. For GCC the solution is to enforce the 
wrap signed arithmetic by using -fwrapv option. I don't know about other 
compilers or any remedies that might exist there.

I attached the file to reproduce the problem, where I cut the functions from 
saturated_arithmetic.h Assembly compiled with -O2-3 shows that GCC always uses 
the kint64max constant. Running it with x=-9223372036854775808, y=1
produces x-y = 7fffffffffffffff, which is incorrect.

Original issue reported on code.google.com by allex2...@gmail.com on 29 Dec 2014 at 8:24

Attachments:

• or-tools-signed.cpp

[GoogleCodeExporter]

Thanks

I will have a look.

Can you use kint64max/2 instead?

Thanks

Original comment by laurent....@gmail.com on 1 Jan 2015 at 12:01

[GoogleCodeExporter]

I have added -fwrapv to the compiler flags.
Thanks

Original comment by laurent....@gmail.com on 5 Jan 2015 at 9:27

• Changed state: Fixed