Commit 8ed134243a
Changed files (5)
test
behavior
src/link/SpirV/BinaryModule.zig
@@ -45,11 +45,30 @@ pub fn deinit(self: *BinaryModule, a: Allocator) void {
}
pub fn iterateInstructions(self: BinaryModule) Instruction.Iterator {
- return Instruction.Iterator.init(self.instructions);
+ return Instruction.Iterator.init(self.instructions, 0);
}
pub fn iterateInstructionsFrom(self: BinaryModule, offset: usize) Instruction.Iterator {
- return Instruction.Iterator.init(self.instructions[offset..]);
+ return Instruction.Iterator.init(self.instructions, offset);
+}
+
+pub fn instructionAt(self: BinaryModule, offset: usize) Instruction {
+ var it = self.iterateInstructionsFrom(offset);
+ return it.next().?;
+}
+
+pub fn finalize(self: BinaryModule, a: Allocator) ![]Word {
+ const result = try a.alloc(Word, 5 + self.instructions.len);
+ errdefer a.free(result);
+
+ result[0] = spec.magic_number;
+ result[1] = @bitCast(self.version);
+ result[2] = spec.zig_generator_id;
+ result[3] = self.id_bound;
+ result[4] = 0; // Schema
+
+ @memcpy(result[5..], self.instructions);
+ return result;
}
/// Errors that can be raised when the module is not correct.
@@ -85,8 +104,8 @@ pub const Instruction = struct {
index: usize = 0,
offset: usize = 0,
- pub fn init(words: []const Word) Iterator {
- return .{ .words = words };
+ pub fn init(words: []const Word, start_offset: usize) Iterator {
+ return .{ .words = words, .offset = start_offset };
}
pub fn next(self: *Iterator) ?Instruction {
@@ -159,6 +178,11 @@ pub const Parser = struct {
return (@as(u32, @intFromEnum(set)) << 16) | opcode;
}
+ pub fn getInstSpec(self: Parser, opcode: Opcode) ?spec.Instruction {
+ const index = self.opcode_table.get(mapSetAndOpcode(.core, @intFromEnum(opcode))) orelse return null;
+ return InstructionSet.core.instructions()[index];
+ }
+
pub fn parse(self: *Parser, module: []const u32) ParseError!BinaryModule {
if (module[0] != spec.magic_number) {
return error.InvalidMagic;
@@ -195,13 +219,12 @@ pub const Parser = struct {
// We can't really efficiently use non-exhaustive enums here, because we would
// need to manually write out all valid cases. Since we have this map anyway, just
// use that.
- const opcode_num: u16 = @truncate(binary.instructions[offset]);
- const index = self.opcode_table.get(mapSetAndOpcode(.core, opcode_num)) orelse {
- log.err("invalid opcode for core set: {}", .{opcode_num});
+ const opcode: Opcode = @enumFromInt(@as(u16, @truncate(binary.instructions[offset])));
+ const inst_spec = self.getInstSpec(opcode) orelse {
+ log.err("invalid opcode for core set: {}", .{@intFromEnum(opcode)});
return error.InvalidOpcode;
};
- const opcode: Opcode = @enumFromInt(opcode_num);
const operands = binary.instructions[offset..][1..len];
switch (opcode) {
.OpExtInstImport => {
@@ -226,11 +249,10 @@ pub const Parser = struct {
// OpSwitch takes a value as argument, not an OpType... hence we need to populate arith_type_width
// with ALL operations that return an int or float.
- const proper_operands = InstructionSet.core.instructions()[index].operands;
-
- if (proper_operands.len >= 2 and
- proper_operands[0].kind == .IdResultType and
- proper_operands[1].kind == .IdResult)
+ const spec_operands = inst_spec.operands;
+ if (spec_operands.len >= 2 and
+ spec_operands[0].kind == .IdResultType and
+ spec_operands[1].kind == .IdResult)
{
if (operands.len < 2) return error.InvalidOperands;
if (binary.arith_type_width.get(@enumFromInt(operands[0]))) |width| {
@@ -283,6 +305,7 @@ pub const Parser = struct {
if (offset + 1 >= inst.operands.len) return error.InvalidPhysicalFormat;
const set_id: ResultId = @enumFromInt(inst.operands[offset]);
+ try offsets.append(@intCast(offset));
const set = binary.ext_inst_map.get(set_id) orelse {
log.err("invalid instruction set {}", .{@intFromEnum(set_id)});
return error.InvalidId;
@@ -375,8 +398,7 @@ pub const Parser = struct {
}
},
.id => {
- const this_offset = std.math.cast(u16, offset) orelse return error.InvalidPhysicalFormat;
- try offsets.append(this_offset);
+ try offsets.append(@intCast(offset));
offset += 1;
},
else => switch (kind) {
@@ -419,20 +441,16 @@ pub const Parser = struct {
33...64 => 2,
else => unreachable,
};
- const this_offset = std.math.cast(u16, offset) orelse return error.InvalidPhysicalFormat;
- try offsets.append(this_offset);
+ try offsets.append(@intCast(offset));
offset += 1;
},
.PairIdRefLiteralInteger => {
- const this_offset = std.math.cast(u16, offset) orelse return error.InvalidPhysicalFormat;
- try offsets.append(this_offset);
+ try offsets.append(@intCast(offset));
offset += 2;
},
.PairIdRefIdRef => {
- const a = std.math.cast(u16, offset) orelse return error.InvalidPhysicalFormat;
- const b = std.math.cast(u16, offset + 1) orelse return error.InvalidPhysicalFormat;
- try offsets.append(a);
- try offsets.append(b);
+ try offsets.append(@intCast(offset));
+ try offsets.append(@intCast(offset + 1));
offset += 2;
},
else => unreachable,
src/link/SpirV/lower_invocation_globals.zig
@@ -345,23 +345,16 @@ const ModuleBuilder = struct {
function_types: std.ArrayHashMapUnmanaged(FunctionType, ResultId, FunctionType.Context, true) = .{},
/// Maps functions to new information required for creating the module
function_new_info: std.AutoArrayHashMapUnmanaged(ResultId, FunctionNewInfo) = .{},
+ /// Offset of the functions section in the new binary.
+ new_functions_section: ?usize,
fn init(arena: Allocator, binary: BinaryModule, info: ModuleInfo) !ModuleBuilder {
- var section = Section{};
-
- try section.instructions.appendSlice(arena, &.{
- spec.magic_number,
- @bitCast(binary.version),
- spec.zig_generator_id,
- 0, // Filled in in finalize()
- 0, // Schema (reserved)
- });
-
var self = ModuleBuilder{
.arena = arena,
- .section = section,
+ .section = .{},
.id_bound = binary.id_bound,
.entry_point_new_id_base = undefined,
+ .new_functions_section = null,
};
self.entry_point_new_id_base = @intFromEnum(self.allocIds(@intCast(info.entry_points.count())));
return self;
@@ -376,9 +369,12 @@ const ModuleBuilder = struct {
return @enumFromInt(self.id_bound);
}
- fn finalize(self: *ModuleBuilder, a: Allocator) ![]Word {
- self.section.instructions.items[3] = self.id_bound;
- return try a.dupe(Word, self.section.instructions.items);
+ fn finalize(self: *ModuleBuilder, a: Allocator, binary: *BinaryModule) !void {
+ binary.id_bound = self.id_bound;
+ binary.instructions = try a.dupe(Word, self.section.instructions.items);
+ // Nothing is removed in this pass so we don't need to change any of the maps,
+ // just make sure the section is updated.
+ binary.sections.functions = self.new_functions_section orelse binary.instructions.len;
}
/// Process everything from `binary` up to the first function and emit it into the builder.
@@ -386,16 +382,6 @@ const ModuleBuilder = struct {
var it = binary.iterateInstructions();
while (it.next()) |inst| {
switch (inst.opcode) {
- // TODO: We should remove this instruction using something that eliminates unreferenced instructions.
- // For now, this is the only place where the .zig instruction set is being referenced, so its safe
- // to remove it here.
- .OpExtInstImport => {
- const set_id: ResultId = @enumFromInt(inst.operands[0]);
- const set = binary.ext_inst_map.get(set_id).?;
- if (set == .zig) {
- continue;
- }
- },
.OpExtInst => {
const set_id: ResultId = @enumFromInt(inst.operands[2]);
const set_inst = inst.operands[3];
@@ -499,6 +485,7 @@ const ModuleBuilder = struct {
var maybe_current_function: ?ResultId = null;
var it = binary.iterateInstructionsFrom(binary.sections.functions);
+ self.new_functions_section = self.section.instructions.items.len;
while (it.next()) |inst| {
result_id_offsets.items.len = 0;
try parser.parseInstructionResultIds(binary, inst, &result_id_offsets);
@@ -695,20 +682,19 @@ const ModuleBuilder = struct {
}
};
-pub fn run(parser: *BinaryModule.Parser, binary: BinaryModule) ![]Word {
+pub fn run(parser: *BinaryModule.Parser, binary: *BinaryModule) !void {
var arena = std.heap.ArenaAllocator.init(parser.a);
defer arena.deinit();
const a = arena.allocator();
- var info = try ModuleInfo.parse(a, parser, binary);
+ var info = try ModuleInfo.parse(a, parser, binary.*);
try info.resolve(a);
- var builder = try ModuleBuilder.init(a, binary, info);
+ var builder = try ModuleBuilder.init(a, binary.*, info);
try builder.deriveNewFnInfo(info);
- try builder.processPreamble(binary, info);
+ try builder.processPreamble(binary.*, info);
try builder.emitFunctionTypes(info);
- try builder.rewriteFunctions(parser, binary, info);
+ try builder.rewriteFunctions(parser, binary.*, info);
try builder.emitNewEntryPoints(info);
-
- return builder.finalize(parser.a);
+ try builder.finalize(parser.a, binary);
}
src/link/SpirV/prune_unused.zig
@@ -0,0 +1,354 @@
+//! This pass is used to simple pruning of unused things:
+//! - Instructions at global scope
+//! - Functions
+//! Debug info and nonsemantic instructions are not handled;
+//! this pass is mainly intended for cleaning up left over
+//! stuff from codegen and other passes that is generated
+//! but not actually used.
+
+const std = @import("std");
+const Allocator = std.mem.Allocator;
+const assert = std.debug.assert;
+const log = std.log.scoped(.spirv_link);
+
+const BinaryModule = @import("BinaryModule.zig");
+const Section = @import("../../codegen/spirv/Section.zig");
+const spec = @import("../../codegen/spirv/spec.zig");
+const Opcode = spec.Opcode;
+const ResultId = spec.IdResult;
+const Word = spec.Word;
+
+/// Return whether a particular opcode's instruction can be pruned.
+/// These are idempotent instructions at globals scope and instructions
+/// within functions that do not have any side effects.
+/// The opcodes that return true here do not necessarily need to
+/// have an .IdResult. If they don't, then they are regarded
+/// as 'decoration'-style instructions that don't keep their
+/// operands alive, but will be emitted if they are.
+fn canPrune(op: Opcode) bool {
+ // This list should be as worked out as possible, but just
+ // getting common instructions is a good effort/effect ratio.
+ // When adding items to this list, also check whether the
+ // instruction requires any special control flow rules (like
+ // with labels and control flow and stuff) and whether the
+ // instruction has any non-trivial side effects (like OpLoad
+ // with the Volatile memory semantics).
+ return switch (op.class()) {
+ .TypeDeclaration,
+ .Conversion,
+ .Arithmetic,
+ .RelationalAndLogical,
+ .Bit,
+ => true,
+ else => switch (op) {
+ .OpFunction,
+ .OpUndef,
+ .OpString,
+ .OpName,
+ .OpMemberName,
+ // Prune OpConstant* instructions but
+ // retain OpSpecConstant declaration instructions
+ .OpConstantTrue,
+ .OpConstantFalse,
+ .OpConstant,
+ .OpConstantComposite,
+ .OpConstantSampler,
+ .OpConstantNull,
+ .OpSpecConstantOp,
+ // Prune ext inst import instructions, but not
+ // ext inst instructions themselves, because
+ // we don't know if they might have side effects.
+ .OpExtInstImport,
+ => true,
+ else => false,
+ },
+ };
+}
+
+const ModuleInfo = struct {
+ const Fn = struct {
+ /// The index of the first callee in `callee_store`.
+ first_callee: usize,
+ };
+
+ /// Maps function result-id -> Fn information structure.
+ functions: std.AutoArrayHashMapUnmanaged(ResultId, Fn),
+ /// For each function, a list of function result-ids that it calls.
+ callee_store: []const ResultId,
+ /// For each instruction, the offset at which it appears in the source module.
+ result_id_to_code_offset: std.AutoArrayHashMapUnmanaged(ResultId, usize),
+
+ /// Fetch the list of callees per function. Guaranteed to contain only unique IDs.
+ fn callees(self: ModuleInfo, fn_id: ResultId) []const ResultId {
+ const fn_index = self.functions.getIndex(fn_id).?;
+ const values = self.functions.values();
+ const first_callee = values[fn_index].first_callee;
+ if (fn_index == values.len - 1) {
+ return self.callee_store[first_callee..];
+ } else {
+ const next_first_callee = values[fn_index + 1].first_callee;
+ return self.callee_store[first_callee..next_first_callee];
+ }
+ }
+
+ /// Extract the information required to run this pass from the binary.
+ // TODO: Should the contents of this function be merged with that of lower_invocation_globals.zig?
+ // Many of the contents are the same...
+ fn parse(
+ arena: Allocator,
+ parser: *BinaryModule.Parser,
+ binary: BinaryModule,
+ ) !ModuleInfo {
+ var functions = std.AutoArrayHashMap(ResultId, Fn).init(arena);
+ var calls = std.AutoArrayHashMap(ResultId, void).init(arena);
+ var callee_store = std.ArrayList(ResultId).init(arena);
+ var result_id_to_code_offset = std.AutoArrayHashMap(ResultId, usize).init(arena);
+ var maybe_current_function: ?ResultId = null;
+ var it = binary.iterateInstructions();
+ while (it.next()) |inst| {
+ const inst_spec = parser.getInstSpec(inst.opcode).?;
+
+ // Result-id can only be the first or second operand
+ const maybe_result_id: ?ResultId = for (0..2) |i| {
+ if (inst_spec.operands.len > i and inst_spec.operands[i].kind == .IdResult) {
+ break @enumFromInt(inst.operands[i]);
+ }
+ } else null;
+
+ // Only add result-ids of functions and anything outside a function.
+ // Result-ids declared inside functions cannot be reached outside anyway,
+ // and we don't care about the internals of functions anyway.
+ // Note that in the case of OpFunction, `maybe_current_function` is
+ // also `null`, because it is set below.
+ if (maybe_result_id) |result_id| {
+ try result_id_to_code_offset.put(result_id, inst.offset);
+ }
+
+ switch (inst.opcode) {
+ .OpFunction => {
+ if (maybe_current_function) |current_function| {
+ log.err("OpFunction {} does not have an OpFunctionEnd", .{current_function});
+ return error.InvalidPhysicalFormat;
+ }
+
+ maybe_current_function = @enumFromInt(inst.operands[1]);
+ },
+ .OpFunctionCall => {
+ const callee: ResultId = @enumFromInt(inst.operands[2]);
+ try calls.put(callee, {});
+ },
+ .OpFunctionEnd => {
+ const current_function = maybe_current_function orelse {
+ log.err("encountered OpFunctionEnd without corresponding OpFunction", .{});
+ return error.InvalidPhysicalFormat;
+ };
+ const entry = try functions.getOrPut(current_function);
+ if (entry.found_existing) {
+ log.err("Function {} has duplicate definition", .{current_function});
+ return error.DuplicateId;
+ }
+
+ const first_callee = callee_store.items.len;
+ try callee_store.appendSlice(calls.keys());
+
+ entry.value_ptr.* = .{
+ .first_callee = first_callee,
+ };
+ maybe_current_function = null;
+ calls.clearRetainingCapacity();
+ },
+ else => {},
+ }
+ }
+
+ if (maybe_current_function) |current_function| {
+ log.err("OpFunction {} does not have an OpFunctionEnd", .{current_function});
+ return error.InvalidPhysicalFormat;
+ }
+
+ return ModuleInfo{
+ .functions = functions.unmanaged,
+ .callee_store = callee_store.items,
+ .result_id_to_code_offset = result_id_to_code_offset.unmanaged,
+ };
+ }
+};
+
+const AliveMarker = struct {
+ parser: *BinaryModule.Parser,
+ binary: BinaryModule,
+ info: ModuleInfo,
+ result_id_offsets: std.ArrayList(u16),
+ alive: std.DynamicBitSetUnmanaged,
+
+ fn markAlive(self: *AliveMarker, result_id: ResultId) BinaryModule.ParseError!void {
+ const index = self.info.result_id_to_code_offset.getIndex(result_id) orelse {
+ log.err("undefined result-id {}", .{result_id});
+ return error.InvalidId;
+ };
+
+ if (self.alive.isSet(index)) {
+ return;
+ }
+ self.alive.set(index);
+
+ const offset = self.info.result_id_to_code_offset.values()[index];
+ const inst = self.binary.instructionAt(offset);
+
+ if (inst.opcode == .OpFunction) {
+ try self.markFunctionAlive(inst);
+ } else {
+ try self.markInstructionAlive(inst);
+ }
+ }
+
+ fn markFunctionAlive(
+ self: *AliveMarker,
+ func_inst: BinaryModule.Instruction,
+ ) !void {
+ // Go through the instruction and mark the
+ // operands of each instruction alive.
+ var it = self.binary.iterateInstructionsFrom(func_inst.offset);
+ try self.markInstructionAlive(it.next().?);
+ while (it.next()) |inst| {
+ if (inst.opcode == .OpFunctionEnd) {
+ break;
+ }
+
+ if (!canPrune(inst.opcode)) {
+ try self.markInstructionAlive(inst);
+ }
+ }
+ }
+
+ fn markInstructionAlive(
+ self: *AliveMarker,
+ inst: BinaryModule.Instruction,
+ ) !void {
+ const start_offset = self.result_id_offsets.items.len;
+ try self.parser.parseInstructionResultIds(self.binary, inst, &self.result_id_offsets);
+ const end_offset = self.result_id_offsets.items.len;
+
+ // Recursive calls to markInstructionAlive() might change the pointer in self.result_id_offsets,
+ // so we need to iterate it manually.
+ var i = start_offset;
+ while (i < end_offset) : (i += 1) {
+ const offset = self.result_id_offsets.items[i];
+ try self.markAlive(@enumFromInt(inst.operands[offset]));
+ }
+ }
+};
+
+fn removeIdsFromMap(a: Allocator, map: anytype, info: ModuleInfo, alive_marker: AliveMarker) !void {
+ var to_remove = std.ArrayList(ResultId).init(a);
+ var it = map.iterator();
+ while (it.next()) |entry| {
+ const id = entry.key_ptr.*;
+ const index = info.result_id_to_code_offset.getIndex(id).?;
+ if (!alive_marker.alive.isSet(index)) {
+ try to_remove.append(id);
+ }
+ }
+
+ for (to_remove.items) |id| {
+ assert(map.remove(id));
+ }
+}
+
+pub fn run(parser: *BinaryModule.Parser, binary: *BinaryModule) !void {
+ var arena = std.heap.ArenaAllocator.init(parser.a);
+ defer arena.deinit();
+ const a = arena.allocator();
+
+ const info = try ModuleInfo.parse(a, parser, binary.*);
+
+ var alive_marker = AliveMarker{
+ .parser = parser,
+ .binary = binary.*,
+ .info = info,
+ .result_id_offsets = std.ArrayList(u16).init(a),
+ .alive = try std.DynamicBitSetUnmanaged.initEmpty(a, info.result_id_to_code_offset.count()),
+ };
+
+ // Mark initial stuff as slive
+ {
+ var it = binary.iterateInstructions();
+ while (it.next()) |inst| {
+ if (inst.opcode == .OpFunction) {
+ // No need to process further.
+ break;
+ } else if (!canPrune(inst.opcode)) {
+ try alive_marker.markInstructionAlive(inst);
+ }
+ }
+ }
+
+ var section = Section{};
+
+ var new_functions_section: ?usize = null;
+ var it = binary.iterateInstructions();
+ skip: while (it.next()) |inst| {
+ const inst_spec = parser.getInstSpec(inst.opcode).?;
+
+ reemit: {
+ if (!canPrune(inst.opcode)) {
+ break :reemit;
+ }
+
+ // Result-id can only be the first or second operand
+ const result_id: ResultId = for (0..2) |i| {
+ if (inst_spec.operands.len > i and inst_spec.operands[i].kind == .IdResult) {
+ break @enumFromInt(inst.operands[i]);
+ }
+ } else {
+ // Instruction can be pruned but doesn't have a result id.
+ // Check all operands to see if they are alive, and emit it only if so.
+ alive_marker.result_id_offsets.items.len = 0;
+ try parser.parseInstructionResultIds(binary.*, inst, &alive_marker.result_id_offsets);
+ for (alive_marker.result_id_offsets.items) |offset| {
+ const id: ResultId = @enumFromInt(inst.operands[offset]);
+ const index = info.result_id_to_code_offset.getIndex(id).?;
+
+ if (!alive_marker.alive.isSet(index)) {
+ continue :skip;
+ }
+ }
+
+ break :reemit;
+ };
+
+ const index = info.result_id_to_code_offset.getIndex(result_id).?;
+ if (alive_marker.alive.isSet(index)) {
+ break :reemit;
+ }
+
+ if (inst.opcode != .OpFunction) {
+ // Instruction can be pruned and its not alive, so skip it.
+ continue :skip;
+ }
+
+ // We're at the start of a function that can be pruned, so skip everything until
+ // we encounter an OpFunctionEnd.
+ while (it.next()) |body_inst| {
+ if (body_inst.opcode == .OpFunctionEnd)
+ break;
+ }
+
+ continue :skip;
+ }
+
+ if (inst.opcode == .OpFunction and new_functions_section == null) {
+ new_functions_section = section.instructions.items.len;
+ }
+
+ try section.emitRawInstruction(a, inst.opcode, inst.operands);
+ }
+
+ // This pass might have pruned ext inst imports or arith types, update
+ // those maps to main consistency.
+ try removeIdsFromMap(a, &binary.ext_inst_map, info, alive_marker);
+ try removeIdsFromMap(a, &binary.arith_type_width, info, alive_marker);
+
+ binary.instructions = try parser.a.dupe(Word, section.toWords());
+ binary.sections.functions = new_functions_section orelse binary.instructions.len;
+}
src/link/SpirV.zig
@@ -245,26 +245,31 @@ pub fn flushModule(self: *SpirV, arena: Allocator, prog_node: *std.Progress.Node
const module = try spv.finalize(arena, target);
errdefer arena.free(module);
- const new_module = self.lowerInstanceGlobals(arena, module) catch |err| switch (err) {
+ const linked_module = self.linkModule(arena, module) catch |err| switch (err) {
error.OutOfMemory => return error.OutOfMemory,
else => |other| {
- std.debug.print("error while lowering instance globals: {s}\n", .{@errorName(other)});
+ log.err("error while linking: {s}\n", .{@errorName(other)});
return error.FlushFailure;
},
};
- defer arena.free(new_module);
- try self.base.file.?.writeAll(std.mem.sliceAsBytes(new_module));
+ try self.base.file.?.writeAll(std.mem.sliceAsBytes(linked_module));
}
-fn lowerInstanceGlobals(self: *SpirV, a: Allocator, module: []Word) ![]Word {
+fn linkModule(self: *SpirV, a: Allocator, module: []Word) ![]Word {
_ = self;
+ const lower_invocation_globals = @import("SpirV/lower_invocation_globals.zig");
+ const prune_unused = @import("SpirV/prune_unused.zig");
+
var parser = try BinaryModule.Parser.init(a);
defer parser.deinit();
- const binary = try parser.parse(module);
- const lower_invocation_globals = @import("SpirV/lower_invocation_globals.zig");
- return try lower_invocation_globals.run(&parser, binary);
+ var binary = try parser.parse(module);
+
+ try lower_invocation_globals.run(&parser, &binary);
+ try prune_unused.run(&parser, &binary);
+
+ return binary.finalize(a);
}
fn writeCapabilities(spv: *SpvModule, target: std.Target) !void {
test/behavior/align.zig
@@ -18,6 +18,7 @@ test "global variable alignment" {
test "large alignment of local constant" {
if (builtin.zig_backend == .stage2_aarch64) return error.SkipZigTest;
if (builtin.zig_backend == .stage2_arm) return error.SkipZigTest;
+ if (builtin.zig_backend == .stage2_spirv64) return error.SkipZigTest; // flaky
const x: f32 align(128) = 12.34;
try std.testing.expect(@intFromPtr(&x) % 128 == 0);