tiny.choir.backends.machine_code

1const std = @import("std");23const Allocator = std.mem.Allocator;45pub const CallRelocation = struct {6    offset: usize,7    target: []const u8,8};910pub const data_symbol_attr_names = struct {11    pub const name = "choir.backend.data_symbol.name";12    pub const bytes = "choir.backend.data_symbol.bytes";13    pub const alignment = "choir.backend.data_symbol.alignment";14};1516/// Largest alignment a data symbol may request.17/// A JIT data mapping starts on a page boundary, so an offset aligned within the mapping is also18/// aligned in memory for any alignment up to one page.19pub const max_data_alignment = 4096;2021pub const DataSymbolError = error{ InvalidDataSymbol, ConflictingDataSymbol };2223pub const DataSymbolBinding = enum {24    local,25    global,26};2728/// The section a data symbol lands in.29pub const DataSection = enum {30    /// Mapped read-only.31    rodata,32    /// Mapped writable, with the bytes the file carries.33    data,34    /// Mapped writable and zero, with no bytes in the file at all.35    bss,3637    /// Reports whether the object file carries this section's bytes.38    pub fn carriesBytes(self: DataSection) bool {39        return self != .bss;40    }41};4243/// Storage that code addresses by name.44///45/// A `.bss` symbol is the same kind as any other and differs only in where its bytes come from:46/// the loader supplies them, so the file carries none and `reserved_size` states the extent that47/// `bytes.len` cannot. Keeping one kind is what lets one `DataSymbolSet` hold every global a48/// module declares, whichever section it lands in.49pub const DataSymbol = struct {50    name: []const u8,51    /// Bytes the file carries verbatim. Empty exactly when the section is `.bss`.52    bytes: []const u8 = &.{},53    /// How many bytes the symbol occupies, when that is not the byte count.54    ///55    /// Absent means the size IS `bytes.len`, which is the only reading available for a section56    /// the file carries bytes for. It is required for `.bss`, where there are no bytes to count,57    /// and a zero here is a refusal rather than an empty symbol.58    reserved_size: ?usize = null,59    alignment: usize = 1,60    binding: DataSymbolBinding = .local,61    section: DataSection = .rodata,6263    /// The number of bytes the symbol occupies once loaded.64    pub fn size(self: DataSymbol) usize {65        return self.reserved_size orelse self.bytes.len;66    }6768    /// Reports whether the symbol has a nonempty name, a power-of-two alignment no larger than69    /// `max_data_alignment`, and content its section can hold: bytes for `.rodata` and `.data`,70    /// a stated nonzero size and no bytes for `.bss`.71    pub fn isValid(self: DataSymbol) bool {72        if (self.name.len == 0) return false;73        if (self.alignment == 0 or self.alignment > max_data_alignment) return false;74        if (!std.math.isPowerOfTwo(self.alignment)) return false;75        if (self.section.carriesBytes()) {76            if (self.bytes.len == 0) return false;77            if (self.reserved_size) |reserved| return reserved == self.bytes.len;78            return true;79        }80        if (self.bytes.len != 0) return false;81        const reserved = self.reserved_size orelse return false;82        return reserved != 0;83    }8485    pub fn eql(self: DataSymbol, other: DataSymbol) bool {86        return std.mem.eql(u8, self.name, other.name) and87            std.mem.eql(u8, self.bytes, other.bytes) and88            self.size() == other.size() and89            self.alignment == other.alignment and90            self.binding == other.binding and91            self.section == other.section;92    }93};9495/// Data symbols in first-insertion order, one per name.96/// The set borrows each symbol's name and bytes, so both must outlive the set.97pub const DataSymbolSet = struct {98    symbols: std.StringArrayHashMapUnmanaged(DataSymbol) = .empty,99100    pub fn deinit(self: *DataSymbolSet, allocator: Allocator) void {101        self.symbols.deinit(allocator);102        self.* = undefined;103    }104105    /// Adds `symbol` unless an equal symbol already holds its name.106    /// Fails when `symbol` is invalid, or when its name already holds different bytes,107    /// alignment, or binding.108    pub fn put(109        self: *DataSymbolSet,110        allocator: Allocator,111        symbol: DataSymbol,112    ) (Allocator.Error || DataSymbolError)!void {113        if (!symbol.isValid()) return error.InvalidDataSymbol;114        const entry = try self.symbols.getOrPut(allocator, symbol.name);115        if (!entry.found_existing) {116            entry.value_ptr.* = symbol;117            return;118        }119        if (!entry.value_ptr.eql(symbol)) return error.ConflictingDataSymbol;120    }121122    pub fn items(self: *const DataSymbolSet) []const DataSymbol {123        return self.symbols.values();124    }125126    pub fn indexOf(self: *const DataSymbolSet, name: []const u8) ?usize {127        return self.symbols.getIndex(name);128    }129130    pub fn clearRetainingCapacity(self: *DataSymbolSet) void {131        self.symbols.clearRetainingCapacity();132    }133};134135/// Places data symbols in order, each at the first offset after the previous symbol that its136/// alignment allows.137pub const DataLayout = struct {138    offsets: []usize,139    size: usize,140    alignment: usize,141142    pub const Error = Allocator.Error || error{ InvalidDataSymbol, DataTooLarge };143144    pub fn init(allocator: Allocator, symbols: []const DataSymbol) Error!DataLayout {145        const offsets = try allocator.alloc(usize, symbols.len);146        errdefer allocator.free(offsets);147        var size: usize = 0;148        var alignment: usize = 1;149        for (symbols, offsets) |symbol, *offset| {150            if (!symbol.isValid()) return error.InvalidDataSymbol;151            const mask = symbol.alignment - 1;152            const padded = std.math.add(usize, size, mask) catch return error.DataTooLarge;153            offset.* = padded & ~mask;154            std.debug.assert(offset.* >= size);155            std.debug.assert(std.mem.isAligned(offset.*, symbol.alignment));156            size = std.math.add(usize, offset.*, symbol.size()) catch return error.DataTooLarge;157            alignment = @max(alignment, symbol.alignment);158        }159        return .{ .offsets = offsets, .size = size, .alignment = alignment };160    }161162    pub fn deinit(self: *DataLayout, allocator: Allocator) void {163        allocator.free(self.offsets);164        self.* = undefined;165    }166167    /// Copies each symbol to its offset in `out` and zeroes the padding between symbols.168    ///169    /// A symbol whose section carries no bytes contributes none, and the memset above has170    /// already left its run at the zero the loader would have supplied.171    pub fn write(self: *const DataLayout, symbols: []const DataSymbol, out: []u8) void {172        std.debug.assert(symbols.len == self.offsets.len);173        std.debug.assert(out.len >= self.size);174        @memset(out[0..self.size], 0);175        for (symbols, self.offsets) |symbol, offset| {176            std.debug.assert(offset + symbol.size() <= self.size);177            @memcpy(out[offset..][0..symbol.bytes.len], symbol.bytes);178        }179    }180};181182pub const DataRelocation = struct {183    offset: usize,184    target: []const u8,185    addend: i64 = 0,186    width_bits: u16 = 64,187};188189pub const MachineCode = struct {190    code: []u8,191    relocations: []CallRelocation,192    data_symbols: []DataSymbol = &.{},193    data_relocations: []DataRelocation = &.{},194195    pub fn deinit(self: *MachineCode, allocator: Allocator) void {196        allocator.free(self.code);197        allocator.free(self.relocations);198        allocator.free(self.data_symbols);199        allocator.free(self.data_relocations);200    }201};202203test "data layouts pack symbols at their alignments" {204    const allocator = std.testing.allocator;205    const symbols = [_]DataSymbol{206        .{ .name = "string", .bytes = "abc", .alignment = 8 },207        .{ .name = "pair", .bytes = "xy", .alignment = 4 },208        .{ .name = "page", .bytes = "z", .alignment = max_data_alignment },209    };210    var layout = try DataLayout.init(allocator, &symbols);211    defer layout.deinit(allocator);212    try std.testing.expectEqualSlices(usize, &.{ 0, 4, max_data_alignment }, layout.offsets);213    try std.testing.expectEqual(@as(usize, max_data_alignment + 1), layout.size);214    try std.testing.expectEqual(@as(usize, max_data_alignment), layout.alignment);215216    var out: [max_data_alignment + 1]u8 = @splat(0xaa);217    layout.write(&symbols, &out);218    try std.testing.expectEqualSlices(u8, "abc\x00xy", out[0..6]);219    try std.testing.expect(std.mem.allEqual(u8, out[6..max_data_alignment], 0));220    try std.testing.expectEqual(@as(u8, 'z'), out[max_data_alignment]);221222    var empty = try DataLayout.init(allocator, &.{});223    defer empty.deinit(allocator);224    try std.testing.expectEqual(@as(usize, 0), empty.size);225    for ([_]usize{ 0, 3, 2 * max_data_alignment }) |alignment| {226        const invalid = [_]DataSymbol{.{ .name = "bad", .bytes = "abc", .alignment = alignment }};227        try std.testing.expectError(error.InvalidDataSymbol, DataLayout.init(allocator, &invalid));228    }229}230231test "data symbol sets keep one symbol per name" {232    const allocator = std.testing.allocator;233    var set: DataSymbolSet = .{};234    defer set.deinit(allocator);235    try set.put(allocator, .{ .name = "table", .bytes = "\x01\x02" });236    try set.put(allocator, .{ .name = "other", .bytes = "\x03", .alignment = 8 });237    try set.put(allocator, .{ .name = "table", .bytes = "\x01\x02" });238    try std.testing.expectEqual(@as(usize, 2), set.items().len);239    try std.testing.expectEqual(@as(?usize, 1), set.indexOf("other"));240241    const conflicts = [_]DataSymbol{242        .{ .name = "table", .bytes = "\x01\x03" },243        .{ .name = "table", .bytes = "\x01\x02", .alignment = 2 },244        .{ .name = "table", .bytes = "\x01\x02", .binding = .global },245    };246    for (conflicts) |conflict| {247        try std.testing.expectError(error.ConflictingDataSymbol, set.put(allocator, conflict));248    }249    const nameless = DataSymbol{ .name = "", .bytes = "\x01" };250    try std.testing.expectError(error.InvalidDataSymbol, set.put(allocator, nameless));251    try std.testing.expectEqual(@as(usize, 2), set.items().len);252    try std.testing.expectEqualSlices(u8, "\x01\x02", set.items()[0].bytes);253}

1pub const machine_code = @import("machine.zig");