セシィ–ウルマン法

セシィ–ウルマン法（英: Sethi–Ullman algorithm）とは、コンパイラにおいて数式に対応したコードを生成する際に、必要な命令数やレジスタ数を最小にするアルゴリズムである。ただし前提条件として、数式内の各演算に交換法則と結合法則が成り立たなければならない。分配法則は成り立たなくてもよい。交換法則や結合法則が成り立たない場合もこのアルゴリズムを適用可能だが、その場合、数式の変形はできない。

単純なセシィ–ウルマン法

セシィ–ウルマン法は次のように動作する（RISCの場合）。

1. 抽象構文木を先頭からか最後尾から見ていく。
   1. 定数でない葉ノードについて、1 を割り当てる（すなわち、その変数などを保持するのにレジスタが1つ必要であることを示す）。定数の葉ノードについては、0 を割り当てる。
   2. 葉でないノード n について、n 配下の部分木の評価に必要なレジスタ数を割り当てる。左側の部分木に必要なレジスタ数（l）が、右側の部分木に必要なレジスタ数（r）と異なる場合、現在見ているノード n が必要とするレジスタ数は max(l,r) となる。l == r の場合、現在ノードが必要とするレジスタ数は l + 1 となる。
2. コード展開
   1. ノード n の左側の部分木の計算に要するレジスタ数が右側の部分木で必要なレジスタ数より大きい場合、先に左側の部分木を評価する（対応するコードを生成する）。これは、右側を先に評価すると、その結果を保持するためのレジスタが余分に必要となって、レジスタが足りなくなる可能性が大きくなるためである。右側の部分木が左側よりもレジスタ数を多く必要とする場合、同様に右側を先に評価する。両側の必要とするレジスタ数が同じ場合、評価する順序はどちらでもよい。

例

数式 $a=(b+c)*(d+3)$ は、抽象構文木では次のように表される。

                 =
              / \
             a   *
                / \
               /   \
              +     +
             / \   / \
            b   c d   3

このアルゴリズムを適用するに当たって、数式の右辺 $(b+c)*(d+3)$ のみを考慮する。すなわち、代入 '=' の右の部分木のみを参照する。

                 *
              / \
             /   \
            +     +
           / \   / \
          b   c d   3

木構造を（とりあえず先頭から）見ていき、各部分木の評価に必要なレジスタを割り当てていく（$(b+c)*(d+3)$ の最後の被加数は定数であることに注意）。

                 *2
              / \
             /   \
            +2    +1
           / \   / \
          b1  c1d1  30

この木構造から、'*' の左の部分木の計算には2つのレジスタが必要だが、右の部分木の計算には1つのレジスタだけでよいことが分かる。従って、この式を計算する時点で使っていないレジスタが2つしかない可能性もあるので、先に左側の計算を行うコードを生成する。レジスタを1つしか必要としない右側の部分木を計算するコードを先に生成すると、左側の計算をする間、右の計算結果を保持しておくレジスタが必要となり、全部で3つのレジスタが必要となってしまう。先に左側を計算するには2つのレジスタが必要だが、結果の保持には1つのレジスタがあればよいので、右の計算に必要な1つのレジスタと合わせても、2つのレジスタがあれば全体を計算可能である。

改良版

セシィ-ウルマン法の改良として、使われている演算の代数的性質を利用して、数式を最初に変換する手法がある。

外部リンク

• The Generation of Optimal Code for Arithmetic Expressions Ravi Sethi, J. D. Ullman, Journal of the ACM, Vol. 17, No. 4, October 1970, pp. 715-728
• Code Generation for Trees