LC1C partially (without peephole optimizer) ported to Zig (original = https://github.com/zseri/lc1c)

basic_block.zig

const std = @import("std");
const Allocator = std.mem.Allocator;

pub fn BasicBlock(comptime Stmt: type, comptime Cond: type) type {
  return struct {
    // entry points
    labels: std.ArrayList([]const u8),
    entp_cnt: usize,

    // exit points
    exip_norm: ?*Self,
    exip_alt: ?CondExitPoint,

    body: std.ArrayList(Stmt),

    const Self = @This();

    pub const CondExitPoint = struct {
      exip: *Self,
      cond: Cond,
    };

    pub fn init(allocator: Allocator) Self {
      return Self {
        .labels = std.ArrayList([]const u8).init(allocator),
        .entp_cnt = 0,

        .exip_norm = null,
        .exip_alt = null,

        .body = std.ArrayList(Stmt).init(allocator),
      };
    }

    // this method is also used to un-register an BB,
    // so take care to make this reentrant.
    pub fn deinit(self: *Self) void {
      //if (self.*.entp_cnt != 0) {
      //  std.debug.print("invalid BasicBlock.deinit call: entp_cnt={d} lbls={s}\n", .{ self.*.entp_cnt, self.*.labels.items });
      //  unreachable;
      //}
      self.*.labels.clearAndFree();
      self.*.body.clearAndFree();
      if (self.*.exip_norm) |exip| {
        unrefExip(exip);
      }
      self.*.exip_norm = null;
      if (self.*.exip_alt) |alt| {
        unrefExip(alt.exip);
      }
      self.*.exip_alt = null;
    }

    pub fn isUnused(self: *const Self) bool {
      return self.*.entp_cnt == 0;
    }

    pub fn isEmpty(self: *const Self) bool {
      return self.*.exip_norm == null
        and self.*.exip_alt == null
        and self.*.body.items.len == 0;
    }

    pub fn shrinkToFit(self: *Self) void {
      self.*.labels.shrinkAndFree(self.*.labels.items.len);
      self.*.body.shrinkAndFree(self.*.body.items.len);
    }

    pub fn unrefExip(self: *Self) void {
      const epcnt = &self.*.entp_cnt;
      if (epcnt.* == 0) {
        std.debug.print("BasicBlock::unref_exip: {*} has illegal state entp_cnt==0\n", .{ self });
        unreachable;
      } else {
        epcnt.* -= 1;
        if (epcnt.* == 0) {
          // propagate
          self.deinit();
        }
      }
    }
  };
}

lc1tys.zig

const std = @import("std");
const Allocator = std.mem.Allocator;
const ArrayList = std.array_list.ArrayList;

fn cmdFstrLut() [26][26][26](?Lc1Cmd) {
  comptime {
    @setEvalBranchQuota(1048576);
    var ret: [26][26][26]?Lc1Cmd = undefined;
    for (ret) |*i| {
      for (i.*) |*j| {
        for (j.*) |*k| {
          k.* = null;
        }
      }
    }
    for (.{
      .{"DEF", Lc1Cmd.Def},
      .{"LDA", Lc1Cmd.Lda},
      .{"LDB", Lc1Cmd.Ldb},
      .{"MOV", Lc1Cmd.Mov},
      .{"MAB", Lc1Cmd.Mab},
      .{"ADD", Lc1Cmd.Add},
      .{"SUB", Lc1Cmd.Sub},
      .{"AND", Lc1Cmd.And},
      .{"NOT", Lc1Cmd.Not},
      .{"JMP", Lc1Cmd.Jmp},
      .{"JPS", Lc1Cmd.Jps},
      .{"JPO", Lc1Cmd.Jpo},
      .{"CAL", Lc1Cmd.Cal},
      .{"RET", Lc1Cmd.Ret},
      .{"RRA", Lc1Cmd.Rra},
      .{"RLA", Lc1Cmd.Rla},
      .{"HLT", Lc1Cmd.Hlt},
    }) |in| {
      const key: [3:0]u8 = in[0].*;
      const value: Lc1Cmd = in[1];
      ret[key[0] - 'A'][key[1] - 'A'][key[2] - 'A'] = value;
    }
    return ret;
  }
}

pub const Error = error {
  InvalidCommand,
  InvalidArg,
  InvalidInvocation,
} || std.fmt.ParseIntError;

pub const Lc1Cmd = enum(u5) {
  // virtual commands
  Label = 0x13,
  None = 0x11,
  Def = 0x10,
  // sorted after command id
  Lda = 0x0,
  Ldb = 0x1,
  Mov = 0x2,
  Mab = 0x3,
  Add = 0x4,
  Sub = 0x5,
  And = 0x6,
  Not = 0x7,
  Jmp = 0x8,
  Jps = 0x9,
  Jpo = 0xA,
  Cal = 0xB,
  Ret = 0xC,
  Rra = 0xD,
  Rla = 0xE,
  Hlt = 0xF,

  const Self = @This();

  pub fn parse_from_str(cmd: []const u8) ?Self {
    if (cmd.len != 3) {
      return null;
    }
    const toUpper = std.ascii.toUpper;
    const ucmd = [3]u8 { toUpper(cmd[0]), toUpper(cmd[1]), toUpper(cmd[2]) };
    const lut = comptime cmdFstrLut();
    if (ucmd[0] < 'A' or ucmd[0] > 'Z' or ucmd[1] < 'A' or ucmd[1] > 'Z' or ucmd[2] < 'A' or ucmd[2] > 'Z') {
      return null;
    } else if (lut[ucmd[0] - 'A'][ucmd[1] - 'A'][ucmd[2] - 'A']) |cmd2| {
      return cmd2;
    } else {
      return null;
    }
  }

  pub fn to_str(self: *const Self) []const u8 {
    return switch (self.*) {
      .Label => "*L-",
      .None => "---",
      .Def => "DEF",
      .Lda => "LDA",
      .Ldb => "LDB",
      .Mov => "MOV",
      .Mab => "MAB",
      .Add => "ADD",
      .Sub => "SUB",
      .And => "AND",
      .Not => "NOT",
      .Jmp => "JMP",
      .Jps => "JPS",
      .Jpo => "JPO",
      .Cal => "CAL",
      .Ret => "RET",
      .Rra => "RRA",
      .Rla => "RLA",
      .Hlt => "HLT",
    };
  }

  pub fn format(
    self: *const Self,
    actual_fmt: []const u8,
    options: std.fmt.FormatOptions,
    writer: anytype,
  ) @TypeOf(writer).Error!void {
    _ = actual_fmt;
    _ = options;
    return std.fmt.format(writer, "{s}", .{ self.to_str() });
  }

  pub fn from_int(val: u4) Self {
    return @intToEnum(Self, val);
  }

  pub fn has_arg(cmd: Self) bool {
    return switch (cmd) {
      .Cal, .Def, .Jmp, .Jpo, .Jps, .Lda, .Ldb, .Mov, .Rla, .Rra => true,
      else => false,
    };
  }
};

pub const Lc1Arg = union(enum) {
  None,
  Absolute: u16,
  Relative: i16,
  IdConst: u16,
  Label: []const u8,

  const Self = @This();

  pub fn parse_from_str(arg: []const u8, is_def: bool) Error!Self {
    if (arg.len == 0) {
      return Lc1Arg.None;
    }
    const parseInt = std.fmt.parseInt;
    return switch (arg[0]) {
      '@' => Lc1Arg { .Absolute = try parseInt(u16, arg[1..], 10) },
      '.' => Lc1Arg { .Relative = try parseInt(i16, arg[1..], 10) },
      '$' => Lc1Arg { .IdConst = try parseInt(u16, arg[1..], 10) },
      '0' ... '9' => if (is_def)
          Lc1Arg { .Absolute = try parseInt(u16, arg, 10) }
        else
          error.InvalidArg,
      '-' => if (is_def)
          Lc1Arg { .Absolute = 0x3ff - try parseInt(u16, arg[1..], 10) }
        else
          error.InvalidArg,
      'A' ... 'Z', 'a' ... 'z' => Lc1Arg { .Label = arg },
      else => error.InvalidArg,
    };
  }

  pub fn typ2str(arg: Self) []const u8 {
    return switch (arg) {
      Lc1Arg.None => "none",
      Lc1Arg.Absolute => "absolute",
      Lc1Arg.Relative => "relative",
      Lc1Arg.IdConst => "ind.const",
      Lc1Arg.Label => "label",
    };
  }
};

pub const Lc1Stmt = struct {
  cmd: Lc1Cmd,
  arg: Lc1Arg,

  do_ignore: bool,

  const Self = @This();

  pub fn init() Self {
    return Self {
      .cmd = Lc1Cmd.None,
      .arg = Lc1Arg.None,
      .do_ignore = false,
    };
  }

  pub fn parse_from_str(cmd_: []const u8, arg: []const u8) Error!Self {
    const do_ignore = cmd_.len == 4 and cmd_[3] == '*';
    if (!do_ignore and cmd_.len != 3) {
      return error.InvalidCommand;
    }
    const cmd = Lc1Cmd.parse_from_str(cmd_[0..3]) orelse return error.InvalidCommand;
    const arg_ = try Lc1Arg.parse_from_str(arg, cmd == Lc1Cmd.Def);
    if ((arg_ == Lc1Arg.None) == cmd.has_arg()) {
      return error.InvalidInvocation;
    }
    return Lc1Stmt {
      .cmd = cmd,
      .arg = arg_,
      .do_ignore = do_ignore,
    };
  }

  pub fn format(
    self: *const Self,
    actual_fmt: []const u8,
    options: std.fmt.FormatOptions,
    writer: anytype,
  ) @TypeOf(writer).Error!void {
    _ = actual_fmt;
    _ = options;
    const format_ = std.fmt.format;
    try format_(writer, "{s}", .{ self.*.cmd });
    try switch (self.*.arg) {
      Lc1Arg.None => return,
      Lc1Arg.Absolute => |val| format_(writer, " {d}", .{ val }),
      Lc1Arg.Relative => |val| format_(writer, " .{d}", .{ val }),
      Lc1Arg.IdConst => |val| format_(writer, " ${d}", .{ val }),
      Lc1Arg.Label => |lbl| format_(writer, " {s}", .{ lbl }),
    };
  }
};

const expectEq = std.testing.expectEqual;

test "lc1arg parse" {
  try expectEq(Lc1Arg.parse_from_str("@5", false), Lc1Arg { .Absolute = 5 });
  try expectEq(Lc1Arg.parse_from_str(".-10", false), Lc1Arg { .Relative = -10 });
  try expectEq(Lc1Arg.parse_from_str("$30", false), Lc1Arg { .IdConst = 30 });
  try expectEq(Lc1Arg.parse_from_str("500", true), Lc1Arg { .Absolute = 500 });
  try expectEq(Lc1Arg.parse_from_str("-15", true), Lc1Arg { .Absolute = 1008 });
  try expectEq(Lc1Arg.parse_from_str("500", false), error.InvalidArg);
  try expectEq(Lc1Arg.parse_from_str("alphazent", false), Lc1Arg { .Label = "alphazent" });
  try expectEq(Lc1Arg.parse_from_str("**what", true), error.InvalidArg);
}

main.zig

const std = @import("std");
const lc1tys = @import("./lc1tys.zig");
const optimize = @import("./optimize.zig").optimize;
const Allocator = std.mem.Allocator;
const Stmt = lc1tys.Lc1Stmt;

test {
  _ = lc1tys;
  _ = optimize;
}

fn file_parse_error(file: []const u8, lineno: ?usize, msg: []const u8) void {
  const stderr = std.io.getStdErr().writer();
  if (lineno == null) {
    stderr.print("lc1c: {s}: {s}\n", .{ file, msg }) catch {};
  } else {
    stderr.print("lc1c: {s}: line {d}: {s}\n", .{ file, lineno, msg }) catch {};
  }
  @panic("fatal error");
}

fn strdup(allocator: Allocator, s: []const u8) ![]const u8 {
  const result = try allocator.alloc(u8, s.len);
  std.mem.copy(u8, result, s);
  return result;
}

fn parse_file(allocator: Allocator, fname: []const u8, f: *std.fs.File) !std.ArrayList(Stmt) {
  var stmts = std.ArrayList(Stmt).init(allocator);
  errdefer stmts.deinit();

  var buf_reader = std.io.bufferedReader(f.reader());
  var in_stream = buf_reader.reader();

  var buf: [1024]u8 = undefined;
  var lineno: usize = 0;

  while (try in_stream.readUntilDelimiterOrEof(&buf, '\n')) |line| {
    defer lineno += 1;

    // parse line; erase spaces and comments
    var tokens = std.mem.tokenize(u8, std.mem.sliceTo(line, ';'), "\r\t ");
    var tok = tokens.next() orelse continue;
    if ((tok.len > 1) and (tok[tok.len - 1] == ':')) {
      // got label
      (try stmts.addOne()).* = .{
        .cmd = lc1tys.Lc1Cmd.Label,
        .arg = lc1tys.Lc1Arg { .Label = try strdup(allocator, line[0..tok.len - 1]) },
        .do_ignore = false,
      };
      tok = tokens.next() orelse continue;
    }

    const tok2 = tokens.next();
    if (tokens.next()) |_| {
      file_parse_error(fname, lineno, "too many tokens");
    }

    if (Stmt.parse_from_str(tok, tok2 orelse "")) |stmt_| {
      var stmt = stmt_;
      switch (stmt.arg) {
        lc1tys.Lc1Arg.Label => |*lbl| {
          // make sure that labels are kept alive
          lbl.* = try strdup(allocator, lbl.*);
        },
        else => {}
      }
      (try stmts.addOne()).* = stmt;
    } else |err| {
      file_parse_error(fname, lineno, switch (err) {
        error.InvalidCommand => "invalid command",
        error.InvalidInvocation => "invalid invocation",
        error.InvalidArg => "invalid argument",
        error.Overflow => "integer overflow",
        error.InvalidCharacter => "invalid character (e.g. in integer)",
      });
    }
  }

  return stmts;
}

pub fn main() anyerror!void {
  var gpa = std.heap.GeneralPurposeAllocator(.{}){};
  const allocator = gpa.allocator();
  defer {
    const leaked = gpa.deinit();
    if (leaked) {
      std.debug.print("lc1c: ERROR: detected memory leak\n", .{});
    }
  }

  var compout: ?std.fs.File = null;
  var inp: ?std.fs.File = null;
  var inpfn: ?[]const u8 = null;
  defer {
    if (inpfn) |inpfn2| {
      allocator.free(inpfn2);
    }
    if (inp) |inp2| {
      inp2.close();
    }
    if (compout) |compout2| {
      compout2.close();
    }
  }

  {
    var argit = std.process.args();
    defer argit.deinit();
    _ = argit.skip();
    while (try argit.next(allocator)) |arg| {
      defer allocator.free(arg);
      const eql = std.mem.eql;
      if (eql(u8, arg, "--help")) {
        std.debug.print("USAGE: lc1c [-o OUTPUT_FILE] INPUT_FILE\n", .{});
        return;
      } else if (eql(u8, arg, "-o")) {
        if (try argit.next(allocator)) |outpf| {
          defer allocator.free(outpf);
          compout = try std.fs.cwd().createFile(outpf, .{});
        } else {
          std.debug.print("lc1c: ERROR: no output file given\n", .{});
          std.os.exit(1);
          return;
        }
      } else {
        inpfn = try strdup(allocator, arg);
        inp = try std.fs.cwd().openFile(arg, .{});
        break;
      }
    }
  }

  if (inpfn == null) {
    std.debug.print("lc1c: ERROR: no input file given\n", .{});
    std.os.exit(1);
    return;
  }

  var arena = std.heap.ArenaAllocator.init(allocator);
  defer arena.deinit();
  const suballocator = arena.allocator();

  var stmts = try parse_file(suballocator, inpfn.?, &inp.?);
  const stdout = std.io.getStdOut();
  const stderr = std.io.getStdErr();
  try optimize(suballocator, stderr.writer(), &stmts);

  // print code
  var real_compout = std.io.bufferedWriter((compout orelse stdout).writer());
  const real_compout_w = real_compout.writer();
  for (stmts.items) |stmt| {
    try real_compout_w.print("{s}\n", .{ stmt });
  }
  try real_compout.flush();
}

optimize.zig

const std = @import("std");
const lc1tys = @import("./lc1tys.zig");
const Allocator = std.mem.Allocator;
const Stmt = lc1tys.Lc1Stmt;
const BasicBlock = @import("./basic_block.zig").BasicBlock(Stmt, lc1tys.Lc1Cmd);

fn countActiveBlocks(bbs: *const std.ArrayList(BasicBlock)) usize {
  var ret: usize = 0;
  for (bbs.items) |*item| {
    if (!item.isUnused()) {
      ret += 1;
    }
  }
  return ret;
}

// label -> BBs which point there
const LblExipCache = std.StringHashMap(std.ArrayList(usize));
// bbid -> bbid, bb[k].exip_norm -> bb[v]
const IdExipCache = std.AutoHashMap(usize, usize);

fn jumpRegexc(
  allocator: Allocator,
  lblexc: *LblExipCache,
  idexc: *IdExipCache,
  blocks: *std.ArrayList(BasicBlock),
  arg: lc1tys.Lc1Arg,
  link2next: bool,
) !void {
  if (arg == .Label) {
    const lbl = arg.Label;
    const old_blkid = blocks.items.len - 1;
    const gop_exc = try lblexc.getOrPut(lbl, );
    if (!gop_exc.found_existing) {
      gop_exc.value_ptr.* = std.ArrayList(usize).init(allocator);
    }
    (try gop_exc.value_ptr.addOne()).* = old_blkid;
    (try blocks.addOne()).* = BasicBlock.init(allocator);
    if (link2next) {
      if (!idexc.contains(old_blkid)) {
        try idexc.put(old_blkid, blocks.items.len - 1);
      }
    }
  } else {
    unreachable;
  }
}

// this gets called in the latest optimize phase, which works mostly on resolved
// addresses to find raw byte constants in the asm-code for re-usage
fn mark_idconst(
  allocator: Allocator,
  stmts: []const Stmt,
  lbls: *std.StringHashMap(usize),
  value: u16,
) !?usize {
  const val_lo = @truncate(u6, value & 0x3f);
  const val_hi = @truncate(u4, value >> 6);
  const cmd_hi = lc1tys.Lc1Cmd.from_int(val_hi);
  if (!cmd_hi.has_arg() and val_lo != 0) {
    return null;
  }
  const lbl = try std.fmt.allocPrintZ(allocator, "${d}", .{ value });
  if (lbls.get(lbl)) |dst| {
    allocator.free(lbl);
    return dst;
  }

  var res: ?usize = null;
  for (stmts) |item, stcnt| {
    if (item.cmd != cmd_hi) {
      continue;
    }
    switch (item.arg) {
      lc1tys.Lc1Arg.Absolute => |argabs| {
        if (argabs == val_lo) {
          res = stcnt;
          break;
        }
      },
      else => continue,
    }
  }
  if (res) |res2| {
    std.debug.print("optimize: re-use existing const {d} @ {d}", .{ value, res2 });
    try lbls.put(lbl, res2);
    // don't free the label
  }
  return res;
}

fn lblexip_deinit_all(lblexc: *LblExipCache) void {
  var it = lblexc.valueIterator();
  while (it.next()) |i| {
    i.deinit();
  }
  lblexc.deinit();
}

/// this expects an arena allocator or something similar,
/// because this won't keep track of every allocation
pub fn optimize(
  allocator: Allocator,
  verbose_writer: anytype,
  stmts: *std.ArrayList(Stmt),
) !void {
  var blocks = std.ArrayList(BasicBlock).init(allocator);
  defer {
    for (blocks.items) |*item| {
      item.deinit();
    }
    blocks.deinit();
  }
  var anon_lblid: usize = 0;

  // note: we don't reallocate the blocks after initialization,
  // so that we don't need to introduce another level of indirection

  // init
  // create the entry point
  {
    const entry_point = try blocks.addOne();
    entry_point.* = BasicBlock.init(allocator);
    entry_point.*.entp_cnt += 1;

    // insert data
    var lexc_jmp = LblExipCache.init(allocator);
    var lexc_jpo = LblExipCache.init(allocator);
    var lexc_jps = LblExipCache.init(allocator);
    var lexc_dests = std.StringHashMap(usize).init(allocator);
    var idexc = IdExipCache.init(allocator);
    defer {
      lblexip_deinit_all(&lexc_jmp);
      lblexip_deinit_all(&lexc_jpo);
      lblexip_deinit_all(&lexc_jps);
      // rest excs only contains integers as keys/values
      lexc_dests.deinit();
      idexc.deinit();
    }

    for (stmts.*.items) |stmt| {
      switch (stmt.cmd) {
        .Jmp => try jumpRegexc(allocator, &lexc_jmp, &idexc, &blocks, stmt.arg, false),
        .Jps => try jumpRegexc(allocator, &lexc_jps, &idexc, &blocks, stmt.arg, true),
        .Jpo => try jumpRegexc(allocator, &lexc_jpo, &idexc, &blocks, stmt.arg, true),
        .Label => {
          const oblkid = blocks.items.len - 1;
          if (!blocks.items[oblkid].isEmpty()) {
            (try blocks.addOne()).* = BasicBlock.init(allocator);
            if (!idexc.contains(oblkid)) {
              try idexc.put(oblkid, blocks.items.len - 1);
            }
          }
          if (stmt.arg == lc1tys.Lc1Arg.Label) {
            const lbl = stmt.arg.Label;
            const gop_dst = try lexc_dests.getOrPut(lbl);
            if (gop_dst.found_existing) {
              std.debug.print("optimize: ERROR: got redefinition of label '{s}'\n", .{ lbl });
            }
            gop_dst.value_ptr.* = blocks.items.len - 1;
            (try blocks.items[blocks.items.len - 1].labels.addOne()).* = lbl;
          } else {
            unreachable;
          }
        },
        .Hlt => {
          (try blocks.addOne()).* = BasicBlock.init(allocator);
        },
        else => {
          (try blocks.items[blocks.items.len - 1].body.addOne()).* = stmt;
        },
      }
    }

    // cleanup data
    for (blocks.items) |*blk| {
      if (blk.*.labels.items.len == 0) {
        (try blk.*.labels.addOne()).* = try std.fmt.allocPrintZ(allocator, "%{d}", .{ anon_lblid });
        anon_lblid += 1;
      }
      blk.shrinkToFit();
      for (blk.*.body.items) |*i| {
        switch (i.*.arg) {
          lc1tys.Lc1Arg.Label => |lbl| {
            if (lexc_dests.get(lbl)) |dst| {
              blocks.items[dst].entp_cnt += 1;
            } else {
              std.debug.print("optimize: ERROR: missing label '{s}'\n", .{ lbl });
            }
          },
          else => {
            // do nothing
          },
        }
      }
    }

    // resolve jumps
    var idit = idexc.iterator();
    while (idit.next()) |i| {
      const jmpdst = &blocks.items[i.value_ptr.*];
      blocks.items[i.key_ptr.*].exip_norm = jmpdst;
      jmpdst.*.entp_cnt += 1;
    }
    var dstsit = lexc_dests.iterator();
    while (dstsit.next()) |i| {
      const jmpdst = &blocks.items[i.value_ptr.*];
      if (lexc_jmp.get(i.key_ptr.*)) |j| {
        for (j.items) |k| {
          const jmpsrc = &blocks.items[k];
          if (jmpsrc.*.exip_norm) |_| {
            unreachable;
          }
          jmpsrc.*.exip_norm = jmpdst;
          jmpdst.*.entp_cnt += 1;
        }
      }
      if (lexc_jpo.get(i.key_ptr.*)) |j| {
        for (j.items) |k| {
          const jmpsrc = &blocks.items[k];
          if (jmpsrc.*.exip_alt) |_| {
            unreachable;
          }
          jmpsrc.*.exip_alt = BasicBlock.CondExitPoint {
            .exip = jmpdst,
            .cond = lc1tys.Lc1Cmd.Jpo,
          };
          jmpdst.*.entp_cnt += 1;
        }
      }
      if (lexc_jps.get(i.key_ptr.*)) |j| {
        for (j.items) |k| {
          const jmpsrc = &blocks.items[k];
          if (jmpsrc.*.exip_alt) |_| {
            unreachable;
          }
          jmpsrc.*.exip_alt = BasicBlock.CondExitPoint {
            .exip = jmpdst,
            .cond = lc1tys.Lc1Cmd.Jps,
          };
          jmpdst.*.entp_cnt += 1;
        }
      }
    }
  }

  stmts.clearRetainingCapacity();

  // run
  var cur_active_bbs = countActiveBlocks(&blocks);
  while(true) {
    // run
    
    // search for blocks with use_count == 1 and "used_from block" direct jump to (1 <-), simplify
    const items: []BasicBlock = blocks.items;
    for (items) |*i| {
      if (!(
        i.*.exip_norm != null
        and i.*.exip_alt == null
        and i.*.exip_norm.?.entp_cnt == 1
      )) {
        continue;
      }
      const othblk = i.*.exip_norm.?;
      const othv = &othblk.*.body;
      try i.*.body.appendSlice(othv.*.items);
      othv.*.clearAndFree();
      // update jumps
      i.*.exip_alt = othblk.*.exip_alt;
      i.*.exip_norm = othblk.*.exip_norm;
      if (i.*.exip_norm) |n2| {
        n2.*.entp_cnt += 1;
      }
      othblk.unrefExip();
    }

    // check for changes
    const new_active_bbs = countActiveBlocks(&blocks);
    //if (cur_active_bbs == new_active_bbs) {
    //  break;
    //} else {
      cur_active_bbs = new_active_bbs;
      try std.fmt.format(verbose_writer, "optimize: DEBUG: current blocks...\n", .{});
      for (blocks.items) |*i, n| {
        try std.fmt.format(verbose_writer, "BB {d} used by {d}\n", .{ n, i.*.entp_cnt });
        for (i.*.labels.items) |lbl| {
          try std.fmt.format(verbose_writer, " LBL {s}\n", .{ lbl });
        }
        for (i.*.body.items) |stmt| {
          try std.fmt.format(verbose_writer, "    {s}\n", .{ stmt });
        }
        if (i.*.exip_norm) |exip_norm| {
          try std.fmt.format(verbose_writer, " X-:", .{});
          for (exip_norm.*.labels.items) |tlbl| {
            try std.fmt.format(verbose_writer, " {s}", .{ tlbl });
          }
          try std.fmt.format(verbose_writer, "\n", .{});
        }
        if (i.*.exip_alt) |exip_alt| {
          try std.fmt.format(verbose_writer, " X{s}:", .{ exip_alt.cond });
          for (exip_alt.exip.*.labels.items) |tlbl| {
            try std.fmt.format(verbose_writer, " {s}", .{ tlbl });
          }
          try std.fmt.format(verbose_writer, "\n", .{});
        }
      }
      try std.fmt.format(verbose_writer, "\n", .{});
    //}
    if (cur_active_bbs == new_active_bbs) {
      break;
    }
  }

  var labels = std.StringHashMap(usize).init(allocator);
  defer labels.deinit();

  // reconstruct stmts
  for (blocks.items) |*item, blkid| {
    if (item.isUnused()) {
      continue;
    }

    // create labels
    for (item.*.labels.items) |lbl| {
      try labels.put(lbl, stmts.items.len);
    }

    // append commands
    try stmts.appendSlice(item.*.body.items);

    if (item.*.exip_alt) |exip_alt| {
      (try stmts.addOne()).* = Stmt {
        .cmd = exip_alt.cond,
        .arg = lc1tys.Lc1Arg { .Label = exip_alt.exip.*.labels.items[0] },
        .do_ignore = false,
      };
    }

    if (item.*.exip_norm) |exip_norm| {
      if (blocks.items.len == blkid or exip_norm != &blocks.items[blkid + 1]) {
        // jump after this block (non-linear flow)
        (try stmts.addOne()).* = Stmt {
          .cmd = lc1tys.Lc1Cmd.Jmp,
          .arg = lc1tys.Lc1Arg { .Label = exip_norm.*.labels.items[0] },
          .do_ignore = false,
        };
      }
      // otherwise fallthrough
    } else {
      (try stmts.addOne()).* = Stmt {
        .cmd = lc1tys.Lc1Cmd.Hlt,
        .arg = lc1tys.Lc1Arg.None,
        .do_ignore = false,
      };
    }
    // we can't call deinit here because we still need e.g. the labels
    // TODO: why does the original code call unref_all_exips here?
  }

  // resolve idconsts and labels
  var extraStmts = std.ArrayList(Stmt).init(allocator);
  defer extraStmts.deinit();

  for (stmts.*.items) |*i| {
    switch (i.*.arg) {
      lc1tys.Lc1Arg.IdConst => |j| {
        if (try mark_idconst(allocator, stmts.items, &labels, j)) |k| {
          i.*.arg = lc1tys.Lc1Arg { .Absolute = @truncate(u16, k) };
        } else {
          (try extraStmts.addOne()).* = Stmt {
            .cmd = lc1tys.Lc1Cmd.Def,
            .arg = lc1tys.Lc1Arg { .Absolute = @truncate(u16, j) },
            .do_ignore = true,
          };
          const k = stmts.*.items.len + extraStmts.items.len - 1;
          try labels.put(try std.fmt.allocPrintZ(allocator, "${d}", .{ j }), k);
          i.*.arg = lc1tys.Lc1Arg { .Absolute = @truncate(u16, k) };
        }
      },
      lc1tys.Lc1Arg.Label => |lbl| {
        if (labels.get(lbl)) |trg| {
          i.*.arg = lc1tys.Lc1Arg { .Absolute = @truncate(u16, trg) };
        } else {
          std.debug.print("lc1c: ERROR: undefined label {s} @ cmd {s}\n", .{ lbl, i.*.cmd });
          @panic("undefined label");
        }
      },
      else => continue,
    }
  }

  try stmts.appendSlice(extraStmts.items);
}