Fil-C on Nix

Filnix wiki

mbrock/filnix/nanofil

check_share.pl

Shared check parts: a heap check of an object an earlier check already tested skips the null test, and right after a check of the same object reuses the upper it loaded (docs/perf.md item 17).

A check test lower; jz; cmp lower, ptr; jb; mov -16(lower), up; sub $Size, up; cmp up, ptr; ja (split bounds, local selection) has two parts that depend only on the object: the null test of its lower and the load of its upper. A capability's lower never changes, so once a check of one lower has passed, the null test of any later check of that lower is dead. Its upper does change, when the object is freed (free sets upper = lower), so a loaded upper is reused only while nothing could have freed the object, and only while the register still holds it. Every check stays where it was, with the same tests otherwise, failure label, pointer and lower.

Facts

FactHolds here when
testedRa full check of a pointer whose lower is R's passed at a point that dominates here
upperRthe last instruction that touched the object state is a full check of R's lower, and everything since is transparent
defReg, Size (machine)Reg = upper − Size as that check computed it, and no line since wrote Reg or could have freed

R is a lower root: a single-definition temporary (parameter, phi or instruction) reached from the checked pointer through single-definition flights' lower donors (ir.pl's lower_chain/3). Every name on the way has one definition, so at any point they all dominate, the pointer's lower is R's current one (docs/m7.md, round 4's dominance argument). A pointer with no such root has no fact.

Transfer, merge and invalidators

  • A full check of class R skips its null test under testedR, then adds testedR, and sets upperR if its access is transparent, otherwise no upper.
  • A transparent instruction keeps both facts; any other instruction clears upper. tested has no invalidator: it is a fact about a value. Functions with setjmp are left alone.
  • A block starts with the tested facts at the end of its immediate dominator (--share=null and upper; block starts empty), and no upper.
  • Transparent (share_transparent/1): arithmetic, comparisons, conversions, flights, scalar raw accesses and raw pointer loads (fused, reused or renewed). Everything else clears upper: calls, allocations, getters, pointer stores (ensure-aux may exit), cas, atomic pointer accesses, fences, va_arg, ABI actions and fixed asm.
  • At the machine level (shared_uppers/2) defReg, Size is cleared by any line that writes Reg, a label, a call, an unconditional jump, a fence, a locked instruction, and any line amd64_contract does not audit. A conditional jump keeps it on its fall-through.

An upper is reused only when both levels agree. Under upperR the check emits the placeholder upper_reuser9, Size, and every check with Size =< 16 marks upper_defReg, Size after computing it; Reg is %r9 for a check whose upper a later one reuses (flight arithmetic between two checks writes %rdx; only calls, pointer stores and cas write %r9) and %rdx, the reference's, otherwise. The machine pass turns each placeholder into the adjustment from the earlier size, or back into the load where def does not hold, and deletes the markers.

--share=none|block|null|upper (NANOFIL_SHARE) selects this; the default is none. Only the split bounds with local selection share.

useslists
usesassoc
usesdcgs
usesirop_kind/2, pointer_memory_effects/2, single_definitions/3
usescfgfunc_cfg/2, cfg_idoms/2
usesamd64_contractinstruction_effects/2
share_mode-Modedet

Mode is NANOFIL_SHARE (main.pl's --share=): none, the default; block, null tests shared within a block; null, also from dominating blocks; upper, also the loaded upper right after a check of the same object.

79share_modeMode ←
getenv'NANOFIL_SHARE', Mode0
memberchkMode0, none, block, null, upper
→
Mode = Mode0
else
Mode = none
shared_blocks+Mode, +Params−Checked, +Blocks0, -Blocksdet

Blocks are the fused Blocks0 (filc_amd64's fused_blocks/5) with each heap fusedcheckLo, Hi, Rights, Align, Access written fusedsharedNull, Upper, checkLo, Hi, Rights, Align, Access: Null is known when tested holds for its lower root, else test; Upper is reuse when upper holds and its size is at most 16, else load. Lower roots are found in Checked, the blocks before fusion: a fused access hides its destination's definition from single_definitions/3. Mode none, and a function with setjmp, change nothing.

96shared_blocksnone, _, Blocks, Blocks ←
!
97shared_blocks_, _, Blocks, Blocks ←
memberblock_, _, Is, _, Blocks
memberlet_, _, setjmp_, _, Is
!
99shared_blocksMode, Params−Checked, Blocks0, Blocks ←
single_definitionsParams, Checked, Once
empty_assocNone
Mode ≡ block
→
maplistshared_blockMode, Once, None, Blocks0, Blocks, _
else
func_cfgBlocks0, Cfg
cfg_idomsCfg, Idom
Cfg = cfg_, Rpo, _, _
findallL−B,
memberB, Blocks0
B = blockL, _, _, _
,
LBs
list_to_assocLBs, ByLabel
foldldominated_blockMode, Once, Idom, ByLabel, Rpo, None−None, Done−_
maplistwalked_blockMode, Once, Done, Blocks0, Blocks
dominated_block+Mode, +Once, +Idom, +ByLabel, +L, +Done0−Exits0, −Done−Exits

L, in reverse postorder, walked from the tested facts at the end of its immediate dominator, which comes earlier.

114dominated_blockMode, Once, Idom, ByLabel, L, Done0−Exits0, Done−Exits ←
get_assocL, Idom, D
→
get_assocD, Exits0, Tested0
else
empty_assocTested0
get_assocL, ByLabel, Block0
shared_blockMode, Once, Tested0, Block0, Block, Tested
put_assocL, Done0, Block, Done
put_assocL, Exits0, Tested, Exits

An unreachable block is walked from no facts.

122walked_blockMode, Once, Done, Block0, Block ←
Block0 = blockL, _, _, _
get_assocL, Done, Block
→
true
else
empty_assocNone
shared_blockMode, Once, None, Block0, Block, _
128shared_blockMode, Once, Tested0, blockL, Ps, Is0, J, blockL, Ps, Is, J, Tested ←
shared_instsIs0, Mode, Once, none, Tested0, Tested, Is1
reverseIs1, Rev1
foldlproducer, Rev1, []−false, Rev−_
Is = Rev

producer(+I, +Is0-Need0, -Is-Need), over a block backwards: a check whose upper a later check reuses (Need) computes it into %r9; every other loaded upper stays in %rdx, as the reference has it, so the register pass still sees %rdx die at the check.

136producerfusedsharedN, Up0, C, A, Is−Need0, fusedsharedN, Up, C, A|Is−Need ←
!
Up0 = reuse_
→
Up = Up0
Need = true
else
Need0 ≡ true
→
Up = loadr9
else
Up = loadrdx
Need = false
140producerI, Is−Need, I|Is−Need
shared_insts+Is0, +Mode, +Once, +Upper, +Tested0, -Tested, -Is

Upper is the lower root of upper(R), or none.

144shared_insts[], _, _, _, Tested, Tested, []
145shared_instsI0|Is0, Mode, Once, Upper0, Tested0, Tested, I|Is ←
I0 = fusedCheck, Access
Check = check_, Size, _, _
→
lower_rootOnce, P, R
→
get_assocR, Tested0, _
→
Null = known
else
Null = test
Mode ≡ upper
Upper0 ≡ R
Size ≤ 16
→
Up = reuser9
else
Up = loadrdx
put_assocR, Tested0, true, Tested1
→
Upper1 = R
else
Upper1 = none
else
Null = test
Up = loadrdx
Tested1 = Tested0
Upper1 = none
I = fusedsharedNull, Up, Check, Access
else
I = I0
Tested1 = Tested0
→
Upper1 = Upper0
else
Upper1 = none
shared_instsIs0, Mode, Once, Upper1, Tested1, Tested, Is
lower_root+Once, +P, -R

R is P's lower root, following single-definition flights to the first name that is not one. The depth bound stops a cycle of flights in unreachable code, as ir:lower_chain/4's does.

164lower_rootOnce, P, R ←
lower_rootOnce, P, R, 0
166lower_rootOnce, tmpX, R, Depth ←
get_assocX, Once, Def
Depth < 64
Def = flight_, _, _, lowerD
Depth1 is Depth + 1
lower_rootOnce, D, R0, Depth1
→
R = R0
else
R = X
access_pointer
174let_, _, raw_load_, _, PP
175raw_store_, _, _, PP
176let_, p, raw_load_pointer_, _, PP
177raw_store_pointer_, _, P, _P
178let_, _, raw_cas_, _, P|_P
179touchPP
share_transparent+Instsemidet

Inst, a fused instruction (filc_amd64's fused_blocks/5), cannot free or reallocate an object, reaches no safepoint, calls nothing and does not synchronize with another thread: the upper fact survives it. Stated here, apart from check_reuse's transfer function, for the emitter's own fact.

188share_transparentflight_, _, _, _
189share_transparentloc_, _
190share_transparentreusedAccess ←
191share_transparentfusedCheck, Access ←
Check ≢ check_function
193share_transparentlet_, _, Op, Args ←
op_kindOp, Kind
196transparent_accesslet_, _, raw_loadT, _, _ ←
T ≢ p
197transparent_accessraw_storeW, _, _, _ ←
W ≢ p
198transparent_accesslet_, p, raw_load_pointer_, Es, _ ←
200transparent_accesstouch_
202transparent_kindadditive, _
203transparent_kindalu, _
204transparent_kindshift, _
205transparent_kindneg, _
206transparent_kindcmp, _
207transparent_kindext, _
208transparent_kindfloat_convert, _
209transparent_kindfloat_to_int, _
210transparent_kindint_to_float, _
211transparent_kindcast, _
212transparent_kindptoi, _
213transparent_kindcopy, Args ←
¬memberchkglobal_, Args
share_bounds+Null, +Upper, +Size, +Fail//det

The split bounds check (filc_amd64's bounds_check//4, local selection) of the pointer in %rax with its lower in %rcx, jumping to Fail unless lower =< ptr =< upper − Size: the null test unless Null is known, then upper − Size into register R, loaded (Upper = load(R)) or the placeholder upper_reuseR, Size that shared_uppers/2 resolves (Upper = reuse(R)), and for Size =< 16 the marker upper_defR, Size. R is %rdx, as the reference check has it, or %r9 for a check whose upper a later one reuses: only calls, pointer stores and cas write %r9, where flight arithmetic writes %rdx. tests/share_smt.py proves the resolved lines against Fil-C's condition.

228share_boundsNull, Upper, Size, Fail ⟶
upper_regUpper, R
null_testNull, Fail
inscmp, q, regrcx, regrax, insjb, none, symFail
upper_partUpper, Size, Fail
Size ≤ 16
→
upper_defR, Size
else
[]
inscmp, q, regR, regrax, insja, none, symFail
238upper_regloadR, R
239upper_regreuseR, R
241null_testtest, Fail ⟶
instest, q, regrcx, regrcx, insjz, none, symFail
244null_testknown, _ ⟶
[]

The upper load and borrow test as filc_amd64's split shape emits them under local selection (item 6a: no borrow test for Size =< 16).

248upper_partloadR, Size, Fail ⟶
upper_loadR, Size
Size ≤ 16
→
[]
else
insjb, none, symFail
251upper_partreuseR, Size, _ ⟶
upper_reuseR, Size
253upper_loadR, Size ⟶
insmov, q, mem-16, rcx, regR, inssub, q, immSize, regR
upper_adjust+R, +Size0, +Size//det

From R = upper − Size0 to upper − Size, both at most 16. Neither borrows: a nonnull lower has its 16-byte header below it and upper >= lower (docs/perf.md item 6a).

262upper_adjust_, Size, Size ⟶
!
[]
263upper_adjustR, Size0, Size ⟶
D is Size0−Size
inslea, q, memD, R, regR
shared_uppers+Lines0, -Linesdet

Lines are a function body's Lines0 with each upper_reuseR, Size replaced by upper_adjust//3 from the upper_defR, Size0 before it, where that marker's R still holds (def, above), and otherwise by the upper load, and with the markers deleted.

273shared_uppersLines0, Lines ←
shared_uppersLines0, none, Lines
275shared_uppers[], _, []
276shared_uppersupper_defR, Size|Ls0, _, Ls ←
!
shared_uppersLs0, defR, Size, Ls
278shared_uppersupper_reuseR, Size|Ls0, Def, Ls ←
!
Def = defR0, Size0
R0 ≡ R
→
phraseupper_adjustR, Size0, Size, Ls, Ls1
else
phraseupper_loadR, Size, Ls, Ls1
shared_uppersLs0, defR, Size, Ls1
283shared_uppersL|Ls0, Def0, L|Ls ←
Def0 = defR, _
→
Def = Def0
else
Def = none
shared_uppersLs0, Def, Ls
keeps_upper+Line, +R

Line falls through or branches conditionally, writes no part of R, is not a fence or locked, and is audited.

289keeps_upperLine, R ←
Line = insOp, _, _
¬memberchkOp, jmp, mfence, 'lock cmpxchg'
instruction_effectsLine, effect_, Writes, _, _, Flow
memberchkFlow, next, branch
¬memberchkwriteR, _, Writes