What is special in gcc about a loop that iterates 999 times?



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)
    return i;

compiles (using -O3 -fwrapv) to:

  mov eax, 2147483647

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

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


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


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.


1 Answer


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.  */
        "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.)

answered on Stack Overflow Mar 2, 2019 by Florian Weimer

User contributions licensed under CC BY-SA 3.0