Gcc -O optimization: Help me understand the effect

Question

So, I’m studying C, and now I’m looking at computer systems: “Programmers Perspective” 3rd Edition and its associated labs. Now I am making the first laboratory for which I must implement (and thus implement) the following function.

/* 
* fitsBits - return 1 if x can be represented as an 
*  n-bit, two complement integer.
*   1 <= n <= 32
*   Examples: fitsBits(5,3) = 0, fitsBits(-4,3) = 1
*   Legal ops: ! ~ & ^ | + << >>
*   Max ops: 15
*   Rating: 2
*/
int fitsBits(int x, int n) {
  int sign_bit = (x >> 31 & 1);
  int minus_one = ~1+1;
  int n_minus_one = n + minus_one;
  return  (!(x >> n_minus_one) & !sign_bit)
           | (!(~(x >> n_minus_one)) & sign_bit);
}

This function will run _a_lot_ test tables in relation to the next test function.

int test_fitsBits(int x, int n)
{
  int TMin_n = -(1 << (n-1));
  int TMax_n = (1 << (n-1)) - 1;
  return x >= TMin_n && x <= TMax_n;
}

Now here's where the strange thing happens: by default, the code compiles with the following flags -O -Wall -m32

Running my code against the test function calls the following statement: ERROR: Test fitsBits (-2147483648 [0x80000000], 32 [0x20]) failed ... ... It gives 1 [0x1]. Must be 0 [0x0]

, , . , test_function :

> Tmin:-2147483648 
> TMax_n:2147483647 
> x: -2147483648 
> x >= TMin_n: 1
> x <= TMax_n: 0
> result: 0

, -2147483648 <= 2147483647, - 0.

-O, . - ?

: , - , ,

Assembly Code without -O;

.section    __TEXT,__text,regular,pure_instructions
.macosx_version_min 10, 11
.globl  _test_fitsBits
.align  4, 0x90
_test_fitsBits:                         ## @test_fitsBits
.cfi_startproc
## BB#0:
pushq   %rbp
Ltmp0:
.cfi_def_cfa_offset 16
Ltmp1:
.cfi_offset %rbp, -16
movq    %rsp, %rbp
Ltmp2:
.cfi_def_cfa_register %rbp
xorl    %eax, %eax
movb    %al, %cl
movl    $1, %eax
xorl    %edx, %edx
movl    %edi, -4(%rbp)
movl    %esi, -8(%rbp)
movl    -8(%rbp), %esi
subl    $1, %esi
movb    %cl, -17(%rbp)          ## 1-byte Spill
movl    %esi, %ecx
                                    ## kill: CL<def> ECX<kill>
movl    %eax, %esi
shll    %cl, %esi
subl    %esi, %edx
movl    %edx, -12(%rbp)
movl    -8(%rbp), %edx
subl    $1, %edx
movl    %edx, %ecx
                                    ## kill: CL<def> ECX<kill>
shll    %cl, %eax
subl    $1, %eax
movl    %eax, -16(%rbp)
movl    -4(%rbp), %eax
cmpl    -12(%rbp), %eax
movb    -17(%rbp), %cl          ## 1-byte Reload
movb    %cl, -18(%rbp)          ## 1-byte Spill
jl  LBB0_2
## BB#1:
movl    -4(%rbp), %eax
cmpl    -16(%rbp), %eax
setle   %cl
movb    %cl, -18(%rbp)          ## 1-byte Spill
LBB0_2:
movb    -18(%rbp), %al          ## 1-byte Reload
andb    $1, %al
movzbl  %al, %eax
popq    %rbp
retq
.cfi_endproc

.globl  _main
.align  4, 0x90
_main:                                  ## @main
.cfi_startproc
## BB#0:
pushq   %rbp
Ltmp3:
.cfi_def_cfa_offset 16
Ltmp4:
.cfi_offset %rbp, -16
movq    %rsp, %rbp
Ltmp5:
.cfi_def_cfa_register %rbp
xorl    %eax, %eax
movl    $0, -4(%rbp)
movl    %edi, -8(%rbp)
movq    %rsi, -16(%rbp)
popq    %rbp
retq
.cfi_endproc


.subsections_via_symbols

-O:

.section    __TEXT,__text,regular,pure_instructions
.macosx_version_min 10, 11
.globl  _test_fitsBits
.align  4, 0x90
_test_fitsBits:                         ## @test_fitsBits
.cfi_startproc
## BB#0:
pushq   %rbp
Ltmp0:
.cfi_def_cfa_offset 16
Ltmp1:
.cfi_offset %rbp, -16
movq    %rsp, %rbp
Ltmp2:
.cfi_def_cfa_register %rbp
                                    ## kill: ESI<def> ESI<kill>       RSI<def>
leal    -1(%rsi), %ecx
movl    $1, %eax
                                    ## kill: CL<def> CL<kill> ECX<kill>
shll    %cl, %eax
movl    %eax, %ecx
negl    %ecx
cmpl    %edi, %eax
setg    %al
cmpl    %ecx, %edi
setge   %cl
andb    %al, %cl
movzbl  %cl, %eax
popq    %rbp
retq
.cfi_endproc

.globl  _main
.align  4, 0x90
_main:                                  ## @main
.cfi_startproc
## BB#0:
pushq   %rbp
Ltmp3:
.cfi_def_cfa_offset 16
Ltmp4:
.cfi_offset %rbp, -16
movq    %rsp, %rbp
Ltmp5:
.cfi_def_cfa_register %rbp
xorl    %eax, %eax
popq    %rbp
retq
.cfi_endproc


.subsections_via_symbols

Answer 1

oauh , undefined, -O.

-O . , x <= (1 << (n-1)) - 1 x < (1 << (n-1)) - - 1.

, 1 << (n-1) . , , - , - , , undefined.

Answer 2

int TMin_n = -(1 << (n-1));
int TMax_n = (1 << (n-1)) - 1;

32- int undefined, n 32. int 32-, 1 << 31 UB C 1 << 31 int.

Answer 3

@ouah, undefined . , , C , "undefined". , , . , , "undefined " , Rogue.

-O , . , C . , , . undefined, , . , -O , . -g . . printf. .

, , heisenbugs , , .

This is why it is important to include all of your compiler warning flags ( -Wall- this is not all, clang has -Weverything) and eliminate them all. Another tool that helps catch such memory problems is Valgrind .

Answer 4

Modify the test.cfile:

int test_fitsBits(int x, int n) {
    int TMin_n, TMax_n;
    if (n < 32) {
      TMin_n = -(1 << (n-1));
      TMax_n = (1 << (n-1)) - 1;
    } else {
      TMin_n = 0x80000000;
      TMax_n = ~TMin_n;
    }
      return x >= TMin_n && x <= TMax_n;
}