radiance · Radiance self-hosting compiler

compiler/ lib/ examples/ std/ arch/ char/ collections/ graph/ lang/ alloc/ ast/ gen/ bitset/ regalloc/ liveness/ assign.rad 11.7 KiB flow.rad 4.1 KiB liveness.rad 9.0 KiB spill.rad 12.4 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.9 KiB gen.rad 513 B il.rad 20.4 KiB lower.rad 321.7 KiB module.rad 17.3 KiB package.rad 1.3 KiB parser.rad 92.2 KiB resolver.rad 511.1 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 graph.rad 4.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 299 B scripts/ seed/ sublime/ test/ vim/ .gitignore 336 B .gitsigners 112 B CELL_PERMISSIONS 6.8 KiB 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 808 B

lib/std/lang/gen/regalloc/assign.rad 11.7 KiB raw

//! Register assignment.
//!
//! This pass assigns physical registers to SSA values. It runs after spilling
//! has ensured register pressure never exceeds available registers.
//!
//! The IL is not modified. Instead, a mapping from SSA registers to physical
//! registers is produced for use by instruction selection.

use std::lang::il;
use std::lang::il::published;
use std::lang::alloc;
use std::lang::gen;
use std::lang::gen::bitset;
use std::lang::gen::regalloc::liveness;
use std::lang::gen::regalloc::spill;

/// Maximum number of active register mappings.
constant MAX_ACTIVE: u32 = 64;

/// Register mapping at a program point.
/// Maps SSA registers to physical registers.
export record RegMap: 'scratch {
    /// SSA (virtual) registers that have mappings.
    virtRegs: &'scratch mut [u32],
    /// Physical register for each virtual register.
    physRegs: &'scratch mut [gen::Reg],
    /// Number of active mappings.
    n: u32,
}

/// Register assignment result, per function.
export record AssignInfo: 'scratch + Copy {
    /// SSA register -> physical register mapping.
    assignments: &'scratch [?gen::Reg],
    /// Bitmask of used callee-saved registers.
    usedCalleeSaved: u32,
}

/// Register state for scanning one block's instructions.
record InstrCtx: 'scratch + 'step where 'scratch: 'step {
    current: &'step mut RegMap 'scratch,
    usedRegs: &'step mut [u32],
    /// Last operand-use index for each register used in the current block.
    lastUse: &'step mut [u32],
    live: &'step liveness::LiveInfo 'scratch,
    blockIdx: u32,
    instrIdx: u32,
    allocatable: *[gen::Reg],
    calleeSaved: *[gen::Reg],
    assignments: &'step mut [?gen::Reg],
    spillInfo: &'step spill::SpillInfo 'scratch,
}

/// Compute register assignment.
export fn assign 'input 'scratch (
    func: &published::Function 'input,
    live: &liveness::LiveInfo 'scratch,
    spillInfo: &spill::SpillInfo 'scratch,
    config: &super::TargetConfig,
    storage: &Session 'scratch
) -> AssignInfo 'scratch throws (alloc::AllocError) {
    return try assignTables(func.params, func.blocks, live, spillInfo, config, storage);
}

