Sethi–Ullman algorithm: Difference between revisions

Revision as of 12:51, 17 June 2010

Revision as of 05:39, 5 February 2011

Line 1:

In [[computer science]], the '''Sethi–Ullman algorithm''' is an [[algorithm]] named after [[Ravi Sethi]] and [[Jeffrey D. Ullman]], its inventors, for translating [[abstract syntax tree]]s into [[machine code]] that uses as few instructions as possible.

When [[Code generation|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 if free registers are scarce). The '''Sethi–Ullman algorithm''' (also known as '''Sethi–Ullman numbering''') fulfills the property of producing code which needs the least number of instructions possible as well as the least number of storage references (under the assumption that at the most [[commutativity]] and [[associativity]] apply to the operators used, but distributive laws i.e. <math>a * b + a * c = a * (b + c)</math> do not hold). Please note that the algorithm succeeds as well if neither [[commutativity]] nor [[associativity]] hold for the expressions used, and therefore arithmetic transformations can not be applied.

==Overview==

When [[Code generation|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. (especiallyEspecially ifin 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 [[register allocation|spilled]] to memory and then restored. The '''Sethi–Ullman algorithm''' (also known as '''Sethi–Ullman numbering''') fulfills the property of producing code which needs the least number of instructions possible as well as the least number of storage references (under the assumption that at the most [[commutativity]] and [[associativity]] apply to the operators used, but distributive laws i.e. <math>a * b + a * c = a * (b + c)</math> do not hold). Please note that the algorithm succeeds as well if neither [[commutativity]] nor [[associativity]] hold for the expressions used, and therefore arithmetic transformations can not be applied.

==Simple Sethi–Ullman algorithm==

Line 50 ⟶ 53:

==Advanced Sethi–Ullman algorithm==

In an advanced version of the '''Sethi–Ullman algorithm''', the arithmetic expressions are first transformed, exploiting the algebraic properties of the operators used.

==See also==

*[[Strahler number]], the minimum number of registers needed to evaluate an expression without any external storage

==References==

*[http://portal.acm.org/{{citation.cfm?doid|title=321607.321620 The Generation of Optimal Code for Arithmetic Expressions] [[|first1=Ravi |last1=Sethi]],|author1-link=Ravi [[Sethi|first2=Jeffrey D. |last2=Ullman|J.author2-link=Jeffrey D. Ullman]], |journal=[[Journal of the [[Association for Computing Machinery|ACM]], Vol. |volume=17, No. |issue=4, October |year=1970, pp. |pages=715–728|doi=10.1145/321607.321620}}.

==External links==

*[http://portal.acm.org/citation.cfm?doid=321607.321620 The Generation of Optimal Code for Arithmetic Expressions] [[Ravi Sethi]], [[Jeffrey D. Ullman|J. D. Ullman]], Journal of the [[Association for Computing Machinery|ACM]], Vol. 17, No. 4, October 1970, pp. 715–728

*[http://lambda.uta.edu/cse5317/fall02/notes/node40.html Code Generation for Trees]