大域値番号付けとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 大域値番号付けの意味・解説 

大域値番号付け

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2015/10/07 06:11 UTC 版)

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

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

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

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

優秀な GVN のルーチンはwxyz にそれぞれ 同じ値番号を割り当てる。たとえば、 の割り当てはこのブロックに関して最適な値と番号の対応関係である。この情報を用いることで、上のコードは下記のコードに安全に変換できる。

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.



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「大域値番号付け」の関連用語

大域値番号付けのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



大域値番号付けのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの大域値番号付け (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS