summaryrefslogtreecommitdiff
path: root/chapter-sccp
diff options
context:
space:
mode:
Diffstat (limited to 'chapter-sccp')
-rw-r--r--chapter-sccp/README.ja.md12
-rw-r--r--chapter-sccp/README.md28
2 files changed, 21 insertions, 19 deletions
diff --git a/chapter-sccp/README.ja.md b/chapter-sccp/README.ja.md
index 71c78ee1..aac03cab 100644
--- a/chapter-sccp/README.ja.md
+++ b/chapter-sccp/README.ja.md
@@ -18,7 +18,7 @@
- ノードから型への対応(`Node._type`)を持っています。
- すでに伝達関数(`Node.compute`)を持っています。
-すべての `_type` を、⊥ ではなく ⊤ に初期化し、すべてのノードをワークリストに置きます。そこからノードを取り、伝達関数 `node.compute()` を実行します。結果が `node._type` と変われば更新し、その出力側の隣接ノードをワークリストへ入れます。アサーションとデバッグ補助をすべて取り除いた簡略版は次のとおりです。
+すべての `_type` を、⊥ ではなく ⊤ に初期化し、すべてのノードをワークリストに置きます。そこからノードを取り、伝達関数 `node.compute()` を実行します。結果が `node._type` と変われば更新し、その出力側の隣接ノードをワークリストへ入れます。依存関係の追跡とデバッグ用の検査の大部分を省いた簡略版は次のとおりです。
```java
while( (n = code._iter._work.pop()) != null ) {
@@ -31,7 +31,7 @@ while( (n = code._iter._work.pop()) != null ) {
}
```
-このアルゴリズムは必ず停止し、一般にはかなり速く、束と伝達関数の制限内での「最良の答え」である *不動点* に必ず到達します。得られる型はピープホール規則で見つけたものより単調に改善されます。その後、型が改善されたノードでピープホール規則を実行し、無関係なピープホール最適化が適用できるかを調べられます。たとえば新しく発見した定数が、計算を ConstantNode に置き換えます。
+単調な伝達関数と、範囲の拡大回数を制限する widening により、アルゴリズムは *不動点* で停止します。widening は範囲の精度を落とすことがあるため、束で表せる最も精密な答えとは限りません。得られる型は悲観的解析と同等以上の精度です。その後、型が改善されたノードでピープホール規則を実行できます。たとえば新しく発見した定数が、計算を ConstantNode に置き換えます。
以下は SSA の擬似コードです。`phi` はマージを意味し、Simple の構文ではありません。
@@ -46,7 +46,7 @@ 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) |
|---|----|----|-----------|-------|-----------|
@@ -72,7 +72,7 @@ while( rand ) {
return x1
```
-再び左から右へ進みますが、今度はすべての経路が到達可能とは限りません。`if` の結果は Control 値の対で、経路が生きていれば `C`、そうでなければ `X` で示します。これは `x4 = phi(x2,x3)` の計算で使います。`PhiNode` は `if` の対応する制御入力 *も* 確認し、生きた経路だけをマージします。
+次の表も処理順の一例ですが、今度はすべての経路が到達可能とは限りません。`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) |
|---|-----|----|-----------|---------|---------|---------|----------------|-----------|
@@ -85,7 +85,7 @@ return x1
この種の条件付き定数伝播は、条件が真か偽と証明できると、最適化後のプログラムから検査と分岐を除去するので、非常に役立ちます。よくあるのが null 検査です。同じプログラムで、整数の代わりに null ポインタを使います。
-```java
+```text
List head = notNullList();
while( rand ) {
if( head ) head = new List(head,payload);
@@ -95,7 +95,7 @@ while( rand ) {
`head` は非 null で始まるため、決して null にならず、`default_action` も起きません。ループは簡略化できます。
-```java
+```text
List head = notNullList();
while( rand ) {
head = new List(head,payload);
diff --git a/chapter-sccp/README.md b/chapter-sccp/README.md
index 3b7599da..eec9a361 100644
--- a/chapter-sccp/README.md
+++ b/chapter-sccp/README.md
@@ -16,8 +16,9 @@ Chapter 24. The numbered snapshot remains a comparison baseline.
## Sparse Conditional Constant Propagation
[SCCP](https://en.wikipedia.org/wiki/Sparse_conditional_constant_propagation)
-is the top-down version of the same peephole/constant-folding work we have
-been doing all along. The rules for the algorithm are well known from the
+is the optimistic version of the same peephole/constant-folding work we have
+been doing all along. Types start at the top of the lattice and fall as we
+discover reachable values. The rules for the algorithm are well known from the
literature and commonly taught at the college level;
[example slides](https://www.cse.psu.edu/~gxt29/teaching/cse522s23/slides/08monotoneFramework.pdf).
@@ -30,7 +31,7 @@ We initialize all `_type` fields to ⊤ (as opposed to ⊥), and place all Nodes
a worklist. We pull a Node from the worklist, run the transfer function
`node.compute()`, and if the result changes from `node._type` we update
`node._type` and put its output neighbors on the worklist. A simplified
-version with all asserts and debug helpers removed:
+version, omitting dependency tracking and most debug checks:
```java
while( (n = code._iter._work.pop()) != null ) {
@@ -43,10 +44,11 @@ while( (n = code._iter._work.pop()) != null ) {
}
```
-This algorithm always terminates (and generally fairly quickly) and always
-reaches a *fixed point*, as "best answer" subject to the limits of our lattice
-and transfer functions. The resulting types are monotonically better than
-those found by the peephole rules; we can then run the peephole rules on nodes
+With monotone transfer functions and bounded range widening, this algorithm
+terminates at a *fixed point*. Widening can lose range precision, so this need
+not be the sharpest answer the lattice can express. The resulting types are
+at least as precise as those found by pessimistic analysis. We can then run
+the peephole rules on nodes
with improved types, to see if unrelated peepholes can fire - such as newly
discovered constants replacing computations with ConstantNodes.
@@ -70,8 +72,8 @@ also a `1`. Folding the value does not prove the loop terminates or make
its condition and side effects removable.
-The algorithm progresses from left to right and stops when no more changes
-happen:
+The table shows one possible worklist order, from left to right. The solve
+stops when no more changes happen:
|Var|init|x0=1|x1=phi(1,T)|x2=2-x1|x1=phi(1,1)|
|---|----|----|-----------|-------|-----------|
@@ -101,7 +103,7 @@ while( rand ) {
return x1
```
-Again the algorithm progresses from left to right, although this time not all
+Again the table shows one possible order, although this time not all
paths are reachable. The `if` result is a pair of Control values, shown as
either `C` if the path is alive or `X` if not. This is used when we compute
`x4 = phi(x2,x3)`; the `PhiNode` ALSO checks the corresponding control input
@@ -120,9 +122,9 @@ from the `if` and only merges alive paths.
This kind of conditional constant propagation really helps if a condition can
be proven true or false, as this removes a test and branch from the optimized
program. A common way this happens is with null tests; here is the same
-program above, but using null pointers instead of integers:
+idea as above, but using null pointers instead of integers (in pseudocode):
-```java
+```text
List head = notNullList();
while( rand ) {
if( head ) head = new List(head,payload);
@@ -134,7 +136,7 @@ Here since `head` starts not-null, it can never be null and the
`default_action` can never happen, and the loop can
simplify:
-```java
+```text
List head = notNullList();
while( rand ) {
head = new List(head,payload);