From ac525dc59de1ae195c40f8e21b09485d0e5d9330 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 24 Oct 2026 09:38:56 -0700 Subject: module split --- chapter-interprocedural-sccp/README.md | 41 +++++++++++++++++----------------- 1 file changed, 21 insertions(+), 20 deletions(-) (limited to 'chapter-interprocedural-sccp/README.md') 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 -- cgit v1.2.3