radiance · Radiance self-hosting compiler

compiler/ kernel/ lib/ examples/ std/ arch/ char/ collections/ lang/ alloc/ ast/ gen/ bitset/ regalloc/ liveness/ assign.rad 10.7 KiB liveness.rad 8.3 KiB spill.rad 10.9 KiB bitset.rad 4.6 KiB data.rad 8.5 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 19.5 KiB lower.rad 308.1 KiB module.rad 14.9 KiB package.rad 1.3 KiB parser.rad 89.5 KiB resolver.rad 439.6 KiB scanner.rad 18.0 KiB sexpr.rad 6.4 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 9.2 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 10.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::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,
}

/// Per-instruction context for freeing and allocating register uses.
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 [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 unsafe fn assign 'scratch (
    func: &il::Fn,
    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 = func.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 func.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 = &func.blocks[b];

        // 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 instr, i in block.instrs {
            let mut registers = il::registers(&instr);
            while let reg = il::nextReg(&mut registers, &instr) {
                recordLastUse(reg, &mut lastUse[..], i);
            }
        }

        // 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(liveness::liveInRow(live, b));
        while let ssaReg = bitset::iterNext(&mut liveInIter, liveness::liveInRow(live, b)) {
            let reg = il::Reg { n: ssaReg };
            if not spill::isSpilled(spillInfo, reg) {
                if let phys = assignments[ssaReg] {
                    bitset::put(usedRegs, *phys as u32);
                    rmapSet(&mut current, ssaReg, phys);
                } else {
                    set assignments[ssaReg] = rallocReg(&mut current, usedRegs, ssaReg, allocatable, config.calleeSaved, spillInfo);
                }
            }
        }

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

        // Process each instruction.
        for instr, i in block.instrs {
            let currentRef: 'step = &mut current, usedRef = &mut usedRegs[..],
                lastUseRef = &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: i,
                    allocatable,
                    calleeSaved: config.calleeSaved,
                    assignments: assignmentsRef,
                    spillInfo: spillRef,
                };
                let mut registers = il::registers(&instr);
                while let reg = il::nextReg(&mut registers, &instr) {
                    processInstrReg(reg, &mut ctx);
                }
            }

            // Allocate destination.
            if let dst = il::instrDst(instr) {
                if dst.n < maxReg and not spill::isSpilled(spillInfo, dst) {
                    set assignments[dst.n] = rallocReg(&mut current, usedRegs, dst.n, allocatable, config.calleeSaved, spillInfo);
                }
            }
        }
    }
    // 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,
    };
}

