tiny.choir.Block

1pub const Block = struct {2    allocator: std.mem.Allocator,34    /// Values keep their addresses until the block is deinitialized.5    arguments: std.ArrayList(*Value),67    argument_locations: std.ArrayList(Location),89    operations: OperationList,1011    parent: ?*anyopaque,1213    prev: ?*Block,14    next: ?*Block,1516    id: u32,1718    predecessors: std.ArrayList(*Block),1920    op_order_valid: bool,2122    pub const order_stride: u32 = 8;23    pub const order_query_scan_limit: u8 = 8;2425    pub const OperationList = struct {26        head: ?*anyopaque,27        tail: ?*anyopaque,2829        pub fn init() OperationList {30            return .{31                .head = null,32                .tail = null,33            };34        }3536        pub fn isEmpty(self: OperationList) bool {37            return self.head == null;38        }39    };4041    pub const OperationIterator = struct {42        current: ?*anyopaque,4344        pub fn next(self: *OperationIterator) ?*@import("operation/root.zig").Operation {45            const op_any = self.current orelse return null;46            const op: *@import("operation/root.zig").Operation = @ptrCast(@alignCast(op_any));47            self.current = op.next_op;48            return op;49        }50    };5152    pub fn init(allocator: std.mem.Allocator) Block {53        return .{54            .allocator = allocator,55            .arguments = .empty,56            .argument_locations = .empty,57            .operations = OperationList.init(),58            .parent = null,59            .prev = null,60            .next = null,61            .id = 0,62            .predecessors = .empty,63            .op_order_valid = true,64        };65    }6667    fn recomputeOpOrder(self: *Block) void {68        var next_order: u32 = 0;69        var current = self.operations.head;70        while (current) |node| {71            const op: *@import("operation/root.zig").Operation = @ptrCast(@alignCast(node));72            op.order = next_order;73            next_order +|= order_stride;74            current = op.next_op;75        }76        self.op_order_valid = true;77    }7879    pub fn sealOperationOrder(self: *Block) bool {80        if (self.op_order_valid) return false;81        self.recomputeOpOrder();82        return true;83    }8485    pub fn operationPrecedes(86        self: *Block,87        first: *const @import("operation/root.zig").Operation,88        second: *const @import("operation/root.zig").Operation,89    ) bool {90        std.debug.assert(first.parent_block == self);91        std.debug.assert(second.parent_block == self);9293        if (self.op_order_valid) return first.order < second.order;9495        var next = first.next_op;96        var previous = first.prev_op;97        var scanned: u8 = 0;98        while (scanned < order_query_scan_limit) : (scanned += 1) {99            if (next) |op| {100                if (op == second) return true;101                next = op.next_op;102            }103            if (previous) |op| {104                if (op == second) return false;105                previous = op.prev_op;106            }107        }108109        _ = self.sealOperationOrder();110        return first.order < second.order;111    }112113    pub fn deinit(self: *Block) void {114        for (self.arguments.items) |argument| self.allocator.destroy(argument);115        self.arguments.deinit(self.allocator);116        self.argument_locations.deinit(self.allocator);117        self.predecessors.deinit(self.allocator);118    }119120    pub fn addArgument(self: *Block, arg_type: Type, loc: Location) !*Value {121        const arg_num: u32 = @intCast(self.arguments.items.len);122        const value = try self.allocator.create(Value);123        errdefer self.allocator.destroy(value);124        value.* = .{125            .kind = .{ .block_argument = .{126                .owner = self,127                .arg_number = arg_num,128            } },129            .type = arg_type,130            .id = 0,131        };132        try self.argument_locations.append(self.allocator, loc);133        errdefer _ = self.argument_locations.pop();134        try self.arguments.append(self.allocator, value);135        return self.arguments.items[self.arguments.items.len - 1];136    }137138    pub fn getArgumentLocation(self: *const Block, index: usize) ?Location {139        if (index >= self.argument_locations.items.len) return null;140        return self.argument_locations.items[index];141    }142143    pub fn setArgumentLocation(self: *Block, index: usize, loc: Location) void {144        std.debug.assert(index < self.argument_locations.items.len);145        self.argument_locations.items[index] = loc;146    }147148    pub fn getNumArguments(self: Block) usize {149        return self.arguments.items.len;150    }151152    pub fn getArgument(self: *Block, index: usize) ?*Value {153        if (index >= self.arguments.items.len) return null;154        return self.arguments.items[index];155    }156157    pub fn empty(self: Block) bool {158        return self.operations.isEmpty();159    }160161    pub fn dropAllReferences(self: *Block) void {162        var ops = self.getOperations();163        while (ops.next()) |op| {164            op.dropAllReferences();165        }166    }167168    pub fn hasNoDefinedValueUses(self: *Block) bool {169        for (self.arguments.items) |argument| {170            if (!argument.hasNoUses()) return false;171        }172173        var ops = self.getOperations();174        while (ops.next()) |op| {175            if (!op.hasNoDefinedValueUses()) return false;176        }177        return true;178    }179180    pub fn dropAllDefinedValueUses(self: *Block) void {181        for (self.arguments.items) |argument| {182            argument.dropAllUses();183        }184185        var ops = self.getOperations();186        while (ops.next()) |op| {187            op.dropAllDefinedValueUses();188        }189    }190191    pub fn getOperations(self: *Block) OperationIterator {192        return .{ .current = self.operations.head };193    }194195    pub fn walkOperations(196        self: *Block,197        options: @import("operation/root.zig").Operation.WalkOptions,198        context: anytype,199        callback: anytype,200    ) anyerror!@import("operation/root.zig").Operation.WalkResult {201        var ops = self.getOperations();202        while (ops.next()) |op| {203            const result = try op.walk(options, context, callback);204            if (result.wasInterrupted()) return .interrupt;205        }206        return .advance;207    }208209    pub fn getParentRegion(self: *const Block) ?*@import("region.zig").Region {210        const parent = self.parent orelse return null;211        return @ptrCast(@alignCast(parent));212    }213214    pub fn getParentOperation(self: *const Block) ?*@import("operation/root.zig").Operation {215        const region = self.getParentRegion() orelse return null;216        return region.getParentOperation();217    }218219    pub fn hasNoPredecessors(self: Block) bool {220        return self.predecessors.items.len == 0;221    }222223    pub fn getNumPredecessors(self: Block) usize {224        return self.predecessors.items.len;225    }226227    pub fn getPredecessors(self: *const Block) []const *Block {228        return self.predecessors.items;229    }230231    pub fn getPredecessor(self: Block, index: usize) ?*Block {232        if (index >= self.predecessors.items.len) return null;233        return self.predecessors.items[index];234    }235236    pub fn hasPredecessor(self: Block, pred: *Block) bool {237        for (self.predecessors.items) |existing| {238            if (existing == pred) return true;239        }240        return false;241    }242243    pub fn getTerminator(self: Block) ?*anyopaque {244        return self.operations.tail;245    }246247    pub fn addOperation(self: *Block, op: anytype) !void {248        const Operation = @import("operation/root.zig").Operation;249        const op_ptr: *Operation = @ptrCast(@alignCast(op));250        if (op_ptr.parent_block != null or op_ptr.prev_op != null or op_ptr.next_op != null) {251            return error.OperationAlreadyInserted;252        }253254        try cfg.attach(self, op_ptr);255256        op_ptr.parent_block = self;257258        if (self.operations.tail) |tail| {259            const tail_op: *Operation = @ptrCast(@alignCast(tail));260            tail_op.next_op = op_ptr;261            op_ptr.prev_op = tail_op;262            if (self.op_order_valid) {263                if (tail_op.order <= std.math.maxInt(u32) - order_stride) {264                    op_ptr.order = tail_op.order + order_stride;265                } else {266                    self.op_order_valid = false;267                }268            }269        } else {270            self.operations.head = op_ptr;271            if (self.op_order_valid) op_ptr.order = 0;272        }273        self.operations.tail = op_ptr;274    }275276    pub fn insertBefore(self: *Block, op: anytype, before: anytype) !void {277        const Operation = @import("operation/root.zig").Operation;278        const before_op: *Operation = @ptrCast(@alignCast(before));279        const op_ptr: *Operation = @ptrCast(@alignCast(op));280        if (before_op.parent_block != self) return error.OperationInsertBeforeDetached;281        if (op_ptr.parent_block != null or op_ptr.prev_op != null or op_ptr.next_op != null) {282            return error.OperationAlreadyInserted;283        }284285        try cfg.attach(self, op_ptr);286287        op_ptr.parent_block = self;288289        const prev = before_op.prev_op;290        op_ptr.prev_op = prev;291        op_ptr.next_op = before_op;292        before_op.prev_op = op_ptr;293294        if (prev) |prev_op| {295            prev_op.next_op = op_ptr;296        } else {297            self.operations.head = op_ptr;298        }299300        if (self.op_order_valid) {301            const low: u64 = if (prev) |prev_op| @as(u64, prev_op.order) + 1 else 0;302            const high: u64 = before_op.order;303            if (high > low) {304                op_ptr.order = @intCast(low + (high - low) / 2);305            } else {306                self.op_order_valid = false;307            }308        }309    }310311    fn unlinkOperation(self: *Block, op_ptr: *@import("operation/root.zig").Operation) bool {312        if (op_ptr.parent_block == null) return false;313        std.debug.assert(op_ptr.parent_block == self);314315        cfg.detach(self, op_ptr);316317        const prev = op_ptr.prev_op;318        const next = op_ptr.next_op;319320        if (prev) |prev_op| {321            prev_op.next_op = next;322        } else {323            self.operations.head = next;324        }325326        if (next) |next_op| {327            next_op.prev_op = prev;328        } else {329            self.operations.tail = prev;330        }331332        op_ptr.prev_op = null;333        op_ptr.next_op = null;334        op_ptr.parent_block = null;335        return true;336    }337338    pub fn detachOperation(self: *Block, op: anytype) void {339        const Operation = @import("operation/root.zig").Operation;340        const op_ptr: *Operation = @ptrCast(@alignCast(op));341        _ = self.unlinkOperation(op_ptr);342    }343344    pub fn removeOperation(self: *Block, op: anytype) void {345        const Operation = @import("operation/root.zig").Operation;346        const op_ptr: *Operation = @ptrCast(@alignCast(op));347        if (self.unlinkOperation(op_ptr)) {348            op_ptr.dropAllReferences();349        }350    }351352    pub fn format(self: Block, writer: *std.Io.Writer) std.Io.Writer.Error!void {353        try writer.print("^bb{d}", .{self.id});354        if (self.arguments.items.len > 0) {355            try writer.writeAll("(");356            for (self.arguments.items, 0..) |arg, i| {357                if (i > 0) try writer.writeAll(", ");358                try writer.print("{f}: {f}", .{ arg, arg.type });359            }360            try writer.writeAll(")");361        }362    }363};

1pub const Block = ir.Block;