lib/choir/src/properties/dce.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

 1 const std = @import("std");
 2 const hypothesis = @import("hypothesis");
 3 const choir = @import("choir");
 4 
 5 fn settings() hypothesis.Settings {
 6     var value = hypothesis.Settings.quick()
 7         .withSeed(0xdce0_c1a1_2026_0710)
 8         .withDatabase("zig-out/hypothesis-failures/choir-dead-chain-dce");
 9     value.max_examples = 100;
10     value.target_examples = 100;
11     return value;
12 }
13 
14 fn drawUsize(conjecture: *hypothesis.ConjectureData, min: usize, max: usize, shrink_towards: usize) !usize {
15     return @intCast(try conjecture.drawInteger(@intCast(min), @intCast(max), @intCast(shrink_towards)));
16 }
17 
18 pub const DeadChainProperty = struct {
19     pub fn property(conjecture: *hypothesis.ConjectureData, allocator: std.mem.Allocator) !void {
20         var ctx = try choir.Context.init(allocator, choir.Context.Limits.testing);
21         defer ctx.deinit(allocator);
22         try ctx.allowUnregistered();
23         try choir.ir.dialects.loadDialectSpec(&ctx, choir.dialects.arith.spec);
24         _ = try ctx.registerOperation("test.dce_sink", .{});
25 
26         const block_count = try drawUsize(conjecture, 1, 16, 1);
27         const ops_per_block = try drawUsize(conjecture, 1, 64, 1);
28         const op_count = block_count * ops_per_block;
29         const live_count = try drawUsize(conjecture, 0, op_count, 0);
30         const dead_count = op_count - live_count;
31         try conjecture.target(op_count, "operation count");
32         try conjecture.target(dead_count, "dead chain length");
33         try conjecture.target(block_count, "block count");
34 
35         const arithmetic = choir.dialects.ArithDialect;
36         const value_type = try arithmetic.getScalarType(&ctx, .i64);
37         const chain = try allocator.alloc(*choir.Operation, op_count);
38         defer allocator.free(chain);
39 
40         var body = choir.ir.context.initRegion(&ctx);
41         defer body.deinit();
42         var previous_value: ?*choir.Value = null;
43         for (0..block_count) |block_index| {
44             const block = try body.addBlock();
45             for (0..ops_per_block) |op_index| {
46                 const index = block_index * ops_per_block + op_index;
47                 const op = if (previous_value) |value|
48                     (try arithmetic.AddOp.create(&ctx, .unknown, value, value)).op
49                 else
50                     (try arithmetic.ConstantOp.createInt(&ctx, .unknown, value_type, 1)).op;
51                 try block.addOperation(op);
52                 chain[index] = op;
53                 previous_value = op.getResult(0).?;
54             }
55         }
56 
57         var sink_state = choir.Operation.State.init("test.dce_sink", .unknown);
58         if (live_count > 0) sink_state.addOperands(&.{chain[live_count - 1].getResult(0).?});
59         const sink = try ctx.createOperation(sink_state);
60         try body.blocks.tail.?.addOperation(sink);
61 
62         var root_state = choir.Operation.State.init("test.dce_root", .unknown);
63         root_state.addRegionBodies(&.{&body});
64         const root = try ctx.createOperation(root_state);
65 
66         var pass_manager = choir.PassManager.init(allocator);
67         defer pass_manager.deinit();
68         try pass_manager.addPass(choir.passes.createDeadCodeEliminationPass());
69         try std.testing.expectEqual(choir.passes.PassResult.success, pass_manager.run(root, &ctx));
70 
71         var observed: usize = 0;
72         var blocks = root.getRegion(0).?.getBlocks();
73         while (blocks.next()) |block| {
74             var operations = block.getOperations();
75             while (operations.next()) |op| {
76                 if (observed < live_count) {
77                     try std.testing.expect(op == chain[observed]);
78                 } else {
79                     try std.testing.expect(op == sink);
80                 }
81                 observed += 1;
82             }
83         }
84         try std.testing.expectEqual(live_count + 1, observed);
85     }
86 };
87 
88 test "property: DCE removes cross-block dead chain suffixes" {
89     try hypothesis.checkNamed(DeadChainProperty, "choir-dead-chain-dce", settings());
90 }