1 ноября 2026Команда Сарнас

Как GCC понижает switch: от GIMPLE до машинного кода

Статья разбирает, как компилятор GCC последовательно преобразует оператор switch — от сворачивания цепочек условий до выбора между таблицей переходов и проверками битовых масок — и какие проходы за это отвечают. Особый интерес представляет описание внутренней логики: порогов, критериев отказа и того, как решения принимаются заново на каждом уровне представления. Это полезно всем, кто хочет понимать, во что реально превращается привычная конструкция языка на выходе.

Оператор switch выглядит как одна конструкция языка, но за ней стоит несколько независимых решений: превратить ли набор меток в таблицу переходов, в битовую маску, в дерево сравнений или в арифметику без таблицы вообще. Каждое решение принимается отдельным проходом, у каждого свои пороги и свои условия отказа. Разберём, в каком порядке эти проходы срабатывают, по каким критериям выбирают форму и что в итоге попадает в ассемблер.

Маршрут понижения: от GENERIC к RTL

Понижение идёт в несколько этапов. Сначала gimplify.cc переводит представление «функции-как-деревья» (GENERIC) в GIMPLE. Затем проход gimple-if-to-switch ищет цепочки if-else, проверяющие одно и то же SSA-имя, и сворачивает их в один GIMPLE_SWITCH. После этого switchconv (tree-switch-conversion) понижает GIMPLE_SWITCH в индексированную загрузку — переход по таблице адресов меток, выбираемой по значению индекса, — или в серию bit-test-and-branch — проверок отдельных битов маски с условными переходами. Его gate включается флагом flag_tree_switch_conversion. Отдельный проход switchlower выполняет понижение switch с вариантом для -O0: его gate возвращает истину при отсутствии оптимизации. Наконец, на уровне RTL stmt.cc разворачивает case-метки в jump table.

Порядок важен: к моменту, когда switchconv берётся за дело, цепочки if-else уже свёрнуты в switch, а на уровне RTL решение принимается заново для того, что осталось.

Проход switchconv: что проверяет gate и что делает execute

Gate прохода тривиален — он лишь проверяет, что флаг flag_tree_switch_conversion ненулевой. Execute (метод, выполняющий сам проход) обходит все базовые блоки функции и для каждого блока, чей последний оператор — switch-выражение, создаёт объект преобразования и запускает его. Изменение CFG накапливается в признаке cfg_altered.

Дальше — характерная деталь. Если преобразование прошло успешно, проход не обновляет информацию о пост-доминаторах, а просто освобождает её. Причина названа прямо: iterate_fix_dominators не поддерживает обновление пост-доминаторов, поэтому вместо обновления информация освобождается. Если преобразование не удалось, причина отказа печатается в dump-файл. В конце execute возвращает запрос на очистку CFG, если граф менялся, иначе — ноль.

Сбор информации о switch

Прежде чем что-то преобразовывать, нужно собрать факты о самом switch. Метод collect сохраняет оператор, извлекает индексное выражение, находит ребро default, и запоминает его вероятность. Вероятность ребра — это профильная оценка того, как часто управление уходит по этому переходу; она сохраняется в m_default_prob и дальше используется при построении новых рёбер: ветви, ведущей внутрь диапазона, присваивается инвертированная вероятность default, а ветви за пределы диапазона — сама m_default_prob. Границы диапазона берутся из первой и последней меток: нижняя — это CASE_LOW первой метки, верхняя — CASE_HIGH последней, если она задана, иначе CASE_LOW последней.

Затем проверяется непрерывность: метки перебираются со второй, и если следующая метка не равна предыдущей плюс один, диапазон объявляется разрывным. Это флаг m_contiguous_range, и от него зависит выбор стартового ребра: при непрерывном диапазоне берётся первое ребро switch, иначе — default.

Параллельно ищется общий блок-преемник всех ветвей. Если у первого не-default блока назначения не один предшественник, он и становится финальным блоком; если у него один преемник и у того не один предшественник — финальным становится этот преемник. Все цели switch должны быть либо этим блоком, либо форвардером к нему (кроме default при непрерывном диапазоне); иначе финальный блок сбрасывается, а число уникальных целей оценивается как число рёбер минус один.

