Will bit-shift by zero bits work correctly?

问题:

Say I have a function like this:

inline int shift( int what, int bitCount )
{
    return what >> bitCount;
}

It will be called from different sites each time bitCount will be non-negative and within the number of bits in int. I'm particularly concerned about call with bitCount equal to zero - will it work correctly then?

Also is there a chance that a compiler seeing the whole code of the function when compiling its call site will reduce calls with bitCount equal to zero to a no-op?

回答1:

It is certain that at least one C++ compiler will recognize the situation (when the 0 is known at compile time) and make it a no-op:

Source

inline int shift( int what, int bitcount)
{
  return what >> bitcount ;
}

int f() {
  return shift(42,0);
}

Compiler switches

icpc -S -O3 -mssse3 -fp-model fast=2 bitsh.C

Intel C++ 11.0 assembly

# -- Begin  _Z1fv
# mark_begin;
       .align    16,0x90
        .globl _Z1fv
_Z1fv:
..B1.1:                         # Preds ..B1.0
        movl      $42, %eax                                     #7.10
        ret                                                     #7.10
        .align    16,0x90
                                # LOE
# mark_end;
        .type   _Z1fv,@function
        .size   _Z1fv,.-_Z1fv
        .data
# -- End  _Z1fv
        .data
        .section .note.GNU-stack, ""
# End

As you can see at ..B1.1, Intel compiles "return shift(42,0)" to "return 42."

Intel 11 also culls the shift for these two variations:

int g() {
  int a = 5;
  int b = 5;
  return shift(42,a-b);
}

int h(int k) {
  return shift(42,k*0);
}

For the case when the shift value is unknowable at compile time ...

int egad(int m, int n) {
  return shift(42,m-n);
}

... the shift cannot be avoided ...

# -- Begin  _Z4egadii
# mark_begin;
       .align    16,0x90
        .globl _Z4egadii
_Z4egadii:
# parameter 1: 4 + %esp
# parameter 2: 8 + %esp
..B1.1:                         # Preds ..B1.0
        movl      4(%esp), %ecx                                 #20.5
        subl      8(%esp), %ecx                                 #21.21
        movl      $42, %eax                                     #21.10
        shrl      %cl, %eax                                     #21.10
        ret                                                     #21.10
        .align    16,0x90
                                # LOE
# mark_end;

... but at least it's inlined so there's no call overhead.

Bonus assembly: volatile is expensive. The source ...

int g() {
  int a = 5;
  volatile int b = 5;
  return shift(42,a-b);
}

... instead of a no-op, compiles to ...

..B3.1:                         # Preds ..B3.0
        pushl     %esi                                          #10.9
        movl      $5, (%esp)                                    #12.18
        movl      (%esp), %ecx                                  #13.21
        negl      %ecx                                          #13.21
        addl      $5, %ecx                                      #13.21
        movl      $42, %eax                                     #13.10
        shrl      %cl, %eax                                     #13.10
        popl      %ecx                                          #13.10
        ret                                                     #13.10
        .align    16,0x90
                                # LOE
# mark_end;

... so if you're working on a machine where values you push on the stack might not be the same when you pop them, well, this missed optimization is likely the least of your troubles.

回答2:

According to K&R "The result is undefined if the right operand is negative, or greater than or equal to the number of bits in the left expression's type." (A.7.8) Therefore >> 0 is the identity right shift and perfectly legal.

回答3:

It will work correctly on any widely used architecture (I can vouch for x86, PPC, ARM). The compiler will not be able to reduce it to a noop unless the function is inlined.

回答4:

The compiler could only perform this optimisation do that if it knew at compile time that the bitCount value was zero. That would mean that the passed parameter would have to be a constant:

const int N = 0;
int x = shift( 123, N );

C++ certainly allows such an optimisation to be performed, but I'm not aware of any compilers that do so. The alternative approach the compiler could take:

int x = n == 0 ? 123 : shift( 123, n );

would be a pessimisation in the majority of cases and I can't imagine compiler writer implementing such a thing.

Edit: AA shift of zero bits is guaranteed to have no effect on the thing being shifted.

回答5:

About the correctness of arg << 0 or arg >> 0, no problem, absolutely fine.

About the eventual optimizations: This will not be reduced to a >nop< when called with a constant what=0 and/or bitcount=0, unless you declare it as inline and choose optimizations (and your compiler of choice understands what inline is).

So, bottom line, optimize this code by conditionally calling the function only if the OR of arguments is non zero (about the fastest way I figure to test that both args are non-zero).

回答6:

To make the function somewhat self documenting, you may want to change bitCount to unsigned to signify to callers that a negative value is not valid.