Loading article…
値の番号付けは、プログラム内の2 つの計算が同等であるかどうかを判定し、意味を保持する最適化によってそのうちの 1 つを削除する手法です。
グローバル値の番号付け
グローバル値番号付け (GVN) は、静的単一代入形式(SSA) 中間表現に基づくコンパイラ最適化です。共通部分式除去(CSE)では除去できない冗長コードを除去するのに役立つ場合があります。ただし同時に、CSE では GVN では除去できないコードが除去される可能性があるため、最新のコンパイラでは両方が使用されていることがよくあります。グローバル値番号付けは、値と番号のマッピングが基本ブロック境界を越えて保持され、マッピングの計算に異なるアルゴリズムが使用されるという点で、ローカル値番号付けとは異なります。
グローバル値の番号付けは、変数と式に値番号を割り当てることによって機能します。おそらく同等である変数と式には、同じ値番号が割り当てられます。たとえば、次のコードでは次のようになります。
w := 3 x := 3 y := x + 4 z := w + 4
w適切な GVN ルーチンは、とに同じ値番号を割り当て、とxに同じ値番号を割り当てます。たとえば、マップはこのブロックの最適な値と番号のマッピングを構成します。この情報を使用すると、前のコード フラグメントを次のように安全に変換できます。
yz
w := 3 x := w y := w + 4 z := y
このフラグメントに続くコードによっては、コピー伝播xによっておよび への割り当てを削除できる場合がありますz。
GVN が CSE よりも強力な場合がある理由は、CSE が語彙的に同一の表現に一致するのに対し、GVN は基礎となる同等性を判断しようとするからです。たとえば、次のコードでは:
a := c × d e := c f := e × d
コピー伝播がなければ、CSE はに割り当てられた再計算を排除しませんfが、貧弱な GVN アルゴリズムでもこの冗長性を検出して排除するはずです。
再バインド (同じ変数に複数回割り当てる) が可能な IR およびソース言語では、誤ったマッピングが作成されないように GVN を実行するために SSA 形式が必要です。
ローカル値の番号付け
ローカル値番号付け (LVN) は、同等の式 (つまり、同じ結果をもたらす式) の複数のインスタンスを検索し、最初の出現に置き換えることを目的としたコンパイラ最適化です。LVN はローカル最適化であり、グローバル値番号付けとは異なり、一度に 1 つの基本ブロックに対して動作します。
ローカル値の番号付けは、各操作に一意の番号を割り当て、これらの関連付けを記憶することによって機能します。その後、後続の命令が検索され、同一の命令がすでに登録されている場合は、前の命令の結果に置き換えられます。例:
a ← 4 a は #1 としてタグ付けされています b ← 5 bは#2としてタグ付けされています c ← a + bc (#1 + #2) は #3 としてタグ付けされます d ← 5 dは#2としてタグ付けされており、bと同じです e ← a + de、「#1 + #2」なので#3としてタグ付けされます
命令に番号を割り当てることで、重複の比較が単純な整数比較になります。この特定の例では、cと に同じ番号 (#3) が割り当てられているため、 への参照はへの参照に単純に置き換えられることeがコンパイラに通知されます。
ec
困難と拡張
SSAを使用しない場合の問題
単純な実装では、数値ではなく変数名を直接使用して最適化を実行しようとする場合があります。ただし、このアプローチは変数の値が変化する可能性がある場合には機能しません。次の疑似コードを検討してください。
a ← 1 a は #1 としてタグ付けされています b ← 2 bは#2としてタグ付けされています c ← a + bc は #3 としてタグ付けされています ば←3 d ← a + bd は誤って #3 としてタグ付けされています
このシナリオでは、d引数が の引数と一致するため、 には誤って数値 3 が割り当てられますc。ただし、 の値が 2 から 3 に変更されたため、実際の結果が異なり、これは誤りですb。SSA 表現を使用すると、この不一致は解決されます。
数学的恒等式の使用
単純な実装では、オペランドの順序のみが異なる場合でも、すべての同等の式をキャッチできない可能性があります。次の例では、aと にb同じ番号が割り当てられます。
ア ← 1 + 2 2 ← 2 + 1
この問題は、両方のケースに同じ番号を割り当てる（つまり、a + bとをb + a両方とも同じ番号で記録する）か、同等のものをチェックする前にオペランドをソートすることで簡単に解決できます。[1]
局所的な値番号付けの最適化では数学的な恒等式も考慮される。が整数aであると仮定すると、次の式にはすべて同じ値を割り当てることができる。[2]
b ← a + 0
c ← a * 1
d ← min(a, MAX_INT)
e ← 最大値(a, a)
f ← a & 0xFF..FF ('&' はビットごとの AND を表すと仮定)
参照
参考文献
- ^ Cooper, Keith D.; Torczon, Linda. 「用語、原則、および懸念事項（ローカル値の番号付けの例付き）」。elsevier 。 2017年5月15日閲覧。
- ^ Cooper, Keith D.; Torczon, Linda. 「局所最適化: 値の番号付け」(PDF)。ライス大学。2017年5 月 15 日閲覧。
さらに読む
- Kildall, Gary Arlen (1973)。「グローバル プログラム最適化への統一アプローチ」。プログラミング言語の原理に関する第 1 回 ACM SIGACT-SIGPLAN シンポジウム議事録 - POPL '73 。pp . 194–206。doi :10.1145/512927.512945。hdl :10945/ 42162。ISBN 9781450373494. S2CID 10219496 . 2006年11月20日閲覧。[1]
- Alpern、Bowen、Wegman、Mark N.、および Zadeck、F. Kenneth。「プログラム内の変数の等価性の検出」、プログラミング言語の原理に関する第 15 回 ACM シンポジウム( POPL ) の会議記録、ACM Press、サンディエゴ、カリフォルニア州、米国、1988 年 1 月、1 ～ 11 ページ。
- L. Taylor Simpson、「価値主導の冗長性除去」。技術レポート 96-308、ライス大学コンピュータサイエンス学部、1996 年。(著者の博士論文)
- Muchnick, Steven Stanley (1997)。Advanced Compiler Design and Implementation。Morgan Kaufmann Publishers。ISBN 978-1-55860-320-2。
- Briggs, P.; Cooper, Keith D .; Simpson, L. Taylor (1997). 「値の番号付け」.ソフトウェア実践と経験. 27 (6): 701–724.