Код уровня сборки корпуса переключателя

Я программирую C на окнах cygwin. Немного попрограммировав на C и освоившись с языком, я захотел заглянуть под капот и посмотреть, что компилятор делает с кодом, который я пишу.

Поэтому я записал блок кода, содержащий операторы switch case, и преобразовал их в сборку, используя:

gcc -S foo.c  

Вот исходник С:

switch(i)
{
    case 1:
    {
        printf("Case 1\n");
        break;
    }
    case 2:
    {           printf("Case 2\n");
        break;
    }
    case 3:
    {
        printf("Case 3\n");
        break;
    }
    case 4:
    {
        printf("Case 4\n");
        break;
    }
    case 5:
    {
        printf("Case 5\n");
        break;
    }
    case 6:
    {
        printf("Case 6\n");
        break;
    }
    case 7:
    {
        printf("Case 7\n");
        break;
    }
    case 8:
    {
        printf("Case 8\n");
        break;
    }
    case 9:
    {
        printf("Case 9\n");
        break;
    }
    case 10:
    {
        printf("Case 10\n");
        break;
    }
    default:
    {
        printf("Nothing\n");
        break;
    }
}  

Теперь результирующая сборка для того же:

movl    $5, -4(%ebp)
cmpl    $10, -4(%ebp)
ja  L13
movl    -4(%ebp), %eax
sall    $2, %eax
movl    L14(%eax), %eax
jmp *%eax
.section .rdata,"dr"
.align 4
L14:
.long   L13
.long   L3
.long   L4
.long   L5
.long   L6
.long   L7
.long   L8
.long   L9
.long   L10
.long   L11
.long   L12
.text
L3:
movl    $LC0, (%esp)
call    _printf
jmp L2
L4:
movl    $LC1, (%esp)
call    _printf
jmp L2
L5:
movl    $LC2, (%esp)
call    _printf
jmp L2
L6:
movl    $LC3, (%esp)
call    _printf
jmp L2
L7:
movl    $LC4, (%esp)
call    _printf
jmp L2
L8:
movl    $LC5, (%esp)
call    _printf
jmp L2
L9:
movl    $LC6, (%esp)
call    _printf
jmp L2
L10:
movl    $LC7, (%esp)
call    _printf
jmp L2
L11:
movl    $LC8, (%esp)
call    _printf
jmp L2
L12:
movl    $LC9, (%esp)
call    _printf
jmp L2
L13:
movl    $LC10, (%esp)
call    _printf
L2:  

Теперь в сборке код сначала проверяет последний случай (т.е. случай 10). Это очень странно. А затем он копирует «i» в «eax» и делает то, что мне не по силам.

Я слышал, что компилятор реализует некоторую таблицу переходов для switch..case. Это то, что делает этот код? Или что он делает и почему? Потому что в случае меньшего количества случаев код очень похож на сгенерированный для лестницы if...else, но когда количество случаев увеличивается, видна эта необычная реализация.

Заранее спасибо.


person puffadder    schedule 10.06.2010    source источник
comment
К сожалению, он не оптимизирован для поиска в таблице указателя строки и call _printf. Ни один из gcc/clang/icc не делает этого даже в -O3. godbolt.org/g/JrSwU3 (хотя они оптимизируют printf до puts и оптимизируют хвост- вызов jmp вместо call/ret)   -  person Peter Cordes    schedule 31.08.2017


Ответы (4)


Сначала код сравнивает i с 10 и переходит к случаю по умолчанию, когда значение больше 10 (cmpl $10, -4(%ebp), за которым следует ja L13).

Следующий бит кода сдвигает ввод влево на два (sall $2, %eax), что равно кратному четырем, что создает смещение в таблице переходов (поскольку каждая запись в таблице имеет длину 4 байта).

Затем он загружает адрес из таблицы переходов (movl L14(%eax), %eax) и переходит к нему (jmp *%eax).

Таблица переходов — это просто список адресов (представленных в ассемблерном коде метками):

L14:
.long   L13
.long   L3
.long   L4
...

Следует отметить, что L13 представляет случай по умолчанию. Это первая запись в таблице переходов (когда i равно 0), и она обрабатывается в начале особым образом (когда i > 10).

person R Samuel Klatchko    schedule 10.06.2010
comment
Понятно... это информативно. Но тогда почему компилятор не создает таблицу переходов в случае меньшего количества случаев (например, 2 или 3)? - person puffadder; 10.06.2010
comment
@puffadder: большинство современных компиляторов используют эвристику, чтобы определить, когда более эффективно использовать ветки, а не таблицу переходов. Например. если бы ваши уровни регистра были, скажем, 1, 100 и 1000, вы могли бы ожидать, что будут использоваться ветки. - person Paul R; 10.06.2010
comment
Я не понимаю, почему каждый шаг переходит к случаю по умолчанию, а не полностью переключается. Кто-нибудь может это объяснить? - person mharris7190; 19.02.2014
comment
@ mharris7190, похоже, что каждая запись в таблице переходит на метку L2, которая полностью находится вне коммутатора. Запись по умолчанию L13 не имеет перехода к L2, потому что это последняя запись в таблице, поэтому следующей инструкцией для L13 является L2. - person Nick; 14.05.2014

Да, это таблица прыжков. Первая проверка заключается в том, чтобы проверить, находится ли значение в регистрах, и перейти к значению по умолчанию, если это не так. Не забывайте, что в такой таблице, если %eax равно 0, L14(%eax) указывает на первый элемент таблицы (L13). Таким образом, в таблице case 10: имеет индекс 9, а не 10.

Способ переключения зависит от значений, которые у вас есть в case; в этом случае они находятся в «последовательности», поэтому возможна простая таблица переходов.

person ShinTakezou    schedule 10.06.2010

Для [1..10] компилятор создаст таблицу, поэтому ему не нужно сравнивать значение, чтобы куда-то перейти, он напрямую делает: goto table[i]. Так быстрее.

Но в случае i > 10 он переходит к оператору по умолчанию. Он должен сначала проверить, прежде чем прыгать, иначе программа с треском рухнет.

Если бы у вас были разреженные значения (например, 23, 9233, 91238, а не 1, 2, 3...), компилятор не создал бы такую ​​таблицу и не сравнил бы каждое значение.

person Nicolas Viennot    schedule 10.06.2010

Да, первый eax вычисляется по значению переключателя (сдвиг sall как умножение), чтобы получить адрес из таблицы переходов (после метки L14:)

jmp *%eax — это почти переход к названию вашего дела. (JMP рядом с EAX)

Код, следующий за другими метками, просто печатается и пропускает другие случаи.

person stacker    schedule 10.06.2010