launder.pl
Pointer-as-integer laundering: an integer converted back to a pointer (itop) keeps the capability of the one pointer it was computed from, by launder_module/2. Fil-C's FilPizlonator does this with inferPointerAsIntLaunderingForFunction; this pass states the same abstract interpretation on nanofil's IR, before any optimization, so that the result does not depend on -O.
The analysis
Every w or l value has one of three abstract values:
| Value | Means |
|---|---|
bot | no capability source: a constant, a parameter, a load from memory, a call, a comparison |
defId | computed from the one capability Id |
top | computed from two different capabilities |
| Definition | Abstract value |
|---|---|
letD, l, ptoi, P | defP; bot when P is a constant plus offsets (&struct s *0→f), whose conversion clang folds |
letD, K, Op, Args, Op arithmetic, bitwise, a shift, copy, ext_ or cast | the merge of Args' values: bot is neutral, equal defs stay, anything else is top |
phiD, K, Ins | defphiD when some incoming value is not bot, else bot |
| anything else | bot |
Fil-C runs its analysis on LLVM's SSA after clang's optimizer, so what it finds depends on the optimization level: at -O0 an integer stored in a local variable comes back from a load, which is bot. This pass evaluates the rules on the SSA form that promote.pl gives the function (promote_func/3, whatever the level): a load of a promotable local is the value last stored to it, a phi where stores merge. Ids are SSA values too, so a pointer variable read twice is one source; so is a member or element read twice, its address computed twice from the same values, with no write between the reads in one block (block_loads/3, an optimizer's value numbering). The rules are Fil-C's; only the program they read is fixed. Clang's idiom recognition, which turns some selects into llvm.umin calls (bot to Fil-C), plays no part.
A local the frontend declares volatile is memory, as it is to Fil-C: its reads are bot (volatile_allocs/2).
A capability chosen this way is always one the program held: the rewrite never creates authority, and every access through the result is checked against that capability's bounds as any other.
The rewrite
The function is rewritten as it came from the frontend, and each capability the analysis names is computed where it is needed:
| Instruction | Becomes |
|---|---|
letD, p, itop, X, X def | I = ptoi C, Off = X - I, D = C + Off, C the capability of X |
the same, X bot or top | unchanged: no capability |
an alloc with integer slots that ever hold a non-bot value | also a pointer slot, the slot's shadow, per such slot |
| a store to such a slot | also a store of the value's capability (or null) to the shadow |
a def load of such a slot | also a load of the shadow |
a def phi whose capability is needed | also a p phi of its incoming values' capabilities (null for bot and top) |
The shadow holds what Fil-C's capability phi would select: the capability of the value last stored, null for a top or bot one. Under -O, promote turns each shadow into exactly that phi. Functions without itop, and functions that are not in strict SSA form, are unchanged.
Items are the module items Items0 (functions, their context/2 items and data) with each function laundered by launder_func/4.
F is the function F0 with each itop of an integer computed from one capability given that capability (this module's header), and Records is its context Records0 with instruction sites moved accordingly.
The analysis
An is an(Copies, States, Defs, Addrs, Shadows): FP's copies T-V, the abstract values of FP's temps (bot left out), F0's definitions T-Inst, F0's address temps X-(A-Off) and the shadow temp of each tracked slot A-Off.
Allocs is the ordset of the alloc temps of locals the frontend's context declares volatile. promote.pl makes such a local a value, but its reads are memory reads to Fil-C, so they are bot and the local has no shadow. The IR does not mark volatility; context only ever takes a capability away here.
Copies is Copies0 with each pure computation of Block that repeats an earlier one on the same values, and each pointer load that repeats an earlier one from the same address with no write between them, a copy of the earlier: one value, as an optimizer's value numbering makes it (s->p read twice computes its address twice).
FP's Inst defines an integer by one of the header's rules.
the pointer P is a constant plus offsets, as a hand-written offsetof, &struct s *0→f, is: clang folds its conversion to an integer, so it is no capability source. Copies holds each p add or sub as base(T)-Base.
T is Prefix.N, the first such name after N0 that is not in Used, the function's own names. Shadows are ld.N and capabilities lc.N, each from its own counter, so a fresh name never needs adding to Used.
Which capabilities are needed
St is st(N, Used, Reals, Loads, Phis, Itops) once every capability needed by an itop or a store to a tracked slot has a value: Reals maps a temp to its capability operand, Loads a load to its shadow load's temp, Phis a phi to C-Ins, its capability phi, Itops an itop to the two temps of its offset.