std: Vectorize shared bulk and bitset operations

6215ce6161fbcef4af5da3bc5b5074d9a32fa79f5717b4d144dc1f3f17faa456
Use checked slice copies and shared vector fills for memory
operations, RAM access, serialization, text buffers, raw vector
storage, and BLAKE3 padding. Vectorize bitset set operations and fused
liveness updates, with scalar paths for single-word sets.

Keep native data records in backend storage and final assembly in the
reclaimed function arena. Startup assembly stays in persistent
storage. This fixes frontend arena exhaustion during cold kernel-test
compilation without increasing memory limits.

Cover bulk boundaries, alignment, patterns, and unequal bitset
lengths. Shorten the retry window so its witness observes active
compilation. Update the opportunities list to retain unfinished
candidates.

Matched cold-cache self compilation uses 0.88% fewer guest instructions.
Benchmark compilation improves 0.9% overall, with 0.1% to 0.3%
regressions on most small fixtures.

Assisted-by: Codex:gpt-6
Change-Id: Id3a2ae4fe9ca72d39224700104ee0214dba46490
Alexis Sellier committed ago 1 parent 127be8c1
compiler/radiance/build.rad +11 -8
46 46
47 47
/// Disjoint storage of the package pipeline and final native generator.
48 48
export record Workspace {
49 49
    /// Persistent syntax, semantic state, and global IL storage.
50 50
    main: *heap::Heap,
51 -
    /// Function IL storage, reclaimed after each function.
51 +
    /// Function IL storage, reclaimed after each function, and final
52 +
    /// assembly storage.
52 53
    functions: *heap::Heap,
53 -
    /// Encoding tables and final code generation storage.
54 +
    /// Native data records, encoding tables, and final code generation storage.
54 55
    emitter: *heap::Heap,
55 56
    /// Immutable artifacts retained across package steps.
56 57
    artifacts: *heap::Heap,
57 58
    /// Encoded function spool for the current package.
58 59
    spool: *mut [u8],
717 718
                    } =
718 719
                        result else panic "buildPackages: expected compilation";
719 720
                    set built = package;
720 721
                    set retained = resolved;
721 722
                    set native = generated;
722 -
                    try allData.extend(data, work.main) catch {
723 -
                        throw super::Error::Other;
723 +
                    try allData.extend(data, work.emitter) catch {
724 +
                        throw super::error(&["native data storage exhausted"]);
724 725
                    };
725 726
                    set fresh = true;
726 727
                    if let root = ctx.cacheDirectory {
727 728
                        // Function storage has no live IL after its sink consumed each function.
728 729
                        try cache::publish(root, &built, work.functions) catch {
1152 1153
    ) catch error {
1153 1154
        asm::printError(error, file.origin, file.bytes);
1154 1155
        throw super::Error::Other;
1155 1156
    };
1156 1157
    try data.extend(result.data, arena) catch {
1157 -
        throw super::Error::Other;
1158 +
        throw super::error(&["assembly data storage exhausted"]);
1158 1159
    };
1159 1160
    try rv64::addAssembly(generator, result) catch error {
1160 1161
        codegen::printError(error);
1161 1162
        throw super::Error::Other;
1162 1163
    };
1211 1212
        throw super::error(&["invalid native package image", package.name]);
1212 1213
    };
1213 1214
    if not mem::eq(head.name, package.name) {
1214 1215
        throw super::error(&["package image name mismatch", package.name]);
1215 1216
    }
1216 -
    try allData.extend(head.program.data, work.main) catch {
1217 -
        throw super::Error::Other;
1217 +
    try allData.extend(head.program.data, work.emitter) catch {
1218 +
        throw super::error(&["native data storage exhausted"]);
1218 1219
    };
1219 1220
    let count = try input.count(binary::MIN_FUNCTION_BYTES) catch {
1220 1221
        throw super::Error::Other;
1221 1222
    };
1222 1223
    for _ in 0 .. count {
1280 1281
            case Contents::Source(source)    => set files = source.files,
1281 1282
            case Contents::Compiled(package) => set files = package.files,
1282 1283
        }
1283 1284
        for file in files {
1284 1285
            if file.role == artifact::FileRole::Assembly {
1285 -
                try assembly(&mut generator, &file, &mut asmData, work.main, &mut ctx.parser.pool);
1286 +
                try assembly(
1287 +
                    &mut generator, &file, &mut asmData, work.functions, &mut ctx.parser.pool
1288 +
                );
1286 1289
            }
1287 1290
        }
1288 1291
    }
1289 1292
    let target = generator.entryPatch;
1290 1293
    if target == rv64::EntryPatch::Reserved(nil) {
kernel/kernel/physical.rad +19 -38
28 28
//! on publication or cancellation. Retained allocation records hold none, so
29 29
//! teardown releases frames from the records alone. A published instance's base
30 30
//! table token lives in `domains::Store.tables` and is replaced by `empty()` when
31 31
//! the instance frames are reclaimed.
32 32
33 +
use std::mem;
33 34
use super::abi;
34 35
use super::frames;
35 36
use super::limits;
36 -
use std::mem;
37 37
38 38
/// Map a physical address to a pointer. The address must be inside RAM that the
39 39
/// caller checked against the frame pool; this module is the only caller.
40 40
unsafe fn pointer(address: u64) -> *unsafe mut opaque;
41 41
134 134
    }
135 135
    let address = try within(access, offset, length);
136 136
    if length == 0 {
137 137
        return;
138 138
    }
139 -
    // SAFETY: within proved the range lies in the token's allocated RAM. The
140 -
    // head and tail are bytes; the aligned middle is stored as whole words.
139 +
    // SAFETY: within proved the range lies in the token's allocated RAM.
140 +
    // Byte accesses permit every input alignment.
141 141
    unsafe {
142 -
        let mut lead = ((8 - (address & 7)) & 7) as u32;
143 -
        if lead > length as u32 {
144 -
            set lead = length as u32;
145 -
        }
146 -
        let words = (length as u32 - lead) / 8;
147 -
        let tail = (length as u32 - lead) % 8;
148 -
        let head = @sliceOf(pointer(address) as *unsafe mut u8, lead);
149 -
        for i in 0 .. head.len {
150 -
            set head[i] = 0;
151 -
        }
152 -
        let middle = @sliceOf(pointer(address + lead as u64) as *unsafe mut u64, words);
153 -
        for i in 0 .. middle.len {
154 -
            set middle[i] = 0;
155 -
        }
156 -
        let end = @sliceOf(
157 -
            pointer(address + lead as u64 + words as u64 * 8) as *unsafe mut u8, tail
158 -
        );
159 -
        for i in 0 .. end.len {
160 -
            set end[i] = 0;
161 -
        }
142 +
        let bytes = @sliceOf(pointer(address) as *unsafe mut u8, length as u32);
143 +
        mem::fill(&mut bytes[..], 0);
162 144
    }
163 145
}
164 146
165 147
/// Copy kernel bytes into physical memory.
166 148
export fn writeAt(access: &Access, offset: u64, source: &[u8]) throws (abi::Error) {
169 151
        return;
170 152
    }
