As far as I can see the loop in the function f() always terminates without the loop counter overflowing, but GCC cannot tell that it does. $ g++-4.3-20070907 -v Using built-in specs. Target: x86_64-unknown-linux-gnu Configured with: ../gcc-4.3-20070907/configure --program-suffix=-4.3-20070907 --enable-language=c,c++ --prefix=/home/jack/opt --with-mpfr=/home/jack/opt Thread model: posix gcc version 4.3.0 20070907 (experimental) (GCC) $ cat no_loop_opt.c void f(unsigned int in) { unsigned int rnd_to_2 = (in - (in % 2)); unsigned int i; for(i = 0; i != rnd_to_2; i += 2) ; } $ gcc-4.3-20070907 -O2 -Wall -Wextra -Wunsafe-loop-optimizations -c no_loop_opt.c no_loop_opt.c: In function ‘f’: no_loop_opt.c:7: warning: cannot optimize loop, the loop counter may overflow
We may be able to propagate somehow that rnd_to_2 is always even. I doubt it is worth the trouble, to be honest... Zdenek may have some thought on this.
Is there be any way to modify the code such that GCC would have an easier time seeing this? I tried using 'assert(rnd_to_2 % 2 == 0)' (since glibc's __assert_fail is marked with noreturn I thought it might help), but that didn't seem to have an effect. Short background that might be relevant: the code this is derived from is doing partial loop unrolling (8 iterations in the actual code) with a block of inline asm inserted, and then another loop following that handles any slop. Would rewriting the loop as while(in >= 2) { in -= 2; i += 2; } be likely to help? I see that it does with one particular version (4.1.2), but I have no intuition if that is because the optimizer understands such loops better or if it is just random luck.
Here's another example, which I think may represent a different case (and which I found much more surprising than the first): $ cat no_loop_opt2.c void g(unsigned int n) { unsigned int k; for(k = 0; k <= n; ++k) ; } (motoko ~)$ g++-4.1.2 -O2 -Wunsafe-loop-optimizations -c no_loop_opt2.c no_loop_opt2.c: In function 'void g(unsigned int)': no_loop_opt2.c:5: warning: cannot optimize possibly infinite loops no_loop_opt2.c:5: warning: cannot optimize possibly infinite loops no_loop_opt2.c:5: warning: cannot optimize possibly infinite loops no_loop_opt2.c:5: warning: cannot optimize possibly infinite loops (same output with 4.2.0) However if <= is changed to <, no problem. Version info: $ g++-4.1.2 -v Using built-in specs. Target: x86_64-pc-linux-gnu Configured with: /var/tmp/portage/sys-devel/gcc-4.1.2/work/gcc-4.1.2/configure --prefix=/usr --bindir=/usr/x86_64-pc-linux-gnu/gcc-bin/4.1.2 --includedir=/usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include --datadir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.1.2 --mandir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.1.2/man --infodir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.1.2/info --with-gxx-include-dir=/usr/lib/gcc/x86_64-pc-linux-gnu/4.1.2/include/g++-v4 --host=x86_64-pc-linux-gnu --build=x86_64-pc-linux-gnu --disable-altivec --enable-nls --without-included-gettext --with-system-zlib --disable-checking --disable-werror --enable-secureplt --disable-libunwind-exceptions --enable-multilib --enable-libmudflap --disable-libssp --disable-libgcj --enable-languages=c,c++,objc,obj-c++,fortran --enable-shared --enable-threads=posix --enable-__cxa_atexit --enable-clocale=gnu Thread model: posix gcc version 4.1.2 (Gentoo 4.1.2) $ g++-4.2.0 -v Using built-in specs. Target: x86_64-unknown-linux-gnu Configured with: ../gcc-4.2.0/configure --enable-languages=c,c++,objc,obj-c++ --program-suffix=-4.2.0 Thread model: posix gcc version 4.2.0
(In reply to comment #3) > Here's another example, which I think may represent a different case (and which > I found much more surprising than the first): > no_loop_opt2.c:5: warning: cannot optimize possibly infinite loops No this is correct, try having n as UINT_MAX. The conditional will always be true.
Argh, you are correct. The original code has unsigned int n = an_input / 160; so this could never occur there, but GCC's inability to tell that this assignment means that n cannot be UINT_MAX (in that code) is clearly much like the original example. And then I simplified it enough that the loop actually could be infinite... Sorry for the noise.
(In reply to comment #2) > Is there be any way to modify the code such that GCC would have an easier time > seeing this? I tried using 'assert(rnd_to_2 % 2 == 0)' (since glibc's > __assert_fail is marked with noreturn I thought it might help), but that didn't > seem to have an effect. As a workaround, you may change the type of i and rnd_to_2 to signed (signed arithmetics in C is guaranteed not to overflow, and loop optimizer will use this to prove that the loop is finite).
Author: amker Date: Tue Aug 2 10:09:33 2016 New Revision: 238982 URL: https://gcc.gnu.org/viewcvs?rev=238982&root=gcc&view=rev Log: PR tree-optimization/34114 * fold-const.c (multiple_of_p): Improve MULT_EXPR, PLUS_EXPR, PLUS_EXPR case. Handle SSA_NAME case. Modified: trunk/gcc/ChangeLog trunk/gcc/fold-const.c
Author: amker Date: Tue Aug 2 10:13:28 2016 New Revision: 238983 URL: https://gcc.gnu.org/viewcvs?rev=238983&root=gcc&view=rev Log: PR tree-optimization/34114 * tree-ssa-loop-niter.c (number_of_iterations_ne): Prove no-overflow information for more control IVs. gcc/testsuite PR tree-optimization/34114 * gcc.dg/tree-ssa/loop-42.c: New test. Added: trunk/gcc/testsuite/gcc.dg/tree-ssa/loop-42.c Modified: trunk/gcc/ChangeLog trunk/gcc/testsuite/ChangeLog trunk/gcc/tree-ssa-loop-niter.c
Fixed now.