User account creation filtered due to spam.

Bug 42810 - Enumeration with sequential values has its for-loop exit condition optimized out.
Summary: Enumeration with sequential values has its for-loop exit condition optimized ...
Status: RESOLVED INVALID
Alias: None
Product: gcc
Classification: Unclassified
Component: c++ (show other bugs)
Version: 4.3.1
: P3 normal
Target Milestone: ---
Assignee: Not yet assigned to anyone
URL:
Keywords:
Depends on:
Blocks:
 
Reported: 2010-01-19 22:51 UTC by Tony Garland
Modified: 2010-05-04 16:06 UTC (History)
2 users (show)

See Also:
Host:
Target:
Build:
Known to work:
Known to fail:
Last reconfirmed:


Attachments
Preprocessed version of the test.cpp file. (3.73 KB, text/plain)
2010-01-19 22:53 UTC, Tony Garland
Details
Compiler output ready to feed to assembler--the problem can be seen here. (751 bytes, text/plain)
2010-01-19 22:53 UTC, Tony Garland
Details
Problem also occurs in ARM gcc 4.4.1 with -O2 as shown in this assembly listing (608 bytes, text/plain)
2010-01-19 22:56 UTC, Tony Garland
Details
Assembler input which works correctly compiled at -O1 (1.54 KB, text/plain)
2010-01-19 22:58 UTC, Tony Garland
Details

Note You need to log in before you can comment on or make changes to this bug.
Description Tony Garland 2010-01-19 22:51:52 UTC
An enumeration with sequentially-assigned values is used as an index of a for loop. The loop operates properly at optimization levels -O0 and -O1. At level -O2 the optimizer "optimizes out" the test for the exit condition and the loop never exits.

I'll be attaching the *.i file, but below is the test source file which shows the situation.  At -O2, the loop itself never exits and a separate counter which is part of the test triggers a break itself--after printing that the test has failed.

/*
Sample program to demonstrate comparison failure involving sequential
enumeration when optimized.  To reproduce the failure:

    g++ -O2 test.cpp && ./a.out

Any one of the following changes correct the problem:

    - Change optimization (omit or use -O0 or -O1).
    - Set ENUM_VALUE_FIRST to 0.
    - Delete one of the enum values between first and last (one less
      value).
    - Insert an addition enum value between first and last (one more
      value).

agarland at fluke dot com

*/

// Compile at -O1 or uncomment any one of the following to "fix" the problem.
//#define FIX1 // Omit an enum value.
//#define FIX2 // Add an extra enum value.
//#define FIX3 // Start first value at zero rather than 1.

#include <stdio.h>
enum ENUM_VALUE
{
#ifdef FIX3
    ENUM_VALUE_FIRST = 0,
#else
    ENUM_VALUE_FIRST = 1,
#endif
    ENUM_VALUE_A,
#ifndef FIX1
    ENUM_VALUE_B,
#endif
    ENUM_VALUE_C,
    ENUM_VALUE_D,
    ENUM_VALUE_E,
#ifdef FIX2
    ENUM_VALUE_F,
#endif
    ENUM_VALUE_LAST
};

main()
{
    printf("Compiled on %s %s\n", __DATE__, __TIME__);
    unsigned int count = 0;
    for (
        ENUM_VALUE id = ENUM_VALUE_FIRST;
        id <= ENUM_VALUE_LAST;
        id = static_cast<ENUM_VALUE>(id+1)
    )
    {
        printf("id=%d\n", id);

        if (100 == count++)
        {
            // Should never get here.
            printf("ENUMERATION COMPARISON FAILED!\n");
            break;
        }
    }
}
Comment 1 Tony Garland 2010-01-19 22:53:19 UTC
Created attachment 19661 [details]
Preprocessed version of the test.cpp file.
Comment 2 Tony Garland 2010-01-19 22:53:58 UTC
Created attachment 19662 [details]
Compiler output ready to feed to assembler--the problem can be seen here.
Comment 3 Tony Garland 2010-01-19 22:54:36 UTC
Here is the compiler information:

