Номер Ершова

Ershov numbers , named after Andrey Petrovich Yershov , ^[1] используются при оптимизации кода для минимизации количества выделяемых регистров . Числа Ершова можно использовать в методах оптимального выбора регистров, когда в блоке кода имеется только одно выражение. Учитывая выражение E = E ₁ op E _2, цель состоит в том, чтобы сгенерировать код, чтобы либо минимизировать количество используемых регистров, либо, если доступно недостаточное количество регистров, минимизировать количество требуемых нерегистровых временных элементов.

Определение

Число Ершова n узла в данном дереве выражений определяется следующим образом: ^[2]^[3]

Каждый лист имеет n = 1.
Для узла с одним дочерним элементом n такое же, как и у дочернего узла.
Для узла с двумя дочерними элементами n определяется как:

n={\begin{cases}max(child_{1},child_{2})&child_{1}\neq child_{2}\\child_{1}+1&child_{1}=child_{2}\end{cases}}

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

Пример

Предположим, у нас есть дерево выражений с операцией «+» в корне, а левое и правое поддеревья имеют числа Ершова 3 и 4 соответственно. Число Ершова этого узла равно 4, поэтому мы сможем сгенерировать код выражения, используя 4 регистра.

Сгенерируйте код для оценки правильного дочернего элемента, используя регистры r1, r2, r3 и r4. Поместите результат в r1.
Сгенерируйте код для оценки левого дочернего элемента, используя регистры r2, r3 и r4. Поместите результат в r2.
Выдать инструкцию ADD r1, r1, r2, который складывает r1 и r2 и сохраняет результат в r1.

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

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

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

В идеальном случае, если имеется n регистров и для первого подвыражения требуется n регистров, а для следующего подвыражения требуется n - 1 регистров, для хранения результата первого выражения можно использовать один регистр, и их все равно будет n - 1. регистры доступны для вычисления следующего подвыражения, поэтому вообще не требуется загрузка или сохранение из памяти. ^[1]

Если число Ершова корня дерева выражений больше количества доступных регистров, число Ершова также можно использовать для определения объема требуемой дополнительной временной памяти, например, в стеке . ^[1]

См. также

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

Ссылки

^ Jump up to: ^а ^б ^с «Заметки по генерации кода» (PDF) . Департамент компьютерных наук Университета Калгари. 14 сентября 2007 года . Проверено 30 мая 2022 г.
^ «Оптимальная генерация кода (для выражений) и анализ потока данных» (PDF) . Карлтонский университет . Проверено 30 мая 2022 г.
^ «Генерация кода, глава 8» (PDF) . Университет Западного Мичигана . Проверено 30 мая 2022 г.

[ucalgary-1] Jump up to: ^а ^б ^с «Заметки по генерации кода» (PDF) . Департамент компьютерных наук Университета Калгари. 14 сентября 2007 года . Проверено 30 мая 2022 г.

[2] «Оптимальная генерация кода (для выражений) и анализ потока данных» (PDF) . Карлтонский университет . Проверено 30 мая 2022 г.

[3] «Генерация кода, глава 8» (PDF) . Университет Западного Мичигана . Проверено 30 мая 2022 г.

[1]

[2]

[3]