Отдельно считается число меток: каждая метка даёт единицу, а диапазонная метка с разными границами — ещё одну, потому что может потребовать двух сравнений.

Кластеры: как метки группируются

Из меток формируется вектор кластеров. Для каждой метки берутся её нижняя и верхняя границы, вычисляется вероятность перехода (вероятность ребра масштабируется по числу покрытых значений) и в вектор добавляется кластер, хранящий диапазон значений, выходное ребро и вероятность выбора.

Кластеры можно объединять в группы. Конструктор группы собирает диапазон кластеров, суммируя их вероятности. Перед проверками группа выясняет, применимо ли экспоненциальное преобразование индекса.

Смысл преобразования в том, что метки-степени двойки (1, 2, 4, 8, …) лежат редко и растягивают диапазон значений, из-за чего switch не проходит проверку диапазона. Если заменить каждую такую метку её показателем степени (то есть логарифмом по основанию два), метки становятся плотными (0, 1, 2, 3, …), диапазон резко сужается и switch становится конвертируемым. Поэтому при применимом преобразовании проверка диапазона пропускается — после замены диапазон всегда разумен.

Условия применимости жёсткие: тип индекса должен допускать логарифм, каждая метка должна соответствовать одному значению (без CASE_HIGH), метка должна быть неотрицательной и являться степенью двойки. При выполнении всех условий блок switch расщепляется, создаётся новый блок с проверкой «индекс — степень двойки», генерируется условный переход по результату этой проверки, затем вычисляется логарифм, он становится новым индексом switch, а метки заменяются своими логарифмами.

Bit-test кластеры: динамическое программирование

Для битовых тестов работает динамическое программирование по массиву, где элемент с номером i означает: префикс из первых i кластеров можно свести к стольким-то кластерам, а последний кластер при этом состоит из входных кластеров с j по i-1. Инициализация — ноль кластеров для пустого префикса и один кластер для первого элемента.

Перебор точек разбиения ограничен bits_in_word кластерами назад, потому что один битовый тест покрывает не более bits_in_word номеров case. Если число уникальных меток достигает m_max_case_bit_tests, цикл прерывается: проверка выгодности для текущей и всех последующих итераций всё равно даст ложь.

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

(uniq == 1 && count >= 3) || (uniq == 2 && count >= 5) || (uniq == 3 && count >= 6)

Здесь count — число меток case в кластере, uniq — число различных исходящих рёбер. То есть битовый тест считается выгодным только при достаточном покрытии для данного числа уникальных целей.

Важно не путать этот порог с порогом jump-таблиц. У jump-таблиц есть свой порог default_case_values_threshold, равный 4 при наличии casesi у целевой платформы и 5 иначе; он относится к jump_table_cluster и в проверке выгодности бит-теста не используется — там пары (uniq, count) заданы жёстко.

На второй фазе массив обходится с конца: если последний кластер состоит ровно из одного входного, он остаётся простым; иначе создаётся бит-тестовый кластер, помеченный как покрывающий весь диапазон, если разбиение начинается с нуля и заканчивается концом списка. Результат переворачивается, чтобы получить исходный порядок.

Jump-таблицы: динамическое программирование с двумя критериями

Разбиение на jump-таблицы строится похожим образом, но критериев два. Для каждого префикса хранится лучший вариант, и кандидат предпочитается, если он даёт меньше таблиц, а при равенстве — меньше случаев, не покрытых таблицами. Слишком маленькая таблица (меньше порога числа значений case) не создаётся: её случаи просто добавляются в счётчик непокрытых.

Допустимость разбиения проверяется отдельно. Сначала вычисляется диапазон от нижней границы первого кластера до верхней границы последнего; если диапазон переполняет разрядную сетку или отрицателен, разбиение отвергается. Затем отбрасываются случаи, где 100 * range переполняется. Итоговое условие:

