Sethi–Ullman algorithm: Difference between revisions

Revision as of 18:10, 12 November 2017

Revision as of 10:33, 22 December 2017

Line 2:

==Overview==

When [[code generation (compiler)|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 [[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 offewest instructions possible as well as the least number offewest 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. The algorithm also does not take advantage of common subexpressions or apply directly to expressions represented as general directed acyclic graphs rather than trees.

==Simple Sethi–Ullman algorithm==