regalloc_evict_test.nx source
↩ module page · 95 lines · 2965 B
1// regalloc_evict_test.nx -- proves the Poletto-Sarkar spill-at-
2// interval eviction policy fires (added to linear_scan in
3// nx_regalloc.nx).
4//
5// Construction: build 17 long-lived binop values (v0..v16) where
6// v0 has the LATEST use (end ~ 34) and v16 has the EARLIEST use
7// (end ~ 18). With 16 GPRs and 17 live values, exactly one must
8// spill.
9//
10// Without eviction: v16 spills (arrival order -- the latest-arriving
11// interval that finds the pool empty gets demoted). This wastes a
12// spill slot on a short-lived value while a long-lived value (v0)
13// happily keeps its register.
14//
15// With eviction (the new policy): when v16 arrives and pop_free
16// returns -1, spill_furthest_gpr walks active[] (sorted by end
17// ascending) and finds v0 at the back with end=34 > v16.end=18.
18// Since v0.end > v16.end, v0 is evicted and v16 gets v0's register.
19//
20// The assertion: locs[ID_OF_V0].kind == VL_SPILLED. This is the
21// proof the eviction fired -- v0 was the LATEST-end interval and
22// got evicted by the new spill heuristic, not by arrival order.
23
24import "nx_syscalls.nx"
25import "nx_types.nx"
26import "nx_ir.nx"
27import "nx_regalloc.nx"
28
29const N_VALS: i64 = 17 // values v0..v16; one more than 16 GPRs
30
31func main() -> i64 {
32 let m_raw: *u8 = sys_mmap(256)
33 let m: *Module = m_raw as *Module
34 m.name = "ra_evict_test" as *u8
35 m.functions = 0 as *Function
36 m.n_functions = 0
37
38 let f: *Function = ir_function_new(m, "main" as *u8, 4, ir_type_i64())
39 let b: *BasicBlock = ir_block_new(f)
40
41 let c0: i64 = ir_const_i64(f, 1)
42
43 let consts_raw: *u8 = sys_mmap(N_VALS * 8 + 8)
44 let consts: *i64 = consts_raw as *i64
45 var i: i64 = 0
46 while i < N_VALS {
47 consts[i] = ir_const_i64(f, i + 2)
48 i = i + 1
49 }
50
51 let vs_raw: *u8 = sys_mmap(N_VALS * 8 + 8)
52 let vs: *i64 = vs_raw as *i64
53 i = 0
54 while i < N_VALS {
55 vs[i] = ir_emit_binop(b, OP_ADD, c0, consts[i], ir_type_i64())
56 i = i + 1
57 }
58
59 var acc: i64 = vs[N_VALS - 1]
60 i = N_VALS - 2
61 while i >= 0 {
62 acc = ir_emit_binop(b, OP_ADD, acc, vs[i], ir_type_i64())
63 i = i - 1
64 }
65
66 ir_emit_return(b, acc)
67
68 let locs_raw: *u8 = sys_mmap(f.n_values * 16 + 16)
69 let locs: *ValueLoc = locs_raw as *ValueLoc
70
71 let mask_raw: *u8 = sys_mmap(16)
72 let mask: *i64 = mask_raw as *i64
73 *mask = 0
74 let mask_fpr_raw: *u8 = sys_mmap(16)
75 let mask_fpr: *i64 = mask_fpr_raw as *i64
76 *mask_fpr = 0
77 let sb_raw: *u8 = sys_mmap(16)
78 let sb: *i64 = sb_raw as *i64
79 *sb = 0
80
81 regalloc_function(f, locs, mask, mask_fpr, sb)
82
83 if *sb < 8 { return 10 }
84
85 let lbase: i64 = locs as i64
86 let v0_id: i64 = N_VALS + 1
87 let v16_id: i64 = v0_id + N_VALS - 1
88 let l_v0: *ValueLoc = (lbase + v0_id * 16) as *ValueLoc
89 let l_v16: *ValueLoc = (lbase + v16_id * 16) as *ValueLoc
90
91 if l_v0.kind != VL_SPILLED { return 20 }
92 if l_v16.kind != VL_REGISTER { return 21 }
93
94 return 0
95}