From 9751a0ae045110fb615c866b94ad47680b9c48c7 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Wed, 11 Jul 2018 19:38:01 -0400 Subject: std.atomic: use spinlocks the lock-free data structures all had ABA problems and std.atomic.Stack had a possibility to load an unmapped memory address. --- std/event/loop.zig | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'std/event/loop.zig') diff --git a/std/event/loop.zig b/std/event/loop.zig index 646f15875f..07575cf2e8 100644 --- a/std/event/loop.zig +++ b/std/event/loop.zig @@ -9,7 +9,7 @@ const AtomicOrder = builtin.AtomicOrder; pub const Loop = struct { allocator: *mem.Allocator, - next_tick_queue: std.atomic.QueueMpsc(promise), + next_tick_queue: std.atomic.Queue(promise), os_data: OsData, final_resume_node: ResumeNode, dispatch_lock: u8, // TODO make this a bool @@ -21,7 +21,7 @@ pub const Loop = struct { available_eventfd_resume_nodes: std.atomic.Stack(ResumeNode.EventFd), eventfd_resume_nodes: []std.atomic.Stack(ResumeNode.EventFd).Node, - pub const NextTickNode = std.atomic.QueueMpsc(promise).Node; + pub const NextTickNode = std.atomic.Queue(promise).Node; pub const ResumeNode = struct { id: Id, @@ -77,7 +77,7 @@ pub const Loop = struct { .pending_event_count = 0, .allocator = allocator, .os_data = undefined, - .next_tick_queue = std.atomic.QueueMpsc(promise).init(), + .next_tick_queue = std.atomic.Queue(promise).init(), .dispatch_lock = 1, // start locked so threads go directly into epoll wait .extra_threads = undefined, .available_eventfd_resume_nodes = std.atomic.Stack(ResumeNode.EventFd).init(), -- cgit v1.2.3 From e78b1b810fd15dfd135c80d06d621851a59f42c6 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Fri, 13 Jul 2018 21:56:38 -0400 Subject: self-hosted: basic IR pass2 --- src-self-hosted/errmsg.zig | 7 + src-self-hosted/ir.zig | 750 ++++++++++++++++++++++++++++++++++----------- src-self-hosted/main.zig | 2 +- src-self-hosted/module.zig | 85 +++-- src-self-hosted/type.zig | 33 ++ src-self-hosted/value.zig | 21 ++ std/event/loop.zig | 15 + 7 files changed, 708 insertions(+), 205 deletions(-) (limited to 'std/event/loop.zig') diff --git a/src-self-hosted/errmsg.zig b/src-self-hosted/errmsg.zig index a92b5145ce..4e353bfb14 100644 --- a/src-self-hosted/errmsg.zig +++ b/src-self-hosted/errmsg.zig @@ -14,6 +14,13 @@ pub const Color = enum { pub const Span = struct { first: ast.TokenIndex, last: ast.TokenIndex, + + pub fn token(i: TokenIndex) Span { + return Span { + .first = i, + .last = i, + }; + } }; pub const Msg = struct { diff --git a/src-self-hosted/ir.zig b/src-self-hosted/ir.zig index 19bb018472..22161a0c27 100644 --- a/src-self-hosted/ir.zig +++ b/src-self-hosted/ir.zig @@ -9,31 +9,34 @@ const Type = Value.Type; const assert = std.debug.assert; const Token = std.zig.Token; const ParsedFile = @import("parsed_file.zig").ParsedFile; +const Span = @import("errmsg.zig").Span; pub const LVal = enum { None, Ptr, }; -pub const Mut = enum { - Mut, - Const, -}; - -pub const Volatility = enum { - NonVolatile, - Volatile, -}; - pub const IrVal = union(enum) { Unknown, - Known: *Value, + KnownType: *Type, + KnownValue: *Value, + + const Init = enum { + Unknown, + NoReturn, + Void, + }; pub fn dump(self: IrVal) void { switch (self) { - IrVal.Unknown => std.debug.warn("Unknown"), - IrVal.Known => |value| { - std.debug.warn("Known("); + IrVal.Unknown => typeof.dump(), + IrVal.KnownType => |typeof| { + std.debug.warn("KnownType("); + typeof.dump(); + std.debug.warn(")"); + }, + IrVal.KnownValue => |value| { + std.debug.warn("KnownValue("); value.dump(); std.debug.warn(")"); }, @@ -46,10 +49,18 @@ pub const Instruction = struct { scope: *Scope, debug_id: usize, val: IrVal, + ref_count: usize, + span: Span, /// true if this instruction was generated by zig and not from user code is_generated: bool, + /// the instruction that is derived from this one in analysis + child: ?*Instruction, + + /// the instruction that this one derives from in analysis + parent: ?*Instruction, + pub fn cast(base: *Instruction, comptime T: type) ?*T { if (base.id == comptime typeToId(T)) { return @fieldParentPtr(T, "base", base); @@ -81,6 +92,47 @@ pub const Instruction = struct { unreachable; } + pub fn hasSideEffects(base: *const Instruction) bool { + comptime var i = 0; + inline while (i < @memberCount(Id)) : (i += 1) { + if (base.id == @field(Id, @memberName(Id, i))) { + const T = @field(Instruction, @memberName(Id, i)); + return @fieldParentPtr(T, "base", base).hasSideEffects(); + } + } + unreachable; + } + + pub fn analyze(base: *Instruction, ira: *Analyze) Analyze.Error!*Instruction { + comptime var i = 0; + inline while (i < @memberCount(Id)) : (i += 1) { + if (base.id == @field(Id, @memberName(Id, i))) { + const T = @field(Instruction, @memberName(Id, i)); + const new_inst = try @fieldParentPtr(T, "base", base).analyze(ira); + new_inst.linkToParent(base); + return new_inst; + } + } + unreachable; + } + + fn getAsParam(param: *Instruction) !*Instruction { + const child = param.child orelse return error.SemanticAnalysisFailed; + switch (child.val) { + IrVal.Unknown => return error.SemanticAnalysisFailed, + else => return child, + } + } + + /// asserts that the type is known + fn getKnownType(self: *Instruction) *Type { + switch (self.val) { + IrVal.KnownType => |typeof| return typeof, + IrVal.KnownValue => |value| return value.typeof, + IrVal.Unknown => unreachable, + } + } + pub fn setGenerated(base: *Instruction) void { base.is_generated = true; } @@ -88,10 +140,18 @@ pub const Instruction = struct { pub fn isNoReturn(base: *const Instruction) bool { switch (base.val) { IrVal.Unknown => return false, - IrVal.Known => |x| return x.typeof.id == Type.Id.NoReturn, + IrVal.KnownValue => |x| return x.typeof.id == Type.Id.NoReturn, + IrVal.KnownType => |typeof| return typeof.id == Type.Id.NoReturn, } } + pub fn linkToParent(self: *Instruction, parent: *Instruction) void { + assert(self.parent == null); + assert(parent.child == null); + self.parent = parent; + parent.child = self; + } + pub const Id = enum { Return, Const, @@ -100,196 +160,231 @@ pub const Instruction = struct { CheckVoidStmt, Phi, Br, + AddImplicitReturnType, }; pub const Const = struct { base: Instruction, + params: Params, - pub fn buildBool(irb: *Builder, scope: *Scope, val: bool) !*Instruction { - const inst = try irb.arena().create(Const{ - .base = Instruction{ - .id = Instruction.Id.Const, - .is_generated = false, - .scope = scope, - .debug_id = irb.next_debug_id, - .val = IrVal{ .Known = &Value.Bool.get(irb.module, val).base }, - }, - }); - irb.next_debug_id += 1; - try irb.current_basic_block.instruction_list.append(&inst.base); - return &inst.base; - } - - pub fn buildVoid(irb: *Builder, scope: *Scope, is_generated: bool) !*Instruction { - const inst = try irb.arena().create(Const{ - .base = Instruction{ - .id = Instruction.Id.Const, - .is_generated = is_generated, - .scope = scope, - .debug_id = irb.next_debug_id, - .val = IrVal{ .Known = &Value.Void.get(irb.module).base }, - }, - }); - irb.next_debug_id += 1; - try irb.current_basic_block.instruction_list.append(&inst.base); - return &inst.base; + const Params = struct {}; + + // Use Builder.buildConst* methods, or, after building a Const instruction, + // manually set the ir_val field. + const ir_val_init = IrVal.Init.Unknown; + + pub fn dump(self: *const Const) void { + self.base.val.KnownValue.dump(); } - pub fn dump(inst: *const Const) void { - inst.base.val.Known.dump(); + pub fn hasSideEffects(self: *const Const) bool { + return false; + } + + pub fn analyze(self: *const Const, ira: *Analyze) !*Instruction { + const new_inst = try ira.irb.build(Const, self.base.scope, self.base.span, Params{}); + new_inst.val = IrVal{ .KnownValue = self.base.val.KnownValue.getRef() }; + return new_inst; } }; pub const Return = struct { base: Instruction, - return_value: *Instruction, - - pub fn build(irb: *Builder, scope: *Scope, return_value: *Instruction) !*Instruction { - const inst = try irb.arena().create(Return{ - .base = Instruction{ - .id = Instruction.Id.Return, - .is_generated = false, - .scope = scope, - .debug_id = irb.next_debug_id, - .val = IrVal{ .Known = &Value.Void.get(irb.module).base }, - }, - .return_value = return_value, - }); - irb.next_debug_id += 1; - try irb.current_basic_block.instruction_list.append(&inst.base); - return &inst.base; + params: Params, + + const Params = struct { + return_value: *Instruction, + }; + + const ir_val_init = IrVal.Init.NoReturn; + + pub fn dump(self: *const Return) void { + std.debug.warn("#{}", self.params.return_value.debug_id); } - pub fn dump(inst: *const Return) void { - std.debug.warn("#{}", inst.return_value.debug_id); + pub fn hasSideEffects(self: *const Return) bool { + return true; + } + + pub fn analyze(self: *const Return, ira: *Analyze) !*Instruction { + const value = try self.params.return_value.getAsParam(); + const casted_value = try ira.implicitCast(value, ira.explicit_return_type); + + // TODO detect returning local variable address + + return ira.irb.build(Return, self.base.scope, self.base.span, Params{ .return_value = casted_value }); } }; pub const Ref = struct { base: Instruction, - target: *Instruction, - mut: Mut, - volatility: Volatility, + params: Params, - pub fn build( - irb: *Builder, - scope: *Scope, + const Params = struct { target: *Instruction, - mut: Mut, - volatility: Volatility, - ) !*Instruction { - const inst = try irb.arena().create(Ref{ - .base = Instruction{ - .id = Instruction.Id.Ref, - .is_generated = false, - .scope = scope, - .debug_id = irb.next_debug_id, - .val = IrVal.Unknown, - }, + mut: Type.Pointer.Mut, + volatility: Type.Pointer.Vol, + }; + + const ir_val_init = IrVal.Init.Unknown; + + pub fn dump(inst: *const Ref) void {} + + pub fn hasSideEffects(inst: *const Ref) bool { + return false; + } + + pub fn analyze(self: *const Ref, ira: *Analyze) !*Instruction { + const target = try self.params.target.getAsParam(); + + if (ira.getCompTimeValOrNullUndefOk(target)) |val| { + return ira.getCompTimeRef( + val, + Value.Ptr.Mut.CompTimeConst, + self.params.mut, + self.params.volatility, + val.typeof.getAbiAlignment(ira.irb.module), + ); + } + + const new_inst = try ira.irb.build(Ref, self.base.scope, self.base.span, Params{ .target = target, - .mut = mut, - .volatility = volatility, + .mut = self.params.mut, + .volatility = self.params.volatility, }); - irb.next_debug_id += 1; - try irb.current_basic_block.instruction_list.append(&inst.base); - return &inst.base; + const elem_type = target.getKnownType(); + const ptr_type = Type.Pointer.get( + ira.irb.module, + elem_type, + self.params.mut, + self.params.volatility, + Type.Pointer.Size.One, + elem_type.getAbiAlignment(ira.irb.module), + ); + // TODO: potentially set the hint that this is a stack pointer. But it might not be - this + // could be a ref of a global, for example + new_inst.val = IrVal{ .KnownType = &ptr_type.base }; + // TODO potentially add an alloca entry here + return new_inst; } - - pub fn dump(inst: *const Ref) void {} }; pub const DeclVar = struct { base: Instruction, - variable: *Variable, + params: Params, + + const Params = struct { + variable: *Variable, + }; + + const ir_val_init = IrVal.Init.Unknown; pub fn dump(inst: *const DeclVar) void {} + + pub fn hasSideEffects(inst: *const DeclVar) bool { + return true; + } + + pub fn analyze(self: *const DeclVar, ira: *Analyze) !*Instruction { + return error.Unimplemented; // TODO + } }; pub const CheckVoidStmt = struct { base: Instruction, - target: *Instruction, + params: Params, - pub fn build( - irb: *Builder, - scope: *Scope, + const Params = struct { target: *Instruction, - ) !*Instruction { - const inst = try irb.arena().create(CheckVoidStmt{ - .base = Instruction{ - .id = Instruction.Id.CheckVoidStmt, - .is_generated = true, - .scope = scope, - .debug_id = irb.next_debug_id, - .val = IrVal{ .Known = &Value.Void.get(irb.module).base }, - }, - .target = target, - }); - irb.next_debug_id += 1; - try irb.current_basic_block.instruction_list.append(&inst.base); - return &inst.base; - } + }; + + const ir_val_init = IrVal.Init.Unknown; pub fn dump(inst: *const CheckVoidStmt) void {} + + pub fn hasSideEffects(inst: *const CheckVoidStmt) bool { + return true; + } + + pub fn analyze(self: *const CheckVoidStmt, ira: *Analyze) !*Instruction { + return error.Unimplemented; // TODO + } }; pub const Phi = struct { base: Instruction, - incoming_blocks: []*BasicBlock, - incoming_values: []*Instruction, + params: Params, - pub fn build( - irb: *Builder, - scope: *Scope, + const Params = struct { incoming_blocks: []*BasicBlock, incoming_values: []*Instruction, - ) !*Instruction { - const inst = try irb.arena().create(Phi{ - .base = Instruction{ - .id = Instruction.Id.Phi, - .is_generated = false, - .scope = scope, - .debug_id = irb.next_debug_id, - .val = IrVal.Unknown, - }, - .incoming_blocks = incoming_blocks, - .incoming_values = incoming_values, - }); - irb.next_debug_id += 1; - try irb.current_basic_block.instruction_list.append(&inst.base); - return &inst.base; - } + }; + + const ir_val_init = IrVal.Init.Unknown; pub fn dump(inst: *const Phi) void {} + + pub fn hasSideEffects(inst: *const Phi) bool { + return false; + } + + pub fn analyze(self: *const Phi, ira: *Analyze) !*Instruction { + return error.Unimplemented; // TODO + } }; pub const Br = struct { base: Instruction, - dest_block: *BasicBlock, - is_comptime: *Instruction, + params: Params, - pub fn build( - irb: *Builder, - scope: *Scope, + const Params = struct { dest_block: *BasicBlock, is_comptime: *Instruction, - ) !*Instruction { - const inst = try irb.arena().create(Br{ - .base = Instruction{ - .id = Instruction.Id.Br, - .is_generated = false, - .scope = scope, - .debug_id = irb.next_debug_id, - .val = IrVal{ .Known = &Value.NoReturn.get(irb.module).base }, - }, - .dest_block = dest_block, - .is_comptime = is_comptime, - }); - irb.next_debug_id += 1; - try irb.current_basic_block.instruction_list.append(&inst.base); - return &inst.base; - } + }; + + const ir_val_init = IrVal.Init.NoReturn; pub fn dump(inst: *const Br) void {} + + pub fn hasSideEffects(inst: *const Br) bool { + return true; + } + + pub fn analyze(self: *const Br, ira: *Analyze) !*Instruction { + return error.Unimplemented; // TODO + } + }; + + pub const AddImplicitReturnType = struct { + base: Instruction, + params: Params, + + pub const Params = struct { + target: *Instruction, + }; + + const ir_val_init = IrVal.Init.Unknown; + + pub fn dump(inst: *const AddImplicitReturnType) void { + std.debug.warn("#{}", inst.params.target.debug_id); + } + + pub fn hasSideEffects(inst: *const AddImplicitReturnType) bool { + return true; + } + + pub fn analyze(self: *const AddImplicitReturnType, ira: *Analyze) !*Instruction { + const target = try self.params.target.getAsParam(); + + try ira.src_implicit_return_type_list.append(target); + + return ira.irb.build( + AddImplicitReturnType, + self.base.scope, + self.base.span, + Params{ .target = target }, + ); + } }; }; @@ -303,16 +398,31 @@ pub const BasicBlock = struct { debug_id: usize, scope: *Scope, instruction_list: std.ArrayList(*Instruction), + ref_instruction: ?*Instruction, + + /// the basic block that is derived from this one in analysis + child: ?*BasicBlock, + + /// the basic block that this one derives from in analysis + parent: ?*BasicBlock, pub fn ref(self: *BasicBlock) void { self.ref_count += 1; } + + pub fn linkToParent(self: *BasicBlock, parent: *BasicBlock) void { + assert(self.parent == null); + assert(parent.child == null); + self.parent = parent; + parent.child = self; + } }; /// Stuff that survives longer than Builder pub const Code = struct { basic_block_list: std.ArrayList(*BasicBlock), arena: std.heap.ArenaAllocator, + return_type: ?*Type, /// allocator is module.a() pub fn destroy(self: *Code, allocator: *Allocator) void { @@ -341,15 +451,13 @@ pub const Builder = struct { parsed_file: *ParsedFile, is_comptime: bool, - pub const Error = error{ - OutOfMemory, - Unimplemented, - }; + pub const Error = Analyze.Error; pub fn init(module: *Module, parsed_file: *ParsedFile) !Builder { const code = try module.a().create(Code{ .basic_block_list = undefined, .arena = std.heap.ArenaAllocator.init(module.a()), + .return_type = null, }); code.basic_block_list = std.ArrayList(*BasicBlock).init(&code.arena.allocator); errdefer code.destroy(module.a()); @@ -381,6 +489,9 @@ pub const Builder = struct { .debug_id = self.next_debug_id, .scope = scope, .instruction_list = std.ArrayList(*Instruction).init(self.arena()), + .child = null, + .parent = null, + .ref_instruction = null, }); self.next_debug_id += 1; return basic_block; @@ -490,14 +601,18 @@ pub const Builder = struct { if (block.statements.len == 0) { // {} - return Instruction.Const.buildVoid(irb, child_scope, false); + return irb.buildConstVoid(child_scope, Span.token(block.lbrace), false); } if (block.label) |label| { block_scope.incoming_values = std.ArrayList(*Instruction).init(irb.arena()); block_scope.incoming_blocks = std.ArrayList(*BasicBlock).init(irb.arena()); block_scope.end_block = try irb.createBasicBlock(parent_scope, "BlockEnd"); - block_scope.is_comptime = try Instruction.Const.buildBool(irb, parent_scope, irb.isCompTime(parent_scope)); + block_scope.is_comptime = try irb.buildConstBool( + parent_scope, + Span.token(block.lbrace), + irb.isCompTime(parent_scope), + ); } var is_continuation_unreachable = false; @@ -530,10 +645,15 @@ pub const Builder = struct { if (statement_value.cast(Instruction.DeclVar)) |decl_var| { // variable declarations start a new scope - child_scope = decl_var.variable.child_scope; + child_scope = decl_var.params.variable.child_scope; } else if (!is_continuation_unreachable) { // this statement's value must be void - _ = Instruction.CheckVoidStmt.build(irb, child_scope, statement_value); + _ = irb.build( + Instruction.CheckVoidStmt, + child_scope, + statement_value.span, + Instruction.CheckVoidStmt.Params{ .target = statement_value }, + ); } } @@ -544,37 +664,34 @@ pub const Builder = struct { } try irb.setCursorAtEndAndAppendBlock(block_scope.end_block); - return Instruction.Phi.build( - irb, - parent_scope, - block_scope.incoming_blocks.toOwnedSlice(), - block_scope.incoming_values.toOwnedSlice(), - ); + return irb.build(Instruction.Phi, parent_scope, Span.token(block.rbrace), Instruction.Phi.Params{ + .incoming_blocks = block_scope.incoming_blocks.toOwnedSlice(), + .incoming_values = block_scope.incoming_values.toOwnedSlice(), + }); } if (block.label) |label| { try block_scope.incoming_blocks.append(irb.current_basic_block); try block_scope.incoming_values.append( - try Instruction.Const.buildVoid(irb, parent_scope, true), + try irb.buildConstVoid(parent_scope, Span.token(block.rbrace), true), ); _ = try irb.genDefersForBlock(child_scope, outer_block_scope, Scope.Defer.Kind.ScopeExit); - (try Instruction.Br.build( - irb, - parent_scope, - block_scope.end_block, - block_scope.is_comptime, - )).setGenerated(); + + _ = try irb.buildGen(Instruction.Br, parent_scope, Span.token(block.rbrace), Instruction.Br.Params{ + .dest_block = block_scope.end_block, + .is_comptime = block_scope.is_comptime, + }); + try irb.setCursorAtEndAndAppendBlock(block_scope.end_block); - return Instruction.Phi.build( - irb, - parent_scope, - block_scope.incoming_blocks.toOwnedSlice(), - block_scope.incoming_values.toOwnedSlice(), - ); + + return irb.build(Instruction.Phi, parent_scope, Span.token(block.rbrace), Instruction.Phi.Params{ + .incoming_blocks = block_scope.incoming_blocks.toOwnedSlice(), + .incoming_values = block_scope.incoming_values.toOwnedSlice(), + }); } _ = try irb.genDefersForBlock(child_scope, outer_block_scope, Scope.Defer.Kind.ScopeExit); - return try Instruction.Const.buildVoid(irb, child_scope, true); + return irb.buildConstVoid(child_scope, Span.token(block.rbrace), true); } fn genDefersForBlock( @@ -603,7 +720,12 @@ pub const Builder = struct { if (instruction.isNoReturn()) { is_noreturn = true; } else { - _ = Instruction.CheckVoidStmt.build(irb, &defer_expr_scope.base, instruction); + _ = try irb.build( + Instruction.CheckVoidStmt, + &defer_expr_scope.base, + Span.token(defer_expr_scope.expr_node.lastToken()), + Instruction.CheckVoidStmt.Params{ .target = instruction }, + ); } } }, @@ -626,7 +748,11 @@ pub const Builder = struct { LVal.Ptr => { // We needed a pointer to a value, but we got a value. So we create // an instruction which just makes a const pointer of it. - return Instruction.Ref.build(irb, scope, instruction, Mut.Const, Volatility.NonVolatile); + return irb.build(Instruction.Ref, scope, instruction.span, Instruction.Ref.Params{ + .target = instruction, + .mut = Type.Pointer.Mut.Const, + .volatility = Type.Pointer.Vol.Non, + }); }, } } @@ -634,9 +760,218 @@ pub const Builder = struct { fn arena(self: *Builder) *Allocator { return &self.code.arena.allocator; } + + fn buildExtra( + self: *Builder, + comptime I: type, + scope: *Scope, + span: Span, + params: I.Params, + is_generated: bool, + ) !*Instruction { + const inst = try self.arena().create(I{ + .base = Instruction{ + .id = Instruction.typeToId(I), + .is_generated = is_generated, + .scope = scope, + .debug_id = self.next_debug_id, + .val = switch (I.ir_val_init) { + IrVal.Init.Unknown => IrVal.Unknown, + IrVal.Init.NoReturn => IrVal{ .KnownValue = &Value.NoReturn.get(self.module).base }, + IrVal.Init.Void => IrVal{ .KnownValue = &Value.Void.get(self.module).base }, + }, + .ref_count = 0, + .span = span, + .child = null, + .parent = null, + }, + .params = params, + }); + + // Look at the params and ref() other instructions + comptime var i = 0; + inline while (i < @memberCount(I.Params)) : (i += 1) { + const FieldType = comptime @typeOf(@field(I.Params(undefined), @memberName(I.Params, i))); + switch (FieldType) { + *Instruction => @field(inst.params, @memberName(I.Params, i)).ref_count += 1, + ?*Instruction => if (@field(inst.params, @memberName(I.Params, i))) |other| other.ref_count += 1, + else => {}, + } + } + + self.next_debug_id += 1; + try self.current_basic_block.instruction_list.append(&inst.base); + return &inst.base; + } + + fn build( + self: *Builder, + comptime I: type, + scope: *Scope, + span: Span, + params: I.Params, + ) !*Instruction { + return self.buildExtra(I, scope, span, params, false); + } + + fn buildGen( + self: *Builder, + comptime I: type, + scope: *Scope, + span: Span, + params: I.Params, + ) !*Instruction { + return self.buildExtra(I, scope, span, params, true); + } + + fn buildConstBool(self: *Builder, scope: *Scope, span: Span, x: bool) !*Instruction { + const inst = try self.build(Instruction.Const, scope, span, Instruction.Const.Params{}); + inst.val = IrVal{ .KnownValue = &Value.Bool.get(self.module, x).base }; + return inst; + } + + fn buildConstVoid(self: *Builder, scope: *Scope, span: Span, is_generated: bool) !*Instruction { + const inst = try self.buildExtra(Instruction.Const, scope, span, Instruction.Const.Params{}, is_generated); + inst.val = IrVal{ .KnownValue = &Value.Void.get(self.module).base }; + return inst; + } +}; + +const Analyze = struct { + irb: Builder, + old_bb_index: usize, + const_predecessor_bb: ?*BasicBlock, + parent_basic_block: *BasicBlock, + instruction_index: usize, + src_implicit_return_type_list: std.ArrayList(*Instruction), + explicit_return_type: ?*Type, + + pub const Error = error{ + /// This is only for when we have already reported a compile error. It is the poison value. + SemanticAnalysisFailed, + + /// This is a placeholder - it is useful to use instead of panicking but once the compiler is + /// done this error code will be removed. + Unimplemented, + + OutOfMemory, + }; + + pub fn init(module: *Module, parsed_file: *ParsedFile, explicit_return_type: ?*Type) !Analyze { + var irb = try Builder.init(module, parsed_file); + errdefer irb.abort(); + + return Analyze{ + .irb = irb, + .old_bb_index = 0, + .const_predecessor_bb = null, + .parent_basic_block = undefined, // initialized with startBasicBlock + .instruction_index = undefined, // initialized with startBasicBlock + .src_implicit_return_type_list = std.ArrayList(*Instruction).init(irb.arena()), + .explicit_return_type = explicit_return_type, + }; + } + + pub fn abort(self: *Analyze) void { + self.irb.abort(); + } + + pub fn getNewBasicBlock(self: *Analyze, old_bb: *BasicBlock, ref_old_instruction: ?*Instruction) !*BasicBlock { + if (old_bb.child) |child| { + if (ref_old_instruction == null or child.ref_instruction != ref_old_instruction) + return child; + } + + const new_bb = try self.irb.createBasicBlock(old_bb.scope, old_bb.name_hint); + new_bb.linkToParent(old_bb); + new_bb.ref_instruction = ref_old_instruction; + return new_bb; + } + + pub fn startBasicBlock(self: *Analyze, old_bb: *BasicBlock, const_predecessor_bb: ?*BasicBlock) void { + self.instruction_index = 0; + self.parent_basic_block = old_bb; + self.const_predecessor_bb = const_predecessor_bb; + } + + pub fn finishBasicBlock(ira: *Analyze, old_code: *Code) !void { + try ira.irb.code.basic_block_list.append(ira.irb.current_basic_block); + ira.instruction_index += 1; + + while (ira.instruction_index < ira.parent_basic_block.instruction_list.len) { + const next_instruction = ira.parent_basic_block.instruction_list.at(ira.instruction_index); + + if (!next_instruction.is_generated) { + try ira.addCompileError(next_instruction.span, "unreachable code"); + break; + } + ira.instruction_index += 1; + } + + ira.old_bb_index += 1; + + var need_repeat = true; + while (true) { + while (ira.old_bb_index < old_code.basic_block_list.len) { + const old_bb = old_code.basic_block_list.at(ira.old_bb_index); + const new_bb = old_bb.child orelse { + ira.old_bb_index += 1; + continue; + }; + if (new_bb.instruction_list.len != 0) { + ira.old_bb_index += 1; + continue; + } + ira.irb.current_basic_block = new_bb; + + ira.startBasicBlock(old_bb, null); + return; + } + if (!need_repeat) + return; + need_repeat = false; + ira.old_bb_index = 0; + continue; + } + } + + fn addCompileError(self: *Analyze, span: Span, comptime fmt: []const u8, args: ...) !void { + return self.irb.module.addCompileError(self.irb.parsed_file, span, fmt, args); + } + + fn resolvePeerTypes(self: *Analyze, expected_type: ?*Type, peers: []const *Instruction) Analyze.Error!*Type { + // TODO actual implementation + return &Type.Void.get(self.irb.module).base; + } + + fn implicitCast(self: *Analyze, target: *Instruction, optional_dest_type: ?*Type) Analyze.Error!*Instruction { + const dest_type = optional_dest_type orelse return target; + @panic("TODO implicitCast"); + } + + fn getCompTimeValOrNullUndefOk(self: *Analyze, target: *Instruction) ?*Value { + @panic("TODO getCompTimeValOrNullUndefOk"); + } + + fn getCompTimeRef( + self: *Analyze, + value: *Value, + ptr_mut: Value.Ptr.Mut, + mut: Type.Pointer.Mut, + volatility: Type.Pointer.Vol, + ptr_align: u32, + ) Analyze.Error!*Instruction { + @panic("TODO getCompTimeRef"); + } }; -pub async fn gen(module: *Module, body_node: *ast.Node, scope: *Scope, parsed_file: *ParsedFile) !*Code { +pub async fn gen( + module: *Module, + body_node: *ast.Node, + scope: *Scope, + end_span: Span, + parsed_file: *ParsedFile, +) !*Code { var irb = try Builder.init(module, parsed_file); errdefer irb.abort(); @@ -646,8 +981,61 @@ pub async fn gen(module: *Module, body_node: *ast.Node, scope: *Scope, parsed_fi const result = try irb.genNode(body_node, scope, LVal.None); if (!result.isNoReturn()) { - (try Instruction.Return.build(&irb, scope, result)).setGenerated(); + _ = irb.buildGen( + Instruction.AddImplicitReturnType, + scope, + end_span, + Instruction.AddImplicitReturnType.Params{ .target = result }, + ); + _ = irb.buildGen( + Instruction.Return, + scope, + end_span, + Instruction.Return.Params{ .return_value = result }, + ); } return irb.finish(); } + +pub async fn analyze(module: *Module, parsed_file: *ParsedFile, old_code: *Code, expected_type: ?*Type) !*Code { + var ira = try Analyze.init(module, parsed_file, expected_type); + errdefer ira.abort(); + + const old_entry_bb = old_code.basic_block_list.at(0); + + const new_entry_bb = try ira.getNewBasicBlock(old_entry_bb, null); + new_entry_bb.ref(); + + ira.irb.current_basic_block = new_entry_bb; + + ira.startBasicBlock(old_entry_bb, null); + + while (ira.old_bb_index < old_code.basic_block_list.len) { + const old_instruction = ira.parent_basic_block.instruction_list.at(ira.instruction_index); + + if (old_instruction.ref_count == 0 and !old_instruction.hasSideEffects()) { + ira.instruction_index += 1; + continue; + } + + const return_inst = try old_instruction.analyze(&ira); + // Note: if we ever modify the above to handle error.CompileError by continuing analysis, + // then here we want to check if ira.isCompTime() and return early if true + + if (return_inst.isNoReturn()) { + try ira.finishBasicBlock(old_code); + continue; + } + + ira.instruction_index += 1; + } + + if (ira.src_implicit_return_type_list.len == 0) { + ira.irb.code.return_type = &Type.NoReturn.get(module).base; + return ira.irb.finish(); + } + + ira.irb.code.return_type = try ira.resolvePeerTypes(expected_type, ira.src_implicit_return_type_list.toSliceConst()); + return ira.irb.finish(); +} diff --git a/src-self-hosted/main.zig b/src-self-hosted/main.zig index d7ead0ba32..058459a2d8 100644 --- a/src-self-hosted/main.zig +++ b/src-self-hosted/main.zig @@ -497,7 +497,7 @@ async fn processBuildEvents(module: *Module, color: errmsg.Color) void { }, Module.Event.Error => |err| { std.debug.warn("build failed: {}\n", @errorName(err)); - @panic("TODO error return trace"); + os.exit(1); }, Module.Event.Fail => |msgs| { for (msgs) |msg| { diff --git a/src-self-hosted/module.zig b/src-self-hosted/module.zig index e74c84e02c..3fbe6d54ad 100644 --- a/src-self-hosted/module.zig +++ b/src-self-hosted/module.zig @@ -24,6 +24,7 @@ const Visib = @import("visib.zig").Visib; const ParsedFile = @import("parsed_file.zig").ParsedFile; const Value = @import("value.zig").Value; const Type = Value.Type; +const Span = errmsg.Span; pub const Module = struct { loop: *event.Loop, @@ -148,13 +149,14 @@ pub const Module = struct { Overflow, NotSupported, BufferTooSmall, - Unimplemented, + Unimplemented, // TODO remove this one + SemanticAnalysisFailed, // TODO remove this one }; pub const Event = union(enum) { Ok, - Fail: []*errmsg.Msg, Error: BuildError, + Fail: []*errmsg.Msg, }; pub const DarwinVersionMin = union(enum) { @@ -413,21 +415,32 @@ pub const Module = struct { while (true) { // TODO directly awaiting async should guarantee memory allocation elision // TODO also async before suspending should guarantee memory allocation elision - (await (async self.addRootSrc() catch unreachable)) catch |err| { - await (async self.events.put(Event{ .Error = err }) catch unreachable); - return; - }; + const build_result = await (async self.addRootSrc() catch unreachable); + + // this makes a handy error return trace and stack trace in debug mode + if (std.debug.runtime_safety) { + build_result catch unreachable; + } + const compile_errors = blk: { const held = await (async self.compile_errors.acquire() catch unreachable); defer held.release(); break :blk held.value.toOwnedSlice(); }; - if (compile_errors.len == 0) { - await (async self.events.put(Event.Ok) catch unreachable); - } else { - await (async self.events.put(Event{ .Fail = compile_errors }) catch unreachable); + if (build_result) |_| { + if (compile_errors.len == 0) { + await (async self.events.put(Event.Ok) catch unreachable); + } else { + await (async self.events.put(Event{ .Fail = compile_errors }) catch unreachable); + } + } else |err| { + // if there's an error then the compile errors have dangling references + self.a().free(compile_errors); + + await (async self.events.put(Event{ .Error = err }) catch unreachable); } + // for now we stop after 1 return; } @@ -477,7 +490,7 @@ pub const Module = struct { const fn_proto = @fieldParentPtr(ast.Node.FnProto, "base", decl); const name = if (fn_proto.name_token) |name_token| tree.tokenSlice(name_token) else { - try self.addCompileError(parsed_file, errmsg.Span{ + try self.addCompileError(parsed_file, Span{ .first = fn_proto.fn_token, .last = fn_proto.fn_token + 1, }, "missing function name"); @@ -518,27 +531,23 @@ pub const Module = struct { } } - fn addCompileError(self: *Module, parsed_file: *ParsedFile, span: errmsg.Span, comptime fmt: []const u8, args: ...) !void { + fn addCompileError(self: *Module, parsed_file: *ParsedFile, span: Span, comptime fmt: []const u8, args: ...) !void { const text = try std.fmt.allocPrint(self.loop.allocator, fmt, args); errdefer self.loop.allocator.free(text); - try self.build_group.call(addCompileErrorAsync, self, parsed_file, span.first, span.last, text); + try self.build_group.call(addCompileErrorAsync, self, parsed_file, span, text); } async fn addCompileErrorAsync( self: *Module, parsed_file: *ParsedFile, - first_token: ast.TokenIndex, - last_token: ast.TokenIndex, + span: Span, text: []u8, ) !void { const msg = try self.loop.allocator.create(errmsg.Msg{ .path = parsed_file.realpath, .text = text, - .span = errmsg.Span{ - .first = first_token, - .last = last_token, - }, + .span = span, .tree = &parsed_file.tree, }); errdefer self.loop.allocator.destroy(msg); @@ -624,6 +633,7 @@ pub async fn resolveDecl(module: *Module, decl: *Decl) !void { if (@atomicRmw(u8, &decl.resolution_in_progress, AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst) == 0) { decl.resolution.data = await (async generateDecl(module, decl) catch unreachable); decl.resolution.resolve(); + return decl.resolution.data; } else { return (await (async decl.resolution.get() catch unreachable)).*; } @@ -655,12 +665,41 @@ async fn generateDeclFn(module: *Module, fn_decl: *Decl.Fn) !void { fn_decl.value = Decl.Fn.Val{ .Ok = fn_val }; - const code = try await (async ir.gen( + const unanalyzed_code = (await (async ir.gen( module, body_node, &fndef_scope.base, + Span.token(body_node.lastToken()), + fn_decl.base.parsed_file, + ) catch unreachable)) catch |err| switch (err) { + // This poison value should not cause the errdefers to run. It simply means + // that self.compile_errors is populated. + error.SemanticAnalysisFailed => return {}, + else => return err, + }; + defer unanalyzed_code.destroy(module.a()); + + if (module.verbose_ir) { + std.debug.warn("unanalyzed:\n"); + unanalyzed_code.dump(); + } + + const analyzed_code = (await (async ir.analyze( + module, fn_decl.base.parsed_file, - ) catch unreachable); - //code.dump(); - //try await (async irAnalyze(module, func) catch unreachable); + unanalyzed_code, + null, + ) catch unreachable)) catch |err| switch (err) { + // This poison value should not cause the errdefers to run. It simply means + // that self.compile_errors is populated. + error.SemanticAnalysisFailed => return {}, + else => return err, + }; + defer analyzed_code.destroy(module.a()); + + if (module.verbose_ir) { + std.debug.warn("analyzed:\n"); + analyzed_code.dump(); + } + // TODO now render to LLVM module } diff --git a/src-self-hosted/type.zig b/src-self-hosted/type.zig index 4b3918854d..66e1470cc0 100644 --- a/src-self-hosted/type.zig +++ b/src-self-hosted/type.zig @@ -39,6 +39,14 @@ pub const Type = struct { } } + pub fn dump(base: *const Type) void { + std.debug.warn("{}", @tagName(base.id)); + } + + pub fn getAbiAlignment(base: *Type, module: *Module) u32 { + @panic("TODO getAbiAlignment"); + } + pub const Struct = struct { base: Type, decls: *Scope.Decls, @@ -143,10 +151,35 @@ pub const Type = struct { }; pub const Pointer = struct { base: Type, + mut: Mut, + vol: Vol, + size: Size, + alignment: u32, + + pub const Mut = enum { + Mut, + Const, + }; + pub const Vol = enum { + Non, + Volatile, + }; + pub const Size = builtin.TypeInfo.Pointer.Size; pub fn destroy(self: *Pointer, module: *Module) void { module.a().destroy(self); } + + pub fn get( + module: *Module, + elem_type: *Type, + mut: Mut, + vol: Vol, + size: Size, + alignment: u32, + ) *Pointer { + @panic("TODO get pointer"); + } }; pub const Array = struct { base: Type, diff --git a/src-self-hosted/value.zig b/src-self-hosted/value.zig index b53d03d0ad..7ee594b41c 100644 --- a/src-self-hosted/value.zig +++ b/src-self-hosted/value.zig @@ -24,10 +24,16 @@ pub const Value = struct { Id.Void => @fieldParentPtr(Void, "base", base).destroy(module), Id.Bool => @fieldParentPtr(Bool, "base", base).destroy(module), Id.NoReturn => @fieldParentPtr(NoReturn, "base", base).destroy(module), + Id.Ptr => @fieldParentPtr(Ptr, "base", base).destroy(module), } } } + pub fn getRef(base: *Value) *Value { + base.ref(); + return base; + } + pub fn dump(base: *const Value) void { std.debug.warn("{}", @tagName(base.id)); } @@ -38,6 +44,7 @@ pub const Value = struct { Void, Bool, NoReturn, + Ptr, }; pub const Type = @import("type.zig").Type; @@ -122,4 +129,18 @@ pub const Value = struct { module.a().destroy(self); } }; + + pub const Ptr = struct { + base: Value, + + pub const Mut = enum { + CompTimeConst, + CompTimeVar, + RunTime, + }; + + pub fn destroy(self: *Ptr, module: *Module) void { + module.a().destroy(self); + } + }; }; diff --git a/std/event/loop.zig b/std/event/loop.zig index 07575cf2e8..ba75109a72 100644 --- a/std/event/loop.zig +++ b/std/event/loop.zig @@ -382,6 +382,21 @@ pub const Loop = struct { return async S.asyncFunc(self, &handle, args); } + /// Awaiting a yield lets the event loop run, starting any unstarted async operations. + /// Note that async operations automatically start when a function yields for any other reason, + /// for example, when async I/O is performed. This function is intended to be used only when + /// CPU bound tasks would be waiting in the event loop but never get started because no async I/O + /// is performed. + pub async fn yield(self: *Loop) void { + suspend |p| { + var my_tick_node = Loop.NextTickNode{ + .next = undefined, + .data = p, + }; + loop.onNextTick(&my_tick_node); + } + } + fn workerRun(self: *Loop) void { start_over: while (true) { if (@atomicRmw(u8, &self.dispatch_lock, AtomicRmwOp.Xchg, 1, AtomicOrder.SeqCst) == 0) { -- cgit v1.2.3 From 278829fc2cc23e55b09915ce07ce1ec2dbf7e68b Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Sat, 14 Jul 2018 15:45:15 -0400 Subject: self-hosted: adding a fn to an llvm module --- src-self-hosted/codegen.zig | 61 ++++++++++++++++++ src-self-hosted/ir.zig | 9 +-- src-self-hosted/llvm.zig | 23 ++++++- src-self-hosted/main.zig | 7 ++- src-self-hosted/module.zig | 112 ++++++++++++++++++++++----------- src-self-hosted/test.zig | 11 +++- src-self-hosted/type.zig | 147 +++++++++++++++++++++++++++++++++++++++++++- src-self-hosted/value.zig | 20 ++++-- std/atomic/int.zig | 18 ++++-- std/event/loop.zig | 1 - 10 files changed, 346 insertions(+), 63 deletions(-) create mode 100644 src-self-hosted/codegen.zig (limited to 'std/event/loop.zig') diff --git a/src-self-hosted/codegen.zig b/src-self-hosted/codegen.zig new file mode 100644 index 0000000000..df8f451856 --- /dev/null +++ b/src-self-hosted/codegen.zig @@ -0,0 +1,61 @@ +const std = @import("std"); +// TODO codegen pretends that Module is renamed to Build because I plan to +// do that refactor at some point +const Build = @import("module.zig").Module; +// we go through llvm instead of c for 2 reasons: +// 1. to avoid accidentally calling the non-thread-safe functions +// 2. patch up some of the types to remove nullability +const llvm = @import("llvm.zig"); +const ir = @import("ir.zig"); +const Value = @import("value.zig").Value; +const Type = @import("type.zig").Type; +const event = std.event; + +pub async fn renderToLlvm(build: *Build, fn_val: *Value.Fn, code: *ir.Code) !void { + fn_val.base.ref(); + defer fn_val.base.deref(build); + defer code.destroy(build.a()); + + const llvm_handle = try build.event_loop_local.getAnyLlvmContext(); + defer llvm_handle.release(build.event_loop_local); + + const context = llvm_handle.node.data; + + const module = llvm.ModuleCreateWithNameInContext(build.name.ptr(), context) orelse return error.OutOfMemory; + defer llvm.DisposeModule(module); + + const builder = llvm.CreateBuilderInContext(context) orelse return error.OutOfMemory; + defer llvm.DisposeBuilder(builder); + + var cunit = CompilationUnit{ + .build = build, + .module = module, + .builder = builder, + .context = context, + .lock = event.Lock.init(build.loop), + }; + + try renderToLlvmModule(&cunit, fn_val, code); + + if (build.verbose_llvm_ir) { + llvm.DumpModule(cunit.module); + } +} + +pub const CompilationUnit = struct { + build: *Build, + module: llvm.ModuleRef, + builder: llvm.BuilderRef, + context: llvm.ContextRef, + lock: event.Lock, + + fn a(self: *CompilationUnit) *std.mem.Allocator { + return self.build.a(); + } +}; + +pub fn renderToLlvmModule(cunit: *CompilationUnit, fn_val: *Value.Fn, code: *ir.Code) !void { + // TODO audit more of codegen.cpp:fn_llvm_value and port more logic + const llvm_fn_type = try fn_val.base.typeof.getLlvmType(cunit); + const llvm_fn = llvm.AddFunction(cunit.module, fn_val.symbol_name.ptr(), llvm_fn_type); +} diff --git a/src-self-hosted/ir.zig b/src-self-hosted/ir.zig index 22161a0c27..f1c395a790 100644 --- a/src-self-hosted/ir.zig +++ b/src-self-hosted/ir.zig @@ -375,15 +375,8 @@ pub const Instruction = struct { pub fn analyze(self: *const AddImplicitReturnType, ira: *Analyze) !*Instruction { const target = try self.params.target.getAsParam(); - try ira.src_implicit_return_type_list.append(target); - - return ira.irb.build( - AddImplicitReturnType, - self.base.scope, - self.base.span, - Params{ .target = target }, - ); + return ira.irb.buildConstVoid(self.base.scope, self.base.span, true); } }; }; diff --git a/src-self-hosted/llvm.zig b/src-self-hosted/llvm.zig index 391a92cd63..b815f75b05 100644 --- a/src-self-hosted/llvm.zig +++ b/src-self-hosted/llvm.zig @@ -2,10 +2,27 @@ const builtin = @import("builtin"); const c = @import("c.zig"); const assert = @import("std").debug.assert; -pub const ValueRef = removeNullability(c.LLVMValueRef); -pub const ModuleRef = removeNullability(c.LLVMModuleRef); -pub const ContextRef = removeNullability(c.LLVMContextRef); pub const BuilderRef = removeNullability(c.LLVMBuilderRef); +pub const ContextRef = removeNullability(c.LLVMContextRef); +pub const ModuleRef = removeNullability(c.LLVMModuleRef); +pub const ValueRef = removeNullability(c.LLVMValueRef); +pub const TypeRef = removeNullability(c.LLVMTypeRef); + +pub const AddFunction = c.LLVMAddFunction; +pub const CreateBuilderInContext = c.LLVMCreateBuilderInContext; +pub const DisposeBuilder = c.LLVMDisposeBuilder; +pub const DisposeModule = c.LLVMDisposeModule; +pub const DumpModule = c.LLVMDumpModule; +pub const ModuleCreateWithNameInContext = c.LLVMModuleCreateWithNameInContext; +pub const VoidTypeInContext = c.LLVMVoidTypeInContext; + +pub const FunctionType = LLVMFunctionType; +extern fn LLVMFunctionType( + ReturnType: TypeRef, + ParamTypes: [*]TypeRef, + ParamCount: c_uint, + IsVarArg: c_int, +) ?TypeRef; fn removeNullability(comptime T: type) type { comptime assert(@typeId(T) == builtin.TypeId.Optional); diff --git a/src-self-hosted/main.zig b/src-self-hosted/main.zig index 972aaae9ac..77ec7f6d32 100644 --- a/src-self-hosted/main.zig +++ b/src-self-hosted/main.zig @@ -14,6 +14,7 @@ const c = @import("c.zig"); const introspect = @import("introspect.zig"); const Args = arg.Args; const Flag = arg.Flag; +const EventLoopLocal = @import("module.zig").EventLoopLocal; const Module = @import("module.zig").Module; const Target = @import("target.zig").Target; const errmsg = @import("errmsg.zig"); @@ -386,9 +387,13 @@ fn buildOutputType(allocator: *Allocator, args: []const []const u8, out_type: Mo var loop: event.Loop = undefined; try loop.initMultiThreaded(allocator); + defer loop.deinit(); + + var event_loop_local = EventLoopLocal.init(&loop); + defer event_loop_local.deinit(); var module = try Module.create( - &loop, + &event_loop_local, root_name, root_source_file, Target.Native, diff --git a/src-self-hosted/module.zig b/src-self-hosted/module.zig index 3fbe6d54ad..617bd0d44a 100644 --- a/src-self-hosted/module.zig +++ b/src-self-hosted/module.zig @@ -25,14 +25,58 @@ const ParsedFile = @import("parsed_file.zig").ParsedFile; const Value = @import("value.zig").Value; const Type = Value.Type; const Span = errmsg.Span; +const codegen = @import("codegen.zig"); + +/// Data that is local to the event loop. +pub const EventLoopLocal = struct { + loop: *event.Loop, + llvm_handle_pool: std.atomic.Stack(llvm.ContextRef), + + fn init(loop: *event.Loop) EventLoopLocal { + return EventLoopLocal{ + .loop = loop, + .llvm_handle_pool = std.atomic.Stack(llvm.ContextRef).init(), + }; + } + + fn deinit(self: *EventLoopLocal) void { + while (self.llvm_handle_pool.pop()) |node| { + c.LLVMContextDispose(node.data); + self.loop.allocator.destroy(node); + } + } + + /// Gets an exclusive handle on any LlvmContext. + /// Caller must release the handle when done. + pub fn getAnyLlvmContext(self: *EventLoopLocal) !LlvmHandle { + if (self.llvm_handle_pool.pop()) |node| return LlvmHandle{ .node = node }; + + const context_ref = c.LLVMContextCreate() orelse return error.OutOfMemory; + errdefer c.LLVMContextDispose(context_ref); + + const node = try self.loop.allocator.create(std.atomic.Stack(llvm.ContextRef).Node{ + .next = undefined, + .data = context_ref, + }); + errdefer self.loop.allocator.destroy(node); + + return LlvmHandle{ .node = node }; + } +}; + +pub const LlvmHandle = struct { + node: *std.atomic.Stack(llvm.ContextRef).Node, + + pub fn release(self: LlvmHandle, event_loop_local: *EventLoopLocal) void { + event_loop_local.llvm_handle_pool.push(self.node); + } +}; pub const Module = struct { + event_loop_local: *EventLoopLocal, loop: *event.Loop, name: Buffer, root_src_path: ?[]const u8, - llvm_module: llvm.ModuleRef, - context: llvm.ContextRef, - builder: llvm.BuilderRef, target: Target, build_mode: builtin.Mode, zig_lib_dir: []const u8, @@ -187,7 +231,7 @@ pub const Module = struct { }; pub fn create( - loop: *event.Loop, + event_loop_local: *EventLoopLocal, name: []const u8, root_src_path: ?[]const u8, target: *const Target, @@ -196,29 +240,20 @@ pub const Module = struct { zig_lib_dir: []const u8, cache_dir: []const u8, ) !*Module { + const loop = event_loop_local.loop; + var name_buffer = try Buffer.init(loop.allocator, name); errdefer name_buffer.deinit(); - const context = c.LLVMContextCreate() orelse return error.OutOfMemory; - errdefer c.LLVMContextDispose(context); - - const llvm_module = c.LLVMModuleCreateWithNameInContext(name_buffer.ptr(), context) orelse return error.OutOfMemory; - errdefer c.LLVMDisposeModule(llvm_module); - - const builder = c.LLVMCreateBuilderInContext(context) orelse return error.OutOfMemory; - errdefer c.LLVMDisposeBuilder(builder); - const events = try event.Channel(Event).create(loop, 0); errdefer events.destroy(); const module = try loop.allocator.create(Module{ .loop = loop, + .event_loop_local = event_loop_local, .events = events, .name = name_buffer, .root_src_path = root_src_path, - .llvm_module = llvm_module, - .context = context, - .builder = builder, .target = target.*, .kind = kind, .build_mode = build_mode, @@ -290,7 +325,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Type, .typeof = undefined, - .ref_count = 3, // 3 because it references itself twice + .ref_count = std.atomic.Int(usize).init(3), // 3 because it references itself twice }, .id = builtin.TypeId.Type, }, @@ -305,7 +340,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Type, .typeof = &Type.MetaType.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .id = builtin.TypeId.Void, }, @@ -317,7 +352,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Type, .typeof = &Type.MetaType.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .id = builtin.TypeId.NoReturn, }, @@ -329,7 +364,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Type, .typeof = &Type.MetaType.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .id = builtin.TypeId.Bool, }, @@ -340,7 +375,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Void, .typeof = &Type.Void.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, }); errdefer module.a().destroy(module.void_value); @@ -349,7 +384,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Bool, .typeof = &Type.Bool.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .x = true, }); @@ -359,7 +394,7 @@ pub const Module = struct { .base = Value{ .id = Value.Id.Bool, .typeof = &Type.Bool.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .x = false, }); @@ -369,16 +404,12 @@ pub const Module = struct { .base = Value{ .id = Value.Id.NoReturn, .typeof = &Type.NoReturn.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, }); errdefer module.a().destroy(module.noreturn_value); } - fn dump(self: *Module) void { - c.LLVMDumpModule(self.module); - } - pub fn destroy(self: *Module) void { self.noreturn_value.base.deref(self); self.void_value.base.deref(self); @@ -389,9 +420,6 @@ pub const Module = struct { self.meta_type.base.base.deref(self); self.events.destroy(); - c.LLVMDisposeBuilder(self.builder); - c.LLVMDisposeModule(self.llvm_module); - c.LLVMContextDispose(self.context); self.name.deinit(); self.a().destroy(self); @@ -657,10 +685,19 @@ async fn generateDeclFn(module: *Module, fn_decl: *Decl.Fn) !void { const fndef_scope = try Scope.FnDef.create(module, fn_decl.base.parent_scope); defer fndef_scope.base.deref(module); - const fn_type = try Type.Fn.create(module); + // TODO actually look at the return type of the AST + const return_type = &Type.Void.get(module).base; + defer return_type.base.deref(module); + + const is_var_args = false; + const params = ([*]Type.Fn.Param)(undefined)[0..0]; + const fn_type = try Type.Fn.create(module, return_type, params, is_var_args); defer fn_type.base.base.deref(module); - const fn_val = try Value.Fn.create(module, fn_type, fndef_scope); + var symbol_name = try std.Buffer.init(module.a(), fn_decl.base.name); + errdefer symbol_name.deinit(); + + const fn_val = try Value.Fn.create(module, fn_type, fndef_scope, symbol_name); defer fn_val.base.deref(module); fn_decl.value = Decl.Fn.Val{ .Ok = fn_val }; @@ -674,6 +711,7 @@ async fn generateDeclFn(module: *Module, fn_decl: *Decl.Fn) !void { ) catch unreachable)) catch |err| switch (err) { // This poison value should not cause the errdefers to run. It simply means // that self.compile_errors is populated. + // TODO https://github.com/ziglang/zig/issues/769 error.SemanticAnalysisFailed => return {}, else => return err, }; @@ -692,14 +730,18 @@ async fn generateDeclFn(module: *Module, fn_decl: *Decl.Fn) !void { ) catch unreachable)) catch |err| switch (err) { // This poison value should not cause the errdefers to run. It simply means // that self.compile_errors is populated. + // TODO https://github.com/ziglang/zig/issues/769 error.SemanticAnalysisFailed => return {}, else => return err, }; - defer analyzed_code.destroy(module.a()); + errdefer analyzed_code.destroy(module.a()); if (module.verbose_ir) { std.debug.warn("analyzed:\n"); analyzed_code.dump(); } - // TODO now render to LLVM module + + // Kick off rendering to LLVM module, but it doesn't block the fn decl + // analysis from being complete. + try module.build_group.call(codegen.renderToLlvm, module, fn_val, analyzed_code); } diff --git a/src-self-hosted/test.zig b/src-self-hosted/test.zig index 4455352f95..e609eb2791 100644 --- a/src-self-hosted/test.zig +++ b/src-self-hosted/test.zig @@ -6,6 +6,7 @@ const Module = @import("module.zig").Module; const introspect = @import("introspect.zig"); const assertOrPanic = std.debug.assertOrPanic; const errmsg = @import("errmsg.zig"); +const EventLoopLocal = @import("module.zig").EventLoopLocal; test "compile errors" { var ctx: TestContext = undefined; @@ -22,6 +23,7 @@ const allocator = std.heap.c_allocator; pub const TestContext = struct { loop: std.event.Loop, + event_loop_local: EventLoopLocal, zig_lib_dir: []u8, zig_cache_dir: []u8, file_index: std.atomic.Int(usize), @@ -34,6 +36,7 @@ pub const TestContext = struct { self.* = TestContext{ .any_err = {}, .loop = undefined, + .event_loop_local = undefined, .zig_lib_dir = undefined, .zig_cache_dir = undefined, .group = undefined, @@ -43,6 +46,9 @@ pub const TestContext = struct { try self.loop.initMultiThreaded(allocator); errdefer self.loop.deinit(); + self.event_loop_local = EventLoopLocal.init(&self.loop); + errdefer self.event_loop_local.deinit(); + self.group = std.event.Group(error!void).init(&self.loop); errdefer self.group.cancelAll(); @@ -60,6 +66,7 @@ pub const TestContext = struct { std.os.deleteTree(allocator, tmp_dir_name) catch {}; allocator.free(self.zig_cache_dir); allocator.free(self.zig_lib_dir); + self.event_loop_local.deinit(); self.loop.deinit(); } @@ -83,7 +90,7 @@ pub const TestContext = struct { msg: []const u8, ) !void { var file_index_buf: [20]u8 = undefined; - const file_index = try std.fmt.bufPrint(file_index_buf[0..], "{}", self.file_index.next()); + const file_index = try std.fmt.bufPrint(file_index_buf[0..], "{}", self.file_index.incr()); const file1_path = try std.os.path.join(allocator, tmp_dir_name, file_index, file1); if (std.os.path.dirname(file1_path)) |dirname| { @@ -94,7 +101,7 @@ pub const TestContext = struct { try std.io.writeFile(allocator, file1_path, source); var module = try Module.create( - &self.loop, + &self.event_loop_local, "test", file1_path, Target.Native, diff --git a/src-self-hosted/type.zig b/src-self-hosted/type.zig index 66e1470cc0..e4c31018a3 100644 --- a/src-self-hosted/type.zig +++ b/src-self-hosted/type.zig @@ -1,7 +1,10 @@ +const std = @import("std"); const builtin = @import("builtin"); const Scope = @import("scope.zig").Scope; const Module = @import("module.zig").Module; const Value = @import("value.zig").Value; +const llvm = @import("llvm.zig"); +const CompilationUnit = @import("codegen.zig").CompilationUnit; pub const Type = struct { base: Value, @@ -39,6 +42,36 @@ pub const Type = struct { } } + pub fn getLlvmType(base: *Type, cunit: *CompilationUnit) (error{OutOfMemory}!llvm.TypeRef) { + switch (base.id) { + Id.Struct => return @fieldParentPtr(Struct, "base", base).getLlvmType(cunit), + Id.Fn => return @fieldParentPtr(Fn, "base", base).getLlvmType(cunit), + Id.Type => unreachable, + Id.Void => unreachable, + Id.Bool => return @fieldParentPtr(Bool, "base", base).getLlvmType(cunit), + Id.NoReturn => unreachable, + Id.Int => return @fieldParentPtr(Int, "base", base).getLlvmType(cunit), + Id.Float => return @fieldParentPtr(Float, "base", base).getLlvmType(cunit), + Id.Pointer => return @fieldParentPtr(Pointer, "base", base).getLlvmType(cunit), + Id.Array => return @fieldParentPtr(Array, "base", base).getLlvmType(cunit), + Id.ComptimeFloat => unreachable, + Id.ComptimeInt => unreachable, + Id.Undefined => unreachable, + Id.Null => unreachable, + Id.Optional => return @fieldParentPtr(Optional, "base", base).getLlvmType(cunit), + Id.ErrorUnion => return @fieldParentPtr(ErrorUnion, "base", base).getLlvmType(cunit), + Id.ErrorSet => return @fieldParentPtr(ErrorSet, "base", base).getLlvmType(cunit), + Id.Enum => return @fieldParentPtr(Enum, "base", base).getLlvmType(cunit), + Id.Union => return @fieldParentPtr(Union, "base", base).getLlvmType(cunit), + Id.Namespace => unreachable, + Id.Block => unreachable, + Id.BoundFn => return @fieldParentPtr(BoundFn, "base", base).getLlvmType(cunit), + Id.ArgTuple => unreachable, + Id.Opaque => return @fieldParentPtr(Opaque, "base", base).getLlvmType(cunit), + Id.Promise => return @fieldParentPtr(Promise, "base", base).getLlvmType(cunit), + } + } + pub fn dump(base: *const Type) void { std.debug.warn("{}", @tagName(base.id)); } @@ -54,27 +87,72 @@ pub const Type = struct { pub fn destroy(self: *Struct, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Struct, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const Fn = struct { base: Type, + return_type: *Type, + params: []Param, + is_var_args: bool, - pub fn create(module: *Module) !*Fn { - return module.a().create(Fn{ + pub const Param = struct { + is_noalias: bool, + typeof: *Type, + }; + + pub fn create(module: *Module, return_type: *Type, params: []Param, is_var_args: bool) !*Fn { + const result = try module.a().create(Fn{ .base = Type{ .base = Value{ .id = Value.Id.Type, .typeof = &MetaType.get(module).base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .id = builtin.TypeId.Fn, }, + .return_type = return_type, + .params = params, + .is_var_args = is_var_args, }); + errdefer module.a().destroy(result); + + result.return_type.base.ref(); + for (result.params) |param| { + param.typeof.base.ref(); + } + return result; } pub fn destroy(self: *Fn, module: *Module) void { + self.return_type.base.deref(module); + for (self.params) |param| { + param.typeof.base.deref(module); + } module.a().destroy(self); } + + pub fn getLlvmType(self: *Fn, cunit: *CompilationUnit) !llvm.TypeRef { + const llvm_return_type = switch (self.return_type.id) { + Type.Id.Void => llvm.VoidTypeInContext(cunit.context) orelse return error.OutOfMemory, + else => try self.return_type.getLlvmType(cunit), + }; + const llvm_param_types = try cunit.a().alloc(llvm.TypeRef, self.params.len); + defer cunit.a().free(llvm_param_types); + for (llvm_param_types) |*llvm_param_type, i| { + llvm_param_type.* = try self.params[i].typeof.getLlvmType(cunit); + } + + return llvm.FunctionType( + llvm_return_type, + llvm_param_types.ptr, + @intCast(c_uint, llvm_param_types.len), + @boolToInt(self.is_var_args), + ) orelse error.OutOfMemory; + } }; pub const MetaType = struct { @@ -118,6 +196,10 @@ pub const Type = struct { pub fn destroy(self: *Bool, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Bool, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const NoReturn = struct { @@ -140,6 +222,10 @@ pub const Type = struct { pub fn destroy(self: *Int, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Int, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const Float = struct { @@ -148,6 +234,10 @@ pub const Type = struct { pub fn destroy(self: *Float, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Float, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const Pointer = struct { base: Type, @@ -180,14 +270,24 @@ pub const Type = struct { ) *Pointer { @panic("TODO get pointer"); } + + pub fn getLlvmType(self: *Pointer, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const Array = struct { base: Type, pub fn destroy(self: *Array, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Array, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const ComptimeFloat = struct { base: Type, @@ -195,6 +295,7 @@ pub const Type = struct { module.a().destroy(self); } }; + pub const ComptimeInt = struct { base: Type, @@ -202,6 +303,7 @@ pub const Type = struct { module.a().destroy(self); } }; + pub const Undefined = struct { base: Type, @@ -209,6 +311,7 @@ pub const Type = struct { module.a().destroy(self); } }; + pub const Null = struct { base: Type, @@ -216,41 +319,67 @@ pub const Type = struct { module.a().destroy(self); } }; + pub const Optional = struct { base: Type, pub fn destroy(self: *Optional, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Optional, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const ErrorUnion = struct { base: Type, pub fn destroy(self: *ErrorUnion, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *ErrorUnion, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const ErrorSet = struct { base: Type, pub fn destroy(self: *ErrorSet, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *ErrorSet, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const Enum = struct { base: Type, pub fn destroy(self: *Enum, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Enum, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const Union = struct { base: Type, pub fn destroy(self: *Union, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Union, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; + pub const Namespace = struct { base: Type, @@ -273,6 +402,10 @@ pub const Type = struct { pub fn destroy(self: *BoundFn, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *BoundFn, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const ArgTuple = struct { @@ -289,6 +422,10 @@ pub const Type = struct { pub fn destroy(self: *Opaque, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Opaque, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; pub const Promise = struct { @@ -297,5 +434,9 @@ pub const Type = struct { pub fn destroy(self: *Promise, module: *Module) void { module.a().destroy(self); } + + pub fn getLlvmType(self: *Promise, cunit: *CompilationUnit) llvm.TypeRef { + @panic("TODO"); + } }; }; diff --git a/src-self-hosted/value.zig b/src-self-hosted/value.zig index 7ee594b41c..779e5c2e45 100644 --- a/src-self-hosted/value.zig +++ b/src-self-hosted/value.zig @@ -8,15 +8,16 @@ const Module = @import("module.zig").Module; pub const Value = struct { id: Id, typeof: *Type, - ref_count: usize, + ref_count: std.atomic.Int(usize), + /// Thread-safe pub fn ref(base: *Value) void { - base.ref_count += 1; + _ = base.ref_count.incr(); } + /// Thread-safe pub fn deref(base: *Value, module: *Module) void { - base.ref_count -= 1; - if (base.ref_count == 0) { + if (base.ref_count.decr() == 1) { base.typeof.base.deref(module); switch (base.id) { Id.Type => @fieldParentPtr(Type, "base", base).destroy(module), @@ -52,6 +53,10 @@ pub const Value = struct { pub const Fn = struct { base: Value, + /// The main external name that is used in the .o file. + /// TODO https://github.com/ziglang/zig/issues/265 + symbol_name: std.Buffer, + /// parent should be the top level decls or container decls fndef_scope: *Scope.FnDef, @@ -62,16 +67,18 @@ pub const Value = struct { block_scope: *Scope.Block, /// Creates a Fn value with 1 ref - pub fn create(module: *Module, fn_type: *Type.Fn, fndef_scope: *Scope.FnDef) !*Fn { + /// Takes ownership of symbol_name + pub fn create(module: *Module, fn_type: *Type.Fn, fndef_scope: *Scope.FnDef, symbol_name: std.Buffer) !*Fn { const self = try module.a().create(Fn{ .base = Value{ .id = Value.Id.Fn, .typeof = &fn_type.base, - .ref_count = 1, + .ref_count = std.atomic.Int(usize).init(1), }, .fndef_scope = fndef_scope, .child_scope = &fndef_scope.base, .block_scope = undefined, + .symbol_name = symbol_name, }); fn_type.base.base.ref(); fndef_scope.fn_val = self; @@ -81,6 +88,7 @@ pub const Value = struct { pub fn destroy(self: *Fn, module: *Module) void { self.fndef_scope.base.deref(module); + self.symbol_name.deinit(); module.a().destroy(self); } }; diff --git a/std/atomic/int.zig b/std/atomic/int.zig index 7042bca78d..d51454c673 100644 --- a/std/atomic/int.zig +++ b/std/atomic/int.zig @@ -4,16 +4,26 @@ const AtomicOrder = builtin.AtomicOrder; /// Thread-safe, lock-free integer pub fn Int(comptime T: type) type { return struct { - value: T, + unprotected_value: T, pub const Self = this; pub fn init(init_val: T) Self { - return Self{ .value = init_val }; + return Self{ .unprotected_value = init_val }; } - pub fn next(self: *Self) T { - return @atomicRmw(T, &self.value, builtin.AtomicRmwOp.Add, 1, AtomicOrder.SeqCst); + /// Returns previous value + pub fn incr(self: *Self) T { + return @atomicRmw(T, &self.unprotected_value, builtin.AtomicRmwOp.Add, 1, AtomicOrder.SeqCst); + } + + /// Returns previous value + pub fn decr(self: *Self) T { + return @atomicRmw(T, &self.unprotected_value, builtin.AtomicRmwOp.Sub, 1, AtomicOrder.SeqCst); + } + + pub fn get(self: *Self) T { + return @atomicLoad(T, &self.unprotected_value, AtomicOrder.SeqCst); } }; } diff --git a/std/event/loop.zig b/std/event/loop.zig index ba75109a72..fc927592b9 100644 --- a/std/event/loop.zig +++ b/std/event/loop.zig @@ -101,7 +101,6 @@ pub const Loop = struct { errdefer self.deinitOsData(); } - /// must call stop before deinit pub fn deinit(self: *Loop) void { self.deinitOsData(); self.allocator.free(self.extra_threads); -- cgit v1.2.3