エルショフ数

アンドレイ・ペトロヴィッチ・イェルショフ^[1]にちなんで名付けられたエルショフ数は、レジスタ割り当ての量を最小限に抑えるためにコード最適化で使用されます。エルショフ数は、コードブロック内に式が1つしかない場合にレジスタを最適に選択する方法で使用できます。式E = E ₁ op E ₂が与えられた場合、目標は、使用されるレジスタの数を最小限に抑えるか、十分な数のレジスタが利用できない場合は、必要な非レジスタ一時変数の数を最小限に抑えるようにコードを生成することです。

与えられた表現ツリーのノードのエルショフ数nは次のように定義される: ^{[2] [3]}

1. すべての葉にはn = 1 があります。
2. 子が 1 つあるノードの場合、n は子と同じです。
3. 2 つの子を持つノードの場合、n は次のように定義されます。

${\displaystyle n={\begin{cases}max(child_{1},child_{2})&child_{1}\neq child_{2}\\child_{1}+1&child_{1}=child_{2}\end{cases}}}$

ノードの Ershov 数は、そのノードをルートとする部分式を評価するために必要なレジスタの最小数を表します。考え方としては、まず Ershov 数が大きい子を評価し、次に他の子を評価し、最後にルートで演算を実行します。

ルートに「+」演算を持つ式ツリーがあり、左と右のサブツリーの Ershov 数がそれぞれ 3 と 4 であるとします。このノードの Ershov 数は 4 なので、4 つのレジスタを使用して式のコードを生成できるはずです。

1. レジスタ r1、r2、r3、r4 を使用して右の子を評価するコードを生成します。結果を r1 に配置します。
2. レジスタ r2、r3、r4 を使用して左の子を評価するコードを生成します。結果を r2 に配置します。
3. ADD r1, r1, r2r1 と r2 を加算し、その結果を r1 に格納する命令を発行します。

メモリからのロードとストアを最小限にしてコードを生成する一般的な手順は次のとおりです。

1. 最初に最大のエルショフ数を持つ子のコードを生成する
2. 結果を一時レジスタに格納する命令を発行する。一時レジスタがない場合は、メモリ内の一時的な場所に格納する。
3. より小さいエルショフ数を持つ子のコードを生成する
4. 一時変数をレジスタにロードする命令を発行する
5. ルートで操作を実行するための命令を発行する

理想的なケースでは、 n 個のレジスタがあり、最初の部分式にはn 個のレジスタが必要で、次の部分式にはn - 1 個のレジスタが必要な場合、1 つのレジスタを使用して最初の式の結果を保存でき、次の部分式を計算するために使用できるn - 1 個のレジスタがまだあるため、メモリからのロードやストアはまったく必要ありません。^[1]

式ツリーのルートのエルショフ数が利用可能なレジスタの数より大きい場合、エルショフ数を使用して、たとえばスタック上に必要な追加の一時メモリ領域の量を決定することもできます。^[1]

• ストララー数、外部ストレージなしで式を評価するために必要な最小のレジスタ数
• セティ・ウルマンアルゴリズム、基本的には同じ概念