大域値番号付けのソースを表示

'''大域的値番号付け'''（[[英語|英]]: '''Global value numbering, GVN'''）
とは、[[静的単一代入]]中間表現に基づく[[コンパイラ最適化]]手法の一つである。

GVN は[[共通部分式除去]] (CSE) によっても取り除くことができない冗長なコードを取り除くことができる。一方、CSE は GVN で除去できないコードを取り除くことができ、両者はいずれも現代的なコンパイラに採用されている。大域的値番号付けは、値と番号の関連付けをブロックの境界を越えて行うことができ、また関連付けのアルゴリズムを計算する方法が異なるという点で[[局所的値番号付け]]とは区別される。

大域的値番号付けは、値番号を変数や式に割り当てることで動作する。等価な変数や式には同じ値番号を割り当てる。例えば下記のコードでは、

 w := 3
 x := 3
 y := x + 4
 z := w + 4

優秀な GVN のルーチンは<code>w</code> 、 <code>x</code> と <code>y</code> 、<code>z</code> にそれぞれ
同じ値番号を割り当てる。たとえば、<math>[{w} \mapsto 1, {x} \mapsto 1, {y} \mapsto 2, {z} \mapsto 2]</math> の割り当てはこのブロックに関して最適な値と番号の対応関係である。この情報を用いることで、上のコードは下記のコードに安全に変換できる。

 w := 3
 x := w
 y := w + 4
 z := y

これ以降のコードしだいで、[[:en:copy propagation|コピーの伝播]]によって <code>x</code> および <code>z</code> に対する割り当てを除去できる可能性がある。

GVN が CSE より強力なのは、CSE は字句的に同一な式をマッチさせるのに対して GVN はその背後の等価性を特定しようとする点である。例えば、

 a := c × d
 e := c
 f := e × d 

というコードで、CSE は <code>f</code> に割り当てられた再計算のコードを除去しないが、GVN はごく初歩的なアルゴリズムでもこれを発見し、冗長性を除去することができる。

GVN を実行するためには、変数名と値名の間に偽の対応関係が作られないよう、静的単一代入形式が必要である。


==参考文献==
* Alpern, Bowen, Wegman, Mark N., and Zadeck, F. Kenneth.  "Detecting Equality of Variables in Programs.", ''Conference Record of the Fifteenth Annual ACM Symposium on Principles of Programming Languages''
([[:en:POPL|POPL]]), ACM Press, San Diego, CA, USA, January 1988, pages 1-11.
* L. Taylor Simpson, "Value-Driven Redundancy Elimination." Technical Report 96-308, Computer Science Department, Rice University, 1996.  (Author's Ph.D. thesis)
* Muchnick, Steven S. ''Advanced Compiler Design and Implementation''.  Morgan Kaufmann.  1997.

{{デフォルトソート:たいいきてきあたいはんこうつけ}}
[[Category:コンパイラ最適化]]