Будет ли бит-сдвиг на ноль бит работать правильно? - PullRequest
15 голосов
/ 11 июня 2009

Скажем, у меня есть такая функция:

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

Он будет вызываться с разных сайтов каждый раз, когда bitCount будет неотрицательным и находится в пределах количества бит в int. Меня особенно беспокоит вызов с bitCount равным нулю - будет ли он работать правильно тогда?

Также существует ли вероятность того, что компилятор, увидевший весь код функции при компиляции своего сайта вызовов, уменьшит количество вызовов с bitCount, равным нулю, до неактивности?

Ответы [ 6 ]

22 голосов
/ 11 июня 2009

Согласно K & R «Результат не определен, если правый операнд отрицательный или больше или равен числу битов в типе левого выражения». (A.7.8) Следовательно, >> 0 - это сдвиг вправо от идентичности и совершенно законный.

17 голосов
/ 11 июня 2009

Это определенно , что по крайней мере один компилятор C ++ распознает ситуацию (когда 0 известен во время компиляции) и сделает ее недоступной:

Источник

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

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

Переключатели компилятора

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

Intel C ++ 11.0 сборка

# -- 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

Как вы можете видеть на ..B1.1, Intel компилирует «return shift (42,0)» в «return 42».

Intel 11 также учитывает сдвиг для этих двух вариантов:

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

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

Для случая, когда значение сдвига неизвестно во время компиляции ...

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

... сдвига нельзя избежать ...

# -- 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;

... но, по крайней мере, он встроен, так что нет накладных расходов на вызов.

Бонус сборки: летучий дорогой. Источник ...

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

... вместо no-op компилируется в ...

..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;

... так что если вы работаете на машине, где значения, которые вы помещаете в стек, могут не совпадать при их извлечении, ну, эта пропущенная оптимизация, вероятно, наименее из ваших проблем.

4 голосов
/ 11 июня 2009

Он будет работать корректно на любой широко используемой архитектуре (я могу поручиться за x86, PPC, ARM). Компилятор не сможет преобразовать его в noop, если функция не встроена.

3 голосов
/ 11 июня 2009

Компилятор может выполнить эту оптимизацию только в том случае, если во время компиляции он знал, что значение bitCount равно нулю. Это будет означать, что переданный параметр должен быть константой:

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

C ++, безусловно, позволяет выполнять такую ​​оптимизацию, но я не знаю ни одного компилятора, который бы это делал. Альтернативный подход, который может использовать компилятор:

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

было бы пессимизацией в большинстве случаев, и я не могу представить, чтобы автор компилятора реализовывал такую ​​вещь.

Редактировать: Смещение нулевых битов АА гарантированно не повлияет на смещаемую вещь.

2 голосов
/ 11 июня 2009

О правильности arg << 0 или arg >> 0, нет проблем, абсолютно нормально.

О возможных оптимизациях: Это значение не будет уменьшено до> nop

Итак, нижняя строка, оптимизируйте этот код, вызывая функцию условно, только если OR аргументов не равно нулю (о самом быстром способе, который я покажу, чтобы проверить, что оба аргумента отличны от нуля).

1 голос
/ 11 июня 2009

Чтобы сделать функцию несколько самодокументируемой, вы можете изменить bitCount на unsigned, чтобы указать вызывающим сторонам, что отрицательное значение недопустимо.

...