GCC 4.4: Избегать проверки диапазона на операторе switch/case в gcc?
Это проблема только в версиях 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 в младшие биты (как пример), используя перечисления, используя gcc_unreachable() безрезультатно. Сгенерированный код всегда проверяет, находится ли переменная внутри диапазона, добавляя бессмысленную условную ветвь и удаляя код вычисления таблицы переходов.
Примечание: это находится в самом внутреннем цикле декодера, производительность имеет большое значение.
Кажется, я не единственный.
Нет никакого способа сказать gcc, что ветвь по умолчанию никогда не берется, хотя она пропустит ветвь по умолчанию, если сможет доказать, что значение никогда не выходит за пределы диапазона на основе предыдущих условных проверок.
Итак, как вы помогаете gcc доказать соответствие переменных, и в приведенном выше примере нет ветки по умолчанию? (Без добавления условной ветки, конечно.)
Обновления
Это было на OS X 10.6 Snow Leopard с GCC 4.2 (по умолчанию от Xcode.) Этого не произошло с GCC 4.4/4.3 в linux (сообщили Натон и Дженс Гастедт.)
Функции в этом примере предназначены для удобства чтения, представьте, что они встроенные или просто операторы. Выполнение вызова функции на 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;Хорошо, я собираюсь использовать некрасивое решение и добавить специальный случай для версий 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 ответов
Я попытался скомпилировать что-то простое и сопоставимое с -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
Вы пробовали играть с уровнями оптимизации?
Возможно, вы могли бы использовать массив указателей на функции вместо переключателя?
#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;
}
Вы пытались объявить switch переменная как битовое поле?
struct Container {
uint16_t a:3;
uint16_t unused:13;
};
struct Container cont;
cont.a = 5; /* assign some value */
switch( cont.a ) {
...
}
Надеюсь, это работает!
Я не пытался, но я не уверен, что gcc_unreachable делает то же самое, что и __builtin_unreachable, Погуглив два, gcc_unreachable Похоже, что он разработан как инструмент утверждения для разработки самого GCC, возможно, с включенной подсказкой предсказания перехода, тогда как __builtin_unreachable делает программу мгновенно неопределенной - это звучит как удаление основного блока, что вам и нужно.
Этот вопрос, безусловно, интересен с точки зрения пропущенной оптимизации компилятора, которая, по-видимому, очевидна для нас, и я потратил немало времени, пытаясь найти простое решение, в основном из личного любопытства.
Тем не менее, я должен признать, что я очень скептически отношусь к тому, что эта дополнительная инструкция когда-либо приведет к ощутимой разнице в производительности на практике, особенно на новом Mac. Если у вас есть какой-либо значительный объем данных, вы будете связаны с вводом / выводом, и одна инструкция никогда не станет вашим узким местом. Если у вас есть небольшое количество данных, вам придется многократно выполнять много вычислений, прежде чем одна инструкция станет узким местом.
Не могли бы вы опубликовать код, чтобы показать, что на самом деле разница в производительности? Или опишите код и данные, с которыми вы работаете?
Возможно, просто используйте default этикетка для первого или последнего случая?