Fil-C on Nix

Filnix wiki

mbrock/filnix/nanofil

amd64_cache.pl

Opt-in block-local caching of private integer frame homes in r10/r11. This is not instruction selection or general register allocation. All eight bytes of a home stay together, even when a read uses only its low word. Every alias must be w/l. Pointers, roots, phi shadows, local storage and ABI bookkeeping retain their original homes.

Each region starts and ends with synchronized memory. Calls, control flow, frame changes and non-rewritable memory accesses separate regions. Loads whose complete destination value is already present are removed first; a low-word load still has to zero its destination's high half. A linear scan assigns a home's entire first-to-last reference interval; every intervening store replaces its cached version. There is no eviction: intervals under pressure keep their stack representation. The fixed register order and interval order make output deterministic.

Unknown original forms or explicit uses of the cache bank keep the whole implementation unchanged. A translation-check failure is an error, never a reason to silently hide an allocator bug.

moduleamd64_cache
useslists
usesassoc
usespairs
usesdcgs

Report is stack, excluded(setjmp|unsupported), or cached(Homes,Regions). Regions counts regions changed by load removal or an assigned interval.

29cache_asmstack, _, Lines, Lines, stack
30cache_asmlocal, Meta, Before, After, Report ←
Meta = cache_metadataSetjmp, Homes
Setjmp ≡ true
→
After = Before
Report = excludedsetjmp
¬maplistaudited, Before
→
After = Before
Report = excludedunsupported
else
findallD−true,
memberhomeD, Ks, Homes
Ks = _|_
maplistinteger_class, Ks
,
Pairs
list_to_assocPairs, Eligible
lengthPairs, N
maplistclassifyEligible, Before, Classified
phraseregionsClassified, Eligible, Count, After
Report = cachedN, Count
check_cacheMeta, Before, After
→
true
else
thrownanofil_error'scalar stack cache translation check failed'
44integer_classw
44integer_classl
45auditedLine ←
¬
memberR, Rs
memberchkR, r10, r11
49classifyEligible, Line, Kind−Line ←
onceinstruction_effectsLine, effect_, Writes, _, Memory, Flow
Flow ≡ next
¬memberchkwriterbp, _, Writes
¬memberchkwritersp, _, Writes
Memory ≡ []
or
home_moveLine, Eligible, _, _
→
Kind = inside
else
Kind = boundary
57home_moveinsmov, q, regR, memD, rbp, Es, D, write ←
get_assocD, Es, _
registerR, _, 64
59home_moveinsmov, S, memD, rbp, regR, Es, D, read ←
get_assocD, Es, _
registerR, _, W
61move_widthq, 64
61move_widthl, 32
63regions[], _, 0 ⟶
[]
64regionsboundary−L|Ls, Es, N ⟶
L
regionsLs, Es, N
65regionsinside−L|Ls, Es, N ⟶
regionLs, More, Rest
Region = L|More
retained_loadsRegion, Es, [], Clean
region_planClean, Es, Plan
Clean ≡ Region
empty_assocPlan
→
Here = 0
else
Here = 1
cached_linesClean, Es, Plan, 0
regionsRest, Es, N1
N is N1 + Here
72regioninside−L|Ls, L|More, Rest ←
!
regionLs, More, Rest
73regionRest, [], Rest

At most one association per ordinary register: part of a current home, and whether the register's upper half is zero. A store invalidates all associations with that physical home, even if its temporary has changed. This bounded forward analysis is separate from the checker's symbols.

79retained_loads[], _, _, []
80retained_loadsL|Ls, Es, Rs, Out ←
→
Out = Rest
Next = Rs
else
Out = L|Rest
register_contentsL, Es, Rs, Next
retained_loadsLs, Es, Next, Rest
85redundant_loadinsmov, S, memD, rbp, regR, Es, Rs ←
get_assocD, Es, _
registerR, F, W
memberchkF−contenthomeD, Bits, Zero, Rs
W =:= 64
→
Bits =:= 64
else
Zero ≡ true
90register_contentsL, Es, Rs, Next ←
home_moveL, Es, D, write
→
L = insmov, q, regF, _
contentsF, Rs, content_, _, Zero
invalidate_homeRs, D, Fresh
replace_contentsF, contenthomeD, 64, Zero, Fresh, Next
home_moveL, Es, D, read
→
L = insmov, S, _, regR
registerR, F, W
W =:= 32
→
Zero = true
else
Zero = false
replace_contentsF, contenthomeD, W, Zero, Rs, Next
else
onceinstruction_effectsL, effect_, Writes, _, _, _
written_contentsWrites, Rs, Next
103contentsF, Rs, C ←
memberchkF−Value, Rs
→
C = Value
else
C = contentnone, 0, false
105replace_contentsF, C, Rs, F−C|Rest ←
selectF−_, Rs, Rest
→
true
else
Rest = Rs
107invalidate_home[], _, []
108invalidate_homeF−contentH, W, Z|Rs, D, F−C|Next ←
H ≡ homeD
→
C = contentnone, 0, Z
else
C = contentH, W, Z
invalidate_homeRs, D, Next
111written_contents[], Rs, Rs
112written_contentswriteF, W|Ws, Rs, Next ←
W =:= 32
→
Zero = true
else
Zero = false
replace_contentsF, contentnone, 0, Zero, Rs, Fresh
written_contentsWs, Fresh, Next
117region_planLines, Es, Plan ←
findallD−I−Access,
nth0I, Lines, L
home_moveL, Es, D, Access
,
Events
keysortEvents, Sorted
group_pairs_by_keySorted, Groups
findallStart−spanD, Start, End, First, Dirty,
memberD−Uses, Groups
Uses = Start−First|_
lastUses, End−_
lengthUses, Count
memberchk_−write, Uses
→
Dirty = true
Spill = 1
else
Dirty = false
Spill = 0
First ≡ read
→
Fill = 1
else
Fill = 0
Count > Fill + Spill
,
Spans
keysortSpans, Ordered
assignOrdered, r10−-1, r11−-1, Assignments
list_to_assocAssignments, Plan
131assign[], _, []
132assignStart−spanD, Start, End, First, Dirty|Ss, Bank, Plan ←
free_registerBank, Start, End, R, Next
→
Plan = D−entryR, Start, End, First, Dirty|Ps
else
Next = Bank
Plan = Ps
assignSs, Next, Ps
137free_registerR−Until|Rs, Start, End, R, R−End|Rs ←
Until < Start
!
138free_registerB|Rs, Start, End, R, B|Next ←
free_registerRs, Start, End, R, Next
140cached_lines[], _, _, _ ⟶
[]
141cached_linesL|Ls, Es, Plan, I ⟶
home_moveL, Es, D, _
get_assocD, Plan, entryR, Start, End, First, Dirty
→
I =:= Start
First ≡ read
→
insmov, q, memD, rbp, regR
else
[]
replace_homeL, R, New
New
I =:= End
Dirty ≡ true
→
insmov, q, regR, memD, rbp
else
[]
else
L
J is I + 1
cached_linesLs, Es, Plan, J
150replace_homeinsmov, q, regS, mem_, rbp, R, insmov, q, regS, regR
151replace_homeinsmov, S, mem_, rbp, regD, R, insmov, S, regN, regD ←