From 3cc68bd9138b5fda6d6066d9c49f7e1b5e04a5ee Mon Sep 17 00:00:00 2001 From: Vexu Date: Tue, 20 Oct 2020 23:10:15 +0300 Subject: stage2: switch liveness analysis --- src/liveness.zig | 85 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 85 insertions(+) (limited to 'src/liveness.zig') diff --git a/src/liveness.zig b/src/liveness.zig index d528e09ce7..7b5ef8dc35 100644 --- a/src/liveness.zig +++ b/src/liveness.zig @@ -144,6 +144,91 @@ fn analyzeInst( // instruction, and the deaths flag for the CondBr instruction will indicate whether the // condition's lifetime ends immediately before entering any branch. }, + .switchbr => { + const inst = base.castTag(.switchbr).?; + + const Table = std.AutoHashMap(*ir.Inst, void); + const case_tables = try table.allocator.alloc(Table, inst.cases.len + 1); // +1 for else + defer table.allocator.free(case_tables); + + std.mem.set(Table, case_tables, Table.init(table.allocator)); + defer for (case_tables) |*ct| ct.deinit(); + + for (inst.cases) |case, i| { + try analyzeWithTable(arena, table, &case_tables[i], case.body); + + // Reset the table back to its state from before the case. + var it = case_tables[i].iterator(); + while (it.next()) |entry| { + table.removeAssertDiscard(entry.key); + } + } + { // else + try analyzeWithTable(arena, table, &case_tables[case_tables.len - 1], inst.else_body); + + // Reset the table back to its state from before the case. + var it = case_tables[case_tables.len - 1].iterator(); + while (it.next()) |entry| { + table.removeAssertDiscard(entry.key); + } + } + + const List = std.ArrayList(*ir.Inst); + const case_deaths = try table.allocator.alloc(List, case_tables.len); // +1 for else + defer table.allocator.free(case_deaths); + + std.mem.set(List, case_deaths, List.init(table.allocator)); + defer for (case_deaths) |*cd| cd.deinit(); + + var total_deaths: u32 = 0; + for (case_tables) |*ct, i| { + total_deaths += ct.count(); + var it = ct.iterator(); + while (it.next()) |entry| { + const case_death = entry.key; + for (case_tables) |*ct_inner, j| { + if (i == j) continue; + if (!ct_inner.contains(case_death)) { + try case_deaths[i].append(case_death); + } + } + // undo resetting the table + _ = try table.put(case_death, {}); + } + } + + // Now we have to correctly populate new_set. + if (new_set) |ns| { + try ns.ensureCapacity(@intCast(u32, ns.count() + total_deaths)); + for (case_tables) |*ct| { + var it = ct.iterator(); + while (it.next()) |entry| { + _ = ns.putAssumeCapacity(entry.key, {}); + } + } + } + + total_deaths = 0; + for (case_deaths[0 .. case_deaths.len - 1]) |*ct, i| { + inst.cases[i].index = total_deaths; + const len = std.math.cast(@TypeOf(inst.else_deaths), ct.items.len) catch return error.OutOfMemory; + inst.cases[i].deaths = len; + total_deaths += len; + } + { // else + const else_deaths = std.math.cast(@TypeOf(inst.else_deaths), case_deaths[case_deaths.len - 1].items.len) catch return error.OutOfMemory; + inst.else_index = total_deaths; + inst.else_deaths = else_deaths; + total_deaths += else_deaths; + } + + const allocated_slice = try arena.alloc(*ir.Inst, total_deaths); + inst.deaths = allocated_slice.ptr; + for (case_deaths[0 .. case_deaths.len - 1]) |*cd, i| { + std.mem.copy(*ir.Inst, inst.caseDeaths(i), cd.items); + } + std.mem.copy(*ir.Inst, inst.elseDeaths(), case_deaths[case_deaths.len - 1].items); + }, else => {}, } -- cgit v1.2.3 From 22ec5e085914d9fd7b17a28a8d3ad01258f3ad03 Mon Sep 17 00:00:00 2001 From: Vexu Date: Fri, 30 Oct 2020 15:57:18 +0200 Subject: stage2: fix typo in liveness; add comptime switch test --- src/liveness.zig | 3 ++- test/stage2/test.zig | 37 +++++++++++++++++++++++++++++++++++++ 2 files changed, 39 insertions(+), 1 deletion(-) (limited to 'src/liveness.zig') diff --git a/src/liveness.zig b/src/liveness.zig index 7b5ef8dc35..0d759f8312 100644 --- a/src/liveness.zig +++ b/src/liveness.zig @@ -189,7 +189,8 @@ fn analyzeInst( for (case_tables) |*ct_inner, j| { if (i == j) continue; if (!ct_inner.contains(case_death)) { - try case_deaths[i].append(case_death); + // instruction is not referenced in this case + try case_deaths[j].append(case_death); } } // undo resetting the table diff --git a/test/stage2/test.zig b/test/stage2/test.zig index 7e1de126b6..51bde87ab0 100644 --- a/test/stage2/test.zig +++ b/test/stage2/test.zig @@ -974,6 +974,43 @@ pub fn addCases(ctx: *TestContext) !void { , "hello\nhello\nhello\nhello\nhello\n", ); + + // comptime switch + + // Basic for loop + case.addCompareOutput( + \\pub export fn _start() noreturn { + \\ assert(foo() == 1); + \\ exit(); + \\} + \\ + \\fn foo() u32 { + \\ const a: comptime_int = 1; + \\ var b: u32 = 0; + \\ switch (a) { + \\ 1 => b = 1, + \\ 2 => b = 2, + \\ else => unreachable, + \\ } + \\ return b; + \\} + \\ + \\pub fn assert(ok: bool) void { + \\ if (!ok) unreachable; // assertion failure + \\} + \\ + \\fn exit() noreturn { + \\ asm volatile ("syscall" + \\ : + \\ : [number] "{rax}" (231), + \\ [arg1] "{rdi}" (0) + \\ : "rcx", "r11", "memory" + \\ ); + \\ unreachable; + \\} + , + "", + ); } { -- cgit v1.2.3