Why is GCC 4.8.2 complaining about addition under strict overflow?

Question

Consider this code (bits.c):

#include <assert.h>
#include <inttypes.h>
#include <stdio.h>

static uint64_t pick_bits(unsigned char *bytes, size_t nbytes, int lo, int hi)
{
  assert(bytes != 0 && nbytes > 0 && nbytes <= 8);
  assert(lo >= 0 && lo < 64);
  assert(hi >= 0 && hi < 64 && hi >= lo);
  uint64_t result = 0;
  for (int i = nbytes - 1; i >= 0; i--)
    result = (result << 8) | bytes[i];
  result >>= lo;
  result &= (UINT64_C(1) << (hi - lo + 1)) - 1;
  return result;
}

int main(void)
{
  unsigned char d1[8] = "\xA5\xB4\xC3\xD2\xE1\xF0\x96\x87";
  for (int u = 0; u < 64; u += 4)
  {
    uint64_t v = pick_bits(d1, sizeof(d1), u, u+3);
    printf("Picking bits %2d..%2d gives 0x%" PRIX64 "\n", u, u+3, v);
  }
  return 0;
}

When compiled with stringent warnings (using GCC 4.8.2 built for an Ubuntu 12.04 derivative):

$ gcc -g -O3 -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
>     -Wold-style-definition -Wold-style-declaration -Werror  bits.c -o bits
In file included from bits.c:1:0:
bits.c: In function ‘main’:
bits.c:9:35: error: assuming signed overflow does not occur when assuming that (X + c) < X is always false [-Werror=strict-overflow]
   assert(hi >= 0 && hi < 64 && hi >= lo);
                                   ^
cc1: all warnings being treated as errors

I'm puzzled: how is GCC complaining about an addition? There are no additions in that line (even when preprocessed)! The relevant section of the preprocessed output is:

# 4 "bits.c" 2

static uint64_t pick_bits(unsigned char *bytes, size_t nbytes, int lo, int hi)
{
  ((bytes != 0 && nbytes > 0 && nbytes <= 8) ? (void) (0) : __assert_fail ("bytes != 0 && nbytes > 0 && nbytes <= 8", "bits.c", 7, __PRETTY_FUNCTION__));
  ((lo >= 0 && lo < 64) ? (void) (0) : __assert_fail ("lo >= 0 && lo < 64", "bits.c", 8, __PRETTY_FUNCTION__));
  ((hi >= 0 && hi < 64 && hi >= lo) ? (void) (0) : __assert_fail ("hi >= 0 && hi < 64 && hi >= lo", "bits.c", 9, __PRETTY_FUNCTION__));
  uint64_t result = 0;
  for (int i = nbytes - 1; i >= 0; i--)
    result = (result << 8) | bytes[i];
  result >>= lo;
  result &= (1UL << (hi - lo + 1)) - 1;
  return result;
}

Clearly, I can add -Wno-strict-overflow to suppress that warning, but I don't understand why the warning is considered to apply to this code in the first place.

(I note that the error is reputedly In function ‘main’:, but that is because it is able to aggressively inline the code of the function into main.)

---

Further observations

Some observations triggered by the answers:

• The problem occurs because of the inlining.
• Removing the static is not sufficient to avoid the problem.
• Compiling the function separately from main works.
• Adding the __attribute__((noinline)) works too.
• Using -O2 optimization avoids the issue, too.

Subsidiary question

This looks to me like dubious behaviour by the GCC compiler.

• Is it worth reporting to the GCC team as a possible bug?

---

Assembler output

Command:

$ gcc -g -O3 -std=c99 -Wall -Wextra -Wmissing-prototypes -Wstrict-prototypes \
> -Wold-style-definition -Wold-style-declaration -Werror -S \
> -Wno-strict-overflow bits.c
$

Assembler (top section):

    .file   "bits.c"
    .text
.Ltext0:
    .section    .rodata.str1.8,"aMS",@progbits,1
    .align 8
