1const std = @import("std");
2const Allocator = std.mem.Allocator;
3const log = std.log.scoped(.loongarch_decode_tree);
4
5const OpcodeDesc = @import("OpcodeDesc.zig");
6const Opcode = OpcodeDesc.Opcode;
7
8pub const Node = struct {
9 mask: u32,
10 /// `cases` when mask is non-zero. `instruction` when mask is zero.
11 next: union {
12 /// catch-all case
13 cases: []const Case,
14 instruction: *const Opcode,
15 },
16};
17
18pub const Case = struct {
19 catch_all: bool,
20 variant: u32, // valid only when catch-all is not set
21 child: *const Node,
22};
23
24pub fn populate(arena: Allocator, desc: *const OpcodeDesc) !*Node {
25 var ops: std.ArrayList(*const Opcode) = .empty;
26 defer ops.deinit(arena);
27 try ops.ensureUnusedCapacity(arena, desc.opcode.items.len);
28 for (desc.opcode.items) |*op| ops.appendAssumeCapacity(op);
29
30 return try populateAdvanced(arena, ops.items, 0);
31}
32
33pub fn populateAdvanced(arena: Allocator, ops: []const *const Opcode, checked_mask: u32) !*Node {
34 if (ops.len == 1) {
35 const node = try arena.create(Node);
36 node.* = .{ .mask = 0, .next = .{ .instruction = ops[0] } };
37 return node;
38 }
39
40 // look for unchecked common static bits
41 common_static_bits: {
42 var common_mask: u32 = ~checked_mask;
43 for (ops) |op| {
44 for (op.format.slots) |slot| {
45 if (slot.tag == .none) break;
46 common_mask &= ~slot.mask();
47 }
48 }
49 if (common_mask == 0) break :common_static_bits;
50
51 // there are some common bits to check
52 var cases: std.ArrayList(Case) = .empty;
53 defer cases.deinit(arena);
54 var known_variants: std.ArrayList(u32) = .empty;
55 defer known_variants.deinit(arena);
56
57 for (ops) |op| {
58 const variant = op.word & common_mask;
59 if (std.mem.indexOfScalar(u32, known_variants.items, variant) == null) {
60 // new variant
61 try known_variants.append(arena, variant);
62
63 var variant_ops: std.ArrayList(*const Opcode) = .empty;
64 defer variant_ops.deinit(arena);
65 variant_ops.ensureTotalCapacity(arena, ops.len / 2) catch {};
66 for (ops) |op1|
67 if ((op1.word & common_mask) == variant) try variant_ops.append(arena, op1);
68
69 const child = try populateAdvanced(arena, variant_ops.items, checked_mask | common_mask);
70 try cases.append(arena, .{
71 .catch_all = false,
72 .variant = variant,
73 .child = child,
74 });
75 }
76 }
77
78 const node = try arena.create(Node);
79 node.* = .{
80 .mask = common_mask,
81 .next = .{ .cases = try cases.toOwnedSlice(arena) },
82 };
83 return node;
84 }
85
86 // look for bits that are static for some opcodes but dynamic for one opcode, e.g. csrxchg
87 half_static_bits: {
88 // these bits are static in at least one opcode
89 var half_static_mask: u32 = 0;
90 for (ops) |op| {
91 var op_static_mask: u32 = 0xffffffff;
92 for (op.format.slots) |slot| {
93 if (slot.tag == .none) break;
94 op_static_mask &= ~slot.mask();
95 }
96 half_static_mask |= op_static_mask;
97 }
98 half_static_mask &= ~checked_mask;
99 if (half_static_mask == 0) break :half_static_bits;
100
101 var cases: std.ArrayList(Case) = .empty;
102 defer cases.deinit(arena);
103 var maybe_dynamic_op: ?*const Opcode = null;
104
105 for (ops) |op| {
106 const variant = op.word & half_static_mask;
107
108 var op_static_mask = ~checked_mask;
109 for (op.format.slots) |slot| {
110 if (slot.tag == .none) break;
111 op_static_mask &= ~slot.mask();
112 }
113 if (op_static_mask != half_static_mask) {
114 if (maybe_dynamic_op) |dynamic_op| {
115 log.err("unsupported: {s}, {s}", .{ dynamic_op.name, op.name });
116 return error.Unsupported;
117 } else {
118 maybe_dynamic_op = op;
119 continue;
120 }
121 }
122
123 const child = try populateAdvanced(arena, &.{op}, checked_mask | half_static_mask);
124 try cases.append(arena, .{
125 .catch_all = false,
126 .variant = variant,
127 .child = child,
128 });
129 }
130
131 if (maybe_dynamic_op) |dynamic_op| {
132 const child = try populateAdvanced(arena, &.{dynamic_op}, checked_mask | half_static_mask);
133 try cases.append(arena, .{
134 .catch_all = true,
135 .variant = 0,
136 .child = child,
137 });
138 } else unreachable;
139
140 const node = try arena.create(Node);
141 node.* = .{
142 .mask = half_static_mask,
143 .next = .{ .cases = try cases.toOwnedSlice(arena) },
144 };
145 return node;
146 }
147
148 return error.Unsupported;
149}