Loop is incorrectly optimized away

[llvmbot]

Bugzilla Link	24402
Resolution	FIXED
Resolved on	Aug 09, 2015 04:33
Version	3.5
OS	MacOS X
Reporter	LLVM Bugzilla Contributor
CC	@DimitryAndric,@zygoloid

Extended Description

The C code below gives different results with -O0/-O1 vs. -O2/-O3. -O1 gives the correct result, whereas -O2 gives an incorrect result. See the comments in the code.

/* Example of a clang optimization bug. Mark Adler, August 8, 2015.

Using -O0 or -O1 takes a little while and gives the correct result:

    47 bits set (4294967296 loops)

Using -O2 or -O3 optimizes out the loop, returning immediately with:

    0 bits set (4294967296 loops)

Of course, there weren't really that many loops.  The number of loops was
calculated, correctly, by the compiler when optimizing.  But it got the
number of bits set wrong.

This is with:

    Apple LLVM version 6.1.0 (clang-602.0.53) (based on LLVM 3.6.0svn)
    Target: x86_64-apple-darwin14.4.0

*/

include

include

/ bit vector of 1<<32 bits, initialized to all zeros / static uint64_t vec[1 << 26] = {0};

int main(void) { / set 47 of the bits. / vec[31415927] = UINT64_C(0xb9fe2f2fedf7ebbd);

/* count the set bits */
uint64_t count = 0;
uint64_t loops = 0;
uint32_t x = 0;
do {
    if (vec[x >> 6] & ((uint64_t)1 << (x & 0x3f)))
        count++;
    x++;
    loops++;
} while (x);
printf("%" PRIu64 " bits set (%" PRIu64 " loops)\n", count, loops);
return 0;

}

[DimitryAndric]

Specifically, this bug is fixed by:

r222451 | mzolotukhin | 2014-11-20 21:19:55 +0100 (Thu, 20 Nov 2014) | 9 lines

Fix a trip-count overflow issue in LoopUnroll.

Currently LoopUnroll generates a prologue loop before the main loop body to execute first N%UnrollFactor iterations. Also, this loop is used if trip-count can overflow - it's determined by a runtime check.

However, we've been mistakenly optimizing this loop to a linear code for UnrollFactor = 2, not taking into account that it also serves as a safe version of the loop if its trip-count overflows.

[llvmbot]

Of course. I am reporting this to Apple. Thanks.

[ec04fc15-fa35-46f2-80e1-5d271f2ef708]

Unfortunately the bug remains in the latest compiler tools release from Apple.

We have no control over that; you should take this up with Apple.

Note that in the comments the reported version includes "based on LLVM 3.6.0svn". I took that to mean version 3.6. Is that not correct? Is it really version 3.5?

Yes, sorry about our version numbering scheme, it's a common source of confusion. 3.6.0svn means approximately "some point on svn trunk between when 3.5.0 branched and when 3.6.0 branched". For instance, right now, the latest release is 3.6.2, we've branched 3.7 but not yet released it, and svn trunk claims to be 3.8.0svn.

[llvmbot]

Unfortunately the bug remains in the latest compiler tools release from Apple.

Note that in the comments the reported version includes "based on LLVM 3.6.0svn". I took that to mean version 3.6. Is that not correct? Is it really version 3.5?

[ec04fc15-fa35-46f2-80e1-5d271f2ef708]

I can't reproduce this with trunk, nor 3.6, but it reproduces with 3.5. Looks like this has been fixed for a while. I remember we had (and fixed) a bug analyzing loops with an N bit induction variable that perform exactly 2^N iterations; that could be the bug you hit.