g++ -v
Using built-in specs.
Target: i586-suse-linux
Configured with: ../configure --prefix=/usr --with-local-prefix=/usr/local --infodir=/usr/share/info --mandir=/usr/share/man --libdir=/usr/lib --libexecdir=/usr/lib --enable-languages=c,c++,objc,fortran,obj-c++,java,ada --enable-checking=release --with-gxx-include-dir=/usr/include/c++/4.3 --enable-ssp --disable-libssp --with-bugurl=http://bugs.opensuse.org/ --with-pkgversion='SUSE Linux' --disable-libgcj --with-slibdir=/lib --with-system-zlib --enable-__cxa_atexit --enable-libstdcxx-allocator=new --disable-libstdcxx-pch --program-suffix=-4.3 --enable-version-specific-runtime-libs --enable-linux-futex --without-system-libunwind --with-cpu=generic --build=i586-suse-linux
Thread model: posix
gcc version 4.3.1 20080507 (prerelease) [gcc-4_3-branch revision 135036] (SUSE Linux)
Comment 4 Tony Garland 2010-01-19 22:56:50 UTC
Created attachment 19663 [details]
Problem also occurs in ARM gcc 4.4.1 with -O2 as shown in this assembly listing

This shows the same problem in gcc for the ARM.
Comment 5 Tony Garland 2010-01-19 22:58:50 UTC
Created attachment 19664 [details]
Assembler input which works correctly compiled at -O1

In this sample, the exit condition is properly tested as can be seen in the assembly listing.  The difference between this file and test.s shows how the exit condition gets optimized out.
Comment 6 Tony Garland 2010-01-19 23:05:07 UTC
There is a related bug here:

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

But unlike that bug which uses an out-of-range enum value, this case does not. We are testing  'value <= max_valid_enum_value'.  So I've entered this as a different bug for reconsideration about how the compiler is handling valid enumeration values in -O2.
Comment 7 Jakub Jelinek 2010-01-19 23:56:21 UTC
This testcase also uses out of range enum value, so has undefined behavior as well.  For ENUM_VALUE_LAST which is a power of 2 minus 1 the for loop condition still lets the body to be executed, then id = static_cast<ENUM_VALUE>(id+1)
i.e. id = static_cast<ENUM_VALUE>(ENUM_VALUE_LAST+1) is the out of range value.
The compiler can assume that no enum value is larger than ENUM_VALUE_LAST if it is a power of 2 minus 1 (i.e. the largest value of the underlying type).
Comment 8 Tony Garland 2010-01-20 00:18:52 UTC
I see what you mean.  I was looking at the "wrong side" of the "<=" and not thinking about the reality that it would have to exceed the last valid value. Pretty obvious once you point it out.

So now my question is why doesn't the compiler issue any warning about this?
The result is a silent "forever loop" and the program hangs.  Surely this is not what the programmer intended?

I can appreciate that the compiler can make certain assumptions, but what I'm really trying to say here is that to truly be helpful in programming a compiler should either accept the code as valid (and try to do what is intended) or issue a warning or error saying it won't or might not.

This is compounded by the fact that the code runs fine at lesser optimization levels--and compiles silently at all levels.  So it is worse than silent, it is misleading in that it allows this poor programming practice during development only to turn it into a permanent hang in optimized production builds. :-)
Comment 9 Tony Garland 2010-01-20 15:42:19 UTC
I am reopening this bug if only because I'd like to get a response to my previous comments.  

I can appreciated that, in your view, the compiler is 'technically correct' in making the assumption that it need not support programs which inadvertently generate an enumeration value outside of the defined range.

But if you step back from this 'technical legitimacy', and look at the bigger picture, we are left with a compiler which is not doing much to help us write reliable code.  In fact, it is doing just the opposite by silently accepting such code and even running it in the expected fashion when optimization is less than -O2.

It is one thing to state that the compiler doesn't have to support a value which is greater than 1 less than the closest power of two, and another to make a compiler which usefully indicates when it refuses to follow where the programmer is directing it to go.

