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

Алгоритм Сети — Ульмана
Назван в честь	Ravi Sethi[d] и Джеффри Ульман
Предназначение	поиск оптимального порядка трансляции выражения
Структура данных	граф

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

Обзор

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

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

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

1. Обход абстрактного синтаксического дерева в прямом или обратном порядке
   1. Любому неконстантному листовому узлу назначим 1 (то есть нужен 1 регистр для хранения переменной/поля/и т.д.). Любому константному листу (правая сторона операции – литералы, значения) назначим 0.
   2. Любому нелистовому узлу n назначаем число регистров, нужных для вычисления соответствующего поддерева n. Если число регистров, необходимых в левом поддереве (l), не равно числу регистров, необходимых в правом поддереве (r), число регистров, нужных в текущем узле n равно max(l, r). Если l == r, то число регистров, необходимых для текущего узла, равно $r+1$.
2. Формирование кода
   1. Если число регистров, нужное для вычисления левого поддерева узла n больше, чем число регистров для правого поддерева, то левое поддерево вычисляется в первую очередь (поскольку может потребоваться один дополнительный регистр для сохранения результата правого поддерева, перекрывается регистром левого поддерева). Если правое поддерево требует больше регистров, чем левое, то правое дерево вычисляется первым. Если оба поддерева требуют равное число регистров, то порядок выполнения не играет роли.

Пример

Для арифметического выражения $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)$ является константой):

               *2
              / \
             /   \
            +2    +1
           / \   / \
          /   \ d1  30
         +1   *1
        / \   / \
       b1  c0f1  g0

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

Улучшенный алгоритм Сети — Ульмана

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

См. также

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

Ссылки

• Code Generation for Trees Архивная копия от 17 июля 2012 на Wayback Machine