From b7452fe35f514d4c04aae4582bc8071bc9e70f1b Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Wed, 20 Jan 2021 20:37:44 -0700 Subject: stage2: rework astgen result locations Motivating test case: ```zig export fn _start() noreturn { var x: u64 = 1; var y: u32 = 2; var thing: u32 = 1; const result = if (thing == 1) x else y; exit(); } ``` The main idea here is for astgen to output ideal ZIR depending on whether or not the sub-expressions of a block consume the result location. Here, neither `x` nor `y` consume the result location of the conditional expression block, and so the ZIR should communicate the result of the condbr using break instructions, not with the result location pointer. With this commit, this is accomplished: ``` %22 = alloc_inferred() %23 = block({ %24 = const(TypedValue{ .ty = type, .val = bool}) %25 = deref(%18) %26 = const(TypedValue{ .ty = comptime_int, .val = 1}) %27 = cmp_eq(%25, %26) %28 = as(%24, %27) %29 = condbr(%28, { %30 = deref(%4) < there is no longer a store instruction here > %31 = break("label_23", %30) }, { %32 = deref(%11) < there is no longer a store instruction here > %33 = break("label_23", %32) }) }) %34 = store_to_inferred_ptr(%22, %23) <-- the store is only here %35 = resolve_inferred_alloc(%22) ``` However if the result location gets consumed, the break instructions change to break_void, and the result value is communicated only by the stores, not by the break instructions. Implementation: * The GenZIR scope that conditional branches uses now has an optional result location pointer field and a count of how many times the result location ended up being an rvalue (not consumed). * When rvalue() is called on a result location for a block, it increments this counter. After generating the branches of a block, astgen for the conditional branch checks this count and if it is 2 then the store_to_block_ptr instructions are elided and it calls rvalue() using the block result (which will account for peer type resolution on the break operands). astgen has many functions disabled until they can be reworked with these new semantics. That will be done before merging the branch. There are some new rules for astgen to follow regarding result locations and what you are allowed/required to do depending on which one is passed to expr(). See the updated doc comments of ResultLoc for details. I also changed naming conventions of stuff in this commit, sorry about that. --- src/codegen.zig | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) (limited to 'src/codegen.zig') diff --git a/src/codegen.zig b/src/codegen.zig index 1ca2bb2abe..a7b067f7e1 100644 --- a/src/codegen.zig +++ b/src/codegen.zig @@ -840,14 +840,14 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { .arg => return self.genArg(inst.castTag(.arg).?), .assembly => return self.genAsm(inst.castTag(.assembly).?), .bitcast => return self.genBitCast(inst.castTag(.bitcast).?), - .bitand => return self.genBitAnd(inst.castTag(.bitand).?), - .bitor => return self.genBitOr(inst.castTag(.bitor).?), + .bit_and => return self.genBitAnd(inst.castTag(.bit_and).?), + .bit_or => return self.genBitOr(inst.castTag(.bit_or).?), .block => return self.genBlock(inst.castTag(.block).?), .br => return self.genBr(inst.castTag(.br).?), .breakpoint => return self.genBreakpoint(inst.src), .brvoid => return self.genBrVoid(inst.castTag(.brvoid).?), - .booland => return self.genBoolOp(inst.castTag(.booland).?), - .boolor => return self.genBoolOp(inst.castTag(.boolor).?), + .bool_and => return self.genBoolOp(inst.castTag(.bool_and).?), + .bool_or => return self.genBoolOp(inst.castTag(.bool_or).?), .call => return self.genCall(inst.castTag(.call).?), .cmp_lt => return self.genCmp(inst.castTag(.cmp_lt).?, .lt), .cmp_lte => return self.genCmp(inst.castTag(.cmp_lte).?, .lte), @@ -1097,7 +1097,7 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { if (inst.base.isUnused()) return MCValue.dead; switch (arch) { - .arm, .armeb => return try self.genArmBinOp(&inst.base, inst.lhs, inst.rhs, .bitand), + .arm, .armeb => return try self.genArmBinOp(&inst.base, inst.lhs, inst.rhs, .bit_and), else => return self.fail(inst.base.src, "TODO implement bitwise and for {}", .{self.target.cpu.arch}), } } @@ -1107,7 +1107,7 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { if (inst.base.isUnused()) return MCValue.dead; switch (arch) { - .arm, .armeb => return try self.genArmBinOp(&inst.base, inst.lhs, inst.rhs, .bitor), + .arm, .armeb => return try self.genArmBinOp(&inst.base, inst.lhs, inst.rhs, .bit_or), else => return self.fail(inst.base.src, "TODO implement bitwise or for {}", .{self.target.cpu.arch}), } } @@ -1371,10 +1371,10 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { writeInt(u32, try self.code.addManyAsArray(4), Instruction.rsb(.al, dst_reg, dst_reg, operand).toU32()); } }, - .booland, .bitand => { + .bool_and, .bit_and => { writeInt(u32, try self.code.addManyAsArray(4), Instruction.@"and"(.al, dst_reg, dst_reg, operand).toU32()); }, - .boolor, .bitor => { + .bool_or, .bit_or => { writeInt(u32, try self.code.addManyAsArray(4), Instruction.orr(.al, dst_reg, dst_reg, operand).toU32()); }, .not, .xor => { @@ -2464,14 +2464,14 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { switch (arch) { .x86_64 => switch (inst.base.tag) { // lhs AND rhs - .booland => return try self.genX8664BinMath(&inst.base, inst.lhs, inst.rhs, 4, 0x20), + .bool_and => return try self.genX8664BinMath(&inst.base, inst.lhs, inst.rhs, 4, 0x20), // lhs OR rhs - .boolor => return try self.genX8664BinMath(&inst.base, inst.lhs, inst.rhs, 1, 0x08), + .bool_or => return try self.genX8664BinMath(&inst.base, inst.lhs, inst.rhs, 1, 0x08), else => unreachable, // Not a boolean operation }, .arm, .armeb => switch (inst.base.tag) { - .booland => return try self.genArmBinOp(&inst.base, inst.lhs, inst.rhs, .booland), - .boolor => return try self.genArmBinOp(&inst.base, inst.lhs, inst.rhs, .boolor), + .bool_and => return try self.genArmBinOp(&inst.base, inst.lhs, inst.rhs, .bool_and), + .bool_or => return try self.genArmBinOp(&inst.base, inst.lhs, inst.rhs, .bool_or), else => unreachable, // Not a boolean operation }, else => return self.fail(inst.base.src, "TODO implement boolean operations for {}", .{self.target.cpu.arch}), -- cgit v1.2.3 From 588171c30b34426fbb07645aa2625e989f369eec Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Fri, 22 Jan 2021 16:45:09 -0700 Subject: sema: after block gets peer type resolved, insert type coercions on the break instruction operands. This involves a new TZIR instruction, br_block_flat, which represents a break instruction where the operand is the result of a flat block. See the doc comments on the instructions for more details. How it works: when adding break instructions in semantic analysis, the underlying allocation is slightly padded so that it is the size of a br_block_flat instruction, which allows the break instruction to later be converted without removing instructions inside the parent body. The extra type coercion instructions go into the body of the br_block_flat, and backends are responsible for dispatching the instruction correctly (it should map to the same function calls for related instructions). --- src/Module.zig | 28 +++++++++++++++-- src/codegen.zig | 31 ++++++++++++------- src/ir.zig | 32 +++++++++++++++++++- src/zir.zig | 28 +++++++++++++++-- src/zir_sema.zig | 91 ++++++++++++++++++++++++++++++++++++++++++-------------- 5 files changed, 171 insertions(+), 39 deletions(-) (limited to 'src/codegen.zig') diff --git a/src/Module.zig b/src/Module.zig index 2dc84a93a9..b7967aacc5 100644 --- a/src/Module.zig +++ b/src/Module.zig @@ -671,14 +671,36 @@ pub const Scope = struct { }; pub const Merges = struct { - results: ArrayListUnmanaged(*Inst), block_inst: *Inst.Block, + /// Separate array list from break_inst_list so that it can be passed directly + /// to resolvePeerTypes. + results: ArrayListUnmanaged(*Inst), + /// Keeps track of the break instructions so that the operand can be replaced + /// if we need to add type coercion at the end of block analysis. + /// Same indexes, capacity, length as `results`. + br_list: ArrayListUnmanaged(*Inst.Br), }; /// For debugging purposes. pub fn dump(self: *Block, mod: Module) void { zir.dumpBlock(mod, self); } + + pub fn makeSubBlock(parent: *Block) Block { + return .{ + .parent = parent, + .inst_table = parent.inst_table, + .func = parent.func, + .owner_decl = parent.owner_decl, + .src_decl = parent.src_decl, + .instructions = .{}, + .arena = parent.arena, + .label = null, + .inlining = parent.inlining, + .is_comptime = parent.is_comptime, + .branch_quota = parent.branch_quota, + }; + } }; /// This is a temporary structure, references to it are valid only @@ -2107,7 +2129,7 @@ pub fn addBr( src: usize, target_block: *Inst.Block, operand: *Inst, -) !*Inst { +) !*Inst.Br { const inst = try scope_block.arena.create(Inst.Br); inst.* = .{ .base = .{ @@ -2119,7 +2141,7 @@ pub fn addBr( .block = target_block, }; try scope_block.instructions.append(self.gpa, &inst.base); - return &inst.base; + return inst; } pub fn addCondBr( diff --git a/src/codegen.zig b/src/codegen.zig index a7b067f7e1..1f5aad8ab8 100644 --- a/src/codegen.zig +++ b/src/codegen.zig @@ -844,6 +844,7 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { .bit_or => return self.genBitOr(inst.castTag(.bit_or).?), .block => return self.genBlock(inst.castTag(.block).?), .br => return self.genBr(inst.castTag(.br).?), + .br_block_flat => return self.genBrBlockFlat(inst.castTag(.br_block_flat).?), .breakpoint => return self.genBreakpoint(inst.src), .brvoid => return self.genBrVoid(inst.castTag(.brvoid).?), .bool_and => return self.genBoolOp(inst.castTag(.bool_and).?), @@ -2441,17 +2442,14 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { } } + fn genBrBlockFlat(self: *Self, parent_inst: *ir.Inst.BrBlockFlat) !MCValue { + try self.genBody(parent_inst.body); + const last = parent_inst.body.instructions[parent_inst.body.instructions.len - 1]; + return self.br(parent_inst.base.src, parent_inst.block, last); + } + fn genBr(self: *Self, inst: *ir.Inst.Br) !MCValue { - if (inst.operand.ty.hasCodeGenBits()) { - const operand = try self.resolveInst(inst.operand); - const block_mcv = @bitCast(MCValue, inst.block.codegen.mcv); - if (block_mcv == .none) { - inst.block.codegen.mcv = @bitCast(AnyMCValue, operand); - } else { - try self.setRegOrMem(inst.base.src, inst.block.base.ty, block_mcv, operand); - } - } - return self.brVoid(inst.base.src, inst.block); + return self.br(inst.base.src, inst.block, inst.operand); } fn genBrVoid(self: *Self, inst: *ir.Inst.BrVoid) !MCValue { @@ -2478,6 +2476,19 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { } } + fn br(self: *Self, src: usize, block: *ir.Inst.Block, operand: *ir.Inst) !MCValue { + if (operand.ty.hasCodeGenBits()) { + const operand_mcv = try self.resolveInst(operand); + const block_mcv = @bitCast(MCValue, block.codegen.mcv); + if (block_mcv == .none) { + block.codegen.mcv = @bitCast(AnyMCValue, operand_mcv); + } else { + try self.setRegOrMem(src, block.base.ty, block_mcv, operand_mcv); + } + } + return self.brVoid(src, block); + } + fn brVoid(self: *Self, src: usize, block: *ir.Inst.Block) !MCValue { // Emit a jump with a relocation. It will be patched up after the block ends. try block.codegen.relocs.ensureCapacity(self.gpa, block.codegen.relocs.items.len + 1); diff --git a/src/ir.zig b/src/ir.zig index b1147871f4..4d421dda4c 100644 --- a/src/ir.zig +++ b/src/ir.zig @@ -61,6 +61,13 @@ pub const Inst = struct { bit_or, block, br, + /// Same as `br` except the operand is a list of instructions to be treated as + /// a flat block; that is there is only 1 break instruction from the block, and + /// it is implied to be after the last instruction, and the last instruction is + /// the break operand. + /// This instruction exists for late-stage semantic analysis patch ups, to + /// replace one br operand with multiple instructions, without moving anything else around. + br_block_flat, breakpoint, brvoid, call, @@ -158,6 +165,7 @@ pub const Inst = struct { .assembly => Assembly, .block => Block, .br => Br, + .br_block_flat => BrBlockFlat, .brvoid => BrVoid, .call => Call, .condbr => CondBr, @@ -252,6 +260,7 @@ pub const Inst = struct { return switch (base.tag) { .br => base.castTag(.br).?.block, .brvoid => base.castTag(.brvoid).?.block, + .br_block_flat => base.castTag(.br_block_flat).?.block, else => null, }; } @@ -355,6 +364,27 @@ pub const Inst = struct { } }; + pub const convertable_br_size = std.math.max(@sizeOf(BrBlockFlat), @sizeOf(Br)); + pub const convertable_br_align = std.math.max(@alignOf(BrBlockFlat), @alignOf(Br)); + comptime { + assert(@byteOffsetOf(BrBlockFlat, "base") == @byteOffsetOf(Br, "base")); + } + + pub const BrBlockFlat = struct { + pub const base_tag = Tag.br_block_flat; + + base: Inst, + block: *Block, + body: Body, + + pub fn operandCount(self: *const BrBlockFlat) usize { + return 0; + } + pub fn getOperand(self: *const BrBlockFlat, index: usize) ?*Inst { + return null; + } + }; + pub const Br = struct { pub const base_tag = Tag.br; @@ -363,7 +393,7 @@ pub const Inst = struct { operand: *Inst, pub fn operandCount(self: *const Br) usize { - return 0; + return 1; } pub fn getOperand(self: *const Br, index: usize) ?*Inst { if (index == 0) diff --git a/src/zir.zig b/src/zir.zig index 651e5ee3dc..301b52efc0 100644 --- a/src/zir.zig +++ b/src/zir.zig @@ -1634,6 +1634,12 @@ const DumpTzir = struct { try dtz.findConst(br.operand); }, + .br_block_flat => { + const br_block_flat = inst.castTag(.br_block_flat).?; + try dtz.findConst(&br_block_flat.block.base); + try dtz.fetchInstsAndResolveConsts(br_block_flat.body); + }, + .brvoid => { const brvoid = inst.castTag(.brvoid).?; try dtz.findConst(&brvoid.block.base); @@ -1779,6 +1785,24 @@ const DumpTzir = struct { } }, + .br_block_flat => { + const br_block_flat = inst.castTag(.br_block_flat).?; + const block_kinky = try dtz.writeInst(writer, &br_block_flat.block.base); + if (block_kinky != null) { + try writer.writeAll(", { // Instruction does not dominate all uses!\n"); + } else { + try writer.writeAll(", {\n"); + } + + const old_indent = dtz.indent; + dtz.indent += 2; + try dtz.dumpBody(br_block_flat.body, writer); + dtz.indent = old_indent; + + try writer.writeByteNTimes(' ', dtz.indent); + try writer.writeAll("})\n"); + }, + .brvoid => { const brvoid = inst.castTag(.brvoid).?; const kinky = try dtz.writeInst(writer, &brvoid.block.base); @@ -1792,7 +1816,7 @@ const DumpTzir = struct { .block => { const block = inst.castTag(.block).?; - try writer.writeAll("\n"); + try writer.writeAll("{\n"); const old_indent = dtz.indent; dtz.indent += 2; @@ -1800,7 +1824,7 @@ const DumpTzir = struct { dtz.indent = old_indent; try writer.writeByteNTimes(' ', dtz.indent); - try writer.writeAll(")\n"); + try writer.writeAll("})\n"); }, .condbr => { diff --git a/src/zir_sema.zig b/src/zir_sema.zig index 40ea563bb6..0297b9873a 100644 --- a/src/zir_sema.zig +++ b/src/zir_sema.zig @@ -664,20 +664,9 @@ fn zirBlockFlat(mod: *Module, scope: *Scope, inst: *zir.Inst.Block, is_comptime: defer tracy.end(); const parent_block = scope.cast(Scope.Block).?; - var child_block: Scope.Block = .{ - .parent = parent_block, - .inst_table = parent_block.inst_table, - .func = parent_block.func, - .owner_decl = parent_block.owner_decl, - .src_decl = parent_block.src_decl, - .instructions = .{}, - .arena = parent_block.arena, - .label = null, - .inlining = parent_block.inlining, - .is_comptime = parent_block.is_comptime or is_comptime, - .branch_quota = parent_block.branch_quota, - }; + var child_block = parent_block.makeSubBlock(); defer child_block.instructions.deinit(mod.gpa); + child_block.is_comptime = child_block.is_comptime or is_comptime; try analyzeBody(mod, &child_block, inst.positionals.body); @@ -728,6 +717,7 @@ fn zirBlock( .zir_block = inst, .merges = .{ .results = .{}, + .br_list = .{}, .block_inst = block_inst, }, }), @@ -739,6 +729,7 @@ fn zirBlock( defer child_block.instructions.deinit(mod.gpa); defer merges.results.deinit(mod.gpa); + defer merges.br_list.deinit(mod.gpa); try analyzeBody(mod, &child_block, inst.positionals.body); @@ -772,22 +763,53 @@ fn analyzeBlockBody( const last_inst = child_block.instructions.items[last_inst_index]; if (last_inst.breakBlock()) |br_block| { if (br_block == merges.block_inst) { - // No need for a block instruction. We can put the new instructions directly into the parent block. - // Here we omit the break instruction. + // No need for a block instruction. We can put the new instructions directly + // into the parent block. Here we omit the break instruction. const copied_instructions = try parent_block.arena.dupe(*Inst, child_block.instructions.items[0..last_inst_index]); try parent_block.instructions.appendSlice(mod.gpa, copied_instructions); return merges.results.items[0]; } } } - // It should be impossible to have the number of results be > 1 in a comptime scope. - assert(!child_block.is_comptime); // We should have already got a compile error in the condbr condition. + // It is impossible to have the number of results be > 1 in a comptime scope. + assert(!child_block.is_comptime); // Should already got a compile error in the condbr condition. // 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(mod.gpa, &merges.block_inst.base); - merges.block_inst.base.ty = try mod.resolvePeerTypes(scope, merges.results.items); - merges.block_inst.body = .{ .instructions = try parent_block.arena.dupe(*Inst, child_block.instructions.items) }; + const resolved_ty = try mod.resolvePeerTypes(scope, merges.results.items); + merges.block_inst.base.ty = resolved_ty; + merges.block_inst.body = .{ + .instructions = try parent_block.arena.dupe(*Inst, child_block.instructions.items), + }; + // Now that the block has its type resolved, we need to go back into all the break + // instructions, and insert type coercion on the operands. + for (merges.br_list.items) |br| { + if (br.operand.ty.eql(resolved_ty)) { + // No type coercion needed. + continue; + } + var coerce_block = parent_block.makeSubBlock(); + defer coerce_block.instructions.deinit(mod.gpa); + const coerced_operand = try mod.coerce(&coerce_block.base, resolved_ty, br.operand); + assert(coerce_block.instructions.items[coerce_block.instructions.items.len - 1] == coerced_operand); + // Here we depend on the br instruction having been over-allocated (if necessary) + // inide analyzeBreak so that it can be converted into a br_block_flat instruction. + const br_src = br.base.src; + const br_ty = br.base.ty; + const br_block_flat = @ptrCast(*Inst.BrBlockFlat, br); + br_block_flat.* = .{ + .base = .{ + .src = br_src, + .ty = br_ty, + .tag = .br_block_flat, + }, + .block = merges.block_inst, + .body = .{ + .instructions = try parent_block.arena.dupe(*Inst, coerce_block.instructions.items), + }, + }; + } return &merges.block_inst.base; } @@ -827,9 +849,28 @@ fn analyzeBreak( while (opt_block) |block| { if (block.label) |*label| { if (label.zir_block == zir_block) { - try label.merges.results.append(mod.gpa, operand); const b = try mod.requireFunctionBlock(scope, src); - return mod.addBr(b, src, label.merges.block_inst, operand); + // Here we add a br instruction, but we over-allocate a little bit + // (if necessary) to make it possible to convert the instruction into + // a br_block_flat instruction later. + const br = @ptrCast(*Inst.Br, try b.arena.alignedAlloc( + u8, + Inst.convertable_br_align, + Inst.convertable_br_size, + )); + br.* = .{ + .base = .{ + .tag = .br, + .ty = Type.initTag(.noreturn), + .src = src, + }, + .operand = operand, + .block = label.merges.block_inst, + }; + try b.instructions.append(mod.gpa, &br.base); + try label.merges.results.append(mod.gpa, operand); + try label.merges.br_list.append(mod.gpa, br); + return &br.base; } } opt_block = block.parent; @@ -980,6 +1021,7 @@ fn zirCall(mod: *Module, scope: *Scope, inst: *zir.Inst.Call) InnerError!*Inst { .casted_args = casted_args, .merges = .{ .results = .{}, + .br_list = .{}, .block_inst = block_inst, }, }; @@ -1004,6 +1046,7 @@ fn zirCall(mod: *Module, scope: *Scope, inst: *zir.Inst.Call) InnerError!*Inst { defer child_block.instructions.deinit(mod.gpa); defer merges.results.deinit(mod.gpa); + defer merges.br_list.deinit(mod.gpa); try mod.emitBackwardBranch(&child_block, inst.base.src); @@ -2194,7 +2237,8 @@ fn zirReturn(mod: *Module, scope: *Scope, inst: *zir.Inst.UnOp) InnerError!*Inst if (b.inlining) |inlining| { // We are inlining a function call; rewrite the `ret` as a `break`. try inlining.merges.results.append(mod.gpa, operand); - return mod.addBr(b, inst.base.src, inlining.merges.block_inst, operand); + const br = try mod.addBr(b, inst.base.src, inlining.merges.block_inst, operand); + return &br.base; } return mod.addUnOp(b, inst.base.src, Type.initTag(.noreturn), .ret, operand); @@ -2208,7 +2252,8 @@ fn zirReturnVoid(mod: *Module, scope: *Scope, inst: *zir.Inst.NoOp) InnerError!* // We are inlining a function call; rewrite the `retvoid` as a `breakvoid`. const void_inst = try mod.constVoid(scope, inst.base.src); try inlining.merges.results.append(mod.gpa, void_inst); - return mod.addBr(b, inst.base.src, inlining.merges.block_inst, void_inst); + const br = try mod.addBr(b, inst.base.src, inlining.merges.block_inst, void_inst); + return &br.base; } if (b.func) |func| { -- cgit v1.2.3 From 6c8985fceeeb6314143691570cf0c7a42521e590 Mon Sep 17 00:00:00 2001 From: Andrew Kelley Date: Sun, 24 Jan 2021 20:23:37 -0700 Subject: astgen: rework labeled blocks --- src/Module.zig | 23 +++-- src/astgen.zig | 249 +++++++++++++++++++++++++++++++++++-------------------- src/codegen.zig | 10 +-- src/ir.zig | 8 +- src/zir.zig | 19 +++-- src/zir_sema.zig | 3 + 6 files changed, 200 insertions(+), 112 deletions(-) (limited to 'src/codegen.zig') diff --git a/src/Module.zig b/src/Module.zig index b7967aacc5..0bafc72e6b 100644 --- a/src/Module.zig +++ b/src/Module.zig @@ -717,7 +717,7 @@ pub const Scope = struct { label: ?Label = null, break_block: ?*zir.Inst.Block = null, continue_block: ?*zir.Inst.Block = null, - /// only valid if label != null or (continue_block and break_block) != null + /// Only valid when setBlockResultLoc is called. break_result_loc: astgen.ResultLoc = undefined, /// When a block has a pointer result location, here it is. rl_ptr: ?*zir.Inst = null, @@ -726,6 +726,17 @@ pub const Scope = struct { /// whether to rely on break instructions or writing to the result /// pointer for the result instruction. rvalue_rl_count: usize = 0, + /// Keeps track of how many break instructions there are. When astgen is finished + /// with a block, it can check this against rvalue_rl_count to find out whether + /// the break instructions should be downgraded to break_void. + break_count: usize = 0, + /// Tracks `break :foo bar` instructions so they can possibly be elided later if + /// the labeled block ends up not needing a result location pointer. + labeled_breaks: std.ArrayListUnmanaged(*zir.Inst.Break) = .{}, + /// Tracks `store_to_block_ptr` instructions that correspond to break instructions + /// so they can possibly be elided later if the labeled block ends up not needing + /// a result location pointer. + labeled_store_to_block_ptr_list: std.ArrayListUnmanaged(*zir.Inst.BinOp) = .{}, pub const Label = struct { token: ast.TokenIndex, @@ -3495,18 +3506,18 @@ pub fn addSafetyCheck(mod: *Module, parent_block: *Scope.Block, ok: *Inst, panic }; const ok_body: ir.Body = .{ - .instructions = try parent_block.arena.alloc(*Inst, 1), // Only need space for the brvoid. + .instructions = try parent_block.arena.alloc(*Inst, 1), // Only need space for the br_void. }; - const brvoid = try parent_block.arena.create(Inst.BrVoid); - brvoid.* = .{ + const br_void = try parent_block.arena.create(Inst.BrVoid); + br_void.* = .{ .base = .{ - .tag = .brvoid, + .tag = .br_void, .ty = Type.initTag(.noreturn), .src = ok.src, }, .block = block_inst, }; - ok_body.instructions[0] = &brvoid.base; + ok_body.instructions[0] = &br_void.base; var fail_block: Scope.Block = .{ .parent = parent_block, diff --git a/src/astgen.zig b/src/astgen.zig index 49f60aa6ba..994205c3a7 100644 --- a/src/astgen.zig +++ b/src/astgen.zig @@ -38,6 +38,21 @@ pub const ResultLoc = union(enum) { /// is inferred based on peer type resolution for a `zir.Inst.Block`. /// The result instruction from the expression must be ignored. block_ptr: *Module.Scope.GenZIR, + + pub const Strategy = struct { + elide_store_to_block_ptr_instructions: bool, + tag: Tag, + + pub const Tag = enum { + /// Both branches will use break_void; result location is used to communicate the + /// result instruction. + break_void, + /// Use break statements to pass the block result value, and call rvalue() at + /// the end depending on rl. Also elide the store_to_block_ptr instructions + /// depending on rl. + break_operand, + }; + }; }; pub fn typeExpr(mod: *Module, scope: *Scope, type_node: *ast.Node) InnerError!*zir.Inst { @@ -348,10 +363,11 @@ pub fn comptimeExpr(mod: *Module, parent_scope: *Scope, rl: ResultLoc, node: *as return &block.base; } -fn breakExpr(mod: *Module, parent_scope: *Scope, node: *ast.Node.ControlFlowExpression) InnerError!*zir.Inst { - if (true) { - @panic("TODO reimplement this"); - } +fn breakExpr( + mod: *Module, + parent_scope: *Scope, + node: *ast.Node.ControlFlowExpression, +) InnerError!*zir.Inst { const tree = parent_scope.tree(); const src = tree.token_locs[node.ltoken].start; @@ -377,25 +393,31 @@ fn breakExpr(mod: *Module, parent_scope: *Scope, node: *ast.Node.ControlFlowExpr continue; }; - if (node.getRHS()) |rhs| { - // Most result location types can be forwarded directly; however - // if we need to write to a pointer which has an inferred type, - // proper type inference requires peer type resolution on the block's - // break operand expressions. - const branch_rl: ResultLoc = switch (gen_zir.break_result_loc) { - .discard, .none, .ty, .ptr, .ref => gen_zir.break_result_loc, - .inferred_ptr, .bitcasted_ptr, .block_ptr => .{ .block_ptr = block_inst }, - }; - const operand = try expr(mod, parent_scope, branch_rl, rhs); - return try addZIRInst(mod, parent_scope, src, zir.Inst.Break, .{ + const rhs = node.getRHS() orelse { + return addZirInstTag(mod, parent_scope, src, .break_void, .{ .block = block_inst, - .operand = operand, - }, .{}); - } else { - return try addZIRInst(mod, parent_scope, src, zir.Inst.BreakVoid, .{ - .block = block_inst, - }, .{}); + }); + }; + gen_zir.break_count += 1; + const prev_rvalue_rl_count = gen_zir.rvalue_rl_count; + const operand = try expr(mod, parent_scope, gen_zir.break_result_loc, rhs); + const have_store_to_block = gen_zir.rvalue_rl_count != prev_rvalue_rl_count; + const br = try addZirInstTag(mod, parent_scope, src, .@"break", .{ + .block = block_inst, + .operand = operand, + }); + if (gen_zir.break_result_loc == .block_ptr) { + try gen_zir.labeled_breaks.append(mod.gpa, br.castTag(.@"break").?); + + if (have_store_to_block) { + const inst_list = parent_scope.cast(Scope.GenZIR).?.instructions.items; + const last_inst = inst_list[inst_list.len - 2]; + const store_inst = last_inst.castTag(.store_to_block_ptr).?; + assert(store_inst.positionals.lhs == gen_zir.rl_ptr.?); + try gen_zir.labeled_store_to_block_ptr_list.append(mod.gpa, store_inst); + } } + return br; }, .local_val => scope = scope.cast(Scope.LocalVal).?.parent, .local_ptr => scope = scope.cast(Scope.LocalPtr).?.parent, @@ -538,7 +560,6 @@ fn labeledBlockExpr( .decl = parent_scope.ownerDecl().?, .arena = gen_zir.arena, .instructions = .{}, - .break_result_loc = rl, // TODO @as here is working around a stage1 miscompilation bug :( .label = @as(?Scope.GenZIR.Label, Scope.GenZIR.Label{ .token = block_node.label, @@ -546,19 +567,57 @@ fn labeledBlockExpr( }), }; defer block_scope.instructions.deinit(mod.gpa); + defer block_scope.labeled_breaks.deinit(mod.gpa); + defer block_scope.labeled_store_to_block_ptr_list.deinit(mod.gpa); + + setBlockResultLoc(&block_scope, rl); try blockExprStmts(mod, &block_scope.base, &block_node.base, block_node.statements()); + if (!block_scope.label.?.used) { return mod.fail(parent_scope, tree.token_locs[block_node.label].start, "unused block label", .{}); } - block_inst.positionals.body.instructions = try block_scope.arena.dupe(*zir.Inst, block_scope.instructions.items); try gen_zir.instructions.append(mod.gpa, &block_inst.base); - return &block_inst.base; + const strat = rlStrategy(rl, &block_scope); + switch (strat.tag) { + .break_void => { + // The code took advantage of the result location as a pointer. + // Turn the break instructions into break_void instructions. + for (block_scope.labeled_breaks.items) |br| { + br.base.tag = .break_void; + } + // TODO technically not needed since we changed the tag to break_void but + // would be better still to elide the ones that are in this list. + try copyBodyNoEliding(&block_inst.positionals.body, block_scope); + + return &block_inst.base; + }, + .break_operand => { + // All break operands are values that did not use the result location pointer. + if (strat.elide_store_to_block_ptr_instructions) { + for (block_scope.labeled_store_to_block_ptr_list.items) |inst| { + inst.base.tag = .void_value; + } + // TODO technically not needed since we changed the tag to void_value but + // would be better still to elide the ones that are in this list. + } + try copyBodyNoEliding(&block_inst.positionals.body, block_scope); + switch (rl) { + .ref => return &block_inst.base, + else => return rvalue(mod, parent_scope, rl, &block_inst.base), + } + }, + } } -fn blockExprStmts(mod: *Module, parent_scope: *Scope, node: *ast.Node, statements: []*ast.Node) !void { +fn blockExprStmts( + mod: *Module, + parent_scope: *Scope, + node: *ast.Node, + statements: []*ast.Node, +) !void { const tree = parent_scope.tree(); var block_arena = std.heap.ArenaAllocator.init(mod.gpa); @@ -1659,7 +1718,6 @@ fn ifExpr(mod: *Module, scope: *Scope, rl: ResultLoc, if_node: *ast.Node.If) Inn cond_kind = .{ .err_union = null }; } } - const block_branch_count = 2; // then and else var block_scope: Scope.GenZIR = .{ .parent = scope, .decl = scope.ownerDecl().?, @@ -1668,6 +1726,8 @@ fn ifExpr(mod: *Module, scope: *Scope, rl: ResultLoc, if_node: *ast.Node.If) Inn }; defer block_scope.instructions.deinit(mod.gpa); + setBlockResultLoc(&block_scope, rl); + const tree = scope.tree(); const if_src = tree.token_locs[if_node.if_token].start; const cond = try cond_kind.cond(mod, &block_scope, if_src, if_node.condition); @@ -1682,33 +1742,6 @@ fn ifExpr(mod: *Module, scope: *Scope, rl: ResultLoc, if_node: *ast.Node.If) Inn .instructions = try block_scope.arena.dupe(*zir.Inst, block_scope.instructions.items), }); - // Depending on whether the result location is a pointer or value, different - // ZIR needs to be generated. In the former case we rely on storing to the - // pointer to communicate the result, and use breakvoid; in the latter case - // the block break instructions will have the result values. - // One more complication: when the result location is a pointer, we detect - // the scenario where the result location is not consumed. In this case - // we emit ZIR for the block break instructions to have the result values, - // and then rvalue() on that to pass the value to the result location. - const branch_rl: ResultLoc = switch (rl) { - .discard, .none, .ty, .ptr, .ref => rl, - - .inferred_ptr => |ptr| blk: { - block_scope.rl_ptr = &ptr.base; - break :blk .{ .block_ptr = &block_scope }; - }, - - .bitcasted_ptr => |ptr| blk: { - block_scope.rl_ptr = &ptr.base; - break :blk .{ .block_ptr = &block_scope }; - }, - - .block_ptr => |parent_block_scope| blk: { - block_scope.rl_ptr = parent_block_scope.rl_ptr.?; - break :blk .{ .block_ptr = &block_scope }; - }, - }; - const then_src = tree.token_locs[if_node.body.lastToken()].start; var then_scope: Scope.GenZIR = .{ .parent = scope, @@ -1721,7 +1754,8 @@ fn ifExpr(mod: *Module, scope: *Scope, rl: ResultLoc, if_node: *ast.Node.If) Inn // declare payload to the then_scope const then_sub_scope = try cond_kind.thenSubScope(mod, &then_scope, then_src, if_node.payload); - const then_result = try expr(mod, then_sub_scope, branch_rl, if_node.body); + block_scope.break_count += 1; + const then_result = try expr(mod, then_sub_scope, block_scope.break_result_loc, if_node.body); // We hold off on the break instructions as well as copying the then/else // instructions into place until we know whether to keep store_to_block_ptr // instructions or not. @@ -1741,47 +1775,18 @@ fn ifExpr(mod: *Module, scope: *Scope, rl: ResultLoc, if_node: *ast.Node.If) Inn // declare payload to the then_scope else_sub_scope = try cond_kind.elseSubScope(mod, &else_scope, else_src, else_node.payload); - break :blk try expr(mod, else_sub_scope, branch_rl, else_node.body); + block_scope.break_count += 1; + break :blk try expr(mod, else_sub_scope, block_scope.break_result_loc, else_node.body); } else blk: { else_src = tree.token_locs[if_node.lastToken()].start; else_sub_scope = &else_scope.base; - block_scope.rvalue_rl_count += 1; break :blk null; }; // We now have enough information to decide whether the result instruction should // be communicated via result location pointer or break instructions. - const Strategy = enum { - /// Both branches will use break_void; result location is used to communicate the - /// result instruction. - break_void, - /// Use break statements to pass the block result value, and call rvalue() at - /// the end depending on rl. Also elide the store_to_block_ptr instructions - /// depending on rl. - break_operand, - }; - var elide_store_to_block_ptr_instructions = false; - const strategy: Strategy = switch (rl) { - // In this branch there will not be any store_to_block_ptr instructions. - .discard, .none, .ty, .ref => .break_operand, - // The pointer got passed through to the sub-expressions, so we will use - // break_void here. - // In this branch there will not be any store_to_block_ptr instructions. - .ptr => .break_void, - .inferred_ptr, .bitcasted_ptr, .block_ptr => blk: { - if (block_scope.rvalue_rl_count == 2) { - // Neither prong of the if consumed the result location, so we can - // use break instructions to create an rvalue. - elide_store_to_block_ptr_instructions = true; - break :blk Strategy.break_operand; - } else { - // Allow the store_to_block_ptr instructions to remain so that - // semantic analysis can turn them into bitcasts. - break :blk Strategy.break_void; - } - }, - }; - switch (strategy) { + const strat = rlStrategy(rl, &block_scope); + switch (strat.tag) { .break_void => { if (!then_result.tag.isNoReturn()) { _ = try addZirInstTag(mod, then_sub_scope, then_src, .break_void, .{ @@ -1799,7 +1804,7 @@ fn ifExpr(mod: *Module, scope: *Scope, rl: ResultLoc, if_node: *ast.Node.If) Inn .block = block, }); } - assert(!elide_store_to_block_ptr_instructions); + assert(!strat.elide_store_to_block_ptr_instructions); try copyBodyNoEliding(&condbr.positionals.then_body, then_scope); try copyBodyNoEliding(&condbr.positionals.else_body, else_scope); return &block.base; @@ -1823,7 +1828,7 @@ fn ifExpr(mod: *Module, scope: *Scope, rl: ResultLoc, if_node: *ast.Node.If) Inn .block = block, }); } - if (elide_store_to_block_ptr_instructions) { + if (strat.elide_store_to_block_ptr_instructions) { try copyBodyWithElidedStoreBlockPtr(&condbr.positionals.then_body, then_scope); try copyBodyWithElidedStoreBlockPtr(&condbr.positionals.else_body, else_scope); } else { @@ -3376,6 +3381,72 @@ fn rvalueVoid(mod: *Module, scope: *Scope, rl: ResultLoc, node: *ast.Node, resul return rvalue(mod, scope, rl, void_inst); } +fn rlStrategy(rl: ResultLoc, block_scope: *Scope.GenZIR) ResultLoc.Strategy { + var elide_store_to_block_ptr_instructions = false; + switch (rl) { + // In this branch there will not be any store_to_block_ptr instructions. + .discard, .none, .ty, .ref => return .{ + .tag = .break_operand, + .elide_store_to_block_ptr_instructions = false, + }, + // The pointer got passed through to the sub-expressions, so we will use + // break_void here. + // In this branch there will not be any store_to_block_ptr instructions. + .ptr => return .{ + .tag = .break_void, + .elide_store_to_block_ptr_instructions = false, + }, + .inferred_ptr, .bitcasted_ptr, .block_ptr => { + if (block_scope.rvalue_rl_count == block_scope.break_count) { + // Neither prong of the if consumed the result location, so we can + // use break instructions to create an rvalue. + return .{ + .tag = .break_operand, + .elide_store_to_block_ptr_instructions = true, + }; + } else { + // Allow the store_to_block_ptr instructions to remain so that + // semantic analysis can turn them into bitcasts. + return .{ + .tag = .break_void, + .elide_store_to_block_ptr_instructions = false, + }; + } + }, + } +} + +fn setBlockResultLoc(block_scope: *Scope.GenZIR, parent_rl: ResultLoc) void { + // Depending on whether the result location is a pointer or value, different + // ZIR needs to be generated. In the former case we rely on storing to the + // pointer to communicate the result, and use breakvoid; in the latter case + // the block break instructions will have the result values. + // One more complication: when the result location is a pointer, we detect + // the scenario where the result location is not consumed. In this case + // we emit ZIR for the block break instructions to have the result values, + // and then rvalue() on that to pass the value to the result location. + switch (parent_rl) { + .discard, .none, .ty, .ptr, .ref => { + block_scope.break_result_loc = parent_rl; + }, + + .inferred_ptr => |ptr| { + block_scope.rl_ptr = &ptr.base; + block_scope.break_result_loc = .{ .block_ptr = block_scope }; + }, + + .bitcasted_ptr => |ptr| { + block_scope.rl_ptr = &ptr.base; + block_scope.break_result_loc = .{ .block_ptr = block_scope }; + }, + + .block_ptr => |parent_block_scope| { + block_scope.rl_ptr = parent_block_scope.rl_ptr.?; + block_scope.break_result_loc = .{ .block_ptr = block_scope }; + }, + } +} + pub fn addZirInstTag( mod: *Module, scope: *Scope, diff --git a/src/codegen.zig b/src/codegen.zig index 1f5aad8ab8..362b04ab26 100644 --- a/src/codegen.zig +++ b/src/codegen.zig @@ -846,7 +846,7 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { .br => return self.genBr(inst.castTag(.br).?), .br_block_flat => return self.genBrBlockFlat(inst.castTag(.br_block_flat).?), .breakpoint => return self.genBreakpoint(inst.src), - .brvoid => return self.genBrVoid(inst.castTag(.brvoid).?), + .br_void => return self.genBrVoid(inst.castTag(.br_void).?), .bool_and => return self.genBoolOp(inst.castTag(.bool_and).?), .bool_or => return self.genBoolOp(inst.castTag(.bool_or).?), .call => return self.genCall(inst.castTag(.call).?), @@ -2442,10 +2442,10 @@ fn Function(comptime arch: std.Target.Cpu.Arch) type { } } - fn genBrBlockFlat(self: *Self, parent_inst: *ir.Inst.BrBlockFlat) !MCValue { - try self.genBody(parent_inst.body); - const last = parent_inst.body.instructions[parent_inst.body.instructions.len - 1]; - return self.br(parent_inst.base.src, parent_inst.block, last); + fn genBrBlockFlat(self: *Self, inst: *ir.Inst.BrBlockFlat) !MCValue { + try self.genBody(inst.body); + const last = inst.body.instructions[inst.body.instructions.len - 1]; + return self.br(inst.base.src, inst.block, last); } fn genBr(self: *Self, inst: *ir.Inst.Br) !MCValue { diff --git a/src/ir.zig b/src/ir.zig index 4d421dda4c..408efc3bba 100644 --- a/src/ir.zig +++ b/src/ir.zig @@ -69,7 +69,7 @@ pub const Inst = struct { /// replace one br operand with multiple instructions, without moving anything else around. br_block_flat, breakpoint, - brvoid, + br_void, call, cmp_lt, cmp_lte, @@ -166,7 +166,7 @@ pub const Inst = struct { .block => Block, .br => Br, .br_block_flat => BrBlockFlat, - .brvoid => BrVoid, + .br_void => BrVoid, .call => Call, .condbr => CondBr, .constant => Constant, @@ -259,7 +259,7 @@ pub const Inst = struct { pub fn breakBlock(base: *Inst) ?*Block { return switch (base.tag) { .br => base.castTag(.br).?.block, - .brvoid => base.castTag(.brvoid).?.block, + .br_void => base.castTag(.br_void).?.block, .br_block_flat => base.castTag(.br_block_flat).?.block, else => null, }; @@ -403,7 +403,7 @@ pub const Inst = struct { }; pub const BrVoid = struct { - pub const base_tag = Tag.brvoid; + pub const base_tag = Tag.br_void; base: Inst, block: *Block, diff --git a/src/zir.zig b/src/zir.zig index 301b52efc0..d372cfbf00 100644 --- a/src/zir.zig +++ b/src/zir.zig @@ -264,8 +264,7 @@ pub const Inst = struct { /// Write a value to a pointer. For loading, see `deref`. store, /// Same as `store` but the type of the value being stored will be used to infer - /// the block type. The LHS is a block instruction, whose result location is - /// being stored to. + /// the block type. The LHS is the pointer to store to. store_to_block_ptr, /// Same as `store` but the type of the value being stored will be used to infer /// the pointer type. @@ -343,6 +342,8 @@ pub const Inst = struct { /// Only checks that `lhs >= rhs` if they are ints, everything else is /// validated by the .switch instruction. switch_range, + /// Does nothing; returns a void value. + void_value, pub fn Type(tag: Tag) type { return switch (tag) { @@ -355,6 +356,7 @@ pub const Inst = struct { .ret_type, .unreachable_unsafe, .unreachable_safe, + .void_value, => NoOp, .alloc, @@ -611,6 +613,7 @@ pub const Inst = struct { .enum_type, .union_type, .struct_type, + .void_value, => false, .@"break", @@ -1640,9 +1643,9 @@ const DumpTzir = struct { try dtz.fetchInstsAndResolveConsts(br_block_flat.body); }, - .brvoid => { - const brvoid = inst.castTag(.brvoid).?; - try dtz.findConst(&brvoid.block.base); + .br_void => { + const br_void = inst.castTag(.br_void).?; + try dtz.findConst(&br_void.block.base); }, .block => { @@ -1803,9 +1806,9 @@ const DumpTzir = struct { try writer.writeAll("})\n"); }, - .brvoid => { - const brvoid = inst.castTag(.brvoid).?; - const kinky = try dtz.writeInst(writer, &brvoid.block.base); + .br_void => { + const br_void = inst.castTag(.br_void).?; + const kinky = try dtz.writeInst(writer, &br_void.block.base); if (kinky) |_| { try writer.writeAll(") // Instruction does not dominate all uses!\n"); } else { diff --git a/src/zir_sema.zig b/src/zir_sema.zig index 0297b9873a..773c782746 100644 --- a/src/zir_sema.zig +++ b/src/zir_sema.zig @@ -155,6 +155,7 @@ pub fn analyzeInst(mod: *Module, scope: *Scope, old_inst: *zir.Inst) InnerError! .switch_range => return zirSwitchRange(mod, scope, old_inst.castTag(.switch_range).?), .bool_and => return zirBoolOp(mod, scope, old_inst.castTag(.bool_and).?), .bool_or => return zirBoolOp(mod, scope, old_inst.castTag(.bool_or).?), + .void_value => return mod.constVoid(scope, old_inst.src), .container_field_named, .container_field_typed, @@ -447,6 +448,8 @@ fn zirStoreToBlockPtr( const ptr = try resolveInst(mod, scope, inst.positionals.lhs); const value = try resolveInst(mod, scope, inst.positionals.rhs); const ptr_ty = try mod.simplePtrType(scope, inst.base.src, value.ty, true, .One); + // TODO detect when this store should be done at compile-time. For example, + // if expressions should force it when the condition is compile-time known. const b = try mod.requireRuntimeBlock(scope, inst.base.src); const bitcasted_ptr = try mod.addUnOp(b, inst.base.src, ptr_ty, .bitcast, ptr); return mod.storePtr(scope, inst.base.src, bitcasted_ptr, value); -- cgit v1.2.3