Алгоритм Сети-Уллмана: Оптимизация использования регистров при компиляции
Sethi–Ullman algorithm
Алгоритм Сети-Уллмана: оптимальная генерация машинного кода из AST с минимальным использованием регистров. Эффективен при ограниченных ресурсах и сложных выражениях.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
В информатике алгоритм Сети–Уллмана — это алгоритм, названный в честь его изобретателей, Рави Сети и Джеффри Д. Уллмана, предназначенный для преобразования абстрактных синтаксических деревьев в машинный код с использованием минимального количества регистров.
In computer science, the Sethi–Ullman algorithm is an algorithm named after Ravi Sethi and Jeffrey D. Ullman, its inventors, for translating abstract syntax trees into machine code that uses as few registers as possible.
Обзор
При генерации кода для арифметических выражений компилятор должен определить оптимальный способ трансляции выражения с точки зрения количества используемых инструкций и числа регистров, необходимых для вычисления заданного поддерева. Особенно, когда свободных регистров недостаточно, порядок вычисления может существенно влиять на длину генерируемого кода, поскольку различные порядки могут приводить к большему или меньшему числу промежуточных значений, которые необходимо сбрасывать в память и затем восстанавливать. Алгоритм Сети–Уллмана (также известный как нумерация Сети–Уллмана) генерирует код, требующий минимального количества инструкций и минимального числа обращений к памяти (при условии, что коммутативность и ассоциативность применимы к используемым операторам, но законы дистрибутивности – нет). Алгоритм также эффективен, если для используемых выражений не выполняются ни коммутативность, ни ассоциативность, и, следовательно, арифметические преобразования неприменимы. Кроме того, алгоритм не использует общие подвыражения и не применяется напрямую к выражениям, представленным в виде общих ориентированных ациклических графов, а не деревьев.
When generating code for arithmetic expressions, the compiler has to decide which is the best way to translate the expression in terms of number of instructions used as well as number of registers needed to evaluate a certain subtree. Especially in the case that free registers are scarce, the order of evaluation can be important to the length of the generated code, because different orderings may lead to larger or smaller numbers of intermediate values being spilled to memory and then restored. The Sethi–Ullman algorithm (also known as Sethi–Ullman numbering) produces code which needs the fewest instructions possible as well as the fewest storage references (under the assumption that at the most commutativity and associativity apply to the operators used, but distributive laws i. e. do not hold). The algorithm succeeds as well if neither commutativity nor associativity hold for the expressions used, and therefore arithmetic transformations can not be applied. The algorithm also does not take advantage of common subexpressions or apply directly to expressions represented as general directed acyclic graphs rather than trees.
Расширенный алгоритм Сети-Уллмана
В усовершенствованной версии алгоритма Сети–Уллмана арифметические выражения сначала преобразуются с использованием алгебраических свойств применяемых операторов.
In an advanced version of the Sethi–Ullman algorithm, the arithmetic expressions are first transformed, exploiting the algebraic properties of the operators used.