Replace O(n) data symbol lookup with O(1) lookup

28a18c72a7434935505a65080675b1b9dddda95e8ed0db34ede69257ac468165
Alexis Sellier committed ago 1 parent e0f33455
compiler/radiance.rad +5 -2
17 17
use std::lang::sexpr;
18 18
use std::lang::gen::data;
19 19
use std::lang::gen::types;
20 20
use std::sys;
21 21
use std::sys::unix;
22 +
use std::collections::dict;
22 23
23 24
/// Maximum number of modules we can load per package.
24 25
const MAX_LOADED_MODULES: u32 = 64;
25 26
/// Maximum number of packages we can compile.
26 27
const MAX_PACKAGES: u32 = 4;
55 56
/// Errors emitted by resolver.
56 57
static RESOLVER_ERRORS: [resolver::Error; resolver::MAX_ERRORS] = undefined;
57 58
58 59
/// Code generation storage.
59 60
static CODEGEN_DATA_SYMS: [data::DataSym; data::MAX_DATA_SYMS] = undefined;
61 +
/// Hash table entries for data symbol lookup.
62 +
static CODEGEN_DATA_SYM_ENTRIES: [dict::Entry; data::DATA_SYM_TABLE_SIZE] = undefined;
60 63
61 64
/// Debug info file extension.
62 65
const DEBUG_EXT: *[u8] = ".debug";
63 66
64 67
/// Read-only data file extension.
791 794
        io::print("\n");
792 795
        return;
793 796
    }
794 797
    if ctx.dump == Dump::Asm {
795 798
        // TODO: Why do we generate code in two places?
796 -
        let result = rv64::generate(&program, rv64::Storage { dataSyms: &mut CODEGEN_DATA_SYMS[..] }, &mut RO_DATA_BUF[..], &mut RW_DATA_BUF[..], &mut res.arena, false);
799 +
        let result = rv64::generate(&program, rv64::Storage { dataSyms: &mut CODEGEN_DATA_SYMS[..], dataSymEntries: &mut CODEGEN_DATA_SYM_ENTRIES[..] }, &mut RO_DATA_BUF[..], &mut RW_DATA_BUF[..], &mut res.arena, false);
797 800
        printer::printCodeTo(&mut out, entryPkg.name, result.code, result.funcs, &mut res.arena);
798 801
        io::print("\n");
799 802
        return;
800 803
    }
801 804
    // Generate binary output if path specified.
807 810
        io::printError("radiance: fatal: no default function found\n");
808 811
        throw Error::Other;
809 812
    }
810 813
    pkgLog(entryPkg, &["generating code", "(", outPath, ")", ".."]);
811 814
812 -
    let storage = rv64::Storage { dataSyms: &mut CODEGEN_DATA_SYMS[..] };
815 +
    let storage = rv64::Storage { dataSyms: &mut CODEGEN_DATA_SYMS[..], dataSymEntries: &mut CODEGEN_DATA_SYM_ENTRIES[..] };
813 816
    let result = rv64::generate(&program, storage, &mut RO_DATA_BUF[..], &mut RW_DATA_BUF[..], &mut res.arena, ctx.debug);
814 817
    if not writeCode(result.code, outPath) {
815 818
        io::printError("radiance: fatal: failed to write output file\n");
816 819
        throw Error::Other;
817 820
    }
lib/std/arch/rv64.rad +10 -5
17 17
pub mod printer;
18 18
19 19
@test mod tests;
20 20
21 21
use std::mem;
22 +
use std::collections::dict;
22 23
use std::lang::il;
23 24
use std::lang::alloc;
24 25
use std::lang::gen::labels;
25 26
use std::lang::gen::regalloc;
26 27
use std::lang::gen::data;
152 153
153 154
/// Storage buffers passed from driver for code generation.
154 155
pub record Storage {
155 156
    /// Buffer for data symbols.
156 157
    dataSyms: *mut [data::DataSym],
158 +
    /// Hash table entries for data symbol lookup.
159 +
    dataSymEntries: *mut [dict::Entry],
157 160
}
158 161
159 162
/// Result of code generation.
160 163
pub record Program {
161 164
    /// Slice of emitted code.
186 189
    let mut dataSymCount: u32 = 0;
187 190
188 191
    let roLayoutSize = data::layoutSection(program, storage.dataSyms, &mut dataSymCount, RO_DATA_BASE, true);
189 192
    data::layoutSection(program, storage.dataSyms, &mut dataSymCount, RW_DATA_BASE, false);
190 193
194 +
    // Build hash-indexed data symbol map for O(1) lookups.
195 +
    let dataSyms = &storage.dataSyms[..dataSymCount];
196 +
    let mut dataSymMap = data::buildMap(dataSyms, storage.dataSymEntries);
197 +
191 198
    // Code base address: code follows read-only data, aligned to dword boundary.
192 199
    let codeBase = mem::alignUp(RO_DATA_BASE + roLayoutSize, DWORD_SIZE as u32);
193 200
194 201
    // Emit placeholder entry jump to default function if there is one.
195 202
    // We'll patch this at the end once we know where the function is.
199 206
        emit::emit(&mut e, encode::nop()); // Placeholder for two-instruction jump.
200 207
        emit::emit(&mut e, encode::nop()); //
201 208
    }