lhs <= max_ratio * comparison_count

где lhs — это 100 * range, то есть ширина диапазона значений, умноженная на 100. comparison_count — суммарное число сравнений, которые пришлось бы выполнить для кластеров префикса, если бы jump-таблица не строилась: это мера «цены» альтернативного, сравненительного варианта. max_ratio — допустимое отношение размера таблицы к числу сравнений: во сколько раз таблица может «разрастись» относительно числа сравнений, которые она заменяет, оставаясь выгодной. Он выбирается по режиму оптимизации: при оптимизации по размеру берётся параметр для размера, иначе — для скорости.

Восстановление разбиения идёт от конца: если кластер выгоден, создаётся jump-таблица, иначе случаи добавляются по отдельности. Проверка выгодности отвергает одиночный случай и требует, чтобы число случаев было не меньше порога, который берётся из параметра, а при нулевом параметре — из целевой платформы.

Поле case_edge->aux в этом алгоритме накапливает число значений, покрытых ребром, и затем используется для вычисления вероятности ребра, а не для выбора разбиения.

Статический массив значений

Когда switch сводится к индексированной загрузке, нужно построить сам массив. Сначала выделяются временные массивы: значения по умолчанию, конструкторы и имена целей. Для каждого конструктора резервируется место под диапазон плюс один элемент.

Значения по умолчанию собираются из phi-узлов финального блока. Виртуальные операнды пропускаются. Для каждого phi значение берётся с того ребра, по которому управление приходит в финальный блок: если блок цели default-метки совпадает с финальным, ребро ищется между блоком switch и финальным блоком, иначе берётся единственное исходящее ребро этого блока. Эти значения позже заполняют промежутки между метками в конструкторах.

Тип элемента массива выбирается с оглядкой на экономию. Для нецелых и слишком широких типов возвращается исходный тип. Если режим не шире самого узкого доступного режима — тоже исходный. Если конструктор короче 2 элементов при оптимизации по размеру или короче 32 — исходный. И только если все элементы конструктора являются целочисленными константами, подбирается более узкий режим, вмещающий все константы с учётом знака.

Объявление массива помечается как mergeable, потому что его адрес никогда не берётся — из него только читают.

Линейная функция вместо таблицы

Отдельная проверка ищет в конструкторе линейную функцию a*x+b. Требуется не меньше двух элементов, первые два должны быть целочисленными константами. Коэффициенты вычисляются по первым двум значениям (индексы последовательные, поэтому разность значений и есть коэффициент наклона), свободный член — через наклон и минимальное значение диапазона. Затем каждый элемент проверяется на совпадение с a * range_min + b, при этом range_min увеличивается на единицу после каждой проверки.

Если проверка прошла, вместо статического массива генерируется арифметика: индекс приводится к нужному типу, умножается на коэффициент наклона, складывается со свободным членом и приводится к типу результата phi-узла. Равные значения — частный случай такой функции с нулевыми коэффициентами.

Генерация CFG: проверка границ и правка phi

Индексированная загрузка требует проверки, что индекс не вышел за диапазон. Строится условный переход, сравнивающий индекс с границей диапазона; условие вставляется перед инструкцией, следующей за первой загрузкой массива.

Затем блоки разбиваются. Блок switch расщепляется по условному переходу. При непрерывном диапазоне меток все промежуточные блоки, кроме финального, должны быть пусты, иначе преобразование отвергается как «non-final BB not empty»; непустой default-блок — единственное исключение, которое допускается отдельно и помечается как нестандартный default. В этом случае блок для значений в диапазоне совпадает с блоком после проверки, а блок default берётся отдельно, и создаётся ребро для значений вне диапазона. Иначе блок для значений в диапазоне получается расщеплением по последнему присваиванию, а лишнее ребро удаляется.

Два новых ребра получают вероятности: ребро для значений в диапазоне — инвертированную вероятность default, ребро для значений вне диапазона — саму вероятность default. Оба ведут в финальный блок.

