amd64_regs.pl
Whole-function register homes for scalar temporaries (docs/perf.md item 3, step 3a), with step 3b's operand rewrite and 5a-loads' frame cells: --registers=temps, and --registers=pointers, the -O default. A fixed map puts frame homes in registers for the whole function: homes live across a call in the callee-saved rbx and r12-r15, the others also in r10/r11. Accesses stay the moves the reference emits, with a register in place of the slot; no instruction is selected differently.
A home is a candidate when it is a scalar (w/l) home, or under pointers a pointer's address word (class a), every access to it is a whole move of that home (amd64_regs_check:substitute/3), its address is never taken, it is not live at entry, and no 32-bit store to it leaves its high half live. Homes interfere when one is written while the other is live; a greedy colouring by estimated execution count (references weighted by the depth of the backward jumps around them) assigns registers. Homes that get none stay in their slots.
The emitter reserves a save slot per callee-saved register in this mode; the registers the map uses are saved after the stack check and restored before every leave. amd64_regs_check validates the result; a failed check is an error, never a silent fallback.
Mode is map (3a's map alone, unchecked, for a layout choice; Final is then not to be emitted) or frame(Cells) (step 3a, then step 3b's operand rewrite with the frame cells of docs/perf.md 5a-loads). Metadata is regs_metadata(Setjmp, Impl, Homes, Saves) with a save slot for every callee-saved register. Checked is the metadata and map the checker validated: checked(Metadata1, Map). Report is excluded(setjmp|unsupported) or allocated(Homes, Registers).
the lines the map depends on: labels, control flow, calls, and lines with a memory operand or a lea. A line left out falls through and touches no home, so home liveness, interference, loop depths and references are the same as on the whole body; only scratch and flags liveness, which the allocation masks off, differ.
Map assigns candidate homes registers. Analysis is body_analysis/4's result for the candidates (a superset of Map's homes), or none when there are none.
the homes of Weighted (D-W, by offset) that the allocator considers, by offset. The liveness sets cost a bit per candidate half per line, so a function whose candidates times lines exceeds the budget (2^29 bits, a 64 MB set) keeps only its heaviest homes, ties going to the lower offset. At most seven registers go round, so the light ones seldom get one anyway. No bench function reaches the budget (sqlite3VdbeExec, the largest, is at 0.68); netcdf's tst_h_atts.c main (14156 homes, 285k lines) and openssh's libcrux (3054, 116k) do.
each reference to a scalar home gives Home-Weight, or Home-bad when the line is not a whole move of exactly that home.
a scalar home H within H0..H1; Words buckets the homes by 8-byte word.
for each line, how many backward jumps span it.
Numeric GNU as labels are nonempty decimal digit sequences, not arbitrary Prolog numbers. Trealla's atom_number/2 throws on symbols.
home_facts: homes live across a call (Cross), homes whose 32-bit store leaves the high half live (Wide), and each home's interference row: an assoc from home number K to the halves live at any write of K, K's own excluded. HomeBits masks off the analysis's scratch and flags bits.
home D gets the first register of its list that no interfering home has. Homes J and K interfere when one's row has a half of the other. Taken holds, per register, the halves of the homes it was given and the union of their rows, so neither direction lists pairs: those are quadratic in the homes (netcdf's tst_h_atts.c had 12 million).
Step 3b: register operands (docs/perf.md)
Untrusted: check_operands/3 validates the result against A. Within each region (lines between boundaries), a forward pass propagates register and immediate copies into the moves and source operands that read them; then moves into dead scratch registers are deleted, a scratch result copied into a register is written there directly, and dead moves are deleted again. Liveness at a region's end is the reference's (operand_lives/4); inside, it is recomputed on the rewritten lines. The passes carry each line as Line-inf(Effect, Use, Def, Move): its audited effects, the scratch and flags sets it uses and defines, and its operand_move/2 reading or none, computed once.
the frame cells whose loads the rewrite may forward, the emitter's (docs/perf.md, 5a-loads).
a load of a cell that a register still holds whole (Held maps the cell to the register family that loaded or stored it, unchanged since) reads that register instead. forward/3 then propagates the copy like any other.
Contents maps a register family to what it holds: copy(G, W), G's value (W = 64) or its low half zero-extended (W = 32), or imm(V), the 64-bit value V.
A home register's name is never replaced by a scratch one: that would keep the scratch register live, and its producer unretargeted.
F changes; drop what it held and every copy of it.
source operands that read a copy or an immediate read the original; memory operands address through the original register. Each replacement must leave an audited form.
moves into scratch registers dead after them are deleted.
each line with the scratch families live after it.
a scratch result copied into a register H is written to H.
the moves that follow, each copying the producer's last operand register (S) into another one, and the scratch set live after the last. The later moves read the first one's destination H instead, so none may write H.
mov Src,%S; op X,%S; mov %S,%H -> mov Src,%H; op X,%H
op ...,%S; mov %S,%H -> op ...,%H, for a form whose last operand is a pure 32- or 64-bit destination.
Region allocation (docs/perf.md item 19, lever 1)
Selection is how operands are chosen after step 3a (main.pl's --operands=, NANOFIL_OPERANDS): rewrite, step 3b's copy forwarding, or regions, the default, alloc_rewrite/5.
Untrusted, like step 3b's rewrite, and validated by the same check_operands/4. Within a region, A's moves are not executed at all: the checker only needs B's paired lines to read A's values and B's registers to hold A's at the region's end where they are live. So each region is allocated again from A's symbolic values, computed by the checker's own step relations (paired/7, move_state/3):
- every paired line's register operands read any register that holds A's value, or an immediate where A's form takes one;
- a destination is the register where the result is needed at the region's end, else A's register, else any register whose value is not needed after the line (a value is needed while a later line or the region's end reads it and no other register holds it);
- a two-address destination is a register that already holds the input and can be overwritten, or gets a copy of it first;
- lines this does not model (division, partial register writes, SSE, shifts by %cl, setcc) keep A's registers, which first get A's values;
- at the region's end, live registers get A's values by a parallel move.
Home registers are free inside a region and dead ones at its end too (operand_lives/5). Moves are the only lines it inserts, so the flags are never touched. A region it cannot allocate, or allocates into more lines than step 3b's rewrite, gets step 3b's rewrite.
B is the implementation body A with each region allocated again (above). Lives are operand_lives/5's sets for A's lines, Cells the valid frame cells, Usable the registers B may write: the scratch families, r10, r11 and the callee-saved registers the map saves.
unreachable lines stay, and so does a region without moves (nothing to remove); otherwise the allocation, unless it fails or step 3b's rewrite is shorter. An allocation of only A's paired lines is shortest, so the rewrite is not built for it.
a register or immediate move, or a load from the frame, which a cell may make one.
a_sim: A's region on the checker's symbolic values. Each paired line is p(J, Line, Effect, Mode, Pre, Post, Cells, Demands, FlagsLive), the last bound by flags_after/3.
The registers B may hold values in, in the order they are tried.
flex(Roles) when every register operand is a general register other than rsp and rbp, every register destination is written whole (32 or 64 bits) and the form has no implicit or fixed register; otherwise fixed.
the values Line reads from registers: lo(Lo) for a read of 32 bits or less, full(Lo, Hi) for 64 bits and addressing. A fixed line needs every register it reads or partly writes whole.
a move that puts K in T.
frame cell D holds K. A cell not stored in this region holds its start value, which names the cell; a stored one is in CS.
binds each line's FlagsLive, whether a later line or the region's end reads the flags it leaves.
Line is a move; S is S0 after it.
A fixed line: its registers get A's values, values it overwrites and that are still needed are copied away, then it is A's line.
A zero idiom: any register that can be overwritten.
A flex line: its destination, then its sources. A two-address destination is, by the first register of dest_order/6 that allows one: a register holding the input (or, for a commutative form, the other input) that can be overwritten, or a lea of an add or a sub of an immediate into it when the flags it leaves are dead; failing all, a register given the input by a move.
T can take LA's result without a move: it holds the input (same), the other input of a commutative form (swap), or a lea computes it (lea).
the line whose operands sources/15 finds in B, and where the destination goes. A swap reads A's second operand first; a lea reads A's two addends as an address.
A register addend that holds a constant becomes the displacement.
where a result goes: the register it is needed in at the region's end, A's register, then the others; registers that already hold their end value last.
each operand of B. A register source reads a register holding A's value, else an immediate, else a register given the value by a move; an address's registers likewise hold A's whole values.
a 64-bit register whose low W bits are A's register N's, for a lea that reads them as an address.
when the first register of Order is where the result LoR is needed at the region's end but still holds a needed value, that value moves on to the register it is needed in at the end, if that one is free or can be freed the same way (at most three deep). Otherwise nothing changes.