大域値番号付け
大域的値番号付け（英: Global value numbering, GVN） とは、静的単一代入中間表現に基づくコンパイラ最適化手法の一つである。
GVN は共通部分式除去 (CSE) によっても取り除くことができない冗長なコードを取り除くことができる。一方、CSE は GVN で除去できないコードを取り除くことができ、両者はいずれも現代的なコンパイラに採用されている。大域的値番号付けは、値と番号の関連付けをブロックの境界を越えて行うことができ、また関連付けのアルゴリズムを計算する方法が異なるという点で局所的値番号付けとは区別される。
大域的値番号付けは、値番号を変数や式に割り当てることで動作する。等価な変数や式には同じ値番号を割り当てる。例えば下記のコードでは、
w := 3 x := 3 y := x + 4 z := w + 4
優秀な GVN のルーチンはw 、 x と y 、z にそれぞれ
同じ値番号を割り当てる。たとえば、 の割り当てはこのブロックに関して最適な値と番号の対応関係である。この情報を用いることで、上のコードは下記のコードに安全に変換できる。
![{\displaystyle [{w}\mapsto 1,{x}\mapsto 1,{y}\mapsto 2,{z}\mapsto 2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98abaf785e047522405142cc103463672b37289a)
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 はごく初歩的なアルゴリズムでもこれを発見し、冗長性を除去することができる。
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
(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.