compiler/
lib/
examples/
std/
arch/
char/
collections/
lang/
alloc/
ast/
gen/
bitset/
regalloc/
liveness/
assign.rad
11.8 KiB
liveness.rad
10.0 KiB
spill.rad
12.5 KiB
bitset.rad
4.6 KiB
data.rad
8.6 KiB
labels.rad
2.4 KiB
regalloc.rad
2.4 KiB
types.rad
594 B
il/
module/
parser/
resolver/
scanner/
alloc.rad
7.1 KiB
ast.rad
26.7 KiB
gen.rad
513 B
il.rad
20.3 KiB
lower.rad
315.6 KiB
module.rad
14.9 KiB
package.rad
1.3 KiB
parser.rad
91.2 KiB
resolver.rad
452.9 KiB
scanner.rad
17.9 KiB
sexpr.rad
6.7 KiB
strings.rad
2.2 KiB
types.rad
1.6 KiB
sys/
arch.rad
68 B
char.rad
855 B
collections.rad
39 B
fmt.rad
8.3 KiB
intrinsics.rad
467 B
io.rad
1.7 KiB
lang.rad
276 B
mem.rad
2.3 KiB
sys.rad
179 B
testing.rad
2.4 KiB
tests.rad
15.7 KiB
vec.rad
3.2 KiB
std.rad
281 B
scripts/
seed/
sublime/
test/
vim/
.gitignore
336 B
.gitsigners
112 B
CONTRIBUTING
2.1 KiB
LICENSE
1.1 KiB
Makefile
5.4 KiB
README
2.5 KiB
STYLE
2.5 KiB
std.lib
1.5 KiB
std.lib.test
662 B
lib/std/lang/gen/regalloc/assign.rad
raw
| 1 | //! Register assignment. |
| 2 | //! |
| 3 | //! This pass assigns physical registers to SSA values. It runs after spilling |
| 4 | //! has ensured register pressure never exceeds available registers. |
| 5 | //! |
| 6 | //! The IL is not modified. Instead, a mapping from SSA registers to physical |
| 7 | //! registers is produced for use by instruction selection. |
| 8 | |
| 9 | use std::lang::il; |
| 10 | use std::lang::alloc; |
| 11 | use std::lang::gen; |
| 12 | use std::lang::gen::bitset; |
| 13 | use std::lang::gen::regalloc::liveness; |
| 14 | use std::lang::gen::regalloc::spill; |
| 15 | |
| 16 | /// Maximum number of active register mappings. |
| 17 | constant MAX_ACTIVE: u32 = 64; |
| 18 | |
| 19 | /// Register mapping at a program point. |
| 20 | /// Maps SSA registers to physical registers. |
| 21 | export record RegMap: 'scratch { |
| 22 | /// SSA (virtual) registers that have mappings. |
| 23 | virtRegs: &'scratch mut [u32], |
| 24 | /// Physical register for each virtual register. |
| 25 | physRegs: &'scratch mut [gen::Reg], |
| 26 | /// Number of active mappings. |
| 27 | n: u32, |
| 28 | } |
| 29 | |
| 30 | /// Register assignment result, per function. |
| 31 | export record AssignInfo: 'scratch + Copy { |
| 32 | /// SSA register -> physical register mapping. |
| 33 | assignments: &'scratch [?gen::Reg], |
| 34 | /// Bitmask of used callee-saved registers. |
| 35 | usedCalleeSaved: u32, |
| 36 | } |
| 37 | |
| 38 | /// Register state for scanning one block's instructions. |
| 39 | record InstrCtx: 'scratch + 'step where 'scratch: 'step { |
| 40 | current: &'step mut RegMap 'scratch, |
| 41 | usedRegs: &'step mut [u32], |
| 42 | /// Last operand-use index for each register used in the current block. |
| 43 | lastUse: &'step mut [u32], |
| 44 | live: &'step liveness::LiveInfo 'scratch, |
| 45 | blockIdx: u32, |
| 46 | instrIdx: u32, |
| 47 | allocatable: *[gen::Reg], |
| 48 | calleeSaved: *[gen::Reg], |
| 49 | assignments: &'step mut [?gen::Reg], |
| 50 | spillInfo: &'step spill::SpillInfo 'scratch, |
| 51 | } |
| 52 | |
| 53 | /// Compute register assignment. |
| 54 | export unsafe fn assign 'scratch ( |
| 55 | func: &il::Fn, |
| 56 | live: &liveness::LiveInfo 'scratch, |
| 57 | spillInfo: &spill::SpillInfo 'scratch, |
| 58 | config: &super::TargetConfig, |
| 59 | storage: &Session 'scratch |
| 60 | ) -> AssignInfo 'scratch throws (alloc::AllocError) { |
| 61 | return try assignTables(func.params, func.blocks, live, spillInfo, config, storage); |
| 62 | } |
| 63 | |
| 64 | /// Allocate register mappings for borrowed function parameter and block tables. |
| 65 | fn assignTables 'scratch ( |
| 66 | params: &[il::Param], |
| 67 | blocks: &[il::Block], |
| 68 | live: &liveness::LiveInfo 'scratch, |
| 69 | spillInfo: &spill::SpillInfo 'scratch, |
| 70 | config: &super::TargetConfig, |
| 71 | storage: &Session 'scratch, |
| 72 | ) -> AssignInfo 'scratch throws (alloc::AllocError) { |
| 73 | let maxReg = live.maxReg; |
| 74 | let blockCount = blocks.len; |
| 75 | let allocatable = config.allocatable; |
| 76 | |
| 77 | if maxReg == 0 or blockCount == 0 { |
| 78 | return AssignInfo 'scratch { |
| 79 | assignments: try storage.fill(nil as ?gen::Reg, 0), |
| 80 | usedCalleeSaved: 0, |
| 81 | }; |
| 82 | } |
| 83 | |
| 84 | // Allocate output structures. |
| 85 | let assignments = try storage.fill(nil as ?gen::Reg, maxReg); |
| 86 | // Pre-assign function parameters to argument registers. |
| 87 | // Cross-call params are NOT pre-assigned here; they will be allocated |
| 88 | // to callee-saved registers by the normal path, and isel emits moves |
| 89 | // from the arg register to the assigned register at function entry. |
| 90 | for param, i in params { |
| 91 | if i < config.argRegs.len { |
| 92 | if not bitset::contains(spillInfo.calleeClass, param.value.n) { |
| 93 | set assignments[param.value.n] = config.argRegs[i]; |
| 94 | } |
| 95 | } |
| 96 | } |
| 97 | // Allocate used registers bitset (32 physical registers per 32-bit word). |
| 98 | let usedRegs = try bitset::allocate(storage, 32); |
| 99 | |
| 100 | // Current register mapping. |
| 101 | // Reuse one last-use table for all blocks in the function. |
| 102 | let lastUse = try storage.fill(0 as u32, maxReg); |
| 103 | let mut current = try createRegMap(storage); |
| 104 | |
| 105 | // Phase 2: Linear scan allocation. |
| 106 | for b in 0..blockCount { |
| 107 | let block = &blocks[b]; |
| 108 | let currentRef: 'step = &mut current, usedRef = &mut usedRegs[..], |
| 109 | lastUseRef = &mut lastUse[..], liveRef = &*live, |
| 110 | assignmentsRef = &mut assignments[..], spillRef = &*spillInfo |
| 111 | where 'scratch: 'step in { |
| 112 | let mut ctx = InstrCtx 'scratch 'step { |
| 113 | current: currentRef, |
| 114 | usedRegs: usedRef, |
| 115 | lastUse: lastUseRef, |
| 116 | live: liveRef, |
| 117 | blockIdx: b, |
| 118 | instrIdx: 0, |
| 119 | allocatable, |
| 120 | calleeSaved: config.calleeSaved, |
| 121 | assignments: assignmentsRef, |
| 122 | spillInfo: spillRef, |
| 123 | }; |
| 124 | unsafe { |
| 125 | assignBlock(block.params, block.instrs, &mut ctx, config); |
| 126 | } |
| 127 | } |
| 128 | } |
| 129 | // Compute bitmask of used callee-saved registers. |
| 130 | let mut usedCalleeSaved: u32 = 0; |
| 131 | for i in 0..maxReg { |
| 132 | if let phys = assignments[i] { |
| 133 | for saved, j in config.calleeSaved { |
| 134 | if *phys == *saved { |
| 135 | set usedCalleeSaved |= (1 << j); |
| 136 | } |
| 137 | } |
| 138 | } |
| 139 | } |
| 140 | |
| 141 | return AssignInfo 'scratch { |
| 142 | assignments: &assignments[..], |
| 143 | usedCalleeSaved, |
| 144 | }; |
| 145 | } |
| 146 | |
| 147 | /// Assign one block's source and destination registers in instruction order. |
| 148 | fn assignBlock 'scratch 'step ( |
| 149 | params: &[il::Param], |
| 150 | instructions: &[il::Instr], |
| 151 | ctx: &mut InstrCtx 'scratch 'step, |
| 152 | config: &super::TargetConfig, |
| 153 | ) where 'scratch: 'step { |
| 154 | // Record every operand before allocation. Only current-block operands |
| 155 | // query this table, so every read is initialized by this scan. |
| 156 | // Entries for other registers need not be cleared between blocks. |
| 157 | for i in 0..instructions.len { |
| 158 | let instr = &instructions[i]; |
| 159 | let mut registers = il::registers(instr); |
| 160 | unsafe { |
| 161 | while let reg = il::nextReg(&mut registers, instr) { |
| 162 | recordLastUse(reg, ctx.lastUse, i); |
| 163 | } |
| 164 | } |
| 165 | } |
| 166 | |
| 167 | enterBlock(ctx.current, ctx.usedRegs, liveness::liveInRow(ctx.live, ctx.blockIdx), params, ctx.assignments, config, ctx.spillInfo); |
| 168 | |
| 169 | // Process each instruction. |
| 170 | for i in 0..instructions.len { |
| 171 | let instr = &instructions[i]; |
| 172 | set ctx.instrIdx = i; |
| 173 | let mut registers = il::registers(instr); |
| 174 | unsafe { |
| 175 | while let reg = il::nextReg(&mut registers, instr) { |
| 176 | processInstrReg(reg, ctx); |
| 177 | } |
| 178 | } |
| 179 | |
| 180 | // Allocate destination. |
| 181 | if let dst = il::instrDst(*instr) { |
| 182 | if dst.n < ctx.assignments.len and not spill::isSpilled(ctx.spillInfo, dst) { |
| 183 | set ctx.assignments[dst.n] = rallocReg(ctx.current, ctx.usedRegs, dst.n, ctx.allocatable, ctx.calleeSaved, ctx.spillInfo); |
| 184 | } |
| 185 | } |
| 186 | } |
| 187 | } |
| 188 | |
| 189 | /// Reserve live-in registers before assigning the block's parameter registers. |
| 190 | fn enterBlock 'scratch ( |
| 191 | current: &mut RegMap 'scratch, |
| 192 | usedRegs: &mut [u32], |
| 193 | liveIn: &[u32], |
| 194 | params: &[il::Param], |
| 195 | assignments: &mut [?gen::Reg], |
| 196 | config: &super::TargetConfig, |
| 197 | spillInfo: &spill::SpillInfo 'scratch, |
| 198 | ) { |
| 199 | // Reset for new block. |
| 200 | set current.n = 0; |
| 201 | bitset::clearAll(usedRegs); |
| 202 | |
| 203 | // Mark all live-in values' registers as used. |
| 204 | // This ensures we don't reuse registers for values that flow in |
| 205 | // from predecessors, even at merge points with multiple predecessors. |
| 206 | // Values that are live-in but have no assignment yet (e.g. callee-saved |
| 207 | // function parameters not used before a phi block) are allocated now to |
| 208 | // prevent conflicts with block parameters. |
| 209 | let mut liveInIter = bitset::iter(liveIn); |
| 210 | while let ssaReg = bitset::iterNext(&mut liveInIter, liveIn) { |
| 211 | let reg = il::Reg { n: ssaReg }; |
| 212 | if not spill::isSpilled(spillInfo, reg) { |
| 213 | if let phys = assignments[ssaReg] { |
| 214 | bitset::put(usedRegs, *phys as u32); |
| 215 | rmapSet(current, ssaReg, phys); |
| 216 | } else { |
| 217 | set assignments[ssaReg] = rallocReg(current, usedRegs, ssaReg, config.allocatable, config.calleeSaved, spillInfo); |
| 218 | } |
| 219 | } |
| 220 | } |
| 221 | |
| 222 | // Allocate block parameters. |
| 223 | for p in params { |
| 224 | if p.value.n < assignments.len and not spill::isSpilled(spillInfo, p.value) { |
| 225 | set assignments[p.value.n] = rallocReg(current, usedRegs, p.value.n, config.allocatable, config.calleeSaved, spillInfo); |
| 226 | } |
| 227 | } |
| 228 | } |
| 229 | |
| 230 | /// Create an empty register map. |
| 231 | fn createRegMap 'scratch (storage: &Session 'scratch) -> RegMap 'scratch throws (alloc::AllocError) { |
| 232 | let virtRegs = try storage.fill(0 as u32, MAX_ACTIVE); |
| 233 | let physRegs = try storage.fill(gen::Reg(0), MAX_ACTIVE); |
| 234 | return RegMap 'scratch { virtRegs, physRegs, n: 0 }; |
| 235 | } |
| 236 | |
| 237 | /// Find physical register for a virtual register in RegMap. |
| 238 | fn rmapFind 'scratch (rmap: &RegMap 'scratch, virtReg: u32) -> ?gen::Reg { |
| 239 | for i in 0..rmap.n { |
| 240 | if rmap.virtRegs[i] == virtReg { |
| 241 | return rmap.physRegs[i]; |
| 242 | } |
| 243 | } |
| 244 | return nil; |
| 245 | } |
| 246 | |
| 247 | /// Add a mapping to the register map. |
| 248 | fn rmapSet 'scratch (rmap: &mut RegMap 'scratch, virtReg: u32, physReg: gen::Reg) { |
| 249 | assert rmap.n < MAX_ACTIVE, "rmapSet: register map overflow"; |
| 250 | set rmap.virtRegs[rmap.n] = virtReg; |
| 251 | set rmap.physRegs[rmap.n] = physReg; |
| 252 | set rmap.n += 1; |
| 253 | } |
| 254 | |
| 255 | /// Remove a mapping from the register map and return its physical register. |
| 256 | fn rmapRemove 'scratch (rmap: &mut RegMap 'scratch, virtReg: u32) -> ?gen::Reg { |
| 257 | for i in 0..rmap.n { |
| 258 | if rmap.virtRegs[i] == virtReg { |
| 259 | let phys = rmap.physRegs[i]; |
| 260 | // Swap with last and decrement. |
| 261 | set rmap.n -= 1; |
| 262 | if i < rmap.n { |
| 263 | set rmap.virtRegs[i] = rmap.virtRegs[rmap.n]; |
| 264 | set rmap.physRegs[i] = rmap.physRegs[rmap.n]; |
| 265 | } |
| 266 | return phys; |
| 267 | } |
| 268 | } |
| 269 | return nil; |
| 270 | } |
| 271 | |
| 272 | /// Find first free register in pool, allocate it, return it. |
| 273 | fn findFreeInPool 'scratch (usedRegs: &mut [u32], current: &mut RegMap 'scratch, ssaReg: u32, pool: *[gen::Reg]) -> ?gen::Reg { |
| 274 | for r in pool { |
| 275 | if not bitset::contains(usedRegs, *r as u32) { |
| 276 | bitset::put(usedRegs, *r as u32); |
| 277 | rmapSet(current, ssaReg, r); |
| 278 | return r; |
| 279 | } |
| 280 | } |
| 281 | return nil; |
| 282 | } |
| 283 | |
| 284 | /// Allocate a physical register for an SSA register. |
| 285 | /// Cross-call values are steered to callee-saved registers. |
| 286 | fn rallocReg 'scratch ( |
| 287 | current: &mut RegMap 'scratch, |
| 288 | usedRegs: &mut [u32], |
| 289 | ssaReg: u32, |
| 290 | allocatable: *[gen::Reg], |
| 291 | calleeSaved: *[gen::Reg], |
| 292 | spillInfo: &spill::SpillInfo 'scratch |
| 293 | ) -> gen::Reg { |
| 294 | // Check if already assigned. |
| 295 | if let phys = rmapFind(current, ssaReg) { |
| 296 | return phys; |
| 297 | } |
| 298 | // Allocate from appropriate pool. Cross-call values must use callee-saved |
| 299 | // registers since they are live across function calls. |
| 300 | if bitset::contains(spillInfo.calleeClass, ssaReg) { |
| 301 | if let r = findFreeInPool(usedRegs, current, ssaReg, calleeSaved) { |
| 302 | return r; |
| 303 | } |
| 304 | panic "rallocReg: no callee-saved register for cross-call value"; |
| 305 | } |
| 306 | if let r = findFreeInPool(usedRegs, current, ssaReg, allocatable) { |
| 307 | return r; |
| 308 | } |
| 309 | panic "rallocReg: no free register, spilling fault"; |
| 310 | } |
| 311 | |
| 312 | /// Record the last instruction that uses the register. |
| 313 | fn recordLastUse(reg: il::Reg, lastUse: &mut [u32], index: u32) { |
| 314 | set lastUse[reg.n] = index; |
| 315 | } |
| 316 | |
| 317 | /// Release expired registers and assign a register for this operand. |
| 318 | fn processInstrReg 'scratch 'step (reg: il::Reg, ctx: &mut InstrCtx 'scratch 'step) where 'scratch: 'step { |
| 319 | if not (bitset::contains(liveness::liveOutRow(ctx.live, ctx.blockIdx), reg.n) or ctx.lastUse[reg.n] > ctx.instrIdx) { |
| 320 | if let phys = rmapRemove(ctx.current, reg.n) { |
| 321 | bitset::clear(ctx.usedRegs, *phys as u32); |
| 322 | } |
| 323 | } |
| 324 | assert reg.n < ctx.assignments.len, "processInstrReg: register out of bounds"; |
| 325 | if spill::isSpilled(ctx.spillInfo, reg) { |
| 326 | return; // Spilled values don't get physical registers. |
| 327 | } |
| 328 | if ctx.assignments[reg.n] == nil { |
| 329 | set ctx.assignments[reg.n] = rallocReg( |
| 330 | ctx.current, ctx.usedRegs, reg.n, ctx.allocatable, |
| 331 | ctx.calleeSaved, ctx.spillInfo |
| 332 | ); |
| 333 | } |
| 334 | } |