Shortest example of code that is compiled and increasing the optimization level makes it take longer

Question

Just curious if someone can provide a short example of code that causes a compiler's optimizer to behave incorrectly:

• without optimization (or at lower optimization), code takes X seconds to run
• with optimization (or at higher optimization), code takes Y seconds to run where Y > X

In other words, the optimizer's cost model causes it to make a poor decision with a specific case, even though (presumably) it makes good decisions in general.

This is meant for C (with gcc the comparisons should be between -O0, -O1, -O2, -O3 in increasing order of optimization), but any compiled language should work.

Answer 1

C (gcc 6.2.0-5ubuntu12 x86_64), 58 bytes

typedef struct{long a,b}s;s f(long*c){return(s){*c,c[1]};}

Compiled with -O1, we get the following assembly code (minus boilerplate):

f:
    movq    8(%rdi), %rdx
    movq    (%rdi), %rax
    ret

With -O3, it looks like this:

f:
    movdqu  (%rdi), %xmm0
    movaps  %xmm0, -24(%rsp)
    movq    -24(%rsp), %rax
    movq    -16(%rsp), %rdx
    ret

This is obviously worse (the first version copies from memory to registers directly, the second version copies from memory into the wrong register, back into scratch space in memory, and then from there into the correct registers, which is just doing more work for no gain).

This is a pretty longstanding example of a silly gcc miscompilation. In older versions of gcc, the -O3 code was even worse (containing a full function setup/teardown sequence, stack protection checks, and the like); it seems to have improved somewhat in the more recent versions.

Incidentally, clang produces code almost identical to gcc's -O1 at any positive optimization level (the only difference is that sometimes the two assignments are done in the other order).