lib/choir/src/product/hashing/numbering.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_arena = @import("alloc_arena");
3 const alloc_phase = @import("alloc_phase");
4 const ir = @import("../../core/root.zig");
5 const hashing = @import("root.zig");
6 const capacity_model = hashing.capacity;
7 const index_model = hashing.index;
8 const walk = hashing.walk;
9
10 const Allocator = std.mem.Allocator;
11
12 pub const StableValueNumbering = struct {
13 pub const claim: alloc_phase.capacity.Declaration = .{
14 .source = .{
15 .id = "choir.stable_value_numbering",
16 .kind = .phase_static,
17 .limit_source = .caller,
18 .storage = .{
19 .covered = &.{
20 .{
21 .id = "valueentry_array_operationframe_array_and_attributeframe_array",
22 .lifetime = .steady,
23 .detail = "ValueEntry array, OperationFrame array, and AttributeFrame array",
24 },
25 },
26 .excluded = &.{
27 "borrowed mutable IR and every referenced Value, type, and attribute payload",
28 "generic fingerprint builder storage and side effects",
29 },
30 },
31 .capacity = .{
32 .inputs = &.{
33 alloc_phase.capacity.bindInput(Limits, "facts_value_count", "facts.value_count"),
34 alloc_phase.capacity.bindInput(Limits, "facts_operation_depth", "facts.operation_depth"),
35 alloc_phase.capacity.bindInput(Limits, "facts_attribute_depth", "facts.attribute_depth"),
36 },
37 .type_selectors = &.{
38 alloc_phase.capacity.bindType(capacity_model.ValueEntry, "valueentry"),
39 alloc_phase.capacity.bindType(capacity_model.OperationFrame, "operationframe"),
40 alloc_phase.capacity.bindType(capacity_model.AttributeFrame, "attributeframe"),
41 },
42 .nodes = &.{
43 .{ .input = 0 },
44 .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 0 } } },
45 .{ .input = 1 },
46 .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 1 } } },
47 .{ .input = 2 },
48 .{ .scale = .{ .node = 4, .coefficient = .{ .size_of_concrete_type = 2 } } },
49 .{ .add = .{ .left = 1, .right = 3 } },
50 .{ .add = .{ .left = 6, .right = 5 } },
51 },
52 .assertions = &.{.{
53 .scope = .closure_total,
54 .measure = .retained,
55 .relation = .exact,
56 .expression = 7,
57 }},
58 },
59 .overload = .{
60 .kind = .reject_before_seal,
61 .detail = "nesting, arithmetic, OOM, or definition drift rejects before activation; there is no steady exhaustion",
62 },
63 .risks = .{
64 .transitive = .{
65 .status = .open,
66 .detail = "updateSubtreeFingerprint invokes unconstrained anytype builder methods and an indirect inherent-property hook",
67 },
68 .foreign = .{
69 .status = .open,
70 .detail = "generic builder and property hook implementations may reacquire allocator policy or cross foreign boundaries",
71 },
72 },
73 .obligations = &.{
74 .{ .key = "numbering_capacity", .role = .capacity_model },
75 .{ .key = "numbering_sealed_repeat_overload", .role = .overload },
76 .{ .key = "numbering_sealed_repeat_transitive_risk", .role = .transitive_risk },
77 .{ .key = "numbering_sealed_repeat_foreign_risk", .role = .foreign_risk },
78 .{ .key = "numbering_oom_retry", .role = .overload },
79 },
80 },
81 .bindings = .{
82 .owner = @This(),
83 .seal = .{
84 .family = alloc_phase.capacity.selector(@This().activate),
85 .premise = .{
86 .class = .checked_semantic_fact,
87 .authority = .checker,
88 },
89 },
90 .teardown = .{
91 .family = alloc_phase.capacity.selector(@This().deinit),
92 .premise = .{
93 .class = .checked_semantic_fact,
94 .authority = .checker,
95 },
96 },
97 },
98 };
99 phase: alloc_phase.capacity.Phase,
100 capacity: Capacity,
101 root: *ir.Operation,
102 index: index_model.ValueIndex,
103 operation_frames: []capacity_model.OperationFrame,
104 attribute_frames: []capacity_model.AttributeFrame,
105
106 pub const Limits = capacity_model.Limits;
107 pub const Capacity = capacity_model.Capacity;
108
109 const Self = @This();
110
111 pub fn init(allocator: Allocator, limits: Limits) !Self {
112 const current = Limits.inspect(limits.root) catch return error.InputChanged;
113 if (!limits.facts.eql(current.facts)) return error.InputChanged;
114 const derived = try Capacity.derive(limits);
115 var index = try index_model.ValueIndex.init(allocator, derived);
116 errdefer index.deinit(allocator);
117 const operation_frames = try allocator.alloc(
118 capacity_model.OperationFrame,
119 derived.facts.operation_depth,
120 );
121 errdefer allocator.free(operation_frames);
122 const attribute_frames = try allocator.alloc(
123 capacity_model.AttributeFrame,
124 derived.facts.attribute_depth,
125 );
126 errdefer allocator.free(attribute_frames);
127 try index.fill(limits.root, operation_frames);
128 return .{
129 .phase = .initialization,
130 .capacity = derived,
131 .root = limits.root,
132 .index = index,
133 .operation_frames = operation_frames,
134 .attribute_frames = attribute_frames,
135 };
136 }
137
138 pub fn activate(self: *Self) error{ AlreadyActive, InputChanged }!void {
139 if (self.phase != .initialization) return error.AlreadyActive;
140 const current = Limits.inspect(self.root) catch return error.InputChanged;
141 if (!self.capacity.facts.eql(current.facts)) return error.InputChanged;
142 if (!self.index.matchesDefinitions(self.root, self.operation_frames)) {
143 return error.InputChanged;
144 }
145 self.phase = .steady;
146 }
147
148 pub fn valueId(self: *const Self, value: *const ir.Value) ?u64 {
149 self.requireSteady();
150 return self.index.lookup(value);
151 }
152
153 pub fn updateSubtreeFingerprint(
154 self: *Self,
155 builder: anytype,
156 operation: *ir.Operation,
157 ) void {
158 self.requireSteady();
159 if (!self.root.isAncestor(operation)) {
160 @panic("stable value numbering subtree is outside its indexed root");
161 }
162 var iterator = walk.Iterator.init(self.operation_frames, operation);
163 while (iterator.next()) |event| switch (event) {
164 .operation => |op| self.updateOperation(builder, op),
165 .region => |region| updateRegion(builder, region),
166 .block => |block| self.updateBlock(builder, block),
167 };
168 }
169
170 pub fn deinit(self: *Self, allocator: Allocator) void {
171 if (self.phase == .teardown) @panic("stable value numbering teardown is terminal");
172 self.phase = .teardown;
173 allocator.free(self.attribute_frames);
174 allocator.free(self.operation_frames);
175 self.index.deinit(allocator);
176 self.root = undefined;
177 self.operation_frames = undefined;
178 self.attribute_frames = undefined;
179 }
180
181 fn updateOperation(
182 self: *Self,
183 builder: anytype,
184 operation: *ir.Operation,
185 ) void {
186 builder.updateBytes(operation.getName().name);
187
188 builder.updateUsize(operation.getNumAttrs());
189 var attrs = operation.getAttrs();
190 while (attrs.next()) |attr| {
191 builder.updateBytes(attr.name);
192 updateAttributeFingerprint(builder, attr.value, self.attribute_frames);
193 }
194
195 builder.updateU64(operation.getNumResults());
196 for (operation.results.items) |*result| {
197 updateTypeFingerprint(builder, result.type);
198 self.updateNumberedValue(builder, result);
199 }
200
201 builder.updateU64(operation.getNumOperands());
202 for (operation.operands.items) |operand| {
203 self.updateNumberedValue(builder, operand.value);
204 }
205 builder.updateU64(operation.getNumRegions());
206 }
207
208 fn updateBlock(
209 self: *Self,
210 builder: anytype,
211 block: *ir.Block,
212 ) void {
213 builder.updateU64(block.getNumArguments());
214 for (block.arguments.items) |argument| {
215 updateTypeFingerprint(builder, argument.type);
216 self.updateNumberedValue(builder, argument);
217 }
218
219 var operation_count: usize = 0;
220 var operation_opaque = block.operations.head;
221 while (operation_opaque) |operation_ptr| {
222 operation_count += 1;
223 const operation: *ir.Operation = @ptrCast(@alignCast(operation_ptr));
224 operation_opaque = operation.next_op;
225 }
226 builder.updateUsize(operation_count);
227 }
228
229 fn updateNumberedValue(
230 self: *const Self,
231 builder: anytype,
232 value: *const ir.Value,
233 ) void {
234 if (self.valueId(value)) |id| {
235 builder.updateBool(true);
236 builder.updateU64(id);
237 } else {
238 builder.updateBool(false);
239 builder.updateU64(std.math.maxInt(u64));
240 }
241 }
242
243 fn requireSteady(self: *const Self) void {
244 if (self.phase != .steady) {
245 @panic("stable value numbering used outside its steady phase");
246 }
247 }
248 };
249
250 comptime {
251 alloc_phase.capacity.requireAllocatorExactOwnerShape(StableValueNumbering);
252 }
253
254 fn updateRegion(builder: anytype, region: *ir.Region) void {
255 var block_count: usize = 0;
256 var block_opaque = region.blocks.head;
257 while (block_opaque) |block_ptr| {
258 block_count += 1;
259 const block: *ir.Block = @ptrCast(@alignCast(block_ptr));
260 block_opaque = block.next;
261 }
262 builder.updateUsize(block_count);
263 }
264
265 fn updateTypeFingerprint(builder: anytype, typ: ir.Type) void {
266 if (typ.getDialectStorage()) |storage| {
267 builder.updateBool(true);
268 builder.updateBytes(storage.name);
269 builder.updateBytes(storage.param_key);
270 return;
271 }
272 builder.updateBool(false);
273 builder.updateU64(@intFromPtr(typ.impl));
274 }
275
276 fn updateAttributeFingerprint(
277 builder: anytype,
278 root: ir.Attribute,
279 frames: []capacity_model.AttributeFrame,
280 ) void {
281 var current: ?ir.Attribute = root;
282 var depth: usize = 0;
283 while (true) {
284 if (current) |attr| {
285 builder.updateU64(@backingInt(attr.attr_id));
286 builder.updateBytes(attr.abstract.name);
287
288 if (attr.cast(ir.Attribute.IntegerAttr)) |integer| {
289 builder.updateU64(@bitCast(integer.value));
290 builder.updateU64(integer.width);
291 builder.updateBool(integer.is_signed);
292 } else if (attr.cast(ir.Attribute.FloatAttr)) |float| {
293 builder.updateU64(@bitCast(float.value));
294 builder.updateU64(float.width);
295 } else if (attr.cast(ir.Attribute.BoolAttr)) |boolean| {
296 builder.updateBool(boolean.value);
297 } else if (attr.cast(ir.Attribute.StringAttr)) |string| {
298 builder.updateBytes(string.value);
299 } else if (attr.cast(ir.Attribute.SymbolRefAttr)) |symbol| {
300 builder.updateBytes(symbol.root_reference);
301 builder.updateUsize(symbol.nested_references.len);
302 for (symbol.nested_references) |nested| builder.updateBytes(nested);
303 } else if (attr.cast(ir.Attribute.StringListAttr)) |list| {
304 builder.updateUsize(list.values.len);
305 for (list.values) |value| builder.updateBytes(value);
306 } else if (attr.cast(ir.Attribute.TypeListAttr)) |list| {
307 builder.updateUsize(list.values.len);
308 for (list.values) |typ| updateTypeFingerprint(builder, typ);
309 } else if (attr.cast(ir.Attribute.ArrayAttr)) |array| {
310 builder.updateUsize(array.values.len);
311 if (array.values.len > 0) {
312 if (depth >= frames.len) {
313 @panic("attribute traversal exceeded inspected depth");
314 }
315 frames[depth] = .{ .values = array.values, .next_index = 1 };
316 depth += 1;
317 current = array.values[0];
318 continue;
319 }
320 } else if (attr.cast(ir.Attribute.DialectAttr)) |dialect| {
321 builder.updateBytes(dialect.payload);
322 } else {
323 builder.updateU64(@intFromPtr(attr.impl));
324 }
325 }
326
327 current = null;
328 while (depth > 0) {
329 const frame = &frames[depth - 1];
330 if (frame.next_index < frame.values.len) {
331 current = frame.values[frame.next_index];
332 frame.next_index += 1;
333 break;
334 }
335 depth -= 1;
336 }
337 if (current == null) return;
338 }
339 }
340
341 const TestFingerprintBuilder = struct {
342 value: u64 = 14_695_981_039_346_656_037,
343
344 fn updateBytes(self: *@This(), bytes: []const u8) void {
345 self.updateU64(bytes.len);
346 self.updateRawBytes(bytes);
347 }
348
349 fn updateRawBytes(self: *@This(), bytes: []const u8) void {
350 for (bytes) |byte| {
351 self.value ^= byte;
352 self.value *%= 1_099_511_628_211;
353 }
354 }
355
356 fn updateBool(self: *@This(), value: bool) void {
357 self.updateU64(@intFromBool(value));
358 }
359
360 fn updateU64(self: *@This(), value: u64) void {
361 var bytes: [8]u8 = undefined;
362 std.mem.writeInt(u64, &bytes, value, .little);
363 self.updateRawBytes(&bytes);
364 }
365
366 fn updateUsize(self: *@This(), value: usize) void {
367 self.updateU64(@intCast(value));
368 }
369
370 fn finish(self: @This()) u64 {
371 return self.value;
372 }
373 };
374
375 fn makeNumberingTree(
376 context: *ir.Context,
377 operation_name: []const u8,
378 reverse_operands: bool,
379 ) !*ir.Operation {
380 const test_dialect = @import("../../dialects/fixture/root.zig");
381 const location = ir.Location.getUnknown();
382 const integer_type = try test_dialect.TestDialect.getI64Type(context);
383 var region = ir.context.initRegion(context);
384 defer region.deinit();
385 const block = try region.addBlock();
386 const first = try block.addArgument(integer_type, location);
387 const second = try block.addArgument(integer_type, location);
388 var state = ir.Operation.State.init(operation_name, location);
389 state.addOperands(if (reverse_operands) &.{ second, first } else &.{ first, second });
390 state.addTypes(&.{integer_type});
391 const operation = try context.createOperation(state);
392 try block.addOperation(operation);
393 var wrapper_state = ir.Operation.State.init("wrapper", location);
394 wrapper_state.addRegionBodies(&.{®ion});
395 return context.createOperation(wrapper_state);
396 }
397
398 fn numberedFingerprint(allocator: Allocator, operation: *ir.Operation) !u64 {
399 const limits = try StableValueNumbering.Limits.inspect(operation);
400 var numbering = try StableValueNumbering.init(allocator, limits);
401 defer numbering.deinit(allocator);
402 try numbering.activate();
403 var builder = TestFingerprintBuilder{};
404 numbering.updateSubtreeFingerprint(&builder, operation);
405 return builder.finish();
406 }
407
408 fn checkStableValueNumberingInitFailures(
409 allocator: Allocator,
410 limits: StableValueNumbering.Limits,
411 ) !void {
412 var numbering = try StableValueNumbering.init(allocator, limits);
413 defer numbering.deinit(allocator);
414 try std.testing.expectEqual(alloc_phase.capacity.Phase.initialization, numbering.phase);
415 }
416
417 test "stable value numbering preserves established protocols" {
418 const allocator = std.testing.allocator;
419 var arena = alloc_arena.Arena.init(allocator);
420 defer arena.deinit();
421 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
422 defer context.deinit(arena.allocator());
423 try context.allowUnregistered();
424
425 const first_add = try makeNumberingTree(&context, "test.add", false);
426 const second_add = try makeNumberingTree(&context, "test.add", false);
427 const first_add_fingerprint = try numberedFingerprint(allocator, first_add);
428 const second_add_fingerprint = try numberedFingerprint(allocator, second_add);
429 try std.testing.expectEqual(first_add_fingerprint, second_add_fingerprint);
430 try std.testing.expectEqual(
431 @as(u64, 11_742_538_809_681_872_813),
432 first_add_fingerprint,
433 );
434
435 const first_sub = try makeNumberingTree(&context, "test.sub", false);
436 const second_sub = try makeNumberingTree(&context, "test.sub", true);
437 try std.testing.expectEqual(
438 @as(u64, 13_191_181_002_833_531_052),
439 try numberedFingerprint(allocator, first_sub),
440 );
441 try std.testing.expectEqual(
442 @as(u64, 13_697_684_465_524_774_060),
443 try numberedFingerprint(allocator, second_sub),
444 );
445 }
446
447 test "stable value numbering initialization cleans every allocation failure and retries" {
448 comptime {
449 @stardustClaim(
450 @import("alloc_phase").capacity.witness(StableValueNumbering, "numbering_oom_retry"),
451 null,
452 null,
453 null,
454 null,
455 null,
456 null,
457 );
458 }
459
460 const allocator = std.testing.allocator;
461 var arena = alloc_arena.Arena.init(allocator);
462 defer arena.deinit();
463 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
464 defer context.deinit(arena.allocator());
465 try context.allowUnregistered();
466
467 const root = try makeNumberingTree(&context, "test.add", false);
468 const leaf = try context.getStringAttr("leaf");
469 const inner = try context.getArrayAttr(&.{leaf});
470 try root.setAttr("nested", try context.getArrayAttr(&.{inner}));
471 const limits = try StableValueNumbering.Limits.inspect(root);
472 try std.testing.expect(limits.facts.value_count > 0);
473 try std.testing.expect(limits.facts.operation_depth > 1);
474 try std.testing.expect(limits.facts.attribute_depth > 1);
475
476 try std.testing.checkAllAllocationFailures(
477 allocator,
478 checkStableValueNumberingInitFailures,
479 .{limits},
480 );
481
482 var numbering = try StableValueNumbering.init(allocator, limits);
483 defer numbering.deinit(allocator);
484 try numbering.activate();
485 const block: *ir.Block = @ptrCast(@alignCast(root.regions.items[0].blocks.head.?));
486 try std.testing.expect(numbering.valueId(block.arguments.items[0]) != null);
487 var builder = TestFingerprintBuilder{};
488 numbering.updateSubtreeFingerprint(&builder, root);
489 _ = builder.finish();
490 }
491
492 test "stable value numbering rejects reordered definitions with unchanged facts" {
493 const allocator = std.testing.allocator;
494 var arena = alloc_arena.Arena.init(allocator);
495 defer arena.deinit();
496 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
497 defer context.deinit(arena.allocator());
498 try context.allowUnregistered();
499 const location = ir.Location.getUnknown();
500 const integer_type = try context.getDialectTypeFromName("test.i64");
501
502 var first_state = ir.Operation.State.init("first", location);
503 first_state.addTypes(&.{integer_type});
504 const first = try context.createOperation(first_state);
505 var second_state = ir.Operation.State.init("second", location);
506 second_state.addTypes(&.{integer_type});
507 const second = try context.createOperation(second_state);
508 var region = ir.context.initRegion(&context);
509 defer region.deinit();
510 const block = try region.addBlock();
511 try block.addOperation(first);
512 try block.addOperation(second);
513 var root_state = ir.Operation.State.init("root", location);
514 root_state.addRegionBodies(&.{®ion});
515 const root = try context.createOperation(root_state);
516
517 const limits = try StableValueNumbering.Limits.inspect(root);
518 var numbering = try StableValueNumbering.init(allocator, limits);
519 defer numbering.deinit(allocator);
520 try second.moveBefore(first);
521 const current = try StableValueNumbering.Limits.inspect(root);
522 try std.testing.expect(limits.facts.eql(current.facts));
523 try std.testing.expect(!numbering.index.matchesDefinitions(
524 root,
525 numbering.operation_frames,
526 ));
527 try std.testing.expectError(error.InputChanged, numbering.activate());
528 }
529
530 test "stable value numbering repeats overlapping updates after sealing" {
531 comptime {
532 @stardustClaim(
533 @import("alloc_phase").capacity.witness(StableValueNumbering, "numbering_sealed_repeat_overload"),
534 null,
535 null,
536 null,
537 null,
538 null,
539 null,
540 );
541 }
542 comptime {
543 @stardustClaim(
544 @import("alloc_phase").capacity.witness(StableValueNumbering, "numbering_sealed_repeat_transitive_risk"),
545 null,
546 null,
547 null,
548 null,
549 null,
550 null,
551 );
552 }
553 comptime {
554 @stardustClaim(
555 @import("alloc_phase").capacity.witness(StableValueNumbering, "numbering_sealed_repeat_foreign_risk"),
556 null,
557 null,
558 null,
559 null,
560 null,
561 null,
562 );
563 }
564
565 const allocator = std.testing.allocator;
566 var arena = alloc_arena.Arena.init(allocator);
567 defer arena.deinit();
568 var context = try ir.Context.init(arena.allocator(), ir.Context.Limits.testing);
569 defer context.deinit(arena.allocator());
570 try context.allowUnregistered();
571 const root = try makeNumberingTree(&context, "test.add", false);
572 const block_opaque = root.regions.items[0].blocks.head.?;
573 const block: *ir.Block = @ptrCast(@alignCast(block_opaque));
574 const child_opaque = block.operations.head.?;
575 const child: *ir.Operation = @ptrCast(@alignCast(child_opaque));
576 const limits = try StableValueNumbering.Limits.inspect(root);
577
578 var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(allocator);
579 var maybe_numbering: ?StableValueNumbering = null;
580 errdefer {
581 if (phase_allocator.phase() == .initialization) phase_allocator.abortInitialization();
582 if (phase_allocator.phase() == .steady) phase_allocator.beginTeardown();
583 if (maybe_numbering) |*numbering| {
584 if (numbering.phase != .teardown) {
585 numbering.deinit(phase_allocator.teardownAllocator());
586 }
587 }
588 if (phase_allocator.phase() == .teardown) phase_allocator.deinit();
589 }
590
591 maybe_numbering = try StableValueNumbering.init(
592 phase_allocator.initializationAllocator(),
593 limits,
594 );
595 const numbering = &maybe_numbering.?;
596 const entries_pointer = numbering.index.entries.ptr;
597 const operations_pointer = numbering.operation_frames.ptr;
598 const attributes_pointer = numbering.attribute_frames.ptr;
599 phase_allocator.seal();
600 try numbering.activate();
601
602 var first = TestFingerprintBuilder{};
603 numbering.updateSubtreeFingerprint(&first, child);
604 numbering.updateSubtreeFingerprint(&first, root);
605 var second = TestFingerprintBuilder{};
606 numbering.updateSubtreeFingerprint(&second, child);
607 numbering.updateSubtreeFingerprint(&second, root);
608 try std.testing.expectEqual(first.finish(), second.finish());
609 try std.testing.expectEqual(entries_pointer, numbering.index.entries.ptr);
610 try std.testing.expectEqual(operations_pointer, numbering.operation_frames.ptr);
611 try std.testing.expectEqual(attributes_pointer, numbering.attribute_frames.ptr);
612 try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
613
614 phase_allocator.beginTeardown();
615 numbering.deinit(phase_allocator.teardownAllocator());
616 try std.testing.expectEqual(alloc_phase.capacity.Phase.teardown, numbering.phase);
617 try std.testing.expectEqual(alloc_phase.PhaseViolations{}, phase_allocator.violations());
618 phase_allocator.deinit();
619 }