lib/choir/src/product/hashing/index.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

  1 const std = @import("std");
  2 const ir = @import("../../core/root.zig");
  3 const hashing = @import("root.zig");
  4 const capacity = hashing.capacity;
  5 const walk = hashing.walk;
  6 
  7 const Allocator = std.mem.Allocator;
  8 
  9 pub const ValueIndex = struct {
 10     entries: []capacity.ValueEntry,
 11 
 12     pub fn init(allocator: Allocator, derived: capacity.Capacity) Allocator.Error!ValueIndex {
 13         return .{
 14             .entries = try allocator.alloc(capacity.ValueEntry, derived.facts.value_count),
 15         };
 16     }
 17 
 18     pub fn deinit(self: *ValueIndex, allocator: Allocator) void {
 19         allocator.free(self.entries);
 20         self.* = undefined;
 21     }
 22 
 23     pub fn fill(
 24         self: *ValueIndex,
 25         root: *ir.Operation,
 26         frames: []capacity.OperationFrame,
 27     ) error{ InputChanged, DuplicateValueDefinition }!void {
 28         var iterator = walk.Iterator.init(frames, root);
 29         var count: usize = 0;
 30         while (iterator.next()) |event| switch (event) {
 31             .operation => |operation| {
 32                 for (operation.results.items) |*result| {
 33                     try self.append(result, &count);
 34                 }
 35             },
 36             .region => {},
 37             .block => |block| {
 38                 for (block.arguments.items) |argument| {
 39                     try self.append(argument, &count);
 40                 }
 41             },
 42         };
 43         if (count != self.entries.len) return error.InputChanged;
 44         std.sort.heap(capacity.ValueEntry, self.entries, {}, lessThanEntry);
 45         if (self.entries.len > 1) {
 46             for (self.entries[1..], self.entries[0 .. self.entries.len - 1]) |current, previous| {
 47                 if (current.value == previous.value) return error.DuplicateValueDefinition;
 48             }
 49         }
 50     }
 51 
 52     pub fn lookup(self: *const ValueIndex, value: *const ir.Value) ?u64 {
 53         const address = @intFromPtr(value);
 54         var low: usize = 0;
 55         var high = self.entries.len;
 56         while (low < high) {
 57             const mid = low + (high - low) / 2;
 58             const candidate = self.entries[mid];
 59             const candidate_address = @intFromPtr(candidate.value);
 60             if (candidate_address < address) {
 61                 low = mid + 1;
 62             } else if (candidate_address > address) {
 63                 high = mid;
 64             } else {
 65                 return candidate.id;
 66             }
 67         }
 68         return null;
 69     }
 70 
 71     pub fn matchesDefinitions(
 72         self: *const ValueIndex,
 73         root: *ir.Operation,
 74         frames: []capacity.OperationFrame,
 75     ) bool {
 76         var iterator = walk.Iterator.init(frames, root);
 77         var count: u64 = 0;
 78         while (iterator.next()) |event| switch (event) {
 79             .operation => |operation| {
 80                 for (operation.results.items) |*result| {
 81                     if (!self.matches(result, count)) return false;
 82                     count += 1;
 83                 }
 84             },
 85             .region => {},
 86             .block => |block| {
 87                 for (block.arguments.items) |argument| {
 88                     if (!self.matches(argument, count)) return false;
 89                     count += 1;
 90                 }
 91             },
 92         };
 93         return count == self.entries.len;
 94     }
 95 
 96     fn append(
 97         self: *ValueIndex,
 98         value: *const ir.Value,
 99         count: *usize,
100     ) error{InputChanged}!void {
101         if (count.* >= self.entries.len) return error.InputChanged;
102         self.entries[count.*] = .{ .value = value, .id = @intCast(count.*) };
103         count.* += 1;
104     }
105 
106     fn matches(self: *const ValueIndex, value: *const ir.Value, id: u64) bool {
107         return self.lookup(value) == id;
108     }
109 };
110 
111 fn lessThanEntry(_: void, lhs: capacity.ValueEntry, rhs: capacity.ValueEntry) bool {
112     return @intFromPtr(lhs.value) < @intFromPtr(rhs.value);
113 }