[Bug c/59538] New: Optimization of -O2 or higher creates incorrect code in loop

[Bug c/59538] New: Optimization of -O2 or higher creates incorrect code in loop

[arsham at skrenes dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59538

            Bug ID: 59538
           Summary: Optimization of -O2 or higher creates incorrect code
                    in loop
           Product: gcc
           Version: 4.8.1
            Status: UNCONFIRMED
          Severity: critical
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: arsham at skrenes dot com

Created attachment 31462
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=31462&action=edit
Small prime number calculating program that shows bug

I'm using Ubuntu 13.10 with all updates installed. GCC was recently updated for
the distribution to:
gcc (Ubuntu/Linaro 4.8.1-10ubuntu9) 4.8.1

Before the update, everything worked correctly. After the update, the -O2 or
higher optimization flag breaks code (in this instance, it's a loop).

I have attached bug.c to this bug report, which compiles with no warnings or
errors. It determines the 10000th prime number (naive algorithm) 5 times and
reports the duration it took for each iteration. If you compile as follows, it
works correctly:
gcc -Wall -Wextra bug.c

If you compile it with optimization level -O2 or higher such as the following,
it breaks the loop:
gcc -O3 -Wall -Wextra bug.c

You will see that it returns the results almost instantly. In the code, I have
a commented print statement that shows the 10000th prime number. If you
uncomment this, it also suddenly works correctly with -O3. It seems the gcc is
"over-optimizing" and breaking the code if variable "i" is not printed.

[Bug middle-end/59538] Optimization of -O2 or higher creates incorrect code in loop

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59538

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
          Component|c                           |middle-end
         Resolution|---                         |INVALID
           Severity|critical                    |normal

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The loop to calculate the prime number is an empty finite loop and the result
of the loop is not used so the loop is removed.  This is a valid optimization.

[Bug middle-end/59538] Optimization of -O2 or higher creates incorrect code in loop

[arsham at skrenes dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59538

Arsham Skrenes <arsham at skrenes dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|INVALID                     |---

--- Comment #2 from Arsham Skrenes <arsham at skrenes dot com> ---
The result of the loop is implicitly used though (benchmarking how long it
takes to find nth prime number; I also use this code to create an artificial
workload for a graduate-level project). This is new behaviour by this version
of GCC. This is NOT a valid optimization as it clearly is having unintended
side-effects which I am showcasing.

[Bug middle-end/59538] Optimization of -O2 or higher creates incorrect code in loop

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59538

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|---                         |INVALID

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Arsham Skrenes from comment #2)
> The result of the loop is implicitly used though (benchmarking how long it
> takes to find nth prime number; I also use this code to create an artificial
> workload for a graduate-level project). This is new behaviour by this
> version of GCC. This is NOT a valid optimization as it clearly is having
> unintended side-effects which I am showcasing.

No you need an explicit use to avoid removing empty finite loops.  Changing the
time is not a side effect of a loop which is defined by the C/C++ standards. 
Many benchmarks can be optimized away if you are not careful; this is true of
any code and most programming languages.

[Bug middle-end/59538] Optimization of -O2 or higher creates incorrect code in loop

[arsham at skrenes dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59538

--- Comment #4 from Arsham Skrenes <arsham at skrenes dot com> ---
Can I suggest then that GCC outputs a compiler warning when it removes a loop?
It outputs warnings for unused variables as well as implicit casting, so why
not have a warning for removing loops?

Also, is there a directive that I can use to explicitly tell GCC to not remove
a loop (without having to resort to a compiler flag which is global, printing a
variable, or using the 'volatile' keyword which de-optimizes the caching of the
target variable)? Thanks!

[Bug middle-end/59538] Optimization of -O2 or higher creates incorrect code in loop

[dominiq at lps dot ens.fr]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59538

--- Comment #5 from Dominique d'Humieres <dominiq at lps dot ens.fr> ---
> Also, is there a directive that I can use to explicitly tell GCC 
> to not remove a loop (without having to resort to a compiler flag 
> which is global, printing a variable, or using the 'volatile' keyword 
> which de-optimizes the caching of the target variable)? Thanks!

Try to print i instead of NTH! The basic way to avoid the removal of loops in a
benchmark is to consume in some way some of the computed data (in some cases
the optimizer may even be clever than you think).

[Bug middle-end/59538] Optimization of -O2 or higher creates incorrect code in loop

[arsham at skrenes dot com]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59538

--- Comment #6 from Arsham Skrenes <arsham at skrenes dot com> ---
(In reply to Dominique d'Humieres from comment #5)
> > Also, is there a directive that I can use to explicitly tell GCC 
> > to not remove a loop (without having to resort to a compiler flag 
> > which is global, PRINTING A VARIABLE, or using the 'volatile' keyword 
> > which de-optimizes the caching of the target variable)? Thanks!
> 
> Try to print i instead of NTH! The basic way to avoid the removal of loops
> in a benchmark is to consume in some way some of the computed data (in some
> cases the optimizer may even be clever than you think).

Your solution is "printing a variable" which if you look at my question, is
exactly what I want to avoid. Before even writing that comment, I had already
added, after line 35, the following:
printf("%d\r",i);

It gets overwritten by the next print statement and retains the loop. It's a
hack and not at all elegant. That is why I'm asking if there is a compiler
directive I can use instead.

If one doesn't exist, there really ought to be a directive to retain a loop and
at the very least, such "optimizations" should output a warning (you shouldn't
be obliterating blocks of code without so much as a warning). The developer
should know if a block of code has been deemed unreachable or useless and
therefore not included.

[Bug middle-end/59538] Optimization of -O2 or higher creates incorrect code in loop

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=59538

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Try:
//  GCC Bug - bug.c
//  Created by Arsham Skrenes on 2013-12-17

#include <stdio.h>
#include <sys/time.h>

// Find the NTH prime number SAMPLES times
#define NTH     10000
#define SAMPLES 5

int main(void)
{
    struct timeval t1, t2, t3;
    int i, sample;
    volatile int keeparound;
    printf("Generating %d samples...\n", SAMPLES);

    // i = prime candidate; check = test number (naive algorithm)
    for (sample = 0; sample < SAMPLES; sample++)
    {
        int count = 2, check;
        gettimeofday(&t1, NULL);
        for (i = 3; count <= NTH; i++)
        {
            for (check = 2; check <= i - 1; check++)
            {
                if (i%check == 0)
                    break;
            }
            if (check == i)
            {
                // found a prime number
                count++;
            }
        }
        gettimeofday(&t2, NULL);

        // calculate primes/second for this sample
        timersub(&t2, &t1, &t3);
        printf("It took %f seconds to find the %dth prime number.\n",
               (double)t3.tv_usec / 1000000 + t3.tv_sec,
               NTH);
    }

    // If you uncomment the following line, or compile this code with flag -O1
    // or less, it will work correctly...
    //printf("The %dth prime number is %d\n", NTH, i-1);
        keeparound = i - 1;

    return 0;
}

Which will keep around the final i and not cause any optimizations to happen
(well GCC might change around the loop to figure out i only once but that
optimization is not done currently but could be in the future).