Алгоритм Сети – Ульмана

В информатике алгоритм Сетхи-Ульмана — это алгоритм, названный в честь Рави Сетхи и Джеффри Д. Ульмана , его изобретателей, предназначенный для перевода абстрактных синтаксических деревьев в машинный код меньше регистров , который использует как можно .

Обзор

При создании кода для арифметических выражений компилятор должен решить, какой способ лучше всего преобразовать выражение с точки зрения количества используемых инструкций, а также количества регистров, необходимых для вычисления определенного поддерева. Особенно в случае, когда свободных регистров мало, порядок вычислений может иметь важное значение для длины сгенерированного кода, поскольку разный порядок может привести к тому, что большее или меньшее количество промежуточных значений будет перенесено в память, а затем восстановлено. Алгоритм Сети-Ульмана (также известный как нумерация Сети-Ульмана наибольшая коммутативность и ассоциативность , но законы распределения, т.е. ) создает код, который требует наименьшего количества инструкций, а также наименьшего количества ссылок на хранилище (при условии, что к используемым операторам применимы $a*b+a*c=a*(b+c)$ не держи). Алгоритм успешен и в том случае, если для используемых выражений не выполняются ни коммутативность , ни ассоциативность и, следовательно, невозможно применить арифметические преобразования. Алгоритм также не использует преимущества общих подвыражений и не применяется непосредственно к выражениям, представленным в виде общих ориентированных ациклических графов, а не деревьев.

Простой алгоритм Сетхи – Ульмана

Простой алгоритм Сетхи-Ульмана работает следующим образом (для архитектуры загрузки/сохранения ):

Обход абстрактного синтаксического дерева в предварительном или обратном порядке.
1. Для каждого листового узла, если он является непостоянным левым дочерним элементом, присвойте 1 (т. е. для хранения переменной/поля/т. д. необходим 1 регистр), в противном случае присвойте 0 (это непостоянный правый дочерний узел или постоянный листовой узел (правая часть операции – литералы, значения)).
2. Для каждого нелистового узла, если левому и правому поддеревьям соответственно требуется разное количество регистров l и r , тогда присвойте max( l , r ), в противном случае присвойте r + 1.
Чтобы выдать код, если поддеревьям требуется разное количество регистров, сначала оцените поддерево, которому требуется наибольшее количество регистров (поскольку регистр, необходимый для сохранения результата одного поддерева, может привести к потере другого ), в противном случае порядок не имеет значения.

Пример

Для арифметического выражения $a=(b+c+f*g)*(d+3)$ , абстрактное синтаксическое дерево выглядит следующим образом:

               =
              / \
             a   *
                / \
               /   \
              +     +
             / \   / \
            /   \ d   3
           +     *
          / \   / \
         b   c f   g

Чтобы продолжить работу с алгоритмом, нам нужно только изучить арифметическое выражение $(b+c+f*g)*(d+3)$ , т.е. нам нужно посмотреть только правое поддерево присваивания '=':

               *
              / \
             /   \
            +     +
           / \   / \
          /   \ d   3
         +     *
        / \   / \
       b   c f   g

Теперь мы начинаем обход дерева (пока в предварительном порядке), назначая количество регистров, необходимых для вычисления каждого поддерева (обратите внимание, что последнее слагаемое в выражении $(b+c+f*g)*(d+3)$ является константой):

               *₂
              / \
             /   \
            +₂    +₁
           / \   / \
          /   \ d₁  3₀
         +₁   *₁
        / \   / \
       b₁  c₀f₁  g₀

Из этого дерева видно, что нам нужно 2 регистра для вычисления левого поддерева '*', но только 1 регистр для вычисления правого поддерева. Узлы «c» и «g» не нуждаются в регистрах по следующим причинам: Если T — лист дерева, то число регистров для оценки T равно 1 или 0 в зависимости от того, является ли T левым или правым поддеревом (поскольку такую операцию, как добавление R1, A может обрабатывать нужный компонент A напрямую, не сохраняя его в регистр). Поэтому сначала мы начнем генерировать код для левого поддерева, потому что мы можем столкнуться с ситуацией, когда у нас останется только 2 регистра для вычисления всего выражения. Если бы мы теперь сначала вычислили правое поддерево (которому нужен только 1 регистр), нам тогда потребовался бы регистр для хранения результата правого поддерева при вычислении левого поддерева (которому все равно потребовалось бы 2 регистра), поэтому нам потребовалось бы 3 регистра одновременно. Для вычисления левого поддерева сначала требуются 2 регистра, но результат может быть сохранен в 1, а поскольку для вычисления правого поддерева требуется только 1 регистр, для вычисления выражения можно использовать только 2 оставшихся регистра.

Расширенный алгоритм Сети – Ульмана

В расширенной версии алгоритма Сетти-Ульмана арифметические выражения сначала преобразуются с использованием алгебраических свойств используемых операторов.

См. также

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

Ссылки

Сетхи, Рави ; Уллман, Джеффри Д. (1970), «Генерация оптимального кода для арифметических выражений», Журнал Ассоциации вычислительной техники , 17 (4): 715–728, doi : 10.1145/321607.321620 , hdl : 10338.dmlcz/101207 .

Внешние ссылки

Генерация кода для деревьев