Числа Ершова используются в оптимизации кода для минимизации числа регистров, используемых выражением. Они могут быть использованы в методах оптимального выбора регистров, когда имеется только одно выражение в блоке кода. Если дано выражение E = E1 операция E2, то целью является сгенерировать код так, чтобы минимизировать общее число использованных регистров, а в случае недостаточного числа доступных регистров, минимизировать число временных переменных (то есть слов памяти).
Число Ершова n узла заданного определяется следующим образом: Все листья имеют значение 1. Число Ершова внутреннего узла с одним дочерним узлом равно числу дочернего узла. Число Ершова узла с двумя дочерними равно: а) наибольшему из чисел дочерних узлов, если числа Ершова дочерних узлов различны; б) числу дочернего узла, увеличенного на 1, если числа Ершова дочерних узлов совпадают. Число Ершова узла представляет минимальное число регистров, требующихся для выполнения подвыражения, корнем которого является данный узел. Идея заключается в выполнении сначала дочернего выражения с бо́льшим числом Ершова, затем второго дочернего выражения, а после чего операции в корне.
Пример
Рассмотрим выражение . Пометим узлы дерева (см. рисунок справа) этого выражения метками, равными числам Ершова. Мы имеем операцию '+' в корне, метки левого и правого поддеревьев равные 2, такие, что метка корня равна 3, следовательно, потребуется 3 регистра для реализации выражения.
Каждый из пяти листьев имеет метки "1" (согласно 1-му правилу). Согласно правилу 3, п. "б" узлы t1 и t2 получают метки, равные 2. Теперь узел t3 имеет дочерние узлы с разными метками, так что для него метка будет также 2 (по правилу 3, п. "а"). Узел t4 опять имеет дочерние узлы с равными метками, так что метка для него будет равна 3 (правило 3, п. "б"). Генерация кода Ниже приведён рекурсивный алгоритм генерации машинного кода. В алгоритме имеется «база» для регистров, то есть для узла с числом Ершова k будут использованы регистры :
Для генерации машинного кода внутреннего узла (не листа) с числом Ершова k и двумя дочерними узлами с равными числами (равных k-1) выполняем: Создаём код для правого дочернего узла с базой , результат будет помещён в регистр ; Создаём код для левого дочернего узла с базой , результат будет помещён в регистр ; Создаём команду «Операция» ; Пусть рассматривается узел с меткой k и дочерние узлы имеют разные метки. В этом случае один из дочерних узлов имеет метку k, а другой некоторую меньшую метку m. Для такого узла выполняем следующее: Создаём код для дочернего узла с бо́льшим числом Ершова, используем базу b, результат будет помещён в регистр ; Создаём код для другого дочернего узла, используем базу b, результат будет помещён в регистр ; Создаём команду «Операция» или «Операция» (зависит от того, где находится узел с бо́льшим числом Ершова); Для листового узла с операндом x создаём команду «Загрузить» .
Вычисление выражений при недостаточном числе регистров Если число Ершова корневого узла выражения больше доступного числа регистров, то число Ершова может быть использовано для генерации кода с минимальным числом операций загрузки и сохранения следующим образом
Для корня выполняем Создаём код для дочернего узла с бо́льшим числом Ершова; Создаём команду сохранения результата в памяти; Создаём код для дочернего узла меньшим числом Ершова; Создаём инструкцию загрузки запомненного значения в регистр; Создаём команду, выполняющую операцию в корне.
См. также Число Стралера — Философова, минимальное число регистров, необходимых для выполнения выражения без внешней памяти Алгоритм Сети — Ульмана, по существу, та же концепция Примечания
Литература
Ссылки Carleton University page on Optimal Code Generation and using Ershov numbers.
Категория:Синтаксис Категория:Оптимизация программного обеспечения