/// Allocate register mappings for borrowed function parameter and block tables.
fn assignTables 'input 'scratch (
    params: &[il::Param],
    blocks: &[published::Block 'input],
    live: &liveness::LiveInfo 'scratch,
    spillInfo: &spill::SpillInfo 'scratch,
    config: &super::TargetConfig,
    storage: &Session 'scratch,
) -> AssignInfo 'scratch throws (alloc::AllocError) {
    let maxReg = live.maxReg;
    let blockCount = blocks.len;
    let allocatable = config.allocatable;

    if maxReg == 0 or blockCount == 0 {
        return AssignInfo 'scratch {
            assignments: try storage.fill(nil as ?gen::Reg, 0),
            usedCalleeSaved: 0,
        };
    }

    // Allocate output structures.
    let assignments = try storage.fill(nil as ?gen::Reg, maxReg);
    // Pre-assign function parameters to argument registers.
    // Cross-call params are NOT pre-assigned here; they will be allocated
    // to callee-saved registers by the normal path, and isel emits moves
    // from the arg register to the assigned register at function entry.
    for param, i in params {
        if i < config.argRegs.len {
            if not bitset::contains(spillInfo.calleeClass, param.value.n) {
                set assignments[param.value.n] = config.argRegs[i];
            }
        }
    }
    // Allocate used registers bitset (32 physical registers per 32-bit word).
    let usedRegs = try bitset::allocate(storage, 32);

    // Current register mapping.
    // Reuse one last-use table for all blocks in the function.
    let lastUse = try storage.fill(0 as u32, maxReg);
    let mut current = try createRegMap(storage);

    // Phase 2: Linear scan allocation.
    for b in 0..blockCount {
        let block = &blocks[b];
        let currentRef: 'step = &mut current, usedRef = &mut usedRegs[..],
            lastUseRef = &mut lastUse[..], liveRef = &*live,
            assignmentsRef = &mut assignments[..], spillRef = &*spillInfo
        where 'scratch: 'step in {
            let mut ctx = InstrCtx 'scratch 'step {
                current: currentRef,
                usedRegs: usedRef,
                lastUse: lastUseRef,
                live: liveRef,
                blockIdx: b,
                instrIdx: 0,
                allocatable,
                calleeSaved: config.calleeSaved,
                assignments: assignmentsRef,
                spillInfo: spillRef,
            };
            assignBlock(block.params, block.instructions, &mut ctx, config);
        }
    }
    // Compute bitmask of used callee-saved registers.
    let mut usedCalleeSaved: u32 = 0;
    for i in 0..maxReg {
        if let phys = assignments[i] {
            for saved, j in config.calleeSaved {
                if *phys == *saved {
                    set usedCalleeSaved |= (1 << j);
                }
            }
        }
    }

    return AssignInfo 'scratch {
        assignments: &assignments[..],
        usedCalleeSaved,
    };
}

/// Assign one block's source and destination registers in instruction order.
fn assignBlock 'input 'scratch 'step (
    params: &[il::Param],
    instructions: &[published::Instruction 'input],
    ctx: &mut InstrCtx 'scratch 'step,
    config: &super::TargetConfig,
) where 'scratch: 'step {
    // Record every operand before allocation. Only current-block operands
    // query this table, so every read is initialized by this scan.
    // Entries for other registers need not be cleared between blocks.
    for i in 0..instructions.len {
        let instr = &instructions[i];
        for reg in published::registers(instr) {
            recordLastUse(reg, ctx.lastUse, i);
        }
    }

    enterBlock(ctx.current, ctx.usedRegs, liveness::liveInRow(ctx.live, ctx.blockIdx), params, ctx.assignments, config, ctx.spillInfo);

    // Process each instruction.
    for i in 0..instructions.len {
        let instr = &instructions[i];
        set ctx.instrIdx = i;
        for reg in published::registers(instr) {
            processInstrReg(reg, ctx);
        }

        // Allocate destination.
        if let dst = published::destination(instr) {
            if dst.n < ctx.assignments.len and not spill::isSpilled(ctx.spillInfo, dst) {
                set ctx.assignments[dst.n] = rallocReg(ctx.current, ctx.usedRegs, dst.n, ctx.allocatable, ctx.calleeSaved, ctx.spillInfo);
            }
        }
    }
}

/// Reserve live-in registers before assigning the block's parameter registers.
fn enterBlock 'scratch (
    current: &mut RegMap 'scratch,
    usedRegs: &mut [u32],
    liveIn: &[u32],
    params: &[il::Param],
    assignments: &mut [?gen::Reg],
    config: &super::TargetConfig,
    spillInfo: &spill::SpillInfo 'scratch,
) {
    // Reset for new block.
    set current.n = 0;
    bitset::clearAll(usedRegs);

    // Mark all live-in values' registers as used.
    // This ensures we don't reuse registers for values that flow in
    // from predecessors, even at merge points with multiple predecessors.
    // Values that are live-in but have no assignment yet (e.g. callee-saved
    // function parameters not used before a phi block) are allocated now to
    // prevent conflicts with block parameters.
    let mut liveInIter = bitset::iter(liveIn);
    while let ssaReg = bitset::iterNext(&mut liveInIter, liveIn) {
        let reg = il::Reg { n: ssaReg };
        if not spill::isSpilled(spillInfo, reg) {
            if let phys = assignments[ssaReg] {
                bitset::put(usedRegs, *phys as u32);
                rmapSet(current, ssaReg, phys);
            } else {
                set assignments[ssaReg] = rallocReg(current, usedRegs, ssaReg, config.allocatable, config.calleeSaved, spillInfo);
            }
        }
    }

    // Allocate block parameters.
    for p in params {
        if p.value.n < assignments.len and not spill::isSpilled(spillInfo, p.value) {
            set assignments[p.value.n] = rallocReg(current, usedRegs, p.value.n, config.allocatable, config.calleeSaved, spillInfo);
        }
    }
}