171 153
    // SAFETY: within proved the range lies in the token's allocated RAM.
172 154
    unsafe {
173 155
        let target = @sliceOf(pointer(address) as *unsafe mut u8, source.len);
174 -
        for x, i in source {
175 -
            set target[i] = x;
176 -
        }
156 +
        try! mem::copy(&mut target[..], source);
177 157
    }
178 158
}
179 159
180 160
/// Copy physical memory into kernel bytes.
181 161
export fn readAt(access: &Access, offset: u64, target: &mut [u8]) throws (abi::Error) {
184 164
        return;
185 165
    }
186 166
    // SAFETY: within proved the range lies in the token's allocated RAM.
187 167
    unsafe {
188 168
        let source = @sliceOf(pointer(address) as *unsafe u8, target.len);
189 -
        for i in 0 .. target.len {
190 -
            set target[i] = source[i];
191 -
        }
169 +
        try! mem::copy(target, &source[..]);
192 170
    }
193 171
}
194 172
195 173
/// Store a little-endian value in a byte buffer.
196 174
fn encode(buffer: &mut [u8], offset: u32, value: u64, width: u32) {
259 237
}
260 238
261 239
/// Store one little-endian 64-bit value in count consecutive words.
262 240
/// The address needs no alignment.
263 241
export fn fillWordsAt(access: &Access, offset: u64, value: u64, count: u32) throws (abi::Error) {
264 -
    let checked = try within(access, offset, count as u64 * 8);
265 -
    let mut bytes: [u8; CHUNK] = undefined;
266 -
    for i in 0 .. CHUNK / 8 {
267 -
        encode(&mut bytes[..], i * 8, value, 8);
268 -
    }
242 +
    let address = try within(access, offset, count as u64 * 8);
243 +
    let mut pattern: [u8; 8] = undefined;
244 +
    mem::store64Le(&mut pattern[..], 0, value);
269 245
    let mut done: u32 = 0;
270 246
    while done < count {
271 -
        let mut chunk = count - done;
272 -
        if chunk > CHUNK / 8 {
273 -
            set chunk = CHUNK / 8;
247 +
        let remaining = count - done;
248 +
        let chunk = remaining if remaining < mem::U32_MAX / 8 else mem::U32_MAX / 8;
249 +
        // SAFETY: within proved the range lies in the token's allocated RAM.
250 +
        // Each byte view fits the 32-bit slice length.
251 +
        unsafe {
252 +
            let bytes = @sliceOf(
253 +
                pointer(address + done as u64 * 8) as *unsafe mut u8, chunk * 8
254 +
            );
255 +
            mem::fillPattern(&mut bytes[..], &pattern[..]);
274 256
        }
275 -
        try! writeAt(access, offset + done as u64 * 8, &bytes[.. chunk * 8]);
276 257
        set done += chunk;
277 258
    }
278 259
}
279 260
280 261
/// Pool-checked clear. Hold the metadata lock.
lib/std/arch/rv64/shared.rad +16 -10
309 309
        let end = location.offset + item.size;
310 310
        if end > initialized {
311 311
            set initialized = end;
312 312
        }
313 313
    }
314 -
    for i in 0 .. initialized {
315 -
        set bytes[i] = 0;
316 -
    }
314 +
    mem::fill(&mut bytes[.. initialized], 0);
317 315
    for item in items {
318 316
        if item.isZeroInit {
319 317
            continue;
320 318
        }
321 319
        let location = try dataRef(try resolve(local, &[], item.name));
353 351
                continue;
354 352
            }
355 353
            if value.count > (end - offset) / width {
356 354
                throw Error::Range;
357 355
            }