Для каждого phi финального блока создаётся копия SSA-имени и присваивание значения по умолчанию, которое вставляется перед точкой вставки. Затем в phi-узлы добавляются аргументы: на ребро для значений в диапазоне — входящее имя, на ребро для значений вне диапазона — исходящее (только при обычном default). Для виртуального результата оба аргумента — виртуальный операнд.

Перенос phi-операндов на новые рёбра

Когда switch заменяется таблицей или бит-тестом, старые рёбра исчезают, а phi-узлы в блоках меток остаются. Чтобы не потерять значения, до расщепления блока switch проход запоминает для каждого phi в блоках меток определение того аргумента, который приходил по ребру из самого блока switch.

После эмиссии кластеров проход снова обходит те же phi-узлы и для каждого аргумента, у которого определения ещё нет (то есть для аргумента на новом ребре), подставляет сохранённое определение и добавляет его на соответствующее ребро. Так значения, приходившие из switch, переносятся на новые переходы.

После эмиссии дерева блок switch удаляется целиком. Если же выбирается бит-тест или случаев слишком мало, преобразование возвращает причину отказа без изменений.

Fallback: сбалансированное дерево сравнений

Когда ни таблица, ни бит-тест не подходят, остаётся дерево сравнений. Оно строится по вероятностям, а не по количеству меток.

Функция балансировки получает упорядоченный список узлов и сначала проходит его, считая число узлов и накапливая суммарную вероятность. Если узлов больше двух, список делится: берётся половина суммарной вероятности, и указатель продвигается по списку, вычитая вероятность каждого узла, пока остаток не станет меньше половины или список не кончится. Узел, на котором цикл прервался, становится pivot. Список разрывается, pivot становится головой, его левым сыном — прежняя голова, и обе половины обрабатываются рекурсивно. После рекурсии вычисляется суммарная вероятность поддерева.

Если узлов не больше двух, ветвь остаётся одним уровнем без разбиения.

Генерация сравнений для листьев работает так. Для одиночного значения вероятность перехода вычисляется как вероятность узла, делённая на сумму вероятности поддерева и вероятности default; выполняется сравнение на равенство с переходом на блок метки, после чего вероятность поддерева уменьшается на вероятность узла. Если у узла оба ребёнка — одиночные значения без детей, делаются два сравнения на равенство (сначала правое, потом левое), что экономит одно упорядоченное сравнение. Иначе ребро расщепляется, создаётся блок проверки, индекс сравнивается с верхней границей по «больше», и рекурсивно обрабатываются обе половины.

Отдельный случай — узел только с левым ребёнком, который либо имеет детей, либо не является одиночным значением. Тогда обычная обработка невозможна, потому что числа меньше значения узла не исключены: сравнение с верхней границей по «больше» увело бы на default, но это неверно. Поэтому узел обрабатывается явно: вычисляется вероятность по вероятности левого поддерева и выполняется сравнение на равенство с переходом на блок левой метки.

Пограничные случаи

Switch с единственной целью до понижения не доживает: такие конструкции удаляются при очистке CFG, поэтому на уровне разворачивания меток стоит проверка, что меток больше нуля.

Если все ветви ведут в один блок, ищется общий преемник, как описано выше; при неудаче финальный блок сбрасывается, а число уникальных целей оценивается по числу рёбер.

Проверка диапазона отвергает случаи, когда диапазон не влезает в беззнаковое машинное слово или превышает допустимое отношение диапазона к числу ветвей. Отдельная проверка требует, чтобы все блоки, кроме финального, были пусты; для непрерывного диапазона непустой default допускается и помечается как нестандартный.

Для _BitInt шире DImode выполняется сдвиг диапазона: отрицательный индекс приводится к беззнаковому типу, из индекса вычитается нижняя граница, вставляется проверка «больше максимума DImode» с разбиением блока, затем индекс приводится к DImode, а из границ всех меток также вычитается нижняя граница. После этого строится новый switch для jump table.