All the more so when its refusal to implement an exit loop--indeed completely expunging the expected exit condition from the code--hinges on such a rare combination of incident:  1) optimization set at -O2, and 2) a maximum enumeration value which happens to fall just under a power of two.  Unless this unhappy combination occurs, the code misleadingly does as the programmer expects.  (Also, I would venture to say that many programmers would be extremely surprised to find that powers of 2 which fit well within 8-bits are apparently to be included in this behavior: 8, 16, 32, 64, 128.)

So, given that those who know much more about enumerations and compilers than I ever will have decided that such behavior is not to be improved upon, why is it that we get no warning about it?  Isn't the intention of warnings to indicate to the programmer when they have done something silly or dangerous where the results may differ from their expectations?  Surely this situation falls into that category.

The fact that there have been two bug reports in this regard and that a number of experienced programmers at my site found the resulting execution completely puzzling and unexpected would seem to indicate some sort of response beyond "this is technically acceptable therefore the bug report is INVALID . . . next!" is in order?
Comment 10 Paolo Carlini 2010-01-20 15:48:14 UTC
Too bad, yes.
Comment 11 Richard Biener 2010-01-20 17:40:14 UTC
Patches welcome to add diagnostics to the C++ frontend.
Comment 12 Tony Garland 2010-01-27 19:01:53 UTC
Here's a modified version of the original code which is intended to show just how arbitrary the compiler optimization is from a programmer's perspective. Here are two loops: one exits as expected, the other does not.  The only difference between the two loops is the use of an automatic variable in one of the two inline functions which test the exist condition.  Is this really how you want gcc to operate?  Is it truly acceptable to the general programming population that such a subtle difference in a supporting function can lead to a forever loop in one case and not in another?

Both of the range testing functions perform the comparison with all their arguments promoted to int. Yet one never returns false.

// Compile and run: g++ -O2 test.cpp && ./a.out
#include <stdio.h>

enum ENUM_VALUE
{
    ENUM_VALUE_FIRST = 1,
    ENUM_VALUE_A,
    ENUM_VALUE_B,
    ENUM_VALUE_C,
    ENUM_VALUE_D,
    ENUM_VALUE_E,
    ENUM_VALUE_LAST
};

inline bool enumInRangeWorks(const ENUM_VALUE& eVal)
{
    int val = eVal;
    return (
        (static_cast<int>(ENUM_VALUE_FIRST) <= val) &&
        (val <= static_cast<int>(ENUM_VALUE_LAST))
    );
}

inline bool enumInRangeFails(const ENUM_VALUE& eVal)
{
    return (
        (static_cast<int>(ENUM_VALUE_FIRST) <= static_cast<int>(eVal)) &&
        (static_cast<int>(eVal) <= static_cast<int>(ENUM_VALUE_LAST))
    );
}

main()
{
    printf("Compiled on %s %s\n", __DATE__, __TIME__);

    // This loop works correctly. The extra counter is not needed.
    unsigned int count = 0;
    for (
        ENUM_VALUE id = ENUM_VALUE_FIRST; 
        enumInRangeWorks(id); 
        id = static_cast<ENUM_VALUE>(id + 1)
    )
    {
        printf("id=%d\n", id);

        // Should never need to exit this way.
        if (10 == count++) break;
    }
    printf("ENUMERATION COMPARISON ");
    printf("%s\n", count < 10? "WORKED" : "FAILED");

    // This loop fails to exit. Without the special case additional
    // counter it results in a forever loop.
    count = 0;
    for (
        ENUM_VALUE id = ENUM_VALUE_FIRST; 
        enumInRangeFails(id); 
        id = static_cast<ENUM_VALUE>(id +1)
    )
    {
        printf("id=%d\n", id);

        // Should never need to exit this way.
        if (10 == count++) break;
    }
    printf("ENUMERATION COMPARISON ");
    printf("%s\n", count < 10? "WORKED" : "FAILED");
}

I'm sure the response is likely to be "the version that happens to work is invalid and therefore this is a moot point."  That may be, but it does illustrate how misleading gcc is when it allows code like this to compile without warning and then behaves radically differently for minor variations.
Comment 13 Andrew Pinski 2010-01-27 19:10:22 UTC
Well the behavior as defined by the C++ standard is explicitly unspecified so GCC is ok to what it does.
Comment 14 Tony Garland 2010-01-27 20:03:04 UTC
Yes, I'm now aware that gcc "meets the minimal requirements" of the C++ standard. That isn't my point. My point is whether what it does is acceptable behavior given that there are no warnings or errors.  And I'm suggesting that it should either:

