Hello, I was just reading the source code and found it by chance. Signed integer overflow is known to be Undefined Behavior (UB) in the C standard. You must simply avoid it. Trying to observe its effects is wrong.
Though I found it by chance, some tools (such as static analysers and compiler's ub sanitizer) could help, but I have no experience with them. If the code is taking much longer, you could try substituting the test with a macro such as #define addition_overflows(u, v) ((u > 0 && v > INT_MAX - u) || (u < 0 && v < INT_MIN - u)) but it would have no effect if the compiler is already inlining the function. Best, Caio Em sex., 17 de dez. de 2021 às 08:22, Domingo Alvarez Duarte < [email protected]> escreveu: > Hello Caio ! > > How have you come to find this problem ? > > Looking through compiler warnings ? > > Trying to solve a specific problem ? > > Using your proposed overflow function and testing the all models in the > "examples" folder I didn't found any difference on the results other than > it takes a bit longer to solve then (before the compiler was effectively > eliminating the "overflow" function). > > Cheers ! > On 15/12/21 16:37, Domingo Alvarez Duarte wrote: > > Hello Caio ! > > Thank you for your discovery ! > > I can confirm what you've found, here is small C program to test it: > > ==== > > #include <stdio.h> > > #include <limits.h> > static int overflow2(int u, int v) > { /* check for integer overflow on computing u + v */ > if (u > 0 && v > INT_MAX - u) return 1; > if (u < 0 && v < INT_MIN - u) return 1; > return 0; > } > > static int overflow(int u, int v) > { /* check for integer overflow on computing u + v */ > if (u > 0 && v > 0 && u + v < 0) return 1; > if (u < 0 && v < 0 && u + v > 0) return 1; > return 0; > } > > int main() { > int max_u = 10; > for(int u= 0, v = 0; u< max_u; ++u, ++v) > printf("== %d : %d : %d : %d\n", u, v, overflow(u,v), > overflow2(u,v)); > for(int u= 0, v = INT_MAX-max_u; u < max_u; ++u, ++v) > printf(":::: %d : %d : %d : %d\n", u, v, overflow(u,v), > overflow2(u,v)); > return 0; > } > > ==== > > Output without optimization: > > ==== > > gcc -o overflow overflow.c > > ./overflow > > == 0 : 0 : 0 : 0 > == 1 : 1 : 0 : 0 > == 2 : 2 : 0 : 0 > == 3 : 3 : 0 : 0 > == 4 : 4 : 0 : 0 > == 5 : 5 : 0 : 0 > == 6 : 6 : 0 : 0 > == 7 : 7 : 0 : 0 > == 8 : 8 : 0 : 0 > == 9 : 9 : 0 : 0 > :::: 0 : 2147483637 : 0 : 0 > :::: 1 : 2147483638 : 0 : 0 > :::: 2 : 2147483639 : 0 : 0 > :::: 3 : 2147483640 : 0 : 0 > :::: 4 : 2147483641 : 0 : 0 > :::: 5 : 2147483642 : 0 : 0 > :::: 6 : 2147483643 : 1 : 1 > :::: 7 : 2147483644 : 1 : 1 > :::: 8 : 2147483645 : 1 : 1 > :::: 9 : 2147483646 : 1 : 1 > > ==== > > Output without optimization: > > ==== > > gcc -O2 -o overflow2 overflow.c > ./overflow2 > == 0 : 0 : 0 : 0 > == 1 : 1 : 0 : 0 > == 2 : 2 : 0 : 0 > == 3 : 3 : 0 : 0 > == 4 : 4 : 0 : 0 > == 5 : 5 : 0 : 0 > == 6 : 6 : 0 : 0 > == 7 : 7 : 0 : 0 > == 8 : 8 : 0 : 0 > == 9 : 9 : 0 : 0 > :::: 0 : 2147483637 : 0 : 0 > :::: 1 : 2147483638 : 0 : 0 > :::: 2 : 2147483639 : 0 : 0 > :::: 3 : 2147483640 : 0 : 0 > :::: 4 : 2147483641 : 0 : 0 > :::: 5 : 2147483642 : 0 : 0 > :::: 6 : 2147483643 : 0 : 1 <<< always 0 > :::: 7 : 2147483644 : 0 : 1 <<< always 0 > :::: 8 : 2147483645 : 0 : 1 <<< always 0 > :::: 9 : 2147483646 : 0 : 1 <<< always 0 > > ==== > > Cheers ! > On 15/12/21 16:01, Caio Giuliani wrote: > > Greetings, > > Files src/misc/okalg.c and src/api/mcfrelax.c define the following > function: > static int overflow(int u, int v) > { /* check for integer overflow on computing u + v */ > if (u > 0 && v > 0 && u + v < 0) return 1; > if (u < 0 && v < 0 && u + v > 0) return 1; > return 0; > } > It contains integer overflow, which is undefined behavior by the C > standard. > As I tested, both GCC 11.1.0 and clang 13.0.0 make this function always > return 0 from optimization level O1 onwards. > Particularly function glp_mincost_relax4 appears to have received ad-hoc > patches on the places this function is used. > > I propose, instead, the following: > #include <limits.h> > static int overflow(int u, int v) > { /* check for integer overflow on computing u + v */ > return (u > 0 && v > INT_MAX - u) return 1; > if (u < 0 && v < INT_MIN - u) return 1; > return 0; > } > > > Best regards, > > -- > Caio Merlini Giuliani > Operations Research Analyst > WPLEX Software Ltda > www.wplex.com.br > > -- Caio Merlini Giuliani Operations Research Analyst WPLEX Software Ltda www.wplex.com.br
