Число Ершова

Числа Ершова используются в оптимизации кода для минимизации числа регистров, используемых выражением. Они могут быть использованы в методах оптимального выбора регистров, когда имеется только одно выражение в блоке кода. Если дано выражение E = E₁ операция E₂, то целью является сгенерировать код так, чтобы минимизировать общее число использованных регистров, а в случае недостаточного числа доступных регистров, минимизировать число временных переменных (то есть слов памяти).

Число Ершова n узла заданного дерева выражения определяется следующим образом:

1. Все листья имеют значение 1.
2. Число Ершова внутреннего узла с одним дочерним узлом равно числу дочернего узла.
3. Число Ершова узла с двумя дочерними равно:

   а) наибольшему из чисел дочерних узлов, если числа Ершова дочерних узлов различны;

   б) числу дочернего узла, увеличенного на 1, если числа Ершова дочерних узлов совпадают.

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

Пример

Дерево выражения $(a-b)+e\times (c+d)$. Справа от узла указаны числа Ершова. Значения a, b, c, d, e — исходные данные, числа tX — промежуточные значения. Пример взят из книги Компиляторы (Ахо, Лам, Сети, Ульман)

Рассмотрим выражение $(a-b)+e\times (c+d)$. Пометим узлы дерева (см. рисунок справа) этого выражения метками, равными числам Ершова. Мы имеем операцию '+' в корне, метки левого и правого поддеревьев равные 2, такие, что метка корня равна 3, следовательно, потребуется 3 регистра для реализации выражения.

Каждый из пяти листьев имеет метки "1" (согласно 1-му правилу). Согласно правилу 3, п. "б" узлы t1 и t2 получают метки, равные 2. Теперь узел t3 имеет дочерние узлы с разными метками, так что для него метка будет также 2 (по правилу 3, п. "а"). Узел t4 опять имеет дочерние узлы с равными метками, так что метка для него будет равна 3 (правило 3, п. "б").

Генерация кода

Ниже приведён рекурсивный алгоритм генерации машинного кода. В алгоритме имеется «база» для регистров, то есть для узла с числом Ершова k будут использованы регистры $R_{b},R_{b+1},\dots ,R_{b+k-1}$:

1. Для генерации машинного кода внутреннего узла (не листа) с числом Ершова k и двумя дочерними узлами с равными числами (равных k-1) выполняем:
   • Создаём код для правого дочернего узла с базой $b+1$, результат будет помещён в регистр $R_{b+k-1}$;
   • Создаём код для левого дочернего узла с базой $b$, результат будет помещён в регистр $R_{b+k-2}$;
   • Создаём команду «Операция» $R_{b+k-1},R_{b+k-2},R_{b+k-1}$;
2. Пусть рассматривается узел с меткой k и дочерние узлы имеют разные метки. В этом случае один из дочерних узлов имеет метку k, а другой некоторую меньшую метку m. Для такого узла выполняем следующее:
   • Создаём код для дочернего узла с бо́льшим числом Ершова, используем базу b, результат будет помещён в регистр $R_{b+k-1}$;
   • Создаём код для другого дочернего узла, используем базу b, результат будет помещён в регистр $R_{b+m-1}$;
   • Создаём команду «Операция» $R_{b+k-1},R_{b+m-2},R_{b+k-1}$ или «Операция» $R_{b+k-1},R_{b+k-1},R_{b+m-1}$ (зависит от того, где находится узел с бо́льшим числом Ершова);
3. Для листового узла с операндом x создаём команду «Загрузить» $R_{b},x$.

Вычисление выражений при недостаточном числе регистров

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

Для корня выполняем

1. Создаём код для дочернего узла с бо́льшим числом Ершова;
2. Создаём команду сохранения результата в памяти;
3. Создаём код для дочернего узла меньшим числом Ершова;
4. Создаём инструкцию загрузки запомненного значения в регистр;
5. Создаём команду, выполняющую операцию в корне.

См. также

• Число Стралера — Философова, минимальное число регистров, необходимых для выполнения выражения без внешней памяти
• Алгоритм Сети — Ульмана, по существу, та же концепция

Ссылки

• Carleton University page on Optimal Code Generation and using Ershov numbers.