/// 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::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	/// Per-instruction context for freeing and allocating register uses.
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 [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	let maxReg = live.maxReg;
62	let blockCount = func.blocks.len;
63	let allocatable = config.allocatable;
64
65	if maxReg == 0 or blockCount == 0 {
66	return AssignInfo 'scratch {
67	assignments: try storage.fill(nil as ?gen::Reg, 0),
68	usedCalleeSaved: 0,
69	};
70	}
71
72	// Allocate output structures.
73	let assignments = try storage.fill(nil as ?gen::Reg, maxReg);
74	// Pre-assign function parameters to argument registers.
75	// Cross-call params are NOT pre-assigned here; they will be allocated
76	// to callee-saved registers by the normal path, and isel emits moves
77	// from the arg register to the assigned register at function entry.
78	for param, i in func.params {
79	if i < config.argRegs.len {
80	if not bitset::contains(spillInfo.calleeClass, param.value.n) {
81	set assignments[param.value.n] = config.argRegs[i];
82	}
83	}
84	}
85	// Allocate used registers bitset (32 physical registers per 32-bit word).
86	let usedRegs = try bitset::allocate(storage, 32);
87
88	// Current register mapping.
89	// Reuse one last-use table for all blocks in the function.
90	let lastUse = try storage.fill(0 as u32, maxReg);
91	let mut current = try createRegMap(storage);
92
93	// Phase 2: Linear scan allocation.
94	for b in 0..blockCount {
95	let block = &func.blocks[b];
96
97	// Record every operand before allocation. Only current-block operands
98	// query this table, so every read is initialized by this scan.
99	// Entries for other registers need not be cleared between blocks.
100	for instr, i in block.instrs {
101	let mut registers = il::registers(&instr);
102	while let reg = il::nextReg(&mut registers, &instr) {
103	recordLastUse(reg, &mut lastUse[..], i);
104	}
105	}
106
107	// Reset for new block.
108	set current.n = 0;
109	bitset::clearAll(usedRegs);
110
111	// Mark all live-in values' registers as used.
112	// This ensures we don't reuse registers for values that flow in
113	// from predecessors, even at merge points with multiple predecessors.
114	// Values that are live-in but have no assignment yet (e.g. callee-saved
115	// function parameters not used before a phi block) are allocated now to
116	// prevent conflicts with block parameters.
117	let mut liveInIter = bitset::iter(liveness::liveInRow(live, b));
118	while let ssaReg = bitset::iterNext(&mut liveInIter, liveness::liveInRow(live, b)) {
119	let reg = il::Reg { n: ssaReg };
120	if not spill::isSpilled(spillInfo, reg) {
121	if let phys = assignments[ssaReg] {
122	bitset::put(usedRegs, *phys as u32);
123	rmapSet(&mut current, ssaReg, phys);
124	} else {
125	set assignments[ssaReg] = rallocReg(&mut current, usedRegs, ssaReg, allocatable, config.calleeSaved, spillInfo);
126	}
127	}
128	}
129
130	// Allocate block parameters.
131	for p in block.params {
132	if p.value.n < maxReg and not spill::isSpilled(spillInfo, p.value) {
133	set assignments[p.value.n] = rallocReg(&mut current, usedRegs, p.value.n, allocatable, config.calleeSaved, spillInfo);
134	}
135	}
136
137	// Process each instruction.
138	for instr, i in block.instrs {
139	let currentRef: 'step = &mut current, usedRef = &mut usedRegs[..],
140	lastUseRef = &lastUse[..], liveRef = &*live,
141	assignmentsRef = &mut assignments[..], spillRef = &*spillInfo
142	where 'scratch: 'step in {
143	let mut ctx = InstrCtx 'scratch 'step {
144	current: currentRef,
145	usedRegs: usedRef,
146	lastUse: lastUseRef,
147	live: liveRef,
148	blockIdx: b,
149	instrIdx: i,
150	allocatable,
151	calleeSaved: config.calleeSaved,
152	assignments: assignmentsRef,
153	spillInfo: spillRef,
154	};
155	let mut registers = il::registers(&instr);
156	while let reg = il::nextReg(&mut registers, &instr) {
157	processInstrReg(reg, &mut ctx);
158	}
159	}
160
161	// Allocate destination.
162	if let dst = il::instrDst(instr) {
163	if dst.n < maxReg and not spill::isSpilled(spillInfo, dst) {
164	set assignments[dst.n] = rallocReg(&mut current, usedRegs, dst.n, allocatable, config.calleeSaved, spillInfo);
165	}
166	}
167	}
168	}
169	// Compute bitmask of used callee-saved registers.
170	let mut usedCalleeSaved: u32 = 0;
171	for i in 0..maxReg {
172	if let phys = assignments[i] {
173	for saved, j in config.calleeSaved {
174	if phys == saved {
175	set usedCalleeSaved \|= (1 << j);
176	}
177	}
178	}
179	}
180
181	return AssignInfo 'scratch {
182	assignments: &assignments[..],
183	usedCalleeSaved,
184	};
185	}
186
187	/// Create an empty register map.
188	fn createRegMap 'scratch (storage: &Session 'scratch) -> RegMap 'scratch throws (alloc::AllocError) {
189	let virtRegs = try storage.fill(0 as u32, MAX_ACTIVE);
190	let physRegs = try storage.fill(gen::Reg(0), MAX_ACTIVE);
191	return RegMap 'scratch { virtRegs, physRegs, n: 0 };
192	}
193
194	/// Find physical register for a virtual register in RegMap.
195	fn rmapFind 'scratch (rmap: &RegMap 'scratch, virtReg: u32) -> ?gen::Reg {
196	for i in 0..rmap.n {
197	if rmap.virtRegs[i] == virtReg {
198	return rmap.physRegs[i];
199	}
200	}
201	return nil;
202	}
203
204	/// Add a mapping to the register map.
205	fn rmapSet 'scratch (rmap: &mut RegMap 'scratch, virtReg: u32, physReg: gen::Reg) {
206	assert rmap.n < MAX_ACTIVE, "rmapSet: register map overflow";
207	set rmap.virtRegs[rmap.n] = virtReg;
208	set rmap.physRegs[rmap.n] = physReg;
209	set rmap.n += 1;
210	}
211
212	/// Remove a mapping from the register map and return its physical register.
213	fn rmapRemove 'scratch (rmap: &mut RegMap 'scratch, virtReg: u32) -> ?gen::Reg {
214	for i in 0..rmap.n {
215	if rmap.virtRegs[i] == virtReg {
216	let phys = rmap.physRegs[i];
217	// Swap with last and decrement.
218	set rmap.n -= 1;
219	if i < rmap.n {
220	set rmap.virtRegs[i] = rmap.virtRegs[rmap.n];
221	set rmap.physRegs[i] = rmap.physRegs[rmap.n];
222	}
223	return phys;
224	}
225	}
226	return nil;
227	}
228
229	/// Find first free register in pool, allocate it, return it.
230	fn findFreeInPool 'scratch (usedRegs: &mut [u32], current: &mut RegMap 'scratch, ssaReg: u32, pool: *[gen::Reg]) -> ?gen::Reg {
231	for r in pool {
232	if not bitset::contains(usedRegs, *r as u32) {
233	bitset::put(usedRegs, *r as u32);
234	rmapSet(current, ssaReg, r);
235	return r;
236	}
237	}
238	return nil;
239	}
240
241	/// Allocate a physical register for an SSA register.
242	/// Cross-call values are steered to callee-saved registers.
243	fn rallocReg 'scratch (
244	current: &mut RegMap 'scratch,
245	usedRegs: &mut [u32],
246	ssaReg: u32,
247	allocatable: *[gen::Reg],
248	calleeSaved: *[gen::Reg],
249	spillInfo: &spill::SpillInfo 'scratch
250	) -> gen::Reg {
251	// Check if already assigned.
252	if let phys = rmapFind(current, ssaReg) {
253	return phys;
254	}
255	// Allocate from appropriate pool. Cross-call values must use callee-saved
256	// registers since they are live across function calls.
257	if bitset::contains(spillInfo.calleeClass, ssaReg) {
258	if let r = findFreeInPool(usedRegs, current, ssaReg, calleeSaved) {
259	return r;
260	}
261	panic "rallocReg: no callee-saved register for cross-call value";
262	}
263	if let r = findFreeInPool(usedRegs, current, ssaReg, allocatable) {
264	return r;
265	}
266	panic "rallocReg: no free register, spilling fault";
267	}
268
269	/// Record the last instruction that uses the register.
270	fn recordLastUse(reg: il::Reg, lastUse: &mut [u32], index: u32) {
271	set lastUse[reg.n] = index;
272	}
273
274	/// Release expired registers and assign a register for this operand.
275	fn processInstrReg 'scratch 'step (reg: il::Reg, ctx: &mut InstrCtx 'scratch 'step) where 'scratch: 'step {
276	if not (bitset::contains(liveness::liveOutRow(ctx.live, ctx.blockIdx), reg.n) or ctx.lastUse[reg.n] > ctx.instrIdx) {
277	if let phys = rmapRemove(ctx.current, reg.n) {
278	bitset::clear(ctx.usedRegs, *phys as u32);
279	}
280	}
281	assert reg.n < ctx.assignments.len, "processInstrReg: register out of bounds";
282	if spill::isSpilled(ctx.spillInfo, reg) {
283	return; // Spilled values don't get physical registers.
284	}
285	if ctx.assignments[reg.n] == nil {
286	set ctx.assignments[reg.n] = rallocReg(
287	ctx.current, ctx.usedRegs, reg.n, ctx.allocatable,
288	ctx.calleeSaved, ctx.spillInfo
289	);
290	}
291	}