.LC0:
    .string "Picking bits %2d..%2d gives 0x%lX\n"
    .section    .text.startup,"ax",@progbits
    .p2align 4,,15
    .globl  main
    .type   main, @function
main:
.LFB8:
    .file 1 "bits.c"
    .loc 1 19 0
    .cfi_startproc
.LVL0:
    pushq   %rbp
    .cfi_def_cfa_offset 16
    .cfi_offset 6, -16
.LBB8:
.LBB9:
    .loc 1 23 0
    movl    $3, %edx
.LBB10:
.LBB11:
    .loc 1 13 0
    movabsq $-8676482779388332891, %rbp
.LBE11:
.LBE10:
.LBE9:
.LBE8:
    .loc 1 19 0
    pushq   %rbx
    .cfi_def_cfa_offset 24
    .cfi_offset 3, -24
.LBB22:
    .loc 1 21 0
    xorl    %ebx, %ebx
.LBE22:
    .loc 1 19 0
    subq    $8, %rsp
    .cfi_def_cfa_offset 32
    jmp .L2
.LVL1:
    .p2align 4,,10
    .p2align 3
.L3:
    leal    3(%rbx), %edx
.LVL2:
.L2:
.LBB23:
.LBB20:
.LBB16:
.LBB12:
    .loc 1 13 0
    movl    %ebx, %ecx
    movq    %rbp, %rax
.LBE12:
.LBE16:
    .loc 1 24 0
    movl    %ebx, %esi
.LBB17:
.LBB13:
    .loc 1 13 0
    shrq    %cl, %rax
.LBE13:
.LBE17:
    .loc 1 24 0
    movl    $.LC0, %edi
.LBE20:
    .loc 1 21 0
    addl    $4, %ebx
.LVL3:
.LBB21:
.LBB18:
.LBB14:
    .loc 1 13 0
    movq    %rax, %rcx
.LBE14:
.LBE18:
    .loc 1 24 0
    xorl    %eax, %eax
.LBB19:
.LBB15:
    .loc 1 14 0
    andl    $15, %ecx
.LBE15:
.LBE19:
    .loc 1 24 0
    call    printf
.LVL4:
.LBE21:
    .loc 1 21 0
    cmpl    $64, %ebx
    jne .L3
.LBE23:
    .loc 1 27 0
    addq    $8, %rsp
    .cfi_def_cfa_offset 24
    xorl    %eax, %eax
    popq    %rbx
    .cfi_def_cfa_offset 16
.LVL5:
    popq    %rbp
    .cfi_def_cfa_offset 8
    ret
    .cfi_endproc
.LFE8:
    .size   main, .-main
    .text
...

Answer 1

It's inlining the function, and then generating the error. You can see for yourself:

__attribute__((noinline))
static uint64_t pick_bits(unsigned char *bytes, size_t nbytes, int lo, int hi)

On my system, the original version generates the same warning, but the noinline version does not.

GCC then optimizes out hi >= lo, because it's really u+3 >= u, and generates a warning because it's not good enough at figuring out that u+3 doesn't overflow. A shame.

Documentation

From the GCC documentation, section 3.8:

An optimization that assumes that signed overflow does not occur is perfectly safe if the values of the variables involved are such that overflow never does, in fact, occur. Therefore this warning can easily give a false positive: a warning about code that is not actually a problem. To help focus on important issues, several warning levels are defined. No warnings are issued for the use of undefined signed overflow when estimating how many iterations a loop requires, in particular when determining whether a loop will be executed at all.

Emphasis added. My personal recommendation is to use -Wno-error=strict-overflow, or to use a #pragma to disable the warning in the offending code.

Answer 2

My assumption is that gcc is inlining pick_bits and thus compiling with the knowledge that hi == lo+3 which allows it to assume that hi >= lo is always true as long as lo is low enough that lo+3 doesn't overflow.