358 -
            for _ in 0 .. value.count {
359 -
                match value.item {
360 -
                    case il::DataItem::Str(s) => {
361 -
                        try! mem::copy(&mut bytes[offset .. offset + width], s);
362 -
                    }
363 -
                    else => {
356 +
            let length = value.count * width;
357 +
            match value.item {
358 +
                case il::DataItem::Str(s) => {
359 +
                    mem::fillPattern(&mut bytes[offset .. offset + length], s);
360 +
                }
361 +
                else => {
362 +
                    if value.count == 1 {
364 363
                        integer(bytes, offset, number, width);
364 +
                        set offset += width;
365 +
                        continue;
365 366
                    }
367 +
                    let mut pattern: [u8; 8] = undefined;
368 +
                    integer(&mut pattern[..], 0, number, width);
369 +
                    mem::fillPattern(
370 +
                        &mut bytes[offset .. offset + length], &pattern[.. width]
371 +
                    );
366 372
                }
367 -
                set offset += width;
368 373
            }
374 +
            set offset += length;
369 375
        }
370 376
    }
371 377
    return TemplateSize { bytes: initialized, relocations: count };
372 378
}
373 379
lib/std/hash/blake3.rad +1 -3
208 208
}
209 209
210 210
/// Complete the final chunk and hash tree, then return the root digest.
211 211
export fn finish(input: State) -> Digest {
212 212
    let mut state = input;
213 -
    for i in state.used .. BLOCK_BYTES {
214 -
        set state.block[i] = 0;
215 -
    }
213 +
    mem::fill(&mut state.block[state.used ..], 0);
216 214
    let flags = CHUNK_END | (CHUNK_START if state.blocks == 0 else 0);
217 215
    let mut output = Output {
218 216
        words: state.words,
219 217
        block: readBlock(&state.block[..]),
220 218
        counter: state.counter,
lib/std/lang/gen/bitset.rad +79 -14
96 96
        }
97 97
    }
98 98
    return total;
