1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
# 関数内の SCCP
[English](README.md) | 日本語
[前: メソッドと型](../chapter23/README.ja.md) |
[次: 関数間の SCCP](../chapter-interprocedural-sccp/README.ja.md)
章の分割中は番号の代わりに名前を使います。この章は第24章から分けた、
単独で実行できるコンパイラです。番号付きの章は比較用に残しています。
最新の説明と検証方法は [英語版](README.md) を参照してください。
## 疎な条件付き定数伝播
[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation) は、これまで行ってきたピープホール最適化／定数畳み込みの、上から下へ進む版です。アルゴリズムの規則は文献でよく知られ、大学で一般に教えられています。[スライドの例](https://www.cse.psu.edu/~gxt29/teaching/cse522s23/slides/08monotoneFramework.pdf) があります。
- すでに束を持っています。
- すでに SSA 形式を持っています。したがってアルゴリズムは *疎* です。
- ノードから型への対応（`Node._type`）を持っています。
- すでに伝達関数（`Node.compute`）を持っています。
すべての `_type` を、⊥ ではなく ⊤ に初期化し、すべてのノードをワークリストに置きます。そこからノードを取り、伝達関数 `node.compute()` を実行します。結果が `node._type` と変われば更新し、その出力側の隣接ノードをワークリストへ入れます。アサーションとデバッグ補助をすべて取り除いた簡略版は次のとおりです。
```java
while( (n = code._iter._work.pop()) != null ) {
Type nval = n.compute();
if( n._type != nval ) {
assert n._type.isa(nval); // Types start high and always fall
n._type = nval; // Update type in Node
code._iter.addAll(n._outputs);// Neighbors might change, need to inspect
}
}
```
このアルゴリズムは必ず停止し、一般にはかなり速く、束と伝達関数の制限内での「最良の答え」である *不動点* に必ず到達します。得られる型はピープホール規則で見つけたものより単調に改善されます。その後、型が改善されたノードでピープホール規則を実行し、無関係なピープホール最適化が適用できるかを調べられます。たとえば新しく発見した定数が、計算を ConstantNode に置き換えます。
以下は SSA の擬似コードです。`phi` はマージを意味し、Simple の構文ではありません。
```text
int x0 = 1; // x0 = 1
while( rand ) {
x1 = phi(x0,x2); // x1 = BOT = phi(1,BOT)
x2 = 2 - x1; // x2 = BOT = 2 - BOT
}
return x1
```
SCCP がなければ、この小さなプログラムは `x` の計算を畳み込めません。見れば `x` は常に `1` とわかりますが、下から上へ進む悲観的手法は、x1 が BOT なので x2 が BOT、したがって x1 が BOT と判断します。行き詰まりを解くには楽観的手法が必要です。x1 が `1` と *仮定* すれば、x2 も `1` と発見できます。値の畳み込みは、ループ停止を証明したり、その条件と副作用を除去可能にしたりするものではありません。
アルゴリズムは左から右へ進み、変化がなくなったら停止します。
| 変数 | 初期 | x0=1 | x1=phi(1,T) | x2=2-x1 | x1=phi(1,1) |
|---|----|----|-----------|-------|-----------|
| x0 | T | 1 | 1 | 1 | 1 |
| x1 | T | T | 1 | 1 | 1 |
| x2 | T | T | T | 1 | 1 |
### 条件付き
制御フローがデータフローと同じグラフ内にあるため（これが Sea-of-Nodes の大きな要点です）、特別なことをする必要はなく、アルゴリズムはすでに *条件付き* です。ここでも例が役に立ちます。
再び SSA の擬似コードを使います。
```text
int x0 = 1; // x0 = 1
while( rand ) {
x1 = phi(x0,x4); // x1 = BOT = phi(1,BOT)
if( x1 == 1 ) // Since x1 is BOT, both true and false arms are taken
x2 = 2 - x1; // x2 = BOT = 2 - BOT
else x3 = 99; // x3 = 99
x4 = phi(x2,x3); // x4 = BOT = phi(BOT,99)
}
return x1
```
再び左から右へ進みますが、今度はすべての経路が到達可能とは限りません。`if` の結果は Control 値の対で、経路が生きていれば `C`、そうでなければ `X` で示します。これは `x4 = phi(x2,x3)` の計算で使います。`PhiNode` は `if` の対応する制御入力 *も* 確認し、生きた経路だけをマージします。
| 変数 | 初期 | x0=1 | x1=phi(1,T) | 1 == 1? | x2=2-x1 | x3=99 | x4=phi(C/1,X/99) | x1=phi(1,1) |
|---|-----|----|-----------|---------|---------|---------|----------------|-----------|
| x0 | T | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
| x1 | T | T | 1 | 1 | 1 | 1 | 1 | 1 |
| if | T | T | T | [C,X] | [C,X] | [C,X] | [C,X] | [C,X] |
| x2 | T | T | T | T | 1 | 1 | 1 | 1 |
| x3 | T | T | T | T | T | 99 | 99 | 99 |
| x4 | T | T | T | T | T | T | 1 | 1 |
この種の条件付き定数伝播は、条件が真か偽と証明できると、最適化後のプログラムから検査と分岐を除去するので、非常に役立ちます。よくあるのが null 検査です。同じプログラムで、整数の代わりに null ポインタを使います。
```java
List head = notNullList();
while( rand ) {
if( head ) head = new List(head,payload);
else { head = null; default_action(); }
}
```
`head` は非 null で始まるため、決して null にならず、`default_action` も起きません。ループは簡略化できます。
```java
List head = notNullList();
while( rand ) {
head = new List(head,payload);
}
```
## 呼び出しとの境界
この章の SCCP は各関数を独立に解析します。未知の呼び出し元を表す Start
入力を残し、呼び出し辺を外します。呼び出しの戻り値には、悲観的解析で得た
型を保持します。これは宣言された戻り値型より精密な場合があります。
呼び出しによるメモリへの影響は保守的に扱います。
ループの整数範囲は Phi で拡大し、解析を収束させます。再帰呼び出しを通る
引数と戻り値の推論・拡大は次の章で導入します。
このディレクトリで最初に `make lib`、続いて `make tests` を実行してください。
リポジトリのルートでは `make tests CHAPTERS=chapter-sccp` を使えます。
|
