nx_x86_regalloc.nx
buildroot/runtime/nx_x86_regalloc.nx
about
nx_x86_regalloc.nx -- genuine x86_64 register allocation (G1 keystone).
FRESH, x86_-prefixed, self-host-isolated: re-implements the proven IDEAS of
nx_regalloc.nx (Interval shape, def-to-last-use scan, mark_crosses_call,
ValueLoc lowering) with ZERO shared symbols and NO `import "nx_regalloc.nx"`,
because regalloc_function is on the live RISC-V self-host bootstrap host
(nx_nxc.nx:139, nx_main.nx:64) that compiles the x86 compiler -- re-binding a
shared name there would corrupt the host. See docs/NX_G1_X86_REGALLOC_PLAN.
ALLOCATE-not-COPY: a homed value LIVES in a callee-saved GPR for its whole
live range (producing op computes straight into it -- zero copy), unlike the
reverted K=1 cache (movq %reg,%rbx per result, +2018 insns -> net-negative).
Home pool = the 5 SysV callee-saved GPRs {r12,r13,r14,r15,rbx} (home idx
0..4) -- none used as scratch/operand/arg/clobber by the x86 backend, so they
survive every CALL/SYSCALL/TAIL_CALL/clone with no save-around-call logic.
FIX-12 INVARIANT: never add rcx/rdx/rbp/r10/r11 to this pool.
THIS IS STEP 1b: full interval analysis (build_intervals + mark_crosses_call
+ single_block) RUNS over every function -- crash-tested by the self-host
fixpoint over the whole corpus -- but its result is DISCARDED: every value
lowers to {VL_SPILLED,-1}, mask 0, so emitted code is byte-identical to the
pre-regalloc backend. Home selection + emit-path retarget land in STEP 2.
dependencies 2 imports · 3 importers
imports: nx_syscalls.nxnx_types.nx
imported by: nx_compile_field_candidate_t280.nxnx_compile_x86.nxnx_x86_64_ctx.nx
structs
| 128 | struct X86Interval |
consts
| 29 | const X86_HOME_CAP: i64 = 5 // {r12,r13,r14,r15,rbx} |
| 33 | const X86_HOME_LOADS: i64 = 1 |
| 50 | const X86_CALLER_POOL_ENABLE: i64 = 1 |
| 51 | const X86_ALLOW_CROSSBLOCK: i64 = 1 |
| 57 | const X86_CALLER_MIN_WCOST: i64 = 256 |
| 61 | const X86_NEGCTL_CALLER_IGNORE_CALL: i64 = 0 |
| 62 | const X86_CALLER_BASE: i64 = 5 |
| 63 | const X86_CALLER_CAP: i64 = 4 // idx 5,6,7,8 |
| 67 | const X86_CALLER_MIN_USES: i64 = 1 |
| 433 | const X86_NEGCTL_NO_BACKEDGE_EXT: i64 = 0 |
| 612 | const X86_HOME_CAP_ENABLE: i64 = 1 // ON: composes with opt_run for the measured crypto win |
| 613 | const X86_HOME_MIN_USES: i64 = 3 // require >= this many uses to beat save/restore |
| 1166 | const X86_NEGCTL_NONNEG_ALWAYS: i64 = 0 |
| 1246 | const X86_FWD_ENABLE: i64 = 1 |
| 1250 | const X86_NEGCTL_FWD_IGNORE_STORE: i64 = 0 |
| 1255 | const X86_NEGCTL_FWD_WRONG_HOME: i64 = 0 |
| 1272 | const X86_CHAIN_ENABLE: i64 = 1 |
| 1276 | const X86_NEGCTL_CHAIN_IGNORE_READ: i64 = 0 |
| 1281 | const X86_NEGCTL_CHAIN_SELFREF_OFF: i64 = 0 |
| 1559 | const X86_LN7_BLOCK_FWD_ENABLE: i64 = 1 |
functions
| 77 | func x86_home_reg_name(idx: i64) -> *u8 |
| 98 | func x86_reg_eq(a: *u8, b: *u8) -> i64 |
| 111 | func x86_home_save_off(slot_index: i64) -> i64 |
| 115 | func x86_popcount(mask: i64) -> i64 |
| 139 | func x86_intv_at(buf: *X86Interval, id: i64) -> *X86Interval |
| 145 | func x86_val_at(f: *Function, id: i64) -> *Value |
| 149 | func x86_block_at(f: *Function, id: i64) -> *BasicBlock |
| 155 | func x86_operand_k(inst: *Instr, k: i64) -> i64 |
| 186 | func x86_n_value_operands(inst: *Instr) -> i64 |
| 197 | func x86_is_call_class(op: i64) -> i64 |
| 206 | func x86_touch_bb(first_bb: *i64, last_bb: *i64, v: i64, bi: i64) -> i64 |
| 222 | func x86_compute_loop_depth(f: *Function, depth: *i64) -> i64 |
| 252 | func x86_weight_for_depth(d: i64) -> i64 |
| 260 | func x86_compute_wcost(f: *Function, depth: *i64, wcost: *i64) -> i64 |
| 287 | func x86_build_intervals(f: *Function, intv: *X86Interval, |
| 435 | func x86_extend_backedge_intervals(f: *Function, intv: *X86Interval, |
| 475 | func x86_mark_crosses_call(intv: *X86Interval, n_values: i64, |
| 496 | func x86_is_pure_rax_binop(op: i64) -> i64 |
| 509 | func x86_is_homeable(f: *Function, intv: *X86Interval, alloca_off: *i64, |
| 564 | func x86_op_clobbers_caller_saved(op: i64) -> i64 |
| 586 | func x86_fn_has_clobber_intrinsic(f: *Function) -> i64 |
| 620 | func x86_select_homes(f: *Function, intv: *X86Interval, alloca_off: *i64, |
| 730 | func x86_ah_value_consume_ok(op: i64) -> i64 |
| 763 | func x86_ah_base_ok(f: *Function, v: i64) -> i64 |
| 778 | func x86_ah_ldst_sz8(inst: *Instr) -> i64 |
| 788 | func x86_ah_scan(f: *Function, alloca_off: *i64, elig: *i64, cnt: *i64) -> i64 |
| 831 | func x86_ah_select(f: *Function, elig: *i64, cnt: *i64, |
| 887 | func x86_g4_is_binop(op: i64) -> i64 |
| 903 | func x86_g4_is_cmp(op: i64) -> i64 |
| 915 | func x86_chain_op_commutative(op: i64) -> i64 |
| 929 | func x86_g4_producer_ok(op: i64) -> i64 |
| 954 | func x86_g4_pos_ok(jop: i64, k: i64, jres_homed: i64) -> i64 |
| 981 | func x86_g4_elide_scan(f: *Function, locs: *ValueLoc, alloca_off: *i64, |
| 1064 | func x86_g5_imm32_ok(v: i64) -> i64 |
| 1070 | func x86_g5_select_const_homes(f: *Function, intv: *X86Interval, |
| 1168 | func x86_const_ge(f: *Function, v: i64, lo: i64) -> i64 |
| 1177 | func x86_val_nonneg(f: *Function, v: i64, depth: i64) -> i64 |
| 1285 | func x86_chain_op_ok(op: i64) -> i64 |
| 1303 | func x86_chain_scan(f: *Function, alloca_off: *i64, alloca_home: *i64, |
| 1462 | func x86_fwd_const_in(f: *Function, u: i64, a: i64, b: i64, c2: i64, d: i64) -> i64 |
| 1479 | func x86_fwd_is_sibish(f: *Function, u: i64) -> i64 |
| 1505 | func x86_fwd_consumer_ok(f: *Function, J: *Instr, k: i64) -> i64 |
| 1565 | func x86_fwd_pos_audited(op: i64, k: i64) -> i64 |
| 1604 | func x86_fwd_step(f: *Function, K: *Instr, a: i64, r: i64) -> i64 |
| 1624 | func x86_fwd_push_succs2(f: *Function, B: *BasicBlock, scratch: *i64, sp_in: i64, nb: i64) -> i64 |
| 1679 | func x86_fwd_probe(f: *Function, inst: *Instr, alloca_off: *i64, intv: *X86Interval, |
| 1837 | func x86_fwd_cand_scan(f: *Function, alloca_off: *i64, intv: *X86Interval, fwd_cand: *i64, |
| 1870 | func x86_fwd_scan(f: *Function, alloca_off: *i64, alloca_home: *i64, |
| 1905 | func x86_recompute_cs_mask(f: *Function, intv: *X86Interval, alloca_off: *i64, |
| 1940 | func x86_ln7_rax_served(f: *Function, intv: *X86Interval, alloca_off: *i64, v: i64) -> i64 |
| 1971 | func x86_select_all(f: *Function, intv: *X86Interval, alloca_off: *i64, |
| 2108 | func x86_regalloc_function(f: *Function, alloca_off: *i64, |