frame_slots.pl

Conservative stack-slot allocation for the Fil-C backend: temp_slots/6 assigns each temporary a frame slot, and temporaries whose live intervals are disjoint may share one.

A temporary's interval is closed and covers every write (even of a dead result), every use by an instruction and every block boundary where it is live in or out. One lowered instruction, including all its helper calls, is thus indivisible. Two temporaries share a slot only when their intervals are strictly disjoint, so a result never overwrites its operands.

Pool	Holds
`pointer`	`p` temporaries: each slot is a payload slot and its lower, allocated together
`scalar`	`w`, `l`, `s` and `d` temporaries; they never use the pointer pool

A variadic function's hidden va_snapshot parameter is kept live for the whole invocation. Functions that call setjmp must not use this allocator (docs/setjmp.md).

moduleframe_slots

exportstemp_slots/6

useslists

usesassoc

usespairs

temp_slots+Params, +Blocks, +Temps, -Aliases, -ScalarCount, -PtrCount

Aliases maps each temp name to physical storage(Pool, Index).

29temp_slotsParams, Blocks, Temps, Aliases, NS, NP ←

temp_livenessBlocks, In, Out

foldlparam_point, Params, [], R₁

block_rangesBlocks, In, Out, 1, End, R₁, R₂

va_args reads this backend-only parameter implicitly. Reserve both

its address and lower for the entire invocation.

memberchkparamp, tmphiddenva_snapshot, Params

→

touchhiddenva_snapshot, End, R₂, Points

else

Points = R₂

Batch the points rather than updating a persistent tree for every

use. Trealla otherwise retains gigabytes of intermediate trees on

large functions. Grouping computes exactly the same convex hulls.

keysortPoints, Sorted

group_pairs_by_keySorted, Groups

maplistgroup_range, Groups, Pairs

list_to_assocPairs, Ranges

maplisttemp_intervalRanges, Temps, Intervals₀

sortIntervals₀, Intervals

empty_assocA₀

allocateIntervals, [], [], 0, NS, 0, NP, A₀, Aliases

49param_pointparam_, tmpN, R₀, R ←

touchN, 0, R₀, R

53group_rangeN−Ps, N−Lo−Hi ←

min_listPs, Lo

max_listPs, Hi

55points[], _, R, R

56pointsN|Ns, P, R₀, R ←

touchN, P, R₀, R₁

pointsNs, P, R₁, R

59block_ranges[], _, _, P, P, R, R

60block_rangesblockL, Phis, Insts, Jump|Bs, In, Out, P, End, R₀, R ←

get_assocL, In, LiveIn

pointsLiveIn, P, R₀, R₁

phi_pointsPhis, P, R₁, R₂

P₁ is P + 1

inst_rangesInsts, P₁, Exit, R₂, R₃

jump_usesJump, Uses

pointsUses, Exit, R₃, R₄

get_assocL, Out, LiveOut

pointsLiveOut, Exit, R₄, R₅

Next is Exit + 1

block_rangesBs, In, Out, Next, End, R₅, R

70phi_points[], _, R, R

71phi_pointsphitmpN, _, _|Ps, P, R₀, R ←

touchN, P, R₀, R₁

phi_pointsPs, P, R₁, R

74inst_ranges[], P, P, R, R

75inst_rangesI|Is, P, End, R₀, R ←

inst_usesI, Uses

pointsUses, P, R₀, R₁

findallN, inst_defI, N, Defs

pointsDefs, P, R₁, R₂

Next is P + 1

inst_rangesIs, Next, End, R₂, R

81temp_intervalRanges, N−K, rangeStart, End, Pool, N ←

get_assocN, Ranges, Start−End

class_poolK, Pool

class_pool
85	p	pointer
86	w	scalar
87	l	scalar
88	s	scalar
89	d	scalar

91allocate[], _, _, NS, NS, NP, NP, A, A

92allocaterangeStart, End, Pool, N|Rs, SS₀, PS₀, NS₀, NS, NP₀, NP, A₀, A ←

pool_slotPool, Start, End, SS₀, SS, PS₀, PS, NS₀, NS₁, NP₀, NP₁, I

put_assocN, A₀, storagePool, I, A₁

allocateRs, SS, PS, NS₁, NS, NP₁, NP, A₁, A

97pool_slotscalar, S, E, SS₀, SS, PS, PS, NS₀, NS, NP, NP, I ←

reuse_slotSS₀, S, E, NS₀, NS, SS, I

99pool_slotpointer, S, E, SS, SS, PS₀, PS, NS, NS, NP₀, NP, I ←

reuse_slotPS₀, S, E, NP₀, NP, PS, I

One end point per physical slot, not an interference graph. Reuse only strictly disjoint intervals: results cannot overwrite their operands.

104reuse_slot[], _, E, N₀, N, slotN₀, E, N₀ ←

N is N₀ + 1

105reuse_slotslotI₀, E₀|Ss₀, S, E, N₀, N, Ss, I ←

E₀ < S

→

Ss = slotI₀, E|Ss₀

I = I₀

N = N₀

else

Ss = slotI₀, E₀|Tail

reuse_slotSs₀, S, E, N₀, N, Tail, I