lang: Select spills by scanning live values
43b0c873792beaafeb139e56cd3ec251dcb77c7f27d9133d9d675a6c13d72528
The spill pass copied every live value into a candidate array and insertion-sorted it at each instruction over the register limit, though it usually spills one value. The sort took most of the 3.9 s of the randomFunctions backend test, which also rebuilt full-size label tables for each of its 300 functions. The pass failed with an allocation error when more than 256 values were live. The pass now picks each spilled value with one scan of the live set, lowest register first among equal costs, so spill choices are unchanged. The candidate array, the cross-call collection and the 256-value limit are gone, and testSpillCandidateLimit becomes testSpillManyLive. The test builds small label tables and runs 100 functions that still exceed the register count, and testSpillCheapest covers ties and several spills at once. Assisted-by: Claude:opus-5.5
1 parent
314d754f
lib/std/arch/rv64/tests.rad
+85 -6
| 1322 | 1322 | try testing::expect(encode::isJumpImm(-1048576)); // Min negative |
|
| 1323 | 1323 | try testing::expectNot(encode::isJumpImm(1)); // Must be even |
|
| 1324 | 1324 | try testing::expectNot(encode::isJumpImm(1048576)); // Out of range |
|
| 1325 | 1325 | } |
|
| 1326 | 1326 | ||
| 1327 | - | /// Excess live values return an error before the spill candidate table overflows. |
|
| 1328 | - | @test unsafe fn testSpillCandidateLimit() throws (testing::TestError) { |
|
| 1327 | + | /// More live values than any fixed table could hold are spilled down to the register count. |
|
| 1328 | + | @test unsafe fn testSpillManyLive() throws (testing::TestError) { |
|
| 1329 | 1329 | let mut arena = alloc::new(&mut REGISTER_SCRATCH[..]); |
|
| 1330 | 1330 | let mut liveSet = try! bitset::allocate(&mut arena, 257); |
|
| 1331 | 1331 | for i in 0 .. 257 { |
|
| 1332 | 1332 | bitset::put(&mut liveSet, i); |
|
| 1333 | 1333 | } |
| 1357 | 1357 | vals: &[], |
|
| 1358 | 1358 | cases: &[], |
|
| 1359 | 1359 | }, |
|
| 1360 | 1360 | &mut arena |
|
| 1361 | 1361 | ); |
|
| 1362 | - | let mut failed = false; |
|
| 1363 | - | try regalloc::spill::analyze(&mut funcs[0], &live, 23, 11, 8, &mut arena) catch { |
|
| 1364 | - | set failed = true; |
|
| 1362 | + | let result = try! regalloc::spill::analyze(&mut funcs[0], &live, 23, 11, 8, &mut arena); |
|
| 1363 | + | // 257 values are live and 23 registers hold them, so 234 values are spilled. |
|
| 1364 | + | try testing::expect(result.info.frameSize == 234 * 8); |
|
| 1365 | + | let mut count: u32 = 0; |
|
| 1366 | + | for n in 0 .. 257 { |
|
| 1367 | + | if regalloc::spill::isSpilled(&result.info, il::Reg { n }) { |
|
| 1368 | + | set count += 1; |
|
| 1369 | + | } |
|
| 1370 | + | } |
|
| 1371 | + | try testing::expect(count == 234); |
|
| 1372 | + | } |
|
| 1373 | + | ||
| 1374 | + | /// Analyze one block whose `count` values are all live into it. Each value is a block |
|
| 1375 | + | /// parameter, which costs 1, except the values in the `free` mask, which cost 0. The result |
|
| 1376 | + | /// has bit `n` set when value `n` is spilled, for the 22 registers and 11 callee-saved |
|
| 1377 | + | /// registers of the target. |
|
| 1378 | + | unsafe fn spilledOf(count: u32, free: u64) -> u64 { |
|
| 1379 | + | let mut arena = alloc::new(&mut REGISTER_SCRATCH[..]); |
|
| 1380 | + | let mut liveSet = try! bitset::allocate(&mut arena, count); |
|
| 1381 | + | let mut params: *mut [il::Param] = &mut []; |
|
| 1382 | + | for n in 0 .. count { |
|
| 1383 | + | bitset::put(&mut liveSet, n); |
|
| 1384 | + | if ((free >> n as u64) & 1) == 0 { |
|
| 1385 | + | try! params.append( |
|
| 1386 | + | il::Param { value: il::Reg { n }, type: il::ValType::Data(il::Type::W64) }, |
|
| 1387 | + | &mut arena |
|
| 1388 | + | ); |
|
| 1389 | + | } |
|
| 1390 | + | } |
|
| 1391 | + | let mut out: *mut [bitset::Bitset] = &mut []; |
|
| 1392 | + | try! out.append(liveSet, &mut arena); |
|
| 1393 | + | let live = regalloc::liveness::LiveInfo { |
|
| 1394 | + | liveIn: &[], liveOut: out, defs: &[], uses: &[], order: &[0], blockCount: 1, maxReg: count |
|
| 1365 | 1395 | }; |
|
| 1366 | - | assert failed; |
|
| 1396 | + | let mut blocks: *mut [il::Block] = &mut []; |
|
| 1397 | + | try! blocks.append( |
|
| 1398 | + | il::Block { |
|
| 1399 | + | label: il::BlockLabel { base: "entry", suffix: nil }, |
|
| 1400 | + | params: ¶ms[..], |
|
| 1401 | + | instrs: &[], |
|
| 1402 | + | locs: &[], |
|
| 1403 | + | preds: &[], |
|
| 1404 | + | loopDepth: 0, |
|
| 1405 | + | }, |
|
| 1406 | + | &mut arena |
|
| 1407 | + | ); |
|
| 1408 | + | let mut funcs: *mut [il::Fn] = &mut []; |
|
| 1409 | + | try! funcs.append( |
|
| 1410 | + | il::Fn { |
|
| 1411 | + | name: "pressure", |
|
| 1412 | + | params: &[], |
|
| 1413 | + | returnType: il::ValType::Void, |
|
| 1414 | + | isExtern: false, |
|
| 1415 | + | isLeaf: true, |
|
| 1416 | + | blocks: &blocks[..], |
|
| 1417 | + | vals: &[], |
|
| 1418 | + | cases: &[], |
|
| 1419 | + | }, |
|
| 1420 | + | &mut arena |
|
| 1421 | + | ); |
|
| 1422 | + | let result = try! regalloc::spill::analyze(&mut funcs[0], &live, 22, 11, 8, &mut arena); |
|
| 1423 | + | let mut spilled: u64 = 0; |
|
| 1424 | + | for n in 0 .. count { |
|
| 1425 | + | if regalloc::spill::isSpilled(&result.info, il::Reg { n }) { |
|
| 1426 | + | set spilled |= 1 << n as u64; |
|
| 1427 | + | } |
|
| 1428 | + | } |
|
| 1429 | + | return spilled; |
|
| 1430 | + | } |
|
| 1431 | + | ||
| 1432 | + | /// The spill pass spills the cheapest values, and the lowest-numbered among equal costs. |
|
| 1433 | + | @test unsafe fn testSpillCheapest() throws (testing::TestError) { |
|
| 1434 | + | // Within the register count, nothing is spilled. |
|
| 1435 | + | try testing::expect(spilledOf(22, 0) == 0); |
|
| 1436 | + | // One value too many: all costs are equal, so the lowest register goes. |
|
| 1437 | + | try testing::expect(spilledOf(23, 0) == 0b1); |
|
| 1438 | + | // Several too many: the lowest registers go. |
|
| 1439 | + | try testing::expect(spilledOf(26, 0) == 0b1111); |
|
| 1440 | + | // A cheaper value goes before lower-numbered ones. |
|
| 1441 | + | try testing::expect(spilledOf(23, 1 << 9) == (1 << 9)); |
|
| 1442 | + | // The cheap values go in full, and then the lowest of the equal ones. |
|
| 1443 | + | try testing::expect(spilledOf(26, (1 << 7) | (1 << 5)) == ((1 << 7) | (1 << 5) | 0b11)); |
|
| 1444 | + | // Cheap values fewer than the excess are all spilled. |
|
| 1445 | + | try testing::expect(spilledOf(26, 1 << 25) == ((1 << 25) | 0b111)); |
|
| 1367 | 1446 | } |
|
| 1368 | 1447 | ||
| 1369 | 1448 | /// Unresolved calls preserve their placeholder instructions and report a symbol error. |
|
| 1370 | 1449 | @test unsafe fn testMissingCallSymbol() throws (testing::TestError) { |
|
| 1371 | 1450 | let mut arena = alloc::new(&mut ASSEMBLY_ARENA_STORAGE[..]); |
lib/std/arch/rv64/tests/bounds.rad
+21 -5
| 184 | 184 | }; |
|
| 185 | 185 | } |
|
| 186 | 186 | ||
| 187 | 187 | /// Generate code for each function in order. |
|
| 188 | 188 | unsafe fn generateAll(funcs: *mut [il::Fn], layouts: &[il::Layout]) throws (rv64::Error) { |
|
| 189 | + | try generateWith(funcs, layouts, labels::MAX_BLOCKS_PER_FN, labels::FUNC_TABLE_SIZE); |
|
| 190 | + | } |
|
| 191 | + | ||
| 192 | + | /// Generate code for each function in order, with label tables of the given sizes. |
|
| 193 | + | /// `funcTable` must be a power of two. Small tables keep the setup of a run short. |
|
| 194 | + | unsafe fn generateWith( |
|
| 195 | + | funcs: *mut [il::Fn], |
|
| 196 | + | layouts: &[il::Layout], |
|
| 197 | + | maxBlocks: u32, |
|
| 198 | + | funcTable: u32 |
|
| 199 | + | ) throws (rv64::Error) { |
|
| 189 | 200 | let mut arena = alloc::new(&mut MEMORY[..]); |
|
| 190 | - | let labelTables = try! tables(&mut arena); |
|
| 201 | + | let mut blockOffsets: *mut [i32] = &mut []; |
|
| 202 | + | try! blockOffsets.resize(maxBlocks, 0, &mut arena); |
|
| 203 | + | let mut funcEntries: *mut [dict::Entry] = &mut []; |
|
| 204 | + | try! funcEntries.resize(funcTable, dict::Entry { key: &[], value: 0 }, &mut arena); |
|
| 205 | + | let labelTables = labels::fresh(blockOffsets, funcEntries); |
|
| 191 | 206 | let mut scratch = alloc::new(&mut SHAPE_SCRATCH[..]); |
|
| 192 | 207 | let mut generator = try rv64::beginProgram( |
|
| 193 | 208 | rv64::ProgramOptions { |
|
| 194 | 209 | stack: rv64::StackCheck::Off, |
|
| 195 | 210 | entryPatch: rv64::EntryPatch::None, |
| 817 | 832 | ||
| 818 | 833 | /// Generate functions of random data operations, calls and jumps that pass many values, and |
|
| 819 | 834 | /// check that code generation accepts all of them. |
|
| 820 | 835 | @test unsafe fn randomFunctions() throws (testing::TestError) { |
|
| 821 | 836 | let mut random = Random { state: 12345 }; |
|
| 822 | - | for _ in 0 .. 300 { |
|
| 837 | + | for _ in 0 .. 100 { |
|
| 823 | 838 | let mut arena = alloc::new(&mut SHAPE_STORAGE[..]); |
|
| 824 | 839 | let mut blocks: *mut [il::Block] = &mut []; |
|
| 825 | 840 | let mut vals: *mut [il::Val] = &mut []; |
|
| 826 | 841 | let mut instrs: *mut [il::Instr] = &mut []; |
|
| 827 | 842 | let mut params: *mut [il::Param] = &mut []; |
|
| 828 | 843 | // Registers defined so far, which every later instruction can use. |
|
| 829 | 844 | let mut defined: u32 = 0; |
|
| 830 | - | // Fewer than 256 values are live, which is the most that the spill pass sorts. |
|
| 831 | - | let steps = 10 + next(&mut random, 40); |
|
| 845 | + | // More values than registers are live, so that the spill pass runs. Its cost grows |
|
| 846 | + | // steeply with the number of steps. |
|
| 847 | + | let steps = 30 + next(&mut random, 10); |
|
| 832 | 848 | for step in 0 .. steps { |
|
| 833 | 849 | let kind = next(&mut random, 10); |
|
| 834 | 850 | if defined < 2 or kind < 3 { |
|
| 835 | 851 | push( |
|
| 836 | 852 | &mut instrs, |
| 940 | 956 | &mut arena |
|
| 941 | 957 | ); |
|
| 942 | 958 | let mut funcs: *mut [il::Fn] = &mut []; |
|
| 943 | 959 | try! funcs.append(target(&mut arena), &mut arena); |
|
| 944 | 960 | try! funcs.append(voidFn("f", &blocks[..], &vals[..]), &mut arena); |
|
| 945 | - | try generateAll(funcs, &[]) catch { |
|
| 961 | + | try generateWith(funcs, &[], 64, 16) catch { |
|
| 946 | 962 | throw testing::TestError::Failed; |
|
| 947 | 963 | }; |
|
| 948 | 964 | } |
|
| 949 | 965 | } |
|
| 950 | 966 |
lib/std/lang/gen/regalloc/spill.rad
+63 -164
| 16 | 16 | //! |
|
| 17 | 17 | //! 2. Pressure analysis: walk instructions backwards, tracking live set. |
|
| 18 | 18 | //! |
|
| 19 | 19 | //! When `|live| > numRegs`: |
|
| 20 | 20 | //! |
|
| 21 | - | //! * Sort live values by cost (ascending). |
|
| 22 | - | //! * Mark lowest-cost values as spilled until pressure is acceptable. |
|
| 21 | + | //! * Mark the lowest-cost live values as spilled until pressure is acceptable. |
|
| 23 | 22 | //! |
|
| 24 | 23 | //! 3. Callee class: values live across a call need callee-saved registers. Walk again, |
|
| 25 | 24 | //! and when more of them are live together than there are such registers, mark the |
|
| 26 | 25 | //! lowest-cost ones as spilled. |
|
| 27 | 26 | //! |
| 41 | 40 | use std::lang::il; |
|
| 42 | 41 | use std::lang::alloc; |
|
| 43 | 42 | use std::lang::gen::bitset; |
|
| 44 | 43 | use std::lang::gen::regalloc::liveness; |
|
| 45 | 44 | ||
| 46 | - | /// Maximum number of candidates for spill sorting. |
|
| 47 | - | constant MAX_CANDIDATES: u32 = 256; |
|
| 48 | 45 | /// Maximum loop depth for cost weighting (2^10 = 1024). |
|
| 49 | 46 | constant MAX_LOOP_WEIGHT: u32 = 10; |
|
| 50 | 47 | ||
| 51 | 48 | /// Spill cost for a single SSA register. |
|
| 52 | 49 | record SpillCost: Copy { |
| 71 | 68 | info: SpillInfo, |
|
| 72 | 69 | /// Values that must be allocated in callee-saved registers. |
|
| 73 | 70 | calleeClass: bitset::Bitset, |
|
| 74 | 71 | } |
|
| 75 | 72 | ||
| 76 | - | /// Entry for cost sorting. |
|
| 77 | - | record CostEntry: Copy { |
|
| 78 | - | reg: u32, |
|
| 79 | - | cost: u32, |
|
| 80 | - | } |
|
| 81 | - | ||
| 82 | 73 | /// Visitor that adds the block weight to the use count of each register. |
|
| 83 | 74 | /// |
|
| 84 | 75 | /// The record owns the cost table for the whole analysis. `weight` is the |
|
| 85 | 76 | /// weight of the block being scanned. |
|
| 86 | 77 | record CountCtx { |
| 90 | 81 | weight: u32, |
|
| 91 | 82 | } |
|
| 92 | 83 | ||
| 93 | 84 | /// State of the walk that limits the callee-class values that are live together. |
|
| 94 | 85 | record ClassWalk { |
|
| 95 | - | /// Values that are live at the current point. |
|
| 86 | + | /// Values of `active` that are live at the current point. |
|
| 96 | 87 | live: bitset::Bitset, |
|
| 97 | 88 | /// Callee-class values that are not spilled. |
|
| 98 | 89 | active: bitset::Bitset, |
|
| 99 | - | /// Number of values that are in both sets. |
|
| 90 | + | /// Number of values in `live`. |
|
| 100 | 91 | count: u32, |
|
| 101 | 92 | } |
|
| 102 | 93 | ||
| 103 | 94 | /// Analyze a function and determine which values need spill slots. |
|
| 104 | 95 | /// The slots and sets are allocated from `a`. |
| 122 | 113 | }; |
|
| 123 | 114 | } |
|
| 124 | 115 | // Allocate cost array. |
|
| 125 | 116 | let mut costs: *mut [SpillCost] = &mut []; |
|
| 126 | 117 | try costs.resize(maxReg, SpillCost { defs: 0, uses: 0 }, a); |
|
| 127 | - | // Scratch entries for one pressure check. A check has at most one candidate |
|
| 128 | - | // per register and at most MAX_CANDIDATES candidates. |
|
| 129 | - | let candidateCount = maxReg if maxReg < MAX_CANDIDATES else MAX_CANDIDATES; |
|
| 130 | - | let mut candidates: *mut [CostEntry] = &mut []; |
|
| 131 | - | try candidates.resize(candidateCount, CostEntry { reg: 0, cost: 0 }, a); |
|
| 132 | 118 | // Phase 1: Calculate spill costs. |
|
| 133 | 119 | let mut counts = CountCtx { costs, weight: 0 }; |
|
| 134 | 120 | fillCosts(func, &mut counts); |
|
| 135 | 121 | ||
| 136 | 122 | // Phase 2: Find values that exceed register pressure. |
| 157 | 143 | if let dst = il::instrDst(instr) { |
|
| 158 | 144 | if not bitset::contains(&scratch, dst.n) { |
|
| 159 | 145 | set limit = numRegs - 1; |
|
| 160 | 146 | } |
|
| 161 | 147 | } |
|
| 162 | - | try limitPressure( |
|
| 163 | - | &mut scratch, &mut spilled, &counts.costs[..], limit, &mut candidates[..] |
|
| 164 | - | ); |
|
| 148 | + | limitPressure(&mut scratch, &mut spilled, &counts.costs[..], limit); |
|
| 165 | 149 | ||
| 166 | - | // Enforce cross-call pressure at call sites. |
|
| 167 | - | if il::isCall(instr) { |
|
| 168 | - | try limitCrossCallPressure( |
|
| 169 | - | &mut scratch, |
|
| 170 | - | &mut spilled, |
|
| 171 | - | &counts.costs[..], |
|
| 172 | - | &mut calleeClass, |
|
| 173 | - | numCalleeSaved, |
|
| 174 | - | il::instrDst(instr), |
|
| 175 | - | &mut candidates[..] |
|
| 176 | - | ); |
|
| 177 | - | } |
|
| 178 | 150 | // Remove definition from live set. |
|
| 179 | 151 | if let dst = il::instrDst(instr) { |
|
| 180 | 152 | bitset::clear(&mut scratch, dst.n); |
|
| 181 | 153 | } |
|
| 154 | + | // The values that are still live cross a call, so each of them needs a |
|
| 155 | + | // callee-saved register. Spill the cheapest of those that do not fit. |
|
| 156 | + | if il::isCall(instr) { |
|
| 157 | + | limitPressure(&mut scratch, &mut spilled, &counts.costs[..], numCalleeSaved); |
|
| 158 | + | bitset::union_(&mut calleeClass, &scratch); |
|
| 159 | + | } |
|
| 182 | 160 | // Add uses to live set. |
|
| 183 | 161 | il::forEachReg(func, instr, &mut scratch); |
|
| 184 | 162 | } |
|
| 185 | 163 | // Also limit pressure at block entry. A parameter that nothing uses is not in the live |
|
| 186 | 164 | // set, but the branches that enter the block write it, so it holds a register too. |
| 192 | 170 | } |
|
| 193 | 171 | let mut entryLimit: u32 = 0; |
|
| 194 | 172 | if unusedParams < numRegs { |
|
| 195 | 173 | set entryLimit = numRegs - unusedParams; |
|
| 196 | 174 | } |
|
| 197 | - | try limitPressure( |
|
| 198 | - | &mut scratch, &mut spilled, &counts.costs[..], entryLimit, &mut candidates[..] |
|
| 199 | - | ); |
|
| 175 | + | limitPressure(&mut scratch, &mut spilled, &counts.costs[..], entryLimit); |
|
| 200 | 176 | } |
|
| 201 | 177 | // Phase 3: Limit the callee-class values that are live at one point. Each call site keeps |
|
| 202 | 178 | // at most `numCalleeSaved` values across it, but the sets of different call sites can add |
|
| 203 | 179 | // up to more, and the values of two sites are live together only when their ranges |
|
| 204 | 180 | // overlap. Spill the cheapest of the values live together, so that assignment finds a |
| 227 | 203 | } |
|
| 228 | 204 | } |
|
| 229 | 205 | if bound <= numCalleeSaved { |
|
| 230 | 206 | continue; |
|
| 231 | 207 | } |
|
| 232 | - | bitset::copy(&mut walk.live, &live.liveOut[b]); |
|
| 233 | - | set walk.count = bitset::countCommon(&walk.live, &walk.active); |
|
| 208 | + | bitset::clearAll(&mut walk.live); |
|
| 209 | + | set walk.count = 0; |
|
| 210 | + | let mut it = bitset::iter(&live.liveOut[b]); |
|
| 211 | + | while let n = bitset::iterNext(&live.liveOut[b], &mut it) { |
|
| 212 | + | if bitset::contains(&walk.active, n) { |
|
| 213 | + | bitset::put(&mut walk.live, n); |
|
| 214 | + | set walk.count += 1; |
|
| 215 | + | } |
|
| 216 | + | } |
|
| 234 | 217 | let mut i = block.instrs.len; |
|
| 235 | 218 | while i > 0 { |
|
| 236 | 219 | set i -= 1; |
|
| 237 | 220 | let instr = block.instrs[i]; |
|
| 238 | - | try limitClassPressure( |
|
| 239 | - | &mut walk, &mut spilled, &counts.costs[..], numCalleeSaved, &mut candidates[..] |
|
| 240 | - | ); |
|
| 221 | + | limitClassPressure(&mut walk, &mut spilled, &counts.costs[..], numCalleeSaved); |
|
| 241 | 222 | if let dst = il::instrDst(instr) { |
|
| 242 | 223 | if bitset::contains(&walk.live, dst.n) { |
|
| 243 | 224 | bitset::clear(&mut walk.live, dst.n); |
|
| 244 | - | if bitset::contains(&walk.active, dst.n) { |
|
| 245 | - | set walk.count -= 1; |
|
| 246 | - | } |
|
| 225 | + | set walk.count -= 1; |
|
| 247 | 226 | } |
|
| 248 | 227 | } |
|
| 249 | 228 | il::forEachReg(func, instr, &mut walk); |
|
| 250 | 229 | } |
|
| 251 | - | try limitClassPressure( |
|
| 252 | - | &mut walk, &mut spilled, &counts.costs[..], numCalleeSaved, &mut candidates[..] |
|
| 253 | - | ); |
|
| 230 | + | limitClassPressure(&mut walk, &mut spilled, &counts.costs[..], numCalleeSaved); |
|
| 254 | 231 | } |
|
| 255 | 232 | } |
|
| 256 | 233 | // Phase 4: Assign stack slots to spilled values. |
|
| 257 | 234 | // Most functions have no spills, so the slot table is allocated only when needed. |
|
| 258 | 235 | let mut slots: *mut [i32] = &mut []; |
| 312 | 289 | set counts.costs[reg.n].uses += counts.weight; |
|
| 313 | 290 | } |
|
| 314 | 291 | } |
|
| 315 | 292 | ||
| 316 | 293 | instance il::RegVisitor for ClassWalk { |
|
| 317 | - | /// Add the register to the live set. |
|
| 294 | + | /// Add the register to the live set if it is in the active class. |
|
| 318 | 295 | fn (walk: &mut ClassWalk) visit(reg: il::Reg) { |
|
| 319 | - | if not bitset::contains(&walk.live, reg.n) { |
|
| 296 | + | if bitset::contains(&walk.active, reg.n) and not bitset::contains(&walk.live, reg.n) { |
|
| 320 | 297 | bitset::put(&mut walk.live, reg.n); |
|
| 321 | - | if bitset::contains(&walk.active, reg.n) { |
|
| 322 | - | set walk.count += 1; |
|
| 323 | - | } |
|
| 298 | + | set walk.count += 1; |
|
| 324 | 299 | } |
|
| 325 | 300 | } |
|
| 326 | 301 | } |
|
| 327 | 302 | ||
| 328 | 303 | instance il::RegVisitor for bitset::Bitset { |
| 330 | 305 | fn (bs: &mut bitset::Bitset) visit(reg: il::Reg) { |
|
| 331 | 306 | bitset::put(bs, reg.n); |
|
| 332 | 307 | } |
|
| 333 | 308 | } |
|
| 334 | 309 | ||
| 335 | - | /// Sort the first `n` candidates of `entries` by cost (ascending) using insertion |
|
| 336 | - | /// sort, then spill the cheapest `excess` values: set in `spilled`, clear in `source`. |
|
| 337 | - | fn spillCheapest( |
|
| 338 | - | entries: &mut [CostEntry], |
|
| 339 | - | n: u32, |
|
| 340 | - | excess: u32, |
|
| 341 | - | source: &mut bitset::Bitset, |
|
| 342 | - | spilled: &mut bitset::Bitset |
|
| 343 | - | ) { |
|
| 344 | - | // Insertion sort ascending by cost. |
|
| 345 | - | for i in 1 .. n { |
|
| 346 | - | let key = entries[i]; |
|
| 347 | - | let mut j: u32 = i; |
|
| 348 | - | while j > 0 and entries[j - 1].cost > key.cost { |
|
| 349 | - | set entries[j] = entries[j - 1]; |
|
| 350 | - | set j -= 1; |
|
| 351 | - | } |
|
| 352 | - | set entries[j] = key; |
|
| 353 | - | } |
|
| 354 | - | let toSpill = n if excess > n else excess; |
|
| 355 | - | for i in 0 .. toSpill { |
|
| 356 | - | bitset::put(spilled, entries[i].reg); |
|
| 357 | - | bitset::clear(source, entries[i].reg); |
|
| 358 | - | } |
|
| 310 | + | /// Cost of spilling a register. |
|
| 311 | + | fn costOf(cost: SpillCost) -> u32 { |
|
| 312 | + | return cost.defs + cost.uses; |
|
| 359 | 313 | } |
|
| 360 | 314 | ||
| 361 | - | /// Collect all values from a bitset into `entries` with their costs. |
|
| 362 | - | /// Returns the number of values collected. |
|
| 363 | - | fn collectCandidates(bs: &bitset::Bitset, costs: &[SpillCost], entries: &mut [CostEntry]) -> u32 |
|
| 364 | - | throws (alloc::AllocError) |
|
| 365 | - | { |
|
| 366 | - | let mut n: u32 = 0; |
|
| 367 | - | let mut it = bitset::iter(bs); |
|
| 368 | - | while let reg = bitset::iterNext(bs, &mut it) { |
|
| 369 | - | if n == MAX_CANDIDATES { |
|
| 370 | - | throw alloc::AllocError::OutOfMemory; |
|
| 371 | - | } |
|
| 372 | - | if reg < costs.len { |
|
| 373 | - | set entries[n] = CostEntry { reg, cost: costs[reg].defs + costs[reg].uses }; |
|
| 374 | - | set n += 1; |
|
| 315 | + | /// Spill the `excess` cheapest values of `live`: set them in `spilled` and clear them in |
|
| 316 | + | /// `live`. Among equal costs, the lowest register goes first. `live` holds at least |
|
| 317 | + | /// `excess` values, and every register of it is below `costs.len`. `excess` is usually one, |
|
| 318 | + | /// so each pick is one scan of `live`. |
|
| 319 | + | fn spillCheapest( |
|
| 320 | + | live: &mut bitset::Bitset, |
|
| 321 | + | spilled: &mut bitset::Bitset, |
|
| 322 | + | costs: &[SpillCost], |
|
| 323 | + | excess: u32 |
|
| 324 | + | ) { |
|
| 325 | + | for _ in 0 .. excess { |
|
| 326 | + | let mut it = bitset::iter(live); |
|
| 327 | + | let first = bitset::iterNext(live, &mut it) else { |
|
| 328 | + | panic "spillCheapest: fewer values than the excess"; |
|
| 329 | + | }; |
|
| 330 | + | let mut best = first; |
|
| 331 | + | let mut bestCost = costOf(costs[first]); |
|
| 332 | + | while let reg = bitset::iterNext(live, &mut it) { |
|
| 333 | + | let cost = costOf(costs[reg]); |
|
| 334 | + | if cost < bestCost { |
|
| 335 | + | set best = reg; |
|
| 336 | + | set bestCost = cost; |
|
| 337 | + | } |
|
| 375 | 338 | } |
|
| 339 | + | bitset::put(spilled, best); |
|
| 340 | + | bitset::clear(live, best); |
|
| 376 | 341 | } |
|
| 377 | - | return n; |
|
| 378 | 342 | } |
|
| 379 | 343 | ||
| 380 | - | /// Limit register pressure by marking low-cost values as spilled. |
|
| 344 | + | /// Limit the values of `live` to `limit` by marking the cheapest ones as spilled. |
|
| 381 | 345 | fn limitPressure( |
|
| 382 | 346 | live: &mut bitset::Bitset, |
|
| 383 | 347 | spilled: &mut bitset::Bitset, |
|
| 384 | 348 | costs: &[SpillCost], |
|
| 385 | - | numRegs: u32, |
|
| 386 | - | entries: &mut [CostEntry] |
|
| 387 | - | ) throws (alloc::AllocError) { |
|
| 349 | + | limit: u32 |
|
| 350 | + | ) { |
|
| 388 | 351 | let liveCount = bitset::count(live); |
|
| 389 | - | if liveCount <= numRegs { |
|
| 390 | - | return; |
|
| 352 | + | if liveCount > limit { |
|
| 353 | + | spillCheapest(live, spilled, costs, liveCount - limit); |
|
| 391 | 354 | } |
|
| 392 | - | let n = try collectCandidates(live, costs, entries); |
|
| 393 | - | spillCheapest(entries, n, liveCount - numRegs, live, spilled); |
|
| 394 | 355 | } |
|
| 395 | 356 | ||
| 396 | 357 | /// Limit the values of the callee class that are live together to `numCalleeSaved`, by marking |
|
| 397 | 358 | /// the cheapest ones as spilled and removing them from the walk. |
|
| 398 | 359 | fn limitClassPressure( |
|
| 399 | 360 | walk: &mut ClassWalk, |
|
| 400 | 361 | spilled: &mut bitset::Bitset, |
|
| 401 | 362 | costs: &[SpillCost], |
|
| 402 | - | numCalleeSaved: u32, |
|
| 403 | - | entries: &mut [CostEntry] |
|
| 404 | - | ) throws (alloc::AllocError) { |
|
| 363 | + | numCalleeSaved: u32 |
|
| 364 | + | ) { |
|
| 405 | 365 | if walk.count <= numCalleeSaved { |
|
| 406 | 366 | return; |
|
| 407 | 367 | } |
|
| 408 | - | let mut n: u32 = 0; |
|
| 409 | - | let mut it = bitset::iter(&walk.live); |
|
| 410 | - | while let reg = bitset::iterNext(&walk.live, &mut it) { |
|
| 411 | - | if reg < costs.len and bitset::contains(&walk.active, reg) { |
|
| 412 | - | if n == MAX_CANDIDATES { |
|
| 413 | - | throw alloc::AllocError::OutOfMemory; |
|
| 414 | - | } |
|
| 415 | - | set entries[n] = CostEntry { reg, cost: costs[reg].defs + costs[reg].uses }; |
|
| 416 | - | set n += 1; |
|
| 417 | - | } |
|
| 418 | - | } |
|
| 419 | - | spillCheapest(entries, n, walk.count - numCalleeSaved, &mut walk.live, spilled); |
|
| 368 | + | spillCheapest(&mut walk.live, spilled, costs, walk.count - numCalleeSaved); |
|
| 420 | 369 | bitset::subtract(&mut walk.active, spilled); |
|
| 421 | - | set walk.count = bitset::countCommon(&walk.live, &walk.active); |
|
| 422 | - | } |
|
| 423 | - | ||
| 424 | - | /// Check whether an SSA register is the destination of a call instruction. |
|
| 425 | - | fn isCallDst(callDst: ?il::Reg, n: u32) -> bool { |
|
| 426 | - | if let d = callDst { |
|
| 427 | - | return d.n == n; |
|
| 428 | - | } |
|
| 429 | - | return false; |
|
| 430 | - | } |
|
| 431 | - | ||
| 432 | - | /// Limit cross-call pressure by spilling values that exceed callee-saved capacity. |
|
| 433 | - | /// |
|
| 434 | - | /// At a call site, every live value must survive the call in a callee-saved |
|
| 435 | - | /// register. If the count exceeds `numCalleeSaved`, spill the cheapest |
|
| 436 | - | /// crossing values. |
|
| 437 | - | fn limitCrossCallPressure( |
|
| 438 | - | live: &mut bitset::Bitset, |
|
| 439 | - | spilled: &mut bitset::Bitset, |
|
| 440 | - | costs: &[SpillCost], |
|
| 441 | - | calleeClass: &mut bitset::Bitset, |
|
| 442 | - | numCalleeSaved: u32, |
|
| 443 | - | callDst: ?il::Reg, |
|
| 444 | - | entries: &mut [CostEntry] |
|
| 445 | - | ) throws (alloc::AllocError) { |
|
| 446 | - | // Collect crossing candidates: live values excluding the call destination. |
|
| 447 | - | let mut numCandidates: u32 = 0; |
|
| 448 | - | let mut it = bitset::iter(live); |
|
| 449 | - | while let n = bitset::iterNext(live, &mut it) { |
|
| 450 | - | if not isCallDst(callDst, n) and n < costs.len { |
|
| 451 | - | if numCandidates == MAX_CANDIDATES { |
|
| 452 | - | throw alloc::AllocError::OutOfMemory; |
|
| 453 | - | } |
|
| 454 | - | set entries[numCandidates] = CostEntry { |
|
| 455 | - | reg: n, |
|
| 456 | - | cost: costs[n].defs + costs[n].uses, |
|
| 457 | - | }; |
|
| 458 | - | set numCandidates += 1; |
|
| 459 | - | } |
|
| 460 | - | } |
|
| 461 | - | // Spill cheapest candidates if crossing count exceeds callee-saved capacity. |
|
| 462 | - | if numCandidates > numCalleeSaved { |
|
| 463 | - | spillCheapest(entries, numCandidates, numCandidates - numCalleeSaved, live, spilled); |
|
| 464 | - | } |
|
| 465 | - | // Mark crossing values that remain after spilling as callee-saved class. |
|
| 466 | - | let mut it2 = bitset::iter(live); |
|
| 467 | - | while let n = bitset::iterNext(live, &mut it2) { |
|
| 468 | - | if not isCallDst(callDst, n) { |
|
| 469 | - | bitset::put(calleeClass, n); |
|
| 470 | - | } |
|
| 471 | - | } |
|
| 370 | + | set walk.count = numCalleeSaved; |
|
| 472 | 371 | } |
|
| 473 | 372 | ||
| 474 | 373 | /// Check if a register is spilled. |
|
| 475 | 374 | export fn isSpilled(info: &SpillInfo, reg: il::Reg) -> bool { |
|
| 476 | 375 | if reg.n >= info.slots.len { |