1const std = @import("std");
2const BinaryModule = @import("BinaryModule.zig");
3const spec = @import("../../codegen/spirv/spec.zig");
4const Opcode = spec.Opcode;
5const ResultId = spec.Id;
6const Word = spec.Word;
7
8pub fn run(parser: *BinaryModule.Parser, binary: *BinaryModule) !void {
9 const gpa = parser.gpa;
10
11 // map result-id → index in id_offsets for preamble instructions and function headers
12 var id_to_index: std.AutoHashMapUnmanaged(ResultId, u32) = .empty;
13 defer id_to_index.deinit(gpa);
14
15 // for each indexed instruction, its offset in the binary
16 var code_offsets: std.ArrayList(usize) = .empty;
17 defer code_offsets.deinit(gpa);
18
19 var it = binary.iterateInstructions();
20 while (it.next()) |inst| {
21 const inst_spec = parser.getInstSpec(inst.opcode) orelse continue;
22 const result_id = getResultId(inst, inst_spec) orelse continue;
23
24 // only index preamble instructions and function headers
25 if (inst.offset < binary.functions_start or inst.opcode == .OpFunction) {
26 const index: u32 = @intCast(code_offsets.items.len);
27 try id_to_index.put(gpa, result_id, index);
28 try code_offsets.append(gpa, inst.offset);
29 }
30 }
31
32 var alive: std.bit_set.Dynamic = try .initEmpty(gpa, code_offsets.items.len);
33 defer alive.deinit(gpa);
34
35 var id_offset_buf: std.ArrayList(u16) = .empty;
36 defer id_offset_buf.deinit(gpa);
37
38 // Mark non-prunable preamble instructions alive
39 // OpExtInst in the preamble is metadata (e.g. Zig error info) that references
40 // functions. skip it here so it doesn't root dead functions alive.
41 // These instructions are handled as prunable during the rewrite phase.
42 it = binary.iterateInstructions();
43 while (it.next()) |inst| {
44 if (inst.offset >= binary.functions_start) break;
45 if (canPrune(inst.opcode) or inst.opcode == .OpExtInst) continue;
46 try markAlive(
47 parser,
48 binary.*,
49 inst,
50 &alive,
51 &id_to_index,
52 &code_offsets,
53 &id_offset_buf,
54 );
55 }
56
57 // mark functions with LinkageAttributes Export alive
58 it = binary.iterateInstructions();
59 while (it.next()) |inst| {
60 if (inst.offset >= binary.functions_start) break;
61 if (inst.opcode == .OpDecorate and inst.operands.len >= 2 and
62 inst.operands[1] == @backingInt(spec.Decoration.linkage_attributes))
63 {
64 // Last word after the string is the linkage type; Export = 0.
65 if (inst.operands[inst.operands.len - 1] == @backingInt(spec.LinkageType.@"export")) {
66 const target: ResultId = @fromBackingInt(@intCast(inst.operands[0]));
67 if (id_to_index.get(target)) |index| {
68 alive.set(index);
69 }
70 }
71 }
72 }
73
74 // mark alive functions' contents alive
75 it = binary.iterateInstructionsFrom(binary.functions_start);
76 while (it.next()) |inst| {
77 if (inst.opcode == .OpFunction) {
78 const inst_spec = parser.getInstSpec(inst.opcode) orelse continue;
79 const result_id = getResultId(inst, inst_spec) orelse continue;
80 const index = id_to_index.get(result_id) orelse continue;
81 if (!alive.isSet(index)) {
82 // skip dead function
83 while (it.next()) |inner| {
84 if (inner.opcode == .OpFunctionEnd) break;
85 }
86 continue;
87 }
88
89 // mark the function's type operands alive
90 try markAlive(parser, binary.*, inst, &alive, &id_to_index, &code_offsets, &id_offset_buf);
91 continue;
92 }
93
94 // mark operands of alive function contents
95 try markAlive(parser, binary.*, inst, &alive, &id_to_index, &code_offsets, &id_offset_buf);
96 }
97
98 // rewrite
99 var new_words: std.ArrayList(Word) = .empty;
100 defer new_words.deinit(gpa);
101 try new_words.ensureTotalCapacity(gpa, binary.instructions.len);
102
103 var new_functions_start: ?usize = null;
104
105 it = binary.iterateInstructions();
106 while (it.next()) |inst| {
107 if (inst.offset >= binary.functions_start and inst.opcode == .OpFunction) {
108 const inst_spec = parser.getInstSpec(inst.opcode) orelse continue;
109 const result_id = getResultId(inst, inst_spec) orelse continue;
110 const index = id_to_index.get(result_id) orelse continue;
111 if (!alive.isSet(index)) {
112 while (it.next()) |inner| {
113 if (inner.opcode == .OpFunctionEnd) break;
114 }
115 continue;
116 }
117 }
118
119 const is_prunable = canPrune(inst.opcode) or
120 (inst.opcode == .OpExtInst and inst.offset < binary.functions_start);
121 if (is_prunable) {
122 const inst_spec = parser.getInstSpec(inst.opcode) orelse {
123 appendInst(&new_words, binary, inst, &new_functions_start);
124 continue;
125 };
126
127 if (getResultId(inst, inst_spec)) |result_id| {
128 const index = id_to_index.get(result_id) orelse {
129 appendInst(&new_words, binary, inst, &new_functions_start);
130 continue;
131 };
132 if (!alive.isSet(index)) continue;
133 } else {
134 // annotation-style: emit only if the target id is alive
135 if (inst.operands.len > 0) {
136 const target: ResultId = @fromBackingInt(@intCast(inst.operands[0]));
137 if (id_to_index.get(target)) |idx| {
138 if (!alive.isSet(idx)) continue;
139 } else continue;
140 }
141 }
142 }
143
144 appendInst(&new_words, binary, inst, &new_functions_start);
145 }
146
147 {
148 var to_remove: std.ArrayList(ResultId) = .empty;
149 defer to_remove.deinit(gpa);
150
151 var ext_it = binary.ext_inst_map.iterator();
152 while (ext_it.next()) |entry| {
153 if (id_to_index.get(entry.key_ptr.*)) |index| {
154 if (!alive.isSet(index)) try to_remove.append(gpa, entry.key_ptr.*);
155 }
156 }
157 for (to_remove.items) |id| _ = binary.ext_inst_map.remove(id);
158
159 to_remove.items.len = 0;
160 var arith_it = binary.arith_type_width.iterator();
161 while (arith_it.next()) |entry| {
162 if (id_to_index.get(entry.key_ptr.*)) |index| {
163 if (!alive.isSet(index)) try to_remove.append(gpa, entry.key_ptr.*);
164 }
165 }
166 for (to_remove.items) |id| _ = binary.arith_type_width.remove(id);
167 }
168
169 binary.instructions = try gpa.dupe(Word, new_words.items);
170 binary.functions_start = new_functions_start orelse new_words.items.len;
171}
172
173fn appendInst(
174 new_words: *std.ArrayList(Word),
175 binary: *const BinaryModule,
176 inst: BinaryModule.Instruction,
177 new_functions_start: *?usize,
178) void {
179 if (new_functions_start.* == null and inst.offset >= binary.functions_start) {
180 new_functions_start.* = new_words.items.len;
181 }
182 const len = @as(usize, binary.instructions[inst.offset] >> 16);
183 new_words.appendSliceAssumeCapacity(binary.instructions[inst.offset..][0..len]);
184}
185
186fn markAlive(
187 parser: *BinaryModule.Parser,
188 binary: BinaryModule,
189 inst: BinaryModule.Instruction,
190 alive: *std.bit_set.Dynamic,
191 id_to_index: *const std.AutoHashMapUnmanaged(ResultId, u32),
192 code_offsets: *const std.ArrayList(usize),
193 id_offset_buf: *std.ArrayList(u16),
194) !void {
195 const start = id_offset_buf.items.len;
196 try parser.parseInstructionResultIds(binary, inst, id_offset_buf);
197 const end = id_offset_buf.items.len;
198
199 var i = start;
200 while (i < end) : (i += 1) {
201 const off = id_offset_buf.items[i];
202 const id: ResultId = @fromBackingInt(@intCast(inst.operands[off]));
203 const index = id_to_index.get(id) orelse continue;
204 if (alive.isSet(index)) continue;
205 alive.set(index);
206
207 const offset = code_offsets.items[index];
208 const ref_inst = BinaryModule.Instruction{
209 .opcode = @fromBackingInt(@intCast(binary.instructions[offset] & 0xFFFF)),
210 .offset = offset,
211 .operands = blk: {
212 const l = binary.instructions[offset] >> 16;
213 break :blk binary.instructions[offset..][1..l];
214 },
215 };
216
217 if (ref_inst.opcode == .OpFunction) {
218 var fn_it = binary.iterateInstructionsFrom(ref_inst.offset);
219 _ = fn_it.next();
220 while (fn_it.next()) |fn_inst| {
221 if (fn_inst.opcode == .OpFunctionEnd) break;
222 try markAlive(parser, binary, fn_inst, alive, id_to_index, code_offsets, id_offset_buf);
223 }
224 try markAlive(parser, binary, ref_inst, alive, id_to_index, code_offsets, id_offset_buf);
225 } else {
226 try markAlive(parser, binary, ref_inst, alive, id_to_index, code_offsets, id_offset_buf);
227 }
228 }
229}
230
231fn getResultId(inst: BinaryModule.Instruction, inst_spec: spec.Instruction) ?ResultId {
232 for (0..@min(2, inst_spec.operands.len)) |i| {
233 if (inst_spec.operands[i].kind == .id_result) {
234 if (i < inst.operands.len) return @fromBackingInt(@intCast(inst.operands[i]));
235 }
236 }
237 return null;
238}
239
240fn canPrune(op: Opcode) bool {
241 return switch (op.class()) {
242 .type_declaration,
243 .constant_creation,
244 .annotation,
245 => true,
246 else => switch (op) {
247 .OpFunction,
248 .OpUndef,
249 .OpString,
250 .OpName,
251 .OpMemberName,
252 .OpVariable,
253 => true,
254 else => false,
255 },
256 };
257}