lib/accy/src/choir/record/reference.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const choir = @import("choir");
  3 const ir = choir.ir;
  4 
  5 pub const Operation = struct {
  6     ordinal: u32,
  7 
  8     pub fn validate(self: Operation, image: choir.bytecode.image.View) !void {
  9         if (self.ordinal >= image.operations.len) return error.UnboundProductInput;
 10     }
 11 };
 12 
 13 pub const Value = union(enum) {
 14     result: struct { operation: Operation, position: u32 },
 15     argument: struct { operation: Operation, region: u32, block: u32, position: u32 },
 16 
 17     pub fn ordinal(self: Value, image: choir.bytecode.image.View) !u32 {
 18         switch (self) {
 19             .result => |result| {
 20                 try result.operation.validate(image);
 21                 const range = image.operations[result.operation.ordinal].results;
 22                 if (result.position >= range.count) return error.UnboundProductInput;
 23                 return range.start + result.position;
 24             },
 25             .argument => |argument| {
 26                 const region = image.region(argument.operation.ordinal, argument.region) orelse
 27                     return error.UnboundProductInput;
 28                 const block = image.block(region, argument.block) orelse
 29                     return error.UnboundProductInput;
 30                 const range = image.blocks[block].arguments;
 31                 if (argument.position >= range.count) return error.UnboundProductInput;
 32                 return range.start + argument.position;
 33             },
 34         }
 35     }
 36 };
 37 
 38 /// Turns pointers into numbers that survive a round trip through bytes, for the
 39 /// encoder and comparer of a stage record, an immutable compile stage result.
 40 /// The index numbers every operation of one program in preorder, by the order a
 41 /// walk from the root visits it, in the same order the bytecode writer uses.
 42 /// The walk stops with `error.RecordLimit` once it reaches `limit` operations.
 43 /// A value is named by its defining operation and its result position, or for a
 44 /// block argument by operation, region, block and position, and never by an
 45 /// address. A lookup of an operation or value absent from the index fails with
 46 /// `error.UnboundProductInput`. The numbering belongs to one job and one
 47 /// program.
 48 pub const Index = struct {
 49     allocator: std.mem.Allocator,
 50     limit: u32,
 51     operations: std.AutoHashMapUnmanaged(*ir.Operation, Operation) = .empty,
 52     values: std.AutoHashMapUnmanaged(*ir.Value, Value) = .empty,
 53 
 54     pub fn init(allocator: std.mem.Allocator, root: *ir.Operation, limit: u32) !Index {
 55         var self = Index{ .allocator = allocator, .limit = limit };
 56         errdefer self.deinit();
 57         _ = try root.walk(.{ .order = .pre_order }, &self, visit);
 58         return self;
 59     }
 60 
 61     pub fn deinit(self: *Index) void {
 62         self.operations.deinit(self.allocator);
 63         self.values.deinit(self.allocator);
 64         self.* = undefined;
 65     }
 66 
 67     pub fn operation(self: *const Index, source: *ir.Operation) !Operation {
 68         return self.operations.get(source) orelse error.UnboundProductInput;
 69     }
 70 
 71     pub fn value(self: *const Index, source: *ir.Value) !Value {
 72         return self.values.get(source) orelse error.UnboundProductInput;
 73     }
 74 
 75     fn visit(self: *Index, op: *ir.Operation) !ir.WalkResult {
 76         if (self.operations.count() == self.limit) return error.RecordLimit;
 77         const ref = Operation{ .ordinal = @intCast(self.operations.count()) };
 78         try self.operations.putNoClobber(self.allocator, op, ref);
 79         for (op.results.items, 0..) |*result, position| {
 80             try self.addValue(result, .{ .result = .{
 81                 .operation = ref,
 82                 .position = @intCast(position),
 83             } });
 84         }
 85         for (op.regions.items, 0..) |*region, region_position| {
 86             var blocks = region.getBlocks();
 87             var block_position: u32 = 0;
 88             while (blocks.next()) |block| : (block_position += 1) {
 89                 if (block_position == self.limit) return error.RecordLimit;
 90                 for (block.arguments.items, 0..) |argument, position| {
 91                     try self.addValue(argument, .{ .argument = .{
 92                         .operation = ref,
 93                         .region = @intCast(region_position),
 94                         .block = block_position,
 95                         .position = @intCast(position),
 96                     } });
 97                 }
 98             }
 99         }
100         return .advance;
101     }
102 
103     fn addValue(self: *Index, source: *ir.Value, ref: Value) !void {
104         if (self.values.count() == self.limit) return error.RecordLimit;
105         try self.values.putNoClobber(self.allocator, source, ref);
106     }
107 };