Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks [LWN.net]

John Regehr explains how new optimizations in GCC 4.8.0 can break code making use of undefined behavior. "A C compiler, upon seeing d[++k], is permitted to assume that the incremented value of k is within the array bounds, since otherwise undefined behavior occurs. For the code here, GCC can infer that k is in the range 0..15. A bit later, when GCC sees k<16, it says to itself: 'Aha-- that expression is always true, so we have an infinite loop.'"

(Log in to post comments)

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 13:48 UTC (Sat) by Thue (subscriber, #14277) [Link]

Doing whatever with undefined behavior is fine. But GCC must do everything it can to warn the programmer when it encounters undefined behavior.

My impression is that GCC is doing a poor job of that; as noted in the article, it doesn't give a warning with -O2. GCC should exist to help the programmer, not to follow the spec at any cost, and ignore the programmer's needs. If GCC can't give proper warnings, then they should turn off the optimizations, IMO.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 15:22 UTC (Sat) by ssam (subscriber, #46587) [Link]

its not so much that the compiler has gone, 'ah huh, this function is undefined so i can replace it with whatever i like'. more that its gone, 'You used dd=d[++k], so if you are assuming that k will always be less that 16, then i can assume that too, hence i'll replace "k<16" with "true".' once it has made that step, it can see that the loop will never finish, and so the function will never return, so why bother calculating anything.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 16:16 UTC (Sat) by HelloWorld (guest, #56129) [Link]

That is an academic distinction. The point is that gcc should give a warning when one uses a very unusual syntax like k < 16 to express 1, because chances are that wasn't the original intent.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 16:38 UTC (Sat) by ssam (subscriber, #46587) [Link]

a 'expression always evaluates to true' or 'expression always evaluates to true' warning. It might be a pain for bits of code that you want the compiler to remove.

I sometimes use code like:

int a[] = {6,8,3};
...
for (int i=0; i<(sizeof(a)/sizeof(int)); i++){
done_stuff_with(a[i]);
}
...

maybe because i want to check if a particle in a simulation is in one of my regions of interest. I may often modify a, and then recompile the code (in my work its not unusual to recompile code before each run). Sometimes a will just be {}, so i would like the compiler remove the loop.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 17:32 UTC (Sat) by apoelstra (subscriber, #75205) [Link]

> maybe because i want to check if a particle in a simulation is in one of my regions of interest. I may often modify a, and then recompile the code (in my work its not unusual to recompile code before each run). Sometimes a will just be {}, so i would like the compiler remove the loop.

I do this too, and I also compile with -Werror, but IMHO I'd rather have the warning than not. A simple (ugly) solution is to couch your loop in #ifdef's, and just flip a preprocessor variable.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 5:31 UTC (Tue) by bronson (subscriber, #4806) [Link]

I think ifdefs would fall apart too quickly to be of much use.

Compiler warnings would too... If the compiler emits 22 "might be true" warnings, and 21 of them are spurious, what are the chances I'll catch the meaningful one? Knowing me, probably next to nil.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 18:24 UTC (Sat) by smurf (subscriber, #17840) [Link]

>> The point is that gcc should give a warning when one uses a very
>> unusual syntax like k < 16 to express 1, because chances are that
>> wasn't the original intent.

The problem is that this kind of thing comes up in macros all the time, esp. in hand-optimized libraries. "(Foo < 8) ? _handcoded_special_function() : _generic_function()" is a common-enough idiom. You cannot just warn about that.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 18:52 UTC (Sat) by mansr (guest, #85328) [Link]

A common strategy is to not warn for integer constant expressions used in conditions while warning if a condition involving a non-constant expression is provably invariant.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 25, 2013 13:37 UTC (Mon) by dlthomas (guest, #89935) [Link]

Fortunately, GCC 4.8 also keeps track of what code is the result of expansion of what macros...

Regehr: GCC 4.8 (pre-release) Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 18:27 UTC (Sat) by mjw (subscriber, #16740) [Link]

Note that the original article was testing a pre-release GCC 4.8. The final version of GCC 4.8 contains the following bug fix:

Bug 53265 - Warn when undefined behavior implies smaller iteration count

And the GCC 4.8 Release Notes were updated to explain:

In some loops that have known constant number of iterations, but undefined behavior is known to occur in the loop before reaching or during the last iteration, GCC will warn about the undefined behavior in the loop instead of deriving lower upper bound of the number of iterations for the loop. The warning can be disabled with -Wno-aggressive-loop-optimizations.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 15:31 UTC (Sat) by proski (subscriber, #104) [Link]

It's actually a common programming mistake often found by Valgrind. I'm afraid the new gcc would generate the code that would behave in unexpected ways without triggering Valgrind warnings.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 25, 2013 13:41 UTC (Mon) by dlthomas (guest, #89935) [Link]

It's not constraining the lookup, which would make valgrind miss it, but constraining its later assumptions about the variable.

int d[16];

d[k] = 10; /*A*/

if(/*B*/ k < 16) {
...
}

The idea is that when it hits A, if that expression would be false, behavior is already undefined because of what happened at B, so let's optimize for the case that didn't segfault (or corrupt data).

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 14:13 UTC (Sat) by juzzor (subscriber, #89840) [Link]

This issue was fixed before the final release yesterday.
So gcc-4.8.0 is actually fine and John must have used a prerelease
version/

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 14:37 UTC (Sat) by felixfix (subscriber, #242) [Link]

What does the final 4.8.0 release do?

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 14:46 UTC (Sat) by juzzor (subscriber, #89840) [Link]

% gcc -S -o - -O2 test.c
        .file   "test.c"
        .section        .text.startup,"ax",@progbits
        .p2align 4,,15
        .globl  main
        .type   main, @function
main:
.LFB0:
        .cfi_startproc
        movl    d(%rip), %ecx
        movl    $d+4, %edx
        xorl    %eax, %eax
        .p2align 4,,10
        .p2align 3
.L3:
        movl    %ecx, %esi
        addq    $4, %rdx
        sarl    $31, %esi
        xorl    %esi, %ecx
        subl    %esi, %ecx
        addl    %ecx, %eax
        movl    -4(%rdx), %ecx
        cmpq    $d+68, %rdx
        jne     .L3
        rep ret
        .cfi_endproc
.LFE0:
        .size   main, .-main
        .comm   d,64,32
        .ident  "GCC: (GNU) 4.8.0"
        .section        .note.GNU-stack,"",@progbits

 % gcc -v
Using built-in specs.
COLLECT_GCC=/usr/x86_64-pc-linux-gnu/gcc-bin/4.8.0/gcc
COLLECT_LTO_WRAPPER=/usr/libexec/gcc/x86_64-pc-linux-gnu/4.8.0/lto-wrapper
Target: x86_64-pc-linux-gnu
Configured with: /home/markus/gcc/configure --prefix=/usr --bindir=/usr/x86_64-pc-linux-gnu/gcc-bin/4.8.0 --includedir=/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.0/include --datadir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.8.0 --mandir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.8.0/man --infodir=/usr/share/gcc-data/x86_64-pc-linux-gnu/4.8.0/info --with-gxx-include-dir=/usr/lib/gcc/x86_64-pc-linux-gnu/4.8.0/include/g++-v4 --host=x86_64-pc-linux-gnu --build=x86_64-pc-linux-gnu --disable-altivec --disable-fixed-point --without-ppl --without-cloog --enable-lto --enable-nls --without-included-gettext --with-system-zlib --disable-werror --enable-initfini-array --with-gold --enable-secureplt --disable-multilib --enable-libmudflap --disable-libssp --disable-libgomp --enable-cld --with-python-dir=/share/gcc-data/x86_64-pc-linux-gnu/4.8.0/python --enable-checking=release --disable-libgcj --enable-languages=c,c++,fortran --enable-shared --enable-threads=posix --enable-__cxa_atexit --enable-clocale=gnu --with-build-config=slim-lto-bootstrap --with-boot-ldflags=-Wl,-O1,--hash-style=gnu,--as-needed,--gc-sections,--icf=safe,--icf-iterations=3 --enable-version-specific-runtime-libs --disable-libstdcxx-pch --enable-libstdcxx-time=yes
Thread model: posix
gcc version 4.8.0 (GCC)

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 15:25 UTC (Sat) by proski (subscriber, #104) [Link]

It would be more interesting to know the description of the commit that changed the behavior. As others wrote, it would be nice if gcc emitted a warning ("comparison is always true") regardless of the code it generates.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 15:46 UTC (Sat) by khim (subscriber, #9252) [Link]

It's easy to do, but you'll be surprised to see just how many such warnings typical code will generate. There are lots of idioms explicitly built around them (think "do { ... } while (TRUE)" defines and recall that TRUE is often is defined "(!FALSE)").

It's trivial to produce bazillion "comparison is always true" warnings or not produce anything at all. To produce meaningful number of warnings… that's different story… it's really hard.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 17:54 UTC (Sat) by HelloWorld (guest, #56129) [Link]

> It's easy to do, but you'll be surprised to see just how many such warnings typical code will generate. There are lots of idioms explicitly built around them (think "do { ... } while (TRUE)" defines and recall that TRUE is often is defined "(!FALSE)").
You could omit the warning whenever the expression to be tested is a constant-expression as defined by the C standard. The code to test for that is already there, so it should be trivial. In any case, it's time for the GCC developers to think about these issues, it's not the first time something like that comes up after all.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 8:26 UTC (Tue) by mlopezibanez (guest, #66088) [Link]

The code that is always true might not have been even written by the user, but come from a system header file, a macro expansion (but not a constant expression), or generated code (very common in C++), from transformations of the code that don't match any original code, etc.

Regardless, there are very few GCC developers, so if you think you could do something better, you should give it a try. Sometimes you realize how difficult your obvious thing turns out to be, and other times you realize that it was indeed obvious but nobody had time to do it before. I can tell you from personal experience that there is a lot of the latter in GCC.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 15:49 UTC (Sat) by juzzor (subscriber, #89840) [Link]

The fix is this commit by Jakub:

http://gcc.gnu.org/git/?p=gcc.git;a=commitdiff;h=228bf2b8...

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 15:51 UTC (Sat) by mlopezibanez (guest, #66088) [Link]

GCC doesn't say: "Aha- let's replace this broken code with an infinite loop"

It is more like: "k is in the range 0..15, so this test I just found for k<16 is redundant, so change it to always true." It doesn't know that the test is used for exiting the loop. Well, in this simple case it does, and it should warn with -Waggressive-loop-optimizations. In other cases, the optimization can be disabled with -fno-aggressive-loop-optimizations.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 25, 2013 20:37 UTC (Mon) by xorbe (subscriber, #3165) [Link]

OTOH, the compiler should know:
#1 k starts as zero
#2 k is incremented every loop, which is its only assignment point.
#3 k is 16 when the loop stops.

Therefore, it also can't be an infinite loop.

> It doesn't know that the test is used for exiting the loop.

What nonsense is this. "k<16" is the exact test in the for loop! Anyways, glad to know the situation is better than the initial blog post.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 25, 2013 21:09 UTC (Mon) by mansr (guest, #85328) [Link]

The problem is that the source code is self-contradicting when interpreted strictly. While your observation is correct, the source also implicitly (through the d[k] array access) promises that k < 16. When given conflicting information like this, the interpretation is unpredictable. That is (part of) what undefined behaviour means. Get over it.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 0:57 UTC (Tue) by nix (subscriber, #2304) [Link]

The 'nonsense', btw, is that the optimization pass which is coming to conclusions about the conditional test does not care where that test is located: in particular, it doesn't know nor care that it might be bounding a for loop. Generality in optimizations is generally a good thing...

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 16:31 UTC (Sat) by dougg (subscriber, #1894) [Link]

While on the subject, C seems to give a guarantee that the address one above the top of an array is valid for comparison purposes, as long as it is not de-referenced. What about those folks with similar logic going through an array backwards? IOW what about the address prior to index 0 ('arr - 1' so to speak)?

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 16:52 UTC (Sat) by mansr (guest, #85328) [Link]

You're not allowed to even think about that address.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 22:46 UTC (Sat) by Trelane (subscriber, #56877) [Link]

What address?

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 23:05 UTC (Sat) by mansr (guest, #85328) [Link]

Any address below the start of an (array) object.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 24, 2013 1:42 UTC (Sun) by wahern (subscriber, #37304) [Link]

*whoosh* :P

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 17:21 UTC (Sat) by jedbrown (subscriber, #49919) [Link]

It's disappointing that SPEC refuses to fix the code and is spreading misinformation like "it is at minimum arguable that the code fragment is compliant under the C89 standard". If the global 'int d[16]' is placed at the very end of a page (which the linker is allowed to do), their code compiled in the most naive possible way will SEGV.

SPEC 2006

Posted Mar 23, 2013 23:10 UTC (Sat) by tialaramex (subscriber, #21167) [Link]

Sure, but on the other hand it's possible to sympathise with their argument that SPEC represents fragments of real code. Probably anybody here who has read a lot of C code has seen people doing things much like this. It's /legal/ for GCC to break all those programs, but it's probably not desirable and so I'm glad they changed that for release.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 17:22 UTC (Sat) by butlerm (subscriber, #13312) [Link]

Wouldn't it be a lot safer in such cases to stop with an error? To refuse to compile until the problem is fixed? Any optimization so radical that it replaces behavior that is undefined some of the time behavior that is undefined all of the time isn't worth having. Stopping and forcing the developer to fix the problem or to use an option to ignore it is much friendlier than an ad lib the developer has given us a license to do anything approach.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 22:08 UTC (Sat) by dvdeug (subscriber, #10998) [Link]

No, because it's impossible for the compiler to tell when it's a bug or not. If you don't want "Any optimization so radical that it replaces behavior that is undefined some of the time [with] behavior that is undefined all of the time", there's a command-line option for that, -O0. These optimizations aren't radical. Why are you using C if you aren't wanting to trade off safety for speed, anyway?

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 24, 2013 1:01 UTC (Sun) by iabervon (subscriber, #722) [Link]

The point is that GCC doesn't think you'll actually reach the undefined behavior part of the loop. Say you've got:

static inline int framelen(char s[]) {
  for (int i = 0; i < 256; i++) {
    if (!s[i])
      return i;
  }
  return i;
}

If you call this with a nul-terminated char array, or any array of at least 256 chars, it is well-defined. If you call it with a nul-terminated array of less than 256 chars, it will be faster if it uses an unconditional branch. It assumes that the programmer has some good reason to believe that short arrays are nul-terminated, which the compiler can't necessarily figure out.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 3:28 UTC (Tue) by butlerm (subscriber, #13312) [Link]

The difference is that in the original example the compiler can prove that an out of bounds array access will occur under all input conditions. This should be considered an error. Dividing by a constant zero is a similar example. What possible good could come from the compiler just making something up in a situation like that?

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 4:12 UTC (Tue) by iabervon (subscriber, #722) [Link]

It's not actually able to prove that (or, really, it's not set up to consider proving that type of thing). It's actually just making a series of optimizations: first, it assumes that there won't be an out-of-bounds access, then it determines that this means that the loop can't exit normally (like in my example), then it finds that the return is unreachable, then it finds that the value being calculated is unused, then it finds that nothing is needed except for the infinite loop. Each of these optimizations improves the performance of some correct code, and it doesn't have the deeper analysis to notice that it can prove that the loop executes 16 times in violation of the assumption.

It doesn't really have an overall knowledge set that could find contradictions; it's got patterns that produce warnings and patterns that produce optimizations, and so it can't tell when optimizations are leading to total nonsense.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 5:10 UTC (Tue) by dlang (✭ supporter ✭, #313) [Link]

and the mistake in the chain of reasoning is the very first one where it assumes that the loop variable will never be out of range..

The rest of the optimizations make sense, but that first one is optimistic thinking on the part of the compiler writer.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 8:39 UTC (Tue) by mlopezibanez (guest, #66088) [Link]

No, the assumption is how C programs work. It is in general impossible to tell if there is going to be an out-of-bounds access without checking every access. If you want code that checks that, then wrap every array access in the equivalent of vector.at() and let the compiler try to remove redundant checks.

Of course, GCC could do better at static analysis and warning about such cases, but that is a different problem from optimization, and GCC needs new developers that are interested in such things.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 27, 2013 22:27 UTC (Wed) by HelloWorld (guest, #56129) [Link]

> and the mistake in the chain of reasoning is the very first one where it assumes that the loop variable will never be out of range.
That's not the chain of reasoning. The reasoning is that if the loop variable is out of range, the program's behaviour is undefined, thus not testing the variable is just as valid as testing it or doing something else entirely.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 27, 2013 19:23 UTC (Wed) by HelloWorld (guest, #56129) [Link]

Use the string.h, Luke!

static inline int framelen(char s[]) {
  return strnlen(s, 256);
}

;)

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 23, 2013 20:23 UTC (Sat) by stevenb (guest, #11536) [Link]

Sloppy reporting of a non-issue, with sloppy reporting of the message that the non-issue was fixed before GCC 4.8 was released.

Nothing to see, move along...

access off end of array

Posted Mar 24, 2013 0:46 UTC (Sun) by pflugstad (subscriber, #224) [Link]

Couldn't doing a read off the end of an array potentially cause a segfault? Depending on how the array was allocated? If so, seems to me like this is just buggy code, plain and simple.

I also think this code is confusing and poor coding style. Why even have dd? I think this code:

    int d[16];
    int SATD (void)
    {
      int satd = 0, k;
      for ( k=0; k<16; k++ ) {
        satd += (d[k] < 0 ? -d[k] : d[k]);
      }
      return satd;
    }

is cleaner, easier to understand and maintain, and eliminates the bug. With any optimization at all, GCC should eliminate the repeated d[k] accesses so I would expect almost identical code and performance. Maybe I'm just missing something? Even if you leave dd in there, doing the assignment inside the block is cleaner and easier to understand than inside the for loop.

I also think that GCC using a undefined data access to essentially short circuit a for loop control variable is just busted - and it looks like they fixed this before the final GCC was actually released.

access off end of array

Posted Mar 24, 2013 1:55 UTC (Sun) by pflugstad (subscriber, #224) [Link]

DOH - I completely missed butlerm's comment... so yeah, it can SEGFAULT.

And I still think it's buggy and unclear code.

access off end of array

Posted Mar 24, 2013 6:53 UTC (Sun) by alankila (subscriber, #47141) [Link]

You don't understand. C developers pride themselves for having come up with these ugly and confusing functions, which perhaps once in history, long time before any of us were born, produced better code from some compiler someone's grandfather used in their youth. Or maybe the grandpa just thought so, or was terribly drunk while writing the code, or experimented with just how much he could get away with using that particular compiler and optimization level. Grandpa was known for being bit unruly. The point is, this specific written form is now hallowed by history and tradition, and therefore can't be changed, and any compiler who dares to break it is immediately at fault.

access off end of array

Posted Mar 25, 2013 19:27 UTC (Mon) by tjc (subscriber, #137) [Link]

If you trace this back to the root problem you may come to the conclusion that changing the state of a variable in a non-assignment expression can be more trouble than it's worth, especially if you're dealing with concurrency. A language that allows

i++;

as a stand-alone statement would be a useful compromise, since it could still be used as the increment statement in a for loop, which is by far the most common idiom for this construct.

access off end of array

Posted Mar 25, 2013 23:13 UTC (Mon) by HelloWorld (guest, #56129) [Link]

The only reason i++ and --i were invented is that that made it possible to generate more efficient code for the PDP-11 with simple-minded compilers. There's no reason for them nowadays as i +=1 is almost as short and most languages today also feature a proper for loop.

access off end of array

Posted Mar 26, 2013 0:34 UTC (Tue) by tjc (subscriber, #137) [Link]

Actually, the ++/PDP-11 connection is urban legend -- see "More History", paragraph 2 at this link:

The Development of the C Language

I think i++ is fine from a syntax point of view, so long as it's a stand-along statement, where it produces the same code as i += 1. But I try to avoid embedding increment operators within expressions that produce easily overlooked side effects.

access off end of array

Posted Mar 26, 2013 9:00 UTC (Tue) by khim (subscriber, #9252) [Link]

Actually, the ++/PDP-11 connection is urban legend -- see "More History", paragraph 2 at this link:

The Development of the C Language

Well, your own link shows that it's not an "urban legend" but more like oversimplification: This is historically impossible, since there was no PDP-11 when B was developed. The PDP-7, however, did have a few `auto-increment' memory cells, with the property that an indirect memory reference through them incremented the cell. This feature probably suggested such operators to Thompson; the generalization to make them both prefix and postfix was his own.

While factually incorrect (C design predates PDP-11) both "++" in C and "(RX)+" in PDP-11's assembler come from the same source.

access off end of array

Posted Mar 26, 2013 16:04 UTC (Tue) by hummassa (subscriber, #307) [Link]

I know for a fact the 6809 microprocessors had some instructions "load/store from pointer with post/pre-auto-increment/decrement" so that one of:

a = *b++
a = *++b
a = *b--
a = *--b
*b++ = a
*++b = a
*b-- = a
*--b = a

was a single instruction; they made easy to implement real fast stacks and queues, and zero-terminated strings (because "a = *b++" &c set the Z flag if the char was zero).

access off end of array

Posted Mar 26, 2013 16:52 UTC (Tue) by brouhaha (subscriber, #1698) [Link]

Yes, but the 6809 came along much later than the PDP-11, so it's not relevant to discussion of where the C pre/post-increment/decrement operators came from.

access off end of array

Posted Mar 26, 2013 8:09 UTC (Tue) by alankila (subscriber, #47141) [Link]

I guess there would be many ways to improve C, which largely are about breaking expressions that used to work but which are ugly, confusing and sometimes semantically broken. Perhaps GCC can slowly over time nudge people away from doing multiple things in a single statement -- that definitely sounds like an improvement.

access off end of array

Posted Mar 26, 2013 16:26 UTC (Tue) by tjc (subscriber, #137) [Link]

I think a warning flag would be a step in the right direction, and maybe as far as things should to go. -Wall doesn't warn against this sort of thing, but since the "all" in -Wall is not really all, there might already be a flag for this.

access off end of array

Posted Mar 24, 2013 19:02 UTC (Sun) by iabervon (subscriber, #722) [Link]

Probably the real reason to have this in a benchmark is because it's stupid. Unless your compiler does particularly good flow control analysis, it'll generate a read of d[16], which is a likely cache miss (if the compiler aligns the array, there's a good chance that d[16] will be in a different cache line from d[15] and anything else that's hot). If the compiler can figure out that dd isn't used outside the loop, and that it can therefore be set after the test instead of before, you'll get code that runs faster than if the compiler is less clever. Of course, if you wanted to get a fast result, you'd just write it the obvious way and get the optimal result on any compiler, but they want to have some compilers do better than other compilers.

It's like writing an exam question: it would be easy to write a question that everybody would get right, but you want to write a question that people who know the material will get right more often than people who don't. Obviously, in ordinary life, you want to ask questions which will be more likely to get correct answers, and you want to write code that all compilers will make as fast as possible, but that's not the situation here.

access off end of array

Posted Mar 25, 2013 5:09 UTC (Mon) by cesarb (subscriber, #6266) [Link]

Except that it is not an "exam question". It is supposed to be real code, in this case from a reference implementation of the H.264 codec.

It was not written to stress test compilers. It is just not very optimized (and since it is only a reference implementation, it does not have to be).

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 25, 2013 7:53 UTC (Mon) by jakub@redhat.com (subscriber, #31780) [Link]

BTW, if you want some testcase where -fno-aggressive-loop-optimizations still makes a difference even in GCC 4.8.0 release, one testcase is e.g.:
int a[4];

__attribute__((noinline, noclone)) int
foo (int x)
{
int i, r = 0, n = x & 31;
for (i = 0; i < n; i++)
r += a[i];
return r;
}

int
main ()
{
int x = 255;
__asm volatile ("" : "+r" (x));
return foo (x);
}
. With -O3 and not -fno-aggressive-loop-optimizations, GCC from the loop determines the high bound to be 4 and completely unrolls the loop into 4 reads from a (+ additions for 2nd and up iteration) preceeded each by test of the n variable, so the code won't actually read beyond end of a array, while with -O3 -fno-aggressive-loop-optimizations GCC won't compute the upper bound estimate so low (VRP can figure out it is 32, while other passes just estimate INT_MAX), so the loop happily will read beyond end of a, is vectorized (which is unlikely desirable for such small number of iterations), etc. Even without the "& 31" the situation is similar, and certainly for that case I don't see why a warning would be ever useful, the routine just can be valid only when called with a parameter 0 to 3, but there is no reason not to assume all the callers don't do that (the asm is optimization barrier, the compiler isn't supposed to look through it).

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 25, 2013 10:12 UTC (Mon) by jezuch (subscriber, #52988) [Link]

> "Because the SPEC CPU benchmarks are drawn from the compute intensive portion of real applications"

Well...

> for (dd=d[k=0]; k<16; dd=d[++k])

That's.... horrifying.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 25, 2013 15:43 UTC (Mon) by hthoma (subscriber, #4743) [Link]

> > for (dd=d[k=0]; k<16; dd=d[++k])

> That's.... horrifying.

Exactly. Looks like obfuscated C contest stuff ...

I would guess that if you write it the "normal" way, i.e.

for(k = 0; k < 16; k++) {
dd = d[k];
satd += (dd < 0 ? -dd : dd);
}

the compiler would not optimize the code to an infinite loop and get a better chance to optimize.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 8:02 UTC (Tue) by jezuch (subscriber, #52988) [Link]

> Exactly. Looks like obfuscated C contest stuff ...

I guess it's a result of a *very* popular misconception that the more you cram into a single statement the faster it is ;)

Seeing how the compiler unwinds all of this stuff is an eye-opening experience. We, humans, have a very limited operating memory; the compiler can analyze much, much larger structures than we imagine it can.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 26, 2013 9:44 UTC (Tue) by khim (subscriber, #9252) [Link]

It may not run faster, but it certainly is shorter and a lot of guys (including me) always try to make code shorter.

It's funny, really: it looks like I've finally found where these clashes come from. Less them two years ago I had no idea and struggled to understand, but now, after a lot of discussions with other guys on an important piece of code in our project, I know that there are two types of programmers: the ones who think about their program in C (C++, C#, Java, JavaScript (uh-oh), PHP (ugh), Python, etc) and the ones who think about their program in English (Hebrew, Mandarin, Russian, whatever).

For the "C thinkers" size of the code is very important (the shorter it is the easier to observe large chunks of code at once) and most comments are just useless distraction (and/or admission of defeat: what, you mean this piece of code is so convoluted and cryptic that you can't understand it just from a C code... gosh I think it's time to give up and add couple of comments). Sure, high-level interface must be described in human language (C is great for low-level bit manipulations, but for description of relationship between HTML document and DOM tree, created from said document it's too low-level), but everything below it must be understandable from the code.

For "English thinkers" comments are vital piece of the information: they expect to fully understand the program from comments alone and perceive the need to actually read C code as something degrading (or as necessary evil when something does not work). Even if they read C code they usually just compare it to the comment near it (and they become angry when they found no comments to compare the code to). For them size of code is less important (because they only ever perceive it in small pieces) and verbose style is, actually, better (it makes it easier to compare code to comments).

I'm not sure which style is better, but I found that C thinkers usually produce fast and efficient code which may contain small, localized bugs (the code in article is prime example) while English thinkers produce code which is verbose and slow yet still contain plethora of bugs - but these bugs are distinctly different: instead of off-by-one errors or simple "++" vs "--" mixup we have cases where one module produces subtly broken object which is mishandled by another module and then everything blows up in a third one.

Easy to understand why: there are no "safety net" in C thinkers code thus localized bugs are easy to miss, but interfaces are very narrow and well-defined while English thinkers produce the code which is locally correct but globally they are hopeless because there are so many interactions between different pieces of code. Think XBox or Wii bootloader code (few bugs in the initial runs which were eventually ironed out and now there are no new bugs in sight) vs JVM code (there are endless bugs without the end in sight - and most of them are because different pieces of code interact "quirckly").

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 27, 2013 13:32 UTC (Wed) by nye (guest, #51576) [Link]

Oh please. Take your macho trolling somewhere else.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 27, 2013 15:16 UTC (Wed) by redden0t8 (guest, #72783) [Link]

Interesting observation, it really made me think.

I'm definitely a C-thinker, but over-shortening code (like in this article's example) really makes me cringe. I really don't understand the drive to make pieces of code as short as possible. I'm more along the lines of "clear and concise", with "clear" being more important than "concise". I guess you could think of it as writing code so as to optimize the time it takes to read and follow, rather than optimizing the line count.

Then again maybe this comes from being a hobbyist programmer and not a professional... maybe I just have a different definition of "clear" lol.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 27, 2013 17:43 UTC (Wed) by dlang (✭ supporter ✭, #313) [Link]

The balance between clear and concise will vary depending on how familiar you are with the language in question.

the obfuscated C contest shows clear examples where concise is far more important than clear.

But the line itself if rather fuzzy.

hijacking an example from elsewhere. If you have a bucket filled with water and start punching holes in the bottom, when does it stop being a bucket that leaks and start being a sieve? At some point it will be very clear that you have passed the line, but exactly where the line is is hard to define.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Mar 27, 2013 19:17 UTC (Wed) by HelloWorld (guest, #56129) [Link]

> It may not run faster, but it certainly is shorter
Uh, no it's not. The obfuscated version is 25 tokens, the sensible one is 22 tokens. Sure, if you use conventional formatting, you'll end up with one more line for the normal version, but nobody says you have to do that...

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Apr 1, 2013 14:51 UTC (Mon) by khim (subscriber, #9252) [Link]

Screen real estate is not measured in tokens. Inches, centimeters, may be pixels, but most definitely not tokens. But this measure it's shorter. Is it worth it? That's debatable and depends very much on the individual, but of course it's separate issue.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Apr 1, 2013 16:19 UTC (Mon) by hummassa (subscriber, #307) [Link]

isn's the "proper" c++ version

for(auto x: dd)
satd += abs(x);

?? (generates the same code, no errors and READABLE...)

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Apr 1, 2013 16:57 UTC (Mon) by hummassa (subscriber, #307) [Link]

Actually, "properest" version would be

auto satd = accumulate(begin(d), end(d), 0, [](int a, int x) { return a+abs(x); });

But I suppose that has the potential to be less efficient, at least it involves some function calls here...

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Apr 2, 2013 17:30 UTC (Tue) by hummassa (subscriber, #307) [Link]

I am answering to my own comments in this subthread, and it really feels like I am losing my mind... :-D
anyway, I tried this with -O4 and both


for(auto x: d) satd += abs(x);

and


auto satd = accumulate(begin(d), end(d), 0, [](int a, int x) { return a+abs(x); });

generated the same code, roughly:


movl	(%rax), %edx
movl	(%rax), %ecx
addq	$4, %rax    
sarl	$31, %edx   
xorl	%edx, %ecx  
subl	%edx, %ecx  
leaq	64(%rsp), %r
addl	%ecx, %ebx  
cmpq	%rax, %rdx  
jne	.L3	#,

which seemed nice to me.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Apr 2, 2013 19:17 UTC (Tue) by jwakely (subscriber, #60262) [Link]

You know GCC doesn't have a -O4 optimisation level, right? ;)

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Apr 2, 2013 20:08 UTC (Tue) by nix (subscriber, #2304) [Link]

I've seen people use -O4, -O6, -O64 ("it's a nice round number and higher than 3" he said, so at least he knew what he was aiming for), and of course glibc, of all things, used -O99 for donkey's years. GCC obviously needs an "-Olots" for these people.

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Apr 2, 2013 22:56 UTC (Tue) by jwakely (subscriber, #60262) [Link]

It should be called -Over9000 though

Regehr: GCC 4.8 Breaks Broken SPEC 2006 Benchmarks

Posted Apr 2, 2013 21:18 UTC (Tue) by hummassa (subscriber, #307) [Link]

It's on my default makefile since forever, because clang does not like -O5 and beyond and I am too lazy to look up which is the biggest effective level for each compiler...