1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
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.
|