Default-ветвь обрабатывается отдельно: её блок находится по метке, входное ребро выбирается так же, как при сборе значений по умолчанию, а затем строится список меток в возрастающем порядке, блок switch расщепляется, для несмежных кластеров создаются пустые блоки, и кластеры эмитируются. Если единственный кластер — не простой случай, он эмитируется с default-меткой и блоком default; иначе эмитируется общий код с вероятностью default, а затем каждый несмежный кластер.

Наконец, на уровне tree-cfg соседние метки, ведущие в один блок, сливаются: если следующая метка ведёт туда же и её нижняя граница равна верхней границе предыдущей плюс один, верхняя граница расширяется, а следующая метка пропускается. Метки, ведущие в default-блок, при этом не рассматриваются. После прохода метки сдвигаются, число меток уменьшается, и функция сообщает, изменилось ли что-то.

Что видно в сгенерированном коде

Разные стратегии дают разный ассемблер, и это лучший способ понять, что произошло.

Плотный switch проверяет диапазон и делает косвенный переход по таблице адресов: сравнение с границей, переход по «выше» на default, затем переход по адресу из таблицы, где индекс масштабируется на размер указателя. Таблица — это массив адресов меток. Вариант с вычитанием базы сначала сдвигает диапазон в 0..N через вычитание, затем та же проверка и тот же косвенный переход.

Разреженный switch превращается в дерево сравнений: последовательные сравнения на равенство с отдельными значениями, переходы на метки функций, ветвление по отдельным значениям, а не по таблице.

Блочный switch сначала отсекает диапазоны сравнениями по «больше», затем внутри блока нормализует индекс вычитанием и повторно проверяет диапазон, после чего переходит на нужную метку.

Бит-тест сначала сдвигает индекс, проверяет диапазон, загружает маску, проверяет бит и по флагу переполнения выполняет переход. При отсутствии совпадения во всех случаях возвращается ноль.

Как сравнивали и что получилось

Отдельных замеров производительности в материале нет — есть только описание эвристик и примеры сгенерированного кода. Поэтому сравнивать по цифрам нечего; можно лишь сопоставить, какой код получается для каждого типа switch.

Тип switch	Что генерируется	Ключевая последовательность
Плотный	Таблица адресов	`cmp` / `ja` / `jmp [table+rax*8]`
Плотный со сдвигом базы	Таблица адресов	`lea` / `cmp` / `ja` / `jmp [table+rax*8]`
Разреженный	Дерево сравнений	`cmp` / `je` / `jle` / `cmp` / `je`
Блочный	Проверки диапазонов	`cmp` / `jg` / `sub` / `cmp` / `ja` / `jmp`
Бит-тест	Битовая маска	`lea` / `cmp` / `ja` / `mov` маски / `bt` / `jc`

Оговорка: это иллюстративные примеры кода, а не результаты замеров на конкретном железе. По ним видно, какую форму принял switch, но не насколько быстро он работает.

Что из этого следует на практике

Порядок проходов объясняет, почему форма switch зависит от контекста. Цепочка if-else по одному и тому же значению сначала сворачивается в switch, и только потом для неё выбирается стратегия — то есть писать цепочку сравнений вручную не имеет смысла, компилятор всё равно увидит switch.

Выбор между таблицей, бит-тестом и деревом определяется не только числом меток, но и числом уникальных целей. Бит-тест выгоден при трёх и более метках с одной целью, пяти и более с двумя, шести и более с тремя; при большем числе целей он не применяется вовсе. Jump-таблица ограничена отношением диапазона к числу сравнений, причём порог зависит от режима оптимизации: при оптимизации по размеру таблицы строятся реже.

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

Проверка границ и правка phi-узлов — обязательная часть преобразования, а не оптимизация. Именно поэтому проход освобождает информацию о пост-доминаторах, а не обновляет её: цена поддержки оказалась выше, чем пересчёт с нуля.

И наконец, fallback строится по вероятностям, а не по числу меток: редкие ветви уходят глубже в дерево, частые проверяются раньше. Профиль выполнения влияет на форму кода сильнее, чем количество case.