lang: Reuse register analysis in native codegen

239afabe1f735ac9c2fd73063f950588514411cc5e2caa191f5da492831404c3
Register allocation scans instruction operands in each pass, and the
RV64 selector tries combination patterns for instructions that cannot
match.

Retain operand ranges and destinations per function, track live-register
counts during spilling, and reject impossible combination patterns
before reading payloads. Read binary RIL immediates with a fixed-width
cursor.

Matched-source self-builds use about 9% fewer warm instructions and 3%
fewer uncached instructions. Generated images remain byte-identical.

Assisted-by: Codex:gpt-6
Change-Id: I7fb25031555894b4a7f6f6d0fb7c1d04b38e9700
Alexis Sellier committed ago 1 parent 6215ce61
lib/std/arch/rv64/isel.rad +13 -3
1501 1501
1502 1502
/// Match adjacent expressions whose intermediate values each have one use.
1503 1503
/// The combined instruction is emitted at the first definition. All source
1504 1504
/// registers are still live there, and the final destination can be written.
1505 1505
fn combination(instrs: &[il::Instr], uses: &[u32]) -> ?Combined {
1506 -
    if let combined = rotation(instrs, uses) {
1507 -
        return combined;
1508 -
    }
1509 1506
    if instrs.len < 2 {
1510 1507
        return nil;
1511 1508
    }
1509 +
    match &instrs[0] {
1510 +
        case il::Instr::BinOp { .. } => {
1511 +
            if let combined = rotation(instrs, uses) {
1512 +
                return combined;
1513 +
            }
1514 +
        }
1515 +
        case il::Instr::UnOp { .. }, il::Instr::Zext { .. } => {}
1516 +
        else                                                => return nil,
1517 +
    }
1518 +
    match &instrs[1] {
1519 +
        case il::Instr::BinOp { .. }, il::Instr::UnOp { .. } => {}
1520 +
        else                                                 => return nil,
1521 +
    }
1512 1522
    let first = instrs[0];
1513 1523
    let second = instrs[1];
1514 1524
    if let case il::Instr::UnOp { op: il::UnOp::Not, typ, dst: temp, a: inverted } = first {
1515 1525
        if uses[temp.n] <> 1 {
1516 1526
            return nil;
lib/std/arch/rv64/tests.rad +18 -2
1444 1444
        bitset::put(&mut liveSet, i);
1445 1445
    }
1446 1446
    let mut out: *mut [bitset::Bitset] = &mut [];
1447 1447
    try! out.append(liveSet, arena);
1448 1448
    let live = regalloc::liveness::LiveInfo {
1449 -
        liveIn: &[], liveOut: out, defs: &[], uses: &[], order: &[0], blockCount: 1, maxReg: 257
1449 +
        operands: &[],
1450 +
        instructions: &[&[]],
1451 +
        liveIn: &[],
1452 +
        liveOut: out,
1453 +
        defs: &[],
1454 +
        uses: &[],
1455 +
        order: &[0],
1456 +
        blockCount: 1,
1457 +
        maxReg: 257,
1450 1458
    };
1451 1459
    let mut funcs: *mut [il::Fn] = &mut [];
1452 1460
    try! funcs.append(
1453 1461
        il::Fn {
1454 1462
            name: "pressure",
1502 1510
        }
1503 1511
    }
1504 1512
    let mut out: *mut [bitset::Bitset] = &mut [];
1505 1513
    try! out.append(liveSet, arena);
1506 1514
    let live = regalloc::liveness::LiveInfo {
1507 -
        liveIn: &[], liveOut: out, defs: &[], uses: &[], order: &[0], blockCount: 1, maxReg: count
1515 +
        operands: &[],
1516 +
        instructions: &[&[]],
1517 +
        liveIn: &[],
1518 +
        liveOut: out,
1519 +
        defs: &[],
1520 +
        uses: &[],
1521 +
        order: &[0],
1522 +
        blockCount: 1,
1523 +
        maxReg: count,
1508 1524
    };
1509 1525
    let mut blocks: *mut [il::Block] = &mut [];
1510 1526
    try! blocks.append(
1511 1527
        il::Block {
1512 1528
            label: il::BlockLabel { base: "entry", suffix: nil },
lib/std/lang/gen/regalloc/assign.rad +46 -60
8 8
//!
9 9
//! Blocks are visited in an order where each block follows its dominators, which is not the
10 10
//! order of the block list. A value is then assigned a register where it is defined, before
11 11
//! any block that reads it. Only a function parameter is assigned at a read.
12 12
13 -
use std::lang::il;
13 +
use std::arch::rv64;
14 14
use std::lang::alloc;
15 -
use std::mem::heap;
16 15
use std::lang::gen;
17 16
use std::lang::gen::bitset;
18 17
use std::lang::gen::regalloc::liveness;
19 18
use std::lang::gen::regalloc::spill;
20 -
use std::arch::rv64;
19 +
use std::lang::il;
20 +
use std::mem::heap;
21 21
22 22
/// Maximum number of active register mappings.
23 23
constant MAX_ACTIVE: u32 = 64;
24 24
/// Last-use index of a register without an operand use in its block. No instruction has it.
25 25
constant NO_USE: u32 = 0xffffffff;
41 41
    assignments: *[?gen::Reg],
42 42
    /// Bitmask of used callee-saved registers.
43 43
    usedCalleeSaved: u32,
44 44
}
45 45
46 -
/// Last operand-use index of each SSA register in the block being allocated.
47 -
/// It is the visitor that records the operands of each instruction.
48 -
record LastUse {
49 -
    /// Last operand-use index of each SSA register. Shared by all blocks of the function.
50 -
    indices: *mut [u32],
51 -
    /// Index of the instruction whose operands are being recorded.
52 -
    index: u32,
53 -
}
54 -
55 -
/// Register assignment state of one function. It is the visitor that
56 -
/// releases and allocates the registers of each instruction operand.
46 +
/// Register assignment state of one function.
47 +
/// Tracks active mappings and the last use of each instruction operand.
57 48
record AssignCtx {
58 49
    /// Register mapping at the current program point.
59 50
    current: RegMap,
60 51
    /// Physical registers in use at the current program point.
61 52
    usedRegs: bitset::Bitset,
62 53
    /// Values that must be allocated in callee-saved registers.
63 54
    crossCall: bitset::Bitset,
64 55
    /// Function parameters, which are defined at entry. Only these may be read before they
65 56
    /// have a register.
66 57
    params: bitset::Bitset,
67 -
    /// Last operand-use indices of the function.
68 -
    lastUse: LastUse,
58 +
    /// Last operand-use index of each SSA register in the current block.
59 +
    lastUses: *mut [u32],
69 60
    /// Physical register of each SSA register, `nil` until assigned.
70 61
    assignments: *mut [?gen::Reg],
71 62
    /// Live-out sets of the function, indexed by block.
72 63
    liveOut: *[bitset::Bitset],
73 64
    /// Spill decisions of the function.
134 125
    let mut ctx = AssignCtx {
135 126
        current: RegMap { virtRegs: [0; MAX_ACTIVE], physRegs: [gen::Reg(0); MAX_ACTIVE], n: 0 },
136 127
        usedRegs,
137 128
        crossCall: calleeClass,
138 129
        params,
139 -
        lastUse: LastUse { indices: lastUseIndices, index: 0 },
130 +
        lastUses: lastUseIndices,
140 131
        assignments,
141 132
        liveOut: live.liveOut,
142 133
        spillInfo,
143 134
        allocatable,
144 135
        calleeSaved: config.calleeSaved,
157 148
        // query this table, so every read is initialized by this scan.
158 149
        // Entries for other registers need not be cleared between blocks, except for
159 150
        // the registers that the block defines: those without an operand use stay
160 151
        // marked as unused, so that their registers are free again at once.
161 152
        for p in block.params {
162 -
            set ctx.lastUse.indices[p.value.n] = NO_USE;
153 +
            set ctx.lastUses[p.value.n] = NO_USE;
163 154
        }
164 -
        for instr in block.instrs {
165 -
            if let dst = il::instrDst(&instr) {
166 -
                set ctx.lastUse.indices[dst.n] = NO_USE;
155 +
        for i in 0 .. block.instrs.len {
156 +
            if let dst = live.instructions[b][i].dst {
157 +
                set ctx.lastUses[dst.n] = NO_USE;
167 158
            }
168 159
        }
169 -
        for instr, i in block.instrs {
170 -
            set ctx.lastUse.index = i;
171 -
            il::forEachReg(func, &instr, &mut ctx.lastUse);
160 +
        for i in 0 .. block.instrs.len {
161 +
            // Forward traversal leaves the last operand-use index.
162 +
            for reg in liveness::registers(live, b, i) {
163 +
                set ctx.lastUses[reg.n] = i;
164 +
            }
172 165
        }
173 166
        // Reset for new block.
174 167
        set ctx.current.n = 0;
175 168
        set ctx.blockIdx = b;
176 169
        bitset::clearAll(&mut ctx.usedRegs);
210 203
            if p.value.n < maxReg and isUnused(&ctx, p.value.n) {
211 204
                releaseReg(&mut ctx, p.value.n);
212 205
            }
213 206
        }
214 207
        // Process each instruction.
215 -
        for instr, i in block.instrs {
208 +
        for i in 0 .. block.instrs.len {
216 209
            set ctx.instrIdx = i;
217 -
            il::forEachReg(func, &instr, &mut ctx);
210 +
            for reg in liveness::registers(live, b, i) {
211 +
                visitUse(&mut ctx, reg);
212 +
            }
218 213
            if ctx.exhausted {
219 214
                throw alloc::AllocError::OutOfMemory;
220 215
            }
221 216
            // Allocate destination.
222 -
            if let dst = il::instrDst(&instr) {
217 +
            if let dst = live.instructions[b][i].dst {
223 218
                if dst.n < maxReg and not spill::isSpilled(&ctx.spillInfo, dst) {
224 219
                    set ctx.assignments[dst.n] = try allocateDef(&mut ctx, dst.n);
225 220
                    // A result that nothing uses must not hold its register.
226 221
                    if isUnused(&ctx, dst.n) {
227 222
                        releaseReg(&mut ctx, dst.n);
249 244
}
250 245
251 246
/// Whether a register that the current block defines has no use: no operand in the block
252 247
/// reads it, and it is not live out of the block.
253 248
fn isUnused(c: &AssignCtx, n: u32) -> bool {
254 -
    return c.lastUse.indices[n] == NO_USE and not bitset::contains(&c.liveOut[c.blockIdx], n);
249 +
    return c.lastUses[n] == NO_USE and not bitset::contains(&c.liveOut[c.blockIdx], n);
255 250
}
256 251
257 252
/// Free the physical register of a value that is no longer live.
258 253
fn releaseReg(c: &mut AssignCtx, n: u32) {
259 254
    if let phys = rmapRemove(&mut c.current, n) {
307 302
fn allocateDef(c: &mut AssignCtx, n: u32) -> gen::Reg throws (alloc::AllocError) {
308 303
    assert c.assignments[n] == nil, "allocateDef: value assigned twice";
309 304
    return try rallocReg(c, n);
310 305
}
311 306
312 -
instance il::RegVisitor for LastUse {
313 -
    /// Record the current index; forward traversal leaves the last operand use.
314 -
    fn (c: &mut LastUse) visit(reg: il::Reg) {
315 -
        set c.indices[reg.n] = c.index;
316 -
    }
317 -
}
318 -
319 -
instance il::RegVisitor for AssignCtx {
320 -
    /// Free operands with no later block use or live-out use, then allocate missing uses.
321 -
    fn (c: &mut AssignCtx) visit(reg: il::Reg) {
322 -
        if not (bitset::contains(&c.liveOut[c.blockIdx], reg.n)
323 -
            or c.lastUse.indices[reg.n] > c.instrIdx)
324 -
        {
325 -
            if let phys = rmapRemove(&mut c.current, reg.n) {
326 -
                bitset::clear(&mut c.usedRegs, *phys as u32);
327 -
            }
328 -
        }
329 -
        // Liveness sized the tables to one past the largest register of the function.
330 -
        assert reg.n < c.assignments.len, "visit: register out of bounds";
331 -
        if spill::isSpilled(&c.spillInfo, reg) {
332 -
            return; // Spilled values don't get physical registers.
333 -
        }
334 -
        if c.assignments[reg.n] == nil {
335 -
            let phys = try allocateUse(c, reg.n) catch {
336 -
                set c.exhausted = true;
337 -
                return;
338 -
            };
339 -
            set c.assignments[reg.n] = phys;
340 -
        }
341 -
    }
342 -
}
343 -
344 307
/// Find physical register for a virtual register in RegMap.
345 308
fn rmapFind(rmap: &RegMap, virtReg: u32) -> ?gen::Reg {
346 309
    for i in 0 .. rmap.n {
347 310
        if rmap.virtRegs[i] == virtReg {
348 311
            return rmap.physRegs[i];
376 339
            return phys;
377 340
        }
378 341
    }
379 342
    return nil;
380 343
}
344 +
345 +
/// Free operands with no later block use or live-out use, then allocate missing uses.
346 +
fn visitUse(c: &mut AssignCtx, reg: il::Reg) {
347 +
    if not (bitset::contains(&c.liveOut[c.blockIdx], reg.n)
348 +
        or c.lastUses[reg.n] > c.instrIdx)
349 +
    {
350 +
        if let phys = rmapRemove(&mut c.current, reg.n) {
351 +
            bitset::clear(&mut c.usedRegs, *phys as u32);
352 +
        }
353 +
    }
354 +
    // Liveness sized the tables to one past the largest register of the function.
355 +
    assert reg.n < c.assignments.len, "visit: register out of bounds";
356 +
    if spill::isSpilled(&c.spillInfo, reg) {
357 +
        return; // Spilled values don't get physical registers.
358 +
    }
359 +
    if c.assignments[reg.n] == nil {
360 +
        let phys = try allocateUse(c, reg.n) catch {
361 +
            set c.exhausted = true;
362 +
            return;
363 +
        };
364 +
        set c.assignments[reg.n] = phys;
365 +
    }
366 +
}
lib/std/lang/gen/regalloc/liveness.rad +86 -22
25 25
//!   let live = liveness::analyze(func, a);
26 26
//!   if not liveness::hasLaterUse(&live, func, blockIdx, instrIdx, reg) {
27 27
//!       // `reg` dies at this instruction.
28 28
//!   }
29 29
30 -
use std::mem;
31 -
use std::lang::il;
32 30
use std::lang::alloc;
33 -
use std::mem::heap;
34 31
use std::lang::gen::bitset;
32 +
use std::lang::il;
33 +
use std::mem;
34 +
use std::mem::heap;
35 35
36 36
/// Maximum number of SSA registers supported.
37 37
export constant MAX_SSA_REGS: u32 = 8192;
38 38
39 39
/// Liveness information for a function.
40 40
export record LiveInfo: Copy {
41 +
    /// Register operands in instruction order.
42 +
    operands: *[il::Reg],
43 +
    /// Destinations and operand ranges, indexed by block and instruction.
44 +
    instructions: *[*[Registers]],
41 45
    /// Per-block live-in sets (indexed by block index).
42 46
    liveIn: *[bitset::Bitset],
43 47
    /// Per-block live-out sets (indexed by block index).
44 48
    liveOut: *[bitset::Bitset],
45 49
    /// Per-block defs sets (registers defined in block).
54 58
    blockCount: u32,
55 59
    /// Maximum register number used.
56 60
    maxReg: u32,
57 61
}
58 62
63 +
/// Registers read and written by one instruction.
64 +
export record Registers: Copy {
65 +
    /// Destination register, if the instruction defines one.
66 +
    dst: ?il::Reg,
67 +
    /// Range of register reads in the function operand table.
68 +
    uses: il::ArgRange,
69 +
}
70 +
59 71
/// Visitor that finds the register count of a function.
60 72
record RegCount {
61 73
    /// One past the largest register number visited, as a 64-bit count.
62 74
    count: u64,
75 +
    /// Number of operand register reads, before the allocation bound is checked.
76 +
    uses: u64,
77 +
}
78 +
79 +
/// Register reads collected into a bounded function-wide table.
80 +
record Operands {
81 +
    /// Storage for register reads.
82 +
    values: *mut [il::Reg],
83 +
    /// Number of register reads written.
84 +
    used: u32,
85 +
}
86 +
87 +
instance il::RegVisitor for Operands {
88 +
    /// Append a register to the pre-sized table.
89 +
    fn (o: &mut Operands) visit(reg: il::Reg) {
90 +
        set o.values[o.used] = reg;
91 +
        set o.used += 1;
92 +
    }
63 93
}
64 94
65 95
/// Defs and uses sets of every block, and the block whose instructions are visited.
66 96
record DefsUses {
67 97
    /// Per-block defs sets (registers defined in block).
78 108
    throws (alloc::AllocError)
79 109
{
80 110
    let blockCount = func.blocks.len;
81 111
    if blockCount == 0 {
82 112
        return LiveInfo {
113 +
            operands: &[],
114 +
            instructions: &[],
83 115
            liveIn: &mut [],
84 116
            liveOut: &mut [],
85 117
            defs: &mut [],
86 118
            uses: &mut [],
87 119
            order: &[],
88 120
            blockCount: 0,
89 121
            maxReg: 0,
90 122
        };
91 123
    }
92 124
    // Find max register number.
93 -
    let mut counter = RegCount { count: 0 };
125 +
    let mut counter = RegCount { count: 0, uses: 0 };
94 126
    for p in func.params {
95 127
        countRegister(p.value, &mut counter);
96 128
    }
97 -
    for b in 0 .. blockCount {
98 -
        let block = &func.blocks[b];
129 +
    for block in func.blocks {
99 130
        for p in block.params {
100 131
            countRegister(p.value, &mut counter);
101 132
        }
102 133
        for instr in block.instrs {
103 134
            il::forEachReg(func, &instr, &mut counter);
104 135
            if let dst = il::instrDst(&instr) {
105 136
                countRegister(dst, &mut counter);
106 137
            }
107 138
        }
108 139
    }
109 -
    if counter.count > MAX_SSA_REGS as u64 {
140 +
    if counter.count > MAX_SSA_REGS as u64 or counter.uses > mem::U32_MAX as u64 {
110 141
        throw alloc::AllocError::OutOfMemory;
111 142
    }
112 143
    let maxReg = counter.count as u32;
144 +
    let mut values: *mut [il::Reg] = &mut [];
145 +
    try values.resize(counter.uses as u32, il::Reg { n: 0 }, a);
146 +
    let mut operands = Operands { values, used: 0 };
147 +
    let mut instructions: *mut [*[Registers]] = &mut [];
148 +
    try instructions.reserve(blockCount, a);
149 +
    for block in func.blocks {
150 +
        let mut registers: *mut [Registers] = &mut [];
151 +
        try registers.reserve(block.instrs.len, a);
152 +
        for instr in block.instrs {
153 +
            let start = operands.used;
154 +
            il::forEachReg(func, &instr, &mut operands);
155 +
            try registers.append(
156 +
                Registers {
157 +
                    dst: il::instrDst(&instr),
158 +
                    uses: il::ArgRange { start, len: operands.used - start },
159 +
                },
160 +
                a
161 +
            );
162 +
        }
163 +
        try instructions.append(&registers[..], a);
164 +
    }
165 +
    let case Operands { values: operandValues, used: _ } = operands
166 +
        else panic "analyze: operand table required";
113 167
168 +
    let operandReads: *[il::Reg] = &operandValues[..];
114 169
    // Allocate per-block bitsets.
115 170
    let mut liveIn = try allocateSets(a, blockCount, maxReg);
116 171
    let mut liveOut = try allocateSets(a, blockCount, maxReg);
117 172
    let defSets = try allocateSets(a, blockCount, maxReg);
118 173
    let useSets = try allocateSets(a, blockCount, maxReg);
119 174
120 175
    // Compute local defs and uses for each block.
121 176
    let mut localSets = DefsUses { defs: defSets, uses: useSets, block: 0 };
122 177
    for b in 0 .. blockCount {
123 178
        set localSets.block = b;
124 -
        computeLocalDefsUses(func, &func.blocks[b], &mut localSets);
179 +
        computeLocalDefsUses(&func.blocks[b], instructions[b], operandReads, &mut localSets);
125 180
    }
126 181
    let order = try reversePostorder(func, a);
127 182
    // Live sets grow monotonically from empty sets; no scratch set is needed.
128 183
    let mut changed = true;
129 184
147 202
        }
148 203
    }
149 204
    let case DefsUses { defs, uses, block: _ } = localSets else panic "analyze: local sets missing";
150 205
151 206
    return LiveInfo {
207 +
        operands: operandReads,
208 +
        instructions: &instructions[..],
152 209
        liveIn,
153 210
        liveOut,
154 211
        defs,
155 212
        uses,
156 213
        order,
227 284
    }
228 285
    return sets;
229 286
}
230 287
231 288
/// Compute local defs and uses for the block that `sets` currently selects.
232 -
fn computeLocalDefsUses(func: *il::Fn, block: *il::Block, sets: &mut DefsUses) {
289 +
fn computeLocalDefsUses(
290 +
    block: *il::Block,
291 +
    instructions: *[Registers],
292 +
    operands: *[il::Reg],
293 +
    sets: &mut DefsUses
294 +
) {
233 295
    for p in block.params {
234 296
        bitset::put(&mut sets.defs[sets.block], p.value.n);
235 297
    }
236 -
    for instr in block.instrs {
237 -
        il::forEachReg(func, &instr, sets);
238 -
239 -
        if let dst = il::instrDst(&instr) {
240 -
            bitset::put(&mut sets.defs[sets.block], dst.n);
298 +
    for instr in instructions {
299 +
        // Record a use of a register that no earlier instruction of the block defines.
300 +
        for reg in &operands[instr.uses.start .. instr.uses.start + instr.uses.len] {
301 +
            if not bitset::contains(&sets.defs[sets.block], reg.n) {
302 +
                bitset::put(&mut sets.uses[sets.block], reg.n);
303 +
            }
241 304
        }
242 -
    }
243 -
}
244 -
245 -
instance il::RegVisitor for DefsUses {
246 -
    /// Record a use of a register that no earlier instruction of the block defines.
247 -
    fn (sets: &mut DefsUses) visit(reg: il::Reg) {
248 -
        if not bitset::contains(&sets.defs[sets.block], reg.n) {
249 -
            bitset::put(&mut sets.uses[sets.block], reg.n);
305 +
        if let dst = instr.dst {
306 +
            bitset::put(&mut sets.defs[sets.block], dst.n);
250 307
        }
251 308
    }
252 309
}
253 310
254 311
/// Include a register in the required bitset size.
262 319
263 320
instance il::RegVisitor for RegCount {
264 321
    /// Include the register in the required bitset size.
265 322
    fn (c: &mut RegCount) visit(reg: il::Reg) {
266 323
        countRegister(reg, c);
324 +
        set c.uses += 1;
267 325
    }
268 326
}
269 327
270 328
/// Add the live-in sets of the successors of block `b` to its live-out set.
271 329
fn addSuccessorLiveIn(
290 348
            return true;
291 349
        }
292 350
    }
293 351
    return false;
294 352
}
353 +
354 +
/// Register reads of one instruction, in operand order.
355 +
export fn registers(info: &LiveInfo, block: u32, instr: u32) -> *[il::Reg] {
356 +
    let range = info.instructions[block][instr].uses;
357 +
    return &info.operands[range.start .. range.start + range.len];
358 +
}
lib/std/lang/gen/regalloc/spill.rad +61 -49
35 35
//!
36 36
//! The result also holds the callee-class set: values live across a call that
37 37
//! must use callee-saved registers. Assignment needs it, but instruction
38 38
//! selection does not.
39 39
40 -
use std::lang::il;
41 40
use std::lang::alloc;
42 -
use std::mem::heap;
43 41
use std::lang::gen::bitset;
44 42
use std::lang::gen::regalloc::liveness;
43 +
use std::lang::il;
44 +
use std::mem::heap;
45 45
46 46
/// Maximum loop depth for cost weighting (2^10 = 1024).
47 47
constant MAX_LOOP_WEIGHT: u32 = 10;
48 48
49 49
/// Spill cost for a single SSA register.
69 69
    info: SpillInfo,
70 70
    /// Values that must be allocated in callee-saved registers.
71 71
    calleeClass: bitset::Bitset,
72 72
}
73 73
74 -
/// Visitor that adds the block weight to the use count of each register.
74 +
/// Spill costs and the weight of the block being scanned.
75 75
///
76 76
/// The record owns the cost table for the whole analysis. `weight` is the
77 77
/// weight of the block being scanned.
78 78
record CountCtx {
79 79
    /// Spill cost of each SSA register.
80 80
    costs: *mut [SpillCost],
81 81
    /// Weight of the block being scanned.
82 82
    weight: u32,
83 83
}
84 84
85 +
/// Live values and their count in the backward pressure walk.
86 +
record Pressure {
87 +
    /// Values that are live at the current instruction.
88 +
    live: bitset::Bitset,
89 +
    /// Number of values in the live set.
90 +
    count: u32,
91 +
}
92 +
85 93
/// State of the walk that limits the callee-class values that are live together.
86 94
record ClassWalk {
87 95
    /// Values of `active` that are live at the current point.
88 96
    live: bitset::Bitset,
89 97
    /// Callee-class values that are not spilled.
116 124
    // Allocate cost array.
117 125
    let mut costs: *mut [SpillCost] = &mut [];
118 126
    try costs.resize(maxReg, SpillCost { defs: 0, uses: 0 }, a);
119 127
    // Phase 1: Calculate spill costs.
120 128
    let mut counts = CountCtx { costs, weight: 0 };
121 -
    fillCosts(func, &mut counts);
129 +
    fillCosts(func, live, &mut counts);
122 130
123 131
    // Phase 2: Find values that exceed register pressure.
124 132
    let mut spilled = try bitset::allocate(a, maxReg);
125 133
    let mut calleeClass = try bitset::allocate(a, maxReg);
126 -
    let mut scratch = try bitset::allocate(a, maxReg);
134 +
    let mut scratch = Pressure { live: try bitset::allocate(a, maxReg), count: 0 };
127 135
128 136
    for b in 0 .. func.blocks.len {
129 137
        let block = &func.blocks[b];
130 138
131 139
        // Start with live-out set.
132 -
        bitset::copy(&mut scratch, &live.liveOut[b]);
140 +
        bitset::copy(&mut scratch.live, &live.liveOut[b]);
141 +
        set scratch.count = bitset::count(&scratch.live);
133 142
134 143
        // Walk instructions backwards.
135 144
        let mut i = block.instrs.len;
136 145
        while i > 0 {
137 146
            set i -= 1;
138 147
            let instr = &block.instrs[i];
139 148
140 149
            // Limit register pressure before processing this instruction. A result that
141 150
            // nothing uses is not in the live set, but it needs a register while the
142 151
            // instruction runs, so one register stays free for it.
152 +
            let dst = live.instructions[b][i].dst;
143 153
            let mut limit = numRegs;
144 -
            if let dst = il::instrDst(instr) {
145 -
                if not bitset::contains(&scratch, dst.n) {
154 +
            if let dst = dst {
155 +
                if not bitset::contains(&scratch.live, dst.n) {
146 156
                    set limit = numRegs - 1;
147 157
                }
148 158
            }
149 159
            limitPressure(&mut scratch, &mut spilled, &counts.costs[..], limit);
150 160
151 161
            // Remove definition from live set.
152 -
            if let dst = il::instrDst(instr) {
153 -
                bitset::clear(&mut scratch, dst.n);
162 +
            if let dst = dst {
163 +
                if bitset::contains(&scratch.live, dst.n) {
164 +
                    bitset::clear(&mut scratch.live, dst.n);
165 +
                    set scratch.count -= 1;
166 +
                }
154 167
            }
155 168
            // The values that are still live cross a call, so each of them needs a
156 169
            // callee-saved register. Spill the cheapest of those that do not fit.
157 170
            if il::isCall(instr) {
158 171
                limitPressure(&mut scratch, &mut spilled, &counts.costs[..], numCalleeSaved);
159 -
                bitset::union_(&mut calleeClass, &scratch);
172 +
                bitset::union_(&mut calleeClass, &scratch.live);
173 +
            }
174 +
            // Count a register when its first use enters the live set.
175 +
            for reg in liveness::registers(live, b, i) {
176 +
                if not bitset::contains(&scratch.live, reg.n) {
177 +
                    bitset::put(&mut scratch.live, reg.n);
178 +
                    set scratch.count += 1;
179 +
                }
160 180
            }
161 -
            // Add uses to live set.
162 -
            il::forEachReg(func, instr, &mut scratch);
163 181
        }
164 182
        // Also limit pressure at block entry. A parameter that nothing uses is not in the live
165 183
        // set, but the branches that enter the block write it, so it holds a register too.
166 184
        let mut unusedParams: u32 = 0;
167 185
        for p in block.params {
168 -
            if not bitset::contains(&scratch, p.value.n) {
186 +
            if not bitset::contains(&scratch.live, p.value.n) {
169 187
                set unusedParams += 1;
170 188
            }
171 189
        }
172 190
        let mut entryLimit: u32 = 0;
173 191
        if unusedParams < numRegs {
174 192
            set entryLimit = numRegs - unusedParams;
175 193
        }
176 194
        limitPressure(&mut scratch, &mut spilled, &counts.costs[..], entryLimit);
177 195
    }
196 +
    let case Pressure { live: scratchLive, count: _ } = scratch
197 +
        else panic "analyze: pressure walk required";
178 198
    // Phase 3: Limit the callee-class values that are live at one point. Each call site keeps
179 199
    // at most `numCalleeSaved` values across it, but the sets of different call sites can add
180 200
    // up to more, and the values of two sites are live together only when their ranges
181 201
    // overlap. Spill the cheapest of the values live together, so that assignment finds a
182 202
    // callee-saved register for each of them. This needs a second walk, since a value is known
183 203
    // to be in the class only after the first walk has reached its call.
184 204
    if bitset::count(&calleeClass) > numCalleeSaved {
185 205
        let mut active = try bitset::allocate(a, maxReg);
186 206
        bitset::copy(&mut active, &calleeClass);
187 207
        bitset::subtract(&mut active, &spilled);
188 -
        let mut walk = ClassWalk { live: scratch, active, count: 0 };
208 +
        let mut walk = ClassWalk { live: scratchLive, active, count: 0 };
189 209
        for b in 0 .. func.blocks.len {
190 210
            let block = &func.blocks[b];
191 211
            // A value that is live inside the block is live into it or defined by it, so
192 212
            // these bound the values that are live together. Most blocks are within the limit.
193 213
            let mut bound = bitset::countCommon(&live.liveIn[b], &walk.active);
194 214
            for p in block.params {
195 215
                if bitset::contains(&walk.active, p.value.n) {
196 216
                    set bound += 1;
197 217
                }
198 218
            }
199 -
            for instr in block.instrs {
200 -
                if let dst = il::instrDst(&instr) {
219 +
            for i in 0 .. block.instrs.len {
220 +
                if let dst = live.instructions[b][i].dst {
201 221
                    if bitset::contains(&walk.active, dst.n) {
202 222
                        set bound += 1;
203 223
                    }
204 224
                }
205 225
            }
216 236
                }
217 237
            }
218 238
            let mut i = block.instrs.len;
219 239
            while i > 0 {
220 240
                set i -= 1;
221 -
                let instr = &block.instrs[i];
222 241
                limitClassPressure(&mut walk, &mut spilled, &counts.costs[..], numCalleeSaved);
223 -
                if let dst = il::instrDst(instr) {
242 +
                if let dst = live.instructions[b][i].dst {
224 243
                    if bitset::contains(&walk.live, dst.n) {
225 244
                        bitset::clear(&mut walk.live, dst.n);
226 245
                        set walk.count -= 1;
227 246
                    }
228 247
                }
229 -
                il::forEachReg(func, instr, &mut walk);
248 +
                for reg in liveness::registers(live, b, i) {
249 +
                    // Add the register to the live set if it is in the active class.
250 +
                    if bitset::contains(&walk.active, reg.n)
251 +
                        and not bitset::contains(&walk.live, reg.n)
252 +
                    {
253 +
                        bitset::put(&mut walk.live, reg.n);
254 +
                        set walk.count += 1;
255 +
                    }
256 +
                }
230 257
            }
231 258
            limitClassPressure(&mut walk, &mut spilled, &counts.costs[..], numCalleeSaved);
232 259
        }
233 260
    }
234 261
    // Phase 4: Assign stack slots to spilled values.
249 276
        calleeClass,
250 277
    };
251 278
}
252 279
253 280
/// Calculate spill costs for all registers, weighted by loop depth.
254 -
fn fillCosts(func: *il::Fn, counts: &mut CountCtx) {
281 +
fn fillCosts(func: *il::Fn, live: &liveness::LiveInfo, counts: &mut CountCtx) {
255 282
    for b in 0 .. func.blocks.len {
256 283
        let block = &func.blocks[b];
257 284
258 285
        // Exponential weight for loop depth, capped to avoid overflow.
259 286
        let depth = MAX_LOOP_WEIGHT if block.loopDepth > MAX_LOOP_WEIGHT else block.loopDepth;
265 292
            if p.value.n < counts.costs.len {
266 293
                set counts.costs[p.value.n].defs += weight;
267 294
            }
268 295
        }
269 296
        // Count instruction defs and uses.
270 -
        for instr in block.instrs {
297 +
        for i in 0 .. block.instrs.len {
271 298
            // Count definition.
272 -
            if let dst = il::instrDst(&instr) {
299 +
            if let dst = live.instructions[b][i].dst {
273 300
                if dst.n < counts.costs.len {
274 301
                    set counts.costs[dst.n].defs += weight;
275 302
                }
276 303
            }
277 -
            // Count uses.
278 -
            il::forEachReg(func, &instr, counts);
279 -
        }
280 -
    }
281 -
}
282 -
283 -
instance il::RegVisitor for CountCtx {
284 -
    /// Add the block weight to the register use count.
285 -
    fn (counts: &mut CountCtx) visit(reg: il::Reg) {
286 -
        // Liveness sized the tables to one past the largest register of the function.
287 -
        assert reg.n < counts.costs.len, "visit: register out of bounds";
288 -
        set counts.costs[reg.n].uses += counts.weight;
289 -
    }
290 -
}
291 -
292 -
instance il::RegVisitor for ClassWalk {
293 -
    /// Add the register to the live set if it is in the active class.
294 -
    fn (walk: &mut ClassWalk) visit(reg: il::Reg) {
295 -
        if bitset::contains(&walk.active, reg.n) and not bitset::contains(&walk.live, reg.n) {
296 -
            bitset::put(&mut walk.live, reg.n);
297 -
            set walk.count += 1;
304 +
            // Add the block weight to the use count of each register.
305 +
            for reg in liveness::registers(live, b, i) {
306 +
                if reg.n < counts.costs.len {
307 +
                    set counts.costs[reg.n].uses += counts.weight;
308 +
                }
309 +
            }
298 310
        }
299 311
    }
300 312
}
301 313
302 314
instance il::RegVisitor for bitset::Bitset {
338 350
        bitset::put(spilled, best);
339 351
        bitset::clear(live, best);
340 352
    }
341 353
}
342 354
343 -
/// Limit the values of `live` to `limit` by marking the cheapest ones as spilled.
355 +
/// Limit the live set to `limit` by marking the cheapest values as spilled.
344 356
fn limitPressure(
345 -
    live: &mut bitset::Bitset,
357 +
    pressure: &mut Pressure,
346 358
    spilled: &mut bitset::Bitset,
347 359
    costs: &[SpillCost],
348 360
    limit: u32
349 361
) {
350 -
    let liveCount = bitset::count(live);
351 -
    if liveCount > limit {
352 -
        spillCheapest(live, spilled, costs, liveCount - limit);
362 +
    if pressure.count > limit {
363 +
        spillCheapest(&mut pressure.live, spilled, costs, pressure.count - limit);
364 +
        set pressure.count = limit;
353 365
    }
354 366
}
355 367
356 368
/// Limit the values of the callee class that are live together to `numCalleeSaved`, by marking
357 369
/// the cheapest ones as spilled and removing them from the walk.
lib/std/lang/il/binary/reader.rad +11 -1
70 70
    let value = mem::load32Le(input.wire, input.offset) as u64;
71 71
    set input.offset += 4;
72 72
    return value;
73 73
}
74 74
75 +
/// Read a little-endian unsigned 64-bit integer.
76 +
fn (input: &mut Reader['wire]) doubleWord() -> u64 throws (binary::Error) {
77 +
    if input.wire.len - input.offset < 8 {
78 +
        throw binary::Error::Truncated;
79 +
    }
80 +
    let value = mem::load64Le(input.wire, input.offset);
81 +
    set input.offset += 8;
82 +
    return value;
83 +
}
84 +
75 85
/// Read an unsigned integer with width 1, 2, 4, or 8.
76 86
export fn (input: &mut Reader['wire]) integer(width: u32) -> u64 throws (binary::Error) {
77 87
    if width <> 1 and width <> 2 and width <> 4 and width <> 8 {
78 88
        throw binary::Error::Invalid;
79 89
    }
314 324
/// Read a tagged value with checked register and symbol indices.
315 325
export fn (input: &mut Reader['wire]) val() -> il::Val throws (binary::Error) {
316 326
    let tag = try input.byte() as u8;
317 327
    match tag {
318 328
        case super::VALUE_REG     => return il::Val::Reg(try input.reg()),
319 -
        case super::VALUE_IMM     => return il::Val::Imm(try input.integer(8) as i64),
329 +
        case super::VALUE_IMM     => return il::Val::Imm(try input.doubleWord() as i64),
320 330
        case super::VALUE_DATASYM => return il::Val::DataSym(try input.symbol()),
321 331
        case super::VALUE_FNADDR  => return il::Val::FnAddr(try input.symbol()),
322 332
        case super::VALUE_UNDEF   => return il::Val::Undef,
323 333
        else                      => throw binary::Error::Invalid,
324 334
    }