202 209
203 210
    // Generate code for all functions.
204 -
    let dataSyms = &storage.dataSyms[..dataSymCount];
205 -
206 211
    for i in 0..program.fns.len {
207 212
        let func = program.fns[i];
208 213
        if not func.isExtern {
209 214
            let checkpoint = alloc::save(arena);
210 215
            let ralloc = try! regalloc::allocate(func, &config, arena);
211 -
            isel::selectFn(&mut e, dataSyms, &ralloc, func);
216 +
            isel::selectFn(&mut e, &dataSymMap, &ralloc, func);
212 217
213 218
            // Reclaim unused memory after instruction selection.
214 219
            alloc::restore(arena, checkpoint);
215 220
        }
216 221
    }
226 231
    // Patch function calls and address loads now that all functions are emitted.
227 232
    emit::patchCalls(&mut e);
228 233
    emit::patchAddrLoads(&mut e);
229 234
230 235
    // Emit data sections.
231 -
    let roDataSize = data::emitSection(program, dataSyms, &e.labels, codeBase, roDataBuf, true);
232 -
    let rwDataSize = data::emitSection(program, dataSyms, &e.labels, codeBase, rwDataBuf, false);
236 +
    let roDataSize = data::emitSection(program, &dataSymMap, &e.labels, codeBase, roDataBuf, true);
237 +
    let rwDataSize = data::emitSection(program, &dataSymMap, &e.labels, codeBase, rwDataBuf, false);