99 99
}
100 100
101 +
/// Union `count` initialized words. Both ranges must contain count words.
102 +
unsafe fn unionWords(dst: &mut u32, src: &u32, count: u32);
103 +
/// Subtract `count` initialized source words from the destination words.
104 +
unsafe fn subtractWords(dst: &mut u32, src: &u32, count: u32);
105 +
/// Compare `count` initialized words from each input range.
106 +
unsafe fn equalWords(a: &u32, b: &u32, count: u32) -> bool;
107 +
/// Update count live-in words and return whether any word changed.
108 +
/// All four ranges must contain count initialized words.
109 +
unsafe fn liveWords(dst: &mut u32, out: &u32, defs: &u32, uses: &u32, count: u32) -> bool;
110 +
101 111
/// Union: `dst = dst | src`.
102 112
export fn union_(dst: &mut Bitset, src: &Bitset) {
103 113
    let numWords = dst.bits.len;
104 114
    let srcWords = src.bits.len;
105 115
    let minWords = min(numWords, srcWords);
106 -
    for i in 0 .. minWords {
107 -
        set dst.bits[i] |= src.bits[i];
116 +
    if minWords == 0 {
117 +
        return;
118 +
    }
119 +
    if minWords == 1 {
120 +
        set dst.bits[0] |= src.bits[0];
121 +
        return;
122 +
    }
123 +
    unsafe {
124 +
        unionWords(&mut dst.bits[0], &src.bits[0], minWords);
108 125
    }
109 126
}
110 127
111 128
/// Subtract: `dst = dst - src`.
112 129
export fn subtract(dst: &mut Bitset, src: &Bitset) {
113 130
    let numWords = dst.bits.len;
114 131
    let srcWords = src.bits.len;
115 132
    let minWords = min(numWords, srcWords);
116 -
    for i in 0 .. minWords {
117 -
        set dst.bits[i] &= ~src.bits[i];
133 +
    if minWords == 0 {
134 +
        return;
135 +
    }
136 +
    if minWords == 1 {
137 +
        set dst.bits[0] &= ~src.bits[0];
138 +
        return;
139 +
    }
140 +
    unsafe {
141 +
        subtractWords(&mut dst.bits[0], &src.bits[0], minWords);
118 142
    }
119 143
}
120 144
121 145
/// Check if two bitsets are equal.
122 146
export fn eq(a: &Bitset, b: &Bitset) -> bool {
123 147
    let numWordsA = a.bits.len;
124 148
    let numWordsB = b.bits.len;
125 149
    let minWords = min(numWordsA, numWordsB);
126 150
127 -
    for i in 0 .. minWords {
128 -
        if a.bits[i] <> b.bits[i] {
151 +
    if minWords == 1 {
152 +
        if a.bits[0] <> b.bits[0] {
153 +
            return false;
154 +
        }
155 +
    }
156 +
    unsafe {
157 +
        if minWords > 1 and not equalWords(&a.bits[0], &b.bits[0], minWords) {
129 158
            return false;
130 159
        }
131 160
    }
132 161
    for i in minWords .. numWordsA {
133 162
        if a.bits[i] <> 0 {
146 175
export fn copy(dst: &mut Bitset, src: &Bitset) {
147 176
    let numWords = dst.bits.len;
148 177
    let srcWords = src.bits.len;
149 178
    let minWords = min(numWords, srcWords);
150 179
151 -
    for i in 0 .. minWords {
152 -
        set dst.bits[i] = src.bits[i];
153 -
    }
180 +
    set dst.bits[.. minWords] = &src.bits[.. minWords];
154 181
    // Clear remaining words if destination is larger.
155 -
    for i in minWords .. numWords {
156 -
        set dst.bits[i] = 0;
182 +
    if minWords < numWords {
183 +
        unsafe {
184 +
            clearWords(&mut dst.bits[minWords], numWords - minWords);
185 +
        }
157 186
    }
158 187
}
159 188
189 +
/// Fill count writable words with zero. The count must be nonzero.
190 +
unsafe fn clearWords(dst: &mut u32, count: u32);
191 +
160 192
/// Clear all bits.
161 193
export fn clearAll(bs: &mut Bitset) {
162 -
    let numWords = bs.bits.len;
163 -
    for i in 0 .. numWords {
164 -
        set bs.bits[i] = 0;
194 +
    let count = bs.bits.len;
195 +
    if count == 1 {
196 +
        set bs.bits[0] = 0;
197 +
        return;
198 +
    }
199 +
    if count > 0 {
200 +
        unsafe {
201 +
            clearWords(&mut bs.bits[0], count);
202 +
        }
203 +
    }
204 +
}
205 +
206 +
/// Set dst to uses | (liveOut & ~defs) and return whether any word changed.
207 +
/// Each input must contain at least as many words as the destination.
208 +
export fn updateLiveIn(
209 +
    dst: &mut Bitset, liveOut: &Bitset, defs: &Bitset, uses: &Bitset
210 +
) -> bool {
211 +
    let count = dst.bits.len;
212 +
    if count == 0 {
213 +
        return false;
214 +
    }
215 +
    if count == 1 {
216 +
        let word = uses.bits[0] | (liveOut.bits[0] & ~defs.bits[0]);
217 +
        let changed = dst.bits[0] <> word;
218 +
        set dst.bits[0] = word;
219 +
        return changed;
220 +
    }
221 +
    assert liveOut.bits.len >= count and defs.bits.len >= count and uses.bits.len >= count;
222 +
    unsafe {
223 +
        return liveWords(
224 +
            &mut dst.bits[0],
225 +
            &liveOut.bits[0],
226 +
            &defs.bits[0],
227 +
            &uses.bits[0],
228 +
            count
229 +
        );
165 230
    }
166 231
}
167 232
168 233
/// Iterator state for iterating set bits.
169 234
///
lib/std/lang/gen/bitset.ras added +97 -0
1 +
//! Word-wise bitset operations. Vector state is caller-saved.
2 +
// Shift from 32-bit word counts to byte counts.
3 +
.constant WORD_BYTE_SHIFT 2;
4 +
.text;
5 +
// a0 and a1 address count initialized words; a2 is the word count.
6 +
.export @"std::lang::gen::bitset::unionWords";
7 +
@"std::lang::gen::bitset::unionWords"
8 +
    beqz %a2 @unionWordsDone;
9 +
@unionWordsLoop
10 +
    vsetvli %t0 %a2 e32 m8 ta ma;
11 +
    vle32.v %v8 (%a0);
12 +
    vle32.v %v16 (%a1);
13 +
    vor.vv %v8 %v8 %v16;
14 +
    vse32.v %v8 (%a0);
15 +
    slli %t1 %t0 WORD_BYTE_SHIFT;
16 +
    add %a0 %a0 %t1;
17 +
    add %a1 %a1 %t1;
18 +
    sub %a2 %a2 %t0;
19 +
    bnez %a2 @unionWordsLoop;
20 +
@unionWordsDone
21 +
    ret;
22 +
23 +
// a0 and a1 address count initialized words; a2 is the word count.
24 +
.export @"std::lang::gen::bitset::subtractWords";
25 +
@"std::lang::gen::bitset::subtractWords"
26 +
    beqz %a2 @subtractWordsDone;
27 +
@subtractWordsLoop
28 +
    vsetvli %t0 %a2 e32 m8 ta ma;
29 +
    vle32.v %v8 (%a0);
30 +
    vle32.v %v16 (%a1);
31 +
    vandn.vv %v8 %v8 %v16;
32 +
    vse32.v %v8 (%a0);
33 +
    slli %t1 %t0 WORD_BYTE_SHIFT;
34 +
    add %a0 %a0 %t1;
35 +
    add %a1 %a1 %t1;
36 +
    sub %a2 %a2 %t0;
37 +
    bnez %a2 @subtractWordsLoop;
38 +
@subtractWordsDone
39 +
    ret;
40 +
41 +
// a0 and a1 address initialized words; a2 is the word count.
42 +
.export @"std::lang::gen::bitset::equalWords";
43 +
@"std::lang::gen::bitset::equalWords"
44 +
    beqz %a2 @equalDone;
45 +
@equalLoop
46 +
    vsetvli %t0 %a2 e32 m8 ta ma;
47 +
    vle32.v %v8 (%a0);
48 +
    vle32.v %v16 (%a1);
49 +
    vmsne.vv %v0 %v8 %v16;
50 +
    vcpop.m %t1 %v0;
51 +
    bnez %t1 @unequal;
52 +
    slli %t1 %t0 WORD_BYTE_SHIFT;
53 +
    add %a0 %a0 %t1;
54 +
    add %a1 %a1 %t1;
55 +
    sub %a2 %a2 %t0;
56 +
    bnez %a2 @equalLoop;
57 +
@equalDone
58 +
    li %a0 1;
59 +
    ret;
60 +
@unequal
61 +
    li %a0 0;
62 +
    ret;
63 +
64 +
// a0 is live-in; a1 is live-out; a2 is defs; a3 is uses; a4 is the word count.
65 +
.export @"std::lang::gen::bitset::liveWords";
66 +
@"std::lang::gen::bitset::liveWords"
67 +
    li %t2 0;
68 +
    beqz %a4 @liveDone;
69 +
@liveLoop
70 +
    vsetvli %t0 %a4 e32 m4 ta ma;
71 +
    vle32.v %v4 (%a0);
72 +
    vle32.v %v8 (%a1);
73 +
    vle32.v %v12 (%a2);
74 +
    vle32.v %v16 (%a3);
75 +
    vandn.vv %v8 %v8 %v12;
76 +
    vor.vv %v8 %v8 %v16;
77 +
    vmsne.vv %v0 %v4 %v8;
78 +
    vcpop.m %t1 %v0;
79 +
    or %t2 %t2 %t1;
80 +
    vse32.v %v8 (%a0);
81 +
    slli %t1 %t0 WORD_BYTE_SHIFT;
82 +
    add %a0 %a0 %t1;
83 +
    add %a1 %a1 %t1;
84 +
    add %a2 %a2 %t1;
85 +
    add %a3 %a3 %t1;
86 +
    sub %a4 %a4 %t0;
87 +
    bnez %a4 @liveLoop;
88 +
@liveDone
89 +
    snez %a0 %t2;
90 +
    ret;
91 +
92 +
// a0 addresses writable words; a1 is a nonzero word count.
93 +
.export @"std::lang::gen::bitset::clearWords";
94 +
@"std::lang::gen::bitset::clearWords"
95 +
    slli %a1 %a1 WORD_BYTE_SHIFT;
96 +
    li %a2 0;
97 +
    j @"std::mem::fillBytes";
lib/std/lang/gen/bitset/tests.rad +51 -1
1 1
//! Tests for the bitset module.
2 2
3 -
use std::testing;
4 3
use std::mem::heap;
4 +
use std::testing;
5 5
6 6
/// Arena storage for the bitsets built by the tests. Each test starts a new arena over it.
7 7
static BITSET_STORAGE: [u8; 4096] = [0; 4096];
8 8
9 9
/// Test [`super::allocate`] and basic set/contains operations.
293 293
    super::clear(&mut bs, 100);
294 294
295 295
    // Contains beyond length should return false.
296 296
    try testing::expect(not super::contains(&bs, 100));
297 297
}
298 +
299 +
/// Vector bitsets preserve unequal lengths and report liveness changes.
300 +
@test unsafe fn testBulkSets() throws (testing::TestError) {
301 +
    let arena = heap::over(&mut BITSET_STORAGE[..]);
302 +
    let mut a = try! super::allocate(arena, 2080);
303 +
    let mut b = try! super::allocate(arena, 2112);
304 +
    let mut out = try! super::allocate(arena, 2080);
305 +
    let mut defs = try! super::allocate(arena, 2080);
306 +
    let mut uses = try! super::allocate(arena, 2080);
307 +
    for i in 0 .. 2080 {
308 +
        if i % 3 == 0 {
309 +
            super::put(&mut a, i);
310 +
        }
311 +
        if i % 5 == 0 {
312 +
            super::put(&mut b, i);
313 +
        }
314 +
        if i % 7 == 0 {
315 +
            super::put(&mut defs, i);
316 +
        }
317 +
        if i % 11 == 0 {
318 +
            super::put(&mut uses, i);
319 +
        }
320 +
    }
321 +
    super::copy(&mut out, &a);
322 +
    assert super::eq(&out, &a);
323 +
    super::union_(&mut out, &b);
324 +
    for i in 0 .. 2080 {
325 +
        assert super::contains(&out, i) == (i % 3 == 0 or i % 5 == 0);
326 +
    }
327 +
    super::subtract(&mut out, &b);
328 +
    for i in 0 .. 2080 {
329 +
        assert super::contains(&out, i) == (i % 3 == 0 and i % 5 <> 0);
330 +
    }
331 +
    super::copy(&mut b, &a);
332 +
    assert super::eq(&a, &b);
333 +
    super::clear(&mut b, 2079);
334 +
    assert not super::eq(&a, &b);
335 +
    super::put(&mut b, 2079);
336 +
    assert super::eq(&a, &b);
337 +
    super::put(&mut b, 2111);
338 +
    assert not super::eq(&a, &b);
339 +
    super::clearAll(&mut out);
340 +
    assert super::updateLiveIn(&mut out, &a, &defs, &uses);
341 +
    assert not super::updateLiveIn(&mut out, &a, &defs, &uses);
342 +
    for i in 0 .. 2080 {
343 +
        assert super::contains(&out, i) == (i % 11 == 0 or (i % 3 == 0 and i % 7 <> 0));
344 +
    }
345 +
    super::clearAll(&mut out);
346 +
    assert super::count(&out) == 0;
347 +
}
lib/std/lang/gen/data.rad +42 -41
1 1
//! Data section layout and emission.
2 2
//!
3 3
//! Target-independent routines for laying out data symbols and
4 4
//! serializing initialized data into binary sections.
5 5
6 -
use std::mem;
7 6
use std::collections::dict;
8 7
use std::lang::alloc;
9 -
use std::mem::heap;
8 +
use std::lang::gen::labels;
10 9
use std::lang::il;
11 10
use std::lang::parser;
12 -
use std::lang::gen::labels;
11 +
use std::mem;
12 +
use std::mem::heap;
13 13
14 14
/// Maximum number of data symbols.
15 15
export constant MAX_DATA_SYMS: u32 = 8192;
16 16
17 17
/// Size of the data symbol hash table. Must be a power of two
244 244
            let aligned = try alignOffset(offset, data.alignment);
245 245
            if aligned > buf.len or data.size > buf.len - aligned {
246 246
                throw Error::Capacity;
247 247
            }
248 248
            // Alignment padding is defined as zero.
249 -
            for j in offset .. aligned {
250 -
                set buf[j] = 0;
251 -
            }
249 +
            mem::fill(&mut buf[offset .. aligned], 0);
252 250
            set offset = aligned;
253 251
            for j in 0 .. data.values.len {
254 252
                let v = &data.values[j];
255 253
                let mut width: u32 = 1;
256 254
                match v.item {
269 267
                    continue;
270 268
                }
271 269
                if v.count > (aligned + data.size - offset) / width {
272 270
                    throw Error::Overflow;
273 271
                }
274 -
                for _ in 0 .. v.count {
275 -
                    match v.item {
276 -
                        case il::DataItem::Val { typ, val } => {
277 -
                            let size = il::typeSize(typ);
278 -
                            mem::writeLe(buf, offset, val as u64, size);
279 -
                            set offset += size;
280 -
                        }
281 -
                        case il::DataItem::Sym(name) => {
282 -
                            let addr = lookupAddr(dataSymMap, name) else {
283 -
                                throw Error::Symbol;
284 -
                            };
285 -
                            mem::writeLe(buf, offset, addr, @sizeOf(u64));
286 -
287 -
                            set offset += @sizeOf(u64);
288 -
                        }
289 -
                        case il::DataItem::Fn(name) => {
290 -
                            let functionOffset = dict::get(&fnLabels.funcs, name) else {
291 -
                                throw Error::Symbol;
292 -
                            };
293 -
                            if codeBase > mem::U64_MAX - functionOffset as u64 {
294 -
                                throw Error::Overflow;
272 +
                if v.count == 0 {
273 +
                    continue;
274 +
                }
275 +
                let length = v.count * width;
276 +
                match v.item {
277 +
                    case il::DataItem::Str(s) => {
278 +
                        mem::fillPattern(&mut buf[offset .. offset + length], s);
279 +
                    }
280 +
                    else => {
281 +
                        let mut number: u64 = 0;
282 +
                        match v.item {
283 +
                            case il::DataItem::Val { val, .. } => set number = val as u64,
284 +
                            case il::DataItem::Sym(name) => {
285 +
                                let address = lookupAddr(dataSymMap, name) else {
286 +
                                    throw Error::Symbol;
287 +
                                };
288 +
                                set number = address;
295 289
                            }
296 -
                            let addr = codeBase + functionOffset as u64;
297 -
                            mem::writeLe(buf, offset, addr, @sizeOf(u64));
298 -
299 -
                            set offset += @sizeOf(*u8);
300 -
                        }
301 -
                        case il::DataItem::Str(s) => {
302 -
                            try! mem::copy(&mut buf[offset ..], s);
303 -
                            set offset += s.len;
290 +
                            case il::DataItem::Fn(name) => {
291 +
                                let functionOffset = dict::get(&fnLabels.funcs, name) else {
292 +
                                    throw Error::Symbol;
293 +
                                };
294 +
                                if codeBase > mem::U64_MAX - functionOffset as u64 {
295 +
                                    throw Error::Overflow;
296 +
                                }
297 +
                                set number = codeBase + functionOffset as u64;
298 +
                            }
299 +
                            else => {}
304 300
                        }
305 -
                        case il::DataItem::Undef => {
306 -
                            set buf[offset] = 0;
307 -
                            set offset += 1;
301 +
                        if v.count == 1 {
302 +
                            mem::writeLe(buf, offset, number, width);
303 +
                            set offset += width;
304 +
                            continue;
308 305
                        }
306 +
                        let mut pattern: [u8; 8] = undefined;
307 +
                        mem::writeLe(&mut pattern[..], 0, number, width);
308 +
                        mem::fillPattern(
309 +
                            &mut buf[offset .. offset + length], &pattern[.. width]
310 +
                        );
309 311
                    }
310 312
                }
313 +
                set offset += length;
311 314
            }
312 315
            // An initializer shorter than its symbol leaves a zero tail.
313 316
            let end = aligned + data.size;
314 317
            assert offset <= end, "emitSectionAtOffset: initializer exceeds symbol size";
315 -
            for j in offset .. end {
316 -
                set buf[j] = 0;
317 -
            }
318 +
            mem::fill(&mut buf[offset .. end], 0);
318 319
            set offset = end;
319 320
        }
320 321
    }
321 322
    return offset;
322 323
}
lib/std/lang/gen/regalloc/liveness.rad +1 -21
137 137
            let b = order[i];
138 138
139 139
            // Add successor live-in sets directly to this block's live-out set.
140 140
            addSuccessorLiveIn(func, b, &liveIn[..], &mut liveOut[b]);
141 141
142 -
            if computeAndUpdateLiveIn(
142 +
            if bitset::updateLiveIn(
143 143
                &mut liveIn[b], &liveOut[b], &localSets.defs[b], &localSets.uses[b]
144 144
            ) {
145 145
                set changed = true;
146 146
            }
147 147
        }
226 226
        try sets.append(bs, a);
227 227
    }
228 228
    return sets;
229 229
}
230 230
231 -
/// Compute `liveIn = uses | (liveOut - defs)` and update `dst`.
232 -
/// Returns `true` if `dst` changed. Combined loop avoids multiple passes.
233 -
fn computeAndUpdateLiveIn(
234 -
    dst: &mut bitset::Bitset,
235 -
    liveOut: &bitset::Bitset,
236 -
    defs: &bitset::Bitset,
237 -
    uses: &bitset::Bitset
238 -
) -> bool {
239 -
    let numWords = dst.bits.len;
240 -
    let mut changed = false;
241 -
    for i in 0 .. numWords {
242 -
        let newWord = uses.bits[i] | (liveOut.bits[i] & ~defs.bits[i]);
243 -
        if dst.bits[i] <> newWord {
244 -
            set dst.bits[i] = newWord;
245 -
            set changed = true;
246 -
        }
247 -
    }
248 -
    return changed;
249 -
}
250 -
251 231
/// Compute local defs and uses for the block that `sets` currently selects.
252 232
fn computeLocalDefsUses(func: *il::Fn, block: *il::Block, sets: &mut DefsUses) {
253 233
    for p in block.params {
254 234
        bitset::put(&mut sets.defs[sets.block], p.value.n);
255 235
    }
lib/std/lang/sexpr.rad +3 -4
7 7
@test mod tests;
8 8
9 9
use std::fmt;
10 10
use std::io;
11 11
use std::lang::alloc;
12 +
use std::mem;
12 13
use std::mem::heap;
13 14
14 15
/// Text sink for printers. Printers call `write` with text in output order.
15 16
export trait Output {
16 17
    /// Write the bytes of `s` at the end of the output.
41 42
instance Output for Buffer {
42 43
    /// Copy as many bytes of `s` as fit in the remaining buffer space.
43 44
    fn (out: &mut Buffer) write(s: &[u8]) {
44 45
        let remaining = out.buf.len - out.pos;
45 46
        let toWrite = remaining if s.len > remaining else s.len;
46 -
        for i in 0 .. toWrite {
47 -
            set out.buf[out.pos] = s[i];
48 -
            set out.pos += 1;
49 -
        }
47 +
        try! mem::copy(&mut out.buf[out.pos .. out.pos + toWrite], &s[.. toWrite]);
48 +
        set out.pos += toWrite;
50 49
    }
51 50
}
52 51
53 52
/// An S-expression element.
54 53
export union Expr: Copy {
lib/std/mem.rad +38 -8
46 46
/// Copy bytes between two slices. Returns the number of bytes copied.
47 47
export fn copy(into: &mut [u8], from: &[u8]) -> u32 throws (MemoryError) {
48 48
    if into.len < from.len {
49 49
        throw MemoryError::BufferTooSmall;
50 50
    }
51 -
    let mut i: u32 = 0;
52 -
    while from.len - i >= 8 {
53 -
        store64Le(into, i, load64Le(from, i));
54 -
        set i += 8;
51 +
    set into[.. from.len] = from;
52 +
    return from.len;
53 +
}
54 +
55 +
/// Fill `count` writable bytes at `out`. The count must be nonzero.
56 +
unsafe fn fillBytes(out: &mut u8, count: u32, value: u8);
57 +
58 +
/// Repeat an initialized pattern into `count` consecutive copies at `out`.
59 +
/// Both count and width must be nonzero. The output must hold count * width bytes.
60 +
unsafe fn repeatBytes(out: &mut u8, pattern: &u8, count: u32, width: u32);
61 +
62 +
/// Set every byte to `value`.
63 +
export fn fill(bytes: &mut [u8], value: u8) {
64 +
    let count = bytes.len;
65 +
    if count == 0 {
66 +
        return;
55 67
    }
56 -
    while i < from.len {
57 -
        set into[i] = from[i];
58 -
        set i += 1;
68 +
    unsafe {
69 +
        fillBytes(bytes.ptr, count, value);
70 +
    }
71 +
}
72 +
73 +
/// Fill bytes with consecutive copies of a nonempty byte pattern.
74 +
/// The byte length must be a multiple of the pattern length.
75 +
export fn fillPattern(bytes: &mut [u8], pattern: &[u8]) {
76 +
    let width = pattern.len;
77 +
    assert width > 0 and bytes.len % width == 0;
78 +
    let count = bytes.len / width;
79 +
    if count == 0 {
80 +
        return;
81 +
    }
82 +
    if count == 1 or width > 8 {
83 +
        for i in 0 .. count {
84 +
            try! copy(&mut bytes[i * width .. (i + 1) * width], pattern);
85 +
        }
86 +
        return;
87 +
    }
88 +
    unsafe {
89 +
        repeatBytes(bytes.ptr, pattern.ptr, count, width);
59 90
    }
60 -
    return from.len;
61 91
}
62 92
63 93
/// Strip a byte-level prefix from the input, and return the suffix.
64 94
/// Returns `nil` if the prefix wasn't found.
65 95
export fn stripPrefix(prefix: &[u8], input: &'r [u8]) -> ?&'r [u8] {
lib/std/mem.ras added +34 -0
1 +
//! Byte-wide bulk memory stores. Vector state is caller-saved.
2 +
.text;
3 +
// a0 is the output address; a1 is its nonzero byte count; a2 is the value.
4 +
.export @"std::mem::fillBytes";
5 +
@"std::mem::fillBytes"
6 +
    vsetvli %t0 %a1 e8 m8 ta ma;
7 +
    vmv.v.x %v8 %a2;
8 +
    vse8.v %v8 (%a0);
9 +
    add %a0 %a0 %t0;
10 +
    sub %a1 %a1 %t0;
11 +
    bnez %a1 @"std::mem::fillBytes";
12 +
    ret;
13 +
14 +
// a0 is the output; a1 is the pattern; a2 is the repetition count;
15 +
// a3 is the pattern width. Count and width must both be nonzero.
16 +
.export @"std::mem::repeatBytes";
17 +
@"std::mem::repeatBytes"
18 +
    vsetvli %t0 %a2 e8 m8 ta ma;
19 +
    mv %t1 %a0;
20 +
    mv %t2 %a1;
21 +
    mv %t3 %a3;
22 +
@repeatByte
23 +
    lbu %t4 0(%t2);
24 +
    vmv.v.x %v8 %t4;
25 +
    vsse8.v %v8 (%t1) %a3;
26 +
    addi %t1 %t1 1;
27 +
    addi %t2 %t2 1;
28 +
    addi %t3 %t3 -1;
29 +
    bnez %t3 @repeatByte;
30 +
    mul %t1 %t0 %a3;
31 +
    add %a0 %a0 %t1;
32 +
    sub %a2 %a2 %t0;
33 +
    bnez %a2 @"std::mem::repeatBytes";
34 +
    ret;
lib/std/mem/tests.rad +53 -0
97 97
            }
98 98
            assert mem::readLe(&bytes[..], offset, size) == expected;
99 99
        }
100 100
    }
101 101
}
102 +
103 +
/// Bulk fills preserve guard bytes at every alignment and vector boundary.
104 +
@test fn bulkFills() throws (testing::TestError) {
105 +
    let pattern: [u8; 3] = [0x12, 0x80, 0xff];
106 +
    for start in 0 .. 8 {
107 +
        for length in &[0 as u32, 1, 63, 64, 65, 255, 256, 257, 513] {
108 +
            let mut bytes: [u8; 536] = [0xa5; 536];
109 +
            mem::fill(&mut bytes[start .. start + length], 0x73);
110 +
            for byte, i in &bytes[..] {
111 +
                assert byte == (0x73 if i >= start and i < start + length else 0xa5);
112 +
            }
113 +
        }
114 +
        let source: [u8; 536] = [0x71; 536];
115 +
        for length in &[0 as u32, 1, 63, 64, 65, 255, 256, 257, 513] {
116 +
            let mut bytes: [u8; 536] = [0xa5; 536];
117 +
            assert try! mem::copy(
118 +
                &mut bytes[start .. start + length], &source[.. length]
119 +
            ) == length;
120 +
            for byte, i in &bytes[..] {
121 +
                assert byte == (0x71 if i >= start and i < start + length else 0xa5);
122 +
            }
123 +
        }
124 +
        for count in &[0 as u32, 1, 63, 64, 65, 255, 256, 257] {
125 +
            let length = count * 3;
126 +
            let mut bytes: [u8; 792] = [0xa5; 792];
127 +
            mem::fillPattern(&mut bytes[start .. start + length], &pattern[..]);
128 +
            for byte, i in &bytes[..] {
129 +
                let expected = pattern[(i - start) % 3]
130 +
                    if i >= start and i < start + length
131 +
                    else 0xa5;
132 +
                assert byte == expected;
133 +
            }
134 +
        }
135 +
    }
136 +
}
137 +
138 +
/// Pattern fills cover each serializer width and whole-pattern copies.
139 +
@test fn bulkPatterns() throws (testing::TestError) {
140 +
    let pattern: [u8; 16] = [
141 +
        0, 1, 0x80, 0xff, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
142 +
    ];
143 +
    for width in &[1 as u32, 2, 4, 8, 16] {
144 +
        for count in &[0 as u32, 1, 2, 65] {
145 +
            let length = width * count;
146 +
            let mut bytes: [u8; 1042] = [0xa5; 1042];
147 +
            mem::fillPattern(&mut bytes[1 .. length + 1], &pattern[.. width]);
148 +
            assert bytes[0] == 0xa5 and bytes[length + 1] == 0xa5;
149 +
            for i in 0 .. length {
150 +
                assert bytes[i + 1] == pattern[i % width];
151 +
            }
152 +
        }
153 +
    }
154 +
}
lib/std/vec.rad +3 -3
2 2
//!
3 3
//! Users provide their own storage and the vector manages
4 4
//! element count within that arena. The arena should be aligned according
5 5
//! to the element type's requirements.
6 6
7 +
use std::mem;
8 +
7 9
/// Raw vector metadata structure.
8 10
///
9 11
/// Does not own storage, points to user-provided arena.
10 12
export record RawVec: Copy {
11 13
    /// Pointer to user-provided byte arena.
106 108
}
107 109
108 110
/// Copy bytes from source to destination.
109 111
fn copyBytes(dst: &mut [u8], src: &[u8]) {
110 112
    assert dst.len == src.len;
111 -
    for i in 0 .. src.len {
112 -
        set dst[i] = src[i];
113 -
    }
113 +
    try! mem::copy(dst, src);
114 114
}
std.lib +2 -0
75 75
lib/std/lang/il/link.rad
76 76
lib/std/lang/il/binary/linkage.rad
77 77
lib/std/lang/il/verify/linking.rad
78 78
lib/std/arch/rv64/vector.rad
79 79
lib/std/hash/blake3.ras
80 +
lib/std/mem.ras
81 +
lib/std/lang/gen/bitset.ras
test/runtime/kernel/dispatchcheck.rad +2 -2
28 28
/// ends, so cancellation covers unpublished native code and metadata.
29 29
constant FIRST_WINDOW_END: u64 = 6000000;
30 30
/// End of the controller's cancellation window.
31 31
constant CANCEL_WINDOW_END: u64 = 50000000;
32 32
/// End of the retry loader's first window.
33 -
constant RETRY_WINDOW_END: u64 = 60000000;
33 +
constant RETRY_WINDOW_END: u64 = 56000000;
34 34
/// End of the witness window.
35 -
constant WITNESS_WINDOW_END: u64 = 62000000;
35 +
constant WITNESS_WINDOW_END: u64 = 58000000;
36 36
/// End of the retry loader's final window.
37 37
constant FINAL_WINDOW_END: u64 = 300000000;
38 38
/// Duration of the final machine verification window.
39 39
constant CHECK_WINDOW: u64 = 10000000;
40 40
/// Maximum maintenance requests while reclaiming cancelled compiler storage.