1. Be modified to work with all enumeration values (in or out of range) that fit within a byte.  This would make the compiler OPERATE THE SAME WAY in all scenarios in the lion's share of situations.

2. Issue a warning or error when the programmer accidentally relies upon values outside of the defined enumeration range: period. (For sure when the enumeration happens to have 3, 7, 15, 31, 63, 127, etc. as the largest value--but better in all cases.)

The issue is that gcc, in its present operation does not help the programmer and in fact is misleading. It should either be practical and provide support for what many programmers expect--no matter what the optimization level--or it should flag it as bad code and refuse to run it at any optimization level. The situation where it silently accepts it and runs it in the 99% case, but then converts it silently to a forever loop in the 1% case is simply a recipe for trouble.

So does the C++ standard say that it is acceptable for the compiler to drop support for an out-of-range enumeration value in a way that the programmer has no idea it happens--but to support out-of-range enumeration values in other situations?

In other words, if gcc is so provably correct according to the standard in refusing to support an out-of-range-by-one enumeration value, why does it run the code at lesser optimization levels? Couldn't the fact that it runs the code without complaint in the majority of cases by considered a bug?
Comment 15 Andrew Pinski 2010-01-27 20:24:13 UTC
Think of overflow, it is overflowing the range.  We don't warn for integer overflow for loops as that would make the noise level huge for most code.
Comment 16 Tony Garland 2010-01-27 20:39:53 UTC
Your analogy is helpful, but a bit like comparing apples with oranges.  The reason being that the compiler executes integer overflow loops identically for all optimization settings.

The following program compiles without warning at all optimization levels and executes as a forever loop in all cases:

#include <stdio.h>
main()
{
    for (unsigned char i = 1 ; i <= 255 ; i++)
    {
        printf( "%d ", i);
    }
}

This example supports my point that the compiler ought not to silently convert an exiting loop into a forever loop based on optimizer settings because in this case it consistently operates the same--and testing will be sure to catch it if it is unintended.

Having now given up on trying to convince the gcc folks that enumeration testing would be greatly facilitated by extending the allowable comparison range by 1 (in both directions), my point has reduced itself to saying that the compiler is essentially whimsical and unpredictable in that code that runs as expected 99% of the time becomes an infinite loop without warning in the 1% case.  This is not what happens with integer overflow.

I submit that if the above integer example operated like enumerations--causing a terminated loop 99% of time but converting to a forever loop at -O2, then the compiler would have been modified long ago because lots more people would have been tripped up by it.
Comment 17 Andrew Pinski 2010-01-27 20:43:49 UTC
> Your analogy is helpful, but a bit like comparing apples with oranges.  The
> reason being that the compiler executes integer overflow loops identically for
> all optimization settings.

Is it?  unsigned integers don't overflow by definition.  They wrap.  Now signed integers overflow and change with different optimization levels.  That is what I was trying to compare with this case, not unsigned integer wrapping.
Comment 18 Tony Garland 2010-01-27 20:56:38 UTC
Thanks for the correction - I missed that aspect.

However, a signed version of my simple example still upholds what I'm trying to comment on: it behaves the same way regardless of optimization level (at least as far as the loop exit is in view) -- a forever loop.

#include <stdio.h>
main()
{
    for (char i = 1 ; i <= 127 ; i++)
    {
        printf( "%d ", i);
    }
}

This program is always a forever loop, regardless of optimizer setting.  The enumeration situation is not--which is my main point: trying to avoid surprising unexpected changes in operation as one changes the optimizer setting.

Incidentally, in the above program, the actual print results differ between -O0 and -O2. At -O0 the printed values increment up to 127 and then, as expected change to -128 and count upwards.  At -O2 the values increment up to 127 and then continue upward to huge positive integer values (e.g., I terminated the test at 4101552 and counting).  It seems at -O2 that the value is no longer considered 8-bit signed.

