Fil-C on Nix

Filnix wiki

mbrock/filnix/nanofil

amd64_cache_check.pl

Independent translation validation for the block-local scalar cache. There are no allocation intervals, slot assignments or eviction plans here. The two streams execute together on symbolic register and home contents; only the three eligible moves may differ, and a load may be absent when its complete result is already in its destination. All other lines match exactly, including flags, failure arguments and control flow.

Ordinary registers have one shared symbolic map: a changed load must prove equality before writing it. Homes have separate reference and actual contents, and each cache register holds a full 64-bit value. Values have independent low/high halves, so a 32-bit read zero-extends its destination without truncating the cached home. Unchanged opaque instructions give their written families fresh, shared symbols.

Before every boundary all homes must agree. Afterward we forget the cache and start with arbitrary common homes/registers. This proves each straight-line region for every possible entry state, including entries from other branches; it does not follow textual fallthrough through a label. Unmentioned/noneligible homes cannot differ because every instruction touching them is unchanged and a boundary. The home map is sparse: untouched homes have a common epoch-tagged default. Boundaries scan only homes written in that region, not the frame.

moduleamd64_cache_check
usesamd64_contractinstruction_effects/2, register/3, explicit_registers/2
usesassoc
useslists
check_cache+Metadata, +Before, +Aftersemidet

Metadata is cache_metadata(Setjmp, [home(Offset, Classes), ...]). Every alias's class must be present; unknown is an ineligible class. Placement and complete alias classes are trusted emitter metadata. Unsupported original code and any setjmp permit identity only. Once preflight succeeds, a bad candidate fails, never falls back to identity. Validate a whole function: caching starts only after movq rsp,rbp.

38check_cacheMetadata, Before, After ←
groundMetadata−Before−After
is_listBefore
is_listAfter
Metadata = cache_metadataSetjmp, Homes
memberchkSetjmp, true, false
home_offsetsHomes, Offsets
Setjmp ≡ true
→
Before ≡ After
preflightBefore, Instructions
→
maplistknown_line, After
empty_assocValues
oncepairedInstructions, After, Offsets, stateValues, [], [], 0, 1, unframed
else
Before ≡ After

Check disjoint offsets, then derive eligibility from the trusted classes. Duplicate/overlapping homes are not a physical scalar-slot description.

56home_offsetsHomes, Eligible ←
is_listHomes
maplisthome_description, Homes, All
msortAll, Sorted
findallO−true,
memberhomeO, Classes, Homes
,
Pairs
list_to_assocPairs, Eligible
66home_descriptionhomeO, Classes, O ←
integerO
O < 0
is_listClasses
69disjoint_homes[]
70disjoint_homes_
71disjoint_homesA, B|Os ←
B−A ≥ 8
75scalar_classesC|Cs ←
memberchkC, w, l
maplistscalar_class, Cs
78scalar_classw
79scalar_classl
81preflight[], []
82preflightLine|Lines, instructionLine, Effect|Instructions ←
onceinstruction_effectsLine, Effect
explicit_registersLine, Registers
¬
memberR, Registers
preflightLines, Instructions
88known_lineLine ←
90cache_familyr10
91cache_familyr11
cache_name
92r10r1064
93r11r1164
94r10dr1032
95r11dr1132

The syntax partitions extra moves from matched instructions: preflight excludes the cache bank everywhere in the original, including addresses.

99pairedBefore, Line|After, Offsets, S0 ←
extra_moveLine, Offsets, Move
fill_anchorMove, Before, After, Offsets
!
execute_extraMove, S0, S
pairedBefore, After, Offsets, S
104pairedinstructionLine, Effect|Before, Actual|After, Offsets, S0 ←
matchedLine, Actual, Effect, Offsets, S0, S
!
pairedBefore, After, Offsets, S
107pairedinstructionLine, Effect|Before, After, Offsets, S0 ←
¬boundaryLine, Effect, Offsets
eligible_moveLine, Offsets, loadO, F, Bits
S0 = stateHs, Rs, _, E, _, open
home_valueO, Hs, E, Reference, _
read_widthBits, Reference, Expected
ordinary_valueF, Rs, Value
Value ≡ Expected
pairedBefore, After, Offsets, S
117paired[], [], _, stateHomes, _, _, _, _, _ ←
120extra_moveinsmov, q, memO, rbp, regR, Os, fillO, F ←
get_assocO, Os, _
cache_nameR, F, 64
122extra_moveinsmov, q, regR, memO, rbp, Os, spillO, F ←
get_assocO, Os, _
cache_nameR, F, 64

A fill replaces the next original read, never speculates one. In particular, rbp may exist before stack growth and its overflow check.