/// Create an empty register map.
fn createRegMap 'scratch (storage: &Session 'scratch) -> RegMap 'scratch throws (alloc::AllocError) {
    let virtRegs = try storage.fill(0 as u32, MAX_ACTIVE);
    let physRegs = try storage.fill(gen::Reg(0), MAX_ACTIVE);
    return RegMap 'scratch { virtRegs, physRegs, n: 0 };
}

/// Find physical register for a virtual register in RegMap.
fn rmapFind 'scratch (rmap: &RegMap 'scratch, virtReg: u32) -> ?gen::Reg {
    for i in 0..rmap.n {
        if rmap.virtRegs[i] == virtReg {
            return rmap.physRegs[i];
        }
    }
    return nil;
}

/// Add a mapping to the register map.
fn rmapSet 'scratch (rmap: &mut RegMap 'scratch, virtReg: u32, physReg: gen::Reg) {
    assert rmap.n < MAX_ACTIVE, "rmapSet: register map overflow";
    set rmap.virtRegs[rmap.n] = virtReg;
    set rmap.physRegs[rmap.n] = physReg;
    set rmap.n += 1;
}

/// Remove a mapping from the register map and return its physical register.
fn rmapRemove 'scratch (rmap: &mut RegMap 'scratch, virtReg: u32) -> ?gen::Reg {
    for i in 0..rmap.n {
        if rmap.virtRegs[i] == virtReg {
            let phys = rmap.physRegs[i];
            // Swap with last and decrement.
            set rmap.n -= 1;
            if i < rmap.n {
                set rmap.virtRegs[i] = rmap.virtRegs[rmap.n];
                set rmap.physRegs[i] = rmap.physRegs[rmap.n];
            }
            return phys;
        }
    }
    return nil;
}

/// Find first free register in pool, allocate it, return it.
fn findFreeInPool 'scratch (usedRegs: &mut [u32], current: &mut RegMap 'scratch, ssaReg: u32, pool: *[gen::Reg]) -> ?gen::Reg {
    for r in pool {
        if not bitset::contains(usedRegs, *r as u32) {
            bitset::put(usedRegs, *r as u32);
            rmapSet(current, ssaReg, r);
            return r;
        }
    }
    return nil;
}

/// Allocate a physical register for an SSA register.
/// Cross-call values are steered to callee-saved registers.
fn rallocReg 'scratch (
    current: &mut RegMap 'scratch,
    usedRegs: &mut [u32],
    ssaReg: u32,
    allocatable: *[gen::Reg],
    calleeSaved: *[gen::Reg],
    spillInfo: &spill::SpillInfo 'scratch
) -> gen::Reg {
    // Check if already assigned.
    if let phys = rmapFind(current, ssaReg) {
        return phys;
    }
    // Allocate from appropriate pool. Cross-call values must use callee-saved
    // registers since they are live across function calls.
    if bitset::contains(spillInfo.calleeClass, ssaReg) {
        if let r = findFreeInPool(usedRegs, current, ssaReg, calleeSaved) {
            return r;
        }
        panic "rallocReg: no callee-saved register for cross-call value";
    }
    if let r = findFreeInPool(usedRegs, current, ssaReg, allocatable) {
        return r;
    }
    panic "rallocReg: no free register, spilling fault";
}

/// Record the last instruction that uses the register.
fn recordLastUse(reg: il::Reg, lastUse: &mut [u32], index: u32) {
    set lastUse[reg.n] = index;
}

/// Release expired registers and assign a register for this operand.
fn processInstrReg 'scratch 'step (reg: il::Reg, ctx: &mut InstrCtx 'scratch 'step) where 'scratch: 'step {
    if not (bitset::contains(liveness::liveOutRow(ctx.live, ctx.blockIdx), reg.n) or ctx.lastUse[reg.n] > ctx.instrIdx) {
        if let phys = rmapRemove(ctx.current, reg.n) {
            bitset::clear(ctx.usedRegs, *phys as u32);
        }
    }
    assert reg.n < ctx.assignments.len, "processInstrReg: register out of bounds";
    if spill::isSpilled(ctx.spillInfo, reg) {
        return; // Spilled values don't get physical registers.
    }
    if ctx.assignments[reg.n] == nil {
        set ctx.assignments[reg.n] = rallocReg(
            ctx.current, ctx.usedRegs, reg.n, ctx.allocatable,
            ctx.calleeSaved, ctx.spillInfo
        );
    }
}

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