std: Reduce vector lookup and hashing work

a1c086d31dd34e4cc3b5a696fe290463949d96ca803a81692d22606d10956f04
Keep BLAKE3 initialization, rounds, and output XORs in vector
registers. Load message blocks with byte-wide vector accesses to
support every input alignment. The matched 1 MiB digest uses
11,004,084 guest instructions instead of 16,417,837.

Use fixed-width bit intrinsics for bitset counts and iteration. Reject
scalar mnemonics and opcodes before scanning the vector instruction
table.

Assisted-by: Codex:gpt-6
Change-Id: I71e11779e978a3c0bb8a1168f05d6b68a82225c3
Alexis Sellier committed ago 1 parent a1d50b0e
lib/std/arch/rv64/vector.rad +14 -0
1 1
//! Integer vector instruction encodings for Zve64x and Zvbb.
2 2
3 3
use std::mem;
4 4
5 +
/// Opcode for vector arithmetic instructions.
6 +
export constant OP_VECTOR: u32 = 0x57;
7 +
/// Opcode for floating-point and vector load instructions.
8 +
export constant OP_LOAD_FP: u32 = 0x07;
9 +
/// Opcode for floating-point and vector store instructions.
10 +
export constant OP_STORE_FP: u32 = 0x27;
5 11
/// Number of vector registers in the instruction encoding.
6 12
export constant REGISTER_COUNT: u32 = 32;
7 13
/// Width of a split unsigned vector immediate.
8 14
export constant WIDE_IMMEDIATE_BITS: u32 = 6;
9 15
/// Minimum width of a vector type immediate.
672 678
    };