127fill_anchorfillO, F, instructionLine, Effect|_, Actual|_, Os ←
¬boundaryLine, Effect, Os
eligible_moveLine, Os, Load
Load = loadO, _, _
replacementLoad, Line, Actual, F
131fill_anchorspill_, _, _, _, _
133execute_extrafillO, F, stateHs, Rs, Cs, E, N, open, stateHs, Rs, Next, E, N, open ←
home_valueO, Hs, E, _, Value
put_valueF, Value, Cs, Next
137execute_extraspillO, F, stateHs, Rs, Cs, E, N, open, stateNext, Rs, Cs, E, N, open ←
memberchkF−Value, Cs
home_valueO, Hs, E, Reference, _
Value ≡ Reference
put_assocO, Hs, homeReference, Value, Next
144matchedLine, Actual, Effect, Os, S0, S ←
boundaryLine, Effect, Os
→
Line ≡ Actual
S0 = stateHs, _, _, _, N, Mode0
empty_assocFresh
frame_modeLine, Effect, Mode0, Mode
N1 is N + 1
S = stateFresh, [], [], N, N1, Mode
eligible_moveLine, Os, Move
→
matched_moveMove, Line, Actual, S0, S1
else
Line ≡ Actual
Effect = effect_, Writes, _, [], next
S0 = stateHs, Rs, Cs, E, N, Mode
opaque_writesWrites, N, Rs, Next
N1 is N + 1
S = stateHs, Next, Cs, E, N1, Mode
164boundary_, effect_, _, _, _, Flow, _ ←
Flow ≢ next
!
165boundary_, effect_, Writes, _, _, _, _ ←
memberwriteF, _, Writes
memberchkF, rbp, rsp
!
167boundaryLine, effect_, _, _, Memory, _, Os ←
Memory ≢ []
¬eligible_moveLine, Os, _

The original prologue must establish the frame before any cache use. Later labels can enter another epilogue's live frame, but labels before that prologue cannot open it. No inserted access follows leave/terminal until a label; even an apparently harmless fill-and-spill is forbidden.

175frame_modeinsmov, q, regrsp, regrbp, _, _, open ←
!
176frame_mode_, _, unframed, unframed ←
!
177frame_modeinsleave, none, [], _, _, closed ←
!
178frame_mode_, effect_, _, _, _, terminal, _, closed ←
!
179frame_mode_, effect_, _, _, _, label, _, open ←
!
180frame_mode_, _, Mode, Mode
182eligible_moveinsmov, q, regR, memO, rbp, Os, storeO, F ←
get_assocO, Os, _
registerR, F, 64
184eligible_moveinsmov, q, memO, rbp, regR, Os, loadO, F, 64 ←
get_assocO, Os, _
registerR, F, 64
186eligible_moveinsmov, l, memO, rbp, regR, Os, loadO, F, 32 ←
get_assocO, Os, _
registerR, F, 32
189matched_moveMove, Line, Actual, S0, S ←
Line ≡ Actual
→
unchanged_moveMove, S0, S
else
replacementMove, Line, Actual, Cache
changed_moveMove, Cache, S0, S
196replacementstore_, _, insmov, q, Source, _, insmov, q, Source, regR, F ←
cache_nameR, F, 64
198replacementload_, _, Bits, insmov, Width, _, Dest, insmov, Width, regR, Dest, F ←
cache_nameR, F, Bits
201unchanged_movestoreO, F, stateHs, Rs, Cs, E, N, Mode, stateNext, Rs, Cs, E, N, Mode ←
ordinary_valueF, Rs, Value
put_assocO, Hs, homeValue, Value, Next
205unchanged_moveloadO, F, Bits, stateHs, Rs, Cs, E, N, Mode, stateHs, Next, Cs, E, N, Mode ←
home_valueO, Hs, E, Reference, Actual
read_widthBits, Reference, Expected
read_widthBits, Actual, Value
Value ≡ Expected
put_valueF, Value, Rs, Next
213changed_movestoreO, F, Cache, stateHs, Rs, Cs, E, N, open, stateNext, Rs, NextCache, E, N, open ←
ordinary_valueF, Rs, Value
home_valueO, Hs, E, _, Actual
put_assocO, Hs, homeValue, Actual, Next
put_valueCache, Value, Cs, NextCache
219changed_moveloadO, F, Bits, Cache, stateHs, Rs, Cs, E, N, open, stateHs, Next, Cs, E, N, open ←
home_valueO, Hs, E, Reference, _
memberchkCache−Cached, Cs
read_widthBits, Reference, Expected
read_widthBits, Cached, Value
Value ≡ Expected
put_valueF, Value, Rs, Next
228read_width64, Value, Value
229read_width32, valueLow, _, valueLow, zero
231ordinary_valueF, Values, Value ←
memberchkF−V, Values
→
Value = V
else
symbol_valueentryF, 64, Value
237opaque_writes[], _, Rs, Rs
238opaque_writeswriteF, Bits|Writes, N, Rs0, Rs ←
symbol_valuewriteN, F, Bits, Value
put_valueF, Value, Rs0, Rs1
opaque_writesWrites, N, Rs1, Rs

Partial and vector writes may conservatively forget the whole family: the original and candidate execute the same instruction on equal inputs.

245symbol_valueSymbol, 32, valuelowSymbol, zero ←
!
246symbol_valueSymbol, _, valuelowSymbol, highSymbol
248home_valueO, Homes, Epoch, Reference, Actual ←
get_assocO, Homes, homeR, A
→
Reference = R
Actual = A
else
symbol_valuehomeEpoch, O, 64, Value
Reference = Value
Actual = Value
255synchronizedHomes ←
assoc_to_listHomes, Pairs
maplistsynchronized_home, Pairs
258synchronized_home_−homeReference, Actual ←
Reference ≡ Actual
260next_symbolstateHs, Rs, Cs, E, N, Mode, stateHs, Rs, Cs, E, N1, Mode ←
N1 is N + 1
263put_valueF, Value, [], F−Value
264put_valueF, Value, F−_|Rest, F−Value|Rest ←
!
265put_valueF, Value, V|Rest, V|Next ←
put_valueF, Value, Rest, Next