Fil-C on Nix

Filnix wiki

mbrock/filnix/nanofil

lower_roots.pl

Shared lowers: a derived pointer's lowers[] entry is its lower root's (docs/lowers.md). Opt-in as --lowers=shared; the default, own, gives every pointer temporary an entry of its own.

A capability's lower never changes, and a flight with lowerP has P's lower, whatever its address. So a flight needs no entry of its own when the entry of the pointer it derives from still holds that lower wherever the flight is live; nor does a phi whose inputs all have one lower root. This module chooses those pointers (the producer); frame_slots.pl keeps each root's entry for as long as any of its derived pointers is live; filc_amd64.pl emits no lower load or store for a flight whose donor's entry is its own, nor for a phi whose inputs' entries are all its own; and lowers_check.pl validates the resulting frame, so none of these is trusted for the GC-root contract.

The rule

TermMeans
D-R in Derivedthe pointer tmpD shares the entry of its lower root tmpR

It is FilPizlonator's computeLowerRoots (staging 18b6663, FilPizlonator.cpp:2914-3004) for nanofil's two derivations. Every pointer starts as its own root; then, until nothing changes, in reachable blocks and for names with one definition:

  • a flight flighttmpD, Op, Args, lowertmpP has P's root;
  • a phi of class p has the root C of its inputs when all of them are temporaries with one definition, every input other than the phi itself has root C, and C is a parameter or is defined in another block that dominates the phi's. Without that, C could be defined in the phi's own loop, after it, and be written again while the phi still holds C's previous lower.

Definitions are counted on the liveness view (fused accesses bare, uses/2 unwrapped), so a fused pointer load cannot hide a second definition (docs/perf.md item 17's review). Functions with setjmp are left alone: longjmp restores lowers[] (docs/setjmp.md). If the roots have not settled after 32 rounds, nothing is shared.

modulelower_roots
useslists
usesassoc
usespairs
usesordsets
usesirtemp_defs/3
usescfgfunc_cfg/2, cfg_idoms/2, dom_intervals/3, dominates_by_interval/3, inst_def/2
lowers_mode-Modedet

Mode is NANOFIL_LOWERS (main.pl's --lowers=): own, the default, or shared.

55lowers_modeMode ←
getenv'NANOFIL_LOWERS', Mode0
memberchkMode0, own, shared
→
Mode = Mode0
else
Mode = own
derived_lowers+Params, +LiveBlocks, -Deriveddet

Derived maps each pointer D that shares its root's lowers[] entry to that root R (the rule above). Empty for a function with setjmp.

65derived_lowersParams, Blocks, Derived ←
empty_assocNone
memberblock_, _, Is, _, Blocks
memberI, Is
bareI, let_, w, setjmp_, _
→
Derived = None
else
maplistbare_block, Blocks, Bare
temp_defsParams, Bare, Defs
pairs_keysDefs, Names
msortNames, Sorted
once_namesSorted, Once0
list_to_assocOnce0, Once
func_cfgBare, Cfg
Cfg = cfg_, Rpo, _, _
cfg_idomsCfg, Idom
dom_intervalsCfg, Idom, Dom
findallN−param, memberparam_, tmpN, Params, PBs
findallN−L,
memberblockL, Phis, Is, _, Bare
memberphitmpN, _, _, Phis
or
memberI, Is
,
Bs0
appendPBs, Bs0, Bs1
findallN−B,
memberN−B, Bs1
get_assocN, Once, _
,
Bs2
list_to_assocBs2, DefBlock
findallL−B,
memberB, Bare
B = blockL, _, _, _
,
LBs
list_to_assocLBs, ByLabel
findallC,
memberL, Rpo
get_assocL, ByLabel, block_, Phis, Is, _
candidateOnce, L, Phis, Is, C
,
Cands
settleCands, DefBlock, Dom, None, 0, Parents
→
findallD−R,
memberC, Cands
rootParents, D, R
R ≢ D
¬get_assocR, Parents, _
,
Pairs
list_to_assocPairs, Derived
else
Derived = None
candidate+Once, +L, +Phis, +Insts, -Cand

a single-definition flight with a single-definition donor, or a single-definition pointer phi of block L whose inputs are all single-definition temporaries.

100candidateOnce, _, _, Is, flightD, P ←
memberflighttmpD, _, _, lowertmpP, Is
get_assocD, Once, _
get_assocP, Once, _
103candidateOnce, L, Phis, _, phiD, L, Vs ←
memberphitmpD, p, Pairs, Phis
get_assocD, Once, _
findallV, member_−V, Pairs, Vs0
forallmemberV, Vs0,
V = tmpN
get_assocN, Once, _
findallN, membertmpN, Vs0, Vs1
sortVs1, Vs
110cand_nameflightD, _, D
111cand_namephiD, _, _, D
settle+Cands, +DefBlock, +Dom, +Parents0, +Round, -Parents

the fixpoint of one pass over the candidates, each pointing at the root its rule gives; fails after 32 rounds.

116settleCands, DefBlock, Dom, Parents0, Round, Parents ←
Round < 32
foldlcand_rootDefBlock, Dom, Cands, Parents0, Parents1
Parents1 ≡ Parents0
→
Parents = Parents1
else
Round1 is Round + 1
settleCands, DefBlock, Dom, Parents1, Round1, Parents
125cand_root_, _, flightD, P, Ps0, Ps ←
rootPs0, P, R
set_parentD, R, Ps0, Ps
128cand_rootDefBlock, Dom, phiD, L, Vs, Ps0, Ps ←
findallR,
memberV, Vs
rootPs0, V, R
R ≢ D
,
Rs0
sortRs0, Rs
Rs = C
get_assocC, DefBlock, CB
CB ≡ param
→
true
else
CB ≢ L
→
set_parentD, C, Ps0, Ps
else
set_parentD, D, Ps0, Ps
136set_parentD, D, Ps0, Ps ←
!
get_assocD, Ps0, _
→
del_assocD, Ps0, _, Ps
else
Ps = Ps0
138set_parentD, R, Ps0, Ps ←
put_assocD, Ps0, R, Ps
root+Parents, +N, -R

N's root, following parents (at most 64).

141rootPs, N, R ←
rootPs, N, R, 0
142rootPs, N, R, Depth ←
Depth < 64
get_assocN, Ps, P
→
Depth1 is Depth + 1
rootPs, P, R, Depth1
else
R = N
148inst_tempI, N ←
150once_names[], []
151once_namesN, M|Ns, Once ←
N ≡ M
!
dropN, Ns, Rest
once_namesRest, Once
152once_namesN|Ns, N−x|Once ←
once_namesNs, Once
154dropN, M|Ns, Rest ←
N ≡ M
!
dropN, Ns, Rest
155drop_, Ns, Ns
157bare_blockblockL, Phis, Is0, J, blockL, Phis, Is, J ←
maplistbare, Is0, Is
159bareusesI0, _, I ←
!
bareI0, I
160bareI, I