From 8fb392dbb443688cdf62e965935e17a4ae4a4267 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Mon, 29 Jun 2020 21:58:34 -0400 Subject: stage2: implement liveness analysis --- src-self-hosted/Module.zig | 6 ++++++ 1 file changed, 6 insertions(+) (limited to 'src-self-hosted/Module.zig') diff --git a/src-self-hosted/Module.zig b/src-self-hosted/Module.zig index f4d65ab7c0..4c83076cad 100644 --- a/src-self-hosted/Module.zig +++ b/src-self-hosted/Module.zig @@ -18,6 +18,7 @@ const Inst = ir.Inst; const Body = ir.Body; const ast = std.zig.ast; const trace = @import("tracy.zig").trace; +const liveness = @import("liveness.zig"); /// General-purpose allocator. allocator: *Allocator, @@ -986,6 +987,11 @@ pub fn performAllTheWork(self: *Module) error{OutOfMemory}!void { .sema_failure, .dependency_failure => continue, .success => {}, } + // Here we tack on additional allocations to the Decl's arena. The allocations are + // lifetime annotations in the ZIR. + var decl_arena = decl.typed_value.most_recent.arena.?.promote(self.allocator); + defer decl.typed_value.most_recent.arena.?.* = decl_arena.state; + try liveness.analyze(self.allocator, &decl_arena.allocator, payload.func.analysis.success); } assert(decl.typed_value.most_recent.typed_value.ty.hasCodeGenBits()); -- cgit v1.2.3 From 8be8ebd698aac447db2babf95def4725d9ddd05f Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Mon, 6 Jul 2020 06:10:44 +0000 Subject: stage2: skeleton codegen for x64 ADD also rework Module to take advantage of the new hash map implementation. --- src-self-hosted/Module.zig | 389 ++++++++++++++++++++----------------------- src-self-hosted/codegen.zig | 251 ++++++++++++++++++++-------- src-self-hosted/ir.zig | 21 ++- src-self-hosted/link.zig | 6 +- src-self-hosted/liveness.zig | 4 +- src-self-hosted/main.zig | 2 +- 6 files changed, 392 insertions(+), 281 deletions(-) (limited to 'src-self-hosted/Module.zig') diff --git a/src-self-hosted/Module.zig b/src-self-hosted/Module.zig index 4c83076cad..4240a1c6c8 100644 --- a/src-self-hosted/Module.zig +++ b/src-self-hosted/Module.zig @@ -20,8 +20,8 @@ const ast = std.zig.ast; const trace = @import("tracy.zig").trace; const liveness = @import("liveness.zig"); -/// General-purpose allocator. -allocator: *Allocator, +/// General-purpose allocator. Used for both temporary and long-term storage. +gpa: *Allocator, /// Pointer to externally managed resource. root_pkg: *Package, /// Module owns this resource. @@ -33,7 +33,7 @@ bin_file_path: []const u8, /// It's rare for a decl to be exported, so we save memory by having a sparse map of /// Decl pointers to details about them being exported. /// The Export memory is owned by the `export_owners` table; the slice itself is owned by this table. -decl_exports: std.AutoHashMap(*Decl, []*Export), +decl_exports: std.AutoHashMapUnmanaged(*Decl, []*Export) = .{}, /// We track which export is associated with the given symbol name for quick /// detection of symbol collisions. symbol_exports: std.StringHashMap(*Export), @@ -41,9 +41,9 @@ symbol_exports: std.StringHashMap(*Export), /// is modified. Note that the key of this table is not the Decl being exported, but the Decl that /// is performing the export of another Decl. /// This table owns the Export memory. -export_owners: std.AutoHashMap(*Decl, []*Export), +export_owners: std.AutoHashMapUnmanaged(*Decl, []*Export) = .{}, /// Maps fully qualified namespaced names to the Decl struct for them. -decl_table: DeclTable, +decl_table: std.HashMapUnmanaged(Scope.NameHash, *Decl, Scope.name_hash_hash, Scope.name_hash_eql, false) = .{}, optimize_mode: std.builtin.Mode, link_error_flags: link.ElfFile.ErrorFlags = .{}, @@ -55,13 +55,13 @@ work_queue: std.fifo.LinearFifo(WorkItem, .Dynamic), /// The ErrorMsg memory is owned by the decl, using Module's allocator. /// Note that a Decl can succeed but the Fn it represents can fail. In this case, /// a Decl can have a failed_decls entry but have analysis status of success. -failed_decls: std.AutoHashMap(*Decl, *ErrorMsg), +failed_decls: std.AutoHashMapUnmanaged(*Decl, *ErrorMsg) = .{}, /// Using a map here for consistency with the other fields here. /// The ErrorMsg memory is owned by the `Scope`, using Module's allocator. -failed_files: std.AutoHashMap(*Scope, *ErrorMsg), +failed_files: std.AutoHashMapUnmanaged(*Scope, *ErrorMsg) = .{}, /// Using a map here for consistency with the other fields here. /// The ErrorMsg memory is owned by the `Export`, using Module's allocator. -failed_exports: std.AutoHashMap(*Export, *ErrorMsg), +failed_exports: std.AutoHashMapUnmanaged(*Export, *ErrorMsg) = .{}, /// Incrementing integer used to compare against the corresponding Decl /// field to determine whether a Decl's status applies to an ongoing update, or a @@ -76,8 +76,6 @@ deletion_set: std.ArrayListUnmanaged(*Decl) = .{}, keep_source_files_loaded: bool, -const DeclTable = std.HashMap(Scope.NameHash, *Decl, Scope.name_hash_hash, Scope.name_hash_eql, false); - const WorkItem = union(enum) { /// Write the machine code for a Decl to the output file. codegen_decl: *Decl, @@ -176,19 +174,23 @@ pub const Decl = struct { /// The shallow set of other decls whose typed_value could possibly change if this Decl's /// typed_value is modified. - dependants: ArrayListUnmanaged(*Decl) = ArrayListUnmanaged(*Decl){}, + dependants: DepsTable = .{}, /// The shallow set of other decls whose typed_value changing indicates that this Decl's /// typed_value may need to be regenerated. - dependencies: ArrayListUnmanaged(*Decl) = ArrayListUnmanaged(*Decl){}, + dependencies: DepsTable = .{}, + + /// The reason this is not `std.AutoHashMapUnmanaged` is a workaround for + /// stage1 compiler giving me: `error: struct 'Module.Decl' depends on itself` + pub const DepsTable = std.HashMapUnmanaged(*Decl, void, std.hash_map.getAutoHashFn(*Decl), std.hash_map.getAutoEqlFn(*Decl), false); - pub fn destroy(self: *Decl, allocator: *Allocator) void { - allocator.free(mem.spanZ(self.name)); + pub fn destroy(self: *Decl, gpa: *Allocator) void { + gpa.free(mem.spanZ(self.name)); if (self.typedValueManaged()) |tvm| { - tvm.deinit(allocator); + tvm.deinit(gpa); } - self.dependants.deinit(allocator); - self.dependencies.deinit(allocator); - allocator.destroy(self); + self.dependants.deinit(gpa); + self.dependencies.deinit(gpa); + gpa.destroy(self); } pub fn src(self: Decl) usize { @@ -247,23 +249,11 @@ pub const Decl = struct { } fn removeDependant(self: *Decl, other: *Decl) void { - for (self.dependants.items) |item, i| { - if (item == other) { - _ = self.dependants.swapRemove(i); - return; - } - } - unreachable; + self.dependants.removeAssertDiscard(other); } fn removeDependency(self: *Decl, other: *Decl) void { - for (self.dependencies.items) |item, i| { - if (item == other) { - _ = self.dependencies.swapRemove(i); - return; - } - } - unreachable; + self.dependencies.removeAssertDiscard(other); } }; @@ -390,10 +380,10 @@ pub const Scope = struct { } } - pub fn unload(base: *Scope, allocator: *Allocator) void { + pub fn unload(base: *Scope, gpa: *Allocator) void { switch (base.tag) { - .file => return @fieldParentPtr(File, "base", base).unload(allocator), - .zir_module => return @fieldParentPtr(ZIRModule, "base", base).unload(allocator), + .file => return @fieldParentPtr(File, "base", base).unload(gpa), + .zir_module => return @fieldParentPtr(ZIRModule, "base", base).unload(gpa), .block => unreachable, .gen_zir => unreachable, .decl => unreachable, @@ -422,17 +412,17 @@ pub const Scope = struct { } /// Asserts the scope is a File or ZIRModule and deinitializes it, then deallocates it. - pub fn destroy(base: *Scope, allocator: *Allocator) void { + pub fn destroy(base: *Scope, gpa: *Allocator) void { switch (base.tag) { .file => { const scope_file = @fieldParentPtr(File, "base", base); - scope_file.deinit(allocator); - allocator.destroy(scope_file); + scope_file.deinit(gpa); + gpa.destroy(scope_file); }, .zir_module => { const scope_zir_module = @fieldParentPtr(ZIRModule, "base", base); - scope_zir_module.deinit(allocator); - allocator.destroy(scope_zir_module); + scope_zir_module.deinit(gpa); + gpa.destroy(scope_zir_module); }, .block => unreachable, .gen_zir => unreachable, @@ -483,7 +473,7 @@ pub const Scope = struct { /// Direct children of the file. decls: ArrayListUnmanaged(*Decl), - pub fn unload(self: *File, allocator: *Allocator) void { + pub fn unload(self: *File, gpa: *Allocator) void { switch (self.status) { .never_loaded, .unloaded_parse_failure, @@ -497,16 +487,16 @@ pub const Scope = struct { } switch (self.source) { .bytes => |bytes| { - allocator.free(bytes); + gpa.free(bytes); self.source = .{ .unloaded = {} }; }, .unloaded => {}, } } - pub fn deinit(self: *File, allocator: *Allocator) void { - self.decls.deinit(allocator); - self.unload(allocator); + pub fn deinit(self: *File, gpa: *Allocator) void { + self.decls.deinit(gpa); + self.unload(gpa); self.* = undefined; } @@ -528,7 +518,7 @@ pub const Scope = struct { switch (self.source) { .unloaded => { const source = try module.root_pkg.root_src_dir.readFileAllocOptions( - module.allocator, + module.gpa, self.sub_file_path, std.math.maxInt(u32), 1, @@ -576,7 +566,7 @@ pub const Scope = struct { /// not this one. decls: ArrayListUnmanaged(*Decl), - pub fn unload(self: *ZIRModule, allocator: *Allocator) void { + pub fn unload(self: *ZIRModule, gpa: *Allocator) void { switch (self.status) { .never_loaded, .unloaded_parse_failure, @@ -585,30 +575,30 @@ pub const Scope = struct { => {}, .loaded_success => { - self.contents.module.deinit(allocator); - allocator.destroy(self.contents.module); + self.contents.module.deinit(gpa); + gpa.destroy(self.contents.module); self.contents = .{ .not_available = {} }; self.status = .unloaded_success; }, .loaded_sema_failure => { - self.contents.module.deinit(allocator); - allocator.destroy(self.contents.module); + self.contents.module.deinit(gpa); + gpa.destroy(self.contents.module); self.contents = .{ .not_available = {} }; self.status = .unloaded_sema_failure; }, } switch (self.source) { .bytes => |bytes| { - allocator.free(bytes); + gpa.free(bytes); self.source = .{ .unloaded = {} }; }, .unloaded => {}, } } - pub fn deinit(self: *ZIRModule, allocator: *Allocator) void { - self.decls.deinit(allocator); - self.unload(allocator); + pub fn deinit(self: *ZIRModule, gpa: *Allocator) void { + self.decls.deinit(gpa); + self.unload(gpa); self.* = undefined; } @@ -630,7 +620,7 @@ pub const Scope = struct { switch (self.source) { .unloaded => { const source = try module.root_pkg.root_src_dir.readFileAllocOptions( - module.allocator, + module.gpa, self.sub_file_path, std.math.maxInt(u32), 1, @@ -701,8 +691,8 @@ pub const AllErrors = struct { msg: []const u8, }; - pub fn deinit(self: *AllErrors, allocator: *Allocator) void { - self.arena.promote(allocator).deinit(); + pub fn deinit(self: *AllErrors, gpa: *Allocator) void { + self.arena.promote(gpa).deinit(); } fn add( @@ -772,20 +762,14 @@ pub fn init(gpa: *Allocator, options: InitOptions) !Module { }; return Module{ - .allocator = gpa, + .gpa = gpa, .root_pkg = options.root_pkg, .root_scope = root_scope, .bin_file_dir = bin_file_dir, .bin_file_path = options.bin_file_path, .bin_file = bin_file, .optimize_mode = options.optimize_mode, - .decl_table = DeclTable.init(gpa), - .decl_exports = std.AutoHashMap(*Decl, []*Export).init(gpa), .symbol_exports = std.StringHashMap(*Export).init(gpa), - .export_owners = std.AutoHashMap(*Decl, []*Export).init(gpa), - .failed_decls = std.AutoHashMap(*Decl, *ErrorMsg).init(gpa), - .failed_files = std.AutoHashMap(*Scope, *ErrorMsg).init(gpa), - .failed_exports = std.AutoHashMap(*Export, *ErrorMsg).init(gpa), .work_queue = std.fifo.LinearFifo(WorkItem, .Dynamic).init(gpa), .keep_source_files_loaded = options.keep_source_files_loaded, }; @@ -793,51 +777,51 @@ pub fn init(gpa: *Allocator, options: InitOptions) !Module { pub fn deinit(self: *Module) void { self.bin_file.deinit(); - const allocator = self.allocator; - self.deletion_set.deinit(allocator); + const gpa = self.gpa; + self.deletion_set.deinit(gpa); self.work_queue.deinit(); for (self.decl_table.items()) |entry| { - entry.value.destroy(allocator); + entry.value.destroy(gpa); } - self.decl_table.deinit(); + self.decl_table.deinit(gpa); for (self.failed_decls.items()) |entry| { - entry.value.destroy(allocator); + entry.value.destroy(gpa); } - self.failed_decls.deinit(); + self.failed_decls.deinit(gpa); for (self.failed_files.items()) |entry| { - entry.value.destroy(allocator); + entry.value.destroy(gpa); } - self.failed_files.deinit(); + self.failed_files.deinit(gpa); for (self.failed_exports.items()) |entry| { - entry.value.destroy(allocator); + entry.value.destroy(gpa); } - self.failed_exports.deinit(); + self.failed_exports.deinit(gpa); for (self.decl_exports.items()) |entry| { const export_list = entry.value; - allocator.free(export_list); + gpa.free(export_list); } - self.decl_exports.deinit(); + self.decl_exports.deinit(gpa); for (self.export_owners.items()) |entry| { - freeExportList(allocator, entry.value); + freeExportList(gpa, entry.value); } - self.export_owners.deinit(); + self.export_owners.deinit(gpa); self.symbol_exports.deinit(); - self.root_scope.destroy(allocator); + self.root_scope.destroy(gpa); self.* = undefined; } -fn freeExportList(allocator: *Allocator, export_list: []*Export) void { +fn freeExportList(gpa: *Allocator, export_list: []*Export) void { for (export_list) |exp| { - allocator.destroy(exp); + gpa.destroy(exp); } - allocator.free(export_list); + gpa.free(export_list); } pub fn target(self: Module) std.Target { @@ -855,7 +839,7 @@ pub fn update(self: *Module) !void { // Until then we simulate a full cache miss. Source files could have been loaded for any reason; // to force a refresh we unload now. if (self.root_scope.cast(Scope.File)) |zig_file| { - zig_file.unload(self.allocator); + zig_file.unload(self.gpa); self.analyzeRootSrcFile(zig_file) catch |err| switch (err) { error.AnalysisFail => { assert(self.totalErrorCount() != 0); @@ -863,7 +847,7 @@ pub fn update(self: *Module) !void { else => |e| return e, }; } else if (self.root_scope.cast(Scope.ZIRModule)) |zir_module| { - zir_module.unload(self.allocator); + zir_module.unload(self.gpa); self.analyzeRootZIRModule(zir_module) catch |err| switch (err) { error.AnalysisFail => { assert(self.totalErrorCount() != 0); @@ -876,7 +860,7 @@ pub fn update(self: *Module) !void { // Process the deletion set. while (self.deletion_set.popOrNull()) |decl| { - if (decl.dependants.items.len != 0) { + if (decl.dependants.items().len != 0) { decl.deletion_flag = false; continue; } @@ -889,7 +873,7 @@ pub fn update(self: *Module) !void { // to report error messages. Otherwise we unload all source files to save memory. if (self.totalErrorCount() == 0) { if (!self.keep_source_files_loaded) { - self.root_scope.unload(self.allocator); + self.root_scope.unload(self.gpa); } try self.bin_file.flush(); } @@ -915,10 +899,10 @@ pub fn totalErrorCount(self: *Module) usize { } pub fn getAllErrorsAlloc(self: *Module) !AllErrors { - var arena = std.heap.ArenaAllocator.init(self.allocator); + var arena = std.heap.ArenaAllocator.init(self.gpa); errdefer arena.deinit(); - var errors = std.ArrayList(AllErrors.Message).init(self.allocator); + var errors = std.ArrayList(AllErrors.Message).init(self.gpa); defer errors.deinit(); for (self.failed_files.items()) |entry| { @@ -989,9 +973,9 @@ pub fn performAllTheWork(self: *Module) error{OutOfMemory}!void { } // Here we tack on additional allocations to the Decl's arena. The allocations are // lifetime annotations in the ZIR. - var decl_arena = decl.typed_value.most_recent.arena.?.promote(self.allocator); + var decl_arena = decl.typed_value.most_recent.arena.?.promote(self.gpa); defer decl.typed_value.most_recent.arena.?.* = decl_arena.state; - try liveness.analyze(self.allocator, &decl_arena.allocator, payload.func.analysis.success); + try liveness.analyze(self.gpa, &decl_arena.allocator, payload.func.analysis.success); } assert(decl.typed_value.most_recent.typed_value.ty.hasCodeGenBits()); @@ -1002,9 +986,9 @@ pub fn performAllTheWork(self: *Module) error{OutOfMemory}!void { decl.analysis = .dependency_failure; }, else => { - try self.failed_decls.ensureCapacity(self.failed_decls.items().len + 1); + try self.failed_decls.ensureCapacity(self.gpa, self.failed_decls.items().len + 1); self.failed_decls.putAssumeCapacityNoClobber(decl, try ErrorMsg.create( - self.allocator, + self.gpa, decl.src(), "unable to codegen: {}", .{@errorName(err)}, @@ -1048,16 +1032,17 @@ fn ensureDeclAnalyzed(self: *Module, decl: *Decl) InnerError!void { // prior to re-analysis. self.deleteDeclExports(decl); // Dependencies will be re-discovered, so we remove them here prior to re-analysis. - for (decl.dependencies.items) |dep| { + for (decl.dependencies.items()) |entry| { + const dep = entry.key; dep.removeDependant(decl); - if (dep.dependants.items.len == 0 and !dep.deletion_flag) { + if (dep.dependants.items().len == 0 and !dep.deletion_flag) { // We don't perform a deletion here, because this Decl or another one // may end up referencing it before the update is complete. dep.deletion_flag = true; - try self.deletion_set.append(self.allocator, dep); + try self.deletion_set.append(self.gpa, dep); } } - decl.dependencies.shrink(self.allocator, 0); + decl.dependencies.clearRetainingCapacity(); break :blk true; }, @@ -1072,9 +1057,9 @@ fn ensureDeclAnalyzed(self: *Module, decl: *Decl) InnerError!void { error.OutOfMemory => return error.OutOfMemory, error.AnalysisFail => return error.AnalysisFail, else => { - try self.failed_decls.ensureCapacity(self.failed_decls.items().len + 1); + try self.failed_decls.ensureCapacity(self.gpa, self.failed_decls.items().len + 1); self.failed_decls.putAssumeCapacityNoClobber(decl, try ErrorMsg.create( - self.allocator, + self.gpa, decl.src(), "unable to analyze: {}", .{@errorName(err)}, @@ -1088,7 +1073,8 @@ fn ensureDeclAnalyzed(self: *Module, decl: *Decl) InnerError!void { // We may need to chase the dependants and re-analyze them. // However, if the decl is a function, and the type is the same, we do not need to. if (type_changed or decl.typed_value.most_recent.typed_value.val.tag() != .function) { - for (decl.dependants.items) |dep| { + for (decl.dependants.items()) |entry| { + const dep = entry.key; switch (dep.analysis) { .unreferenced => unreachable, .in_progress => unreachable, @@ -1127,8 +1113,8 @@ fn astGenAndAnalyzeDecl(self: *Module, decl: *Decl) !bool { // to complete the Decl analysis. var fn_type_scope: Scope.GenZIR = .{ .decl = decl, - .arena = std.heap.ArenaAllocator.init(self.allocator), - .instructions = std.ArrayList(*zir.Inst).init(self.allocator), + .arena = std.heap.ArenaAllocator.init(self.gpa), + .instructions = std.ArrayList(*zir.Inst).init(self.gpa), }; defer fn_type_scope.arena.deinit(); defer fn_type_scope.instructions.deinit(); @@ -1178,7 +1164,7 @@ fn astGenAndAnalyzeDecl(self: *Module, decl: *Decl) !bool { _ = try self.addZIRInst(&fn_type_scope.base, fn_src, zir.Inst.Return, .{ .operand = fn_type_inst }, .{}); // We need the memory for the Type to go into the arena for the Decl - var decl_arena = std.heap.ArenaAllocator.init(self.allocator); + var decl_arena = std.heap.ArenaAllocator.init(self.gpa); errdefer decl_arena.deinit(); const decl_arena_state = try decl_arena.allocator.create(std.heap.ArenaAllocator.State); @@ -1189,7 +1175,7 @@ fn astGenAndAnalyzeDecl(self: *Module, decl: *Decl) !bool { .instructions = .{}, .arena = &decl_arena.allocator, }; - defer block_scope.instructions.deinit(self.allocator); + defer block_scope.instructions.deinit(self.gpa); const fn_type = try self.analyzeBodyValueAsType(&block_scope, .{ .instructions = fn_type_scope.instructions.items, @@ -1202,8 +1188,8 @@ fn astGenAndAnalyzeDecl(self: *Module, decl: *Decl) !bool { // pass completes, and semantic analysis of it completes. var gen_scope: Scope.GenZIR = .{ .decl = decl, - .arena = std.heap.ArenaAllocator.init(self.allocator), - .instructions = std.ArrayList(*zir.Inst).init(self.allocator), + .arena = std.heap.ArenaAllocator.init(self.gpa), + .instructions = std.ArrayList(*zir.Inst).init(self.gpa), }; errdefer gen_scope.arena.deinit(); defer gen_scope.instructions.deinit(); @@ -1235,7 +1221,7 @@ fn astGenAndAnalyzeDecl(self: *Module, decl: *Decl) !bool { prev_type_has_bits = tvm.typed_value.ty.hasCodeGenBits(); type_changed = !tvm.typed_value.ty.eql(fn_type); - tvm.deinit(self.allocator); + tvm.deinit(self.gpa); } decl_arena_state.* = decl_arena.state; @@ -1626,40 +1612,31 @@ fn getSimplePrimitiveValue(name: []const u8) ?TypedValue { } fn declareDeclDependency(self: *Module, depender: *Decl, dependee: *Decl) !void { - try depender.dependencies.ensureCapacity(self.allocator, depender.dependencies.items.len + 1); - try dependee.dependants.ensureCapacity(self.allocator, dependee.dependants.items.len + 1); - - for (depender.dependencies.items) |item| { - if (item == dependee) break; // Already in the set. - } else { - depender.dependencies.appendAssumeCapacity(dependee); - } + try depender.dependencies.ensureCapacity(self.gpa, depender.dependencies.items().len + 1); + try dependee.dependants.ensureCapacity(self.gpa, dependee.dependants.items().len + 1); - for (dependee.dependants.items) |item| { - if (item == depender) break; // Already in the set. - } else { - dependee.dependants.appendAssumeCapacity(depender); - } + depender.dependencies.putAssumeCapacity(dependee, {}); + dependee.dependants.putAssumeCapacity(depender, {}); } fn getSrcModule(self: *Module, root_scope: *Scope.ZIRModule) !*zir.Module { switch (root_scope.status) { .never_loaded, .unloaded_success => { - try self.failed_files.ensureCapacity(self.failed_files.items().len + 1); + try self.failed_files.ensureCapacity(self.gpa, self.failed_files.items().len + 1); const source = try root_scope.getSource(self); var keep_zir_module = false; - const zir_module = try self.allocator.create(zir.Module); - defer if (!keep_zir_module) self.allocator.destroy(zir_module); + const zir_module = try self.gpa.create(zir.Module); + defer if (!keep_zir_module) self.gpa.destroy(zir_module); - zir_module.* = try zir.parse(self.allocator, source); - defer if (!keep_zir_module) zir_module.deinit(self.allocator); + zir_module.* = try zir.parse(self.gpa, source); + defer if (!keep_zir_module) zir_module.deinit(self.gpa); if (zir_module.error_msg) |src_err_msg| { self.failed_files.putAssumeCapacityNoClobber( &root_scope.base, - try ErrorMsg.create(self.allocator, src_err_msg.byte_offset, "{}", .{src_err_msg.msg}), + try ErrorMsg.create(self.gpa, src_err_msg.byte_offset, "{}", .{src_err_msg.msg}), ); root_scope.status = .unloaded_parse_failure; return error.AnalysisFail; @@ -1686,22 +1663,22 @@ fn getAstTree(self: *Module, root_scope: *Scope.File) !*ast.Tree { switch (root_scope.status) { .never_loaded, .unloaded_success => { - try self.failed_files.ensureCapacity(self.failed_files.items().len + 1); + try self.failed_files.ensureCapacity(self.gpa, self.failed_files.items().len + 1); const source = try root_scope.getSource(self); var keep_tree = false; - const tree = try std.zig.parse(self.allocator, source); + const tree = try std.zig.parse(self.gpa, source); defer if (!keep_tree) tree.deinit(); if (tree.errors.len != 0) { const parse_err = tree.errors[0]; - var msg = std.ArrayList(u8).init(self.allocator); + var msg = std.ArrayList(u8).init(self.gpa); defer msg.deinit(); try parse_err.render(tree.token_ids, msg.outStream()); - const err_msg = try self.allocator.create(ErrorMsg); + const err_msg = try self.gpa.create(ErrorMsg); err_msg.* = .{ .msg = msg.toOwnedSlice(), .byte_offset = tree.token_locs[parse_err.loc()].start, @@ -1732,11 +1709,11 @@ fn analyzeRootSrcFile(self: *Module, root_scope: *Scope.File) !void { const decls = tree.root_node.decls(); try self.work_queue.ensureUnusedCapacity(decls.len); - try root_scope.decls.ensureCapacity(self.allocator, decls.len); + try root_scope.decls.ensureCapacity(self.gpa, decls.len); // Keep track of the decls that we expect to see in this file so that // we know which ones have been deleted. - var deleted_decls = std.AutoHashMap(*Decl, void).init(self.allocator); + var deleted_decls = std.AutoHashMap(*Decl, void).init(self.gpa); defer deleted_decls.deinit(); try deleted_decls.ensureCapacity(root_scope.decls.items.len); for (root_scope.decls.items) |file_decl| { @@ -1760,9 +1737,9 @@ fn analyzeRootSrcFile(self: *Module, root_scope: *Scope.File) !void { decl.src_index = decl_i; if (deleted_decls.remove(decl) == null) { decl.analysis = .sema_failure; - const err_msg = try ErrorMsg.create(self.allocator, tree.token_locs[name_tok].start, "redefinition of '{}'", .{decl.name}); - errdefer err_msg.destroy(self.allocator); - try self.failed_decls.putNoClobber(decl, err_msg); + const err_msg = try ErrorMsg.create(self.gpa, tree.token_locs[name_tok].start, "redefinition of '{}'", .{decl.name}); + errdefer err_msg.destroy(self.gpa); + try self.failed_decls.putNoClobber(self.gpa, decl, err_msg); } else { if (!srcHashEql(decl.contents_hash, contents_hash)) { try self.markOutdatedDecl(decl); @@ -1796,14 +1773,14 @@ fn analyzeRootZIRModule(self: *Module, root_scope: *Scope.ZIRModule) !void { const src_module = try self.getSrcModule(root_scope); try self.work_queue.ensureUnusedCapacity(src_module.decls.len); - try root_scope.decls.ensureCapacity(self.allocator, src_module.decls.len); + try root_scope.decls.ensureCapacity(self.gpa, src_module.decls.len); - var exports_to_resolve = std.ArrayList(*zir.Decl).init(self.allocator); + var exports_to_resolve = std.ArrayList(*zir.Decl).init(self.gpa); defer exports_to_resolve.deinit(); // Keep track of the decls that we expect to see in this file so that // we know which ones have been deleted. - var deleted_decls = std.AutoHashMap(*Decl, void).init(self.allocator); + var deleted_decls = std.AutoHashMap(*Decl, void).init(self.gpa); defer deleted_decls.deinit(); try deleted_decls.ensureCapacity(self.decl_table.items().len); for (self.decl_table.items()) |entry| { @@ -1845,7 +1822,7 @@ fn analyzeRootZIRModule(self: *Module, root_scope: *Scope.ZIRModule) !void { } fn deleteDecl(self: *Module, decl: *Decl) !void { - try self.deletion_set.ensureCapacity(self.allocator, self.deletion_set.items.len + decl.dependencies.items.len); + try self.deletion_set.ensureCapacity(self.gpa, self.deletion_set.items.len + decl.dependencies.items().len); // Remove from the namespace it resides in. In the case of an anonymous Decl it will // not be present in the set, and this does nothing. @@ -1855,9 +1832,10 @@ fn deleteDecl(self: *Module, decl: *Decl) !void { const name_hash = decl.fullyQualifiedNameHash(); self.decl_table.removeAssertDiscard(name_hash); // Remove itself from its dependencies, because we are about to destroy the decl pointer. - for (decl.dependencies.items) |dep| { + for (decl.dependencies.items()) |entry| { + const dep = entry.key; dep.removeDependant(decl); - if (dep.dependants.items.len == 0 and !dep.deletion_flag) { + if (dep.dependants.items().len == 0 and !dep.deletion_flag) { // We don't recursively perform a deletion here, because during the update, // another reference to it may turn up. dep.deletion_flag = true; @@ -1865,7 +1843,8 @@ fn deleteDecl(self: *Module, decl: *Decl) !void { } } // Anything that depends on this deleted decl certainly needs to be re-analyzed. - for (decl.dependants.items) |dep| { + for (decl.dependants.items()) |entry| { + const dep = entry.key; dep.removeDependency(decl); if (dep.analysis != .outdated) { // TODO Move this failure possibility to the top of the function. @@ -1873,11 +1852,11 @@ fn deleteDecl(self: *Module, decl: *Decl) !void { } } if (self.failed_decls.remove(decl)) |entry| { - entry.value.destroy(self.allocator); + entry.value.destroy(self.gpa); } self.deleteDeclExports(decl); self.bin_file.freeDecl(decl); - decl.destroy(self.allocator); + decl.destroy(self.gpa); } /// Delete all the Export objects that are caused by this Decl. Re-analysis of @@ -1899,7 +1878,7 @@ fn deleteDeclExports(self: *Module, decl: *Decl) void { i += 1; } } - decl_exports_kv.value = self.allocator.shrink(list, new_len); + decl_exports_kv.value = self.gpa.shrink(list, new_len); if (new_len == 0) { self.decl_exports.removeAssertDiscard(exp.exported_decl); } @@ -1907,12 +1886,12 @@ fn deleteDeclExports(self: *Module, decl: *Decl) void { self.bin_file.deleteExport(exp.link); if (self.failed_exports.remove(exp)) |entry| { - entry.value.destroy(self.allocator); + entry.value.destroy(self.gpa); } _ = self.symbol_exports.remove(exp.options.name); - self.allocator.destroy(exp); + self.gpa.destroy(exp); } - self.allocator.free(kv.value); + self.gpa.free(kv.value); } fn analyzeFnBody(self: *Module, decl: *Decl, func: *Fn) !void { @@ -1920,7 +1899,7 @@ fn analyzeFnBody(self: *Module, decl: *Decl, func: *Fn) !void { defer tracy.end(); // Use the Decl's arena for function memory. - var arena = decl.typed_value.most_recent.arena.?.promote(self.allocator); + var arena = decl.typed_value.most_recent.arena.?.promote(self.gpa); defer decl.typed_value.most_recent.arena.?.* = arena.state; var inner_block: Scope.Block = .{ .parent = null, @@ -1929,10 +1908,10 @@ fn analyzeFnBody(self: *Module, decl: *Decl, func: *Fn) !void { .instructions = .{}, .arena = &arena.allocator, }; - defer inner_block.instructions.deinit(self.allocator); + defer inner_block.instructions.deinit(self.gpa); const fn_zir = func.analysis.queued; - defer fn_zir.arena.promote(self.allocator).deinit(); + defer fn_zir.arena.promote(self.gpa).deinit(); func.analysis = .{ .in_progress = {} }; //std.debug.warn("set {} to in_progress\n", .{decl.name}); @@ -1947,7 +1926,7 @@ fn markOutdatedDecl(self: *Module, decl: *Decl) !void { //std.debug.warn("mark {} outdated\n", .{decl.name}); try self.work_queue.writeItem(.{ .analyze_decl = decl }); if (self.failed_decls.remove(decl)) |entry| { - entry.value.destroy(self.allocator); + entry.value.destroy(self.gpa); } decl.analysis = .outdated; } @@ -1958,7 +1937,7 @@ fn allocateNewDecl( src_index: usize, contents_hash: std.zig.SrcHash, ) !*Decl { - const new_decl = try self.allocator.create(Decl); + const new_decl = try self.gpa.create(Decl); new_decl.* = .{ .name = "", .scope = scope.namespace(), @@ -1981,10 +1960,10 @@ fn createNewDecl( name_hash: Scope.NameHash, contents_hash: std.zig.SrcHash, ) !*Decl { - try self.decl_table.ensureCapacity(self.decl_table.items().len + 1); + try self.decl_table.ensureCapacity(self.gpa, self.decl_table.items().len + 1); const new_decl = try self.allocateNewDecl(scope, src_index, contents_hash); - errdefer self.allocator.destroy(new_decl); - new_decl.name = try mem.dupeZ(self.allocator, u8, decl_name); + errdefer self.gpa.destroy(new_decl); + new_decl.name = try mem.dupeZ(self.gpa, u8, decl_name); self.decl_table.putAssumeCapacityNoClobber(name_hash, new_decl); return new_decl; } @@ -1992,7 +1971,7 @@ fn createNewDecl( fn analyzeZirDecl(self: *Module, decl: *Decl, src_decl: *zir.Decl) InnerError!bool { var decl_scope: Scope.DeclAnalysis = .{ .decl = decl, - .arena = std.heap.ArenaAllocator.init(self.allocator), + .arena = std.heap.ArenaAllocator.init(self.gpa), }; errdefer decl_scope.arena.deinit(); @@ -2008,7 +1987,7 @@ fn analyzeZirDecl(self: *Module, decl: *Decl, src_decl: *zir.Decl) InnerError!bo prev_type_has_bits = tvm.typed_value.ty.hasCodeGenBits(); type_changed = !tvm.typed_value.ty.eql(typed_value.ty); - tvm.deinit(self.allocator); + tvm.deinit(self.gpa); } arena_state.* = decl_scope.arena.state; @@ -2146,11 +2125,11 @@ fn analyzeExport(self: *Module, scope: *Scope, src: usize, symbol_name: []const else => return self.fail(scope, src, "unable to export type '{}'", .{typed_value.ty}), } - try self.decl_exports.ensureCapacity(self.decl_exports.items().len + 1); - try self.export_owners.ensureCapacity(self.export_owners.items().len + 1); + try self.decl_exports.ensureCapacity(self.gpa, self.decl_exports.items().len + 1); + try self.export_owners.ensureCapacity(self.gpa, self.export_owners.items().len + 1); - const new_export = try self.allocator.create(Export); - errdefer self.allocator.destroy(new_export); + const new_export = try self.gpa.create(Export); + errdefer self.gpa.destroy(new_export); const owner_decl = scope.decl().?; @@ -2164,27 +2143,27 @@ fn analyzeExport(self: *Module, scope: *Scope, src: usize, symbol_name: []const }; // Add to export_owners table. - const eo_gop = self.export_owners.getOrPut(owner_decl) catch unreachable; + const eo_gop = self.export_owners.getOrPut(self.gpa, owner_decl) catch unreachable; if (!eo_gop.found_existing) { eo_gop.entry.value = &[0]*Export{}; } - eo_gop.entry.value = try self.allocator.realloc(eo_gop.entry.value, eo_gop.entry.value.len + 1); + eo_gop.entry.value = try self.gpa.realloc(eo_gop.entry.value, eo_gop.entry.value.len + 1); eo_gop.entry.value[eo_gop.entry.value.len - 1] = new_export; - errdefer eo_gop.entry.value = self.allocator.shrink(eo_gop.entry.value, eo_gop.entry.value.len - 1); + errdefer eo_gop.entry.value = self.gpa.shrink(eo_gop.entry.value, eo_gop.entry.value.len - 1); // Add to exported_decl table. - const de_gop = self.decl_exports.getOrPut(exported_decl) catch unreachable; + const de_gop = self.decl_exports.getOrPut(self.gpa, exported_decl) catch unreachable; if (!de_gop.found_existing) { de_gop.entry.value = &[0]*Export{}; } - de_gop.entry.value = try self.allocator.realloc(de_gop.entry.value, de_gop.entry.value.len + 1); + de_gop.entry.value = try self.gpa.realloc(de_gop.entry.value, de_gop.entry.value.len + 1); de_gop.entry.value[de_gop.entry.value.len - 1] = new_export; - errdefer de_gop.entry.value = self.allocator.shrink(de_gop.entry.value, de_gop.entry.value.len - 1); + errdefer de_gop.entry.value = self.gpa.shrink(de_gop.entry.value, de_gop.entry.value.len - 1); if (self.symbol_exports.get(symbol_name)) |_| { - try self.failed_exports.ensureCapacity(self.failed_exports.items().len + 1); + try self.failed_exports.ensureCapacity(self.gpa, self.failed_exports.items().len + 1); self.failed_exports.putAssumeCapacityNoClobber(new_export, try ErrorMsg.create( - self.allocator, + self.gpa, src, "exported symbol collision: {}", .{symbol_name}, @@ -2198,9 +2177,9 @@ fn analyzeExport(self: *Module, scope: *Scope, src: usize, symbol_name: []const self.bin_file.updateDeclExports(self, exported_decl, de_gop.entry.value) catch |err| switch (err) { error.OutOfMemory => return error.OutOfMemory, else => { - try self.failed_exports.ensureCapacity(self.failed_exports.items().len + 1); + try self.failed_exports.ensureCapacity(self.gpa, self.failed_exports.items().len + 1); self.failed_exports.putAssumeCapacityNoClobber(new_export, try ErrorMsg.create( - self.allocator, + self.gpa, src, "unable to export: {}", .{@errorName(err)}, @@ -2224,13 +2203,13 @@ fn addNewInstArgs( } fn newZIRInst( - allocator: *Allocator, + gpa: *Allocator, src: usize, comptime T: type, positionals: std.meta.fieldInfo(T, "positionals").field_type, kw_args: std.meta.fieldInfo(T, "kw_args").field_type, ) !*zir.Inst { - const inst = try allocator.create(T); + const inst = try gpa.create(T); inst.* = .{ .base = .{ .tag = T.base_tag, @@ -2273,7 +2252,7 @@ fn addNewInst(self: *Module, block: *Scope.Block, src: usize, ty: Type, comptime }, .args = undefined, }; - try block.instructions.append(self.allocator, &inst.base); + try block.instructions.append(self.gpa, &inst.base); return inst; } @@ -2433,7 +2412,7 @@ fn analyzeInst(self: *Module, scope: *Scope, old_inst: *zir.Inst) InnerError!*In fn analyzeInstStr(self: *Module, scope: *Scope, str_inst: *zir.Inst.Str) InnerError!*Inst { // The bytes references memory inside the ZIR module, which can get deallocated // after semantic analysis is complete. We need the memory to be in the new anonymous Decl's arena. - var new_decl_arena = std.heap.ArenaAllocator.init(self.allocator); + var new_decl_arena = std.heap.ArenaAllocator.init(self.gpa); const arena_bytes = try new_decl_arena.allocator.dupe(u8, str_inst.positionals.bytes); const ty_payload = try scope.arena().create(Type.Payload.Array_u8_Sentinel0); @@ -2457,8 +2436,8 @@ fn createAnonymousDecl( ) !*Decl { const name_index = self.getNextAnonNameIndex(); const scope_decl = scope.decl().?; - const name = try std.fmt.allocPrint(self.allocator, "{}${}", .{ scope_decl.name, name_index }); - defer self.allocator.free(name); + const name = try std.fmt.allocPrint(self.gpa, "{}${}", .{ scope_decl.name, name_index }); + defer self.gpa.free(name); const name_hash = scope.namespace().fullyQualifiedNameHash(name); const src_hash: std.zig.SrcHash = undefined; const new_decl = try self.createNewDecl(scope, name, scope_decl.src_index, name_hash, src_hash); @@ -2554,8 +2533,8 @@ fn analyzeInstBlock(self: *Module, scope: *Scope, inst: *zir.Inst.Block) InnerEr }; const label = &child_block.label.?; - defer child_block.instructions.deinit(self.allocator); - defer label.results.deinit(self.allocator); + defer child_block.instructions.deinit(self.gpa); + defer label.results.deinit(self.gpa); try self.analyzeBody(&child_block.base, inst.positionals.body); @@ -2567,7 +2546,7 @@ fn analyzeInstBlock(self: *Module, scope: *Scope, inst: *zir.Inst.Block) InnerEr // No need to add the Block instruction; we can add the instructions to the parent block directly. // Blocks are terminated with a noreturn instruction which we do not want to include. const instrs = child_block.instructions.items; - try parent_block.instructions.appendSlice(self.allocator, instrs[0 .. instrs.len - 1]); + try parent_block.instructions.appendSlice(self.gpa, instrs[0 .. instrs.len - 1]); if (label.results.items.len == 1) { return label.results.items[0]; } else { @@ -2577,7 +2556,7 @@ fn analyzeInstBlock(self: *Module, scope: *Scope, inst: *zir.Inst.Block) InnerEr // Need to set the type and emit the Block instruction. This allows machine code generation // to emit a jump instruction to after the block when it encounters the break. - try parent_block.instructions.append(self.allocator, &block_inst.base); + try parent_block.instructions.append(self.gpa, &block_inst.base); block_inst.base.ty = try self.resolvePeerTypes(scope, label.results.items); block_inst.args.body = .{ .instructions = try parent_block.arena.dupe(*Inst, child_block.instructions.items) }; return &block_inst.base; @@ -2596,7 +2575,7 @@ fn analyzeInstBreakVoid(self: *Module, scope: *Scope, inst: *zir.Inst.BreakVoid) while (opt_block) |block| { if (block.label) |*label| { if (mem.eql(u8, label.name, label_name)) { - try label.results.append(self.allocator, void_inst); + try label.results.append(self.gpa, void_inst); return self.constNoReturn(scope, inst.base.src); } } @@ -2719,8 +2698,8 @@ fn analyzeInstCall(self: *Module, scope: *Scope, inst: *zir.Inst.Call) InnerErro // TODO handle function calls of generic functions - const fn_param_types = try self.allocator.alloc(Type, fn_params_len); - defer self.allocator.free(fn_param_types); + const fn_param_types = try self.gpa.alloc(Type, fn_params_len); + defer self.gpa.free(fn_param_types); func.ty.fnParamTypes(fn_param_types); const casted_args = try scope.arena().alloc(*Inst, fn_params_len); @@ -2739,7 +2718,7 @@ fn analyzeInstCall(self: *Module, scope: *Scope, inst: *zir.Inst.Call) InnerErro fn analyzeInstFn(self: *Module, scope: *Scope, fn_inst: *zir.Inst.Fn) InnerError!*Inst { const fn_type = try self.resolveType(scope, fn_inst.positionals.fn_type); const fn_zir = blk: { - var fn_arena = std.heap.ArenaAllocator.init(self.allocator); + var fn_arena = std.heap.ArenaAllocator.init(self.gpa); errdefer fn_arena.deinit(); const fn_zir = try scope.arena().create(Fn.ZIR); @@ -3120,7 +3099,7 @@ fn analyzeInstCondBr(self: *Module, scope: *Scope, inst: *zir.Inst.CondBr) Inner .instructions = .{}, .arena = parent_block.arena, }; - defer true_block.instructions.deinit(self.allocator); + defer true_block.instructions.deinit(self.gpa); try self.analyzeBody(&true_block.base, inst.positionals.true_body); var false_block: Scope.Block = .{ @@ -3130,7 +3109,7 @@ fn analyzeInstCondBr(self: *Module, scope: *Scope, inst: *zir.Inst.CondBr) Inner .instructions = .{}, .arena = parent_block.arena, }; - defer false_block.instructions.deinit(self.allocator); + defer false_block.instructions.deinit(self.gpa); try self.analyzeBody(&false_block.base, inst.positionals.false_body); return self.addNewInstArgs(parent_block, inst.base.src, Type.initTag(.void), Inst.CondBr, Inst.Args(Inst.CondBr){ @@ -3284,7 +3263,7 @@ fn cmpNumeric( return self.constUndef(scope, src, Type.initTag(.bool)); const is_unsigned = if (lhs_is_float) x: { var bigint_space: Value.BigIntSpace = undefined; - var bigint = try lhs_val.toBigInt(&bigint_space).toManaged(self.allocator); + var bigint = try lhs_val.toBigInt(&bigint_space).toManaged(self.gpa); defer bigint.deinit(); const zcmp = lhs_val.orderAgainstZero(); if (lhs_val.floatHasFraction()) { @@ -3319,7 +3298,7 @@ fn cmpNumeric( return self.constUndef(scope, src, Type.initTag(.bool)); const is_unsigned = if (rhs_is_float) x: { var bigint_space: Value.BigIntSpace = undefined; - var bigint = try rhs_val.toBigInt(&bigint_space).toManaged(self.allocator); + var bigint = try rhs_val.toBigInt(&bigint_space).toManaged(self.gpa); defer bigint.deinit(); const zcmp = rhs_val.orderAgainstZero(); if (rhs_val.floatHasFraction()) { @@ -3457,7 +3436,7 @@ fn coerceArrayPtrToSlice(self: *Module, scope: *Scope, dest_type: Type, inst: *I fn fail(self: *Module, scope: *Scope, src: usize, comptime format: []const u8, args: var) InnerError { @setCold(true); - const err_msg = try ErrorMsg.create(self.allocator, src, format, args); + const err_msg = try ErrorMsg.create(self.gpa, src, format, args); return self.failWithOwnedErrorMsg(scope, src, err_msg); } @@ -3487,9 +3466,9 @@ fn failNode( fn failWithOwnedErrorMsg(self: *Module, scope: *Scope, src: usize, err_msg: *ErrorMsg) InnerError { { - errdefer err_msg.destroy(self.allocator); - try self.failed_decls.ensureCapacity(self.failed_decls.items().len + 1); - try self.failed_files.ensureCapacity(self.failed_files.items().len + 1); + errdefer err_msg.destroy(self.gpa); + try self.failed_decls.ensureCapacity(self.gpa, self.failed_decls.items().len + 1); + try self.failed_files.ensureCapacity(self.gpa, self.failed_files.items().len + 1); } switch (scope.tag) { .decl => { @@ -3542,28 +3521,28 @@ pub const ErrorMsg = struct { byte_offset: usize, msg: []const u8, - pub fn create(allocator: *Allocator, byte_offset: usize, comptime format: []const u8, args: var) !*ErrorMsg { - const self = try allocator.create(ErrorMsg); - errdefer allocator.destroy(self); - self.* = try init(allocator, byte_offset, format, args); + pub fn create(gpa: *Allocator, byte_offset: usize, comptime format: []const u8, args: var) !*ErrorMsg { + const self = try gpa.create(ErrorMsg); + errdefer gpa.destroy(self); + self.* = try init(gpa, byte_offset, format, args); return self; } /// Assumes the ErrorMsg struct and msg were both allocated with allocator. - pub fn destroy(self: *ErrorMsg, allocator: *Allocator) void { - self.deinit(allocator); - allocator.destroy(self); + pub fn destroy(self: *ErrorMsg, gpa: *Allocator) void { + self.deinit(gpa); + gpa.destroy(self); } - pub fn init(allocator: *Allocator, byte_offset: usize, comptime format: []const u8, args: var) !ErrorMsg { + pub fn init(gpa: *Allocator, byte_offset: usize, comptime format: []const u8, args: var) !ErrorMsg { return ErrorMsg{ .byte_offset = byte_offset, - .msg = try std.fmt.allocPrint(allocator, format, args), + .msg = try std.fmt.allocPrint(gpa, format, args), }; } - pub fn deinit(self: *ErrorMsg, allocator: *Allocator) void { - allocator.free(self.msg); + pub fn deinit(self: *ErrorMsg, gpa: *Allocator) void { + gpa.free(self.msg); self.* = undefined; } }; diff --git a/src-self-hosted/codegen.zig b/src-self-hosted/codegen.zig index eea3de7f36..e364763b0a 100644 --- a/src-self-hosted/codegen.zig +++ b/src-self-hosted/codegen.zig @@ -46,7 +46,14 @@ pub fn generateSymbol( var mc_args = try std.ArrayList(Function.MCValue).initCapacity(bin_file.allocator, param_types.len); defer mc_args.deinit(); - var next_stack_offset: u64 = 0; + var branch_stack = std.ArrayList(Function.Branch).init(bin_file.allocator); + defer { + assert(branch_stack.items.len == 1); + branch_stack.items[0].deinit(bin_file.allocator); + branch_stack.deinit(); + } + const branch = try branch_stack.addOne(); + branch.* = .{}; switch (fn_type.fnCallingConvention()) { .Naked => assert(mc_args.items.len == 0), @@ -61,8 +68,8 @@ pub fn generateSymbol( switch (param_type.zigTypeTag()) { .Bool, .Int => { if (next_int_reg >= integer_registers.len) { - try mc_args.append(.{ .stack_offset = next_stack_offset }); - next_stack_offset += param_type.abiSize(bin_file.options.target); + try mc_args.append(.{ .stack_offset = branch.next_stack_offset }); + branch.next_stack_offset += @intCast(u32, param_type.abiSize(bin_file.options.target)); } else { try mc_args.append(.{ .register = @enumToInt(integer_registers[next_int_reg]) }); next_int_reg += 1; @@ -100,23 +107,17 @@ pub fn generateSymbol( } var function = Function{ + .gpa = bin_file.allocator, .target = &bin_file.options.target, .bin_file = bin_file, .mod_fn = module_fn, .code = code, .err_msg = null, .args = mc_args.items, - .branch_stack = .{}, + .branch_stack = &branch_stack, }; - defer { - assert(function.branch_stack.items.len == 1); - function.branch_stack.items[0].inst_table.deinit(); - function.branch_stack.deinit(bin_file.allocator); - } - try function.branch_stack.append(bin_file.allocator, .{ - .inst_table = std.AutoHashMap(*ir.Inst, Function.MCValue).init(bin_file.allocator), - }); + branch.max_end_stack = branch.next_stack_offset; function.gen() catch |err| switch (err) { error.CodegenFail => return Result{ .fail = function.err_msg.? }, else => |e| return e, @@ -218,6 +219,7 @@ pub fn generateSymbol( } const Function = struct { + gpa: *Allocator, bin_file: *link.ElfFile, target: *const std.Target, mod_fn: *const Module.Fn, @@ -232,10 +234,37 @@ const Function = struct { /// within different branches. Special consideration is needed when a branch /// joins with its parent, to make sure all instructions have the same MCValue /// across each runtime branch upon joining. - branch_stack: std.ArrayListUnmanaged(Branch), + branch_stack: *std.ArrayList(Branch), const Branch = struct { - inst_table: std.AutoHashMap(*ir.Inst, MCValue), + inst_table: std.AutoHashMapUnmanaged(*ir.Inst, MCValue) = .{}, + + /// The key is an enum value of an arch-specific register. + registers: std.AutoHashMapUnmanaged(usize, RegisterAllocation) = .{}, + + /// Maps offset to what is stored there. + stack: std.AutoHashMapUnmanaged(usize, StackAllocation) = .{}, + /// Offset from the stack base, representing the end of the stack frame. + max_end_stack: u32 = 0, + /// Represents the current end stack offset. If there is no existing slot + /// to place a new stack allocation, it goes here, and then bumps `max_end_stack`. + next_stack_offset: u32 = 0, + + fn deinit(self: *Branch, gpa: *Allocator) void { + self.inst_table.deinit(gpa); + self.registers.deinit(gpa); + self.stack.deinit(gpa); + self.* = undefined; + } + }; + + const RegisterAllocation = struct { + inst: *ir.Inst, + }; + + const StackAllocation = struct { + inst: *ir.Inst, + size: u32, }; const MCValue = union(enum) { @@ -256,6 +285,13 @@ const Function = struct { memory: u64, /// The value is one of the stack variables. stack_offset: u64, + + fn isMemory(mcv: MCValue) bool { + return switch (mcv) { + .embedded_in_code, .memory, .stack_offset => true, + else => false, + }; + } }; fn gen(self: *Function) !void { @@ -318,7 +354,7 @@ const Function = struct { const inst_table = &self.branch_stack.items[0].inst_table; for (self.mod_fn.analysis.success.instructions) |inst| { const new_inst = try self.genFuncInst(inst, arch); - try inst_table.putNoClobber(inst, new_inst); + try inst_table.putNoClobber(self.gpa, inst, new_inst); } } @@ -344,19 +380,99 @@ const Function = struct { } fn genAdd(self: *Function, inst: *ir.Inst.Add, comptime arch: std.Target.Cpu.Arch) !MCValue { - const lhs = try self.resolveInst(inst.args.lhs); - const rhs = try self.resolveInst(inst.args.rhs); + // No side effects, so if it's unreferenced, do nothing. + if (inst.base.isUnused()) + return MCValue.dead; switch (arch) { - .i386, .x86_64 => { - // const lhs_reg = try self.instAsReg(lhs); - // const rhs_reg = try self.instAsReg(rhs); - // const result = try self.allocateReg(); - - // try self.code.append(??); + .x86_64 => { + // Biggest encoding of ADD is 8 bytes. + try self.code.ensureCapacity(self.code.items.len + 8); + + // In x86, ADD has 2 operands, destination and source. + // Either one, but not both, can be a memory operand. + // Source operand can be an immediate, 8 bits or 32 bits. + // So, if either one of the operands dies with this instruction, we can use it + // as the result MCValue. + var dst_mcv: MCValue = undefined; + var src_mcv: MCValue = undefined; + if (inst.base.operandDies(0)) { + // LHS dies; use it as the destination. + dst_mcv = try self.resolveInst(inst.args.lhs); + // Both operands cannot be memory. + if (dst_mcv.isMemory()) { + src_mcv = try self.resolveInstImmOrReg(inst.args.rhs); + } else { + src_mcv = try self.resolveInst(inst.args.rhs); + } + } else if (inst.base.operandDies(1)) { + // RHS dies; use it as the destination. + dst_mcv = try self.resolveInst(inst.args.rhs); + // Both operands cannot be memory. + if (dst_mcv.isMemory()) { + src_mcv = try self.resolveInstImmOrReg(inst.args.lhs); + } else { + src_mcv = try self.resolveInst(inst.args.lhs); + } + } else { + const lhs = try self.resolveInst(inst.args.lhs); + const rhs = try self.resolveInst(inst.args.rhs); + if (lhs.isMemory()) { + dst_mcv = try self.copyToNewRegister(inst.base.src, lhs); + src_mcv = rhs; + } else { + dst_mcv = try self.copyToNewRegister(inst.base.src, rhs); + src_mcv = lhs; + } + } + // x86 ADD supports only signed 32-bit immediates at most. If the immediate + // value is larger than this, we put it in a register. + // A potential opportunity for future optimization here would be keeping track + // of the fact that the instruction is available both as an immediate + // and as a register. + switch (src_mcv) { + .immediate => |imm| { + if (imm > std.math.maxInt(u31)) { + src_mcv = try self.copyToNewRegister(inst.base.src, src_mcv); + } + }, + else => {}, + } - // lhs_reg.release(); - // rhs_reg.release(); - return self.fail(inst.base.src, "TODO implement register allocation", .{}); + switch (dst_mcv) { + .none => unreachable, + .dead, .unreach, .immediate => unreachable, + .register => |dst_reg_usize| { + const dst_reg = @intToEnum(Reg(arch), @intCast(@TagType(Reg(arch)), dst_reg_usize)); + switch (src_mcv) { + .none => unreachable, + .dead, .unreach => unreachable, + .register => |src_reg_usize| { + const src_reg = @intToEnum(Reg(arch), @intCast(@TagType(Reg(arch)), src_reg_usize)); + self.rex(.{ .b = dst_reg.isExtended(), .r = src_reg.isExtended(), .w = dst_reg.size() == 64 }); + self.code.appendSliceAssumeCapacity(&[_]u8{ 0x1, 0xC0 | (@as(u8, src_reg.id() & 0b111) << 3) | @as(u8, dst_reg.id() & 0b111) }); + }, + .immediate => |imm| { + const imm32 = @intCast(u31, imm); // We handle this case above. + // 81 /0 id + if (imm32 <= std.math.maxInt(u7)) { + self.rex(.{ .b = dst_reg.isExtended(), .w = dst_reg.size() == 64 }); + self.code.appendSliceAssumeCapacity(&[_]u8{ 0x83, 0xC0 | @as(u8, dst_reg.id() & 0b111), @intCast(u8, imm32)}); + } else { + self.rex(.{ .r = dst_reg.isExtended(), .w = dst_reg.size() == 64 }); + self.code.appendSliceAssumeCapacity(&[_]u8{ 0x81, 0xC0 | @as(u8, dst_reg.id() & 0b111) }); + std.mem.writeIntLittle(u32, self.code.addManyAsArrayAssumeCapacity(4), imm32); + } + }, + .embedded_in_code, .memory, .stack_offset => { + return self.fail(inst.base.src, "TODO implement x86 add source memory", .{}); + }, + } + }, + .embedded_in_code, .memory, .stack_offset => { + return self.fail(inst.base.src, "TODO implement x86 add destination memory", .{}); + }, + } + return dst_mcv; }, else => return self.fail(inst.base.src, "TODO implement add for {}", .{self.target.cpu.arch}), } @@ -526,23 +642,23 @@ const Function = struct { /// resulting REX is meaningful, but will remain the same if it is not. /// * Deliberately inserting a "meaningless REX" requires explicit usage of /// 0x40, and cannot be done via this function. - fn REX(self: *Function, arg: struct { B: bool = false, W: bool = false, X: bool = false, R: bool = false }) !void { + fn rex(self: *Function, arg: struct { b: bool = false, w: bool = false, x: bool = false, r: bool = false }) void { // From section 2.2.1.2 of the manual, REX is encoded as b0100WRXB. var value: u8 = 0x40; - if (arg.B) { + if (arg.b) { value |= 0x1; } - if (arg.X) { + if (arg.x) { value |= 0x2; } - if (arg.R) { + if (arg.r) { value |= 0x4; } - if (arg.W) { + if (arg.w) { value |= 0x8; } if (value != 0x40) { - try self.code.append(value); + self.code.appendAssumeCapacity(value); } } @@ -570,11 +686,11 @@ const Function = struct { // If we're accessing e.g. r8d, we need to use a REX prefix before the actual operation. Since // this is a 32-bit operation, the W flag is set to zero. X is also zero, as we're not using a SIB. // Both R and B are set, as we're extending, in effect, the register bits *and* the operand. - try self.REX(.{ .R = reg.isExtended(), .B = reg.isExtended() }); + try self.code.ensureCapacity(self.code.items.len + 3); + self.rex(.{ .r = reg.isExtended(), .b = reg.isExtended() }); const id = @as(u8, reg.id() & 0b111); - return self.code.appendSlice(&[_]u8{ - 0x31, 0xC0 | id << 3 | id, - }); + self.code.appendSliceAssumeCapacity(&[_]u8{ 0x31, 0xC0 | id << 3 | id }); + return; } if (x <= std.math.maxInt(u32)) { // Next best case: if we set the lower four bytes, the upper four will be zeroed. @@ -607,9 +723,9 @@ const Function = struct { // Since we always need a REX here, let's just check if we also need to set REX.B. // // In this case, the encoding of the REX byte is 0b0100100B - - try self.REX(.{ .W = true, .B = reg.isExtended() }); - try self.code.resize(self.code.items.len + 9); + try self.code.ensureCapacity(self.code.items.len + 10); + self.rex(.{ .w = true, .b = reg.isExtended() }); + self.code.items.len += 9; self.code.items[self.code.items.len - 9] = 0xB8 | @as(u8, reg.id() & 0b111); const imm_ptr = self.code.items[self.code.items.len - 8 ..][0..8]; mem.writeIntLittle(u64, imm_ptr, x); @@ -620,13 +736,13 @@ const Function = struct { } // We need the offset from RIP in a signed i32 twos complement. // The instruction is 7 bytes long and RIP points to the next instruction. - // + try self.code.ensureCapacity(self.code.items.len + 7); // 64-bit LEA is encoded as REX.W 8D /r. If the register is extended, the REX byte is modified, // but the operation size is unchanged. Since we're using a disp32, we want mode 0 and lower three // bits as five. // REX 0x8D 0b00RRR101, where RRR is the lower three bits of the id. - try self.REX(.{ .W = true, .B = reg.isExtended() }); - try self.code.resize(self.code.items.len + 6); + self.rex(.{ .w = true, .b = reg.isExtended() }); + self.code.items.len += 6; const rip = self.code.items.len; const big_offset = @intCast(i64, code_offset) - @intCast(i64, rip); const offset = @intCast(i32, big_offset); @@ -646,9 +762,10 @@ const Function = struct { // If the *source* is extended, the B field must be 1. // Since the register is being accessed directly, the R/M mode is three. The reg field (the middle // three bits) contain the destination, and the R/M field (the lower three bits) contain the source. - try self.REX(.{ .W = true, .R = reg.isExtended(), .B = src_reg.isExtended() }); + try self.code.ensureCapacity(self.code.items.len + 3); + self.rex(.{ .w = true, .r = reg.isExtended(), .b = src_reg.isExtended() }); const R = 0xC0 | (@as(u8, reg.id() & 0b111) << 3) | @as(u8, src_reg.id() & 0b111); - try self.code.appendSlice(&[_]u8{ 0x8B, R }); + self.code.appendSliceAssumeCapacity(&[_]u8{ 0x8B, R }); }, .memory => |x| { if (reg.size() != 64) { @@ -662,14 +779,14 @@ const Function = struct { // The SIB must be 0x25, to indicate a disp32 with no scaled index. // 0b00RRR100, where RRR is the lower three bits of the register ID. // The instruction is thus eight bytes; REX 0x8B 0b00RRR100 0x25 followed by a four-byte disp32. - try self.REX(.{ .W = true, .B = reg.isExtended() }); - try self.code.resize(self.code.items.len + 7); - const r = 0x04 | (@as(u8, reg.id() & 0b111) << 3); - self.code.items[self.code.items.len - 7] = 0x8B; - self.code.items[self.code.items.len - 6] = r; - self.code.items[self.code.items.len - 5] = 0x25; - const imm_ptr = self.code.items[self.code.items.len - 4 ..][0..4]; - mem.writeIntLittle(u32, imm_ptr, @intCast(u32, x)); + try self.code.ensureCapacity(self.code.items.len + 8); + self.rex(.{ .w = true, .b = reg.isExtended() }); + self.code.appendSliceAssumeCapacity(&[_]u8{ + 0x8B, + 0x04 | (@as(u8, reg.id() & 0b111) << 3), // R + 0x25, + }); + mem.writeIntLittle(u32, self.code.addManyAsArrayAssumeCapacity(4), @intCast(u32, x)); } else { // If this is RAX, we can use a direct load; otherwise, we need to load the address, then indirectly load // the value. @@ -700,15 +817,15 @@ const Function = struct { // Currently, we're only allowing 64-bit registers, so we need the `REX.W 8B /r` variant. // TODO: determine whether to allow other sized registers, and if so, handle them properly. // This operation requires three bytes: REX 0x8B R/M - // + try self.code.ensureCapacity(self.code.items.len + 3); // For this operation, we want R/M mode *zero* (use register indirectly), and the two register // values must match. Thus, it's 00ABCABC where ABC is the lower three bits of the register ID. // // Furthermore, if this is an extended register, both B and R must be set in the REX byte, as *both* // register operands need to be marked as extended. - try self.REX(.{ .W = true, .B = reg.isExtended(), .R = reg.isExtended() }); + self.rex(.{ .w = true, .b = reg.isExtended(), .r = reg.isExtended() }); const RM = (@as(u8, reg.id() & 0b111) << 3) | @truncate(u3, reg.id()); - try self.code.appendSlice(&[_]u8{ 0x8B, RM }); + self.code.appendSliceAssumeCapacity(&[_]u8{ 0x8B, RM }); } } }, @@ -731,36 +848,40 @@ const Function = struct { } fn resolveInst(self: *Function, inst: *ir.Inst) !MCValue { - if (self.inst_table.get(inst)) |mcv| { - return mcv; - } // Constants have static lifetimes, so they are always memoized in the outer most table. if (inst.cast(ir.Inst.Constant)) |const_inst| { const branch = &self.branch_stack.items[0]; - const gop = try branch.inst_table.getOrPut(inst); + const gop = try branch.inst_table.getOrPut(self.gpa, inst); if (!gop.found_existing) { const mcv = try self.genTypedValue(inst.src, .{ .ty = inst.ty, .val = const_inst.val }); - try branch.inst_table.putNoClobber(inst, mcv); - gop.kv.value = mcv; + try branch.inst_table.putNoClobber(self.gpa, inst, mcv); + gop.entry.value = mcv; return mcv; } - return gop.kv.value; + return gop.entry.value; } // Treat each stack item as a "layer" on top of the previous one. var i: usize = self.branch_stack.items.len; while (true) { i -= 1; - if (self.branch_stack.items[i].inst_table.getValue(inst)) |mcv| { + if (self.branch_stack.items[i].inst_table.get(inst)) |mcv| { return mcv; } } } + fn resolveInstImmOrReg(self: *Function, inst: *ir.Inst) !MCValue { + return self.fail(inst.src, "TODO implement resolveInstImmOrReg", .{}); + } + + fn copyToNewRegister(self: *Function, src: usize, mcv: MCValue) !MCValue { + return self.fail(src, "TODO implement copyToNewRegister", .{}); + } + fn genTypedValue(self: *Function, src: usize, typed_value: TypedValue) !MCValue { const ptr_bits = self.target.cpu.arch.ptrBitWidth(); const ptr_bytes: u64 = @divExact(ptr_bits, 8); - const allocator = self.code.allocator; switch (typed_value.ty.zigTypeTag()) { .Pointer => { if (typed_value.val.cast(Value.Payload.DeclRef)) |payload| { @@ -787,7 +908,7 @@ const Function = struct { fn fail(self: *Function, src: usize, comptime format: []const u8, args: var) error{ CodegenFail, OutOfMemory } { @setCold(true); assert(self.err_msg == null); - self.err_msg = try ErrorMsg.create(self.code.allocator, src, format, args); + self.err_msg = try ErrorMsg.create(self.bin_file.allocator, src, format, args); return error.CodegenFail; } }; diff --git a/src-self-hosted/ir.zig b/src-self-hosted/ir.zig index 6fa06c8138..17e6a54725 100644 --- a/src-self-hosted/ir.zig +++ b/src-self-hosted/ir.zig @@ -2,6 +2,7 @@ const std = @import("std"); const Value = @import("value.zig").Value; const Type = @import("type.zig").Type; const Module = @import("Module.zig"); +const assert = std.debug.assert; /// These are in-memory, analyzed instructions. See `zir.Inst` for the representation /// of instructions that correspond to the ZIR text format. @@ -12,18 +13,28 @@ pub const Inst = struct { tag: Tag, /// Each bit represents the index of an `Inst` parameter in the `args` field. /// If a bit is set, it marks the end of the lifetime of the corresponding - /// instruction parameter. For example, 0b00000101 means that the first and + /// instruction parameter. For example, 0b000_00101 means that the first and /// third `Inst` parameters' lifetimes end after this instruction, and will /// not have any more following references. /// The most significant bit being set means that the instruction itself is /// never referenced, in other words its lifetime ends as soon as it finishes. - /// If the byte is `0xff`, it means this is a special case and this data is - /// encoded elsewhere. - deaths: u8 = 0xff, + /// If bit 7 (0b1xxx_xxxx) is set, it means this instruction itself is unreferenced. + /// If bit 6 (0bx1xx_xxxx) is set, it means this is a special case and the + /// lifetimes of operands are encoded elsewhere. + deaths: u8 = undefined, ty: Type, /// Byte offset into the source. src: usize, + pub fn isUnused(self: Inst) bool { + return (self.deaths & 0b1000_0000) != 0; + } + + pub fn operandDies(self: Inst, index: u3) bool { + assert(index < 6); + return @truncate(u1, self.deaths << index) != 0; + } + pub const Tag = enum { add, arg, @@ -240,4 +251,4 @@ pub const Inst = struct { pub const Body = struct { instructions: []*Inst, -}; \ No newline at end of file +}; diff --git a/src-self-hosted/link.zig b/src-self-hosted/link.zig index c615ad35fd..a0894fb1a1 100644 --- a/src-self-hosted/link.zig +++ b/src-self-hosted/link.zig @@ -1007,7 +1007,7 @@ pub const ElfFile = struct { .appended => code_buffer.items, .fail => |em| { decl.analysis = .codegen_failure; - _ = try module.failed_decls.put(decl, em); + _ = try module.failed_decls.put(module.gpa, decl, em); return; }, }; @@ -1093,7 +1093,7 @@ pub const ElfFile = struct { for (exports) |exp| { if (exp.options.section) |section_name| { if (!mem.eql(u8, section_name, ".text")) { - try module.failed_exports.ensureCapacity(module.failed_exports.items().len + 1); + try module.failed_exports.ensureCapacity(module.gpa, module.failed_exports.items().len + 1); module.failed_exports.putAssumeCapacityNoClobber( exp, try Module.ErrorMsg.create(self.allocator, 0, "Unimplemented: ExportOptions.section", .{}), @@ -1111,7 +1111,7 @@ pub const ElfFile = struct { }, .Weak => elf.STB_WEAK, .LinkOnce => { - try module.failed_exports.ensureCapacity(module.failed_exports.items().len + 1); + try module.failed_exports.ensureCapacity(module.gpa, module.failed_exports.items().len + 1); module.failed_exports.putAssumeCapacityNoClobber( exp, try Module.ErrorMsg.create(self.allocator, 0, "Unimplemented: GlobalLinkage.LinkOnce", .{}), diff --git a/src-self-hosted/liveness.zig b/src-self-hosted/liveness.zig index 65f81bbf4a..2e0aad49c3 100644 --- a/src-self-hosted/liveness.zig +++ b/src-self-hosted/liveness.zig @@ -123,7 +123,7 @@ fn analyzeInst(arena: *std.mem.Allocator, table: *std.AutoHashMap(*ir.Inst, void if (arg_index >= 6) { @compileError("out of bits to mark deaths of operands"); } - const prev = try table.put(@field(inst.args, field.name), {}); + const prev = try table.fetchPut(@field(inst.args, field.name), {}); if (prev == null) { // Death. inst.base.deaths |= 1 << arg_index; @@ -131,4 +131,4 @@ fn analyzeInst(arena: *std.mem.Allocator, table: *std.AutoHashMap(*ir.Inst, void arg_index += 1; } } -} \ No newline at end of file +} diff --git a/src-self-hosted/main.zig b/src-self-hosted/main.zig index 33f422692c..82edcc4eff 100644 --- a/src-self-hosted/main.zig +++ b/src-self-hosted/main.zig @@ -502,7 +502,7 @@ fn updateModule(gpa: *Allocator, module: *Module, zir_out_path: ?[]const u8) !vo const update_nanos = timer.read(); var errors = try module.getAllErrorsAlloc(); - defer errors.deinit(module.allocator); + defer errors.deinit(module.gpa); if (errors.list.len != 0) { for (errors.list) |full_err_msg| { -- cgit v1.2.3 From 12737c9a3071a49f8c05348fadd0b602b6952542 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Mon, 6 Jul 2020 09:21:57 +0000 Subject: stage2: codegen skeleton for cmp and sub --- src-self-hosted/Module.zig | 5 + src-self-hosted/codegen.zig | 297 ++++++++++++++++++++++++++++++-------------- src-self-hosted/ir.zig | 14 ++- src-self-hosted/zir.zig | 30 +++++ 4 files changed, 254 insertions(+), 92 deletions(-) (limited to 'src-self-hosted/Module.zig') diff --git a/src-self-hosted/Module.zig b/src-self-hosted/Module.zig index 4240a1c6c8..776e63018b 100644 --- a/src-self-hosted/Module.zig +++ b/src-self-hosted/Module.zig @@ -2402,6 +2402,7 @@ fn analyzeInst(self: *Module, scope: *Scope, old_inst: *zir.Inst) InnerError!*In .bitcast => return self.analyzeInstBitCast(scope, old_inst.cast(zir.Inst.BitCast).?), .elemptr => return self.analyzeInstElemPtr(scope, old_inst.cast(zir.Inst.ElemPtr).?), .add => return self.analyzeInstAdd(scope, old_inst.cast(zir.Inst.Add).?), + .sub => return self.analyzeInstSub(scope, old_inst.cast(zir.Inst.Sub).?), .cmp => return self.analyzeInstCmp(scope, old_inst.cast(zir.Inst.Cmp).?), .condbr => return self.analyzeInstCondBr(scope, old_inst.cast(zir.Inst.CondBr).?), .isnull => return self.analyzeInstIsNull(scope, old_inst.cast(zir.Inst.IsNull).?), @@ -2903,6 +2904,10 @@ fn analyzeInstElemPtr(self: *Module, scope: *Scope, inst: *zir.Inst.ElemPtr) Inn return self.fail(scope, inst.base.src, "TODO implement more analyze elemptr", .{}); } +fn analyzeInstSub(self: *Module, scope: *Scope, inst: *zir.Inst.Sub) InnerError!*Inst { + return self.fail(scope, inst.base.src, "TODO implement analysis of sub", .{}); +} + fn analyzeInstAdd(self: *Module, scope: *Scope, inst: *zir.Inst.Add) InnerError!*Inst { const tracy = trace(@src()); defer tracy.end(); diff --git a/src-self-hosted/codegen.zig b/src-self-hosted/codegen.zig index e364763b0a..aac1a53d6a 100644 --- a/src-self-hosted/codegen.zig +++ b/src-self-hosted/codegen.zig @@ -285,6 +285,9 @@ const Function = struct { memory: u64, /// The value is one of the stack variables. stack_offset: u64, + /// The value is the compare flag, with this operator + /// applied on top of it. + compare_flag: std.math.CompareOperator, fn isMemory(mcv: MCValue) bool { return switch (mcv) { @@ -292,6 +295,31 @@ const Function = struct { else => false, }; } + + fn isImmediate(mcv: MCValue) bool { + return switch (mcv) { + .immediate => true, + else => false, + }; + } + + fn isMutable(mcv: MCValue) bool { + return switch (mcv) { + .none => unreachable, + .unreach => unreachable, + .dead => unreachable, + + .immediate, + .embedded_in_code, + .memory, + .compare_flag, + => false, + + .register, + .stack_offset, + => true, + }; + } }; fn gen(self: *Function) !void { @@ -362,20 +390,21 @@ const Function = struct { switch (inst.tag) { .add => return self.genAdd(inst.cast(ir.Inst.Add).?, arch), .arg => return self.genArg(inst.cast(ir.Inst.Arg).?), + .assembly => return self.genAsm(inst.cast(ir.Inst.Assembly).?, arch), + .bitcast => return self.genBitCast(inst.cast(ir.Inst.BitCast).?), .block => return self.genBlock(inst.cast(ir.Inst.Block).?, arch), .breakpoint => return self.genBreakpoint(inst.src, arch), .call => return self.genCall(inst.cast(ir.Inst.Call).?, arch), - .unreach => return MCValue{ .unreach = {} }, + .cmp => return self.genCmp(inst.cast(ir.Inst.Cmp).?, arch), + .condbr => return self.genCondBr(inst.cast(ir.Inst.CondBr).?, arch), .constant => unreachable, // excluded from function bodies - .assembly => return self.genAsm(inst.cast(ir.Inst.Assembly).?, arch), + .isnonnull => return self.genIsNonNull(inst.cast(ir.Inst.IsNonNull).?, arch), + .isnull => return self.genIsNull(inst.cast(ir.Inst.IsNull).?, arch), .ptrtoint => return self.genPtrToInt(inst.cast(ir.Inst.PtrToInt).?), - .bitcast => return self.genBitCast(inst.cast(ir.Inst.BitCast).?), .ret => return self.genRet(inst.cast(ir.Inst.Ret).?, arch), .retvoid => return self.genRetVoid(inst.cast(ir.Inst.RetVoid).?, arch), - .cmp => return self.genCmp(inst.cast(ir.Inst.Cmp).?, arch), - .condbr => return self.genCondBr(inst.cast(ir.Inst.CondBr).?, arch), - .isnull => return self.genIsNull(inst.cast(ir.Inst.IsNull).?, arch), - .isnonnull => return self.genIsNonNull(inst.cast(ir.Inst.IsNonNull).?, arch), + .sub => return self.genSub(inst.cast(ir.Inst.Sub).?, arch), + .unreach => return MCValue{ .unreach = {} }, } } @@ -385,96 +414,136 @@ const Function = struct { return MCValue.dead; switch (arch) { .x86_64 => { - // Biggest encoding of ADD is 8 bytes. - try self.code.ensureCapacity(self.code.items.len + 8); + return try self.genX8664BinMath(&inst.base, inst.args.lhs, inst.args.rhs, 0, 0x00); + }, + else => return self.fail(inst.base.src, "TODO implement add for {}", .{self.target.cpu.arch}), + } + } - // In x86, ADD has 2 operands, destination and source. - // Either one, but not both, can be a memory operand. - // Source operand can be an immediate, 8 bits or 32 bits. - // So, if either one of the operands dies with this instruction, we can use it - // as the result MCValue. - var dst_mcv: MCValue = undefined; - var src_mcv: MCValue = undefined; - if (inst.base.operandDies(0)) { - // LHS dies; use it as the destination. - dst_mcv = try self.resolveInst(inst.args.lhs); - // Both operands cannot be memory. - if (dst_mcv.isMemory()) { - src_mcv = try self.resolveInstImmOrReg(inst.args.rhs); - } else { - src_mcv = try self.resolveInst(inst.args.rhs); - } - } else if (inst.base.operandDies(1)) { - // RHS dies; use it as the destination. - dst_mcv = try self.resolveInst(inst.args.rhs); - // Both operands cannot be memory. - if (dst_mcv.isMemory()) { - src_mcv = try self.resolveInstImmOrReg(inst.args.lhs); - } else { - src_mcv = try self.resolveInst(inst.args.lhs); - } - } else { - const lhs = try self.resolveInst(inst.args.lhs); - const rhs = try self.resolveInst(inst.args.rhs); - if (lhs.isMemory()) { - dst_mcv = try self.copyToNewRegister(inst.base.src, lhs); - src_mcv = rhs; - } else { - dst_mcv = try self.copyToNewRegister(inst.base.src, rhs); - src_mcv = lhs; - } - } - // x86 ADD supports only signed 32-bit immediates at most. If the immediate - // value is larger than this, we put it in a register. - // A potential opportunity for future optimization here would be keeping track - // of the fact that the instruction is available both as an immediate - // and as a register. - switch (src_mcv) { - .immediate => |imm| { - if (imm > std.math.maxInt(u31)) { - src_mcv = try self.copyToNewRegister(inst.base.src, src_mcv); - } - }, - else => {}, + fn genSub(self: *Function, inst: *ir.Inst.Sub, comptime arch: std.Target.Cpu.Arch) !MCValue { + // No side effects, so if it's unreferenced, do nothing. + if (inst.base.isUnused()) + return MCValue.dead; + switch (arch) { + .x86_64 => { + return try self.genX8664BinMath(&inst.base, inst.args.lhs, inst.args.rhs, 5, 0x28); + }, + else => return self.fail(inst.base.src, "TODO implement sub for {}", .{self.target.cpu.arch}), + } + } + + /// ADD, SUB + fn genX8664BinMath(self: *Function, inst: *ir.Inst, op_lhs: *ir.Inst, op_rhs: *ir.Inst, opx: u8, mr: u8) !MCValue { + try self.code.ensureCapacity(self.code.items.len + 8); + + const lhs = try self.resolveInst(op_lhs); + const rhs = try self.resolveInst(op_rhs); + + // There are 2 operands, destination and source. + // Either one, but not both, can be a memory operand. + // Source operand can be an immediate, 8 bits or 32 bits. + // So, if either one of the operands dies with this instruction, we can use it + // as the result MCValue. + var dst_mcv: MCValue = undefined; + var src_mcv: MCValue = undefined; + var src_inst: *ir.Inst = undefined; + if (inst.operandDies(0) and lhs.isMutable()) { + // LHS dies; use it as the destination. + // Both operands cannot be memory. + src_inst = op_rhs; + if (lhs.isMemory() and rhs.isMemory()) { + dst_mcv = try self.copyToNewRegister(op_lhs); + src_mcv = rhs; + } else { + dst_mcv = lhs; + src_mcv = rhs; + } + } else if (inst.operandDies(1) and rhs.isMutable()) { + // RHS dies; use it as the destination. + // Both operands cannot be memory. + src_inst = op_lhs; + if (lhs.isMemory() and rhs.isMemory()) { + dst_mcv = try self.copyToNewRegister(op_rhs); + src_mcv = lhs; + } else { + dst_mcv = rhs; + src_mcv = lhs; + } + } else { + if (lhs.isMemory()) { + dst_mcv = try self.copyToNewRegister(op_lhs); + src_mcv = rhs; + src_inst = op_rhs; + } else { + dst_mcv = try self.copyToNewRegister(op_rhs); + src_mcv = lhs; + src_inst = op_lhs; + } + } + // This instruction supports only signed 32-bit immediates at most. If the immediate + // value is larger than this, we put it in a register. + // A potential opportunity for future optimization here would be keeping track + // of the fact that the instruction is available both as an immediate + // and as a register. + switch (src_mcv) { + .immediate => |imm| { + if (imm > std.math.maxInt(u31)) { + src_mcv = try self.copyToNewRegister(src_inst); } + }, + else => {}, + } + + try self.genX8664BinMathCode(inst.src, dst_mcv, src_mcv, opx, mr); - switch (dst_mcv) { + return dst_mcv; + } + + fn genX8664BinMathCode(self: *Function, src: usize, dst_mcv: MCValue, src_mcv: MCValue, opx: u8, mr: u8) !void { + switch (dst_mcv) { + .none => unreachable, + .dead, .unreach, .immediate => unreachable, + .compare_flag => unreachable, + .register => |dst_reg_usize| { + const dst_reg = @intToEnum(Reg(.x86_64), @intCast(u8, dst_reg_usize)); + switch (src_mcv) { .none => unreachable, - .dead, .unreach, .immediate => unreachable, - .register => |dst_reg_usize| { - const dst_reg = @intToEnum(Reg(arch), @intCast(@TagType(Reg(arch)), dst_reg_usize)); - switch (src_mcv) { - .none => unreachable, - .dead, .unreach => unreachable, - .register => |src_reg_usize| { - const src_reg = @intToEnum(Reg(arch), @intCast(@TagType(Reg(arch)), src_reg_usize)); - self.rex(.{ .b = dst_reg.isExtended(), .r = src_reg.isExtended(), .w = dst_reg.size() == 64 }); - self.code.appendSliceAssumeCapacity(&[_]u8{ 0x1, 0xC0 | (@as(u8, src_reg.id() & 0b111) << 3) | @as(u8, dst_reg.id() & 0b111) }); - }, - .immediate => |imm| { - const imm32 = @intCast(u31, imm); // We handle this case above. - // 81 /0 id - if (imm32 <= std.math.maxInt(u7)) { - self.rex(.{ .b = dst_reg.isExtended(), .w = dst_reg.size() == 64 }); - self.code.appendSliceAssumeCapacity(&[_]u8{ 0x83, 0xC0 | @as(u8, dst_reg.id() & 0b111), @intCast(u8, imm32)}); - } else { - self.rex(.{ .r = dst_reg.isExtended(), .w = dst_reg.size() == 64 }); - self.code.appendSliceAssumeCapacity(&[_]u8{ 0x81, 0xC0 | @as(u8, dst_reg.id() & 0b111) }); - std.mem.writeIntLittle(u32, self.code.addManyAsArrayAssumeCapacity(4), imm32); - } - }, - .embedded_in_code, .memory, .stack_offset => { - return self.fail(inst.base.src, "TODO implement x86 add source memory", .{}); - }, + .dead, .unreach => unreachable, + .register => |src_reg_usize| { + const src_reg = @intToEnum(Reg(.x86_64), @intCast(u8, src_reg_usize)); + self.rex(.{ .b = dst_reg.isExtended(), .r = src_reg.isExtended(), .w = dst_reg.size() == 64 }); + self.code.appendSliceAssumeCapacity(&[_]u8{ mr + 0x1, 0xC0 | (@as(u8, src_reg.id() & 0b111) << 3) | @as(u8, dst_reg.id() & 0b111) }); + }, + .immediate => |imm| { + const imm32 = @intCast(u31, imm); // This case must be handled before calling genX8664BinMathCode. + // 81 /opx id + if (imm32 <= std.math.maxInt(u7)) { + self.rex(.{ .b = dst_reg.isExtended(), .w = dst_reg.size() == 64 }); + self.code.appendSliceAssumeCapacity(&[_]u8{ + 0x83, + 0xC0 | (opx << 3) | @truncate(u3, dst_reg.id()), + @intCast(u8, imm32), + }); + } else { + self.rex(.{ .r = dst_reg.isExtended(), .w = dst_reg.size() == 64 }); + self.code.appendSliceAssumeCapacity(&[_]u8{ + 0x81, + 0xC0 | (opx << 3) | @truncate(u3, dst_reg.id()), + }); + std.mem.writeIntLittle(u32, self.code.addManyAsArrayAssumeCapacity(4), imm32); } }, .embedded_in_code, .memory, .stack_offset => { - return self.fail(inst.base.src, "TODO implement x86 add destination memory", .{}); + return self.fail(src, "TODO implement x86 ADD/SUB/CMP source memory", .{}); + }, + .compare_flag => { + return self.fail(src, "TODO implement x86 ADD/SUB/CMP source compare flag", .{}); }, } - return dst_mcv; }, - else => return self.fail(inst.base.src, "TODO implement add for {}", .{self.target.cpu.arch}), + .embedded_in_code, .memory, .stack_offset => { + return self.fail(src, "TODO implement x86 ADD/SUB/CMP destination memory", .{}); + }, } } @@ -550,7 +619,29 @@ const Function = struct { } fn genCmp(self: *Function, inst: *ir.Inst.Cmp, comptime arch: std.Target.Cpu.Arch) !MCValue { + // No side effects, so if it's unreferenced, do nothing. + if (inst.base.isUnused()) + return MCValue.dead; switch (arch) { + .x86_64 => { + try self.code.ensureCapacity(self.code.items.len + 8); + + const lhs = try self.resolveInst(inst.args.lhs); + const rhs = try self.resolveInst(inst.args.rhs); + + // There are 2 operands, destination and source. + // Either one, but not both, can be a memory operand. + // Source operand can be an immediate, 8 bits or 32 bits. + const dst_mcv = if (lhs.isImmediate() or (lhs.isMemory() and rhs.isMemory())) + try self.copyToNewRegister(inst.args.lhs) + else + lhs; + // This instruction supports only signed 32-bit immediates at most. + const src_mcv = try self.limitImmediateType(inst.args.rhs, i32); + + try self.genX8664BinMathCode(inst.base.src, dst_mcv, src_mcv, 7, 0x38); + return MCValue{.compare_flag = inst.args.op}; + }, else => return self.fail(inst.base.src, "TODO implement cmp for {}", .{self.target.cpu.arch}), } } @@ -668,6 +759,9 @@ const Function = struct { .dead => unreachable, .none => unreachable, .unreach => unreachable, + .compare_flag => |op| { + return self.fail(src, "TODO set register with compare flag value", .{}); + }, .immediate => |x| { if (reg.size() != 64) { return self.fail(src, "TODO decide whether to implement non-64-bit loads", .{}); @@ -871,14 +965,35 @@ const Function = struct { } } - fn resolveInstImmOrReg(self: *Function, inst: *ir.Inst) !MCValue { - return self.fail(inst.src, "TODO implement resolveInstImmOrReg", .{}); + fn copyToNewRegister(self: *Function, inst: *ir.Inst) !MCValue { + return self.fail(inst.src, "TODO implement copyToNewRegister", .{}); } - fn copyToNewRegister(self: *Function, src: usize, mcv: MCValue) !MCValue { - return self.fail(src, "TODO implement copyToNewRegister", .{}); + /// If the MCValue is an immediate, and it does not fit within this type, + /// we put it in a register. + /// A potential opportunity for future optimization here would be keeping track + /// of the fact that the instruction is available both as an immediate + /// and as a register. + fn limitImmediateType(self: *Function, inst: *ir.Inst, comptime T: type) !MCValue { + const mcv = try self.resolveInst(inst); + const ti = @typeInfo(T).Int; + switch (mcv) { + .immediate => |imm| { + // This immediate is unsigned. + const U = @Type(.{ .Int = .{ + .bits = ti.bits - @boolToInt(ti.is_signed), + .is_signed = false, + }}); + if (imm >= std.math.maxInt(U)) { + return self.copyToNewRegister(inst); + } + }, + else => {}, + } + return mcv; } + fn genTypedValue(self: *Function, src: usize, typed_value: TypedValue) !MCValue { const ptr_bits = self.target.cpu.arch.ptrBitWidth(); const ptr_bytes: u64 = @divExact(ptr_bits, 8); diff --git a/src-self-hosted/ir.zig b/src-self-hosted/ir.zig index 17e6a54725..c8acc14545 100644 --- a/src-self-hosted/ir.zig +++ b/src-self-hosted/ir.zig @@ -51,6 +51,7 @@ pub const Inst = struct { ptrtoint, ret, retvoid, + sub, unreach, /// Returns whether the instruction is one of the control flow "noreturn" types. @@ -64,12 +65,13 @@ pub const Inst = struct { .bitcast, .block, .breakpoint, + .call, .cmp, .constant, .isnonnull, .isnull, .ptrtoint, - .call, + .sub, => false, .condbr, @@ -242,6 +244,16 @@ pub const Inst = struct { args: void, }; + pub const Sub = struct { + pub const base_tag = Tag.sub; + base: Inst, + + args: struct { + lhs: *Inst, + rhs: *Inst, + }, + }; + pub const Unreach = struct { pub const base_tag = Tag.unreach; base: Inst, diff --git a/src-self-hosted/zir.zig b/src-self-hosted/zir.zig index 95548657a9..628773e09c 100644 --- a/src-self-hosted/zir.zig +++ b/src-self-hosted/zir.zig @@ -73,6 +73,7 @@ pub const Inst = struct { bitcast, elemptr, add, + sub, cmp, condbr, isnull, @@ -110,6 +111,7 @@ pub const Inst = struct { .bitcast => BitCast, .elemptr => ElemPtr, .add => Add, + .sub => Sub, .cmp => Cmp, .condbr => CondBr, .isnull => IsNull, @@ -512,6 +514,17 @@ pub const Inst = struct { kw_args: struct {}, }; + pub const Sub = struct { + pub const base_tag = Tag.sub; + base: Inst, + + positionals: struct { + lhs: *Inst, + rhs: *Inst, + }, + kw_args: struct {}, + }; + pub const Cmp = struct { pub const base_tag = Tag.cmp; base: Inst, @@ -677,6 +690,7 @@ pub const Module = struct { .bitcast => return self.writeInstToStreamGeneric(stream, .bitcast, inst, inst_table), .elemptr => return self.writeInstToStreamGeneric(stream, .elemptr, inst, inst_table), .add => return self.writeInstToStreamGeneric(stream, .add, inst, inst_table), + .sub => return self.writeInstToStreamGeneric(stream, .sub, inst, inst_table), .cmp => return self.writeInstToStreamGeneric(stream, .cmp, inst, inst_table), .condbr => return self.writeInstToStreamGeneric(stream, .condbr, inst, inst_table), .isnull => return self.writeInstToStreamGeneric(stream, .isnull, inst, inst_table), @@ -1542,6 +1556,22 @@ const EmitZIR = struct { }; break :blk &new_inst.base; }, + .sub => blk: { + const old_inst = inst.cast(ir.Inst.Sub).?; + const new_inst = try self.arena.allocator.create(Inst.Sub); + new_inst.* = .{ + .base = .{ + .src = inst.src, + .tag = Inst.Sub.base_tag, + }, + .positionals = .{ + .lhs = try self.resolveInst(new_body, old_inst.args.lhs), + .rhs = try self.resolveInst(new_body, old_inst.args.rhs), + }, + .kw_args = .{}, + }; + break :blk &new_inst.base; + }, .arg => blk: { const old_inst = inst.cast(ir.Inst.Arg).?; const new_inst = try self.arena.allocator.create(Inst.Arg); -- cgit v1.2.3 From 4d01385e147ae36ad96a1c28d2b6fdec69ce69c9 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Tue, 7 Jul 2020 03:48:20 +0000 Subject: fix liveness analysis and not correctly propagating link errors We still flush the ELF file even when there are compile errors. --- src-self-hosted/Module.zig | 12 +++++++----- src-self-hosted/link.zig | 23 ++++++++++++----------- src-self-hosted/liveness.zig | 29 +++++++++++++++++------------ src-self-hosted/main.zig | 5 ++++- 4 files changed, 40 insertions(+), 29 deletions(-) (limited to 'src-self-hosted/Module.zig') diff --git a/src-self-hosted/Module.zig b/src-self-hosted/Module.zig index 776e63018b..6cd64e9235 100644 --- a/src-self-hosted/Module.zig +++ b/src-self-hosted/Module.zig @@ -867,15 +867,16 @@ pub fn update(self: *Module) !void { try self.deleteDecl(decl); } + // This is needed before reading the error flags. + try self.bin_file.flush(); + self.link_error_flags = self.bin_file.error_flags; + std.log.debug(.module, "link_error_flags: {}\n", .{self.link_error_flags}); // If there are any errors, we anticipate the source files being loaded // to report error messages. Otherwise we unload all source files to save memory. - if (self.totalErrorCount() == 0) { - if (!self.keep_source_files_loaded) { - self.root_scope.unload(self.gpa); - } - try self.bin_file.flush(); + if (self.totalErrorCount() == 0 and !self.keep_source_files_loaded) { + self.root_scope.unload(self.gpa); } } @@ -975,6 +976,7 @@ pub fn performAllTheWork(self: *Module) error{OutOfMemory}!void { // lifetime annotations in the ZIR. var decl_arena = decl.typed_value.most_recent.arena.?.promote(self.gpa); defer decl.typed_value.most_recent.arena.?.* = decl_arena.state; + std.log.debug(.module, "analyze liveness of {}\n", .{decl.name}); try liveness.analyze(self.gpa, &decl_arena.allocator, payload.func.analysis.success); } diff --git a/src-self-hosted/link.zig b/src-self-hosted/link.zig index a0894fb1a1..c297c3a1ce 100644 --- a/src-self-hosted/link.zig +++ b/src-self-hosted/link.zig @@ -369,7 +369,7 @@ pub const ElfFile = struct { const file_size = self.options.program_code_size_hint; const p_align = 0x1000; const off = self.findFreeSpace(file_size, p_align); - //std.log.debug(.link, "found PT_LOAD free space 0x{x} to 0x{x}\n", .{ off, off + file_size }); + std.log.debug(.link, "found PT_LOAD free space 0x{x} to 0x{x}\n", .{ off, off + file_size }); try self.program_headers.append(self.allocator, .{ .p_type = elf.PT_LOAD, .p_offset = off, @@ -390,7 +390,7 @@ pub const ElfFile = struct { // page align. const p_align = 0x1000; const off = self.findFreeSpace(file_size, p_align); - //std.log.debug(.link, "found PT_LOAD free space 0x{x} to 0x{x}\n", .{ off, off + file_size }); + std.log.debug(.link, "found PT_LOAD free space 0x{x} to 0x{x}\n", .{ off, off + file_size }); // TODO instead of hard coding the vaddr, make a function to find a vaddr to put things at. // we'll need to re-use that function anyway, in case the GOT grows and overlaps something // else in virtual memory. @@ -412,7 +412,7 @@ pub const ElfFile = struct { assert(self.shstrtab.items.len == 0); try self.shstrtab.append(self.allocator, 0); // need a 0 at position 0 const off = self.findFreeSpace(self.shstrtab.items.len, 1); - //std.log.debug(.link, "found shstrtab free space 0x{x} to 0x{x}\n", .{ off, off + self.shstrtab.items.len }); + std.log.debug(.link, "found shstrtab free space 0x{x} to 0x{x}\n", .{ off, off + self.shstrtab.items.len }); try self.sections.append(self.allocator, .{ .sh_name = try self.makeString(".shstrtab"), .sh_type = elf.SHT_STRTAB, @@ -470,7 +470,7 @@ pub const ElfFile = struct { const each_size: u64 = if (small_ptr) @sizeOf(elf.Elf32_Sym) else @sizeOf(elf.Elf64_Sym); const file_size = self.options.symbol_count_hint * each_size; const off = self.findFreeSpace(file_size, min_align); - //std.log.debug(.link, "found symtab free space 0x{x} to 0x{x}\n", .{ off, off + file_size }); + std.log.debug(.link, "found symtab free space 0x{x} to 0x{x}\n", .{ off, off + file_size }); try self.sections.append(self.allocator, .{ .sh_name = try self.makeString(".symtab"), @@ -586,7 +586,7 @@ pub const ElfFile = struct { shstrtab_sect.sh_offset = self.findFreeSpace(needed_size, 1); } shstrtab_sect.sh_size = needed_size; - //std.log.debug(.link, "shstrtab start=0x{x} end=0x{x}\n", .{ shstrtab_sect.sh_offset, shstrtab_sect.sh_offset + needed_size }); + std.log.debug(.link, "shstrtab start=0x{x} end=0x{x}\n", .{ shstrtab_sect.sh_offset, shstrtab_sect.sh_offset + needed_size }); try self.file.?.pwriteAll(self.shstrtab.items, shstrtab_sect.sh_offset); if (!self.shdr_table_dirty) { @@ -632,7 +632,7 @@ pub const ElfFile = struct { for (buf) |*shdr, i| { shdr.* = self.sections.items[i]; - //std.log.debug(.link, "writing section {}\n", .{shdr.*}); + std.log.debug(.link, "writing section {}\n", .{shdr.*}); if (foreign_endian) { bswapAllFields(elf.Elf64_Shdr, shdr); } @@ -643,6 +643,7 @@ pub const ElfFile = struct { self.shdr_table_dirty = false; } if (self.entry_addr == null and self.options.output_mode == .Exe) { + std.log.debug(.link, "no_entry_point_found = true\n", .{}); self.error_flags.no_entry_point_found = true; } else { self.error_flags.no_entry_point_found = false; @@ -956,10 +957,10 @@ pub const ElfFile = struct { try self.offset_table_free_list.ensureCapacity(self.allocator, self.local_symbols.items.len); if (self.local_symbol_free_list.popOrNull()) |i| { - //std.log.debug(.link, "reusing symbol index {} for {}\n", .{i, decl.name}); + std.log.debug(.link, "reusing symbol index {} for {}\n", .{i, decl.name}); decl.link.local_sym_index = i; } else { - //std.log.debug(.link, "allocating symbol index {} for {}\n", .{self.local_symbols.items.len, decl.name}); + std.log.debug(.link, "allocating symbol index {} for {}\n", .{self.local_symbols.items.len, decl.name}); decl.link.local_sym_index = @intCast(u32, self.local_symbols.items.len); _ = self.local_symbols.addOneAssumeCapacity(); } @@ -1027,11 +1028,11 @@ pub const ElfFile = struct { !mem.isAlignedGeneric(u64, local_sym.st_value, required_alignment); if (need_realloc) { const vaddr = try self.growTextBlock(&decl.link, code.len, required_alignment); - //std.log.debug(.link, "growing {} from 0x{x} to 0x{x}\n", .{ decl.name, local_sym.st_value, vaddr }); + std.log.debug(.link, "growing {} from 0x{x} to 0x{x}\n", .{ decl.name, local_sym.st_value, vaddr }); if (vaddr != local_sym.st_value) { local_sym.st_value = vaddr; - //std.log.debug(.link, " (writing new offset table entry)\n", .{}); + std.log.debug(.link, " (writing new offset table entry)\n", .{}); self.offset_table.items[decl.link.offset_table_index] = vaddr; try self.writeOffsetTableEntry(decl.link.offset_table_index); } @@ -1049,7 +1050,7 @@ pub const ElfFile = struct { const decl_name = mem.spanZ(decl.name); const name_str_index = try self.makeString(decl_name); const vaddr = try self.allocateTextBlock(&decl.link, code.len, required_alignment); - //std.log.debug(.link, "allocated text block for {} at 0x{x}\n", .{ decl_name, vaddr }); + std.log.debug(.link, "allocated text block for {} at 0x{x}\n", .{ decl_name, vaddr }); errdefer self.freeTextBlock(&decl.link); local_sym.* = .{ diff --git a/src-self-hosted/liveness.zig b/src-self-hosted/liveness.zig index 2e0aad49c3..28eb2145c7 100644 --- a/src-self-hosted/liveness.zig +++ b/src-self-hosted/liveness.zig @@ -25,22 +25,25 @@ fn analyzeWithTable(arena: *std.mem.Allocator, table: *std.AutoHashMap(*ir.Inst, while (i != 0) { i -= 1; const base = body.instructions[i]; + try analyzeInstGeneric(arena, table, base); + } +} - // Obtain the corresponding instruction type based on the tag type. - inline for (std.meta.declarations(ir.Inst)) |decl| { - switch (decl.data) { - .Type => |T| { - if (@hasDecl(T, "base_tag")) { - if (T.base_tag == base.tag) { - return analyzeInst(arena, table, T, @fieldParentPtr(T, "base", base)); - } +fn analyzeInstGeneric(arena: *std.mem.Allocator, table: *std.AutoHashMap(*ir.Inst, void), base: *ir.Inst) error{OutOfMemory}!void { + // Obtain the corresponding instruction type based on the tag type. + inline for (std.meta.declarations(ir.Inst)) |decl| { + switch (decl.data) { + .Type => |T| { + if (@hasDecl(T, "base_tag")) { + if (T.base_tag == base.tag) { + return analyzeInst(arena, table, T, @fieldParentPtr(T, "base", base)); } - }, - else => continue, - } + } + }, + else => {}, } - unreachable; } + unreachable; } fn analyzeInst(arena: *std.mem.Allocator, table: *std.AutoHashMap(*ir.Inst, void), comptime T: type, inst: *T) error{OutOfMemory}!void { @@ -131,4 +134,6 @@ fn analyzeInst(arena: *std.mem.Allocator, table: *std.AutoHashMap(*ir.Inst, void arg_index += 1; } } + + std.log.debug(.liveness, "analyze {}: 0b{b}\n", .{inst.base.tag, inst.base.deaths}); } diff --git a/src-self-hosted/main.zig b/src-self-hosted/main.zig index 82edcc4eff..7a47fc5f78 100644 --- a/src-self-hosted/main.zig +++ b/src-self-hosted/main.zig @@ -50,7 +50,10 @@ pub fn log( const scope_prefix = "(" ++ switch (scope) { // Uncomment to hide logs //.compiler, - .link => return, + .module, + .liveness, + .link, + => return, else => @tagName(scope), } ++ "): "; -- cgit v1.2.3 From b55d0193e41311532e7b3603b9386863626afcd2 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Tue, 7 Jul 2020 08:01:54 +0000 Subject: stage2: progress towards Block and CondBr codegen --- src-self-hosted/Module.zig | 19 ++++++------------- src-self-hosted/codegen.zig | 21 +++++++++++++++++++-- src-self-hosted/ir.zig | 14 ++++++++++++++ src-self-hosted/zir.zig | 16 ++++++++++++++++ 4 files changed, 55 insertions(+), 15 deletions(-) (limited to 'src-self-hosted/Module.zig') diff --git a/src-self-hosted/Module.zig b/src-self-hosted/Module.zig index 6cd64e9235..d40afebb64 100644 --- a/src-self-hosted/Module.zig +++ b/src-self-hosted/Module.zig @@ -2545,18 +2545,6 @@ fn analyzeInstBlock(self: *Module, scope: *Scope, inst: *zir.Inst.Block) InnerEr assert(child_block.instructions.items.len != 0); assert(child_block.instructions.items[child_block.instructions.items.len - 1].tag.isNoReturn()); - if (label.results.items.len <= 1) { - // No need to add the Block instruction; we can add the instructions to the parent block directly. - // Blocks are terminated with a noreturn instruction which we do not want to include. - const instrs = child_block.instructions.items; - try parent_block.instructions.appendSlice(self.gpa, instrs[0 .. instrs.len - 1]); - if (label.results.items.len == 1) { - return label.results.items[0]; - } else { - return self.constNoReturn(scope, inst.base.src); - } - } - // Need to set the type and emit the Block instruction. This allows machine code generation // to emit a jump instruction to after the block when it encounters the break. try parent_block.instructions.append(self.gpa, &block_inst.base); @@ -2579,7 +2567,10 @@ fn analyzeInstBreakVoid(self: *Module, scope: *Scope, inst: *zir.Inst.BreakVoid) if (block.label) |*label| { if (mem.eql(u8, label.name, label_name)) { try label.results.append(self.gpa, void_inst); - return self.constNoReturn(scope, inst.base.src); + const b = try self.requireRuntimeBlock(scope, inst.base.src); + return self.addNewInstArgs(b, inst.base.src, Type.initTag(.noreturn), Inst.BreakVoid, .{ + .block = label.block_inst, + }); } } opt_block = block.parent; @@ -3366,6 +3357,8 @@ fn makeIntType(self: *Module, scope: *Scope, signed: bool, bits: u16) !Type { fn resolvePeerTypes(self: *Module, scope: *Scope, instructions: []*Inst) !Type { if (instructions.len == 0) return Type.initTag(.noreturn); + if (instructions.len == 1) + return instructions[0].ty; return self.fail(scope, instructions[0].src, "TODO peer type resolution", .{}); } diff --git a/src-self-hosted/codegen.zig b/src-self-hosted/codegen.zig index aac1a53d6a..d1b32f4ed4 100644 --- a/src-self-hosted/codegen.zig +++ b/src-self-hosted/codegen.zig @@ -218,6 +218,11 @@ pub fn generateSymbol( } } +const InnerError = error { + OutOfMemory, + CodegenFail, +}; + const Function = struct { gpa: *Allocator, bin_file: *link.ElfFile, @@ -379,8 +384,12 @@ const Function = struct { } fn genArch(self: *Function, comptime arch: std.Target.Cpu.Arch) !void { + return self.genBody(self.mod_fn.analysis.success, arch); + } + + fn genBody(self: *Function, body: ir.Body, comptime arch: std.Target.Cpu.Arch) InnerError!void { const inst_table = &self.branch_stack.items[0].inst_table; - for (self.mod_fn.analysis.success.instructions) |inst| { + for (body.instructions) |inst| { const new_inst = try self.genFuncInst(inst, arch); try inst_table.putNoClobber(self.gpa, inst, new_inst); } @@ -394,6 +403,7 @@ const Function = struct { .bitcast => return self.genBitCast(inst.cast(ir.Inst.BitCast).?), .block => return self.genBlock(inst.cast(ir.Inst.Block).?, arch), .breakpoint => return self.genBreakpoint(inst.src, arch), + .breakvoid => return self.genBreakVoid(inst.cast(ir.Inst.BreakVoid).?, arch), .call => return self.genCall(inst.cast(ir.Inst.Call).?, arch), .cmp => return self.genCmp(inst.cast(ir.Inst.Cmp).?, arch), .condbr => return self.genCondBr(inst.cast(ir.Inst.CondBr).?, arch), @@ -686,9 +696,16 @@ const Function = struct { } fn genBlock(self: *Function, inst: *ir.Inst.Block, comptime arch: std.Target.Cpu.Arch) !MCValue { + // A block is nothing but a setup to be able to jump to the end. + try self.genBody(inst.args.body, arch); + return self.fail(inst.base.src, "TODO process jump relocs after block end", .{}); + } + + fn genBreakVoid(self: *Function, inst: *ir.Inst.BreakVoid, comptime arch: std.Target.Cpu.Arch) !MCValue { switch (arch) { - else => return self.fail(inst.base.src, "TODO implement codegen Block for {}", .{self.target.cpu.arch}), + else => return self.fail(inst.base.src, "TODO implement breakvoid for {}", .{self.target.cpu.arch}), } + return .none; } fn genAsm(self: *Function, inst: *ir.Inst.Assembly, comptime arch: Target.Cpu.Arch) !MCValue { diff --git a/src-self-hosted/ir.zig b/src-self-hosted/ir.zig index c8acc14545..81b617c8a2 100644 --- a/src-self-hosted/ir.zig +++ b/src-self-hosted/ir.zig @@ -35,6 +35,10 @@ pub const Inst = struct { return @truncate(u1, self.deaths << index) != 0; } + pub fn specialOperandDeaths(self: Inst) bool { + return (self.deaths & 0b1000_0000) != 0; + } + pub const Tag = enum { add, arg, @@ -42,6 +46,7 @@ pub const Inst = struct { bitcast, block, breakpoint, + breakvoid, call, cmp, condbr, @@ -74,6 +79,7 @@ pub const Inst = struct { .sub, => false, + .breakvoid, .condbr, .ret, .retvoid, @@ -159,6 +165,14 @@ pub const Inst = struct { args: void, }; + pub const BreakVoid = struct { + pub const base_tag = Tag.breakvoid; + base: Inst, + args: struct { + block: *Block, + }, + }; + pub const Call = struct { pub const base_tag = Tag.call; base: Inst, diff --git a/src-self-hosted/zir.zig b/src-self-hosted/zir.zig index 628773e09c..8cc6cdaf05 100644 --- a/src-self-hosted/zir.zig +++ b/src-self-hosted/zir.zig @@ -1608,6 +1608,22 @@ const EmitZIR = struct { break :blk &new_inst.base; }, .breakpoint => try self.emitTrivial(inst.src, Inst.Breakpoint), + .breakvoid => blk: { + const old_inst = inst.cast(ir.Inst.BreakVoid).?; + const new_block = inst_table.get(&old_inst.args.block.base).?; + const new_inst = try self.arena.allocator.create(Inst.BreakVoid); + new_inst.* = .{ + .base = .{ + .src = inst.src, + .tag = Inst.BreakVoid.base_tag, + }, + .positionals = .{ + .label = new_block.cast(Inst.Block).?.positionals.label, + }, + .kw_args = .{}, + }; + break :blk &new_inst.base; + }, .call => blk: { const old_inst = inst.cast(ir.Inst.Call).?; const new_inst = try self.arena.allocator.create(Inst.Call); -- cgit v1.2.3 From 5e60872060da894c38343f2afc1ddc45bce14fc6 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Wed, 8 Jul 2020 06:56:20 +0000 Subject: stage2 misc fixes --- src-self-hosted/Module.zig | 13 ++++++++++--- src-self-hosted/codegen.zig | 33 +++++++++++++++++++++++---------- src-self-hosted/zir.zig | 34 ++++++++++++++++++++++++++++++++++ 3 files changed, 67 insertions(+), 13 deletions(-) (limited to 'src-self-hosted/Module.zig') diff --git a/src-self-hosted/Module.zig b/src-self-hosted/Module.zig index d40afebb64..0bd917b2b1 100644 --- a/src-self-hosted/Module.zig +++ b/src-self-hosted/Module.zig @@ -867,8 +867,10 @@ pub fn update(self: *Module) !void { try self.deleteDecl(decl); } - // This is needed before reading the error flags. - try self.bin_file.flush(); + if (self.totalErrorCount() == 0) { + // This is needed before reading the error flags. + try self.bin_file.flush(); + } self.link_error_flags = self.bin_file.error_flags; std.log.debug(.module, "link_error_flags: {}\n", .{self.link_error_flags}); @@ -2388,6 +2390,7 @@ fn analyzeInst(self: *Module, scope: *Scope, old_inst: *zir.Inst) InnerError!*In const big_int = old_inst.cast(zir.Inst.Int).?.positionals.int; return self.constIntBig(scope, old_inst.src, Type.initTag(.comptime_int), big_int); }, + .inttype => return self.analyzeInstIntType(scope, old_inst.cast(zir.Inst.IntType).?), .ptrtoint => return self.analyzeInstPtrToInt(scope, old_inst.cast(zir.Inst.PtrToInt).?), .fieldptr => return self.analyzeInstFieldPtr(scope, old_inst.cast(zir.Inst.FieldPtr).?), .deref => return self.analyzeInstDeref(scope, old_inst.cast(zir.Inst.Deref).?), @@ -2737,6 +2740,10 @@ fn analyzeInstFn(self: *Module, scope: *Scope, fn_inst: *zir.Inst.Fn) InnerError }); } +fn analyzeInstIntType(self: *Module, scope: *Scope, inttype: *zir.Inst.IntType) InnerError!*Inst { + return self.fail(scope, inttype.base.src, "TODO implement inttype", .{}); +} + fn analyzeInstFnType(self: *Module, scope: *Scope, fntype: *zir.Inst.FnType) InnerError!*Inst { const return_type = try self.resolveType(scope, fntype.positionals.return_type); @@ -3333,7 +3340,7 @@ fn cmpNumeric( break :blk try self.makeIntType(scope, dest_int_is_signed, casted_bits); }; const casted_lhs = try self.coerce(scope, dest_type, lhs); - const casted_rhs = try self.coerce(scope, dest_type, lhs); + const casted_rhs = try self.coerce(scope, dest_type, rhs); return self.addNewInstArgs(b, src, Type.initTag(.bool), Inst.Cmp, .{ .lhs = casted_lhs, diff --git a/src-self-hosted/codegen.zig b/src-self-hosted/codegen.zig index b3fa94f088..232703b697 100644 --- a/src-self-hosted/codegen.zig +++ b/src-self-hosted/codegen.zig @@ -698,18 +698,34 @@ const Function = struct { .lte => 0x8f, .eq => 0x85, }; - self.code.appendSliceAssumeCapacity(&[_]u8{0x0f, opcode}); - const reloc = Reloc{ .rel32 = self.code.items.len }; - self.code.items.len += 4; - try self.genBody(inst.args.true_body, arch); - try self.performReloc(inst.base.src, reloc); - try self.genBody(inst.args.false_body, arch); + return self.genX86CondBr(inst, opcode, arch); + }, + .compare_flags_unsigned => |cmp_op| { + // Here we map to the opposite opcode because the jump is to the false branch. + const opcode: u8 = switch (cmp_op) { + .gte => 0x82, + .gt => 0x86, + .neq => 0x84, + .lt => 0x83, + .lte => 0x87, + .eq => 0x85, + }; + return self.genX86CondBr(inst, opcode, arch); }, else => return self.fail(inst.base.src, "TODO implement condbr {} when condition not already in the compare flags", .{self.target.cpu.arch}), } }, else => return self.fail(inst.base.src, "TODO implement condbr for {}", .{self.target.cpu.arch}), } + } + + fn genX86CondBr(self: *Function, inst: *ir.Inst.CondBr, opcode: u8, comptime arch: std.Target.Cpu.Arch) !MCValue { + self.code.appendSliceAssumeCapacity(&[_]u8{0x0f, opcode}); + const reloc = Reloc{ .rel32 = self.code.items.len }; + self.code.items.len += 4; + try self.genBody(inst.args.true_body, arch); + try self.performReloc(inst.base.src, reloc); + try self.genBody(inst.args.false_body, arch); return MCValue.unreach; } @@ -1028,10 +1044,7 @@ const Function = struct { const branch = &self.branch_stack.items[0]; const gop = try branch.inst_table.getOrPut(self.gpa, inst); if (!gop.found_existing) { - const mcv = try self.genTypedValue(inst.src, .{ .ty = inst.ty, .val = const_inst.val }); - try branch.inst_table.putNoClobber(self.gpa, inst, mcv); - gop.entry.value = mcv; - return mcv; + gop.entry.value = try self.genTypedValue(inst.src, .{ .ty = inst.ty, .val = const_inst.val }); } return gop.entry.value; } diff --git a/src-self-hosted/zir.zig b/src-self-hosted/zir.zig index 697c7673ac..ab48bf535f 100644 --- a/src-self-hosted/zir.zig +++ b/src-self-hosted/zir.zig @@ -57,6 +57,7 @@ pub const Inst = struct { /// String Literal. Makes an anonymous Decl and then takes a pointer to it. str, int, + inttype, ptrtoint, fieldptr, deref, @@ -95,6 +96,7 @@ pub const Inst = struct { .@"const" => Const, .str => Str, .int => Int, + .inttype => IntType, .ptrtoint => PtrToInt, .fieldptr => FieldPtr, .deref => Deref, @@ -369,6 +371,17 @@ pub const Inst = struct { }, }; + pub const IntType = struct { + pub const base_tag = Tag.inttype; + base: Inst, + + positionals: struct { + signed: *Inst, + bits: *Inst, + }, + kw_args: struct {}, + }; + pub const Export = struct { pub const base_tag = Tag.@"export"; base: Inst, @@ -675,6 +688,7 @@ pub const Module = struct { .@"const" => return self.writeInstToStreamGeneric(stream, .@"const", inst, inst_table, indent), .str => return self.writeInstToStreamGeneric(stream, .str, inst, inst_table, indent), .int => return self.writeInstToStreamGeneric(stream, .int, inst, inst_table, indent), + .inttype => return self.writeInstToStreamGeneric(stream, .inttype, inst, inst_table, indent), .ptrtoint => return self.writeInstToStreamGeneric(stream, .ptrtoint, inst, inst_table, indent), .fieldptr => return self.writeInstToStreamGeneric(stream, .fieldptr, inst, inst_table, indent), .deref => return self.writeInstToStreamGeneric(stream, .deref, inst, inst_table, indent), @@ -1886,6 +1900,26 @@ const EmitZIR = struct { }; return self.emitUnnamedDecl(&fntype_inst.base); }, + .Int => { + const info = ty.intInfo(self.old_module.target()); + const signed = try self.emitPrimitive(src, if (info.signed) .@"true" else .@"false"); + const bits_payload = try self.arena.allocator.create(Value.Payload.Int_u64); + bits_payload.* = .{ .int = info.bits }; + const bits = try self.emitComptimeIntVal(src, Value.initPayload(&bits_payload.base)); + const inttype_inst = try self.arena.allocator.create(Inst.IntType); + inttype_inst.* = .{ + .base = .{ + .src = src, + .tag = Inst.IntType.base_tag, + }, + .positionals = .{ + .signed = signed.inst, + .bits = bits.inst, + }, + .kw_args = .{}, + }; + return self.emitUnnamedDecl(&inttype_inst.base); + }, else => std.debug.panic("TODO implement emitType for {}", .{ty}), }, } -- cgit v1.2.3 From be0546d877e0df18201e73e803d8a966b57625c5 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Wed, 8 Jul 2020 07:04:43 +0000 Subject: stage2: implement compare operator AST->ZIR --- src-self-hosted/Module.zig | 27 +++++++++++++++++++++++++++ src-self-hosted/zir.zig | 2 ++ 2 files changed, 29 insertions(+) (limited to 'src-self-hosted/Module.zig') diff --git a/src-self-hosted/Module.zig b/src-self-hosted/Module.zig index 0bd917b2b1..67c1b00a1e 100644 --- a/src-self-hosted/Module.zig +++ b/src-self-hosted/Module.zig @@ -1309,6 +1309,33 @@ fn astGenInfixOp(self: *Module, scope: *Scope, infix_node: *ast.Node.InfixOp) In return self.addZIRInst(scope, src, zir.Inst.Add, .{ .lhs = lhs, .rhs = rhs }, .{}); }, + .BangEqual, + .EqualEqual, + .GreaterThan, + .GreaterOrEqual, + .LessThan, + .LessOrEqual, + => { + const lhs = try self.astGenExpr(scope, infix_node.lhs); + const rhs = try self.astGenExpr(scope, infix_node.rhs); + + const tree = scope.tree(); + const src = tree.token_locs[infix_node.op_token].start; + + return self.addZIRInst(scope, src, zir.Inst.Cmp, .{ + .lhs = lhs, + .op = @as(std.math.CompareOperator, switch (infix_node.op) { + .BangEqual => .neq, + .EqualEqual => .eq, + .GreaterThan => .gt, + .GreaterOrEqual => .gte, + .LessThan => .lt, + .LessOrEqual => .lte, + else => unreachable, + }), + .rhs = rhs, + }, .{}); + }, else => |op| { return self.failNode(scope, &infix_node.base, "TODO implement infix operator {}", .{op}); }, diff --git a/src-self-hosted/zir.zig b/src-self-hosted/zir.zig index ab48bf535f..0221e4d330 100644 --- a/src-self-hosted/zir.zig +++ b/src-self-hosted/zir.zig @@ -538,6 +538,8 @@ pub const Inst = struct { kw_args: struct {}, }; + /// TODO get rid of the op positional arg and make that data part of + /// the base Inst tag. pub const Cmp = struct { pub const base_tag = Tag.cmp; base: Inst, -- cgit v1.2.3 From 8e425c0c8d78acc64a4223a35010df478d5b7e16 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Wed, 8 Jul 2020 20:33:33 -0700 Subject: stage2: `if` AST=>ZIR --- lib/std/zig/ast.zig | 2 + src-self-hosted/Module.zig | 186 ++++++++++++++++++++++++++++-------- src-self-hosted/codegen.zig | 13 ++- src-self-hosted/ir.zig | 19 +++- src-self-hosted/zir.zig | 225 ++++++++++++++++++++++++++++---------------- 5 files changed, 317 insertions(+), 128 deletions(-) (limited to 'src-self-hosted/Module.zig') diff --git a/lib/std/zig/ast.zig b/lib/std/zig/ast.zig index 370f42b463..72d8f3560e 100644 --- a/lib/std/zig/ast.zig +++ b/lib/std/zig/ast.zig @@ -959,6 +959,8 @@ pub const Node = struct { }; /// The params are directly after the FnProto in memory. + /// TODO have a flags field for the optional nodes, and have them appended + /// before or after the parameters in memory. pub const FnProto = struct { base: Node = Node{ .id = .FnProto }, doc_comments: ?*DocComment, diff --git a/src-self-hosted/Module.zig b/src-self-hosted/Module.zig index 67c1b00a1e..328b043153 100644 --- a/src-self-hosted/Module.zig +++ b/src-self-hosted/Module.zig @@ -303,14 +303,14 @@ pub const Scope = struct { switch (self.tag) { .block => return self.cast(Block).?.arena, .decl => return &self.cast(DeclAnalysis).?.arena.allocator, - .gen_zir => return &self.cast(GenZIR).?.arena.allocator, + .gen_zir => return self.cast(GenZIR).?.arena, .zir_module => return &self.cast(ZIRModule).?.contents.module.arena.allocator, .file => unreachable, } } - /// Asserts the scope has a parent which is a DeclAnalysis and - /// returns the Decl. + /// If the scope has a parent which is a `DeclAnalysis`, + /// returns the `Decl`, otherwise returns `null`. pub fn decl(self: *Scope) ?*Decl { return switch (self.tag) { .block => self.cast(Block).?.decl, @@ -653,7 +653,7 @@ pub const Scope = struct { label: ?Label = null, pub const Label = struct { - name: []const u8, + zir_block: *zir.Inst.Block, results: ArrayListUnmanaged(*Inst), block_inst: *Inst.Block, }; @@ -674,8 +674,8 @@ pub const Scope = struct { pub const base_tag: Tag = .gen_zir; base: Scope = Scope{ .tag = base_tag }, decl: *Decl, - arena: std.heap.ArenaAllocator, - instructions: std.ArrayList(*zir.Inst), + arena: *Allocator, + instructions: std.ArrayListUnmanaged(*zir.Inst) = .{}, }; }; @@ -1115,19 +1115,19 @@ fn astGenAndAnalyzeDecl(self: *Module, decl: *Decl) !bool { // This arena allocator's memory is discarded at the end of this function. It is used // to determine the type of the function, and hence the type of the decl, which is needed // to complete the Decl analysis. + var fn_type_scope_arena = std.heap.ArenaAllocator.init(self.gpa); + defer fn_type_scope_arena.deinit(); var fn_type_scope: Scope.GenZIR = .{ .decl = decl, - .arena = std.heap.ArenaAllocator.init(self.gpa), - .instructions = std.ArrayList(*zir.Inst).init(self.gpa), + .arena = &fn_type_scope_arena.allocator, }; - defer fn_type_scope.arena.deinit(); - defer fn_type_scope.instructions.deinit(); + defer fn_type_scope.instructions.deinit(self.gpa); const body_node = fn_proto.body_node orelse return self.failTok(&fn_type_scope.base, fn_proto.fn_token, "TODO implement extern functions", .{}); const param_decls = fn_proto.params(); - const param_types = try fn_type_scope.arena.allocator.alloc(*zir.Inst, param_decls.len); + const param_types = try fn_type_scope.arena.alloc(*zir.Inst, param_decls.len); for (param_decls) |param_decl, i| { const param_type_node = switch (param_decl.param_type) { .var_type => |node| return self.failNode(&fn_type_scope.base, node, "TODO implement anytype parameter", .{}), @@ -1190,24 +1190,24 @@ fn astGenAndAnalyzeDecl(self: *Module, decl: *Decl) !bool { const fn_zir = blk: { // This scope's arena memory is discarded after the ZIR generation // pass completes, and semantic analysis of it completes. + var gen_scope_arena = std.heap.ArenaAllocator.init(self.gpa); + errdefer gen_scope_arena.deinit(); var gen_scope: Scope.GenZIR = .{ .decl = decl, - .arena = std.heap.ArenaAllocator.init(self.gpa), - .instructions = std.ArrayList(*zir.Inst).init(self.gpa), + .arena = &gen_scope_arena.allocator, }; - errdefer gen_scope.arena.deinit(); - defer gen_scope.instructions.deinit(); + defer gen_scope.instructions.deinit(self.gpa); const body_block = body_node.cast(ast.Node.Block).?; try self.astGenBlock(&gen_scope.base, body_block); - const fn_zir = try gen_scope.arena.allocator.create(Fn.ZIR); + const fn_zir = try gen_scope_arena.allocator.create(Fn.ZIR); fn_zir.* = .{ .body = .{ - .instructions = try gen_scope.arena.allocator.dupe(*zir.Inst, gen_scope.instructions.items), + .instructions = try gen_scope.arena.dupe(*zir.Inst, gen_scope.instructions.items), }, - .arena = gen_scope.arena.state, + .arena = gen_scope_arena.state, }; break :blk fn_zir; }; @@ -1351,9 +1351,70 @@ fn astGenIf(self: *Module, scope: *Scope, if_node: *ast.Node.If) InnerError!*zir return self.failNode(scope, payload, "TODO implement astGenIf for error unions", .{}); } } - const cond = try self.astGenExpr(scope, if_node.condition); - const body = try self.astGenExpr(scope, if_node.condition); - return self.failNode(scope, if_node.condition, "TODO implement astGenIf", .{}); + var block_scope: Scope.GenZIR = .{ + .decl = scope.decl().?, + .arena = scope.arena(), + .instructions = .{}, + }; + defer block_scope.instructions.deinit(self.gpa); + + const cond = try self.astGenExpr(&block_scope.base, if_node.condition); + + const tree = scope.tree(); + const if_src = tree.token_locs[if_node.if_token].start; + const condbr = try self.addZIRInstSpecial(&block_scope.base, if_src, zir.Inst.CondBr, .{ + .condition = cond, + .true_body = undefined, // populated below + .false_body = undefined, // populated below + }, .{}); + + const block = try self.addZIRInstBlock(scope, if_src, .{ + .instructions = try block_scope.arena.dupe(*zir.Inst, block_scope.instructions.items), + }); + var then_scope: Scope.GenZIR = .{ + .decl = block_scope.decl, + .arena = block_scope.arena, + .instructions = .{}, + }; + defer then_scope.instructions.deinit(self.gpa); + + const then_result = try self.astGenExpr(&then_scope.base, if_node.body); + const then_src = tree.token_locs[if_node.body.lastToken()].start; + _ = try self.addZIRInst(&then_scope.base, then_src, zir.Inst.Break, .{ + .block = block, + .operand = then_result, + }, .{}); + condbr.positionals.true_body = .{ + .instructions = try then_scope.arena.dupe(*zir.Inst, then_scope.instructions.items), + }; + + var else_scope: Scope.GenZIR = .{ + .decl = block_scope.decl, + .arena = block_scope.arena, + .instructions = .{}, + }; + defer else_scope.instructions.deinit(self.gpa); + + if (if_node.@"else") |else_node| { + const else_result = try self.astGenExpr(&else_scope.base, else_node.body); + const else_src = tree.token_locs[else_node.body.lastToken()].start; + _ = try self.addZIRInst(&else_scope.base, else_src, zir.Inst.Break, .{ + .block = block, + .operand = else_result, + }, .{}); + } else { + // TODO Optimization opportunity: we can avoid an allocation and a memcpy here + // by directly allocating the body for this one instruction. + const else_src = tree.token_locs[if_node.lastToken()].start; + _ = try self.addZIRInst(&else_scope.base, else_src, zir.Inst.BreakVoid, .{ + .block = block, + }, .{}); + } + condbr.positionals.false_body = .{ + .instructions = try else_scope.arena.dupe(*zir.Inst, else_scope.instructions.items), + }; + + return &block.base; } fn astGenControlFlowExpression( @@ -1379,12 +1440,12 @@ fn astGenControlFlowExpression( fn astGenIdent(self: *Module, scope: *Scope, ident: *ast.Node.Identifier) InnerError!*zir.Inst { const tree = scope.tree(); const ident_name = tree.tokenSlice(ident.token); + const src = tree.token_locs[ident.token].start; if (mem.eql(u8, ident_name, "_")) { return self.failNode(scope, &ident.base, "TODO implement '_' identifier", .{}); } if (getSimplePrimitiveValue(ident_name)) |typed_value| { - const src = tree.token_locs[ident.token].start; return self.addZIRInstConst(scope, src, typed_value); } @@ -1408,7 +1469,6 @@ fn astGenIdent(self: *Module, scope: *Scope, ident: *ast.Node.Identifier) InnerE 64 => if (is_signed) Value.initTag(.i64_type) else Value.initTag(.u64_type), else => return self.failNode(scope, &ident.base, "TODO implement arbitrary integer bitwidth types", .{}), }; - const src = tree.token_locs[ident.token].start; return self.addZIRInstConst(scope, src, .{ .ty = Type.initTag(.type), .val = val, @@ -1417,10 +1477,21 @@ fn astGenIdent(self: *Module, scope: *Scope, ident: *ast.Node.Identifier) InnerE } if (self.lookupDeclName(scope, ident_name)) |decl| { - const src = tree.token_locs[ident.token].start; return try self.addZIRInst(scope, src, zir.Inst.DeclValInModule, .{ .decl = decl }, .{}); } + // Function parameter + if (scope.decl()) |decl| { + if (tree.root_node.decls()[decl.src_index].cast(ast.Node.FnProto)) |fn_proto| { + for (fn_proto.params()) |param, i| { + const param_name = tree.tokenSlice(param.name_token.?); + if (mem.eql(u8, param_name, ident_name)) { + return try self.addZIRInst(scope, src, zir.Inst.Arg, .{ .index = i }, .{}); + } + } + } + } + return self.failNode(scope, &ident.base, "TODO implement local variable identifier lookup", .{}); } @@ -1563,7 +1634,7 @@ fn astGenCall(self: *Module, scope: *Scope, call: *ast.Node.Call) InnerError!*zi const lhs = try self.astGenExpr(scope, call.lhs); const param_nodes = call.params(); - const args = try scope.cast(Scope.GenZIR).?.arena.allocator.alloc(*zir.Inst, param_nodes.len); + const args = try scope.cast(Scope.GenZIR).?.arena.alloc(*zir.Inst, param_nodes.len); for (param_nodes) |param_node, i| { args[i] = try self.astGenExpr(scope, param_node); } @@ -2239,7 +2310,7 @@ fn newZIRInst( comptime T: type, positionals: std.meta.fieldInfo(T, "positionals").field_type, kw_args: std.meta.fieldInfo(T, "kw_args").field_type, -) !*zir.Inst { +) !*T { const inst = try gpa.create(T); inst.* = .{ .base = .{ @@ -2249,30 +2320,48 @@ fn newZIRInst( .positionals = positionals, .kw_args = kw_args, }; - return &inst.base; + return inst; } -fn addZIRInst( +fn addZIRInstSpecial( self: *Module, scope: *Scope, src: usize, comptime T: type, positionals: std.meta.fieldInfo(T, "positionals").field_type, kw_args: std.meta.fieldInfo(T, "kw_args").field_type, -) !*zir.Inst { +) !*T { const gen_zir = scope.cast(Scope.GenZIR).?; - try gen_zir.instructions.ensureCapacity(gen_zir.instructions.items.len + 1); - const inst = try newZIRInst(&gen_zir.arena.allocator, src, T, positionals, kw_args); - gen_zir.instructions.appendAssumeCapacity(inst); + try gen_zir.instructions.ensureCapacity(self.gpa, gen_zir.instructions.items.len + 1); + const inst = try newZIRInst(gen_zir.arena, src, T, positionals, kw_args); + gen_zir.instructions.appendAssumeCapacity(&inst.base); return inst; } +fn addZIRInst( + self: *Module, + scope: *Scope, + src: usize, + comptime T: type, + positionals: std.meta.fieldInfo(T, "positionals").field_type, + kw_args: std.meta.fieldInfo(T, "kw_args").field_type, +) !*zir.Inst { + const inst_special = try self.addZIRInstSpecial(scope, src, T, positionals, kw_args); + return &inst_special.base; +} + /// TODO The existence of this function is a workaround for a bug in stage1. fn addZIRInstConst(self: *Module, scope: *Scope, src: usize, typed_value: TypedValue) !*zir.Inst { const P = std.meta.fieldInfo(zir.Inst.Const, "positionals").field_type; return self.addZIRInst(scope, src, zir.Inst.Const, P{ .typed_value = typed_value }, .{}); } +/// TODO The existence of this function is a workaround for a bug in stage1. +fn addZIRInstBlock(self: *Module, scope: *Scope, src: usize, body: zir.Module.Body) !*zir.Inst.Block { + const P = std.meta.fieldInfo(zir.Inst.Block, "positionals").field_type; + return self.addZIRInstSpecial(scope, src, zir.Inst.Block, P{ .body = body }, .{}); +} + fn addNewInst(self: *Module, block: *Scope.Block, src: usize, ty: Type, comptime T: type) !*T { const inst = try block.arena.create(T); inst.* = .{ @@ -2403,6 +2492,7 @@ fn analyzeInst(self: *Module, scope: *Scope, old_inst: *zir.Inst) InnerError!*In switch (old_inst.tag) { .arg => return self.analyzeInstArg(scope, old_inst.cast(zir.Inst.Arg).?), .block => return self.analyzeInstBlock(scope, old_inst.cast(zir.Inst.Block).?), + .@"break" => return self.analyzeInstBreak(scope, old_inst.cast(zir.Inst.Break).?), .breakpoint => return self.analyzeInstBreakpoint(scope, old_inst.cast(zir.Inst.Breakpoint).?), .breakvoid => return self.analyzeInstBreakVoid(scope, old_inst.cast(zir.Inst.BreakVoid).?), .call => return self.analyzeInstCall(scope, old_inst.cast(zir.Inst.Call).?), @@ -2559,7 +2649,7 @@ fn analyzeInstBlock(self: *Module, scope: *Scope, inst: *zir.Inst.Block) InnerEr .arena = parent_block.arena, // TODO @as here is working around a miscompilation compiler bug :( .label = @as(?Scope.Block.Label, Scope.Block.Label{ - .name = inst.positionals.label, + .zir_block = inst, .results = .{}, .block_inst = block_inst, }), @@ -2588,25 +2678,39 @@ fn analyzeInstBreakpoint(self: *Module, scope: *Scope, inst: *zir.Inst.Breakpoin return self.addNewInstArgs(b, inst.base.src, Type.initTag(.void), Inst.Breakpoint, {}); } +fn analyzeInstBreak(self: *Module, scope: *Scope, inst: *zir.Inst.Break) InnerError!*Inst { + const operand = try self.resolveInst(scope, inst.positionals.operand); + const block = inst.positionals.block; + return self.analyzeBreak(scope, inst.base.src, block, operand); +} + fn analyzeInstBreakVoid(self: *Module, scope: *Scope, inst: *zir.Inst.BreakVoid) InnerError!*Inst { - const label_name = inst.positionals.label; + const block = inst.positionals.block; const void_inst = try self.constVoid(scope, inst.base.src); + return self.analyzeBreak(scope, inst.base.src, block, void_inst); +} +fn analyzeBreak( + self: *Module, + scope: *Scope, + src: usize, + zir_block: *zir.Inst.Block, + operand: *Inst, +) InnerError!*Inst { var opt_block = scope.cast(Scope.Block); while (opt_block) |block| { if (block.label) |*label| { - if (mem.eql(u8, label.name, label_name)) { - try label.results.append(self.gpa, void_inst); - const b = try self.requireRuntimeBlock(scope, inst.base.src); - return self.addNewInstArgs(b, inst.base.src, Type.initTag(.noreturn), Inst.BreakVoid, .{ + if (label.zir_block == zir_block) { + try label.results.append(self.gpa, operand); + const b = try self.requireRuntimeBlock(scope, src); + return self.addNewInstArgs(b, src, Type.initTag(.noreturn), Inst.Br, .{ .block = label.block_inst, + .operand = operand, }); } } opt_block = block.parent; - } else { - return self.fail(scope, inst.base.src, "use of undeclared label '{}'", .{label_name}); - } + } else unreachable; } fn analyzeInstDeclRefStr(self: *Module, scope: *Scope, inst: *zir.Inst.DeclRefStr) InnerError!*Inst { diff --git a/src-self-hosted/codegen.zig b/src-self-hosted/codegen.zig index 232703b697..e2c5c989ac 100644 --- a/src-self-hosted/codegen.zig +++ b/src-self-hosted/codegen.zig @@ -418,8 +418,9 @@ const Function = struct { .assembly => return self.genAsm(inst.cast(ir.Inst.Assembly).?, arch), .bitcast => return self.genBitCast(inst.cast(ir.Inst.BitCast).?), .block => return self.genBlock(inst.cast(ir.Inst.Block).?, arch), + .br => return self.genBr(inst.cast(ir.Inst.Br).?, arch), .breakpoint => return self.genBreakpoint(inst.src, arch), - .breakvoid => return self.genBreakVoid(inst.cast(ir.Inst.BreakVoid).?, arch), + .brvoid => return self.genBrVoid(inst.cast(ir.Inst.BrVoid).?, arch), .call => return self.genCall(inst.cast(ir.Inst.Call).?, arch), .cmp => return self.genCmp(inst.cast(ir.Inst.Cmp).?, arch), .condbr => return self.genCondBr(inst.cast(ir.Inst.CondBr).?, arch), @@ -767,7 +768,13 @@ const Function = struct { } } - fn genBreakVoid(self: *Function, inst: *ir.Inst.BreakVoid, comptime arch: std.Target.Cpu.Arch) !MCValue { + fn genBr(self: *Function, inst: *ir.Inst.Br, comptime arch: std.Target.Cpu.Arch) !MCValue { + switch (arch) { + else => return self.fail(inst.base.src, "TODO implement br for {}", .{self.target.cpu.arch}), + } + } + + fn genBrVoid(self: *Function, inst: *ir.Inst.BrVoid, comptime arch: std.Target.Cpu.Arch) !MCValue { // Emit a jump with a relocation. It will be patched up after the block ends. try inst.args.block.codegen.relocs.ensureCapacity(self.gpa, inst.args.block.codegen.relocs.items.len + 1); @@ -780,7 +787,7 @@ const Function = struct { // Leave the jump offset undefined inst.args.block.codegen.relocs.appendAssumeCapacity(.{ .rel32 = self.code.items.len - 4 }); }, - else => return self.fail(inst.base.src, "TODO implement breakvoid for {}", .{self.target.cpu.arch}), + else => return self.fail(inst.base.src, "TODO implement brvoid for {}", .{self.target.cpu.arch}), } return .none; } diff --git a/src-self-hosted/ir.zig b/src-self-hosted/ir.zig index f2ba3801a1..1de7c626ea 100644 --- a/src-self-hosted/ir.zig +++ b/src-self-hosted/ir.zig @@ -46,8 +46,9 @@ pub const Inst = struct { assembly, bitcast, block, + br, breakpoint, - breakvoid, + brvoid, call, cmp, condbr, @@ -80,7 +81,8 @@ pub const Inst = struct { .sub, => false, - .breakvoid, + .br, + .brvoid, .condbr, .ret, .retvoid, @@ -162,14 +164,23 @@ pub const Inst = struct { codegen: codegen.BlockData = .{}, }; + pub const Br = struct { + pub const base_tag = Tag.br; + base: Inst, + args: struct { + block: *Block, + operand: *Inst, + }, + }; + pub const Breakpoint = struct { pub const base_tag = Tag.breakpoint; base: Inst, args: void, }; - pub const BreakVoid = struct { - pub const base_tag = Tag.breakvoid; + pub const BrVoid = struct { + pub const base_tag = Tag.brvoid; base: Inst, args: struct { block: *Block, diff --git a/src-self-hosted/zir.zig b/src-self-hosted/zir.zig index 0221e4d330..2a4db02c19 100644 --- a/src-self-hosted/zir.zig +++ b/src-self-hosted/zir.zig @@ -38,6 +38,8 @@ pub const Inst = struct { arg, /// A labeled block of code, which can return a value. block, + /// Return a value from a `Block`. + @"break", breakpoint, /// Same as `break` but without an operand; the operand is assumed to be the void value. breakvoid, @@ -85,6 +87,7 @@ pub const Inst = struct { return switch (tag) { .arg => Arg, .block => Block, + .@"break" => Break, .breakpoint => Breakpoint, .breakvoid => BreakVoid, .call => Call, @@ -143,12 +146,22 @@ pub const Inst = struct { base: Inst, positionals: struct { - label: []const u8, body: Module.Body, }, kw_args: struct {}, }; + pub const Break = struct { + pub const base_tag = Tag.@"break"; + base: Inst, + + positionals: struct { + block: *Block, + operand: *Inst, + }, + kw_args: struct {}, + }; + pub const Breakpoint = struct { pub const base_tag = Tag.breakpoint; base: Inst, @@ -162,7 +175,7 @@ pub const Inst = struct { base: Inst, positionals: struct { - label: []const u8, + block: *Block, }, kw_args: struct {}, }; @@ -610,8 +623,6 @@ pub const Module = struct { self.writeToStream(std.heap.page_allocator, std.io.getStdErr().outStream()) catch {}; } - const InstPtrTable = std.AutoHashMap(*Inst, struct { inst: *Inst, index: ?usize, name: []const u8 }); - const DeclAndIndex = struct { decl: *Decl, index: usize, @@ -645,84 +656,100 @@ pub const Module = struct { /// The allocator is used for temporary storage, but this function always returns /// with no resources allocated. pub fn writeToStream(self: Module, allocator: *Allocator, stream: var) !void { - // First, build a map of *Inst to @ or % indexes - var inst_table = InstPtrTable.init(allocator); - defer inst_table.deinit(); + var write = Writer{ + .module = &self, + .inst_table = InstPtrTable.init(allocator), + .block_table = std.AutoHashMap(*Inst.Block, []const u8).init(allocator), + .arena = std.heap.ArenaAllocator.init(allocator), + .indent = 2, + }; + defer write.arena.deinit(); + defer write.inst_table.deinit(); + defer write.block_table.deinit(); - try inst_table.ensureCapacity(self.decls.len); + // First, build a map of *Inst to @ or % indexes + try write.inst_table.ensureCapacity(self.decls.len); for (self.decls) |decl, decl_i| { - try inst_table.putNoClobber(decl.inst, .{ .inst = decl.inst, .index = null, .name = decl.name }); + try write.inst_table.putNoClobber(decl.inst, .{ .inst = decl.inst, .index = null, .name = decl.name }); if (decl.inst.cast(Inst.Fn)) |fn_inst| { for (fn_inst.positionals.body.instructions) |inst, inst_i| { - try inst_table.putNoClobber(inst, .{ .inst = inst, .index = inst_i, .name = undefined }); + try write.inst_table.putNoClobber(inst, .{ .inst = inst, .index = inst_i, .name = undefined }); } } } for (self.decls) |decl, i| { try stream.print("@{} ", .{decl.name}); - try self.writeInstToStream(stream, decl.inst, &inst_table, 2); + try write.writeInstToStream(stream, decl.inst); try stream.writeByte('\n'); } } +}; + +const InstPtrTable = std.AutoHashMap(*Inst, struct { inst: *Inst, index: ?usize, name: []const u8 }); + +const Writer = struct { + module: *const Module, + inst_table: InstPtrTable, + block_table: std.AutoHashMap(*Inst.Block, []const u8), + arena: std.heap.ArenaAllocator, + indent: usize, + fn writeInstToStream( - self: Module, + self: *Writer, stream: var, inst: *Inst, - inst_table: *const InstPtrTable, - indent: usize, - ) @TypeOf(stream).Error!void { + ) (@TypeOf(stream).Error || error{OutOfMemory})!void { // TODO I tried implementing this with an inline for loop and hit a compiler bug switch (inst.tag) { - .arg => return self.writeInstToStreamGeneric(stream, .arg, inst, inst_table, indent), - .block => return self.writeInstToStreamGeneric(stream, .block, inst, inst_table, indent), - .breakpoint => return self.writeInstToStreamGeneric(stream, .breakpoint, inst, inst_table, indent), - .breakvoid => return self.writeInstToStreamGeneric(stream, .breakvoid, inst, inst_table, indent), - .call => return self.writeInstToStreamGeneric(stream, .call, inst, inst_table, indent), - .declref => return self.writeInstToStreamGeneric(stream, .declref, inst, inst_table, indent), - .declref_str => return self.writeInstToStreamGeneric(stream, .declref_str, inst, inst_table, indent), - .declval => return self.writeInstToStreamGeneric(stream, .declval, inst, inst_table, indent), - .declval_in_module => return self.writeInstToStreamGeneric(stream, .declval_in_module, inst, inst_table, indent), - .compileerror => return self.writeInstToStreamGeneric(stream, .compileerror, inst, inst_table, indent), - .@"const" => return self.writeInstToStreamGeneric(stream, .@"const", inst, inst_table, indent), - .str => return self.writeInstToStreamGeneric(stream, .str, inst, inst_table, indent), - .int => return self.writeInstToStreamGeneric(stream, .int, inst, inst_table, indent), - .inttype => return self.writeInstToStreamGeneric(stream, .inttype, inst, inst_table, indent), - .ptrtoint => return self.writeInstToStreamGeneric(stream, .ptrtoint, inst, inst_table, indent), - .fieldptr => return self.writeInstToStreamGeneric(stream, .fieldptr, inst, inst_table, indent), - .deref => return self.writeInstToStreamGeneric(stream, .deref, inst, inst_table, indent), - .as => return self.writeInstToStreamGeneric(stream, .as, inst, inst_table, indent), - .@"asm" => return self.writeInstToStreamGeneric(stream, .@"asm", inst, inst_table, indent), - .@"unreachable" => return self.writeInstToStreamGeneric(stream, .@"unreachable", inst, inst_table, indent), - .@"return" => return self.writeInstToStreamGeneric(stream, .@"return", inst, inst_table, indent), - .returnvoid => return self.writeInstToStreamGeneric(stream, .returnvoid, inst, inst_table, indent), - .@"fn" => return self.writeInstToStreamGeneric(stream, .@"fn", inst, inst_table, indent), - .@"export" => return self.writeInstToStreamGeneric(stream, .@"export", inst, inst_table, indent), - .primitive => return self.writeInstToStreamGeneric(stream, .primitive, inst, inst_table, indent), - .fntype => return self.writeInstToStreamGeneric(stream, .fntype, inst, inst_table, indent), - .intcast => return self.writeInstToStreamGeneric(stream, .intcast, inst, inst_table, indent), - .bitcast => return self.writeInstToStreamGeneric(stream, .bitcast, inst, inst_table, indent), - .elemptr => return self.writeInstToStreamGeneric(stream, .elemptr, inst, inst_table, indent), - .add => return self.writeInstToStreamGeneric(stream, .add, inst, inst_table, indent), - .sub => return self.writeInstToStreamGeneric(stream, .sub, inst, inst_table, indent), - .cmp => return self.writeInstToStreamGeneric(stream, .cmp, inst, inst_table, indent), - .condbr => return self.writeInstToStreamGeneric(stream, .condbr, inst, inst_table, indent), - .isnull => return self.writeInstToStreamGeneric(stream, .isnull, inst, inst_table, indent), - .isnonnull => return self.writeInstToStreamGeneric(stream, .isnonnull, inst, inst_table, indent), + .arg => return self.writeInstToStreamGeneric(stream, .arg, inst), + .block => return self.writeInstToStreamGeneric(stream, .block, inst), + .@"break" => return self.writeInstToStreamGeneric(stream, .@"break", inst), + .breakpoint => return self.writeInstToStreamGeneric(stream, .breakpoint, inst), + .breakvoid => return self.writeInstToStreamGeneric(stream, .breakvoid, inst), + .call => return self.writeInstToStreamGeneric(stream, .call, inst), + .declref => return self.writeInstToStreamGeneric(stream, .declref, inst), + .declref_str => return self.writeInstToStreamGeneric(stream, .declref_str, inst), + .declval => return self.writeInstToStreamGeneric(stream, .declval, inst), + .declval_in_module => return self.writeInstToStreamGeneric(stream, .declval_in_module, inst), + .compileerror => return self.writeInstToStreamGeneric(stream, .compileerror, inst), + .@"const" => return self.writeInstToStreamGeneric(stream, .@"const", inst), + .str => return self.writeInstToStreamGeneric(stream, .str, inst), + .int => return self.writeInstToStreamGeneric(stream, .int, inst), + .inttype => return self.writeInstToStreamGeneric(stream, .inttype, inst), + .ptrtoint => return self.writeInstToStreamGeneric(stream, .ptrtoint, inst), + .fieldptr => return self.writeInstToStreamGeneric(stream, .fieldptr, inst), + .deref => return self.writeInstToStreamGeneric(stream, .deref, inst), + .as => return self.writeInstToStreamGeneric(stream, .as, inst), + .@"asm" => return self.writeInstToStreamGeneric(stream, .@"asm", inst), + .@"unreachable" => return self.writeInstToStreamGeneric(stream, .@"unreachable", inst), + .@"return" => return self.writeInstToStreamGeneric(stream, .@"return", inst), + .returnvoid => return self.writeInstToStreamGeneric(stream, .returnvoid, inst), + .@"fn" => return self.writeInstToStreamGeneric(stream, .@"fn", inst), + .@"export" => return self.writeInstToStreamGeneric(stream, .@"export", inst), + .primitive => return self.writeInstToStreamGeneric(stream, .primitive, inst), + .fntype => return self.writeInstToStreamGeneric(stream, .fntype, inst), + .intcast => return self.writeInstToStreamGeneric(stream, .intcast, inst), + .bitcast => return self.writeInstToStreamGeneric(stream, .bitcast, inst), + .elemptr => return self.writeInstToStreamGeneric(stream, .elemptr, inst), + .add => return self.writeInstToStreamGeneric(stream, .add, inst), + .sub => return self.writeInstToStreamGeneric(stream, .sub, inst), + .cmp => return self.writeInstToStreamGeneric(stream, .cmp, inst), + .condbr => return self.writeInstToStreamGeneric(stream, .condbr, inst), + .isnull => return self.writeInstToStreamGeneric(stream, .isnull, inst), + .isnonnull => return self.writeInstToStreamGeneric(stream, .isnonnull, inst), } } fn writeInstToStreamGeneric( - self: Module, + self: *Writer, stream: var, comptime inst_tag: Inst.Tag, base: *Inst, - inst_table: *const InstPtrTable, - indent: usize, - ) @TypeOf(stream).Error!void { + ) (@TypeOf(stream).Error || error{OutOfMemory})!void { const SpecificInst = Inst.TagToType(inst_tag); const inst = @fieldParentPtr(SpecificInst, "base", base); const Positionals = @TypeOf(inst.positionals); @@ -732,7 +759,7 @@ pub const Module = struct { if (i != 0) { try stream.writeAll(", "); } - try self.writeParamToStream(stream, @field(inst.positionals, arg_field.name), inst_table, indent); + try self.writeParamToStream(stream, @field(inst.positionals, arg_field.name)); } comptime var need_comma = pos_fields.len != 0; @@ -742,13 +769,13 @@ pub const Module = struct { if (@field(inst.kw_args, arg_field.name)) |non_optional| { if (need_comma) try stream.writeAll(", "); try stream.print("{}=", .{arg_field.name}); - try self.writeParamToStream(stream, non_optional, inst_table, indent); + try self.writeParamToStream(stream, non_optional); need_comma = true; } } else { if (need_comma) try stream.writeAll(", "); try stream.print("{}=", .{arg_field.name}); - try self.writeParamToStream(stream, @field(inst.kw_args, arg_field.name), inst_table, indent); + try self.writeParamToStream(stream, @field(inst.kw_args, arg_field.name)); need_comma = true; } } @@ -756,31 +783,37 @@ pub const Module = struct { try stream.writeByte(')'); } - fn writeParamToStream(self: Module, stream: var, param: var, inst_table: *const InstPtrTable, indent: usize) !void { + fn writeParamToStream(self: *Writer, stream: var, param: var) !void { if (@typeInfo(@TypeOf(param)) == .Enum) { return stream.writeAll(@tagName(param)); } switch (@TypeOf(param)) { - *Inst => return self.writeInstParamToStream(stream, param, inst_table), + *Inst => return self.writeInstParamToStream(stream, param), []*Inst => { try stream.writeByte('['); for (param) |inst, i| { if (i != 0) { try stream.writeAll(", "); } - try self.writeInstParamToStream(stream, inst, inst_table); + try self.writeInstParamToStream(stream, inst); } try stream.writeByte(']'); }, Module.Body => { try stream.writeAll("{\n"); for (param.instructions) |inst, i| { - try stream.writeByteNTimes(' ', indent); + try stream.writeByteNTimes(' ', self.indent); try stream.print("%{} ", .{i}); - try self.writeInstToStream(stream, inst, inst_table, indent + 2); + if (inst.cast(Inst.Block)) |block| { + const name = try std.fmt.allocPrint(&self.arena.allocator, "label_{}", .{i}); + try self.block_table.put(block, name); + } + self.indent += 2; + try self.writeInstToStream(stream, inst); + self.indent -= 2; try stream.writeByte('\n'); } - try stream.writeByteNTimes(' ', indent - 2); + try stream.writeByteNTimes(' ', self.indent - 2); try stream.writeByte('}'); }, bool => return stream.writeByte("01"[@boolToInt(param)]), @@ -788,12 +821,16 @@ pub const Module = struct { BigIntConst, usize => return stream.print("{}", .{param}), TypedValue => unreachable, // this is a special case *IrModule.Decl => unreachable, // this is a special case + *Inst.Block => { + const name = self.block_table.get(param).?; + return std.zig.renderStringLiteral(name, stream); + }, else => |T| @compileError("unimplemented: rendering parameter of type " ++ @typeName(T)), } } - fn writeInstParamToStream(self: Module, stream: var, inst: *Inst, inst_table: *const InstPtrTable) !void { - if (inst_table.get(inst)) |info| { + fn writeInstParamToStream(self: *Writer, stream: var, inst: *Inst) !void { + if (self.inst_table.get(inst)) |info| { if (info.index) |i| { try stream.print("%{}", .{info.index}); } else { @@ -823,7 +860,9 @@ pub fn parse(allocator: *Allocator, source: [:0]const u8) Allocator.Error!Module .global_name_map = &global_name_map, .decls = .{}, .unnamed_index = 0, + .block_table = std.StringHashMap(*Inst.Block).init(allocator), }; + defer parser.block_table.deinit(); errdefer parser.arena.deinit(); parser.parseRoot() catch |err| switch (err) { @@ -849,6 +888,7 @@ const Parser = struct { global_name_map: *std.StringHashMap(*Inst), error_msg: ?ErrorMsg = null, unnamed_index: usize, + block_table: std.StringHashMap(*Inst.Block), const Body = struct { instructions: std.ArrayList(*Inst), @@ -1057,6 +1097,10 @@ const Parser = struct { .tag = InstType.base_tag, }; + if (InstType == Inst.Block) { + try self.block_table.put(inst_name, inst_specific); + } + if (@hasField(InstType, "ty")) { inst_specific.ty = opt_type orelse { return self.fail("instruction '" ++ fn_name ++ "' requires type", .{}); @@ -1162,6 +1206,10 @@ const Parser = struct { }, TypedValue => return self.fail("'const' is a special instruction; not legal in ZIR text", .{}), *IrModule.Decl => return self.fail("'declval_in_module' is a special instruction; not legal in ZIR text", .{}), + *Inst.Block => { + const name = try self.parseStringLiteral(); + return self.block_table.get(name).?; + }, else => @compileError("Unimplemented: ir parseParameterGeneric for type " ++ @typeName(T)), } return self.fail("TODO parse parameter {}", .{@typeName(T)}); @@ -1226,7 +1274,9 @@ pub fn emit(allocator: *Allocator, old_module: IrModule) !Module { .names = std.StringHashMap(void).init(allocator), .primitive_table = std.AutoHashMap(Inst.Primitive.Builtin, *Decl).init(allocator), .indent = 0, + .block_table = std.AutoHashMap(*ir.Inst.Block, *Inst.Block).init(allocator), }; + defer ctx.block_table.deinit(); defer ctx.decls.deinit(allocator); defer ctx.names.deinit(); defer ctx.primitive_table.deinit(); @@ -1249,6 +1299,7 @@ const EmitZIR = struct { next_auto_name: usize, primitive_table: std.AutoHashMap(Inst.Primitive.Builtin, *Decl), indent: usize, + block_table: std.AutoHashMap(*ir.Inst.Block, *Inst.Block), fn emit(self: *EmitZIR) !void { // Put all the Decls in a list and sort them by name to avoid nondeterminism introduced @@ -1611,33 +1662,47 @@ const EmitZIR = struct { const old_inst = inst.cast(ir.Inst.Block).?; const new_inst = try self.arena.allocator.create(Inst.Block); - // We do this now so that the break instructions within the block - // can find it. - try inst_table.put(&old_inst.base, &new_inst.base); + try self.block_table.put(old_inst, new_inst); + + var block_body = std.ArrayList(*Inst).init(self.allocator); + defer block_body.deinit(); + + try self.emitBody(old_inst.args.body, inst_table, &block_body); + new_inst.* = .{ .base = .{ .src = inst.src, .tag = Inst.Block.base_tag, }, .positionals = .{ - .label = try self.autoName(), - .body = undefined, + .body = .{ .instructions = block_body.toOwnedSlice() }, }, .kw_args = .{}, }; - var block_body = std.ArrayList(*Inst).init(self.allocator); - defer block_body.deinit(); - - try self.emitBody(old_inst.args.body, inst_table, &block_body); - new_inst.positionals.body = .{ .instructions = block_body.toOwnedSlice() }; - + break :blk &new_inst.base; + }, + .br => blk: { + const old_inst = inst.cast(ir.Inst.Br).?; + const new_block = self.block_table.get(old_inst.args.block).?; + const new_inst = try self.arena.allocator.create(Inst.Break); + new_inst.* = .{ + .base = .{ + .src = inst.src, + .tag = Inst.Break.base_tag, + }, + .positionals = .{ + .block = new_block, + .operand = try self.resolveInst(new_body, old_inst.args.operand), + }, + .kw_args = .{}, + }; break :blk &new_inst.base; }, .breakpoint => try self.emitTrivial(inst.src, Inst.Breakpoint), - .breakvoid => blk: { - const old_inst = inst.cast(ir.Inst.BreakVoid).?; - const new_block = inst_table.get(&old_inst.args.block.base).?; + .brvoid => blk: { + const old_inst = inst.cast(ir.Inst.BrVoid).?; + const new_block = self.block_table.get(old_inst.args.block).?; const new_inst = try self.arena.allocator.create(Inst.BreakVoid); new_inst.* = .{ .base = .{ @@ -1645,7 +1710,7 @@ const EmitZIR = struct { .tag = Inst.BreakVoid.base_tag, }, .positionals = .{ - .label = new_block.cast(Inst.Block).?.positionals.label, + .block = new_block, }, .kw_args = .{}, }; -- cgit v1.2.3