lib/choir/src/core/block.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const Value = @import("value.zig").Value;
3 const Type = @import("type.zig").Type;
4 const Location = @import("location.zig").Location;
5 const cfg = @import("cfg.zig");
6
7 pub const Block = struct {
8 allocator: std.mem.Allocator,
9
10 /// Values keep their addresses until the block is deinitialized.
11 arguments: std.ArrayList(*Value),
12
13 argument_locations: std.ArrayList(Location),
14
15 operations: OperationList,
16
17 parent: ?*anyopaque,
18
19 prev: ?*Block,
20 next: ?*Block,
21
22 id: u32,
23
24 predecessors: std.ArrayList(*Block),
25
26 op_order_valid: bool,
27
28 pub const order_stride: u32 = 8;
29 pub const order_query_scan_limit: u8 = 8;
30
31 pub const OperationList = struct {
32 head: ?*anyopaque,
33 tail: ?*anyopaque,
34
35 pub fn init() OperationList {
36 return .{
37 .head = null,
38 .tail = null,
39 };
40 }
41
42 pub fn isEmpty(self: OperationList) bool {
43 return self.head == null;
44 }
45 };
46
47 pub const OperationIterator = struct {
48 current: ?*anyopaque,
49
50 pub fn next(self: *OperationIterator) ?*@import("operation/root.zig").Operation {
51 const op_any = self.current orelse return null;
52 const op: *@import("operation/root.zig").Operation = @ptrCast(@alignCast(op_any));
53 self.current = op.next_op;
54 return op;
55 }
56 };
57
58 pub fn init(allocator: std.mem.Allocator) Block {
59 return .{
60 .allocator = allocator,
61 .arguments = .empty,
62 .argument_locations = .empty,
63 .operations = OperationList.init(),
64 .parent = null,
65 .prev = null,
66 .next = null,
67 .id = 0,
68 .predecessors = .empty,
69 .op_order_valid = true,
70 };
71 }
72
73 fn recomputeOpOrder(self: *Block) void {
74 var next_order: u32 = 0;
75 var current = self.operations.head;
76 while (current) |node| {
77 const op: *@import("operation/root.zig").Operation = @ptrCast(@alignCast(node));
78 op.order = next_order;
79 next_order +|= order_stride;
80 current = op.next_op;
81 }
82 self.op_order_valid = true;
83 }
84
85 pub fn sealOperationOrder(self: *Block) bool {
86 if (self.op_order_valid) return false;
87 self.recomputeOpOrder();
88 return true;
89 }
90
91 pub fn operationPrecedes(
92 self: *Block,
93 first: *const @import("operation/root.zig").Operation,
94 second: *const @import("operation/root.zig").Operation,
95 ) bool {
96 std.debug.assert(first.parent_block == self);
97 std.debug.assert(second.parent_block == self);
98
99 if (self.op_order_valid) return first.order < second.order;
100
101 var next = first.next_op;
102 var previous = first.prev_op;
103 var scanned: u8 = 0;
104 while (scanned < order_query_scan_limit) : (scanned += 1) {
105 if (next) |op| {
106 if (op == second) return true;
107 next = op.next_op;
108 }
109 if (previous) |op| {
110 if (op == second) return false;
111 previous = op.prev_op;
112 }
113 }
114
115 _ = self.sealOperationOrder();
116 return first.order < second.order;
117 }
118
119 pub fn deinit(self: *Block) void {
120 for (self.arguments.items) |argument| self.allocator.destroy(argument);
121 self.arguments.deinit(self.allocator);
122 self.argument_locations.deinit(self.allocator);
123 self.predecessors.deinit(self.allocator);
124 }
125
126 pub fn addArgument(self: *Block, arg_type: Type, loc: Location) !*Value {
127 const arg_num: u32 = @intCast(self.arguments.items.len);
128 const value = try self.allocator.create(Value);
129 errdefer self.allocator.destroy(value);
130 value.* = .{
131 .kind = .{ .block_argument = .{
132 .owner = self,
133 .arg_number = arg_num,
134 } },
135 .type = arg_type,
136 .id = 0,
137 };
138 try self.argument_locations.append(self.allocator, loc);
139 errdefer _ = self.argument_locations.pop();
140 try self.arguments.append(self.allocator, value);
141 return self.arguments.items[self.arguments.items.len - 1];
142 }
143
144 pub fn getArgumentLocation(self: *const Block, index: usize) ?Location {
145 if (index >= self.argument_locations.items.len) return null;
146 return self.argument_locations.items[index];
147 }
148
149 pub fn setArgumentLocation(self: *Block, index: usize, loc: Location) void {
150 std.debug.assert(index < self.argument_locations.items.len);
151 self.argument_locations.items[index] = loc;
152 }
153
154 pub fn getNumArguments(self: Block) usize {
155 return self.arguments.items.len;
156 }
157
158 pub fn getArgument(self: *Block, index: usize) ?*Value {
159 if (index >= self.arguments.items.len) return null;
160 return self.arguments.items[index];
161 }
162
163 pub fn empty(self: Block) bool {
164 return self.operations.isEmpty();
165 }
166
167 pub fn dropAllReferences(self: *Block) void {
168 var ops = self.getOperations();
169 while (ops.next()) |op| {
170 op.dropAllReferences();
171 }
172 }
173
174 pub fn hasNoDefinedValueUses(self: *Block) bool {
175 for (self.arguments.items) |argument| {
176 if (!argument.hasNoUses()) return false;
177 }
178
179 var ops = self.getOperations();
180 while (ops.next()) |op| {
181 if (!op.hasNoDefinedValueUses()) return false;
182 }
183 return true;
184 }
185
186 pub fn dropAllDefinedValueUses(self: *Block) void {
187 for (self.arguments.items) |argument| {
188 argument.dropAllUses();
189 }
190
191 var ops = self.getOperations();
192 while (ops.next()) |op| {
193 op.dropAllDefinedValueUses();
194 }
195 }
196
197 pub fn getOperations(self: *Block) OperationIterator {
198 return .{ .current = self.operations.head };
199 }
200
201 pub fn walkOperations(
202 self: *Block,
203 options: @import("operation/root.zig").Operation.WalkOptions,
204 context: anytype,
205 callback: anytype,
206 ) anyerror!@import("operation/root.zig").Operation.WalkResult {
207 var ops = self.getOperations();
208 while (ops.next()) |op| {
209 const result = try op.walk(options, context, callback);
210 if (result.wasInterrupted()) return .interrupt;
211 }
212 return .advance;
213 }
214
215 pub fn getParentRegion(self: *const Block) ?*@import("region.zig").Region {
216 const parent = self.parent orelse return null;
217 return @ptrCast(@alignCast(parent));
218 }
219
220 pub fn getParentOperation(self: *const Block) ?*@import("operation/root.zig").Operation {
221 const region = self.getParentRegion() orelse return null;
222 return region.getParentOperation();
223 }
224
225 pub fn hasNoPredecessors(self: Block) bool {
226 return self.predecessors.items.len == 0;
227 }
228
229 pub fn getNumPredecessors(self: Block) usize {
230 return self.predecessors.items.len;
231 }
232
233 pub fn getPredecessors(self: *const Block) []const *Block {
234 return self.predecessors.items;
235 }
236
237 pub fn getPredecessor(self: Block, index: usize) ?*Block {
238 if (index >= self.predecessors.items.len) return null;
239 return self.predecessors.items[index];
240 }
241
242 pub fn hasPredecessor(self: Block, pred: *Block) bool {
243 for (self.predecessors.items) |existing| {
244 if (existing == pred) return true;
245 }
246 return false;
247 }
248
249 pub fn getTerminator(self: Block) ?*anyopaque {
250 return self.operations.tail;
251 }
252
253 pub fn addOperation(self: *Block, op: anytype) !void {
254 const Operation = @import("operation/root.zig").Operation;
255 const op_ptr: *Operation = @ptrCast(@alignCast(op));
256 if (op_ptr.parent_block != null or op_ptr.prev_op != null or op_ptr.next_op != null) {
257 return error.OperationAlreadyInserted;
258 }
259
260 try cfg.attach(self, op_ptr);
261
262 op_ptr.parent_block = self;
263
264 if (self.operations.tail) |tail| {
265 const tail_op: *Operation = @ptrCast(@alignCast(tail));
266 tail_op.next_op = op_ptr;
267 op_ptr.prev_op = tail_op;
268 if (self.op_order_valid) {
269 if (tail_op.order <= std.math.maxInt(u32) - order_stride) {
270 op_ptr.order = tail_op.order + order_stride;
271 } else {
272 self.op_order_valid = false;
273 }
274 }
275 } else {
276 self.operations.head = op_ptr;
277 if (self.op_order_valid) op_ptr.order = 0;
278 }
279 self.operations.tail = op_ptr;
280 }
281
282 pub fn insertBefore(self: *Block, op: anytype, before: anytype) !void {
283 const Operation = @import("operation/root.zig").Operation;
284 const before_op: *Operation = @ptrCast(@alignCast(before));
285 const op_ptr: *Operation = @ptrCast(@alignCast(op));
286 if (before_op.parent_block != self) return error.OperationInsertBeforeDetached;
287 if (op_ptr.parent_block != null or op_ptr.prev_op != null or op_ptr.next_op != null) {
288 return error.OperationAlreadyInserted;
289 }
290
291 try cfg.attach(self, op_ptr);
292
293 op_ptr.parent_block = self;
294
295 const prev = before_op.prev_op;
296 op_ptr.prev_op = prev;
297 op_ptr.next_op = before_op;
298 before_op.prev_op = op_ptr;
299
300 if (prev) |prev_op| {
301 prev_op.next_op = op_ptr;
302 } else {
303 self.operations.head = op_ptr;
304 }
305
306 if (self.op_order_valid) {
307 const low: u64 = if (prev) |prev_op| @as(u64, prev_op.order) + 1 else 0;
308 const high: u64 = before_op.order;
309 if (high > low) {
310 op_ptr.order = @intCast(low + (high - low) / 2);
311 } else {
312 self.op_order_valid = false;
313 }
314 }
315 }
316
317 fn unlinkOperation(self: *Block, op_ptr: *@import("operation/root.zig").Operation) bool {
318 if (op_ptr.parent_block == null) return false;
319 std.debug.assert(op_ptr.parent_block == self);
320
321 cfg.detach(self, op_ptr);
322
323 const prev = op_ptr.prev_op;
324 const next = op_ptr.next_op;
325
326 if (prev) |prev_op| {
327 prev_op.next_op = next;
328 } else {
329 self.operations.head = next;
330 }
331
332 if (next) |next_op| {
333 next_op.prev_op = prev;
334 } else {
335 self.operations.tail = prev;
336 }
337
338 op_ptr.prev_op = null;
339 op_ptr.next_op = null;
340 op_ptr.parent_block = null;
341 return true;
342 }
343
344 pub fn detachOperation(self: *Block, op: anytype) void {
345 const Operation = @import("operation/root.zig").Operation;
346 const op_ptr: *Operation = @ptrCast(@alignCast(op));
347 _ = self.unlinkOperation(op_ptr);
348 }
349
350 pub fn removeOperation(self: *Block, op: anytype) void {
351 const Operation = @import("operation/root.zig").Operation;
352 const op_ptr: *Operation = @ptrCast(@alignCast(op));
353 if (self.unlinkOperation(op_ptr)) {
354 op_ptr.dropAllReferences();
355 }
356 }
357
358 pub fn format(self: Block, writer: *std.Io.Writer) std.Io.Writer.Error!void {
359 try writer.print("^bb{d}", .{self.id});
360 if (self.arguments.items.len > 0) {
361 try writer.writeAll("(");
362 for (self.arguments.items, 0..) |arg, i| {
363 if (i > 0) try writer.writeAll(", ");
364 try writer.print("{f}: {f}", .{ arg, arg.type });
365 }
366 try writer.writeAll(")");
367 }
368 }
369 };
370
371 test "block predecessor tracking" {
372 const testing = std.testing;
373 const allocator = testing.allocator;
374 const Operation = @import("operation/root.zig").Operation;
375 const Context = @import("context/root.zig").Context;
376
377 var ctx = try Context.init(allocator, Context.Limits.testing);
378 var entry = Block.init(allocator);
379 var then_block = Block.init(allocator);
380 var merge = Block.init(allocator);
381 defer {
382 ctx.deinit(allocator);
383 entry.deinit();
384 then_block.deinit();
385 merge.deinit();
386 }
387 try ctx.allowUnregistered();
388
389 try testing.expect(entry.hasNoPredecessors());
390 try testing.expect(then_block.hasNoPredecessors());
391 try testing.expect(merge.hasNoPredecessors());
392 try testing.expectEqual(@as(usize, 0), entry.getNumPredecessors());
393
394 var entry_state = Operation.State.init("test.entry_branch", .unknown);
395 entry_state.addSuccessors(&.{ &then_block, &merge });
396 try entry.addOperation(try ctx.createOperation(entry_state));
397 var then_state = Operation.State.init("test.then_branch", .unknown);
398 then_state.addSuccessors(&.{&merge});
399 try then_block.addOperation(try ctx.createOperation(then_state));
400
401 try testing.expect(!then_block.hasNoPredecessors());
402 try testing.expectEqual(@as(usize, 1), then_block.getNumPredecessors());
403 try testing.expectEqual(&entry, then_block.getPredecessor(0).?);
404
405 try testing.expectEqual(@as(usize, 2), merge.getNumPredecessors());
406 try testing.expect(merge.hasPredecessor(&entry));
407 try testing.expect(merge.hasPredecessor(&then_block));
408 try testing.expect(!merge.hasPredecessor(&merge));
409
410 try testing.expect(entry.hasNoPredecessors());
411 }
412
413 test "block insert and remove operations" {
414 const testing = std.testing;
415 const allocator = testing.allocator;
416 const Operation = @import("operation/root.zig").Operation;
417 const context = @import("context/root.zig");
418
419 var ctx = try context.Context.init(allocator, context.Context.Limits.testing);
420 defer ctx.deinit(allocator);
421 try ctx.allowUnregistered();
422
423 var block = Block.init(allocator);
424 defer block.deinit();
425 var succ = Block.init(allocator);
426 defer succ.deinit();
427
428 const loc = Location.getUnknown();
429
430 var state1 = Operation.State.init("test.br", loc);
431 state1.addSuccessors(&.{&succ});
432 const op1 = try ctx.createOperation(state1);
433
434 const state2 = Operation.State.init("test.noop", loc);
435 const op2 = try ctx.createOperation(state2);
436
437 try block.addOperation(op1);
438 try testing.expectEqual(@as(usize, 1), succ.getNumPredecessors());
439 try testing.expect(succ.hasPredecessor(&block));
440
441 try block.insertBefore(op2, op1);
442 const head: *Operation = @ptrCast(@alignCast(block.operations.head.?));
443 const tail: *Operation = @ptrCast(@alignCast(block.operations.tail.?));
444 try testing.expect(head == op2);
445 try testing.expect(tail == op1);
446 try testing.expect(op2.next_op == op1);
447 try testing.expect(op1.prev_op == op2);
448
449 block.removeOperation(op2);
450 const head_after: *Operation = @ptrCast(@alignCast(block.operations.head.?));
451 const tail_after: *Operation = @ptrCast(@alignCast(block.operations.tail.?));
452 try testing.expect(head_after == op1);
453 try testing.expect(tail_after == op1);
454 try testing.expect(op1.prev_op == null);
455
456 block.removeOperation(op1);
457 try testing.expect(block.operations.head == null);
458 try testing.expect(block.operations.tail == null);
459 try testing.expect(op1.parent_block == null);
460 try testing.expect(!succ.hasPredecessor(&block));
461 }
462
463 test "removing one of two block edges preserves the predecessor" {
464 const testing = std.testing;
465 const Operation = @import("operation/root.zig").Operation;
466 const Context = @import("context/root.zig").Context;
467
468 var ctx = try Context.init(testing.allocator, Context.Limits.testing);
469 var source = Block.init(testing.allocator);
470 var target = Block.init(testing.allocator);
471 defer {
472 ctx.deinit(testing.allocator);
473 source.deinit();
474 target.deinit();
475 }
476 try ctx.allowUnregistered();
477
478 var first_state = Operation.State.init("test.first_branch", .unknown);
479 first_state.addSuccessors(&.{&target});
480 const first = try ctx.createOperation(first_state);
481 var second_state = Operation.State.init("test.second_branch", .unknown);
482 second_state.addSuccessors(&.{&target});
483 const second = try ctx.createOperation(second_state);
484
485 try source.addOperation(first);
486 try source.addOperation(second);
487 source.removeOperation(first);
488
489 try testing.expect(target.hasPredecessor(&source));
490 try testing.expect(second.getSuccessor(0).? == &target);
491
492 source.removeOperation(second);
493 try testing.expect(target.hasNoPredecessors());
494 }
495
496 test "block op order stays coherent through append, insert, and move" {
497 const testing = std.testing;
498 const allocator = testing.allocator;
499 const Operation = @import("operation/root.zig").Operation;
500 const context = @import("context/root.zig");
501
502 var ctx = try context.Context.init(allocator, context.Context.Limits.testing);
503 defer ctx.deinit(allocator);
504 try ctx.allowUnregistered();
505
506 var block = Block.init(allocator);
507 defer block.deinit();
508
509 const loc = Location.getUnknown();
510 var ops: [6]*Operation = undefined;
511 for (&ops) |*slot| {
512 slot.* = try ctx.createOperation(Operation.State.init("test.noop", loc));
513 }
514
515 try block.addOperation(ops[0]);
516 try block.addOperation(ops[1]);
517 try block.addOperation(ops[2]);
518 try testing.expect(block.op_order_valid);
519 try testing.expect(ops[0].isBeforeInBlock(ops[2]));
520 try testing.expect(!ops[2].isBeforeInBlock(ops[0]));
521
522 try block.insertBefore(ops[3], ops[1]);
523 try testing.expect(ops[0].isBeforeInBlock(ops[3]));
524 try testing.expect(ops[3].isBeforeInBlock(ops[1]));
525
526 try block.insertBefore(ops[4], ops[3]);
527 try block.insertBefore(ops[5], ops[4]);
528 try testing.expect(ops[0].isBeforeInBlock(ops[5]));
529 try testing.expect(ops[5].isBeforeInBlock(ops[4]));
530 try testing.expect(ops[4].isBeforeInBlock(ops[3]));
531 try testing.expect(ops[3].isBeforeInBlock(ops[1]));
532 try testing.expect(block.op_order_valid);
533
534 try ops[1].moveBefore(ops[0]);
535 try testing.expect(!block.op_order_valid);
536 try testing.expect(ops[1].isBeforeInBlock(ops[0]));
537 try testing.expect(!ops[0].isBeforeInBlock(ops[1]));
538 try testing.expect(!block.op_order_valid);
539 try testing.expect(block.sealOperationOrder());
540 try testing.expect(block.op_order_valid);
541 try testing.expect(!block.sealOperationOrder());
542
543 block.removeOperation(ops[2]);
544 try testing.expect(ops[1].isBeforeInBlock(ops[3]));
545 try testing.expect(ops[0].isBeforeInBlock(ops[3]));
546 }
547
548 test "block order queries bound local scans before sealing" {
549 const testing = std.testing;
550 const allocator = testing.allocator;
551 const Operation = @import("operation/root.zig").Operation;
552 const context = @import("context/root.zig");
553
554 var ctx = try context.Context.init(allocator, context.Context.Limits.testing);
555 defer ctx.deinit(allocator);
556 try ctx.allowUnregistered();
557
558 var block = Block.init(allocator);
559 defer block.deinit();
560
561 const loc = Location.getUnknown();
562 var ops: [12]*Operation = undefined;
563 for (&ops) |*slot| {
564 slot.* = try ctx.createOperation(Operation.State.init("test.noop", loc));
565 try block.addOperation(slot.*);
566 }
567
568 try ops[11].moveBefore(ops[0]);
569 try testing.expect(!block.op_order_valid);
570 try testing.expect(ops[11].isBeforeInBlock(ops[0]));
571 try testing.expect(!block.op_order_valid);
572 try testing.expect(ops[11].isBeforeInBlock(ops[9]));
573 try testing.expect(block.op_order_valid);
574 }
575
576 test "block insertion rejects already parented operations" {
577 const testing = std.testing;
578 const allocator = testing.allocator;
579 const Operation = @import("operation/root.zig").Operation;
580 const context = @import("context/root.zig");
581
582 var ctx = try context.Context.init(allocator, context.Context.Limits.testing);
583 defer ctx.deinit(allocator);
584 try ctx.allowUnregistered();
585
586 var first = Block.init(allocator);
587 defer first.deinit();
588 var second = Block.init(allocator);
589 defer second.deinit();
590
591 const op = try ctx.createOperation(Operation.State.init("test.noop", Location.getUnknown()));
592 const anchor = try ctx.createOperation(Operation.State.init("test.anchor", Location.getUnknown()));
593 const detached = try ctx.createOperation(Operation.State.init("test.detached", Location.getUnknown()));
594 try first.addOperation(op);
595 try second.addOperation(anchor);
596
597 try testing.expectError(error.OperationAlreadyInserted, second.addOperation(op));
598 try testing.expectError(error.OperationAlreadyInserted, second.insertBefore(op, anchor));
599 try testing.expectError(error.OperationMoveDetached, detached.moveBefore(anchor));
600 try testing.expectError(error.OperationMoveDetached, detached.moveToEnd(&second));
601 const first_head: *Operation = @ptrCast(@alignCast(first.operations.head.?));
602 const first_tail: *Operation = @ptrCast(@alignCast(first.operations.tail.?));
603 const second_head: *Operation = @ptrCast(@alignCast(second.operations.head.?));
604 const second_tail: *Operation = @ptrCast(@alignCast(second.operations.tail.?));
605 try testing.expect(first_head == op);
606 try testing.expect(first_tail == op);
607 try testing.expect(op.parent_block == &first);
608 try testing.expect(second_head == anchor);
609 try testing.expect(second_tail == anchor);
610 }
611
612 test "operation movement preserves operands and repairs successor predecessors" {
613 const testing = std.testing;
614 const allocator = testing.allocator;
615 const Operation = @import("operation/root.zig").Operation;
616 const context = @import("context/root.zig");
617
618 var ctx = try context.Context.init(allocator, context.Context.Limits.testing);
619
620 var source = Block.init(allocator);
621 defer source.deinit();
622 var target = Block.init(allocator);
623 defer target.deinit();
624 var successor = Block.init(allocator);
625 defer successor.deinit();
626 defer ctx.deinit(allocator);
627 try ctx.allowUnregistered();
628
629 const ty = try ctx.getDialectTypeFromName("test.i32");
630 var producer_state = Operation.State.init("test.producer", Location.getUnknown());
631 producer_state.addTypes(&.{ty});
632 const producer = try ctx.createOperation(producer_state);
633
634 var consumer_state = Operation.State.init("test.consumer", Location.getUnknown());
635 consumer_state.addOperands(&.{producer.getResult(0).?});
636 const consumer = try ctx.createOperation(consumer_state);
637
638 var branch_state = Operation.State.init("test.br", Location.getUnknown());
639 branch_state.addSuccessors(&.{&successor});
640 const branch = try ctx.createOperation(branch_state);
641
642 const anchor = try ctx.createOperation(Operation.State.init("test.anchor", Location.getUnknown()));
643
644 try source.addOperation(producer);
645 try source.addOperation(consumer);
646 try source.addOperation(branch);
647 try target.addOperation(anchor);
648
649 try testing.expectEqual(@as(usize, 1), producer.getResult(0).?.getNumUses());
650 try testing.expect(successor.hasPredecessor(&source));
651 try testing.expect(!successor.hasPredecessor(&target));
652
653 try consumer.moveBefore(anchor);
654 const source_head_after_consumer_move: *Operation = @ptrCast(@alignCast(source.operations.head.?));
655 const source_tail_after_consumer_move: *Operation = @ptrCast(@alignCast(source.operations.tail.?));
656 const target_head_after_consumer_move: *Operation = @ptrCast(@alignCast(target.operations.head.?));
657 try testing.expect(consumer.parent_block == &target);
658 try testing.expect(source_head_after_consumer_move == producer);
659 try testing.expect(source_tail_after_consumer_move == branch);
660 try testing.expect(producer.next_op == branch);
661 try testing.expect(branch.prev_op == producer);
662 try testing.expect(target_head_after_consumer_move == consumer);
663 try testing.expect(consumer.next_op == anchor);
664 try testing.expect(anchor.prev_op == consumer);
665 try testing.expect(consumer.getOperand(0).? == producer.getResult(0).?);
666 try testing.expectEqual(@as(usize, 1), producer.getResult(0).?.getNumUses());
667
668 try branch.moveToEnd(&target);
669 const source_head_after_branch_move: *Operation = @ptrCast(@alignCast(source.operations.head.?));
670 const source_tail_after_branch_move: *Operation = @ptrCast(@alignCast(source.operations.tail.?));
671 const target_tail_after_branch_move: *Operation = @ptrCast(@alignCast(target.operations.tail.?));
672 try testing.expect(branch.parent_block == &target);
673 try testing.expect(source_head_after_branch_move == producer);
674 try testing.expect(source_tail_after_branch_move == producer);
675 try testing.expect(target_tail_after_branch_move == branch);
676 try testing.expect(anchor.next_op == branch);
677 try testing.expect(branch.prev_op == anchor);
678 try testing.expect(!successor.hasPredecessor(&source));
679 try testing.expect(successor.hasPredecessor(&target));
680 }
681
682 test "block detach operation preserves operand uses" {
683 const testing = std.testing;
684 const allocator = testing.allocator;
685 const Operation = @import("operation/root.zig").Operation;
686 const context = @import("context/root.zig");
687
688 var ctx = try context.Context.init(allocator, context.Context.Limits.testing);
689 defer ctx.deinit(allocator);
690 try ctx.allowUnregistered();
691
692 var block = Block.init(allocator);
693 defer block.deinit();
694
695 const loc = Location.getUnknown();
696 const ty = try ctx.getDialectTypeFromName("test.i32");
697
698 var producer_state = Operation.State.init("test.producer", loc);
699 producer_state.addTypes(&.{ty});
700 const producer = try ctx.createOperation(producer_state);
701
702 var consumer_state = Operation.State.init("test.consumer", loc);
703 consumer_state.addOperands(&.{producer.getResult(0).?});
704 const consumer = try ctx.createOperation(consumer_state);
705
706 try block.addOperation(producer);
707 try block.addOperation(consumer);
708 try testing.expectEqual(@as(usize, 1), producer.getResult(0).?.getNumUses());
709
710 block.detachOperation(consumer);
711 try testing.expect(consumer.parent_block == null);
712 try testing.expectEqual(@as(usize, 1), producer.getResult(0).?.getNumUses());
713
714 try block.addOperation(consumer);
715 try testing.expectEqual(@as(usize, 1), producer.getResult(0).?.getNumUses());
716
717 block.removeOperation(consumer);
718 try testing.expectEqual(@as(usize, 0), producer.getResult(0).?.getNumUses());
719 }
720
721 test "block predecessor deduplication" {
722 const testing = std.testing;
723 const allocator = testing.allocator;
724 const Operation = @import("operation/root.zig").Operation;
725 const Context = @import("context/root.zig").Context;
726
727 var ctx = try Context.init(allocator, Context.Limits.testing);
728 var pred = Block.init(allocator);
729 var succ = Block.init(allocator);
730 defer {
731 ctx.deinit(allocator);
732 pred.deinit();
733 succ.deinit();
734 }
735 try ctx.allowUnregistered();
736
737 var state = Operation.State.init("test.duplicate_branch", .unknown);
738 state.addSuccessors(&.{ &succ, &succ, &succ });
739 try pred.addOperation(try ctx.createOperation(state));
740
741 try testing.expectEqual(@as(usize, 1), succ.getNumPredecessors());
742 }
743
744 test "block predecessor removal" {
745 const testing = std.testing;
746 const allocator = testing.allocator;
747 const Operation = @import("operation/root.zig").Operation;
748 const Context = @import("context/root.zig").Context;
749
750 var ctx = try Context.init(allocator, Context.Limits.testing);
751 var a = Block.init(allocator);
752 var b = Block.init(allocator);
753 var c = Block.init(allocator);
754 defer {
755 ctx.deinit(allocator);
756 a.deinit();
757 b.deinit();
758 c.deinit();
759 }
760 try ctx.allowUnregistered();
761
762 var a_state = Operation.State.init("test.a_branch", .unknown);
763 a_state.addSuccessors(&.{&c});
764 const a_branch = try ctx.createOperation(a_state);
765 try a.addOperation(a_branch);
766 var b_state = Operation.State.init("test.b_branch", .unknown);
767 b_state.addSuccessors(&.{&c});
768 const b_branch = try ctx.createOperation(b_state);
769 try b.addOperation(b_branch);
770 try testing.expectEqual(@as(usize, 2), c.getNumPredecessors());
771
772 a.removeOperation(a_branch);
773 try testing.expectEqual(@as(usize, 1), c.getNumPredecessors());
774 try testing.expect(!c.hasPredecessor(&a));
775 try testing.expect(c.hasPredecessor(&b));
776
777 b.removeOperation(b_branch);
778 try testing.expect(c.hasNoPredecessors());
779 }
780
781 test "block arguments keep identity across nine appends" {
782 const testing = std.testing;
783 const Context = @import("context/root.zig").Context;
784 const Operation = @import("operation/root.zig").Operation;
785 const verify = @import("verify.zig");
786 const dump = @import("dump.zig");
787
788 var block = Block.init(testing.allocator);
789 defer block.deinit();
790 var ctx = try Context.init(testing.allocator, Context.Limits.testing);
791 defer ctx.deinit(testing.allocator);
792 try ctx.allowUnregistered();
793 const typ = try ctx.getDialectTypeFromName("test.ty");
794 const first = try block.addArgument(typ, .unknown);
795 for (1..9) |_| _ = try block.addArgument(typ, .unknown);
796 try testing.expectEqual(first, block.getArgument(0).?);
797
798 var state = Operation.State.init("test.use", .unknown);
799 state.addOperands(&.{first});
800 const user = try ctx.createOperation(state);
801 try block.addOperation(user);
802 try verify.verifyBlock(&block, verify.default_options);
803 try testing.expect(first.hasOneUse());
804 const text = try dump.operationAlloc(testing.allocator, user);
805 defer testing.allocator.free(text);
806 try testing.expectEqualStrings("test.use(%0)\n", text);
807 }