On the Sethi-Ullman algorithm

Abstract

A directed acyclic graph (dag) can be used to represent an arithmetic expression consisting of sequences of binary operations on arguments. The Sethi-Ullman algorithm (Journal of the ACM, Vol. 17 No. 4, pp. 715-728) generates optimal object code for a machine with N≧1 registers and unlimited memory capacity when the dag is a binary tree.

We first describe a dag labeling algorithm which gives the minimum number of registers required to evaluate any node without any stores.

We then define a subclass of dags, the 1-load binary dags, employing a tree-like grammar, and modify the Sethi-Ullman algorithm to include this subclass but only when N = 2 registers. The proof of optimality relies on the use of syntax directed translation schemas. Modification of the algorithm to include all dags, or to allow N > 2 registers, appears difficult.

Keywords:

• arithmetic expression
• code generation
• compilers
• object-code optimization
• register assignment
• trees

C.R. Categories:

• 4.12
• 5.24
• 5.32