lib/choir/src/backends/x64/legality.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 //! x86_64 target legality for the SysV machine-code emitter.
2
3 const std = @import("std");
4 const alloc_arena = @import("alloc_arena");
5 const ir = @import("../../core/root.zig");
6 const dialects = @import("../../dialects/root.zig");
7 const diagnostics = @import("../../root.zig").diagnostics;
8 const artifact = @import("../root.zig").artifact;
9 const boundary = @import("../root.zig").signature;
10 const interface = @import("../root.zig").interface;
11 const machine = @import("../root.zig").machine_code;
12 const abi = @import("abi.zig");
13 const data = @import("data.zig");
14
15 const BackendError = interface.BackendError;
16 const FuncDialect = dialects.FuncDialect;
17
18 /// Diagnostic stage recorded on legality failures.
19 pub const stage = "backend/x86_64/legality";
20
21 /// An operation shape the SysV emitter cannot represent.
22 pub const Violation = enum {
23 /// More results than one result record holds.
24 too_many_results,
25 /// A vector among several results. A vector result returns alone.
26 vector_in_product,
27 /// Data-symbol attributes that do not name read-only bytes on a 64-bit integer constant.
28 malformed_data_symbol,
29 /// A function definition with more parameters than a signature records.
30 too_many_parameters,
31 /// A function definition parameter or result whose type has no boundary equivalent.
32 unsupported_boundary_type,
33 /// A vector parameter of a function definition.
34 vector_parameter,
35 /// A vector argument of a call.
36 vector_argument,
37 };
38
39 const Offender = struct {
40 operation: ?*ir.Operation = null,
41 violation: Violation = .too_many_results,
42 };
43
44 /// Rejects the first operation the emitter cannot represent: a function, call, or return with
45 /// unrepresentable results, a call with a vector argument, a function definition whose signature
46 /// this backend cannot record or pass, or an operation with malformed data-symbol attributes.
47 /// Fails with `error.UnsupportedOperation` and reports one error diagnostic located at that
48 /// operation.
49 pub fn checkModule(module: *ir.Operation) BackendError!void {
50 std.debug.assert(module.regions.items.len == 1);
51 var offender = Offender{};
52 const walked = module.walk(.{ .order = .pre_order }, &offender, visit) catch unreachable;
53 if (walked != .interrupt) {
54 std.debug.assert(offender.operation == null);
55 return;
56 }
57 return reject(offender);
58 }
59
60 fn visit(offender: *Offender, op: *ir.Operation) ir.WalkResult {
61 std.debug.assert(offender.operation == null);
62 const violation = violationOf(op) orelse return .advance;
63 offender.* = .{ .operation = op, .violation = violation };
64 return .interrupt;
65 }
66
67 /// Classifies `op`, or returns `null` when the emitter can represent it.
68 pub fn violationOf(op: *ir.Operation) ?Violation {
69 _ = data.symbolOf(op) catch return .malformed_data_symbol;
70 const name = op.name.name;
71 const is_function = std.mem.eql(u8, name, FuncDialect.FuncOp.operation_name);
72 const is_return = std.mem.eql(u8, name, FuncDialect.ReturnOp.operation_name);
73 const is_call = std.mem.eql(u8, name, FuncDialect.CallOp.operation_name);
74 if (!is_function and !is_return and !is_call) return null;
75 if (resultViolation(op, is_return)) |violation| return violation;
76 if (is_call) return argumentViolation(op);
77 if (!is_function or op.getRegion(0) == null) return null;
78 return boundaryViolation(op);
79 }
80
81 fn argumentViolation(call: *ir.Operation) ?Violation {
82 for (call.operands.items) |operand| {
83 const type_name = operand.value.type.getDialectTypeName() orelse continue;
84 if (dialects.arith.parseVectorTypeName(type_name) != null) return .vector_argument;
85 }
86 return null;
87 }
88
89 fn resultViolation(op: *ir.Operation, is_return: bool) ?Violation {
90 const count = if (is_return) op.operands.items.len else op.results.items.len;
91 if (count > abi.max_result_count) return .too_many_results;
92 if (count < 2) return null;
93 for (0..count) |index| {
94 const result_type = if (is_return)
95 op.operands.items[index].value.type
96 else
97 op.results.items[index].type;
98 const type_name = result_type.getDialectTypeName() orelse continue;
99 if (dialects.arith.parseVectorTypeName(type_name) != null) return .vector_in_product;
100 }
101 return null;
102 }
103
104 fn boundaryViolation(func: *ir.Operation) ?Violation {
105 const recorded = boundary.ofFunction(func) catch |err| return switch (err) {
106 error.TooManyParameters => .too_many_parameters,
107 error.TooManyResults => unreachable,
108 error.UnsupportedType => .unsupported_boundary_type,
109 };
110 for (recorded.parameters()) |parameter| {
111 if (parameter == .vector) return .vector_parameter;
112 }
113 std.debug.assert(abi.admitsSignature(&recorded));
114 return null;
115 }
116
117 fn reject(offender: Offender) BackendError {
118 const op = offender.operation.?;
119 std.debug.assert(violationOf(op) == offender.violation);
120 const message = switch (offender.violation) {
121 .too_many_results => std.fmt.comptimePrint(
122 "x86_64 functions, calls, and returns carry at most {d} results",
123 .{abi.max_result_count},
124 ),
125 .vector_in_product => "x86_64 functions, calls, and returns with several results " ++
126 "carry scalars and memrefs only",
127 .malformed_data_symbol => std.fmt.comptimePrint(
128 "x86_64 data symbols need an arith.constant of type arith.i64, arith.u64, or " ++
129 "arith.index whose choir.backend.data_symbol attributes give a nonempty string " ++
130 "name, nonempty string bytes, and an optional integer alignment that is a power " ++
131 "of two up to {d}",
132 .{machine.max_data_alignment},
133 ),
134 .too_many_parameters => std.fmt.comptimePrint(
135 "x86_64 functions take at most {d} parameters",
136 .{artifact.Signature.max_parameters},
137 ),
138 .unsupported_boundary_type => "x86_64 function parameters and results take memref " ++
139 "and arith types other than arith.f16, arith.bf16, and their vectors",
140 .vector_parameter => "x86_64 function parameters take scalars and memrefs but not vectors",
141 .vector_argument => "x86_64 calls pass scalars and memrefs but not vectors",
142 };
143 var in_flight = op.emitError(message);
144 defer in_flight.deinit();
145 in_flight.addMetadata("choir.stage", stage) catch {};
146 _ = in_flight.emit() catch {};
147 return BackendError.UnsupportedOperation;
148 }
149
150 const Recorder = struct {
151 seen: usize = 0,
152 operation: ?*ir.Operation = null,
153 stage: []const u8 = "",
154
155 fn handle(
156 context: ?*anyopaque,
157 diagnostic: *const diagnostics.Diagnostic,
158 ) !diagnostics.HandlerResult {
159 const self: *Recorder = @ptrCast(@alignCast(context.?));
160 self.seen += 1;
161 self.operation = diagnostic.operation;
162 for (diagnostic.metadata) |metadata| {
163 if (std.mem.eql(u8, metadata.name, "choir.stage")) self.stage = metadata.value;
164 }
165 return .consumed;
166 }
167 };
168
169 test "x86_64 legality admits scalar products and rejects unrepresentable results" {
170 var arena = alloc_arena.Arena.init(std.testing.allocator);
171 defer arena.deinit();
172 const allocator = arena.allocator();
173 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
174 defer ctx.deinit(allocator);
175 try dialects.registerAllDialects(&ctx);
176
177 const loc = ir.Location.getFile("legality.choir", 3, 5);
178 const i64_type = try dialects.ArithDialect.getScalarType(&ctx, .i64);
179 const module = try dialects.BuiltinDialect.ModuleOp.create(&ctx, loc);
180 const pair_types = [_]ir.Type{ i64_type, i64_type };
181 const pair = try FuncDialect.FuncOp.create(&ctx, loc, "pair", &.{i64_type}, &pair_types);
182 try module.getBodyBlock().addOperation(pair.op);
183 const argument = pair.getArgument(0);
184 const pair_ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{ argument, argument });
185 try pair.getEntryBlock().addOperation(pair_ret.op);
186
187 var recorder = Recorder{};
188 _ = try ctx.registerDiagnosticHandler(.{ .context = &recorder, .handle = Recorder.handle });
189 try checkModule(module.op);
190 try std.testing.expectEqual(@as(usize, 0), recorder.seen);
191
192 var wide_types: [abi.max_result_count + 1]ir.Type = undefined;
193 @memset(&wide_types, i64_type);
194 const wide = try FuncDialect.FuncOp.create(&ctx, loc, "wide", &.{i64_type}, &wide_types);
195 try module.getBodyBlock().addOperation(wide.op);
196 try std.testing.expectError(BackendError.UnsupportedOperation, checkModule(module.op));
197 try std.testing.expectEqual(@as(usize, 1), recorder.seen);
198 try std.testing.expectEqual(wide.op, recorder.operation.?);
199 try std.testing.expectEqualStrings(stage, recorder.stage);
200
201 const float64 = dialects.arith.type_names.float64;
202 const vec_type = (try dialects.ArithDialect.getVecType(&ctx, 2, float64)).?;
203 const vectors = try dialects.BuiltinDialect.ModuleOp.create(&ctx, loc);
204 const mixed_types = [_]ir.Type{ vec_type, i64_type };
205 const mixed = try FuncDialect.FuncOp.create(&ctx, loc, "mixed", &.{vec_type}, &mixed_types);
206 try vectors.getBodyBlock().addOperation(mixed.op);
207 try std.testing.expectEqual(Violation.vector_in_product, violationOf(mixed.op).?);
208 try std.testing.expectError(BackendError.UnsupportedOperation, checkModule(vectors.op));
209 try std.testing.expectEqual(@as(usize, 2), recorder.seen);
210 try std.testing.expectEqual(mixed.op, recorder.operation.?);
211 }
212
213 test "x86_64 legality rejects function boundaries it cannot record" {
214 var arena = alloc_arena.Arena.init(std.testing.allocator);
215 defer arena.deinit();
216 const allocator = arena.allocator();
217 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
218 defer ctx.deinit(allocator);
219 try dialects.registerAllDialects(&ctx);
220
221 const loc = ir.Location.getFile("legality.choir", 12, 1);
222 const i64_type = try dialects.ArithDialect.getScalarType(&ctx, .i64);
223 const f16_type = try dialects.ArithDialect.getScalarType(&ctx, .f16);
224 const float64 = dialects.arith.type_names.float64;
225 const vec_type = (try dialects.ArithDialect.getVecType(&ctx, 2, float64)).?;
226 var wide: [artifact.Signature.max_parameters + 1]ir.Type = undefined;
227 @memset(&wide, i64_type);
228 const Case = struct { parameters: []const ir.Type, violation: Violation };
229 const cases = [_]Case{
230 .{ .parameters = &.{f16_type}, .violation = .unsupported_boundary_type },
231 .{ .parameters = &.{ i64_type, vec_type }, .violation = .vector_parameter },
232 .{ .parameters = &wide, .violation = .too_many_parameters },
233 };
234
235 var recorder = Recorder{};
236 _ = try ctx.registerDiagnosticHandler(.{ .context = &recorder, .handle = Recorder.handle });
237 for (cases, 1..) |case, seen| {
238 const module = try dialects.BuiltinDialect.ModuleOp.create(&ctx, loc);
239 const results = [_]ir.Type{i64_type};
240 const function = try FuncDialect.FuncOp.create(&ctx, loc, "f", case.parameters, &results);
241 try module.getBodyBlock().addOperation(function.op);
242 try std.testing.expectEqual(@as(?Violation, case.violation), violationOf(function.op));
243 try std.testing.expectError(BackendError.UnsupportedOperation, checkModule(module.op));
244 try std.testing.expectEqual(seen, recorder.seen);
245 try std.testing.expectEqual(function.op, recorder.operation.?);
246 try std.testing.expectEqualStrings(stage, recorder.stage);
247 }
248
249 const halves = [_]ir.Type{f16_type};
250 const declared = try FuncDialect.FuncOp.createDeclaration(&ctx, loc, "d", &halves, &halves);
251 try std.testing.expectEqual(@as(?Violation, null), violationOf(declared.op));
252 }
253
254 test "x86_64 legality rejects vector call arguments at the call" {
255 var arena = alloc_arena.Arena.init(std.testing.allocator);
256 defer arena.deinit();
257 const allocator = arena.allocator();
258 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
259 defer ctx.deinit(allocator);
260 try dialects.registerAllDialects(&ctx);
261
262 const loc = ir.Location.getFile("legality.choir", 21, 9);
263 const f64_type = try dialects.ArithDialect.getF64Type(&ctx);
264 const float64 = dialects.arith.type_names.float64;
265 const vec_type = (try dialects.ArithDialect.getVecType(&ctx, 2, float64)).?;
266 const module = try dialects.BuiltinDialect.ModuleOp.create(&ctx, loc);
267 const sink_types = [_]ir.Type{vec_type};
268 const results = [_]ir.Type{f64_type};
269 const sink = try FuncDialect.FuncOp.createDeclaration(&ctx, loc, "sink", &sink_types, &results);
270 try module.getBodyBlock().addOperation(sink.op);
271 const function = try FuncDialect.FuncOp.create(&ctx, loc, "f", &.{f64_type}, &.{f64_type});
272 try module.getBodyBlock().addOperation(function.op);
273 const entry = function.getEntryBlock();
274 const splat = dialects.ArithDialect.SplatOp;
275 const lanes = try splat.create(&ctx, loc, function.getArgument(0), vec_type);
276 try entry.addOperation(lanes.op);
277 const call = try FuncDialect.CallOp.create(&ctx, loc, "sink", &.{lanes.getResult()}, &results);
278 try entry.addOperation(call.op);
279 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{call.getResult(0).?});
280 try entry.addOperation(ret.op);
281
282 var recorder = Recorder{};
283 _ = try ctx.registerDiagnosticHandler(.{ .context = &recorder, .handle = Recorder.handle });
284 try std.testing.expectEqual(@as(?Violation, .vector_argument), violationOf(call.op));
285 try std.testing.expectEqual(@as(?Violation, null), violationOf(sink.op));
286 try std.testing.expectError(BackendError.UnsupportedOperation, checkModule(module.op));
287 try std.testing.expectEqual(@as(usize, 1), recorder.seen);
288 try std.testing.expectEqual(call.op, recorder.operation.?);
289 try std.testing.expectEqualStrings(stage, recorder.stage);
290 }
291
292 test "x86_64 legality rejects malformed data symbols at their constant" {
293 var arena = alloc_arena.Arena.init(std.testing.allocator);
294 defer arena.deinit();
295 const allocator = arena.allocator();
296 var ctx = try ir.Context.init(allocator, ir.Context.Limits.testing);
297 defer ctx.deinit(allocator);
298 try dialects.registerAllDialects(&ctx);
299
300 const loc = ir.Location.getFile("legality.choir", 9, 3);
301 const i64_type = try dialects.ArithDialect.getScalarType(&ctx, .i64);
302 const module = try dialects.BuiltinDialect.ModuleOp.create(&ctx, loc);
303 const function = try FuncDialect.FuncOp.create(&ctx, loc, "table", &.{}, &.{i64_type});
304 try module.getBodyBlock().addOperation(function.op);
305 const constant = try dialects.ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, 0);
306 try function.getEntryBlock().addOperation(constant.op);
307 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, &.{constant.getResult()});
308 try function.getEntryBlock().addOperation(ret.op);
309
310 var recorder = Recorder{};
311 _ = try ctx.registerDiagnosticHandler(.{ .context = &recorder, .handle = Recorder.handle });
312 const names = machine.data_symbol_attr_names;
313 try constant.op.setAttr(names.bytes, try ctx.getStringAttr("\x01\x02"));
314 try std.testing.expectEqual(Violation.malformed_data_symbol, violationOf(constant.op).?);
315 try std.testing.expectError(BackendError.UnsupportedOperation, checkModule(module.op));
316 try std.testing.expectEqual(@as(usize, 1), recorder.seen);
317 try std.testing.expectEqual(constant.op, recorder.operation.?);
318 try std.testing.expectEqualStrings(stage, recorder.stage);
319
320 try constant.op.setAttr(names.name, try ctx.getStringAttr("table"));
321 try std.testing.expectEqual(@as(?Violation, null), violationOf(constant.op));
322 try checkModule(module.op);
323 try std.testing.expectEqual(@as(usize, 1), recorder.seen);
324 }