Global value numberingとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > Global value numberingの意味・解説 

大域値番号付け

(Global value numbering から転送)

出典: フリー百科事典『ウィキペディア(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.

「Global value numbering」の例文・使い方・用例・文例

Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。


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

辞書ショートカット

すべての辞書の索引

「Global value numbering」の関連用語

Global value numberingのお隣キーワード
検索ランキング

   

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



Global value numberingのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの大域値番号付け (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。
Tanaka Corpusのコンテンツは、特に明示されている場合を除いて、次のライセンスに従います:
 Creative Commons Attribution (CC-BY) 2.0 France.
この対訳データはCreative Commons Attribution 3.0 Unportedでライセンスされています。
浜島書店 Catch a Wave
Copyright © 1995-2025 Hamajima Shoten, Publishers. All rights reserved.
株式会社ベネッセコーポレーション株式会社ベネッセコーポレーション
Copyright © Benesse Holdings, Inc. All rights reserved.
研究社研究社
Copyright (c) 1995-2025 Kenkyusha Co., Ltd. All rights reserved.
日本語WordNet日本語WordNet
日本語ワードネット1.1版 (C) 情報通信研究機構, 2009-2010 License All rights reserved.
WordNet 3.0 Copyright 2006 by Princeton University. All rights reserved. License
日外アソシエーツ株式会社日外アソシエーツ株式会社
Copyright (C) 1994- Nichigai Associates, Inc., All rights reserved.
「斎藤和英大辞典」斎藤秀三郎著、日外アソシエーツ辞書編集部編
EDRDGEDRDG
This page uses the JMdict dictionary files. These files are the property of the Electronic Dictionary Research and Development Group, and are used in conformance with the Group's licence.

©2025 GRAS Group, Inc.RSS