lib/choir/src/core/region.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const alloc_arena = @import("alloc_arena");
3 const Block = @import("block.zig").Block;
4 const Mapping = @import("mapping.zig").Mapping;
5
6 pub const Region = struct {
7 allocator: std.mem.Allocator,
8
9 blocks: BlockList,
10
11 parent: ?*anyopaque,
12
13 pub const BlockList = struct {
14 head: ?*Block,
15 tail: ?*Block,
16 size: usize,
17
18 pub fn init() BlockList {
19 return .{
20 .head = null,
21 .tail = null,
22 .size = 0,
23 };
24 }
25
26 pub fn isEmpty(self: BlockList) bool {
27 return self.head == null;
28 }
29
30 pub fn front(self: BlockList) ?*Block {
31 return self.head;
32 }
33
34 pub fn back(self: BlockList) ?*Block {
35 return self.tail;
36 }
37 };
38
39 pub const BlockIterator = struct {
40 current: ?*Block,
41
42 pub fn next(self: *BlockIterator) ?*Block {
43 const block = self.current;
44 if (self.current) |b| {
45 self.current = b.next;
46 }
47 return block;
48 }
49 };
50
51 pub fn init(allocator: std.mem.Allocator) Region {
52 return .{
53 .allocator = allocator,
54 .blocks = BlockList.init(),
55 .parent = null,
56 };
57 }
58
59 pub fn deinit(self: *Region) void {
60 var current = self.blocks.head;
61 while (current) |block| {
62 const next = block.next;
63 block.deinit();
64 self.allocator.destroy(block);
65 current = next;
66 }
67 }
68
69 pub fn takeBody(self: *Region, source: *Region) !void {
70 if (self == source) return;
71 if (!source.empty() and !sameAllocator(self.allocator, source.allocator)) {
72 return error.RegionAllocatorMismatch;
73 }
74
75 self.deinit();
76 self.blocks = source.blocks;
77 source.blocks = BlockList.init();
78
79 var current = self.blocks.head;
80 while (current) |block| {
81 block.parent = self;
82 current = block.next;
83 }
84 }
85
86 pub fn dropAllReferences(self: *Region) void {
87 var blocks = self.getBlocks();
88 while (blocks.next()) |block| {
89 block.dropAllReferences();
90 }
91 }
92
93 pub fn hasNoDefinedValueUses(self: *Region) bool {
94 var blocks = self.getBlocks();
95 while (blocks.next()) |block| {
96 if (!block.hasNoDefinedValueUses()) return false;
97 }
98 return true;
99 }
100
101 pub fn dropAllDefinedValueUses(self: *Region) void {
102 var blocks = self.getBlocks();
103 while (blocks.next()) |block| {
104 block.dropAllDefinedValueUses();
105 }
106 }
107
108 pub fn walkOperations(
109 self: *Region,
110 options: @import("operation/root.zig").Operation.WalkOptions,
111 context: anytype,
112 callback: anytype,
113 ) anyerror!@import("operation/root.zig").Operation.WalkResult {
114 var blocks = self.getBlocks();
115 while (blocks.next()) |block| {
116 const result = try block.walkOperations(options, context, callback);
117 if (result.wasInterrupted()) return .interrupt;
118 }
119 return .advance;
120 }
121
122 pub fn cloneInto(self: *Region, dest: *Region, mapping: *Mapping) anyerror!void {
123 if (self == dest) return error.RegionCloneIntoSelf;
124
125 var source_block = self.blocks.head;
126 while (source_block) |block| : (source_block = block.next) {
127 const cloned_block = try dest.addBlock();
128 try mapping.mapBlock(block, cloned_block);
129 try cloned_block.arguments.ensureTotalCapacity(cloned_block.allocator, block.arguments.items.len);
130 for (block.arguments.items, 0..) |argument, index| {
131 const cloned_argument = try cloned_block.addArgument(
132 argument.type,
133 block.getArgumentLocation(index).?,
134 );
135 try mapping.mapValue(argument, cloned_argument);
136 }
137 }
138
139 source_block = self.blocks.head;
140 while (source_block) |block| : (source_block = block.next) {
141 const cloned_block = mapping.lookupBlock(block).?;
142 var ops = block.getOperations();
143 while (ops.next()) |op| {
144 const cloned_op = try op.cloneWithoutRegionsMapped(mapping, .{ .clone_operands = false });
145 try cloned_block.addOperation(cloned_op);
146 }
147 }
148
149 source_block = self.blocks.head;
150 while (source_block) |block| : (source_block = block.next) {
151 const cloned_block = mapping.lookupBlock(block).?;
152 var source_ops = block.getOperations();
153 var cloned_ops = cloned_block.getOperations();
154 while (source_ops.next()) |op| {
155 const cloned_op = cloned_ops.next().?;
156 try remapOperationBody(op, cloned_op, mapping);
157 }
158 }
159 }
160
161 pub fn empty(self: Region) bool {
162 return self.blocks.isEmpty();
163 }
164
165 pub fn hasOneBlock(self: Region) bool {
166 return self.blocks.size == 1;
167 }
168
169 pub fn getEntryBlock(self: Region) ?*Block {
170 return self.blocks.front();
171 }
172
173 pub fn addBlock(self: *Region) !*Block {
174 const block = try self.allocator.create(Block);
175 block.* = Block.init(self.allocator);
176 block.parent = self;
177 block.id = @intCast(self.blocks.size);
178
179 block.prev = self.blocks.tail;
180 block.next = null;
181 if (self.blocks.tail) |tail| {
182 tail.next = block;
183 } else {
184 self.blocks.head = block;
185 }
186 self.blocks.tail = block;
187 self.blocks.size += 1;
188
189 return block;
190 }
191
192 pub fn pushFront(self: *Region, block: *Block) void {
193 block.parent = self;
194 block.prev = null;
195 block.next = self.blocks.head;
196
197 if (self.blocks.head) |head| {
198 head.prev = block;
199 } else {
200 self.blocks.tail = block;
201 }
202 self.blocks.head = block;
203 self.blocks.size += 1;
204 }
205
206 pub fn pushBack(self: *Region, block: *Block) void {
207 block.parent = self;
208 block.prev = self.blocks.tail;
209 block.next = null;
210
211 if (self.blocks.tail) |tail| {
212 tail.next = block;
213 } else {
214 self.blocks.head = block;
215 }
216 self.blocks.tail = block;
217 self.blocks.size += 1;
218 }
219
220 pub fn eraseBlock(self: *Region, block: *Block) bool {
221 if (block.parent != @as(*anyopaque, @ptrCast(self))) return false;
222 if (!block.hasNoPredecessors()) return false;
223
224 var op_node = block.operations.tail;
225 while (op_node) |node| {
226 const op: *@import("operation/root.zig").Operation = @ptrCast(@alignCast(node));
227 op_node = op.prev_op;
228 op.erase();
229 }
230 std.debug.assert(block.hasNoDefinedValueUses());
231
232 const prev = block.prev;
233 const next = block.next;
234
235 if (prev) |prev_block| {
236 prev_block.next = next;
237 } else {
238 self.blocks.head = next;
239 }
240
241 if (next) |next_block| {
242 next_block.prev = prev;
243 } else {
244 self.blocks.tail = prev;
245 }
246
247 block.parent = null;
248 block.prev = null;
249 block.next = null;
250 self.blocks.size -= 1;
251
252 block.deinit();
253 self.allocator.destroy(block);
254 return true;
255 }
256
257 pub fn getParentOperation(self: *const Region) ?*@import("operation/root.zig").Operation {
258 const parent = self.parent orelse return null;
259 return @ptrCast(@alignCast(parent));
260 }
261
262 pub fn getBlocks(self: *Region) BlockIterator {
263 return BlockIterator{ .current = self.blocks.head };
264 }
265
266 pub fn format(self: Region, writer: *std.Io.Writer) std.Io.Writer.Error!void {
267 try writer.writeAll("{\n");
268 var current = self.blocks.head;
269 while (current) |block| {
270 try writer.print(" {f}\n", .{block.*});
271 current = block.next;
272 }
273 try writer.writeAll("}");
274 }
275
276 fn sameAllocator(a: std.mem.Allocator, b: std.mem.Allocator) bool {
277 return a.ptr == b.ptr and a.vtable == b.vtable;
278 }
279 };
280
281 fn remapOperationBody(source: *@import("operation/root.zig").Operation, dest: *@import("operation/root.zig").Operation, mapping: *Mapping) anyerror!void {
282 var operands: []*@import("value.zig").Value = &.{};
283 defer if (operands.len > 0) dest.allocator.free(operands);
284 if (source.operand_values.len > 0) {
285 operands = try dest.allocator.alloc(*@import("value.zig").Value, source.operand_values.len);
286 for (source.operand_values, 0..) |operand, i| {
287 operands[i] = mapping.lookupOrDefaultValue(operand);
288 }
289 }
290 try dest.replaceOperands(operands);
291
292 for (source.regions.items, 0..) |*region, i| {
293 try region.cloneInto(&dest.regions.items[i], mapping);
294 }
295 }
296
297 test "region takeBody transfers blocks and repairs parents" {
298 const testing = std.testing;
299
300 var source = Region.init(testing.allocator);
301 defer source.deinit();
302 var dest = Region.init(testing.allocator);
303 defer dest.deinit();
304
305 const old_dest_block = try dest.addBlock();
306 try testing.expect(old_dest_block.parent == @as(*anyopaque, @ptrCast(&dest)));
307
308 const first = try source.addBlock();
309 const second = try source.addBlock();
310 try testing.expectEqual(@as(usize, 2), source.blocks.size);
311
312 try dest.takeBody(&source);
313
314 try testing.expect(source.empty());
315 try testing.expectEqual(@as(usize, 0), source.blocks.size);
316 try testing.expectEqual(@as(usize, 2), dest.blocks.size);
317 try testing.expect(dest.blocks.head == first);
318 try testing.expect(dest.blocks.tail == second);
319 try testing.expect(first.parent == @as(*anyopaque, @ptrCast(&dest)));
320 try testing.expect(second.parent == @as(*anyopaque, @ptrCast(&dest)));
321 try testing.expect(first.prev == null);
322 try testing.expect(first.next == second);
323 try testing.expect(second.prev == first);
324 try testing.expect(second.next == null);
325 }
326
327 test "region takeBody rejects non-empty allocator mismatch" {
328 const testing = std.testing;
329
330 var arena = alloc_arena.Arena.init(testing.allocator);
331 defer arena.deinit();
332
333 var source = Region.init(arena.allocator());
334 defer source.deinit();
335 var dest = Region.init(testing.allocator);
336 defer dest.deinit();
337
338 _ = try source.addBlock();
339
340 try testing.expectError(error.RegionAllocatorMismatch, dest.takeBody(&source));
341 try testing.expect(!source.empty());
342 try testing.expect(dest.empty());
343 }