tiny.choir.backends.wasm.emission.plan

1const std = @import("std");2const ir = @import("../../../../core/root.zig");3const plan = @import("root.zig");45const empty = std.math.maxInt(u32);6const pointer_hash_multiplier: usize = switch (@bitSizeOf(usize)) {7    32 => 0x9e3779b9,8    64 => 0x9e3779b97f4a7c15,9    else => @compileError("unsupported pointer width"),10};1112pub 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)) catch18        error.CapacityOverflow;19}2021pub fn storageIsValid(entry_count: usize, slots: []const u32) bool {22    const required = slotsFor(entry_count) catch return false;23    return slots.len == required;24}2526pub fn clear(slots: []u32) void {27    @memset(slots, empty);28}2930pub 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}4950pub 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}6970pub 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}8687pub 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}109110fn advance(slot: usize, slot_count: usize) usize {111    return (slot + 1) & (slot_count - 1);112}113114fn hashBytes(bytes: []const u8) usize {115    return @truncate(std.hash.Wyhash.hash(0, bytes));116}117118fn hashPointer(value: *const ir.Value) usize {119    return hashAddress(@intFromPtr(value));120}121122fn hashAddress(address: usize) usize {123    return std.math.rotl(124        usize,125        address *% pointer_hash_multiplier,126        @bitSizeOf(usize) / 2,127    );128}129130test "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}136137test "WASM plan index storage requires the exact derived capacity" {138    var four: [4]u32 = undefined;139    var eight: [8]u32 = undefined;140141    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}150151test "WASM plan index capacity rejects overflow" {152    try std.testing.expectError(error.CapacityOverflow, slotsFor(std.math.maxInt(usize)));153}154155test "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));194195    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}241242test "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);250251    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}

1const binary = @import("../../binary/root.zig");2const ir = @import("../../../../core/root.zig");3const emission = @import("../root.zig");45pub const index = @import("index.zig");6pub const planning = @import("planning.zig");78pub const FunctionPlan = struct {9    name: []const u8,10    value_start: u32,11    value_count: u32,12    param_count: u32,13    local_count: u32,14    function_index: u32,15    body_bytes: usize,16};1718pub const ValuePlan = struct {19    value: *ir.Value,20    local_index: u32,21    value_type: binary.ValueType,22};2324pub const Plan = struct {25    functions: []FunctionPlan,26    function_index: []u32,27    values: []ValuePlan,28    value_index: []u32,29    import_count: usize,30    definition_count: usize,31    needs_memory: bool,32    sections: emission.SectionSizes,3334    pub fn functionIndex(self: *const Plan, name: []const u8) ?u32 {35        return index.findFunction(self.function_index, self.functions, name);36    }3738    pub fn localFor(self: *const Plan, function_ordinal: usize, value: *ir.Value) ?u32 {39        if (function_ordinal >= self.functions.len) return null;40        return index.findLocal(41            self.value_index,42            self.values,43            self.functions[function_ordinal],44            value,45        );46    }4748    pub fn localPlans(self: *const Plan, function_ordinal: usize) []const ValuePlan {49        const function_plan = self.functions[function_ordinal];50        const start: usize = function_plan.value_start + function_plan.param_count;51        const end = start + function_plan.local_count;52        return self.values[start..end];53    }5455    pub fn functionCount(self: *const Plan) usize {56        return self.functions.len;57    }5859    pub fn importCount(self: *const Plan) usize {60        return self.import_count;61    }6263    pub fn definitionCount(self: *const Plan) usize {64        return self.definition_count;65    }6667    pub fn localCount(self: *const Plan, function_ordinal: usize) usize {68        return self.functions[function_ordinal].local_count;69    }7071    pub fn bodyBytes(self: *const Plan, function_ordinal: usize) usize {72        return self.functions[function_ordinal].body_bytes;73    }7475    pub fn needsMemory(self: *const Plan) bool {76        return self.needs_memory;77    }78};

1pub const plan = @import("plan/root.zig");