Избегайте проверки диапазона в инструкции switch/case в gcc?

[Edit: Кажется, это проблема в версиях gcc до 4.4, я запутался из-за записи gcc bugzilla, сообщающей об этом для 4.5 (последняя). К сожалению, я должен был протестировать более поздние версии. Тем не менее, проблема несколько верна, так как большинство людей не запускают gcc 4.4 +.]

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

extern int a;
main()
{
        switch (a & 0x7) {   // 0x7  == 111  values are 0-7
        case 0: f0(); break;
        case 1: f1(); break;
        case 2: f2(); break;
        case 3: f3(); break;
        case 4: f4(); break;
        case 5: f5(); break;
        case 6: f6(); break;
        case 7: f7(); break;
        }
}

Я попробовал xor'ing для младших бит (в качестве примера), используя перечисления, используя gcc_unreachable() безрезультатно. Сгенерированный код всегда проверяет, находится ли переменная внутри диапазона, добавив неопределенную ветвь и отменив код вычисления таблицы перехода.

Примечание: это самый внутренний цикл декодера, производительность имеет значение значительно.

Кажется, я не только one.

Невозможно сказать gcc, что ветвь по умолчанию никогда не берется, хотя он будет опускать ветвь по умолчанию, если она может доказать, что значение никогда не выходит за пределы, основанные на более ранних условных проверках.

Итак, как вы поможете gcc доказать, что переменная подходит, и в примере выше нет ветки по умолчанию? (Без добавления условной ветки, конечно.)

EDIT1: Это было на OS X 10.6 Snow Leopard с GCC 4.2 (по умолчанию от Xcode.) Это не произошло с GCC 4.4/4.3 в Linux (сообщено Nathon и Jens Gustedt.)

EDIT2: Функции в этом примере доступны для читаемости, считая, что это встроенные или просто инструкции. Выполнение вызова функции на x86 является дорогостоящим.

Также пример, как указано в примечании, принадлежит внутри цикла для данных (большие данные.)

Сгенерированный код с gcc 4.2/OS X:

[...]
andl    $7, %eax
cmpl    $7, %eax
ja  L11
mov %eax, %eax
leaq    L20(%rip), %rdx
movslq  (%rdx,%rax,4),%rax
addq    %rdx, %rax
jmp *%rax
.align 2,0x90
L20:
.long   L12-L20
.long   L13-L20
.long   L14-L20
.long   L15-L20
.long   L16-L20
.long   L17-L20
.long   L18-L20
.long   L19-L20
L19:
[...]

Задача лежит на cmp $7,% eax/ja L11.

EDIT3:

ОК, я пойду с уродливым решением и добавлю специальный случай для версий gcc ниже 4.4, используя другую версию без коммутатора и используя расширения расширений goto и gcc & &.

static void *jtb[] = { &&c_1, &&c_2, &&c_3, &&c_4, &&c_5, &&c_6, &&c_7, &&c_8 };
[...]
goto *jtb[a & 0x7];
[...]
while(0) {
c_1:
// something
break;
c_2:
// something
break;
[...]
}

Обратите внимание, что массив меток является статическим, поэтому он не вычисляет каждый вызов.

Спасибо всем за большую помощь! И жаль тех, у кого есть достоверные ответы, которые не получили оценку: (

Ответ 1

Я пробовал компилировать что-то простое и сопоставимое с -O5 и -fno-inline (мои функции f0-f7 были тривиальны), и он сгенерировал это:


 8048420:   55                      push   %ebp ;; function preamble
 8048421:   89 e5                   mov    %esp,%ebp ;; Yeah, yeah, it a function.
 8048423:   83 ec 04                sub    $0x4,%esp ;; do stuff with the stack
 8048426:   8b 45 08                mov    0x8(%ebp),%eax ;; x86 sucks, we get it
 8048429:   83 e0 07                and    $0x7,%eax ;; Do the (a & 0x7)
 804842c:   ff 24 85 a0 85 04 08    jmp    *0x80485a0(,%eax,4) ;; Jump table!
 8048433:   90                      nop
 8048434:   8d 74 26 00             lea    0x0(%esi,%eiz,1),%esi
 8048438:   8d 45 08                lea    0x8(%ebp),%eax
 804843b:   89 04 24                mov    %eax,(%esp)
 804843e:   e8 bd ff ff ff          call   8048400 
 8048443:   8b 45 08                mov    0x8(%ebp),%eax
 8048446:   c9                      leave

Вы пытались играть с уровнями оптимизации?

Ответ 2

Возможно, вы могли бы использовать массив указателей на функции вместо переключателя?

#include <stdio.h>

typedef void (*func)(void);

static void f0(void) { printf("%s\n", __FUNCTION__); }
static void f1(void) { printf("%s\n", __FUNCTION__); }
static void f2(void) { printf("%s\n", __FUNCTION__); }
static void f3(void) { printf("%s\n", __FUNCTION__); }
static void f4(void) { printf("%s\n", __FUNCTION__); }
static void f5(void) { printf("%s\n", __FUNCTION__); }
static void f6(void) { printf("%s\n", __FUNCTION__); }
static void f7(void) { printf("%s\n", __FUNCTION__); }

int main(void)
{
    const func f[8] = { f0, f1, f2, f3, f4, f5, f6, f7 };
    int i;

    for (i = 0; i < 8; ++i)
    {
        f[i]();
    }
    return 0;
}

Ответ 3

Вы пытались объявить переменную switch как битовое поле?

struct Container {
  uint16_t a:3;
  uint16_t unused:13;
};

struct Container cont;

cont.a = 5;  /* assign some value */
switch( cont.a ) {
...
}

Надеюсь, что это сработает!

Ответ 4

Возможно, просто используйте метку default для кулака или последнего случая?

Ответ 5

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

Тем не менее, я должен признать . Я очень скептически отношусь к тому, что эта дополнительная инструкция когда-либо приведет к измеримой разнице в производительности на практике, особенно на новом Mac. Если у вас есть значительный объем данных, вы будете связаны с I/O, и одна инструкция никогда не станет вашим узким местом. Если у вас есть крошечный объем данных, вам придется многократно выполнять много расчетов, прежде чем одна инструкция станет узким местом.

Вы опубликовали бы какой-то код, чтобы показать, что на самом деле разница в производительности? Или описать код и данные, с которыми работаете?

Ответ 6

Я не пытался, но я не уверен, что gcc_unreachable делает то же самое, что и __builtin_unreachable. Взаимодействующий с двумя, gcc_unreachable, по-видимому, разработан как инструмент утверждения для разработки самого GCC, возможно, с включенным подсказкой предсказания ветвления, тогда как __builtin_unreachable делает программу мгновенно undefined - которая звучит как удаление базового блока, что вы хотите.

http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html#index-g_t_005f_005fbuiltin_005funreachable-3075