673 679
}
674 680
675 681
/// Find an instruction by its assembly mnemonic.
676 682
export fn find(mnemonic: *[u8]) -> ?Format {
683 +
    if mnemonic.len == 0 or mnemonic[0] <> 'v' {
684 +
        return nil;
685 +
    }
677 686
    for row in &ROWS[..] {
678 687
        if mem::eq(mnemonic, row.mnemonic) {
679 688
            return format(&row);
680 689
        }
681 690
    }
682 691
    return nil;
683 692
}
684 693
685 694
/// Decode fixed fields of an integer vector instruction.
686 695
export fn decode(word: u32) -> ?Format {
696 +
    // Integer vector instructions use OP-V, LOAD-FP and STORE-FP opcodes.
697 +
    let opcode = super::decode::opcode(word);
698 +
    if opcode <> OP_VECTOR and opcode <> OP_LOAD_FP and opcode <> OP_STORE_FP {
699 +
        return nil;
700 +
    }
687 701
    for row in &ROWS[..] {
688 702
        if (word & row.mask) == row.value {
689 703
            return format(&row);
690 704
        }
691 705
    }
lib/std/hash/blake3.rad +50 -50
3 3
@test export mod tests;
4 4
5 5
use std::bits;
6 6
use std::mem;
7 7
8 +
/// Number of bytes in one BLAKE3 compression block.
9 +
constant BLOCK_BYTES: u32 = 64;
10 +
/// Number of 32-bit words in one BLAKE3 compression block.
11 +
constant BLOCK_WORDS: u32 = BLOCK_BYTES / 4;
8 12
/// Number of bytes in a BLAKE3 digest.
9 13
export constant DIGEST_BYTES: u32 = 32;
10 14
11 15
/// Initial chaining words from the BLAKE3 specification.
12 16
constant IV: [u32; 8] = [
42 46
/// Compression input for a chunk block or a parent node.
43 47
record Output: Copy {
44 48
    /// Input chaining words.
45 49
    words: [u32; 8],
46 50
    /// Little-endian message words with zero padding.
47 -
    block: [u32; 16],
51 +
    block: [u32; BLOCK_WORDS],
48 52
    /// Chunk number, or zero for a parent or root output.
49 53
    counter: u64,
50 54
    /// Number of message bytes in the block.
51 55
    length: u32,
52 56
    /// Node and block flags.
56 60
/// Incremental state for a message shorter than 2^64 bytes.
57 61
export opaque record State {
58 62
    /// Current chunk chaining words.
59 63
    words: [u32; 8],
60 64
    /// Partial block, retained until more input or finalization.
61 -
    block: [u8; 64],
65 +
    block: [u8; BLOCK_BYTES],
62 66
    /// Number of initialized bytes in the block.
63 67
    used: u32,
64 68
    /// Number of compressed blocks in the current chunk, from zero to 15.
65 69
    blocks: u32,
66 70
    /// Current chunk number.
75 79
76 80
/// Initialize an unkeyed BLAKE3 message.
77 81
export fn new() -> State {
78 82
    return State {
79 83
        words: IV,
80 -
        block: [0; 64],
84 +
        block: [0; BLOCK_BYTES],
81 85
        used: 0,
82 86
        blocks: 0,
83 87
        counter: 0,
84 88
        length: 0,
85 89
        stack: [0; 432],
86 90
        depth: 0,
87 91
    };
88 92
}
89 93
90 -
/// Apply seven wrapping rounds to four rows of four 32-bit words.
91 -
/// The assembly routine reads 64 message bytes and updates 64 state bytes.
92 -
/// Each schedule offset must address one of the 16 message words.
93 -
unsafe fn rounds(state: &mut [u32; 16], message: &[u32; 16], schedule: *u32);
94 +
/// Compress one block into eight output words with seven wrapping rounds.
95 +
/// The input arrays must be initialized. The metadata contains the counter
96 +
/// halves, block length and flags. The schedule must contain 112 offsets,
97 +
/// each of which addresses a message word. All result words are written.
98 +
unsafe fn compressWords(
99 +
    result: &mut [u32; 8],
100 +
    words: &[u32; 8],
101 +
    message: &[u32; BLOCK_WORDS],
102 +
    metadata: &[u32; 4],
103 +
    iv: &[u32; 8],
104 +
    schedule: *u32
105 +
);
106 +
107 +
/// Read exactly 64 bytes into little-endian message words.
108 +
/// The input address must provide 64 readable bytes. It can be unaligned.
109 +
unsafe fn loadBlock(result: &mut [u32; BLOCK_WORDS], bytes: &u8);
94 110
95 111
/// Compress a node and return its first eight output words.
96 112
fn compress(input: &Output) -> [u32; 8] {
97 -
    let mut state: [u32; 16] = [
98 -
        input.words[0], input.words[1], input.words[2], input.words[3],
99 -
        input.words[4], input.words[5], input.words[6], input.words[7],
100 -
        IV[0], IV[1], IV[2], IV[3], input.counter as u32,
101 -
        (input.counter >> 32) as u32, input.length, input.flags,
113 +
    let metadata: [u32; 4] = [
114 +
        input.counter as u32, (input.counter >> 32) as u32,
115 +
        input.length, input.flags,
102 116
    ];
117 +
    let mut result: [u32; 8] = undefined;
103 118
    unsafe {
104 -
        rounds(&mut state, &input.block, SCHEDULE.ptr);
119 +
        compressWords(
120 +
            &mut result, &input.words, &input.block, &metadata, &IV, SCHEDULE.ptr
121 +
        );
105 122
    }
106 -
    return [
107 -
        state[0] ^ state[8], state[1] ^ state[9],
108 -
        state[2] ^ state[10], state[3] ^ state[11],
109 -
        state[4] ^ state[12], state[5] ^ state[13],
110 -
        state[6] ^ state[14], state[7] ^ state[15],
111 -
    ];
123 +
    return result;
112 124
}
113 125
114 126
/// Read one complete block as little-endian words.
115 -
fn readBlock(bytes: &[u8]) -> [u32; 16] {
116 -
    return [
117 -
        mem::load32Le(bytes, 0),
118 -
        mem::load32Le(bytes, 4),
119 -
        mem::load32Le(bytes, 8),
120 -
        mem::load32Le(bytes, 12),
121 -
        mem::load32Le(bytes, 16),
122 -
        mem::load32Le(bytes, 20),
123 -
        mem::load32Le(bytes, 24),
124 -
        mem::load32Le(bytes, 28),
125 -
        mem::load32Le(bytes, 32),
126 -
        mem::load32Le(bytes, 36),
127 -
        mem::load32Le(bytes, 40),
128 -
        mem::load32Le(bytes, 44),
129 -
        mem::load32Le(bytes, 48),
130 -
        mem::load32Le(bytes, 52),
131 -
        mem::load32Le(bytes, 56),
132 -
        mem::load32Le(bytes, 60),
133 -
    ];
127 +
fn readBlock(bytes: &[u8]) -> [u32; BLOCK_WORDS] {
128 +
    assert bytes.len >= BLOCK_BYTES;
129 +
    let mut result: [u32; BLOCK_WORDS] = undefined;
130 +
    unsafe {
131 +
        loadBlock(&mut result, bytes.ptr);
132 +
    }
133 +
    return result;
134 134
}
135 135
136 136
/// Join two subtree values into a parent compression input.
137 137
fn parent(left: &[u32], right: &[u32]) -> Output {
138 -
    let mut block: [u32; 16] = [0; 16];
138 +
    let mut block: [u32; BLOCK_WORDS] = [0; BLOCK_WORDS];
139 139
    for i in 0 as u32 .. 8 {
140 140
        set block[i] = left[i];
141 141
        set block[i + 8] = right[i];
142 142
    }
143 -
    return Output { words: IV, block, counter: 0, length: 64, flags: PARENT };
143 +
    return Output { words: IV, block, counter: 0, length: BLOCK_BYTES, flags: PARENT };
144 144
}
145 145
146 146
/// Add message bytes. The complete message must be shorter than 2^64 bytes.
147 147
export fn update(state: &mut State, bytes: &[u8]) {
148 -
    assert bytes.len as u64 <= 0xffffffffffffffff - state.length;
148 +
    assert bytes.len as u64 <= mem::U64_MAX - state.length;
149 149
    set state.length += bytes.len as u64;
150 150
    let mut offset: u32 = 0;
151 151
    while offset < bytes.len {
152 152
        let flags = CHUNK_START if state.blocks == 0 else 0;
153 -
        if state.used == 64 {
153 +
        if state.used == BLOCK_BYTES {
154 154
            let mut output = Output {
155 155
                words: state.words,
156 156
                block: readBlock(&state.block[..]),
157 157
                counter: state.counter,
158 -
                length: 64,
158 +
                length: BLOCK_BYTES,
159 159
                flags,
160 160
            };
161 161
            if state.blocks == 15 {
162 162
                set output.flags |= CHUNK_END;
163 163
                let mut value = compress(&output);
182 182
            }
183 183
            set state.used = 0;
184 184
            continue;
185 185
        }
186 186
        // Full nonfinal blocks can be read from the input slice.
187 -
        if state.used == 0 and bytes.len - offset > 64 and state.blocks < 15 {
187 +
        if state.used == 0 and bytes.len - offset > BLOCK_BYTES and state.blocks < 15 {
188 188
            set state.words = compress(&Output {
189 189
                words: state.words,
190 -
                block: readBlock(&bytes[offset .. offset + 64]),
190 +
                block: readBlock(&bytes[offset .. offset + BLOCK_BYTES]),
191 191
                counter: state.counter,
192 -
                length: 64,
192 +
                length: BLOCK_BYTES,
193 193
                flags,
194 194
            });
195 195
            set state.blocks += 1;
196 -
            set offset += 64;
196 +
            set offset += BLOCK_BYTES;
197 197
            continue;
198 198
        }
199 -
        let space = 64 - state.used;
199 +
        let space = BLOCK_BYTES - state.used;
200 200
        let remaining = bytes.len - offset;
201 201
        let count = remaining if remaining < space else space;
202 202
        try! mem::copy(
203 203
            &mut state.block[state.used .. state.used + count], &bytes[offset .. offset + count]
204 204
        );
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 .. 64 {
213 +
    for i in state.used .. BLOCK_BYTES {
214 214
        set state.block[i] = 0;
215 215
    }
216 216
    let flags = CHUNK_END | (CHUNK_START if state.blocks == 0 else 0);
217 217
    let mut output = Output {
218 218
        words: state.words,
228 228
        set output = parent(&state.stack[start .. start + 8], &right[..]);
229 229
    }
230 230
    set output.counter = 0;
231 231
    set output.flags |= ROOT;
232 232
    let words = compress(&output);
233 -
    let mut result = Digest { bytes: [0; 32] };
233 +
    let mut result = Digest { bytes: [0; DIGEST_BYTES] };
234 234
    for word, i in &words[..] {
235 235
        mem::store32Le(&mut result.bytes[..], i * 4, word);
236 236
    }
237 237
    return result;
238 238
}
lib/std/hash/blake3.ras +46 -42
1 -
//! Four-lane BLAKE3 rounds with Zve64x and Zvbb.
2 -
// a0 addresses 16 writable state words; a1 addresses 16 message words.
3 -
// a2 addresses 112 message offsets, four per vector load.
4 -
// m2 provides four 32-bit lanes when VLEN is at least 64 bits.
5 -
// Vector registers, vl and vtype are caller-saved.
6 -
// BLAKE3 compression rounds and mixing rotations.
1 +
//! Four-lane BLAKE3 compression with Zve64x and Zvbb.
2 +
// Vector registers, vl and vtype are caller-saved. VLEN must be at least 64.
3 +
// BLAKE3 compression block size and number of rounds.
4 +
.constant BLOCK_BYTES 64;
7 5
.constant ROUNDS 7;
6 +
// Right rotations in one BLAKE3 mixing operation.
8 7
.constant ROTATE_FIRST 16;
9 8
.constant ROTATE_SECOND 12;
10 9
.constant ROTATE_THIRD 8;
11 10
.constant ROTATE_FOURTH 7;
12 11
.text;
13 -
.export @"std::hash::blake3::rounds";
14 -
@"std::hash::blake3::rounds"
12 +
// a0 addresses 64 writable bytes; a1 addresses 64 readable bytes.
13 +
.export @"std::hash::blake3::loadBlock";
14 +
@"std::hash::blake3::loadBlock"
15 +
    li %t0 BLOCK_BYTES;
16 +
    vsetvli %zero %t0 e8 m8 ta ma;
17 +
    vle8.v %v8 (%a1);
18 +
    vse8.v %v8 (%a0);
19 +
    ret;
20 +
21 +
// a0 addresses eight output words; a1 addresses eight chaining words.
22 +
// a2 addresses 16 message words; a3 addresses four metadata words.
23 +
// a4 addresses four IV words; a5 addresses 112 message offsets.
24 +
// m2 provides four 32-bit lanes when VLEN is at least 64 bits.
25 +
.export @"std::hash::blake3::compressWords";
26 +
@"std::hash::blake3::compressWords"
15 27
    vsetivli %zero 4 e32 m2 ta ma;
16 -
    vle32.v %v8 (%a0);
17 -
    addi %t0 %a0 16;
28 +
    vle32.v %v8 (%a1);
29 +
    addi %t0 %a1 16;
18 30
    vle32.v %v10 (%t0);
19 -
    addi %t0 %t0 16;
20 -
    vle32.v %v12 (%t0);
21 -
    addi %t0 %t0 16;
22 -
    vle32.v %v14 (%t0);
31 +
    vle32.v %v12 (%a4);
32 +
    vle32.v %v14 (%a3);
33 +
    mv %a1 %a2;
34 +
    mv %a2 %a5;
23 35
    // Lane indices for left rotations by one, two and three words.
24 36
    vid.v %v2;
25 37
    vadd.vi %v4 %v2 2;
26 38
    vand.vi %v4 %v4 3;
27 39
    vadd.vi %v6 %v2 3;
49 61
    vxor.vv %v14 %v14 %v8;
50 62
    vror.vi %v14 %v14 ROTATE_THIRD;
51 63
    vadd.vv %v12 %v12 %v14;
52 64
    vxor.vv %v10 %v10 %v12;
53 65
    vror.vi %v10 %v10 ROTATE_FOURTH;
54 -
    vrgather.vv %v24 %v10 %v2;
55 -
    vmv.v.v %v10 %v24;
56 -
    vrgather.vv %v24 %v12 %v4;
57 -
    vmv.v.v %v12 %v24;
58 -
    vrgather.vv %v24 %v14 %v6;
59 -
    vmv.v.v %v14 %v24;
66 +
    vrgather.vv %v16 %v10 %v2;
67 +
    vrgather.vv %v18 %v12 %v4;
68 +
    vrgather.vv %v20 %v14 %v6;
60 69
    vle32.v %v24 (%a2);
61 70
    addi %a2 %a2 16;
62 71
    vluxei32.v %v26 (%a1) %v24;
63 -
    vadd.vv %v8 %v8 %v10;
72 +
    vadd.vv %v8 %v8 %v16;
64 73
    vadd.vv %v8 %v8 %v26;
65 -
    vxor.vv %v14 %v14 %v8;
66 -
    vror.vi %v14 %v14 ROTATE_FIRST;
67 -
    vadd.vv %v12 %v12 %v14;
68 -
    vxor.vv %v10 %v10 %v12;
69 -
    vror.vi %v10 %v10 ROTATE_SECOND;
74 +
    vxor.vv %v20 %v20 %v8;
75 +
    vror.vi %v20 %v20 ROTATE_FIRST;
76 +
    vadd.vv %v18 %v18 %v20;
77 +
    vxor.vv %v16 %v16 %v18;
78 +
    vror.vi %v16 %v16 ROTATE_SECOND;
70 79
    vle32.v %v24 (%a2);
71 80
    addi %a2 %a2 16;
72 81
    vluxei32.v %v26 (%a1) %v24;
73 -
    vadd.vv %v8 %v8 %v10;
82 +
    vadd.vv %v8 %v8 %v16;
74 83
    vadd.vv %v8 %v8 %v26;
75 -
    vxor.vv %v14 %v14 %v8;
76 -
    vror.vi %v14 %v14 ROTATE_THIRD;
77 -
    vadd.vv %v12 %v12 %v14;
78 -
    vxor.vv %v10 %v10 %v12;
79 -
    vror.vi %v10 %v10 ROTATE_FOURTH;
84 +
    vxor.vv %v20 %v20 %v8;
85 +
    vror.vi %v20 %v20 ROTATE_THIRD;
86 +
    vadd.vv %v18 %v18 %v20;
87 +
    vxor.vv %v16 %v16 %v18;
88 +
    vror.vi %v16 %v16 ROTATE_FOURTH;
80 89
    // Restore row order before the next column phase.
81 -
    vrgather.vv %v24 %v10 %v6;
82 -
    vmv.v.v %v10 %v24;
83 -
    vrgather.vv %v24 %v12 %v4;
84 -
    vmv.v.v %v12 %v24;
85 -
    vrgather.vv %v24 %v14 %v2;
86 -
    vmv.v.v %v14 %v24;
90 +
    vrgather.vv %v10 %v16 %v6;
91 +
    vrgather.vv %v12 %v18 %v4;
92 +
    vrgather.vv %v14 %v20 %v2;
87 93
    addi %t1 %t1 -1;
88 94
    bnez %t1 @round;
95 +
    vxor.vv %v8 %v8 %v12;
96 +
    vxor.vv %v10 %v10 %v14;
89 97
    vse32.v %v8 (%a0);
90 98
    addi %t0 %a0 16;
91 99
    vse32.v %v10 (%t0);
92 -
    addi %t0 %t0 16;
93 -
    vse32.v %v12 (%t0);
94 -
    addi %t0 %t0 16;
95 -
    vse32.v %v14 (%t0);
96 100
    ret;
lib/std/lang/gen/bitset.rad +5 -32
2 2
//!
3 3
//! Provides efficient bit-level set operations for tracking live registers
4 4
//! during liveness analysis and register allocation.
5 5
@test mod tests;
6 6
7 +
use std::bits;
7 8
use std::lang::alloc;
8 9
use std::mem::heap;
9 10
10 11
/// Return the minimum of two 32-bit values.
11 12
fn min(a: u32, b: u32) -> u32 {
77 78
    let mut total: u32 = 0;
78 79
    let numWords = bs.bits.len;
79 80
    for i in 0 .. numWords {
80 81
        let word = bs.bits[i];
81 82
        if word <> 0 {
82 -
            set total += popCount(word);
83 +
            set total += bits::popCount32(word);
83 84
        }
84 85
    }
85 86
    return total;
86 87
}
87 88
89 90
export fn countCommon(a: &Bitset, b: &Bitset) -> u32 {
90 91
    let mut total: u32 = 0;
91 92
    for i in 0 .. min(a.bits.len, b.bits.len) {
92 93
        let word = a.bits[i] & b.bits[i];
93 94
        if word <> 0 {
94 -
            set total += popCount(word);
95 +
            set total += bits::popCount32(word);
95 96
        }
96 97
    }
97 98
    return total;
98 99
}
99 100
100 -
/// Population count for a 32-bit word.
101 -
fn popCount(x: u32) -> u32 {
102 -
    let mut n = x;
103 -
    set n -= (n >> 1) & 0x55555555;
104 -
    set n = (n & 0x33333333) + ((n >> 2) & 0x33333333);
105 -
    set n = (n + (n >> 4)) & 0x0F0F0F0F;
106 -
    set n += n >> 8;
107 -
    set n += n >> 16;
108 -
109 -
    return n & 0x3F;
110 -
}
111 -
112 101
/// Union: `dst = dst | src`.
113 102
export fn union_(dst: &mut Bitset, src: &Bitset) {
114 103
    let numWords = dst.bits.len;
115 104
    let srcWords = src.bits.len;
116 105
    let minWords = min(numWords, srcWords);
203 192
        if it.wordIdx >= numWords {
204 193
            return nil;
205 194
        }
206 195
        set it.remaining = bs.bits[it.wordIdx];
207 196
    }
208 -
    // Find lowest set bit position using de Bruijn sequence.
209 -
    let b = ctz(it.remaining);
197 +
    // Find the lowest set bit position.
198 +
    let b = bits::trailingZeros32(it.remaining);
210 199
    let n = it.wordIdx * 32 + b;
211 200
    if n >= bs.len {
212 201
        return nil;
213 202
    }
214 203
    // Clear the lowest set bit.
215 204
    set it.remaining &= it.remaining - 1;
216 205
217 206
    return n;
218 207
}
219 -
220 -
/// Count trailing zeros in a 32-bit value.
221 -
/// Returns the bit position of the lowest set bit (0-31).
222 -
/// Behavior is undefined if `x` is 0.
223 -
fn ctz(x: u32) -> u32 {
224 -
    // De Bruijn sequence for 32-bit CTZ.
225 -
    constant DEBRUIJN: u32 = 0x077CB531;
226 -
    constant TABLE: [u8; 32] = [
227 -
        0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
228 -
        31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9,
229 -
    ];
230 -
    // Isolate lowest set bit, multiply by de Bruijn constant, look up.
231 -
    let isolated = x & (~x + 1);
232 -
233 -
    return TABLE[(isolated * DEBRUIJN) >> 27] as u32;
234 -
}