Меню Главная Случайная статья Настройки Число Ершова Материал из https://ru.wikipedia.org Числа Ершова используются в оптимизации кода для минимизации числа регистров, используемых выражением. Они могут быть использованы в методах оптимального выбора регистров, когда имеется только одно выражение в блоке кода. Если дано выражение E = E1 операция E2, то целью является сгенерировать код так, чтобы минимизировать общее число использованных регистров, а в случае недостаточного числа доступных регистров, минимизировать число временных переменных (то есть слов памяти). Число Ершова n узла заданного дерева выражения[англ.] определяется следующим образом[1]: Все листья имеют значение 1. Число Ершова внутреннего узла с одним дочерним узлом равно числу дочернего узла. Число Ершова узла с двумя дочерними равно: а) наибольшему из чисел дочерних узлов, если числа Ершова дочерних узлов различны; б) числу дочернего узла, увеличенного на 1, если числа Ершова дочерних узлов совпадают. Число Ершова узла представляет минимальное число регистров, требующихся для выполнения подвыражения, корнем которого является данный узел. Идея заключается в выполнении сначала дочернего выражения с большим числом Ершова, затем второго дочернего выражения, а после чего операции в корне. Содержание 1 Пример 2 Генерация кода 2.1 Вычисление выражений при недостаточном числе регистров 3 См. также 4 Примечания 5 Литература 6 Ссылки Пример Рассмотрим выражение ${\displaystyle (a-b)+e\times (c+d)}$. Пометим узлы дерева (см. рисунок справа) этого выражения метками, равными числам Ершова. Мы имеем операцию '+' в корне, метки левого и правого поддеревьев равные 2, такие, что метка корня равна 3, следовательно, потребуется 3 регистра для реализации выражения. Каждый из пяти листьев имеет метки "1" (согласно 1-му правилу). Согласно правилу 3, п. "б" узлы t1 и t2 получают метки, равные 2. Теперь узел t3 имеет дочерние узлы с разными метками, так что для него метка будет также 2 (по правилу 3, п. "а"). Узел t4 опять имеет дочерние узлы с равными метками, так что метка для него будет равна 3 (правило 3, п. "б"). Генерация кода Ниже приведён рекурсивный алгоритм генерации машинного кода[2]. В алгоритме имеется «база» для регистров, то есть для узла с числом Ершова k будут использованы регистры ${\displaystyle R_{b},R_{b+1},\dots ,R_{b+k-1}}$: Для генерации машинного кода внутреннего узла (не листа) с числом Ершова k и двумя дочерними узлами с равными числами (равных k-1) выполняем: Создаём код для правого дочернего узла с базой ${\displaystyle b+1}$, результат будет помещён в регистр ${\displaystyle R_{b+k-1}}$; Создаём код для левого дочернего узла с базой ${\displaystyle b}$, результат будет помещён в регистр ${\displaystyle R_{b+k-2}}$; Создаём команду «Операция» ${\displaystyle R_{b+k-1},R_{b+k-2},R_{b+k-1}}$; Пусть рассматривается узел с меткой k и дочерние узлы имеют разные метки. В этом случае один из дочерних узлов имеет метку k, а другой некоторую меньшую метку m. Для такого узла выполняем следующее: Создаём код для дочернего узла с большим числом Ершова, используем базу b, результат будет помещён в регистр ${\displaystyle R_{b+k-1}}$; Создаём код для другого дочернего узла, используем базу b, результат будет помещён в регистр ${\displaystyle R_{b+m-1}}$; Создаём команду «Операция» ${\displaystyle R_{b+k-1},R_{b+m-2},R_{b+k-1}}$ или «Операция» ${\displaystyle R_{b+k-1},R_{b+k-1},R_{b+m-1}}$ (зависит от того, где находится узел с большим числом Ершова); Для листового узла с операндом x создаём команду «Загрузить» ${\displaystyle R_{b},x}$. Вычисление выражений при недостаточном числе регистров Если число Ершова корневого узла выражения больше доступного числа регистров, то число Ершова может быть использовано для генерации кода с минимальным числом операций загрузки и сохранения следующим образом[3] Для корня выполняем Создаём код для дочернего узла с большим числом Ершова; Создаём команду сохранения результата в памяти; Создаём код для дочернего узла меньшим числом Ершова; Создаём инструкцию загрузки запомненного значения в регистр; Создаём команду, выполняющую операцию в корне. См. также Число Стралера — Философова, минимальное число регистров, необходимых для выполнения выражения без внешней памяти Алгоритм Сети — Ульмана, по существу, та же концепция Примечания Ахо, Лам, Сети, Ульман, 2008, с. 689-692. Ахо, Лам, Сети, Ульман, 2008, с. 690. Ахо, Лам, Сети, Ульман, 2008, с. 692-693. Литература Альфред В. Ахо, Моника С. Лам, Рави Сети, Джеффри Д. Ульман. 8.10.1 Числа Ершова // Компиляторы (принципы, технологии и инструментарий). — Москва, Санкт-Петербург, Киев: «Вильямс», 2008. — ISBN 978-5-8459-1349-4. Ссылки Carleton University page on Optimal Code Generation and using Ershov numbers.