tiny.choir.backends.aarch64.placement

1const std = @import("std");2const ir = @import("../../core/root.zig");3const shared = @import("../root.zig").regalloc;4const control = @import("root.zig").control;5const GPR = @import("root.zig").GPR;67pub const max_registers: usize = 7;8pub const max_frame_slots: usize = 64;9pub const max_live_values: usize = max_registers + max_frame_slots;10pub const max_values: usize = 256;11pub const max_operations: usize = 1024;12pub const max_events: usize = 3 * max_operations;13pub const Event = struct {14    pub const Kind = enum { operation, next_region, end };15    kind: Kind,16    op: *ir.Operation,17    depth: usize,18};19pub const slot_bytes: usize = 8;20pub const registers = [max_registers]GPR{ .x9, .x10, .x11, .x12, .x13, .x14, .x15 };2122pub const Location = union(enum) { register: GPR, stack: u16, dead };23pub const Error = control.Error || error{ ValueCapacity, FrameCapacity, OperationCapacity, MissingValue };2425const Entry = struct {26    value: *ir.Value,27    owner: *ir.Operation,28    retained: bool,29    range: shared.IntervalRange,30    location: Location = .dead,31};3233/// One immutable home per SSA result. Arguments retain their incoming homes.34pub const Plan = struct {35    entries: [max_values]Entry = undefined,36    count: usize = 0,37    events: [max_events]Event = undefined,38    event_count: usize = 0,39    loops: [max_operations]shared.LoopInterval = undefined,40    loop_count: usize = 0,41    frame_slots: usize = 0,42    entry_block: ?*ir.Block = null,43    refused_operation: ?*ir.Operation = null,4445    pub fn storageBytes() usize {46        return @sizeOf(Plan);47    }4849    pub fn frameBytes(self: *const Plan) usize {50        std.debug.assert(self.frame_slots <= max_frame_slots);51        return std.mem.alignForward(usize, self.frame_slots * slot_bytes, 16);52    }5354    pub fn get(self: *const Plan, value: *ir.Value) ?Location {55        std.debug.assert(self.count <= max_values);56        for (self.entries[0..self.count]) |entry| {57            if (entry.value == value) return entry.location;58        }59        return null;60    }6162    /// A fixed traversal stack linearizes regions without host recursion.63    /// Once loop boundaries exist, each actual source use reaches the shared64    /// loop extension through one borrowed record, without allocation.65    pub fn build(self: *Plan, block: *ir.Block) Error!void {66        self.* = .{ .entry_block = block };67        const Frame = struct { next: ?*ir.Operation, owner: ?*ir.Operation = null, region: usize = 0, entry: u32 = 0 };68        var frames: [control.max_depth + 1]Frame = undefined;69        frames[0] = .{ .next = first(block) };70        var depth: usize = 0;71        var operations: usize = 0;72        for (0..max_events) |_| {73            const frame = &frames[depth];74            if (frame.next) |op| {75                self.refused_operation = op;76                if (operations == max_operations) return error.OperationCapacity;77                operations += 1;78                frame.next = op.next_op;79                const position = self.appendEvent(.operation, op, depth);80                if (control.kind(op)) |construct| {81                    if (depth == control.max_depth) return error.DepthCapacity;82                    try control.validate(op, construct);83                    for (op.results.items) |*value| try self.define(value, op, position, true);84                    for (op.regions.items) |*region| {85                        for (region.getEntryBlock().?.arguments.items) |arg| try self.define(arg, op, position, true);86                    }87                    depth += 1;88                    frames[depth] = .{ .next = first(op.regions.items[0].getEntryBlock().?), .owner = op, .entry = position + 1 };89                } else {90                    if (op.regions.items.len != 0) return error.ControlShape;91                    for (op.results.items) |*value| try self.define(value, op, position, false);92                }93            } else if (frame.owner) |owner| {94                self.refused_operation = owner;95                frame.region += 1;96                if (frame.region < owner.regions.items.len) {97                    _ = self.appendEvent(.next_region, owner, depth - 1);98                    frame.next = first(owner.regions.items[frame.region].getEntryBlock().?);99                } else {100                    const position = self.appendEvent(.end, owner, depth - 1);101                    if (control.kind(owner).? != .conditional) {102                        std.debug.assert(self.loop_count < max_operations);103                        self.loops[self.loop_count] = .{ .entry = frame.entry, .trailing = position };104                        self.loop_count += 1;105                    }106                    for (owner.results.items) |*value| try self.use(value, position);107                    for (owner.regions.items) |*region| {108                        for (region.getEntryBlock().?.arguments.items) |arg| try self.use(arg, position);109                    }110                    if (control.kind(owner).? == .counted) {111                        try self.use(owner.operands.items[1].value, position);112                        try self.use(owner.operands.items[2].value, position);113                    }114                    depth -= 1;115                }116            } else break;117        } else unreachable;118        for (self.events[0..self.event_count], 0..) |event, position| {119            if (event.kind != .operation) continue;120            self.refused_operation = event.op;121            for (event.op.operands.items) |operand| try self.use(operand.value, @intCast(position));122        }123        try self.place();124        self.refused_operation = null;125    }126127    fn first(block: *ir.Block) ?*ir.Operation {128        return if (block.operations.head) |op| @ptrCast(@alignCast(op)) else null;129    }130131    fn appendEvent(self: *Plan, kind: Event.Kind, op: *ir.Operation, depth: usize) u32 {132        std.debug.assert(self.event_count < max_events);133        const position = self.event_count;134        self.events[position] = .{ .kind = kind, .op = op, .depth = depth };135        self.event_count += 1;136        return @intCast(position);137    }138139    fn define(self: *Plan, value: *ir.Value, owner: *ir.Operation, position: u32, retained: bool) Error!void {140        if (self.count == max_values) return error.ValueCapacity;141        self.entries[self.count] = .{142            .value = value,143            .owner = owner,144            .retained = retained,145            .range = .{ .start = position, .end = position, .end_phase = .definition },146        };147        self.count += 1;148    }149150    fn use(self: *Plan, value: *ir.Value, position: u32) Error!void {151        const entry = self.find(value) orelse {152            if (value.getOwnerBlock() == @as(*anyopaque, self.entry_block.?)) return;153            return error.MissingValue;154        };155        if (entry.range.start > position) return error.MissingValue;156        if (position >= entry.range.end) {157            entry.range.end = position;158            entry.range.end_phase = .source;159        }160        var use_storage = [_]shared.UsePosition(GPR, u32){.{ .point = shared.PositionPoint.source(position), .requirement = .any, .source_blockers = 0 }};161        var candidate = [_]shared.Candidate(GPR, u32){.{162            .value = value,163            .range = entry.range,164            .use_positions = .{ .items = &use_storage, .capacity = use_storage.len },165            .definition = .{ .point = shared.PositionPoint.definition(entry.range.start), .requirement = .any, .source = .any },166            .order = 0,167            .is_constant = false,168        }};169        shared.extendAcrossLoops(GPR, u32, &candidate, self.loops[0..self.loop_count]);170        entry.range = candidate[0].range;171    }172173    fn find(self: *Plan, value: *ir.Value) ?*Entry {174        for (self.entries[0..self.count]) |*entry| {175            if (entry.value == value) return entry;176        }177        return null;178    }179180    /// Shared interval expiration and register selection borrow stack storage.181    fn place(self: *Plan) Error!void {182        var active_storage: [max_registers]shared.Active(GPR) = undefined;183        var active: shared.ActiveSet(GPR) = .{184            .items = .{ .items = active_storage[0..0], .capacity = active_storage.len },185        };186        var stack_ends: [max_frame_slots]?shared.PositionPoint = @splat(null);187        for (self.entries[0..self.count], 0..) |*entry, index| {188            if (!entry.retained and entry.value.hasNoUses()) continue;189            self.refused_operation = entry.owner;190            const start = shared.PositionPoint.definition(entry.range.start);191            const end: shared.PositionPoint = .{ .position = entry.range.end, .phase = entry.range.end_phase };192            for (0..max_registers) |_| {193                if (active.takeExpiredBefore(start) == null) break;194            }195            if (shared.firstAvailableRegister(GPR, active, &registers, Policy{})) |register| {196                std.debug.assert(active.items.items.len < max_registers);197                active.items.appendAssumeCapacity(.{198                    .start = entry.range.start,199                    .end = entry.range.end,200                    .end_phase = entry.range.end_phase,201                    .reg = register,202                    .candidate_index = index,203                });204                entry.location = .{ .register = register };205                continue;206            }207            var placed = false;208            for (&stack_ends, 0..) |*last, slot| {209                if (last.*) |point| if (!point.lessThan(start)) continue;210                last.* = end;211                entry.location = .{ .stack = @intCast(slot) };212                self.frame_slots = @max(self.frame_slots, slot + 1);213                placed = true;214                break;215            }216            if (!placed) return error.FrameCapacity;217        }218    }219};220221const Policy = struct {222    pub fn blocksRegister(_: Policy, _: GPR) bool {223        return false;224    }225};

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