compiler/
lib/
examples/
std/
arch/
collections/
lang/
alloc/
ast/
gen/
bitset/
regalloc/
bitset.rad
5.0 KiB
labels.rad
2.4 KiB
regalloc.rad
2.3 KiB
il/
lower/
module/
parser/
resolver/
scanner/
alloc.rad
4.2 KiB
ast.rad
22.6 KiB
gen.rad
265 B
il.rad
15.1 KiB
lower.rad
258.3 KiB
module.rad
14.1 KiB
package.rad
1.4 KiB
parser.rad
78.7 KiB
resolver.rad
227.9 KiB
scanner.rad
23.4 KiB
sexpr.rad
7.0 KiB
strings.rad
2.2 KiB
sys/
arch.rad
65 B
collections.rad
36 B
fmt.rad
3.8 KiB
intrinsics.rad
206 B
io.rad
1.2 KiB
lang.rad
222 B
mem.rad
2.2 KiB
sys.rad
167 B
testing.rad
2.4 KiB
tests.rad
11.6 KiB
vec.rad
3.1 KiB
std.rad
231 B
scripts/
seed/
test/
vim/
.gitignore
353 B
.gitsigners
112 B
LICENSE
1.1 KiB
Makefile
3.1 KiB
README
2.5 KiB
std.lib
987 B
std.lib.test
252 B
lib/std/lang/gen/regalloc.rad
raw
| 1 | //! Register allocator. |
| 2 | //! |
| 3 | //! Coordinates the two phases of register allocation: |
| 4 | //! 1. `spill`: Determine spill slots and register class constraints. |
| 5 | //! 2. `assign`: Map SSA values to physical registers. |
| 6 | //! |
| 7 | //! Spill pass focuses on *what* to spill and call-clobber policy. |
| 8 | //! Assign pass focuses on *where* to put values. |
| 9 | //! Neither pass can fail if the other did its job correctly. |
| 10 | //! |
| 11 | //! [`il`] -> [`liveness`] -> [`spill`] -> [`assign`] -> [`AllocResult`]. |
| 12 | //! |
| 13 | //! Note that the IL is not modified. The allocator produces a mapping that |
| 14 | //! instruction selection uses to emit physical registers. Spilled values are |
| 15 | //! handled by [`isel`] inserting loads/stores. |
| 16 | |
| 17 | pub mod liveness; |
| 18 | pub mod spill; |
| 19 | pub mod assign; |
| 20 | |
| 21 | use std::lang::il; |
| 22 | use std::lang::alloc; |
| 23 | |
| 24 | /// Target configuration for register allocation. |
| 25 | pub record TargetConfig { |
| 26 | /// List of allocatable physical register numbers. |
| 27 | /// Order determines allocation preference. |
| 28 | allocatable: *[u8], |
| 29 | /// Function argument registers. |
| 30 | argRegs: *[u8], |
| 31 | /// Callee-saved register numbers. |
| 32 | calleeSaved: *[u8], |
| 33 | /// Size of a spill slot in bytes. |
| 34 | slotSize: u32, |
| 35 | } |
| 36 | |
| 37 | /// Complete register allocation result. |
| 38 | pub record AllocResult { |
| 39 | /// SSA register to physical register mapping. |
| 40 | assignments: *[?u8], |
| 41 | /// Spill slot information. |
| 42 | spill: spill::SpillInfo, |
| 43 | /// Bitmask of used callee-saved registers. |
| 44 | usedCalleeSaved: u32, |
| 45 | } |
| 46 | |
| 47 | /// Run register allocation on a function. |
| 48 | /// |
| 49 | /// Returns a mapping from SSA registers to physical registers, plus |
| 50 | /// spill information. |
| 51 | pub fn allocate( |
| 52 | func: *il::Fn, |
| 53 | config: *TargetConfig, |
| 54 | arena: *mut alloc::Arena |
| 55 | ) -> AllocResult throws (alloc::AllocError) { |
| 56 | // Phase 1: Liveness analysis. |
| 57 | let live = try liveness::analyze(func, arena); |
| 58 | // Phase 2: Spill analysis (determine which values need stack slots). |
| 59 | let spillInfo = try spill::analyze(func, &live, config.allocatable.len, config.calleeSaved.len, config.slotSize, arena); |
| 60 | // Phase 3: Register assignment (map SSA registers to physical registers). |
| 61 | let assignInfo = try assign::assign(func, &live, &spillInfo, config, arena); |
| 62 | |
| 63 | return AllocResult { |
| 64 | assignments: assignInfo.assignments, |
| 65 | spill: spillInfo, |
| 66 | usedCalleeSaved: assignInfo.usedCalleeSaved, |
| 67 | }; |
| 68 | } |