diff options
| author | Cliff Click <cliffc@acm.org> | 2026-10-24 09:38:56 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-24 09:38:56 -0700 |
| commit | ac525dc59de1ae195c40f8e21b09485d0e5d9330 (patch) | |
| tree | d1af8c53dbcdf64526d0d5b5d49c8fdc53489af1 /chapter-sccp/README.ja.md | |
| parent | 2a7ed6bda01f028cf13f803d89b10908d7ea7937 (diff) | |
| download | Simple-ac525dc59de1ae195c40f8e21b09485d0e5d9330.tar.gz Simple-ac525dc59de1ae195c40f8e21b09485d0e5d9330.zip | |
module split
Diffstat (limited to 'chapter-sccp/README.ja.md')
| -rw-r--r-- | chapter-sccp/README.ja.md | 12 |
1 files changed, 6 insertions, 6 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); |