233 238
234 239
    return Program {
235 240
        code: emit::getCode(&e),
236 241
        funcs: emit::getFuncs(&e),
237 242
        roDataSize,
lib/std/arch/rv64/isel.rad +5 -5
79 79
pub record Selector {
80 80
    /// Emitter for outputting instructions.
81 81
    e: *mut emit::Emitter,
82 82
    /// Register allocation result.
83 83
    ralloc: *regalloc::AllocResult,
84 -
    /// Data symbols for resolving symbol addresses.
85 -
    dataSyms: *[data::DataSym],
84 +
    /// Hash-indexed data symbol map.
85 +
    dataSymMap: *data::DataSymMap,
86 86
    /// Total stack frame size.
87 87
    frameSize: i32,
88 88
    /// Running offset into the reserve region of the frame.
89 89
    /// Tracks current position within the pre-allocated reserve slots.
90 90
    reserveOffset: i32,
136 136
    return getReg(s, ssa);
137 137
}
138 138
139 139
/// Look up symbol address in data map.
140 140
fn lookupDataSym(s: *Selector, name: *[u8]) -> u32 throws (SelectorError) {
141 -
    let addr = data::lookupDataSymAddr(s.dataSyms, name) else {
141 +
    let addr = data::lookupAddr(s.dataSymMap, name) else {
142 142
        throw SelectorError::Internal;
143 143
    };
144 144
    return addr;
145 145
}
146 146
248 248
}
249 249
250 250
/// Select instructions for a function.
251 251
pub fn selectFn(
252 252
    e: *mut emit::Emitter,
253 -
    dataSyms: *[data::DataSym],
253 +
    dataSymMap: *data::DataSymMap,
254 254
    ralloc: *regalloc::AllocResult,
255 255
    func: *il::Fn
256 256
) {
257 257
    // Reset block offsets for this function.
258 258
    labels::resetBlocks(&mut e.labels);
264 264
        ralloc.usedCalleeSaved,
265 265
        func.blocks.len
266 266
    );
267 267
    // Synthetic block indices start after real blocks and the epilogue block.
268 268
    let mut s = Selector {
269 -
        e, ralloc, dataSyms, frameSize: frame.totalSize,
269 +
        e, ralloc, dataSymMap, frameSize: frame.totalSize,
270 270
        reserveOffset: 0, pendingSpill: nil,
271 271
        nextSynthBlock: func.blocks.len + 1,
272 272
    };
273 273
    // Record function name for printing.
274 274
    emit::recordFunc(s.e, func.name);
lib/std/lang/gen/data.rad +34 -3
2 2
//!
3 3
//! Target-independent routines for laying out data symbols and
4 4
//! serializing initialized data into binary sections.
5 5
6 6
use std::mem;
7 +
use std::collections::dict;
7 8
use std::lang::il;
8 9
use std::lang::gen::labels;
9 10
10 11
/// Maximum number of data symbols.
11 12
pub const MAX_DATA_SYMS: u32 = 8192;
12 13
14 +
/// Size of the data symbol hash table. Must be a power of two
15 +
/// and at least twice the size of [`MAX_DATA_SYMS`].
16 +
pub const DATA_SYM_TABLE_SIZE: u32 = 16384;
17 +
13 18
/// Data symbol entry mapping name to address.
14 19
pub record DataSym {
15 20
    /// Symbol name.
16 21
    name: *[u8],
17 22
    /// Absolute address, including data base address.
18 23
    addr: u32,
19 24
}
20 25
26 +
/// Hash-indexed data symbol map.
27 +
pub record DataSymMap {
28 +
    /// Underlying hash table.
29 +
    dict: dict::Dict,
30 +
    /// Fallback linear array for edge cases.
31 +
    syms: *[DataSym],
32 +
}
33 +
21 34
/// Lay out data symbols for a single section.
22 35
/// Initialized data is placed first, then uninitialized, so that only
23 36
/// initialized data needs to be written to the output file.
24 37
/// Returns the updated offset past all placed symbols.
25 38
pub fn layoutSection(
57 70
/// Emit data bytes for a single section (read-only or read-write) into `buf`.
58 71
/// Iterates initialized data in the IL program, serializing each data item.
59 72
/// Returns the total number of bytes written.
60 73
pub fn emitSection(
61 74
    program: *il::Program,
62 -
    dataSyms: *[DataSym],
75 +
    dataSymMap: *DataSymMap,
63 76
    fnLabels: *labels::Labels,
64 77
    codeBase: u32,
65 78
    buf: *mut [u8],
66 79
    readOnly: bool
67 80
) -> u32 {
83 96
                            let valPtr = &val as *u8;
84 97
                            try! mem::copy(&mut buf[offset..], @sliceOf(valPtr, size));
85 98
                            offset += size;
86 99
                        },
87 100
                        case il::DataItem::Sym(name) => {
88 -
                            let addr = lookupDataSymAddr(dataSyms, name) else {
101 +
                            let addr = lookupAddr(dataSymMap, name) else {
89 102
                                panic "emitSection: data symbol not found";
90 103
                            };
91 104
                            // Write 8-byte pointer: low 4 bytes are the
92 105
                            // address, high 4 bytes are zero.
93 106
                            // TODO: Use `u64` once it's supported.
127 140
        }
128 141
    }
129 142
    return offset;
130 143
}
131 144
132 -
/// Resolve a data symbol to its final absolute address.
145 +
/// Build a hash-indexed data symbol map from the laid-out symbols.
146 +
/// The `entries` slice must have length `DATA_SYM_TABLE_SIZE`.
147 +
pub fn buildMap(syms: *[DataSym], entries: *mut [dict::Entry]) -> DataSymMap {
148 +
    let mut d = dict::init(entries);
149 +
    for i in 0..syms.len {
150 +
        dict::insert(&mut d, syms[i].name, syms[i].addr as i32);
151 +
    }
152 +
    return DataSymMap { dict: d, syms };
153 +
}
154 +
155 +
/// Resolve a data symbol to its final absolute address using the hash map.
156 +
pub fn lookupAddr(m: *DataSymMap, name: *[u8]) -> ?u32 {
157 +
    if let v = dict::get(&m.dict, name) {
158 +
        return v as u32;
159 +
    }
160 +
    return nil;
161 +
}
162 +
163 +
/// Resolve a data symbol to its final absolute address (linear scan fallback).
133 164
pub fn lookupDataSymAddr(dataSyms: *[DataSym], name: *[u8]) -> ?u32 {
134 165
    for i in 0..dataSyms.len {
135 166
        let sym = dataSyms[i];
136 167
        if mem::eq(sym.name, name) {
137 168
            return sym.addr;