Алгоритм Сетхи – Уллмана - Sethi–Ullman algorithm

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

Обзор

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

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

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

1. Пройдите через абстрактное синтаксическое дерево в предварительном или постзаказе
   1. Для каждого непостоянного листового узла присвойте 1 (т. Е. 1 регистр необходим для хранения переменной / поля и т. Д.), Если он является левым дочерним элементом своего родителя, иначе назначьте 0. Для каждого константного листового узла (RHS узла операция - литералы, значения), присвойте 0.
   2. Для каждого нелистового узла п, назначьте количество регистров, необходимое для оценки соответствующих поддеревьев п. Если количество регистров необходимо в левом поддереве (л) не равны количеству регистров, необходимых в правом поддереве (р), количество регистров, необходимых для текущего узла п равно max (l, r). Если л == г, то количество регистров, необходимых для текущего узла, равно р + 1.
2. Код эмиссии
   1. Если количество регистров, необходимое для вычисления левого поддерева узла п больше, чем количество регистров для правого поддерева, тогда сначала оценивается левое поддерево (так как возможно, что еще один регистр, необходимый правому поддереву для сохранения результата, сделает левое поддерево проливать ). Если правому поддереву требуется больше регистров, чем левому поддереву, сначала соответственно оценивается правое поддерево. Если для обоих поддеревьев требуется одинаковое количество регистров, то порядок оценки не имеет значения.

Пример

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

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

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

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

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

               *2              / \             /   \            +2    +1           /  /  /  d1  30         +1   *1        /  /  b1  c0ж1  грамм0

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

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

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

Смотрите также

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

Рекомендации

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

внешняя ссылка

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