In any case, the forever loop remains a forever loop and doesn't morph into anything radically different.
Comment 19 Andrew Pinski 2010-01-27 21:08:30 UTC
Try:
#include <stdio.h>
main()
{
    for (signed char i = 1 ; i >= -2 ; i++)
    {
        printf( "%d ", i);
    }
}

The first one will never overflow the integer range as you have i <= 127 which is always true with no overflow happening.
Comment 20 Andrew Pinski 2010-01-27 21:10:12 UTC
(In reply to comment #19)
> Try:
Actually that code is defined as signed char++ is defined to be signed char = (signed char) ((int)i + 1); by the C/C++ promotion rules.

#include <stdio.h>
main()
{
    for (signed i = 1 ; i >= -2 ; i++)
    {
        printf( "%d ", i);
    }
}

---- CUT ---
That will cause different behavior at different optimization levels.
Comment 21 Tony Garland 2010-01-27 22:24:48 UTC
Thanks for that last example which does illustrate a condition where -O0 terminates and -O2 never does.  So we've established there are other looping situations where the compiler does the same thing as in the enumeration examples above and converts a finite loop at -O0 to an infinite loop at -O2.  So the enumeration behavior is not unique.

But does that really establish that this what the compiler should do (I know it is "free to" do it, but should it)?  Surely the bulk of programmers would find this surprising and disconcerting! Isn't it more likely to contribute to a serious failure in the field some day?  Especially in situations where the enumeration values are well within an 8-bit quantity.

In any event, I'm still wondering though about how similar in practice your example is to the enumeration situation? How much typical looping code is written as your example shows.  In other words, it would be very rare to encounter in typical code. For one, you are not testing against a value at the top end of its defined range.

I guess I don't have anything more to say by way of appeal other than this is one of those situations which may be "technically correct" and make some compiler implementers satisfied, but which will continue to trip up programmers who simply are trying to get something to work and are unaware of the dangers of combining enumeration range checks + enumeration values ending just before a power of two + -O2.

Is it really true that providing a warning whenever a comparison results in an implied check against a value beyond the range of the native type would cause lots of grief for existing code?  I guess I haven't seen situations where people make such comparisons and they don't expect them to work.

Anyway, it seems clear I'm unable to make enough of a case to motivate gcc developers to consider changing the behavior of the compiler and we'll have to live with the situation.

Thanks for your patience and explanations.
Comment 22 Jonathan Wakely 2010-01-28 10:13:58 UTC
(In reply to comment #14)
> 
> So does the C++ standard say that it is acceptable for the compiler to drop
> support for an out-of-range enumeration value in a way that the programmer has
> no idea it happens--but to support out-of-range enumeration values in other
> situations?

The standard says nothing about warnings, a program is either correct or not. If it's not correct, the standard doesn't apply.  The standard only defines what happens if you stick to its rules. It can't possibly legislate what happens if you go outside those rules, pretty much by definition.
 
> In other words, if gcc is so provably correct according to the standard in
> refusing to support an out-of-range-by-one enumeration value, why does it run
> the code at lesser optimization levels? Couldn't the fact that it runs the code
> without complaint in the majority of cases by considered a bug?

No. Undefined behaviour is undefined, not defined to behave consistently at all optimisation levels.
 
I think a warning for this would be helpful, but asking for the compiler to assume types can have values that they can't have is not a good idea.
Comment 23 Tony Garland 2010-01-28 17:16:57 UTC
Jonathan,

Thanks for explaining that operation outside the norm is unspecified such
that the compiler can do anything and everything.

>I think a warning for this would be helpful, but asking for the compiler to
>assume types can have values that they can't have is not a good idea.

In the absence of making enumerations more useful (in the standard--which is unlikely), I completely agree: a warning would be helpful.

Enough said by me.
Comment 24 Jason Merrill 2010-05-04 04:47:23 UTC
G++ 4.6 will no longer optimize away the exit condition unless -fstrict-enums is specified.
Comment 25 Tony Garland 2010-05-04 16:06:42 UTC
(In reply to comment #24)
> G++ 4.6 will no longer optimize away the exit condition unless -fstrict-enums
> is specified.
> 

I'm very encouraged by this.  Thanks for responding to this concern.