Компиляция операторов switch для простой виртуальной машины

Question

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

switch (e) {
  case 0: { ... }
  case 1: { ... }
  ...
  case k: { ... }
}

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

Прямо сейчас я использую символические метки для первого прохода, а во время второго прохода я собираюсь разрешить метки для реальных целей перехода, потому что наличие меток значительно упрощает первоначальную компиляцию, чтобы складывать инструкции. Моя идея сейчас состоит в том, чтобы обобщить то, что в книге, для любой последовательности значений падежей в любом порядке по следующей схеме. Назовите значения дела c1, c2, ..., cn и соответствующие ярлыки j1, j2, ..., jn затем сгенерируйте следующую последовательность команд, принимая значение e находится на вершине стека:

dup, loadc c1, eq, jumpnz j1,
dup, loadc c2, eq, jumpnz j2,
...
dup, loadc cn, eq, jumpnz jn,
pop, jump :default
j1: ...
j2: ...
...
jn: ...
default: ...

Надеемся, что запись понятна, но если нет: dup = дублирующее значение на вершине стека, loadc c = толкать константу c на вершине стека, eq = сравнить два верхних значения в стеке и нажать 0 или 1 на основе сравнения, jumpnz j = перейти к метке j если значение верхнего стека не равно 0, label: = то, что будет преобразовано в фактический адрес во время второго этапа компиляции.

Итак, мой вопрос: каковы другие способы составления операторов switch? Мой способ сделать это намного менее компактен, чем индексированная таблица переходов для смежных диапазонов значений регистра, но работает довольно хорошо, когда есть большие промежутки.

Answer 1

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