From 2a7ed6bda01f028cf13f803d89b10908d7ea7937 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Fri, 23 Oct 2026 09:33:11 -0700 Subject: Split out escape analysis chapter --- chapter-escape/README.md | 177 +++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 177 insertions(+) create mode 100644 chapter-escape/README.md (limited to 'chapter-escape/README.md') diff --git a/chapter-escape/README.md b/chapter-escape/README.md new file mode 100644 index 00000000..6098c72c --- /dev/null +++ b/chapter-escape/README.md @@ -0,0 +1,177 @@ +# Escape Analysis and Unknown Callers + +English | [日本語](README.ja.md) + +[Previous: Construction and Private Memory](../chapter-construction/README.md) + + +We run a simple form of escape analysis in this chapter, tracking both +functions and some aliases across all calls and memory updates. One of the +goals here is to discover when we've found *all* the callers of a function; at +this point we can drop the conservative "unknown caller" input and run +constant propagation through a functions arguments. + +The preceding compiler kept an unknown caller for every surviving function +address. That was safe, but it lost facts even when all uses stayed within the +program. Escape analysis makes that boundary more precise. + +## A callback that stays within known code + +```simple +val run = { int n -> + val power = { int base, int exponent -> + if (exponent <= 0) return 1; + int smaller = power(base, exponent - 1); + return base * smaller; + }; + val sumPowers = { int n, {int int -> int} f -> + if (n <= 0) return 0; + return f(2,n) + sumPowers(n-1,f); + }; + return sumPowers(n,power); +}; +return run(arg); +``` + +For `arg == 3`, this computes `2 + 4 + 8 == 14`. Both functions are recursive; +their calls remain in the graph. In the prior chapters, the address passed as +`f` keeps an unknown caller for `power`, so `base` stays `i64`. + +Here the compiler follows the address through the arguments and recursive +calls. Neither function returns it, stores it where unknown code can find it, +nor passes it to an unknown callee. Every call to `power` is accounted for. +SCCP can then infer `base == 2`, including in its recursive body. The multiply +by 2 can become a shift without inlining or cloning either recursive body - and +we open ourselves up to further optimizations. + +Passing `power` to an unknown caller, or passing it to a native function, +changes the answer. The external caller may choose another base. The compiler +must retain `power` and give its parameters their declared bounds. + + +## Publishing an object and exposing it to unknown code + +The construction chapter's `EscapeNode` publishes initialized fields into +ordinary public memory. The completed object has not, yet, escaped; it +depends on what happens to the `self` pointer. + +Escape analysis starts at the boundary with unknown code. Returning an object +across that boundary exposes its field aliases. An exposed field can contain +another object or a callback, so discovery continues through memory: + +```text +external result -> Wrap.child -> Holder.f -> callback -> unknown caller +``` + +The same rule applies to arguments passed to native code. Native code may keep +an address after the call returns, or use it on a path that never returns. +`Stop` therefore also collects exposure directly from reachable native calls. +A call to a known Simple function instead passes the values and memory to that +function's graph; its uses SCCP to determine what escapes. + +This is a conservative analysis by field alias. Two instances of the same +struct share their field aliases. Exposing one may therefore expose addresses +stored in the same fields of another. It does not identify each allocation +separately. + +Another way to think of this: this analysis is what we get "for free" from just +running SCCP. We extend and sharpen the lattice a litte more, to allow more +precise tracking. + + +## Memory carries exposure sets + +`TypeMem` now carries two interned sets alongside its contents: + +* `_escFs`: function identities reachable through this memory. +* `_escAs`: field aliases reachable through this memory. + +`XInt`, already used for function sets, represents both. An empty set means no +address has been discovered; a full set is the conservative unknown case. +Meeting summaries unions the sets. Dual types complement them, so the existing +lattice operations and tests still apply. The `XInt` utilities themselves just +track collections of immutable bits. They have no indirection, they are just +fly-weight wrappers around `int[]`s. The help support shared and immutable +`int[]`s so that these bit sets follow the same invariants as the rest of the +Types. + +Stores record addresses carried by their values. Memory Phis combine those +facts over live paths. `MemMergeNode` gathers the slices whose aliases are +exposed, rather than making every locally stored callback externally callable. +If an exposed field reveals another alias, that slice participates as well. In +short, we follow escaping values through memory using `Types` using the formal +`Node.compute` and `Type` machinery. + +The hidden constructor helpers still keep fields in local SSA values and use +ordinary Phis. Their private-memory arguments and results describe the object +being built; they are not external returns. Initializing Stores and +publication preserve the address facts when those fields enter ordinary memory. + + + +## Start and Stop close the cycle + +Start represents unknown callers. Stop collects what known code can expose to +them. The two form an analysis cycle: + +```text +Start -> callable functions -> returns and exposed memory -> Stop + ^ | + +---------------- newly exposed addresses ----------------+ +``` + +Before SCCP, parsing and pessimistic iteration keep conservative callers and +memory. During SCCP, functions lose their unknown-caller edges unless their +function pointer escapes and become unknown entry points. Concrete calls then +rebuild the known call graph. + +Stop combines the results and memory visible to external callers. Those +callers already hold their object arguments, so writes through such arguments +also count. Start feeds the resulting alias set back into memory summaries. +If a function identity escapes, SCCP restores a Start edge and its conservative +parameter inputs. That function can reveal further addresses through its own +calls and returns. The ordinary worklist repeats until types, exposure sets, +and call edges agree - i.e. the normal SCCP reaches a fixed point. + +If you have a `main` function, it starts discovery. Without `main`, the code +is assumed to be a library, and all public entry points are fair game. + +Once SCCP finishes, you might have ordinary public functions callable from +anywhere, or functions called via their name (direct field load holding the +function point), or via a function pointer thats only used in a few locations, +or it might escape in a region and get mixed with other function pointers, or +you might never call a function at all. If a function is getting called, but +never publically, its arguments can sharpen across the `meet` of all call sites +- perhaps allowing not-null-ness to be tracked precisely and avoid some +explicit tests. + +After optimization, `FinalizeIR` freezes the external summary - the escaped +values from `Start/Stop`, for tracking if a function gets a public entry in the +ELF file. `FinalizerIR` does a few more cleanups, including removing the +`Stop->Start` edge SCCP uses to track escapes across external calls. + + +## Construction boundary to review + +The language still prevents a partially built object from escaping. Constructor +fields remain local values until helper exit. Exact local aliases of `self` +can access those values; passing `self` to ordinary code, storing it in an +object, or accessing fields through a merge that may choose another object +remains rejected in this snapshot. + +Discovering that a completed object stays private does not prove that an early +read of an uninitialized field is legal. These are separate checks. The runnable +construction and escape snapshots now make that border available for review. +Neither topic requires the other to be taught first. + +## Build and check + +From this directory, run `make lib tests CTAGS=`. From the repository root, run: + +```bash +make tests CHAPTERS=chapter-escape CTAGS= +``` + +`EscapeTest` checks the recursive callback, direct and indirect returned +addresses, and native exposure. The inherited construction, language, memory, +lattice, evaluator, and native/backend suites also run. -- cgit v1.2.3