summaryrefslogtreecommitdiff
path: root/chapter-interprocedural-sccp
diff options
context:
space:
mode:
authorCliff Click <cliffc@acm.org>2026-10-24 09:38:56 -0700
committerCliff Click <cliffc@acm.org>2026-10-24 09:38:56 -0700
commitac525dc59de1ae195c40f8e21b09485d0e5d9330 (patch)
treed1af8c53dbcdf64526d0d5b5d49c8fdc53489af1 /chapter-interprocedural-sccp
parent2a7ed6bda01f028cf13f803d89b10908d7ea7937 (diff)
downloadSimple-ac525dc59de1ae195c40f8e21b09485d0e5d9330.tar.gz
Simple-ac525dc59de1ae195c40f8e21b09485d0e5d9330.zip
module split
Diffstat (limited to 'chapter-interprocedural-sccp')
-rw-r--r--chapter-interprocedural-sccp/README.ja.md6
-rw-r--r--chapter-interprocedural-sccp/README.md41
2 files changed, 24 insertions, 23 deletions
diff --git a/chapter-interprocedural-sccp/README.ja.md b/chapter-interprocedural-sccp/README.ja.md
index 4dec73c7..e9e57c6d 100644
--- a/chapter-interprocedural-sccp/README.ja.md
+++ b/chapter-interprocedural-sccp/README.ja.md
@@ -14,11 +14,11 @@
**Simple** では、ここでもほぼ何もせず、SCCP を手続き間で実行します。`CallNode` は `FunNode` を呼び、`ReturnNode` は `CallEndNode` に戻り、まったく通常の方法で型情報を渡します。ただし問題が1つあります。`Call` と `Fun`、および `Return` と `CallEnd` の間に辺がありません。そのような辺が [呼び出しグラフ](https://en.wikipedia.org/wiki/Call_graph) を構成します。
-通常の SCCP を拡張し、`Call` の関数ポインタ入力が変わり、新しい関数対象を得る時点を監視します。対象の数は有限なので、前の章で説明した *関数インデックス* で正確に表します。分割コンパイルでは、このコンパイル単位の外で呼ばれる無限の未知関数に対して、特別なインデックスを追加します。
+通常の SCCP を拡張し、`Call` の関数ポインタ入力が変わり、新しい関数対象を得る時点を監視します。対象の数は有限なので、前の章で説明した *関数インデックス* で表します。未知の対象には保守的な要約が必要です。後の分割コンパイルでは、オブジェクトファイルをまたいで関数の同一性も保ちます。
-`Call` で新しい *fidx* を見つけたら、`Call` と `Fun`、`Return` と `CallEnd` を *リンク* します。このリンクは、`Call` から `Fun`、そして `Call` の引数から `Fun` の `ParmNode` へ CFG 辺を追加したかのように動きます。`FunNode` は `RegionNode` を、`ParmNode` は `PhiNode` を拡張するため、同じ意味規則を使います。`Fun` は呼ばれると到達可能になり、`Parm` はすべての呼び出し引数をマージ(*meet*)します。同様に `CallEnd` は、すべての `Return` の *meet* を計算して、呼ばれたすべての関数の結果をマージします。
+`Call` で新しい *fidx* を見つけたら、`Call` と `Fun`、`Return` と `CallEnd` を *リンク* します。このリンクは、`Call` から `Fun` へ制御辺を、`Call` の引数から `Fun` の `ParmNode` へデータ辺を追加したかのように動きます。`FunNode` は `RegionNode` を、`ParmNode` は `PhiNode` を拡張するため、同じ意味規則を使います。`Fun` は呼ばれると到達可能になり、`Parm` はすべての呼び出し引数をマージ(*meet*)します。同様に `CallEnd` は、すべての `Return` の *meet* を計算して、呼ばれたすべての関数の結果をマージします。
-この *リンク* 段階はアルゴリズムの内部ループにいくつかの検査を加え、正確な呼び出しグラフも構築し、SCCP の手続き間実行を可能にします。進行中に新しい辺を少し発見する以外は、中核アルゴリズムは変わりません。不動点解で停止することが保証され、たとえば特定の呼び出しパラメータが、すべての呼び出し経路で定数、あるいは非 null と発見できることがあります。
+この *リンク* 段階はアルゴリズムの内部ループにいくつかの検査を加え、型伝播で発見した対象から保守的な呼び出しグラフを構築します。進行中に新しい辺を少し発見する以外は、中核アルゴリズムは変わりません。不動点解で停止することが保証され、たとえば特定の呼び出しパラメータが、すべての呼び出し経路で定数、あるいは非 null と発見できることがあります。
## 再帰もループ
diff --git a/chapter-interprocedural-sccp/README.md b/chapter-interprocedural-sccp/README.md
index 7310de80..d17f937c 100644
--- a/chapter-interprocedural-sccp/README.md
+++ b/chapter-interprocedural-sccp/README.md
@@ -3,11 +3,11 @@
English | [日本語](README.ja.md)
[Previous: SCCP Within a Function](../chapter-sccp/README.md) |
-[Next: SSA Before Types Are Known](../chapter-incomplete-types/README.md) |
+[Next: SSA Before Types Are Known](../chapter-incomplete-types/README.md)
-The previous chapter runs SCCP with each function, and assumes very
+The previous chapter runs SCCP within each function, and assumes very
conservative typing across calls. This chapter lets the same worklist
-discover call edges and propagate values between functions.
+discover call edges and propagate values between functions.
## Discovering calls while solving types
@@ -20,21 +20,21 @@ Such edges make up a [Call Graph](https://en.wikipedia.org/wiki/Call_graph).
We extend the normal SCCP algorithm to observe when a `Call`s function pointer
input changes - when it picks up new function targets. There are only a finite
number so we represent them exactly with *function indices*, or *fidx*
-internally, as described earlier chapters. (Separate compilation adds a
-special index for the infinite unknown functions that are called outside this
-compilation unit).
+internally, as described in earlier chapters. Unknown targets still require
+conservative summaries. Later, separate compilation must also preserve function
+identities across object files.
Once we observe a new *fidx* at a `Call`, we *link* the `Call` with the `Fun`,
and the `Return` with the `CallEnd`. Such linkage acts exactly as-if we added
-a CFG edge from the `Call` to the `Fun`, and the `Call`s arguments to the
-`Fun`s `ParmNodes`. `FunNodes` extend `RegionNodes` (and `ParmNodes` extend
+a CFG edge from the `Call` to the `Fun`, and data edges from the `Call`s arguments
+to the `Fun`s `ParmNodes`. `FunNodes` extend `RegionNodes` (and `ParmNodes` extend
`PhiNodes`), so this linkage uses the same semantics. `Fun`s become reachable
when called; `Parm`s merge (*meet*) all calling arguments, and so on.
Similarly, `CallEnd`s merge results from all called functions, computing the
*meet* over all the `Return`s.
This *link* step adds a few checks to our algorithm's inner loop, and also
-builds a precise Call Graph which allows our SCCP to run interprocedurally.
+builds a conservative Call Graph from the targets found by type propagation.
Other than discovering a few new edges as the algorithm proceeds, the core
algorithm is unchanged. We are guaranteed to terminate with a fixed point
solution, and may discover e.g. certain call parameters are constants (or
@@ -42,25 +42,26 @@ e.g. not-null) on all calling paths.
## Recursion is a loop in disguise
-We use the notion of *widening* integer ranges at loop heads, see Chapter XXX.
+We use *widening* of integer ranges at loop heads, as described in the
+[previous chapter](../chapter-sccp/README.md#convergence-and-calls).
This allows us to have a sharper notion of integers over `BOTTOM` without also
-allowing the lattice to fall 2^32 times. The same issue arises during
+allowing the range to grow one integer at a time. The same issue arises during
recursive calls: an argument can flow from a Parm through arithmetic into a
recursive call, then back to the same Parm.
```simple
-val fact = { int x -> x ? 0 : f(x-1)+1; };
+val f = { int x -> x == 0 ? 0 : f(x-1)+1; };
```
-Here if we pass in `f(999)` , parameter `x` will have the integer range
-`[999]`. We'll then track the recursive call to `f(998)` via normal SCCP
-and realize the parameter `x` has a range `[999-998]`. Lather, rinse, repeat
-and we're at `[999-997]`. We need to *widen* integer parameters at `Parms`
-not just loop-head `Phis`.
+If the only outside call is `f(999)`, parameter `x` starts with the range
+`[999,999]`. We'll then track the recursive call to `f(998)` via normal SCCP
+and discover that `x` has range `[998,999]`. Lather, rinse, repeat,
+and we're at `[997,999]`. We need to *widen* integer parameters at `Parms`,
+not just loop-head `Phis`.
The same issue arises during the recursive return: the first return will be
-with `0` when `x` is zero, then we return `0+1` or the range `[0-1]` then range
-`[0-2]`, etc. `CallEnds` also need to widen.
+with `0` when `x` is zero, then we return `0+1` or the range `[0,1]`, then range
+`[0,2]`, etc. `CallEnds` also need to widen.
Loop Phis, Parms, and CallEnds get widening points, and since this same issue
hits in 3 unrelated places, their comments all cross-reference each other.
@@ -72,7 +73,7 @@ A `FunPtrNode` (function address) that survives outside a direct call may be
called by code we cannot see. We have to assume the address escapes into
unknown code, which later calls it. We preserve its unknown-caller input,
since we cannot tell what that unknown caller will pass. Precise escape
-analysis is introduced later exactly to inmprove this.
+analysis is introduced later to improve this.
## Building and checking