lib/choir/src/core/traits.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const Operation = @import("operation/root.zig").Operation;
3 const Block = @import("block.zig").Block;
4 const Value = @import("value.zig").Value;
5 const Context = @import("context/root.zig").Context;
6 const interfaces = @import("interfaces/root.zig");
7
8 pub const TraitError = error{
9 OperandCountMismatch,
10 ResultCountMismatch,
11 RegionCountMismatch,
12 SingleBlockRegionMismatch,
13 ImplicitTerminatorMismatch,
14 TerminatorNotLast,
15 IsolatedFromAbove,
16 SameOperandsAndResultTypeMismatch,
17 SameTypeOperandsMismatch,
18 TypesMatchWithMismatch,
19 };
20
21 fn isValueWithin(root: *const Operation, value: *const Value) bool {
22 return switch (value.kind) {
23 .block_argument => |info| blk: {
24 const block: *const Block = @ptrCast(@alignCast(info.owner));
25 const parent_op = block.getParentOperation() orelse break :blk false;
26 break :blk root.isAncestor(parent_op);
27 },
28 .op_result => |info| root.isProperAncestor(@ptrCast(@alignCast(info.owner))),
29 };
30 }
31
32 pub fn verifyOperandsWithin(root: *const Operation, candidate: *const Operation) TraitError!void {
33 for (candidate.operands.items) |operand| {
34 if (!isValueWithin(root, operand.value)) {
35 return TraitError.IsolatedFromAbove;
36 }
37 }
38 }
39
40 fn verifyOperationOperandsWithin(root: *const Operation, candidate: *const Operation, check_candidate: bool) TraitError!void {
41 if (check_candidate) {
42 try verifyOperandsWithin(root, candidate);
43 }
44
45 for (candidate.regions.items) |*region| {
46 var block = region.blocks.head;
47 while (block) |current_block| {
48 var op_node = current_block.operations.head;
49 while (op_node) |node| {
50 const nested_op: *const Operation = @ptrCast(@alignCast(node));
51 try verifyOperationOperandsWithin(root, nested_op, true);
52 op_node = nested_op.next_op;
53 }
54 block = current_block.next;
55 }
56 }
57 }
58
59 fn verifySingleBlockRegions(op: *const Operation) TraitError!void {
60 for (op.regions.items) |region| {
61 if (!region.hasOneBlock()) return TraitError.SingleBlockRegionMismatch;
62 }
63 }
64
65 pub fn registerOperationTrait(ctx: *Context, op_name: []const u8, comptime Trait: type) anyerror!void {
66 if (@hasDecl(Trait, "traits")) {
67 _ = try ctx.registerOperation(op_name, Trait.traits);
68 }
69
70 ctx.registerTraitDefinition(Trait.entry()) catch |err| switch (err) {
71 error.DuplicateTrait => {},
72 else => return err,
73 };
74
75 try ctx.registerOperationTraitId(op_name, Trait.id);
76 }
77
78 pub fn NOperands(comptime count: usize) type {
79 return struct {
80 pub const trait_name = std.fmt.comptimePrint("ir.trait.n_operands.{d}", .{count});
81 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
82
83 fn verify(op_ptr: *const anyopaque) anyerror!void {
84 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
85 if (op.operands.items.len != count) return TraitError.OperandCountMismatch;
86 }
87
88 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
89
90 pub fn entry() interfaces.TraitEntry {
91 return .{ .id = id, .vtable = &vtable };
92 }
93 };
94 }
95
96 pub fn NResults(comptime count: usize) type {
97 return struct {
98 pub const trait_name = std.fmt.comptimePrint("ir.trait.n_results.{d}", .{count});
99 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
100
101 fn verify(op_ptr: *const anyopaque) anyerror!void {
102 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
103 if (op.results.items.len != count) return TraitError.ResultCountMismatch;
104 }
105
106 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
107
108 pub fn entry() interfaces.TraitEntry {
109 return .{ .id = id, .vtable = &vtable };
110 }
111 };
112 }
113
114 pub const ZeroOperands = NOperands(0);
115 pub const OneOperand = NOperands(1);
116 pub const ZeroResults = NResults(0);
117 pub const OneResult = NResults(1);
118
119 pub fn NRegions(comptime count: usize) type {
120 return struct {
121 pub const trait_name = std.fmt.comptimePrint("ir.trait.n_regions.{d}", .{count});
122 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
123
124 fn verify(op_ptr: *const anyopaque) anyerror!void {
125 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
126 if (op.regions.items.len != count) return TraitError.RegionCountMismatch;
127 }
128
129 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
130
131 pub fn entry() interfaces.TraitEntry {
132 return .{ .id = id, .vtable = &vtable };
133 }
134 };
135 }
136
137 pub fn AtLeastNRegions(comptime count: usize) type {
138 return struct {
139 pub const trait_name = std.fmt.comptimePrint("ir.trait.at_least_n_regions.{d}", .{count});
140 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
141
142 fn verify(op_ptr: *const anyopaque) anyerror!void {
143 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
144 if (op.regions.items.len < count) return TraitError.RegionCountMismatch;
145 }
146
147 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
148
149 pub fn entry() interfaces.TraitEntry {
150 return .{ .id = id, .vtable = &vtable };
151 }
152 };
153 }
154
155 pub fn AtMostNRegions(comptime count: usize) type {
156 return struct {
157 pub const trait_name = std.fmt.comptimePrint("ir.trait.at_most_n_regions.{d}", .{count});
158 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
159
160 fn verify(op_ptr: *const anyopaque) anyerror!void {
161 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
162 if (op.regions.items.len > count) return TraitError.RegionCountMismatch;
163 }
164
165 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
166
167 pub fn entry() interfaces.TraitEntry {
168 return .{ .id = id, .vtable = &vtable };
169 }
170 };
171 }
172
173 pub const ZeroRegions = NRegions(0);
174 pub const OneRegion = NRegions(1);
175
176 pub const SingleBlock = struct {
177 pub const trait_name = "ir.trait.single_block";
178 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
179
180 fn verify(op_ptr: *const anyopaque) anyerror!void {
181 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
182 try verifySingleBlockRegions(op);
183 }
184
185 pub const vtable: interfaces.TraitVTable = .{ .verify_regions = verify };
186
187 pub fn entry() interfaces.TraitEntry {
188 return .{ .id = id, .vtable = &vtable };
189 }
190 };
191
192 pub fn SingleBlockImplicitTerminator(comptime terminator_name: []const u8) type {
193 return struct {
194 pub const trait_name = std.fmt.comptimePrint(
195 "ir.trait.single_block_implicit_terminator.{s}",
196 .{terminator_name},
197 );
198 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
199
200 fn verify(op_ptr: *const anyopaque) anyerror!void {
201 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
202 try verifySingleBlockRegions(op);
203 for (op.regions.items) |region| {
204 const block = region.getEntryBlock() orelse return TraitError.SingleBlockRegionMismatch;
205 const term_any = block.getTerminator() orelse return TraitError.ImplicitTerminatorMismatch;
206 const term: *const Operation = @ptrCast(@alignCast(term_any));
207 if (!std.mem.eql(u8, term.name.name, terminator_name)) {
208 return TraitError.ImplicitTerminatorMismatch;
209 }
210 }
211 }
212
213 pub const vtable: interfaces.TraitVTable = .{ .verify_regions = verify };
214
215 pub fn entry() interfaces.TraitEntry {
216 return .{ .id = id, .vtable = &vtable };
217 }
218 };
219 }
220
221 pub const Terminator = struct {
222 pub const trait_name = "ir.trait.terminator";
223 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
224 pub const traits = interfaces.OperationTraits{ .is_terminator = true };
225
226 fn verify(op_ptr: *const anyopaque) anyerror!void {
227 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
228 if (op.getBlock() == null) return;
229 if (op.next_op != null) return TraitError.TerminatorNotLast;
230 }
231
232 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
233
234 pub fn entry() interfaces.TraitEntry {
235 return .{ .id = id, .vtable = &vtable };
236 }
237 };
238
239 pub const NoTerminator = struct {
240 pub const trait_name = "ir.trait.no_terminator";
241 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
242 pub const traits = interfaces.OperationTraits{ .has_no_terminator = true };
243
244 fn verify(op_ptr: *const anyopaque) anyerror!void {
245 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
246 try verifySingleBlockRegions(op);
247 }
248
249 pub const vtable: interfaces.TraitVTable = .{ .verify_regions = verify };
250
251 pub fn entry() interfaces.TraitEntry {
252 return .{ .id = id, .vtable = &vtable };
253 }
254 };
255
256 pub const HasOnlyGraphRegion = struct {
257 pub const trait_name = "ir.trait.has_only_graph_region";
258 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
259 pub const traits = interfaces.OperationTraits{ .has_only_graph_regions = true };
260
261 pub const vtable: interfaces.TraitVTable = .{};
262
263 pub fn entry() interfaces.TraitEntry {
264 return .{ .id = id, .vtable = &vtable };
265 }
266 };
267
268 pub const SameOperandsAndResultType = struct {
269 pub const trait_name = "ir.trait.same_operands_and_result_type";
270 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
271
272 fn verify(op_ptr: *const anyopaque) anyerror!void {
273 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
274 if (op.results.items.len == 0) return TraitError.SameOperandsAndResultTypeMismatch;
275 if (op.operands.items.len == 0) return TraitError.SameOperandsAndResultTypeMismatch;
276
277 const ref_type = op.results.items[0].type;
278 for (op.results.items) |result| {
279 if (!result.type.eql(ref_type)) return TraitError.SameOperandsAndResultTypeMismatch;
280 }
281 for (op.operands.items) |operand| {
282 if (!operand.value.type.eql(ref_type)) return TraitError.SameOperandsAndResultTypeMismatch;
283 }
284 }
285
286 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
287
288 pub fn entry() interfaces.TraitEntry {
289 return .{ .id = id, .vtable = &vtable };
290 }
291 };
292
293 pub const SameTypeOperands = struct {
294 pub const trait_name = "ir.trait.same_type_operands";
295 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
296
297 fn verify(op_ptr: *const anyopaque) anyerror!void {
298 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
299 if (op.operands.items.len < 2) return;
300
301 const ref_type = op.operands.items[0].value.type;
302 for (op.operands.items[1..]) |operand| {
303 if (!operand.value.type.eql(ref_type)) {
304 return TraitError.SameTypeOperandsMismatch;
305 }
306 }
307 }
308
309 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
310
311 pub fn entry() interfaces.TraitEntry {
312 return .{ .id = id, .vtable = &vtable };
313 }
314 };
315
316 pub const TypeRef = union(enum) {
317 operand: usize,
318 result: usize,
319 };
320
321 pub const TypesMatchWithConfig = struct {
322 label: []const u8,
323 target: TypeRef,
324 source: TypeRef,
325 };
326
327 pub fn TypesMatchWith(comptime config: TypesMatchWithConfig) type {
328 return struct {
329 pub const trait_name = std.fmt.comptimePrint(
330 "ir.trait.types_match_with.{s}.{s}{d}_{s}{d}",
331 .{
332 config.label,
333 @tagName(config.target),
334 switch (config.target) {
335 inline else => |idx| idx,
336 },
337 @tagName(config.source),
338 switch (config.source) {
339 inline else => |idx| idx,
340 },
341 },
342 );
343 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
344
345 fn typeAt(op: *const Operation, ref: TypeRef) ?@import("type.zig").Type {
346 return switch (ref) {
347 .operand => |idx| if (idx < op.operands.items.len)
348 op.operands.items[idx].value.type
349 else
350 null,
351 .result => |idx| if (idx < op.results.items.len)
352 op.results.items[idx].type
353 else
354 null,
355 };
356 }
357
358 fn verify(op_ptr: *const anyopaque) anyerror!void {
359 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
360 const target_type = typeAt(op, config.target) orelse
361 return TraitError.TypesMatchWithMismatch;
362 const source_type = typeAt(op, config.source) orelse
363 return TraitError.TypesMatchWithMismatch;
364 if (!target_type.eql(source_type)) {
365 return TraitError.TypesMatchWithMismatch;
366 }
367 }
368
369 pub const vtable: interfaces.TraitVTable = .{ .verify = verify };
370
371 pub fn entry() interfaces.TraitEntry {
372 return .{ .id = id, .vtable = &vtable };
373 }
374 };
375 }
376
377 pub const IsolatedFromAbove = struct {
378 pub const trait_name = "ir.trait.isolated_from_above";
379 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
380
381 fn verify(op_ptr: *const anyopaque) anyerror!void {
382 const op: *const Operation = @ptrCast(@alignCast(op_ptr));
383 try verifyOperationOperandsWithin(op, op, false);
384 }
385
386 pub const vtable: interfaces.TraitVTable = .{ .verify_regions = verify };
387
388 pub fn entry() interfaces.TraitEntry {
389 return .{ .id = id, .vtable = &vtable };
390 }
391 };
392
393 pub const SymbolTable = struct {
394 pub const trait_name = "ir.trait.symbol_table";
395 pub const id: interfaces.TraitId = interfaces.traitId(trait_name);
396 pub const traits = interfaces.OperationTraits{ .is_symbol_table = true };
397
398 fn verify(op_ptr: *const anyopaque) anyerror!void {
399 const op: *Operation = @ptrCast(@alignCast(@constCast(op_ptr)));
400 try @import("symbols.zig").SymbolTable.verifyOperation(op);
401 }
402
403 pub const vtable: interfaces.TraitVTable = .{ .verify_regions = verify };
404
405 pub fn entry() interfaces.TraitEntry {
406 return .{ .id = id, .vtable = &vtable };
407 }
408 };