lib/choir/src/backends/wasm/emission/plan/index.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ir = @import("../../../../core/root.zig");
3 const plan = @import("root.zig");
4
5 const empty = std.math.maxInt(u32);
6 const pointer_hash_multiplier: usize = switch (@bitSizeOf(usize)) {
7 32 => 0x9e3779b9,
8 64 => 0x9e3779b97f4a7c15,
9 else => @compileError("unsupported pointer width"),
10 };
11
12 pub fn slotsFor(count: usize) error{CapacityOverflow}!usize {
13 if (count == 0) return 0;
14 const scaled = std.math.mul(usize, count, 4) catch return error.CapacityOverflow;
15 const rounded = std.math.add(usize, scaled, 2) catch return error.CapacityOverflow;
16 const minimum = rounded / 3;
17 return std.math.ceilPowerOfTwo(usize, @max(@as(usize, 4), minimum)) catch
18 error.CapacityOverflow;
19 }
20
21 pub fn storageIsValid(entry_count: usize, slots: []const u32) bool {
22 const required = slotsFor(entry_count) catch return false;
23 return slots.len == required;
24 }
25
26 pub fn clear(slots: []u32) void {
27 @memset(slots, empty);
28 }
29
30 pub fn insertFunction(
31 slots: []u32,
32 functions: []const plan.FunctionPlan,
33 ordinal: u32,
34 ) error{ CodeGenFailed, InputChanged }!void {
35 var slot = hashBytes(functions[ordinal].name) & (slots.len - 1);
36 for (0..slots.len) |_| {
37 const existing = slots[slot];
38 if (existing == empty) {
39 slots[slot] = ordinal;
40 return;
41 }
42 if (std.mem.eql(u8, functions[existing].name, functions[ordinal].name)) {
43 return error.CodeGenFailed;
44 }
45 slot = advance(slot, slots.len);
46 }
47 return error.InputChanged;
48 }
49
50 pub fn insertValue(
51 slots: []u32,
52 values: []const plan.ValuePlan,
53 value_index: u32,
54 ) error{ CodeGenFailed, InputChanged }!void {
55 var slot = hashPointer(values[value_index].value) & (slots.len - 1);
56 for (0..slots.len) |_| {
57 const existing = slots[slot];
58 if (existing == empty) {
59 slots[slot] = value_index;
60 return;
61 }
62 if (values[existing].value == values[value_index].value) {
63 return error.CodeGenFailed;
64 }
65 slot = advance(slot, slots.len);
66 }
67 return error.InputChanged;
68 }
69
70 pub fn findFunction(
71 slots: []const u32,
72 functions: []const plan.FunctionPlan,
73 name: []const u8,
74 ) ?u32 {
75 if (slots.len == 0) return null;
76 var slot = hashBytes(name) & (slots.len - 1);
77 for (0..slots.len) |_| {
78 const ordinal = slots[slot];
79 if (ordinal == empty) return null;
80 const entry = functions[ordinal];
81 if (std.mem.eql(u8, name, entry.name)) return entry.function_index;
82 slot = advance(slot, slots.len);
83 }
84 return null;
85 }
86
87 pub fn findLocal(
88 slots: []const u32,
89 values: []const plan.ValuePlan,
90 function_plan: plan.FunctionPlan,
91 value: *ir.Value,
92 ) ?u32 {
93 if (slots.len == 0) return null;
94 const start: usize = function_plan.value_start;
95 const end = start + function_plan.value_count;
96 var slot = hashPointer(value) & (slots.len - 1);
97 for (0..slots.len) |_| {
98 const value_index = slots[slot];
99 if (value_index == empty) return null;
100 const entry = values[value_index];
101 if (entry.value == value) {
102 if (value_index < start or value_index >= end) return null;
103 return entry.local_index;
104 }
105 slot = advance(slot, slots.len);
106 }
107 return null;
108 }
109
110 fn advance(slot: usize, slot_count: usize) usize {
111 return (slot + 1) & (slot_count - 1);
112 }
113
114 fn hashBytes(bytes: []const u8) usize {
115 return @truncate(std.hash.Wyhash.hash(0, bytes));
116 }
117
118 fn hashPointer(value: *const ir.Value) usize {
119 return hashAddress(@intFromPtr(value));
120 }
121
122 fn hashAddress(address: usize) usize {
123 return std.math.rotl(
124 usize,
125 address *% pointer_hash_multiplier,
126 @bitSizeOf(usize) / 2,
127 );
128 }
129
130 test "WASM plan index capacity preserves its load bound" {
131 try std.testing.expectEqual(@as(usize, 0), try slotsFor(0));
132 try std.testing.expectEqual(@as(usize, 4), try slotsFor(1));
133 try std.testing.expectEqual(@as(usize, 4), try slotsFor(3));
134 try std.testing.expectEqual(@as(usize, 8), try slotsFor(4));
135 }
136
137 test "WASM plan index storage requires the exact derived capacity" {
138 var four: [4]u32 = undefined;
139 var eight: [8]u32 = undefined;
140
141 try std.testing.expect(storageIsValid(0, &.{}));
142 try std.testing.expect(storageIsValid(1, &four));
143 try std.testing.expect(storageIsValid(3, &four));
144 try std.testing.expect(storageIsValid(4, &eight));
145 try std.testing.expect(!storageIsValid(0, &four));
146 try std.testing.expect(!storageIsValid(1, &eight));
147 try std.testing.expect(!storageIsValid(4, &four));
148 try std.testing.expect(!storageIsValid(std.math.maxInt(usize), &.{}));
149 }
150
151 test "WASM plan index capacity rejects overflow" {
152 try std.testing.expectError(error.CapacityOverflow, slotsFor(std.math.maxInt(usize)));
153 }
154
155 test "WASM plan indices probe through function and value collisions" {
156 const names = [_][]const u8{ "a", "b", "c", "d", "e" };
157 var first_name_by_slot = @as([4]?usize, @splat(null));
158 var name_pair: ?[2]usize = null;
159 for (names, 0..) |name, name_index| {
160 const slot = hashBytes(name) & 3;
161 if (first_name_by_slot[slot]) |first_name| {
162 name_pair = .{ first_name, name_index };
163 break;
164 }
165 first_name_by_slot[slot] = name_index;
166 }
167 const colliding_names = name_pair.?;
168 const functions = [_]plan.FunctionPlan{
169 .{
170 .name = names[colliding_names[0]],
171 .value_start = 0,
172 .value_count = 0,
173 .param_count = 0,
174 .local_count = 0,
175 .function_index = 7,
176 .body_bytes = 0,
177 },
178 .{
179 .name = names[colliding_names[1]],
180 .value_start = 0,
181 .value_count = 0,
182 .param_count = 0,
183 .local_count = 0,
184 .function_index = 11,
185 .body_bytes = 0,
186 },
187 };
188 var function_slots: [4]u32 = undefined;
189 clear(&function_slots);
190 try insertFunction(&function_slots, &functions, 0);
191 try insertFunction(&function_slots, &functions, 1);
192 try std.testing.expectEqual(@as(?u32, 7), findFunction(&function_slots, &functions, functions[0].name));
193 try std.testing.expectEqual(@as(?u32, 11), findFunction(&function_slots, &functions, functions[1].name));
194
195 var raw_values: [5]ir.Value = undefined;
196 var first_value_by_slot = @as([4]?usize, @splat(null));
197 var value_pair: ?[2]usize = null;
198 for (&raw_values, 0..) |*value, value_index| {
199 const slot = hashPointer(value) & 3;
200 if (first_value_by_slot[slot]) |first_value| {
201 value_pair = .{ first_value, value_index };
202 break;
203 }
204 first_value_by_slot[slot] = value_index;
205 }
206 const colliding_values = value_pair.?;
207 const values = [_]plan.ValuePlan{
208 .{
209 .value = &raw_values[colliding_values[0]],
210 .local_index = 3,
211 .value_type = .i32,
212 },
213 .{
214 .value = &raw_values[colliding_values[1]],
215 .local_index = 5,
216 .value_type = .i32,
217 },
218 };
219 var value_slots: [4]u32 = undefined;
220 clear(&value_slots);
221 try insertValue(&value_slots, &values, 0);
222 try insertValue(&value_slots, &values, 1);
223 const function_plan = plan.FunctionPlan{
224 .name = "values",
225 .value_start = 0,
226 .value_count = 2,
227 .param_count = 0,
228 .local_count = 2,
229 .function_index = 0,
230 .body_bytes = 0,
231 };
232 try std.testing.expectEqual(
233 @as(?u32, 3),
234 findLocal(&value_slots, &values, function_plan, values[0].value),
235 );
236 try std.testing.expectEqual(
237 @as(?u32, 5),
238 findLocal(&value_slots, &values, function_plan, values[1].value),
239 );
240 }
241
242 test "WASM value pointer hash disperses aligned addresses" {
243 const slot_count = 512;
244 var values: [256]ir.Value = undefined;
245 var value_loads = @as([slot_count]u8, @splat(0));
246 for (&values) |*value| {
247 value_loads[hashPointer(value) & (slot_count - 1)] += 1;
248 }
249 for (value_loads) |load| try std.testing.expect(load <= 2);
250
251 for ([_]usize{ 8, 16, 32, 64, 128 }) |stride| {
252 var loads = @as([slot_count]u8, @splat(0));
253 for (0..256) |index| {
254 const address = 0x1000 + index * stride;
255 loads[hashAddress(address) & (slot_count - 1)] += 1;
256 }
257 for (loads) |load| try std.testing.expect(load <= 2);
258 }
259 }