セティ・ウルマンアルゴリズム

コンピュータサイエンスにおいて、セティ・ウルマンアルゴリズムは、発明者であるラヴィ・セティとジェフリー・D・ウルマンにちなんで名付けられた、抽象構文木をできるだけ 少ないレジスタを使用するマシンコードに変換するアルゴリズムです。

算術式のコードを生成する場合、コンパイラは、使用される命令の数と特定のサブツリーを評価するために必要なレジスタの数の観点から、どの方法が式を変換するのに最適かを決定する必要があります。特に空きレジスタが少ない場合、評価の順序は生成されるコードの長さに重要になることがあります。順序が異なると、メモリにスピルされてから復元される中間値の数が多くなったり少なくなったりする可能性があるためです。Sethi-Ullman アルゴリズム ( Sethi-Ullman 番号付けとも呼ばれる) は、必要な命令が最小限で、ストレージ参照も最小限のコードを生成します (使用される演算子にはせいぜい可換法則と結合法則が適用され、分配法則は成り立たないという仮定の下)。使用される式に可換法則も結合法則も成立せず、したがって算術変換を適用できない場合でも、このアルゴリズムは成功します。また、このアルゴリズムは共通部分式を利用したり、ツリーではなく一般的な有向非巡回グラフとして表される式に直接適用したりしません。 ${\displaystyle a*b+a*c=a*(b+c)}$

単純なSethi -Ullman アルゴリズムは次のように動作します (ロード/ストア アーキテクチャの場合)。

1. 抽象構文木を前順または後順で 走査する
   1. すべてのリーフ ノードについて、それが非定数の左の子である場合は 1 を割り当てます (つまり、変数/フィールドなどを保持するには 1 つのレジスタが必要です)。それ以外の場合は 0 を割り当てます (非定数の右の子または定数のリーフ ノード (操作の RHS - リテラル、値))。
   2. すべての非リーフノードについて、左のサブツリーと右のサブツリーにそれぞれ異なる数のレジスタlとr が必要な場合は max( l ,  r ) を割り当て、それ以外の場合はr  + 1 を割り当てます。
2. コードを生成するには、サブツリーで必要なレジスタの数が異なる場合は、最も多くのレジスタを必要とするサブツリーを最初に評価します (1 つのサブツリーの結果を保存するために必要なレジスタによって、他のサブツリーの結果が保存されてしまう可能性があるため)。それ以外の場合、順序は関係ありません。

算術式の場合、抽象構文木は次のようになります。 ${\displaystyle a=(b+c+f*g)*(d+3)}$

               =
              / \
             * は
                / \
               / \
              + +
             / \ / \
            / \ d 3
           + *
          / \ / \
         bcfg

アルゴリズムを続行するには、算術式を調べるだけで済みます。つまり、代入 '=' の右側のサブツリーだけを確認する必要があります。 ${\displaystyle (b+c+f*g)*(d+3)}$

               *
              / \
             / \
            + +
           / \ / \
          / \ d 3
         + *
        / \ / \
       bcfg

ここで、ツリーのトラバースを開始し (今のところは事前順序で)、各サブツリーを評価するために必要なレジスタの数を割り当てます (式の最後の加数は定数であることに注意してください)。 ${\displaystyle (b+c+f*g)*(d+3)}$

               * 2
              / \
             / \
            + 2     + 1
           / \ / \
          / \ d 1   3 0 
         + 1    * 1
        / \ / \
       b 1   c 0 f 1   g 0

このツリーから、'*' の左のサブツリーを計算するには 2 つのレジスタが必要ですが、右のサブツリーを計算するには 1 つのレジスタのみが必要であることがわかります。ノード 'c' と 'g' には、次の理由でレジスタが必要ありません。T がツリー リーフの場合、T を評価するレジスタの数は、T が左のサブツリーか右のサブツリーかに応じて 1 または 0 になります (add R1, A などの操作では、右のコンポーネント A をレジスタに格納せずに直接処理できるため)。したがって、最初に左のサブツリーのコードを出力し始めます。これは、式全体を計算するために 2 つのレジスタしか残っていないという状況に遭遇する可能性があるためです。ここで、最初に右のサブツリーを計算すると (必要なレジスタは 1 つだけ)、左のサブツリーを計算する間 (それでも 2 つのレジスタが必要)、右のサブツリーの結果を保持するレジスタが必要になるため、同時に 3 つのレジスタが必要になります。最初に左のサブツリーを計算するには 2 つのレジスタが必要ですが、結果は 1 つのレジスタに格納でき、右のサブツリーの計算には 1 つのレジスタのみが必要なので、式の評価は残りの 2 つのレジスタのみで実行できます。

Sethi-Ullman アルゴリズムの高度なバージョンでは、使用される演算子の代数的特性を利用して、算術式が最初に変換されます。

• ストララー数、外部ストレージなしで式を評価するために必要な最小のレジスタ数
• エルショフ数、基本的にはシュトララー数と同じ概念である。

• セティ、ラヴィ;ウルマン、ジェフリー D. (1970)、「算術式のための最適コードの生成」、計算機協会誌、17 (4): 715–728、doi :10.1145/321607.321620、hdl : 10338.dmlcz/101207。

• ツリーのコード生成