lib/choir/src/properties/codegen.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const hypothesis = @import("hypothesis");
3 const choir = @import("choir");
4
5 const ir = choir.ir;
6 const ArithDialect = choir.dialects.ArithDialect;
7 const CmpPredicate = choir.dialects.arith.CmpPredicate;
8 const FuncDialect = choir.dialects.FuncDialect;
9 const BuiltinDialect = choir.dialects.BuiltinDialect;
10 const ScfDialect = choir.dialects.ScfDialect;
11 const Evaluator = choir.eval.Evaluator;
12 const x86_64_backend = choir.backends.x86_64;
13 const CallValue = x86_64_backend.invoke.Value;
14
15 pub const has_jit = @hasDecl(x86_64_backend, "jit");
16
17 const max_args = 4;
18 const max_ops = 16;
19 const max_results = 3;
20 const helper_arg_count = 4;
21 const helper_name = "diff_helper";
22 const pair_helper_name = "diff_pair";
23 const triple_helper_name = "diff_triple";
24 const function_name = "diff_fn";
25
26 pub fn settings() hypothesis.Settings {
27 var configured = hypothesis.Settings.dev()
28 .withSeed(0x5149_525f_4a49_5421)
29 .withDatabase("zig-out/hypothesis-failures/choir-codegen");
30 configured.per_example_leak_check = true;
31 return configured;
32 }
33
34 const interesting_values = [_]i64{
35 0, 1, -1, 2, -2,
36 3, 7, 8, 16, 255,
37 256, -256, 1000, -1000, 65535,
38 65536, -65536, 2147483647, -2147483648, 4294967296,
39 1099511627776, -1099511627776, std.math.maxInt(i64), std.math.minInt(i64),
40 };
41
42 const interesting_divisors = [_]i64{
43 1, 2, -2, 3, -3, 5, -5, 7, -7, 16, -16, 255, -255, 1000, -1000, std.math.maxInt(i64), std.math.minInt(i64),
44 };
45
46 const BinOpKind = enum { add, sub, mul, max, min, band, bor, bxor };
47 const UnaryOpKind = enum { neg, abs, bnot };
48 const ShiftOpKind = enum { shl, shr, ushr };
49 const DivRemOpKind = enum { div, rem };
50 fn drawUsize(
51 conjecture: *hypothesis.ConjectureData,
52 min: usize,
53 max: usize,
54 shrink_towards: usize,
55 ) !usize {
56 return @intCast(try conjecture.drawInteger(
57 @intCast(min),
58 @intCast(max),
59 @intCast(shrink_towards),
60 ));
61 }
62
63 fn drawValue(conjecture: *hypothesis.ConjectureData) !i64 {
64 if (try conjecture.drawBoolean()) {
65 return interesting_values[try drawUsize(conjecture, 0, interesting_values.len - 1, 0)];
66 }
67 const raw = try drawUsize(conjecture, 0, 1 << 16, 1 << 15);
68 return @as(i64, @intCast(raw)) - (1 << 15);
69 }
70
71 fn drawShiftCount(conjecture: *hypothesis.ConjectureData) !i64 {
72 return @intCast(try drawUsize(conjecture, 0, 63, 0));
73 }
74
75 fn drawLoopCount(conjecture: *hypothesis.ConjectureData) !i64 {
76 return @intCast(try drawUsize(conjecture, 0, 8, 0));
77 }
78
79 fn drawDivisor(conjecture: *hypothesis.ConjectureData) !i64 {
80 if (try conjecture.drawBoolean()) {
81 return interesting_divisors[try drawUsize(conjecture, 0, interesting_divisors.len - 1, 0)];
82 }
83 const magnitude = try drawUsize(conjecture, 1, 1 << 16, 2);
84 const value: i64 = @intCast(magnitude);
85 if (try conjecture.drawBoolean()) return value;
86 if (value == 1) return -2;
87 return -value;
88 }
89
90 fn drawCmpPredicate(conjecture: *hypothesis.ConjectureData) !CmpPredicate {
91 return @fromBackingInt(@intCast(try drawUsize(conjecture, 0, @typeInfo(CmpPredicate).@"enum".field_names.len - 1, 0)));
92 }
93
94 fn createBin(
95 ctx: *ir.Context,
96 loc: ir.Location,
97 kind: BinOpKind,
98 lhs: *ir.Value,
99 rhs: *ir.Value,
100 ) !*ir.Operation {
101 return switch (kind) {
102 .add => (try ArithDialect.AddOp.create(ctx, loc, lhs, rhs)).op,
103 .sub => (try ArithDialect.SubOp.create(ctx, loc, lhs, rhs)).op,
104 .mul => (try ArithDialect.MulOp.create(ctx, loc, lhs, rhs)).op,
105 .max => (try ArithDialect.MaxOp.create(ctx, loc, lhs, rhs)).op,
106 .min => (try ArithDialect.MinOp.create(ctx, loc, lhs, rhs)).op,
107 .band => (try ArithDialect.AndOp.create(ctx, loc, lhs, rhs)).op,
108 .bor => (try ArithDialect.OrOp.create(ctx, loc, lhs, rhs)).op,
109 .bxor => (try ArithDialect.XorOp.create(ctx, loc, lhs, rhs)).op,
110 };
111 }
112
113 fn createShift(
114 ctx: *ir.Context,
115 loc: ir.Location,
116 kind: ShiftOpKind,
117 value: *ir.Value,
118 count: *ir.Value,
119 ) !*ir.Operation {
120 return switch (kind) {
121 .shl => (try ArithDialect.ShlOp.create(ctx, loc, value, count)).op,
122 .shr => (try ArithDialect.ShrOp.create(ctx, loc, value, count)).op,
123 .ushr => (try ArithDialect.UshrOp.create(ctx, loc, value, count)).op,
124 };
125 }
126
127 fn createDivRem(
128 ctx: *ir.Context,
129 loc: ir.Location,
130 kind: DivRemOpKind,
131 lhs: *ir.Value,
132 rhs: *ir.Value,
133 ) !*ir.Operation {
134 return switch (kind) {
135 .div => (try ArithDialect.DivOp.create(ctx, loc, lhs, rhs)).op,
136 .rem => (try ArithDialect.RemOp.create(ctx, loc, lhs, rhs)).op,
137 };
138 }
139
140 fn createCmp(
141 ctx: *ir.Context,
142 loc: ir.Location,
143 predicate: CmpPredicate,
144 lhs: *ir.Value,
145 rhs: *ir.Value,
146 ) !*ir.Operation {
147 return (try ArithDialect.CmpOp.create(ctx, loc, predicate, lhs, rhs)).op;
148 }
149
150 fn createSelect(
151 ctx: *ir.Context,
152 loc: ir.Location,
153 condition: *ir.Value,
154 true_value: *ir.Value,
155 false_value: *ir.Value,
156 ) !*ir.Operation {
157 return (try ArithDialect.SelectOp.create(ctx, loc, condition, true_value, false_value)).op;
158 }
159
160 fn createUnary(
161 ctx: *ir.Context,
162 loc: ir.Location,
163 kind: UnaryOpKind,
164 operand: *ir.Value,
165 ) !*ir.Operation {
166 return switch (kind) {
167 .neg => (try ArithDialect.NegOp.create(ctx, loc, operand)).op,
168 .abs => (try ArithDialect.AbsOp.create(ctx, loc, operand)).op,
169 .bnot => (try ArithDialect.NotOp.create(ctx, loc, operand)).op,
170 };
171 }
172
173 fn createCallHelper(
174 ctx: *ir.Context,
175 body: *ir.Block,
176 loc: ir.Location,
177 i64_type: ir.Type,
178 ) !void {
179 const helper = try FuncDialect.FuncOp.create(ctx, loc, helper_name, &.{ i64_type, i64_type, i64_type, i64_type }, &.{i64_type});
180 try body.addOperation(helper.op);
181 const entry = helper.getEntryBlock();
182
183 const lhs = try ArithDialect.AddOp.create(ctx, loc, helper.getArgument(0), helper.getArgument(1));
184 try entry.addOperation(lhs.op);
185 const rhs = try ArithDialect.XorOp.create(ctx, loc, helper.getArgument(2), helper.getArgument(3));
186 try entry.addOperation(rhs.op);
187 const three = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 3);
188 try entry.addOperation(three.op);
189 const scaled = try ArithDialect.MulOp.create(ctx, loc, lhs.getResult(), three.getResult());
190 try entry.addOperation(scaled.op);
191 const result = try ArithDialect.SubOp.create(ctx, loc, scaled.getResult(), rhs.getResult());
192 try entry.addOperation(result.op);
193 const ret = try FuncDialect.ReturnOp.create(ctx, loc, &.{result.getResult()});
194 try entry.addOperation(ret.op);
195 }
196
197 fn createProductHelpers(
198 ctx: *ir.Context,
199 body: *ir.Block,
200 loc: ir.Location,
201 i64_type: ir.Type,
202 ) !void {
203 const bool_type = try ArithDialect.getScalarType(ctx, .bool);
204 const pair_types = [_]ir.Type{ i64_type, i64_type };
205 const pair =
206 try FuncDialect.FuncOp.create(ctx, loc, pair_helper_name, &pair_types, &pair_types);
207 try body.addOperation(pair.op);
208 const pair_entry = pair.getEntryBlock();
209 const pair_lhs = pair.getArgument(0);
210 const pair_rhs = pair.getArgument(1);
211 const difference = try ArithDialect.SubOp.create(ctx, loc, pair_lhs, pair_rhs);
212 try pair_entry.addOperation(difference.op);
213 const mixed = try ArithDialect.XorOp.create(ctx, loc, pair_lhs, pair_rhs);
214 try pair_entry.addOperation(mixed.op);
215 const pair_values = [_]*ir.Value{ difference.getResult(), mixed.getResult() };
216 try pair_entry.addOperation((try FuncDialect.ReturnOp.create(ctx, loc, &pair_values)).op);
217
218 const triple_types = [_]ir.Type{ i64_type, i64_type, bool_type };
219 const triple =
220 try FuncDialect.FuncOp.create(ctx, loc, triple_helper_name, &pair_types, &triple_types);
221 try body.addOperation(triple.op);
222 const triple_entry = triple.getEntryBlock();
223 const triple_lhs = triple.getArgument(0);
224 const triple_rhs = triple.getArgument(1);
225 const sum = try ArithDialect.AddOp.create(ctx, loc, triple_lhs, triple_rhs);
226 try triple_entry.addOperation(sum.op);
227 const below = try ArithDialect.CmpOp.create(ctx, loc, .lt, triple_lhs, triple_rhs);
228 try triple_entry.addOperation(below.op);
229 const triple_values = [_]*ir.Value{ triple_rhs, sum.getResult(), below.getResult() };
230 try triple_entry.addOperation((try FuncDialect.ReturnOp.create(ctx, loc, &triple_values)).op);
231 }
232
233 fn createCall(
234 ctx: *ir.Context,
235 loc: ir.Location,
236 args: []const *ir.Value,
237 i64_type: ir.Type,
238 ) !*ir.Operation {
239 return (try FuncDialect.CallOp.create(ctx, loc, helper_name, args, &.{i64_type})).op;
240 }
241
242 fn createProductCall(
243 ctx: *ir.Context,
244 loc: ir.Location,
245 i64_type: ir.Type,
246 result_count: usize,
247 lhs: *ir.Value,
248 rhs: *ir.Value,
249 ) !*ir.Operation {
250 std.debug.assert(result_count >= 2);
251 std.debug.assert(result_count <= 3);
252 const bool_type = try ArithDialect.getScalarType(ctx, .bool);
253 const types = [_]ir.Type{ i64_type, i64_type, bool_type };
254 const name = if (result_count == 2) pair_helper_name else triple_helper_name;
255 const results = types[0..result_count];
256 return (try FuncDialect.CallOp.create(ctx, loc, name, &.{ lhs, rhs }, results)).op;
257 }
258
259 fn createWhile(
260 ctx: *ir.Context,
261 entry: *ir.Block,
262 loc: ir.Location,
263 i64_type: ir.Type,
264 initial_count: *ir.Value,
265 initial_acc: *ir.Value,
266 ) !*ir.Operation {
267 const while_op = try ScfDialect.WhileOp.create(ctx, loc, &.{ initial_count, initial_acc }, &.{ i64_type, i64_type });
268 try entry.addOperation(while_op.op);
269
270 const before = while_op.getBeforeBlock();
271 const before_count = before.arguments.items[0];
272 const before_acc = before.arguments.items[1];
273 const zero = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 0);
274 try before.addOperation(zero.op);
275 const keep_going = try ArithDialect.CmpOp.create(ctx, loc, .gt, before_count, zero.getResult());
276 try before.addOperation(keep_going.op);
277 const condition = try ScfDialect.ConditionOp.create(ctx, loc, keep_going.getResult(), &.{ before_count, before_acc });
278 try before.addOperation(condition.op);
279
280 const after = while_op.getAfterBlock();
281 const after_count = after.arguments.items[0];
282 const after_acc = after.arguments.items[1];
283 const one = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 1);
284 try after.addOperation(one.op);
285 const next_count = try ArithDialect.SubOp.create(ctx, loc, after_count, one.getResult());
286 try after.addOperation(next_count.op);
287 const next_acc = try ArithDialect.AddOp.create(ctx, loc, after_acc, after_count);
288 try after.addOperation(next_acc.op);
289 const yield = try ScfDialect.YieldOp.create(ctx, loc, &.{ next_count.getResult(), next_acc.getResult() });
290 try after.addOperation(yield.op);
291
292 return while_op.op;
293 }
294
295 fn createIf(
296 ctx: *ir.Context,
297 entry: *ir.Block,
298 loc: ir.Location,
299 i64_type: ir.Type,
300 condition: *ir.Value,
301 true_value: *ir.Value,
302 false_value: *ir.Value,
303 then_bias_value: i64,
304 else_bias_value: i64,
305 ) !*ir.Operation {
306 const if_op = try ScfDialect.IfOp.create(ctx, loc, condition, &.{i64_type});
307 try entry.addOperation(if_op.op);
308
309 const then_block = if_op.getThenBlock();
310 const then_bias = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, then_bias_value);
311 try then_block.addOperation(then_bias.op);
312 const then_result = try ArithDialect.AddOp.create(ctx, loc, true_value, then_bias.getResult());
313 try then_block.addOperation(then_result.op);
314 const then_yield = try ScfDialect.YieldOp.create(ctx, loc, &.{then_result.getResult()});
315 try then_block.addOperation(then_yield.op);
316
317 const else_block = if_op.getElseBlock() orelse return error.InvalidOperand;
318 const else_bias = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, else_bias_value);
319 try else_block.addOperation(else_bias.op);
320 const else_result = try ArithDialect.SubOp.create(ctx, loc, false_value, else_bias.getResult());
321 try else_block.addOperation(else_result.op);
322 const else_yield = try ScfDialect.YieldOp.create(ctx, loc, &.{else_result.getResult()});
323 try else_block.addOperation(else_yield.op);
324
325 return if_op.op;
326 }
327
328 fn runDifferential(conjecture: *hypothesis.ConjectureData, property_allocator: std.mem.Allocator) !void {
329 var ctx = try ir.Context.init(property_allocator, ir.Context.Limits.testing);
330 defer ctx.deinit(property_allocator);
331 try choir.dialects.registerAllDialects(&ctx);
332
333 const i64_type = try ArithDialect.getScalarType(&ctx, .i64);
334 const loc = ir.Location.getUnknown();
335
336 const num_args = try drawUsize(conjecture, 0, max_args, 0);
337 const result_count = try drawUsize(conjecture, 1, max_results, 1);
338 var i64_types: [@max(max_args, max_results)]ir.Type = undefined;
339 @memset(&i64_types, i64_type);
340
341 const module = try BuiltinDialect.ModuleOp.create(&ctx, loc);
342 const body = module.getBodyBlock();
343 try createCallHelper(&ctx, body, loc, i64_type);
344 try createProductHelpers(&ctx, body, loc, i64_type);
345 const inputs = i64_types[0..num_args];
346 const outputs = i64_types[0..result_count];
347 const func = try FuncDialect.FuncOp.create(&ctx, loc, function_name, inputs, outputs);
348 try body.addOperation(func.op);
349 const entry = func.getEntryBlock();
350
351 var pool: std.ArrayListUnmanaged(*ir.Value) = .empty;
352 defer pool.deinit(property_allocator);
353
354 var bool_pool: std.ArrayListUnmanaged(*ir.Value) = .empty;
355 defer bool_pool.deinit(property_allocator);
356
357 var arg_values: [max_args]i64 = undefined;
358 for (0..num_args) |i| {
359 arg_values[i] = try drawValue(conjecture);
360 try pool.append(property_allocator, func.getArgument(i));
361 }
362
363 const seed = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, try drawValue(conjecture));
364 try entry.addOperation(seed.op);
365 try pool.append(property_allocator, seed.op.getResult(0).?);
366
367 const true_const = try ArithDialect.ConstantOp.createBool(&ctx, loc, true);
368 try entry.addOperation(true_const.op);
369 try bool_pool.append(property_allocator, true_const.op.getResult(0).?);
370
371 const false_const = try ArithDialect.ConstantOp.createBool(&ctx, loc, false);
372 try entry.addOperation(false_const.op);
373 try bool_pool.append(property_allocator, false_const.op.getResult(0).?);
374
375 const num_ops = try drawUsize(conjecture, 1, max_ops, 4);
376 var op_index: usize = 0;
377 while (op_index < num_ops) : (op_index += 1) {
378 const make_const = (try drawUsize(conjecture, 0, 3, 0)) == 0;
379 if (make_const) {
380 const constant = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, try drawValue(conjecture));
381 try entry.addOperation(constant.op);
382 try pool.append(property_allocator, constant.op.getResult(0).?);
383 } else {
384 const shape = try drawUsize(conjecture, 0, 10, 10);
385 if (shape == 0) {
386 const kind: UnaryOpKind = @fromBackingInt(@intCast(try drawUsize(conjecture, 0, @typeInfo(UnaryOpKind).@"enum".field_names.len - 1, 0)));
387 const operand = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
388 const op = try createUnary(&ctx, loc, kind, operand);
389 try entry.addOperation(op);
390 try pool.append(property_allocator, op.getResult(0).?);
391 } else if (shape == 1) {
392 const value = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
393 const count_const = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, try drawShiftCount(conjecture));
394 try entry.addOperation(count_const.op);
395 const count = count_const.op.getResult(0).?;
396 try pool.append(property_allocator, count);
397 const kind: ShiftOpKind = @fromBackingInt(@intCast(try drawUsize(conjecture, 0, @typeInfo(ShiftOpKind).@"enum".field_names.len - 1, 0)));
398 const op = try createShift(&ctx, loc, kind, value, count);
399 try entry.addOperation(op);
400 try pool.append(property_allocator, op.getResult(0).?);
401 } else if (shape == 2) {
402 const lhs = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
403 const rhs_const = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, try drawDivisor(conjecture));
404 try entry.addOperation(rhs_const.op);
405 const rhs = rhs_const.op.getResult(0).?;
406 try pool.append(property_allocator, rhs);
407 const kind: DivRemOpKind = @fromBackingInt(@intCast(try drawUsize(conjecture, 0, @typeInfo(DivRemOpKind).@"enum".field_names.len - 1, 0)));
408 const op = try createDivRem(&ctx, loc, kind, lhs, rhs);
409 try entry.addOperation(op);
410 try pool.append(property_allocator, op.getResult(0).?);
411 } else if (shape == 3) {
412 const lhs = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
413 const rhs = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
414 const op = try createCmp(&ctx, loc, try drawCmpPredicate(conjecture), lhs, rhs);
415 try entry.addOperation(op);
416 try bool_pool.append(property_allocator, op.getResult(0).?);
417 } else if (shape == 4) {
418 const condition = bool_pool.items[try drawUsize(conjecture, 0, bool_pool.items.len - 1, 0)];
419 const true_value = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
420 const false_value = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
421 const op = try createSelect(&ctx, loc, condition, true_value, false_value);
422 try entry.addOperation(op);
423 try pool.append(property_allocator, op.getResult(0).?);
424 } else if (shape == 5) {
425 var call_args: [helper_arg_count]*ir.Value = undefined;
426 for (&call_args) |*arg| {
427 arg.* = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
428 }
429 const op = try createCall(&ctx, loc, call_args[0..], i64_type);
430 try entry.addOperation(op);
431 try pool.append(property_allocator, op.getResult(0).?);
432 } else if (shape == 6) {
433 const count_const = try ArithDialect.ConstantOp.createInt(&ctx, loc, i64_type, try drawLoopCount(conjecture));
434 try entry.addOperation(count_const.op);
435 const initial_acc = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
436 const op = try createWhile(&ctx, entry, loc, i64_type, count_const.getResult(), initial_acc);
437 try pool.append(property_allocator, op.getResult(0).?);
438 try pool.append(property_allocator, op.getResult(1).?);
439 } else if (shape == 7) {
440 const condition = bool_pool.items[try drawUsize(conjecture, 0, bool_pool.items.len - 1, 0)];
441 const true_value = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
442 const false_value = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
443 const op = try createIf(
444 &ctx,
445 entry,
446 loc,
447 i64_type,
448 condition,
449 true_value,
450 false_value,
451 try drawValue(conjecture),
452 try drawValue(conjecture),
453 );
454 try pool.append(property_allocator, op.getResult(0).?);
455 } else if (shape == 8 or shape == 9) {
456 const lhs = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
457 const rhs = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
458 const count: usize = if (shape == 8) 2 else 3;
459 const op = try createProductCall(&ctx, loc, i64_type, count, lhs, rhs);
460 try entry.addOperation(op);
461 try pool.append(property_allocator, op.getResult(0).?);
462 try pool.append(property_allocator, op.getResult(1).?);
463 if (count == 3) try bool_pool.append(property_allocator, op.getResult(2).?);
464 } else {
465 const kind: BinOpKind = @fromBackingInt(@intCast(try drawUsize(conjecture, 0, @typeInfo(BinOpKind).@"enum".field_names.len - 1, 0)));
466 const lhs = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
467 const rhs = pool.items[try drawUsize(conjecture, 0, pool.items.len - 1, 0)];
468 const op = try createBin(&ctx, loc, kind, lhs, rhs);
469 try entry.addOperation(op);
470 try pool.append(property_allocator, op.getResult(0).?);
471 }
472 }
473 }
474
475 var ret_values: [max_results]*ir.Value = undefined;
476 for (ret_values[0..result_count], 0..) |*ret_value, index| {
477 ret_value.* = pool.items[(pool.items.len - 1) -| index];
478 }
479 const ret = try FuncDialect.ReturnOp.create(&ctx, loc, ret_values[0..result_count]);
480 try entry.addOperation(ret.op);
481
482 const args = arg_values[0..num_args];
483 try expectJitMatchesEvaluator(&ctx, property_allocator, module.op, func.op, args, result_count);
484 }
485
486 fn expectJitMatchesEvaluator(
487 ctx: *ir.Context,
488 allocator: std.mem.Allocator,
489 module: *ir.Operation,
490 func: *ir.Operation,
491 args: []const i64,
492 result_count: usize,
493 ) !void {
494 std.debug.assert(args.len <= max_args);
495 std.debug.assert(result_count >= 1);
496 std.debug.assert(result_count <= max_results);
497 var arg_attrs: [max_args]ir.Attribute = undefined;
498 for (args, arg_attrs[0..args.len]) |arg, *attr| attr.* = try ctx.getI64Attr(arg);
499
500 var evaluator = Evaluator.init(allocator, ctx);
501 defer evaluator.deinit();
502 try evaluator.setRootOperation(module);
503 const expected_attr = try evaluator.evaluateFunctionOp(func, arg_attrs[0..args.len]);
504 var expected: [max_results]i64 = undefined;
505 try evaluatedResults(expected_attr, expected[0..result_count]);
506
507 var runtime = x86_64_backend.jit.JitRuntime.init(allocator, .testing);
508 defer runtime.deinit();
509 const compiled = try runtime.compile(module);
510 var actual: [max_results]i64 = undefined;
511 try nativeResults(&runtime, compiled, args, actual[0..result_count]);
512
513 try std.testing.expectEqualSlices(i64, expected[0..result_count], actual[0..result_count]);
514 }
515
516 fn evaluatedResults(attr: ir.Attribute, values: []i64) !void {
517 if (values.len == 1) {
518 values[0] = ArithDialect.getIntValue(attr) orelse return error.EvalResultNotInteger;
519 return;
520 }
521 const array = attr.cast(ir.Attribute.ArrayAttr) orelse return error.EvalResultNotProduct;
522 const elements = array.getValues();
523 if (elements.len != values.len) return error.EvalResultArityMismatch;
524 for (elements, values) |element, *value| {
525 value.* = ArithDialect.getIntValue(element) orelse return error.EvalResultNotInteger;
526 }
527 }
528
529 fn nativeResults(
530 runtime: *const x86_64_backend.jit.JitRuntime,
531 compiled: x86_64_backend.jit.ModuleHandle,
532 args: []const i64,
533 values: []i64,
534 ) !void {
535 std.debug.assert(args.len <= max_args);
536 std.debug.assert(values.len <= max_results);
537 var arguments: [max_args]CallValue = undefined;
538 for (args, arguments[0..args.len]) |arg, *argument| argument.* = .{ .i64 = arg };
539 var results: [max_results]CallValue = undefined;
540 try runtime.call(compiled, function_name, arguments[0..args.len], results[0..values.len]);
541 for (results[0..values.len], values) |result, *value| value.* = result.i64;
542 }
543
544 pub const DifferentialProperty = struct {
545 pub fn property(conjecture: *hypothesis.ConjectureData, property_allocator: std.mem.Allocator) !void {
546 if (comptime has_jit) {
547 try runDifferential(conjecture, property_allocator);
548 } else {
549 return error.SkipZigTest;
550 }
551 }
552 };
553
554 test "property: x64 jit matches evaluator on random integer functions and products" {
555 if (comptime !has_jit) return error.SkipZigTest;
556 try hypothesis.checkNamed(DifferentialProperty, "choir-x64-differential", settings());
557 }
558
559 const max_data_tables = 4;
560 const max_data_bytes = 64;
561 const data_alignments = [_]usize{ 1, 2, 4, 8, 16, 64, 4096 };
562 const data_symbol_attrs = choir.backends.machine_code.data_symbol_attr_names;
563
564 const DataTable = struct {
565 name: []const u8,
566 bytes: []const u8,
567 alignment: usize,
568 offset: usize,
569 };
570
571 /// Compiles functions that address random data tables, then checks each table's alignment and
572 /// bytes, and that tables share an address exactly when they share a name.
573 fn runDataSymbols(
574 conjecture: *hypothesis.ConjectureData,
575 property_allocator: std.mem.Allocator,
576 ) !void {
577 var ctx = try ir.Context.init(property_allocator, ir.Context.Limits.testing);
578 defer ctx.deinit(property_allocator);
579 try choir.dialects.registerAllDialects(&ctx);
580 const loc = ir.Location.getUnknown();
581 const module = try BuiltinDialect.ModuleOp.create(&ctx, loc);
582
583 const count = try drawUsize(conjecture, 1, max_data_tables, 1);
584 var tables: [max_data_tables]DataTable = undefined;
585 var names: [max_data_tables][16]u8 = undefined;
586 var bytes: [max_data_tables][max_data_bytes]u8 = undefined;
587 for (tables[0..count], 0..) |*table, index| {
588 if (index != 0 and try conjecture.drawBoolean()) {
589 table.* = tables[try drawUsize(conjecture, 0, index - 1, 0)];
590 } else {
591 const drawn = try conjecture.drawBytes(1, max_data_bytes);
592 @memcpy(bytes[index][0..drawn.len], drawn);
593 const last_alignment = data_alignments.len - 1;
594 const alignment = data_alignments[try drawUsize(conjecture, 0, last_alignment, 0)];
595 table.* = .{
596 .name = try std.fmt.bufPrint(&names[index], "table_{d}", .{index}),
597 .bytes = bytes[index][0..drawn.len],
598 .alignment = alignment,
599 .offset = 0,
600 };
601 }
602 table.offset = try drawUsize(conjecture, 0, table.bytes.len - 1, 0);
603 try addDataFunctions(&ctx, module.getBodyBlock(), loc, index, table.*);
604 }
605
606 var runtime = x86_64_backend.jit.JitRuntime.init(property_allocator, .testing);
607 defer runtime.deinit();
608 const compiled = try runtime.compile(module.op);
609 var bases: [max_data_tables]usize = undefined;
610 for (tables[0..count], 0..) |table, index| {
611 const base = try callDataFunction(&runtime, compiled, "data", index) - table.offset;
612 try std.testing.expect(std.mem.isAligned(base, table.alignment));
613 const placed: [*]const u8 = @ptrFromInt(base);
614 try std.testing.expectEqualSlices(u8, table.bytes, placed[0..table.bytes.len]);
615 const delta = try callDataFunction(&runtime, compiled, "delta", index);
616 try std.testing.expectEqual(table.offset, delta);
617 for (tables[0..index], bases[0..index]) |earlier, earlier_base| {
618 const same_name = std.mem.eql(u8, earlier.name, table.name);
619 try std.testing.expectEqual(same_name, earlier_base == base);
620 }
621 bases[index] = base;
622 }
623 }
624
625 /// Adds `data_{index}`, which returns the table's address plus its offset, and `delta_{index}`,
626 /// which subtracts the address from that sum.
627 fn addDataFunctions(
628 ctx: *ir.Context,
629 body: *ir.Block,
630 loc: ir.Location,
631 index: usize,
632 table: DataTable,
633 ) !void {
634 std.debug.assert(index < max_data_tables);
635 std.debug.assert(table.offset < table.bytes.len);
636 const i64_type = try ArithDialect.getScalarType(ctx, .i64);
637 for ([_][]const u8{ "data", "delta" }) |prefix| {
638 var name: [16]u8 = undefined;
639 const symbol = try std.fmt.bufPrint(&name, "{s}_{d}", .{ prefix, index });
640 const func = try FuncDialect.FuncOp.create(ctx, loc, symbol, &.{}, &.{i64_type});
641 try body.addOperation(func.op);
642 const entry = func.getEntryBlock();
643 const constant = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, 7);
644 try entry.addOperation(constant.op);
645 try constant.op.setAttr(data_symbol_attrs.name, try ctx.getStringAttr(table.name));
646 try constant.op.setAttr(data_symbol_attrs.bytes, try ctx.getStringAttr(table.bytes));
647 const alignment = try ctx.getI64Attr(@intCast(table.alignment));
648 try constant.op.setAttr(data_symbol_attrs.alignment, alignment);
649 const address = constant.getResult();
650 const offset_value: i64 = @intCast(table.offset);
651 const offset = try ArithDialect.ConstantOp.createInt(ctx, loc, i64_type, offset_value);
652 try entry.addOperation(offset.op);
653 const sum = try ArithDialect.AddOp.create(ctx, loc, address, offset.getResult());
654 try entry.addOperation(sum.op);
655 var result = sum.getResult();
656 if (std.mem.eql(u8, prefix, "delta")) {
657 const difference = try ArithDialect.SubOp.create(ctx, loc, result, address);
658 try entry.addOperation(difference.op);
659 result = difference.getResult();
660 }
661 const ret = try FuncDialect.ReturnOp.create(ctx, loc, &.{result});
662 try entry.addOperation(ret.op);
663 }
664 }
665
666 fn callDataFunction(
667 runtime: *const x86_64_backend.jit.JitRuntime,
668 compiled: x86_64_backend.jit.ModuleHandle,
669 prefix: []const u8,
670 index: usize,
671 ) !usize {
672 std.debug.assert(index < max_data_tables);
673 var name: [16]u8 = undefined;
674 const symbol = try std.fmt.bufPrint(&name, "{s}_{d}", .{ prefix, index });
675 const Nullary = *const fn () callconv(.c) i64;
676 return @intCast((try runtime.getFunction(compiled, symbol, Nullary))());
677 }
678
679 pub const DataSymbolProperty = struct {
680 pub fn property(
681 conjecture: *hypothesis.ConjectureData,
682 property_allocator: std.mem.Allocator,
683 ) !void {
684 if (comptime has_jit) {
685 try runDataSymbols(conjecture, property_allocator);
686 } else {
687 return error.SkipZigTest;
688 }
689 }
690 };
691
692 test "property: x64 jit places data symbols at their alignment and patches each address" {
693 if (comptime !has_jit) return error.SkipZigTest;
694 try hypothesis.checkNamed(DataSymbolProperty, "choir-x64-data-symbols", settings());
695 }
696
697 const max_typed_parameters = 16;
698 const max_typed_results = 6;
699 const typed_function_name = "typed_fn";
700 const boundary_tags = [_]std.meta.Tag(CallValue){
701 .i8, .i16, .i32, .i64, .u8, .u16, .u32, .u64, .index, .bool, .f32, .f64, .memref,
702 };
703
704 const TypedCall = struct {
705 args: [max_typed_parameters]CallValue = undefined,
706 parameter_count: usize = 0,
707 selected: [max_typed_results]usize = undefined,
708 result_count: usize = 0,
709 splat: ?usize = null,
710
711 fn draw(conjecture: *hypothesis.ConjectureData) !TypedCall {
712 var typed = TypedCall{};
713 typed.parameter_count = try drawUsize(conjecture, 0, max_typed_parameters, 0);
714 for (typed.args[0..typed.parameter_count]) |*arg| {
715 const tag = boundary_tags[try drawUsize(conjecture, 0, boundary_tags.len - 1, 0)];
716 arg.* = try drawBoundaryValue(conjecture, tag);
717 }
718 if (typed.parameter_count == 0) return typed;
719 const last = typed.parameter_count - 1;
720 if (try conjecture.drawBoolean()) {
721 const source = try drawUsize(conjecture, 0, last, 0);
722 if (splatLanes(typed.args[source]) != null) {
723 typed.splat = source;
724 return typed;
725 }
726 }
727 typed.result_count = try drawUsize(conjecture, 0, max_typed_results, 1);
728 for (typed.selected[0..typed.result_count]) |*index| {
729 index.* = try drawUsize(conjecture, 0, last, 0);
730 }
731 return typed;
732 }
733
734 fn parameters(self: *const TypedCall) []const CallValue {
735 return self.args[0..self.parameter_count];
736 }
737
738 fn resultCount(self: *const TypedCall) usize {
739 return if (self.splat == null) self.result_count else 1;
740 }
741
742 fn expected(self: *const TypedCall, index: usize) CallValue {
743 std.debug.assert(index < self.resultCount());
744 const source = self.splat orelse return self.args[self.selected[index]];
745 return splatOf(self.args[source]);
746 }
747 };
748
749 fn drawBoundaryValue(
750 conjecture: *hypothesis.ConjectureData,
751 tag: std.meta.Tag(CallValue),
752 ) !CallValue {
753 const word = try conjecture.drawInteger(0, std.math.maxInt(u64), 0);
754 switch (tag) {
755 .vector => unreachable,
756 .bool => return .{ .bool = (word & 1) == 1 },
757 inline else => |known| {
758 const Payload = @FieldType(CallValue, @tagName(known));
759 const Bits = @Int(.unsigned, @bitSizeOf(Payload));
760 return @unionInit(CallValue, @tagName(known), @bitCast(@as(Bits, @truncate(word))));
761 },
762 }
763 }
764
765 fn splatLanes(value: CallValue) ?u8 {
766 return switch (value) {
767 .f32, .i32, .u32 => 4,
768 .f64, .i64, .u64 => 2,
769 else => null,
770 };
771 }
772
773 fn splatOf(value: CallValue) CallValue {
774 const lanes = splatLanes(value).?;
775 const word: u64 = switch (value) {
776 .f32 => |float| @as(u32, @bitCast(float)),
777 .i32 => |int| @as(u32, @bitCast(int)),
778 .u32 => |int| int,
779 .f64 => |float| @bitCast(float),
780 .i64 => |int| @bitCast(int),
781 .u64 => |int| int,
782 else => unreachable,
783 };
784 var bits: [choir.backends.artifact.VectorType.max_lanes]u64 = @splat(0);
785 @memset(bits[0..lanes], word);
786 const element = value.valueType().scalar;
787 return .{ .vector = .{ .element = element, .lanes = lanes, .bits = bits } };
788 }
789
790 fn scalarKindOf(scalar: choir.backends.artifact.ScalarType) ArithDialect.ScalarTypeKind {
791 return switch (scalar) {
792 inline else => |tag| @field(ArithDialect.ScalarTypeKind, @tagName(tag)),
793 };
794 }
795
796 fn boundaryType(ctx: *ir.Context, value: CallValue) !ir.Type {
797 switch (value.valueType()) {
798 .memref => {
799 const byte = try ArithDialect.getScalarType(ctx, .u8);
800 return choir.dialects.MemrefDialect.getMemrefTypeDynamic(ctx, byte, .host);
801 },
802 .scalar => |scalar| return ArithDialect.getScalarType(ctx, scalarKindOf(scalar)),
803 .vector => |vector| {
804 const element = choir.dialects.arith.scalarTypeName(scalarKindOf(vector.element));
805 return (try ArithDialect.getVecType(ctx, vector.lanes, element)).?;
806 },
807 }
808 }
809
810 fn addTypedFunction(ctx: *ir.Context, typed: *const TypedCall) !BuiltinDialect.ModuleOp {
811 const loc = ir.Location.getUnknown();
812 const module = try BuiltinDialect.ModuleOp.create(ctx, loc);
813 var parameter_types: [max_typed_parameters]ir.Type = undefined;
814 for (typed.parameters(), parameter_types[0..typed.parameter_count]) |arg, *parameter_type| {
815 parameter_type.* = try boundaryType(ctx, arg);
816 }
817 const result_count = typed.resultCount();
818 var result_types: [max_typed_results]ir.Type = undefined;
819 for (result_types[0..result_count], 0..) |*result_type, index| {
820 result_type.* = try boundaryType(ctx, typed.expected(index));
821 }
822 const inputs = parameter_types[0..typed.parameter_count];
823 const outputs = result_types[0..result_count];
824 const func = try FuncDialect.FuncOp.create(ctx, loc, typed_function_name, inputs, outputs);
825 try module.getBodyBlock().addOperation(func.op);
826 const entry = func.getEntryBlock();
827 var values: [max_typed_results]*ir.Value = undefined;
828 if (typed.splat) |source| {
829 const input = func.getArgument(source);
830 const repeated = try ArithDialect.SplatOp.create(ctx, loc, input, outputs[0]);
831 try entry.addOperation(repeated.op);
832 values[0] = repeated.getResult();
833 } else {
834 for (typed.selected[0..result_count], values[0..result_count]) |index, *value| {
835 value.* = func.getArgument(index);
836 }
837 }
838 const ret = try FuncDialect.ReturnOp.create(ctx, loc, values[0..result_count]);
839 try entry.addOperation(ret.op);
840 return module;
841 }
842
843 fn loadTypedArtifact(
844 allocator: std.mem.Allocator,
845 runtime: *x86_64_backend.jit.JitRuntime,
846 func: *ir.Operation,
847 ) !x86_64_backend.jit.ModuleHandle {
848 const serialization = choir.backends.artifact.serialization;
849 const object = x86_64_backend.object;
850 var built = try object.compileFunctionToArtifact(allocator, func, typed_function_name);
851 defer built.deinit();
852 const bytes = try serialization.serialize(allocator, &built);
853 defer allocator.free(bytes);
854 var restored = try serialization.deserialize(allocator, bytes);
855 defer restored.deinit();
856 return runtime.loadMachineCodeArtifact(&restored);
857 }
858
859 fn expectTypedCall(
860 runtime: *const x86_64_backend.jit.JitRuntime,
861 handle: x86_64_backend.jit.ModuleHandle,
862 typed: *const TypedCall,
863 ) !void {
864 const count = typed.resultCount();
865 var results: [max_typed_results + 1]CallValue = undefined;
866 try runtime.call(handle, typed_function_name, typed.parameters(), results[0..count]);
867 for (results[0..count], 0..) |result, index| {
868 try expectSameBits(typed.expected(index), result);
869 }
870
871 const mismatch = error.SignatureMismatch;
872 const extra_slot = results[0 .. count + 1];
873 const extra = runtime.call(handle, typed_function_name, typed.parameters(), extra_slot);
874 try std.testing.expectError(mismatch, extra);
875 if (typed.parameter_count == 0) return;
876 var args = typed.args;
877 const last = typed.parameter_count - 1;
878 args[last] = if (args[last] == .i64) .{ .u64 = 0 } else .{ .i64 = 0 };
879 const retyped_args = args[0..typed.parameter_count];
880 const retyped = runtime.call(handle, typed_function_name, retyped_args, results[0..count]);
881 try std.testing.expectError(mismatch, retyped);
882 }
883
884 fn expectSameBits(expected: CallValue, actual: CallValue) !void {
885 try std.testing.expectEqual(std.meta.activeTag(expected), std.meta.activeTag(actual));
886 switch (expected) {
887 .bool => |flag| try std.testing.expectEqual(flag, actual.bool),
888 .vector => |vector| {
889 try std.testing.expectEqual(vector.element, actual.vector.element);
890 try std.testing.expectEqual(vector.lanes, actual.vector.lanes);
891 try std.testing.expectEqualSlices(u64, &vector.bits, &actual.vector.bits);
892 },
893 inline else => |payload, tag| {
894 const Bits = @Int(.unsigned, @bitSizeOf(@TypeOf(payload)));
895 const found = @field(actual, @tagName(tag));
896 try std.testing.expectEqual(@as(Bits, @bitCast(payload)), @as(Bits, @bitCast(found)));
897 },
898 }
899 }
900
901 fn runTypedCalls(
902 conjecture: *hypothesis.ConjectureData,
903 property_allocator: std.mem.Allocator,
904 ) !void {
905 var ctx = try ir.Context.init(property_allocator, ir.Context.Limits.testing);
906 defer ctx.deinit(property_allocator);
907 try choir.dialects.registerAllDialects(&ctx);
908 const typed = try TypedCall.draw(conjecture);
909 const module = try addTypedFunction(&ctx, &typed);
910 const func = ir.inspection.functionDefinitionByName(module.op, typed_function_name).?;
911
912 var runtime = x86_64_backend.jit.JitRuntime.init(property_allocator, .testing);
913 defer runtime.deinit();
914 const compiled = try runtime.compile(module.op);
915 const loaded = try loadTypedArtifact(property_allocator, &runtime, func);
916 const recorded = try runtime.functionSignature(compiled, typed_function_name);
917 const restored = try runtime.functionSignature(loaded, typed_function_name);
918 try std.testing.expect(recorded.eql(&restored));
919 for ([_]x86_64_backend.jit.ModuleHandle{ compiled, loaded }) |handle| {
920 try expectTypedCall(&runtime, handle, &typed);
921 }
922 }
923
924 pub const TypedCallProperty = struct {
925 pub fn property(
926 conjecture: *hypothesis.ConjectureData,
927 property_allocator: std.mem.Allocator,
928 ) !void {
929 if (comptime has_jit) {
930 try runTypedCalls(conjecture, property_allocator);
931 } else {
932 return error.SkipZigTest;
933 }
934 }
935 };
936
937 test "property: x64 checked calls return drawn boundary values through both load paths" {
938 if (comptime !has_jit) return error.SkipZigTest;
939 try hypothesis.checkNamed(TypedCallProperty, "choir-x64-typed-calls", settings());
940 }