大域値番号付け

大域的値番号付け（GVN）について

大域的値番号付け（Global Value Numbering, GVN）は、現代のコンパイラにおいて採用される主要な最適化技術の一つであり、静的単一代入中間表現に基づいています。GVNは主に冗長なコードを除去することを目的としており、従来の手法である共通部分式除去（CSE）と補完的に働きます。これにより、GVNはCSEが対処できない二重計算を効率的に削除することができます。

GVNとCSEの関係

GVNとCSEは、コンパイラの最適化において相互に補完する役割を果たします。具体的には、CSEが同一の式を検出して冗長な計算を削除するのに対し、GVNは背後にある等価性を見極めることで、より広範囲な冗長性を排除します。例えば、以下の式を考慮してみましょう。

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

このコードでは、GVNを適用することで、`w`と`x`、`y`と`z`に同等の値番号を割り当てることが可能です。結果として、以下のような割り当てが行われます。

```plaintext
[w ↦ 1, x ↦ 1, y ↦ 2, z ↦ 2]
```

この対応関係を元に、元のコードは以下のように変形することができます。

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

この変形により、後続のコードにおいて水準を維持しつつ、冗長なデータの保持を防ぎ、最適化が実現されます。

GVNの動作原理

GVNの根本的な動作原理は、変数や式に一意の値番号を割り当てることにあります。同じ値を持つ変数や式には共通の値番号が与えられます。これにより、特に分岐を含む複雑なプログラムにおいても、最適化の範囲を広げることができます。また、GVNは局所的なスコープを超えて、全体的なコードの冗長性を削減する特徴を持ち、性能を向上させます。

例えば、次のコードを見てみましょう。
```
a := c × d
e := c
f := e × d
```
この場合、CSEは同じ式を含むfの計算を削除できませんが、GVNを利用することで、この冗長性を簡単に特定し、除去することが可能です。

実行に必要な条件

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.

もう一度検索