3

Background

Using gcc 7.2 I found that the compiler output changes when a loop iterates 999 times.

In particular this program (link to compiler explorer using gcc 7.2):

int f()
{
    int i=0x7fffffff-998;
    while (i+1>i)
        i++;
    return i;
}

compiles (using -O3 -fwrapv) to:

f():
  mov eax, 2147483647
  ret

but, if I change the 998 to 999, it instead compiles to:

f():
  xor eax, eax
  movdqa xmm0, XMMWORD PTR .LC0[rip]
  movdqa xmm2, XMMWORD PTR .LC1[rip]
  jmp .L2
.L3:
  movdqa xmm0, xmm1
.L2:
  movdqa xmm1, xmm0
  add eax, 1
  cmp eax, 250
  paddd xmm1, xmm2
  jne .L3
  pshufd xmm0, xmm0, 255
  movd eax, xmm0
  ret
.LC0:
  .long 2147482648
  .long 2147482649
  .long 2147482650
  .long 2147482651
.LC1:
  .long 4
  .long 4
  .long 4
  .long 4

Question

Why does the output change, and is there a switch to control the threshold at which the behaviour changes?

Note

As signed overflow is undefined behaviour, by default the compiler will turn this program into an infinite loop. This is why the -fwrapv option is needed during compilation.

Peter de Rivaz
  • 33,126
  • 4
  • 46
  • 75
  • 4
    Undefined behaviour is undefined behaviour. It could be an infinite loop. It could crash. It could do anything. – tadman Mar 01 '19 at 22:10
  • 6
    Signed overflow is UB; any attempts at reasoning about it are futile – Govind Parmar Mar 01 '19 at 22:11
  • 2
    @tadman I thought that signed overflow was well defined when using -fwrapv? Is this wrong? – Peter de Rivaz Mar 01 '19 at 22:17
  • 2
    I think you're misunderstanding [what that flag does](https://stackoverflow.com/questions/47232954/what-does-fwrapv-do). – tadman Mar 01 '19 at 22:24
  • @tadman Thanks, I am now interested in checking my understanding of -fwrapv so I will ask a separate question on that topic – Peter de Rivaz Mar 01 '19 at 22:29
  • I suppose gcc propagates constants with limit of 1000 iterations (or several thousand operations). – zch Mar 01 '19 at 22:35
  • @tadman How so? – melpomene Mar 01 '19 at 23:12
  • 1
    In case anyone is interested, my new question about -fwrapv is [here](https://stackoverflow.com/questions/54953219/is-signed-overflow-still-undefined-behaviour-in-gcc-when-fwrapv-is-used) – Peter de Rivaz Mar 01 '19 at 23:16
  • 1
    @tadman See his new question about what the option does. It seems to me that he does understand it. – Barmar Mar 01 '19 at 23:18
  • @Barmar The new question seems more focused on that particular aspect, yeah. – tadman Mar 01 '19 at 23:42
  • 1
    It's not clear why you think this question demonstrates a misunderstanding. He's using it precisely to get the behavior he expects. The only difference between the two cases is how the compiler optimizes it. – Barmar Mar 01 '19 at 23:44

1 Answers1

2

This is basically the result of an arbitrary constant in the GCC sources.

GCC has an internal parameter that controls how many times a loop is tentatively unrolled during optimization:

/* The maximum number of iterations of a loop the brute force algorithm
   for analysis of # of iterations of the loop tries to evaluate.  */
DEFPARAM(PARAM_MAX_ITERATIONS_TO_TRACK,
        "max-iterations-to-track",
        "Bound on the number of iterations the brute force #"
        " of iterations analysis algorithm evaluates.",
        1000, 0, 0)

This is used for analyzing loops if GCC does not have special logic to perform some sort of algebraic transformation to get the iteration count.

If you change this parameter to a different value, the switch from outcome to the other will happen at a different magic value. With your original 998 value, I get this:

$ gcc -O3 -fwrapv -S -o- --param max-iterations-to-track=997 t.c | grep jl
    jl  .L3
$ gcc -O3 -fwrapv -S -o- --param max-iterations-to-track=998 t.c | grep jl
    jl  .L3
$ gcc -O3 -fwrapv -S -o- --param max-iterations-to-track=999 t.c | grep jl
$ gcc -O3 -fwrapv -S -o- --param max-iterations-to-track=1000 t.c | grep jl

These parameters are an internal implementation detail and can change meaning at any time, or go away entirely.

(The compiler version I used, based on GCC 6.3, does not use those vector instructions for the unoptimized case, but a sequence with a conditional jl jump, and the cut-off point is slightly different, presumably due to other optimizations.)

Florian Weimer
  • 32,022
  • 3
  • 48
  • 92