#compiler

Быстрый Switch: таблица адресов 💨

В C++ оператор switch используется для передачи потока управления в разные места в зависимости от значения переменной.
Оператор switch можно представить как соответствие между значениями переменной, и кодом который должен выполниться для каждого значения.

В зависимости от целевой архитектуры, настроек оптимизации, и свойств конкретного switch-оператора, код может сгенерироваться в разном виде. Есть два варианта, какой ассемблер сгенерирует компилятор:
1️⃣ Цепочка последовательных if-ов. Это самый простой путь, потому что switch-оператор всегда представим в этом виде.
2️⃣ Таблица адресов (мой перевод), он же branch table, он же jump table.

Первый вариант неинтересен, он самый простой и самый неоптимизированный. Если в нашем switch 30 штук case-ов, то в худшем случае произойдет 30 (!) последовательных сравнений (цепочка if-ов), прежде чем программа поймет номер нужной инструкции.
На самом деле в таких случаях компиляторы умеют делать а-ля "бинарный поиск", поэтому вероятно будет log_2(30) сравнений в худшем случае 😁

Во втором варианте номер инструкции, куда надо перепрыгнуть, вычисляется в зависимости от значения переменной, в процессе чего не выполнится ни одного сравнения.

Пример switch с таблицей адресов: https://godbolt.org/z/3debYb4vq
В этом примере в switch сравнивается значение enum-а. Для компилятора enum представляется как underlying type. По умолчанию этот тип int, то есть во всех операциях с enum происходит неявная конвертация в int.
Таким образом, можно представить, что это switch по значениям от 0 до 6 включительно.

В примере компилятор сгенерировал метки LBB0_2, LBB0_3, ..., LBB0_8 для каждого соответствующего кода case X.

Также компилятор сделал таблицу LJTI0_0, где лежат адреса этих меток. Вообще "таблица" это громко сказано, это просто наша абстракция.
"Таблица" представляет из себя несколько последовательных 8-байтовых числа, которые являются адресами меток LBB0_2-LBB0_8.
А метка LJTI0_0 указывает на начало последовательности.

Теперь, имея "таблицу адресов", можно вычислить номер инструкции, куда надо прыгать. Если параметр равен 0, то прыгаем по первому адресу таблицы, если 1 - по второму, и так далее.

        lea     rcx, [rip + .LJTI0_0]
        movsxd  rax, dword ptr [rcx + 4*rax]
        add     rax, rcx
        jmp     rax

Отступление: Как известно, метки имеют смысл только для ассемблера. Метка просто условно указывает на позицию в бинарнике (инструкцию или данные). После процесса линковки, когда в один исполняемый файл (бинарник) утрамбуются отдельные объектные файлы, вместо меток появятся нормальные адреса.

        lea     rcx, [rip + 0x012345678]

Таблица адресов может иметь другую реализацию, но такая общая идея. Например, в примере с Википедии для рандомного 8-битного ассемблера, значение переменной прибавляется к регистру счетчика команд (addwf PCL,F), а сразу после этой инструкции находится таблица с goto до нужной инструкции, и счетчик команд укажет на нужный goto.

Компилятор сам определяет, нужна ли таблица адресов. Обычно она используется для "плотных" switch, где есть case X для последовательных значений X. Если в case X поставить рандомные значения, то таблицы не получится - пример на godbolt, будут последовательные if-ы.