Wird Bit-Verschiebung von Null-Bits korrekt funktionieren?

Question

Sagen, ich habe eine Funktion wie folgt aus:

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

Es wird von verschiedenen Standorten jedes Mal bitCount wird nicht negativ sein und innerhalb der Anzahl von Bits in int aufgerufen werden. Ich bin besonders besorgt über Anruf mit bitCount gleich Null - wird es dann richtig funktionieren

Auch gibt es eine Chance, dass ein Compiler den gesamten Code der Funktion zu sehen, wenn sein Aufrufort Kompilieren Anrufe mit bitCount gleich Null auf einen no-op reduzieren?

Answer 1

Es ist sicher , dass mindestens ein C ++ Compiler wird die Situation erkennen (wenn die 0 zum Zeitpunkt der Kompilierung bekannt ist) und macht es zu einem no-op:

Quelle

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

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

Compiler-Schalter

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

Intel C ++ 11.0 Montage

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

Wie Sie bei ..B1.1 sehen können, Intel kompiliert "return Verschiebung (42,0)" bis "42 zurück."

Intel 11 pflückt auch die Verschiebung für diese beiden Varianten:

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

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

Für den Fall, wenn der Verschiebungswert zum Zeitpunkt der Kompilierung unerkennbar ist ...

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

... die Verschiebung nicht vermieden werden kann ...

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

... aber zumindest ist es inlined so dass es Kopf kein Anruf ist.

Bonus Montage: volatile ist teuer. Die Quelle ...

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

... statt einer No-op, kompiliert ...

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

... also, wenn Sie auf einem Computer arbeiten, wo man auf den Stapel schieben Werte möglicherweise nicht die gleiche sein, wenn Sie sie Pop, na ja, diese verpassten Optimierung wahrscheinlich die am wenigsten Ihrer Probleme ist.

Answer 2

Nach K & R „Das Ergebnis wenn der rechte Operand negativ ist nicht definiert ist, oder größer als oder gleich der Anzahl von Bits in der linken Gesichtsausdruck des Typs“. (A.7.8) Daher >> 0 ist die Identität richtig und vollkommen legal verschieben.

Answer 3

Es korrekt auf jede weit verbreitete Architektur arbeiten (ich kann für x86 bürgen, PPC, ARM). Der Compiler wird nicht in der Lage sein, es zu einem noop zu reduzieren, wenn die Funktion inlined wird.

Answer 4

Der Compiler konnte nur diese Optimierung durchführen zu tun, dass, wenn sie zum Zeitpunkt der Kompilierung wusste, dass der Bitcount Wert war Null. Das würde bedeuten, dass der übergebene Parameter eine Konstante sein müßte:

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

C ++ ermöglicht sicherlich eine solche Optimierung durchgeführt werden, aber ich bin keine Kenntnis von Compilern, die dies tun. Der alternative Ansatz der Compiler könnte nehmen:

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

wäre ein pessimisation in der Mehrzahl der Fälle sein, und ich kann nicht Compiler Schriftsteller Umsetzung so etwas vorstellen.

Edit:. AA Verschiebung von Null-Bits ist garantiert keinen Einfluss auf die Sache verschoben werden müssen

Answer 5

über die Richtigkeit der arg << 0 oder arg >> 0, kein Problem, absolut in Ordnung.

über die eventuellen Optimierungen: Dies wird nicht reduziert werden a> nop <, wenn sie mit einem konstanten genannt, was = 0 und / oder Bitcount = 0, wenn Sie es als Inline deklarieren und wählen Optimierungen (und Compiler der Wahl verstehen, was Inline ist).

So Unterm Strich optimiert diesen Code bedingt die Funktion nur, wenn die OR von Argumenten ist nicht Null Aufruf (über den schnellsten Weg, ich meint, zu prüfen, dass beiden Argumente nicht Null).

Answer 6

Um die Funktion etwas selbstdokumentiere zu machen, möchten Sie vielleicht Bitcount in unsigned ändern, um Anrufer zu signalisieren, dass ein negativer Wert nicht gültig ist.