GCC 4.4: Избегать проверки диапазона в параметре switch / case в gcc? - PullRequest
Новая
       57

GCC 4.4: Избегать проверки диапазона в параметре switch / case в gcc?

14 голосов
/ 15 июля 2010

Это проблема только в версиях GCC до 4.4, это было исправлено в GCC 4.5.

Можно ли сообщить компилятору, что переменная, используемая в переключателе, соответствует указанным операторам 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 в младшие биты (как пример), используя enums, используя gcc_unreachable (), но безрезультатно. Сгенерированный код всегда проверяет, находится ли переменная внутри диапазона, добавляя бессмысленную условную ветвь и удаляя код вычисления таблицы переходов.

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

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

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

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

Обновление

  1. Это было на OS X 10.6 Snow Leopard с GCC 4.2 (по умолчанию от Xcode.) Этого не произошло с GCC 4.4 / 4.3 в Linux (сообщается Натоном и Дженсом Гастедтом.)

  2. Функции в примере предназначены для удобства чтения, представьте, что это встроенные или просто операторы. Выполнение вызова функции на 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;

  3. ОК, я собираюсь использовать некрасивое решение и добавить специальный случай для версий 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;
[...]
}

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

Ответы [ 6 ]

5 голосов
/ 15 июля 2010

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

#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;
}
2 голосов
/ 15 июля 2010

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

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

struct Container cont;

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

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

1 голос
/ 30 сентября 2010

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

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

1 голос
/ 15 июля 2010

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

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

1 голос
/ 15 июля 2010

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


 8048420:   55                      push   %ebp ;; function preamble
 8048421:   89 e5                   mov    %esp,%ebp ;; Yeah, yeah, it's 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

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

1 голос
/ 15 июля 2010

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

...