#!/bin/bash
: <<'````````bash'
# Programming Exercise 6: Liveness Analysis

This is the continuation of hw5-new. You can continue from your own code or use the solution from the website as starting point.

**Note:** the tester currently does _not_ validate that all live-out values are actually used (i.e., it can be fooled by marking more values as live-out than correct). Test coverage is probably also lower than it should be.

## Implementation

Implement a liveness analysis for your low-level SSA IR.


## Analysis (write answers as comment in your code)

Test your implementation with larger inputs. What is the observed asymptotic runtime?


## Output Specification

- At the beginning of a basic block before the first instruction, print a line starting with `%livein` followed by all virtual registers that are live-in (e.g. `%livein 1 3 5`). Phi nodes must be live-in.
- At the end of a basic block after the terminator, print a line starting with `%liveout` followed by all virtual registers that are live-out (e.g. `%liveout 1 3 5`). Values used in phi nodes of successors must be live-out.
- For every instruction operand that is killed, the register must be prefixed with `k`, possibly including the result value. If a killed operand is used multiple times in the same instruction, only the last use shall be marked as kill.


## Command Line Interface

    usage: ./bc3 (-a|-c|-l|-i|-L) program_file
        B compiler. Exit with non-zero status code on invalid input.
        -a: print AST as S-Expressions.
        -c: syntax/semantic check only (build AST nonetheless). No output other than the exit code.
        -l: emit LLVM-IR.
        -i: emit instruction-selected IR.
        -L: emit instruction-selected IR with liveness information.
        program_file: file that contains the input program

Note that `program_file` is not necessarily a regular file, but can also be a pipe as used in the tests below, where you cannot determine the input size without reading it.

You can add extra options, e.g., to control optimizations or for debugging, but do not assign `-r`, and `-S`, which will be used in subsequent homework.


## Submission

- Submission deadline: 2025-12-17 23:59
- Submit using `curl --data-binary "@<your-submission-file>" 'https://db.in.tum.de/teaching/ws2526/codegen/submit.py?hw=6&matrno=<your-matrno>'`


````````bash
set -euo pipefail

FAILED=0
testcase_ec() { if ./bc3 -L "$3" | ./cgmir -l; s="${PIPESTATUS[@]}"; [ "$s" != "0 $2" ]; \
    then echo "FAILED: $1 (got [$s] expected [0 $2])"; FAILED=1; fi; }
testcase_run_chk() { ./bc3 -L "$2" | ./cgmir -l | "${@:3}" || { echo "FAILED: $1"; FAILED=1; }; }

extract() { TMP=$(mktemp); cat > "$TMP"; cmp -s "$1" "$TMP" && rm "$TMP" || mv "$TMP" "$1"; }

# Extract interpreter for output.
extract cgmir.cc <<EOF
#include <array>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <dlfcn.h>
#include <iostream>
#include <memory>
#include <ranges>
#include <string>
#include <string_view>
#include <unordered_map>
#include <unordered_set>
#include <vector>

static bool virtualRegs = true;
static bool verbose = false;

// TARGET_OP(name, retinfo, opinfo, clobbers)
//   retinfo: 0=void; 1=reg; 2=reg-fixed (bits 7:4 indicate register);
//            3=reg-tied (must be identical to first op), 4=terminator.
//   optypes: 8-bit units, elements: 0=none/end; 1=reg; 2=reg-fixed (bits 7:4
//            indicate register); 3=reg-opt (can be unset, for memory operands);
//            4=imm32; 5=imm64; 6=imm-scale (1/2/4/8, for memory operands);
//            7=basic block, 8=call target.
//   clobbers: bit set of registers that are clobbered.
//
// Notes:
// - XOR64zero is special; while it does have operands in reality, they are not
//   read. We therefore model this as instruction that doesn't have inputs.
// - Memory operands are always 0x04030603 (base, scale, idx, off).
#define TARGET_OPS                                                             \
  TARGET_OP(PseudoPhi, 0x01, 0x0105, 0)           /* Phi block:r64 */          \
  TARGET_OP(PseudoRegArg, 0x01, 0x05, 0)          /* Register argument i */    \
  TARGET_OP(PseudoSP, 0x42, 0, 0)                 /* Stack pointer */          \
  TARGET_OP(PseudoFP, 0x52, 0, 0)                 /* Frame pointer */          \
  TARGET_OP(RET, 0x04, 0x02, 0)                   /* RET (rax) */              \
  TARGET_OP(JMP, 0x04, 0x07, 0)                   /* JMP target */             \
  TARGET_OP(JCC, 0x04, 0x070705, 0)               /* Jcc cond, then, else */   \
  TARGET_OP(CALL, 0x02, 0x92821222627208, 0x0fc7) /* CALL target, r64... */    \
  TARGET_OP(SETCC8r, 0x01, 0x05, 0)               /* SETCC r8, cond */         \
  TARGET_OP(LEA64rm, 0x01, 0x04030603, 0)         /* LEA r64, mem */           \
  TARGET_OP(MOV64rr, 0x01, 0x01, 0)               /* MOV r64, r64 */           \
  TARGET_OP(MOV64ri, 0x01, 0x05, 0)               /* MOV r64, imm */           \
  TARGET_OP(MOV64rm, 0x01, 0x04030603, 0)         /* MOV r64, mem */           \
  TARGET_OP(MOV64mr, 0x00, 0x0104030603, 0)       /* MOV mem, r64 */           \
  TARGET_OP(MOV64mi, 0x00, 0x0404030603, 0)       /* MOV mem, imm */           \
  TARGET_OP(MOV32rr, 0x01, 0x01, 0)               /* MOV r32, r32 */           \
  TARGET_OP(MOV32ri, 0x01, 0x05, 0)               /* MOV r32, imm */           \
  TARGET_OP(MOV32rm, 0x01, 0x04030603, 0)         /* MOV r32, mem */           \
  TARGET_OP(MOV32mr, 0x00, 0x0104030603, 0)       /* MOV mem, r32 */           \
  TARGET_OP(MOV32mi, 0x00, 0x0404030603, 0)       /* MOV mem, imm */           \
  TARGET_OP(MOV16mr, 0x00, 0x0104030603, 0)       /* MOV mem, r16 */           \
  TARGET_OP(MOV16mi, 0x00, 0x0404030603, 0)       /* MOV mem, imm */           \
  TARGET_OP(MOV8mr, 0x00, 0x0104030603, 0)        /* MOV mem, r8 */            \
  TARGET_OP(MOV8mi, 0x00, 0x0404030603, 0)        /* MOV mem, imm */           \
  TARGET_OP(MOVZXB32rr, 0x01, 0x01, 0)            /* MOVZX r32, r8 */          \
  TARGET_OP(MOVZXB32rm, 0x01, 0x04030603, 0)      /* MOVZX r32, mem8 */        \
  TARGET_OP(MOVZXW32rr, 0x01, 0x01, 0)            /* MOVZX r32, r16 */         \
  TARGET_OP(MOVZXW32rm, 0x01, 0x04030603, 0)      /* MOVZX r32, mem16 */       \
  TARGET_OP(MOVSXB64rr, 0x01, 0x01, 0)            /* MOVSX r64, r8 */          \
  TARGET_OP(MOVSXB64rm, 0x01, 0x04030603, 0)      /* MOVSX r64, mem8 */        \
  TARGET_OP(MOVSXW64rr, 0x01, 0x01, 0)            /* MOVSX r64, r16 */         \
  TARGET_OP(MOVSXW64rm, 0x01, 0x04030603, 0)      /* MOVSX r64, mem16 */       \
  TARGET_OP(MOVSXD64rr, 0x01, 0x01, 0)            /* MOVSX r64, r32 */         \
  TARGET_OP(MOVSXD64rm, 0x01, 0x04030603, 0)      /* MOVSX r64, mem32 */       \
  TARGET_OP(NEG64r, 0x03, 0x01, 0)                /* NEG r64 */                \
  TARGET_OP(NOT64r, 0x03, 0x01, 0)                /* NOT r64 */                \
  TARGET_OP(ADD64rr, 0x03, 0x0101, 0)             /* ADD r64, r64 */           \
  TARGET_OP(ADD64ri, 0x03, 0x0401, 0)             /* ADD r64, imm */           \
  TARGET_OP(ADD64rm, 0x03, 0x0403060301, 0)       /* ADD r64, mem */           \
  TARGET_OP(ADD64mr, 0x00, 0x0104030603, 0)       /* ADD mem, r64 */           \
  TARGET_OP(ADD64mi, 0x00, 0x0404030603, 0)       /* ADD mem, imm */           \
  TARGET_OP(SUB64rr, 0x03, 0x0101, 0)             /* SUB r64, r64 */           \
  TARGET_OP(SUB64ri, 0x03, 0x0401, 0)             /* SUB r64, imm */           \
  TARGET_OP(SUB64rm, 0x03, 0x0403060301, 0)       /* SUB r64, mem */           \
  TARGET_OP(SUB64mr, 0x00, 0x0104030603, 0)       /* SUB mem, r64 */           \
  TARGET_OP(SUB64mi, 0x00, 0x0404030603, 0)       /* SUB mem, imm */           \
  TARGET_OP(XOR64rr, 0x03, 0x0101, 0)             /* XOR r64, r64 */           \
  TARGET_OP(XOR64ri, 0x03, 0x0401, 0)             /* XOR r64, imm */           \
  TARGET_OP(XOR64rm, 0x03, 0x0403060301, 0)       /* XOR r64, mem */           \
  TARGET_OP(XOR64mr, 0x00, 0x0104030603, 0)       /* XOR mem, r64 */           \
  TARGET_OP(XOR64mi, 0x00, 0x0404030603, 0)       /* XOR mem, imm */           \
  TARGET_OP(XOR64zero, 0x01, 0, 0)                /* XOR reg = zero */         \
  TARGET_OP(AND64rr, 0x03, 0x0101, 0)             /* AND r64, r64 */           \
  TARGET_OP(AND64ri, 0x03, 0x0401, 0)             /* AND r64, imm */           \
  TARGET_OP(AND64rm, 0x03, 0x0403060301, 0)       /* AND r64, mem */           \
  TARGET_OP(AND64mr, 0x00, 0x0104030603, 0)       /* AND mem, r64 */           \
  TARGET_OP(AND64mi, 0x00, 0x0404030603, 0)       /* AND mem, imm */           \
  TARGET_OP(OR64rr, 0x03, 0x0101, 0)              /* OR r64, r64 */            \
  TARGET_OP(OR64ri, 0x03, 0x0401, 0)              /* OR r64, imm */            \
  TARGET_OP(OR64rm, 0x03, 0x0403060301, 0)        /* OR r64, mem */            \
  TARGET_OP(OR64mr, 0x00, 0x0104030603, 0)        /* OR mem, r64 */            \
  TARGET_OP(OR64mi, 0x00, 0x0404030603, 0)        /* OR mem, imm */            \
  TARGET_OP(CMP64rr, 0x00, 0x0101, 0)             /* CMP r64, r64 */           \
  TARGET_OP(CMP64ri, 0x00, 0x0401, 0)             /* CMP r64, imm */           \
  TARGET_OP(CMP64rm, 0x00, 0x0403060301, 0)       /* CMP r64, mem */           \
  TARGET_OP(CMP64mr, 0x00, 0x0104030603, 0)       /* CMP mem, r64 */           \
  TARGET_OP(CMP64mi, 0x00, 0x0404030603, 0)       /* CMP mem, imm */           \
  TARGET_OP(TEST64rr, 0x00, 0x0101, 0)            /* TEST r64, r64 */          \
  TARGET_OP(TEST64ri, 0x00, 0x0401, 0)            /* TEST r64, imm */          \
  TARGET_OP(TEST64rm, 0x00, 0x0403060301, 0)      /* TEST r64, mem */          \
  TARGET_OP(TEST64mr, 0x00, 0x0104030603, 0)      /* TEST mem, r64 */          \
  TARGET_OP(TEST64mi, 0x00, 0x0404030603, 0)      /* TEST mem, imm */          \
  TARGET_OP(IMUL64rr, 0x03, 0x0101, 0)            /* IMUL r64, r64 */          \
  TARGET_OP(IMUL64rri, 0x01, 0x0401, 0)           /* IMUL r64, r64, imm */     \
  TARGET_OP(IMUL64rm, 0x03, 0x0403060301, 0)      /* IMUL r64, mem */          \
  TARGET_OP(IMUL64rmi, 0x01, 0x0404030603, 0)     /* IMUL r64, mem, imm */     \
  TARGET_OP(SHL64ri, 0x03, 0x0501, 0)             /* SHL r64, imm */           \
  TARGET_OP(SHL64rCL, 0x03, 0x1201, 0)            /* SHL r64, cl */            \
  TARGET_OP(SHR64ri, 0x03, 0x0501, 0)             /* SHR r64, imm */           \
  TARGET_OP(SHR64rCL, 0x03, 0x1201, 0)            /* SHR r64, cl */            \
  TARGET_OP(SAR64ri, 0x03, 0x0501, 0)             /* SAR r64, imm */           \
  TARGET_OP(SAR64rCL, 0x03, 0x1201, 0)            /* SAR r64, cl */            \
  TARGET_OP(CQO, 0x22, 0x02, 0)                   /* CQO (rdx, rax) */         \
  TARGET_OP(IDIV64r_quot, 0x02, 0x220201, 0x0004) /* IDIV r64 (quotient) */    \
  TARGET_OP(IDIV64r_rem, 0x22, 0x220201, 0x0001)  /* IDIV r64 (remainder) */

#define TARGET_OP(opname, ...) opname,
enum Opcode { TARGET_OPS };
#undef TARGET_OP

struct OpInfo {
  uint8_t ret;
  uint16_t clobbers;
  uint64_t ops;
};
#define TARGET_OP(opname, ret, ops, clobbers)                                  \
  {ret, clobbers,                                                              \
   uint8_t((ret & 0xf) - 1) < 3 ? uint64_t{ops} << 8 | ret : ops},
static constexpr OpInfo OpInfos[] = {TARGET_OPS};
#undef TARGET_OP

struct Inst {
  Opcode opc;
  uint64_t ops[8];
};

struct Func {
  std::vector<Inst> insts;
  std::vector<size_t> blockStarts;
  std::vector<std::unordered_set<uint32_t>> liveIns;
  std::vector<std::unordered_set<uint32_t>> liveOuts;
  void *native = nullptr;
};

struct RunState {
  std::vector<uint64_t> r;
  bool of = 0, sf = 0, zf = 0, af = 0, pf = 0, cf = 0;

  std::unordered_map<std::string, size_t> funcDefs;
  std::vector<std::unique_ptr<Func>> funcs;

  RunState() {
    if (!virtualRegs)
      r.resize(16);
  }

  size_t getOrInsertFuncID(const std::string &name) {
    auto [it, inserted] = funcDefs.try_emplace(name, funcs.size());
    if (inserted)
      funcs.emplace_back(std::make_unique<Func>());
    return it->second;
  }

  uint64_t &operator[](size_t idx) {
    if (virtualRegs && r.size() <= idx)
      r.resize(idx + 1);
    return r[idx];
  }

  void flags_add(uint64_t a, uint64_t b) {
    zf = (a + b == 0);
    sf = (int64_t)(a + b) < 0;
    cf = a + b < a;
    int64_t tmp;
    of = __builtin_add_overflow((int64_t)a, (int64_t)b, &tmp);
    af = pf = 0; // FIXME
  }

  void flags_sub(uint64_t a, uint64_t b) {
    zf = a == b;
    sf = (int64_t)(a - b) < 0;
    cf = a < b;
    int64_t tmp;
    of = __builtin_sub_overflow((int64_t)a, (int64_t)b, &tmp);
    af = pf = 0; // FIXME
  }

  void flags_mul(uint64_t a, uint64_t b) {
    zf = !a | !b;
    sf = (int64_t)(a * b) < 0;
    int64_t tmp;
    cf = of = __builtin_mul_overflow((int64_t)a, (int64_t)b, &tmp);
    af = pf = 0; // FIXME
  }

  void flags_logical(uint64_t r) {
    zf = !r;
    sf = (int64_t)r < 0;
    cf = of = 0;
    af = pf = 0; // FIXME
  }

  bool cond(unsigned cc) {
    switch (cc) {
    case 0: return of;
    case 1: return !of;
    case 2: return cf;
    case 3: return !cf;
    case 4: return zf;
    case 5: return !zf;
    case 6: return cf || zf;
    case 7: return !(cf || zf);
    case 8: return sf;
    case 9: return !sf;
    case 10: return pf;
    case 11: return !pf;
    case 12: return sf != of;
    case 13: return !(sf != of);
    case 14: return sf != of || zf;
    case 15: return !(sf != of || zf);
    default: return false;
    }
  }

  uint64_t addrgen(const uint64_t *memOp) {
    uint64_t base = memOp[0] == -uint64_t{1} ? 0 : (*this)[memOp[0]];
    uint64_t index = memOp[2] == -uint64_t{1} ? 0 : (*this)[memOp[2]];
    return base + memOp[1] * index + memOp[3];
  }

  template <typename T> T load(const uint64_t *memOp) {
    T res;
    memcpy(&res, reinterpret_cast<void *>(addrgen(memOp)), sizeof(T));
    if (verbose)
      std::cerr << "load " << addrgen(memOp) << "\n";
    return res;
  }

  template <typename T> void store(const uint64_t *memOp, T val) {
    if (verbose)
      std::cerr << "store " << addrgen(memOp) << " " << val << "\n";
    memcpy(reinterpret_cast<void *>(addrgen(memOp)), &val, sizeof(T));
  }

  template <typename T> static void merge(uint64_t &rv, T val) {
    uint64_t mask = -T{1};
    rv = (rv & ~mask) | (val & mask);
  }
};

using RegArgs = std::array<uint64_t, 6>;

extern "C" uint64_t runNative(uint64_t, uint64_t, uint64_t, uint64_t, uint64_t,
                              uint64_t, void *, void *);
#if defined(__x86_64__)
__asm__(
    "runNative: .intel_syntax noprefix;"
    "push rbp; mov rbp, rsp; mov rsp, [rbp + 24]; call [rbp + 16]; leave; ret;"
    ".att_syntax prefix");
#elif defined(__aarch64__)
__asm__("runNative:"
        "stp x29, x30, [sp, #-16]!; mov x29, sp;"
        "add sp, x7, #16; mov x16, x6; ldp x6, x7, [sp, #-16];"
        "blr x16; mov sp, x29; ldp x29, x30, [sp], #16; ret");
#else
#error "unsupported architecture"
#endif

uint64_t runFunc(const Func &fn, RunState &r, RegArgs args, char *stack) {
  // stack points to the bottom of the argument region.
  std::unique_ptr<char[]> frameLow{new char[0x10000]};
  size_t pc = 0;
  size_t block = 0, nextBlock;
  while (true) {
    if (verbose) {
      std::cout << "eflags=" << r.of << r.sf << r.zf << r.af << r.pf << r.cf
                << " ";
      for (size_t i = 0; i < r.r.size(); ++i)
        std::cout << "r" << i << " " << r[i] << " ";
      std::cout << "exec " << pc << "\n";
    }
    if (pc >= fn.insts.size())
      abort();
    const uint64_t *o = fn.insts[pc].ops;
    uint64_t t;
    switch (fn.insts[pc].opc) {
    case PseudoPhi:
      std::cerr << "PHIs must be at beginning of jumped-to basic block\n";
      abort();
    case PseudoSP: r[o[0]] = uintptr_t(frameLow.get() + 0x8000); break;
    case PseudoFP: r[o[0]] = uintptr_t(stack - 16); break;
    case PseudoRegArg: r[o[0]] = args[o[1]]; break;
    case RET: return r[o[0]]; break;
    case JMP:
      nextBlock = o[0];
    doJump:
      pc = fn.blockStarts[nextBlock];
      {
        std::vector<std::pair<uint64_t, uint64_t>> phiVals;
        while (fn.insts[pc].opc == PseudoPhi) {
          if (fn.insts[pc].ops[1] == block)
            phiVals.emplace_back(fn.insts[pc].ops[0], r[fn.insts[pc].ops[2]]);
          pc += 1;
        }
        for (auto [dst, val] : phiVals)
          r[dst] = val;
      }
      block = nextBlock;
      continue;
    case JCC: nextBlock = o[r.cond(o[0]) ? 1 : 2]; goto doJump;
    case CALL: {
      const Func &tgt = *r.funcs[o[1]];
      RegArgs ra;
      for (unsigned i = 0; i < 6; ++i)
        ra[i] = r[o[2 + i]];
      char *sp = frameLow.get() + 0x8000;
      if (!tgt.native) {
        std::vector<uint64_t> tmp;
        std::swap(r.r, tmp);
        uint64_t res = runFunc(tgt, r, ra, sp);
        std::swap(r.r, tmp);
        r[o[0]] = res;
      } else {
        r[o[0]] =
            runNative(ra[0], ra[1], ra[2], ra[3], ra[4], ra[5], tgt.native, sp);
      }
      break;
    }
      // clang-format off
    case SETCC8r: r.merge<uint8_t>(r[o[0]], r.cond(o[1])); break;
    case LEA64rm: r[o[0]] = r.addrgen(&o[1]); break;
    case MOV64rr: r[o[0]] = r[o[1]]; break;
    case MOV64rm: r[o[0]] = r.load<uint64_t>(&o[1]); break;
    case MOV64ri: r[o[0]] = o[1]; break;
    case MOV64mr: r.store<uint64_t>(&o[0], r[o[4]]); break;
    case MOV64mi: r.store<uint64_t>(&o[0], o[4]); break;
    case MOV32rr: r[o[0]] = uint32_t(r[o[1]]); break;
    case MOV32rm: r[o[0]] = r.load<uint32_t>(&o[1]); break;
    case MOV32ri: r[o[0]] = uint32_t(o[1]); break;
    case MOV32mr: r.store<uint32_t>(&o[0], r[o[4]]); break;
    case MOV32mi: r.store<uint32_t>(&o[0], o[4]); break;
    case MOV16mr: r.store<uint16_t>(&o[0], r[o[4]]); break;
    case MOV16mi: r.store<uint16_t>(&o[0], o[4]); break;
    case MOV8mr: r.store<uint8_t>(&o[0], r[o[4]]); break;
    case MOV8mi: r.store<uint8_t>(&o[0], o[4]); break;
    case MOVZXB32rr: r[o[0]] = uint8_t(r[o[1]]); break;
    case MOVZXB32rm: r[o[0]] = r.load<uint8_t>(&o[1]); break;
    case MOVZXW32rr: r[o[0]] = uint16_t(r[o[1]]); break;
    case MOVZXW32rm: r[o[0]] = r.load<uint16_t>(&o[1]); break;
    case MOVSXB64rr: r[o[0]] = int8_t(r[o[1]]); break;
    case MOVSXB64rm: r[o[0]] = r.load<int8_t>(&o[1]); break;
    case MOVSXW64rr: r[o[0]] = int16_t(r[o[1]]); break;
    case MOVSXW64rm: r[o[0]] = r.load<int16_t>(&o[1]); break;
    case MOVSXD64rr: r[o[0]] = int32_t(r[o[1]]); break;
    case MOVSXD64rm: r[o[0]] = r.load<int32_t>(&o[1]); break;
    case NEG64r: r.flags_sub(0, r[o[1]]); r[o[0]] = -r[o[1]]; break;
    case NOT64r: r[o[0]] = ~r[o[1]]; break;
    case ADD64rr: r.flags_add(r[o[1]], r[o[2]]); r[o[0]] = r[o[1]] + r[o[2]]; break;
    case ADD64ri: r.flags_add(r[o[1]], o[2]); r[o[0]] = r[o[1]] + o[2]; break;
    case ADD64rm: t = r.load<uint64_t>(&o[2]); r.flags_add(r[o[1]], t); r[o[0]] = r[o[1]] + t; break;
    case ADD64mr: t = r.load<uint64_t>(&o[0]); r.flags_add(t, r[o[4]]); t += r[o[4]]; r.store<uint64_t>(&o[0], t); break;
    case ADD64mi: t = r.load<uint64_t>(&o[0]); r.flags_add(t, o[4]); t += o[4]; r.store<uint64_t>(&o[0], t); break;
    case SUB64rr: r.flags_sub(r[o[1]], r[o[2]]); r[o[0]] = r[o[1]] - r[o[2]]; break;
    case SUB64ri: r.flags_sub(r[o[1]], o[2]); r[o[0]] = r[o[1]] - o[2]; break;
    case SUB64rm: t = r.load<uint64_t>(&o[2]); r.flags_sub(r[o[1]], t); r[o[0]] = r[o[1]] - t; break;
    case SUB64mr: t = r.load<uint64_t>(&o[0]); r.flags_sub(t, r[o[4]]); t -= r[o[4]]; r.store<uint64_t>(&o[0], t); break;
    case SUB64mi: t = r.load<uint64_t>(&o[0]); r.flags_sub(t, o[4]); t -= o[4]; r.store<uint64_t>(&o[0], t); break;
    case XOR64rr: r.flags_logical(r[o[1]] ^ r[o[2]]); r[o[0]] = r[o[1]] ^ r[o[2]]; break;
    case XOR64ri: r.flags_logical(r[o[1]] ^ o[2]); r[o[0]] = r[o[1]] ^ o[2]; break;
    case XOR64rm: t = r.load<uint64_t>(&o[2]); r.flags_logical(r[o[1]] ^ t); r[o[0]] = r[o[1]] ^ t; break;
    case XOR64mr: t = r.load<uint64_t>(&o[0]); r.flags_logical(t ^ r[o[4]]); t ^= r[o[4]]; r.store<uint64_t>(&o[0], t); break;
    case XOR64mi: t = r.load<uint64_t>(&o[0]); r.flags_logical(t ^ o[4]); t ^= o[4]; r.store<uint64_t>(&o[0], t); break;
    case XOR64zero: r.flags_logical(0); r[o[0]] = 0; break;
    case AND64rr: r.flags_logical(r[o[1]] & r[o[2]]); r[o[0]] = r[o[1]] & r[o[2]]; break;
    case AND64ri: r.flags_logical(r[o[1]] & o[2]); r[o[0]] = r[o[1]] & o[2]; break;
    case AND64rm: t = r.load<uint64_t>(&o[2]); r.flags_logical(r[o[1]] & t); r[o[0]] = r[o[1]] & t; break;
    case AND64mr: t = r.load<uint64_t>(&o[0]); r.flags_logical(t & r[o[4]]); t &= r[o[4]]; r.store<uint64_t>(&o[0], t); break;
    case AND64mi: t = r.load<uint64_t>(&o[0]); r.flags_logical(t & o[4]); t &= o[4]; r.store<uint64_t>(&o[0], t); break;
    case OR64rr: r.flags_logical(r[o[1]] | r[o[2]]); r[o[0]] = r[o[1]] | r[o[2]]; break;
    case OR64ri: r.flags_logical(r[o[1]] | o[2]); r[o[0]] = r[o[1]] | o[2]; break;
    case OR64rm: t = r.load<uint64_t>(&o[2]); r.flags_logical(r[o[1]] | t); r[o[0]] = r[o[1]] | t; break;
    case OR64mr: t = r.load<uint64_t>(&o[0]); r.flags_logical(t | r[o[4]]); t |= r[o[4]]; r.store<uint64_t>(&o[0], t); break;
    case OR64mi: t = r.load<uint64_t>(&o[0]); r.flags_logical(t | o[4]); t |= o[4]; r.store<uint64_t>(&o[0], t); break;
    case CMP64rr: r.flags_sub(r[o[0]], r[o[1]]); break;
    case CMP64ri: r.flags_sub(r[o[0]], o[1]); break;
    case CMP64rm: t = r.load<uint64_t>(&o[1]); r.flags_sub(r[o[0]], t); break;
    case CMP64mr: t = r.load<uint64_t>(&o[0]); r.flags_sub(t, r[o[4]]); t -= r[o[4]];  break;
    case CMP64mi: t = r.load<uint64_t>(&o[0]); r.flags_sub(t, o[4]); t -= o[4];  break;
    case TEST64rr: r.flags_logical(r[o[0]] & r[o[1]]); break;
    case TEST64ri: r.flags_logical(r[o[0]] & o[1]); break;
    case TEST64rm: t = r.load<uint64_t>(&o[1]); r.flags_logical(r[o[0]] & t); break;
    case TEST64mr: t = r.load<uint64_t>(&o[0]); r.flags_logical(t & r[o[4]]); t -= r[o[4]];  break;
    case TEST64mi: t = r.load<uint64_t>(&o[0]); r.flags_logical(t & o[4]); t -= o[4];  break;
    case IMUL64rr: r.flags_mul(r[o[1]], r[o[2]]); r[o[0]] = r[o[1]] * r[o[2]]; break;
    case IMUL64rri: r.flags_mul(r[o[1]], o[2]); r[o[0]] = r[o[1]] * o[2]; break;
    case IMUL64rm: t = r.load<uint64_t>(&o[2]); r.flags_mul(r[o[1]], t); r[o[0]] = r[o[1]] * t; break;
    case IMUL64rmi: t = r.load<uint64_t>(&o[1]); r.flags_mul(t, o[5]); r[o[0]] = t * o[5]; break;
    case SHL64ri: /* TODO: flags */ r[o[0]] = r[o[1]] << (o[2] & 0x3f); break;
    case SHL64rCL: /* TODO: flags */ r[o[0]] = r[o[1]] << (r[o[2]] & 0x3f); break;
    case SHR64ri: /* TODO: flags */ r[o[0]] = r[o[1]] >> (o[2] & 0x3f); break;
    case SHR64rCL: /* TODO: flags */ r[o[0]] = r[o[1]] >> (r[o[2]] & 0x3f); break;
    case SAR64ri: /* TODO: flags */ r[o[0]] = int64_t(r[o[1]]) >> (o[2] & 0x3f); break;
    case SAR64rCL: /* TODO: flags */ r[o[0]] = int64_t(r[o[1]]) >> (r[o[2]] & 0x3f); break;
    case CQO: r[o[0]] = -uint64_t(r[o[1]] < 1); break;
      // clang-format on
    default:
      std::cerr << "unimplemented: " << fn.insts[pc].opc << "\n";
      abort();
    }
    pc += 1;
  }
}

int main(int argc, char **argv) {
  int c;
  bool liveness = false;
  while ((c = getopt(argc, argv, "vlp")) != -1) {
    switch (c) {
    case 'v': verbose = true; break;
    case 'l': liveness = true; break;
    case 'p': virtualRegs = false; break;
    default:
      fprintf(stderr, "usage: %s [-v] [-p]\n", argv[0]);
      return EXIT_FAILURE;
    }
  }

#define TARGET_OP(opname, ...) {#opname, opname},
  std::unordered_map<std::string, Opcode> opcMap = {TARGET_OPS};
#undef TARGET_OP

  RunState r;

  std::string line;
  Func *fn = nullptr;
  std::unordered_set<uint32_t> live;
  while (std::getline(std::cin, line)) {
    if (verbose)
      std::cerr << "IN:" << line << "\n";
    if (line.ends_with(':')) {
      fn = r.funcs[r.getOrInsertFuncID(line.substr(0, line.size() - 1))].get();
      if (!fn->blockStarts.empty()) {
        std::cerr << "redundant definition of " << line << "\n";
        return 1;
      }
      fn->blockStarts.push_back(0);
      fn->liveIns.emplace_back();
      continue;
    }
    assert(fn);
    size_t split = line.find(' ');
    Inst inst{};
    std::string op = line.substr(0, split);
    if (auto it = opcMap.find(op); it != opcMap.end()) {
      inst.opc = it->second;
    } else if (op == "%livein") {
      assert(fn->blockStarts.back() == fn->insts.size());
      std::string_view rem = line;
      while (split != std::string_view::npos) {
        rem.remove_prefix(split + 1);
        split = rem.find(' ');
        std::string opStr(rem.substr(0, split)); // needless copy... whatever
        uint64_t op = std::stoll(opStr);         // errors... whatever
        live.insert(op);
      }
      fn->liveIns.back().insert(live.begin(), live.end());
      continue;
    } else if (op == "%liveout") {
      assert(fn->blockStarts.back() == fn->insts.size());
      assert(fn->liveOuts.size() > 0);
      const auto &liveOut = fn->liveOuts.back();
      std::string_view rem = line;
      size_t count = 0;
      while (split != std::string_view::npos) {
        rem.remove_prefix(split + 1);
        split = rem.find(' ');
        std::string opStr(rem.substr(0, split)); // needless copy... whatever
        uint64_t op = std::stoll(opStr);         // errors... whatever
        assert(liveOut.count(op) && "missing live-out?");
        count += 1;
      }
      if (count != liveOut.size()) {
        std::cerr << "liveout mismatch; expected:";
        for (auto v : liveOut)
          std::cerr << ' ' << v;
        std::cerr << "\n";
        return 1;
      }
      continue;
    } else {
      std::cerr << "invalid opcode " << line << "\n";
      return 1;
    }
    std::string_view rem = line;
    unsigned nops = 0;
    const OpInfo &oi = OpInfos[inst.opc];
    while (split != std::string_view::npos) {
      rem.remove_prefix(split + 1);
      split = rem.find(' ');
      std::string opStr(rem.substr(0, split)); // needless copy... whatever
      unsigned opType = (oi.ops >> (nops * 8)) & 0xff;
      if (nops >= 8 || opType == 0) {
        std::cerr << "too many operands in " << line << "\n";
        std::cerr << "op type = " << opType << " " << nops << "\n";
        return 1;
      }
      if (opType == 8) {
        inst.ops[nops++] = r.getOrInsertFuncID(opStr);
        continue;
      }
      bool kill = opStr.starts_with('k');
      if (kill)
        opStr = opStr.substr(1);
      bool isReg = false;
      uint64_t op = inst.ops[nops++] = std::stoll(opStr); // errors... whatever
      switch (opType & 0xf) {
      case 1:
        isReg = true;
        if (!virtualRegs && op >= 16)
          abort();
        assert(op < 0x10000 && "so many virtual regs?");
        break;
      case 2:
        isReg = true;
        if (!virtualRegs && op != (opType >> 4))
          abort();
        break;
      case 3:
        isReg = op != -uint64_t{1};
        // TODO: tied-def/opt reg
        break;
      case 4:
        if (int64_t(op) != int32_t(op) || kill)
          abort();
        break;
      case 6:
        if ((op != 1 && op != 2 && op != 4 && op != 8) || kill)
          abort();
        break;
      case 5:
      case 7:
        if (kill)
          abort();
        break;
      case 8:
      default: assert(0);
      }
      if (liveness && isReg) {
        if (nops == 1 && (oi.ret & 3)) {
          if (!kill && inst.opc != PseudoPhi) {
            auto [it, inserted] = live.insert(op);
            assert(inserted && "def already live");
          } else if (kill) {
            assert(!live.count(op) && "killed def already live");
          } else {
            assert(live.count(op) && "phi must be in live in");
            if (kill)
              live.erase(op);
          }
        } else if (nops == 1 || inst.opc != PseudoPhi) {
          if (kill) {
            bool removed = live.erase(op);
            assert(removed && "killed dead value");
          } else {
            assert(live.count(op) && "use of non-live value");
          }
        }
      }
    }

    fn->insts.push_back(inst);
    if (oi.ret == 0x04) {
      fn->blockStarts.push_back(fn->insts.size());
      fn->liveIns.emplace_back();
      fn->liveOuts.push_back(std::move(live));
      live.clear();
    }
  }

  for (auto &it : r.funcDefs) {
    Func &fn = *r.funcs[it.second];
    if (fn.insts.empty()) {
      fn.native = dlsym(nullptr, it.first.c_str());
      if (!fn.native) {
        std::cerr << "unable to resolve " << it.first << "\n";
        return 1;
      }
    } else if (fn.blockStarts.back() != fn.insts.size()) {
      std::cerr << "function must end with terminator\n";
      return 1;
    } else {
      for (size_t i = 1; i < fn.blockStarts.size(); ++i) {
        Inst &term = fn.insts[fn.blockStarts[i] - 1];
        unsigned ty = 0;
        switch (term.opc) {
        case RET: assert(fn.liveOuts[i - 1].size() == 0); break;
        case JMP: ty = 1; break;
        case JCC: ty = 2; break;
        default: assert(0 && "unexpected terminator");
        }
        for (unsigned opidx = ty - 1; opidx < ty + ty - 1; opidx++) {
          unsigned succ = term.ops[opidx];
          assert(succ < fn.blockStarts.size() - 1 && "invalid successor");
          if (liveness) {
            for (uint32_t liveIn : fn.liveIns[succ]) {
              if (!fn.liveOuts[i - 1].count(liveIn)) {
                for (size_t j = fn.blockStarts[succ];; ++j) {
                  if (fn.insts[j].opc != PseudoPhi) {
                    assert(false && "value in live-in must be in pred liveout");
                  }
                  if (fn.insts[j].ops[0] == liveIn)
                    break;
                }
              }
            }
          }
        }
      }
    }
  }

  auto mainIt = r.funcDefs.find("main");
  if (mainIt == r.funcDefs.end()) {
    std::cerr << "no main function\n";
    return 1;
  }

  std::unique_ptr<char[]> rootFrame{new char[0x8000]};
  char argv0[2] = "-";
  argv[0] = argv0;
  RegArgs mainArgs = {{1, uintptr_t(argv)}};
  return runFunc(*r.funcs[mainIt->second], r, mainArgs,
                 reinterpret_cast<char *>(rootFrame.get() + 0x8000));
}
EOF

CXX=clang++ CXXFLAGS="-O2 -g -Wall -Wextra -Wno-unused-parameter -std=c++20 $(llvm-config --cppflags --ldflags | tr '\n' ' ')" \
    LDLIBS="$(llvm-config --libs)" make bc3 cgmir -j2

testcase_ec "return 1" 0 <(echo "main(){return 0;}")
testcase_ec "return 2" 10 <(echo "main(){return 10;}")
testcase_ec "return 3" 10 <(echo "main(){return 10;return 0;}")
# NB: this is a flaky test
testcase_ec "return 4" 1 <(echo "main(argc){return argc;}")
testcase_ec "return 5" 2 <(echo "main(){return 4294967298;}")

# Test important operators: binary +/-, unary -/!.
testcase_ec "neg 1" 255 <(echo "main(){return -1;}")
testcase_ec "inv neg 1" 0 <(echo "main(){return ~(-1);}")
testcase_ec "neg inv 1" 2 <(echo "main(){return -(~1);}")
testcase_ec "neg inv 2" 3 <(echo "main(){return -~2;}")
testcase_ec "inv 2" 253 <(echo "main(){return ~2;}")
testcase_ec "not 1" 0 <(echo "main(){return !1;}")
testcase_ec "not 2" 0 <(echo "main(){return !2;}")
testcase_ec "not -1" 0 <(echo "main(){return !-1;}")
testcase_ec "not not 1" 0 <(echo "main(){return !!0;}")
testcase_ec "not not 2" 2 <(echo "main(){return 1+!!2;}")
testcase_ec "add 1" 0 <(echo "main(){return 1+(-1);}")
testcase_ec "add 2" 4 <(echo "main(){return 2+1+1;}")
testcase_ec "sub 1" 0 <(echo "main(){return 1-1;}")
testcase_ec "eq 1" 2 <(echo "main(){return (1==1)+1;}")
testcase_ec "eq 2" 11 <(echo "main(){return 10+((1==1)-(1==2));}")
testcase_ec "eq 3" 12 <(echo "main(){return 10+((1==1)+(1==1));}")

# Test some basic operators with a non-constant operand.
testcase_ec "sub argc 1" 255 <(echo "main(argc){return 0-argc;}")
testcase_ec "sub argc 2" 255 <(echo "main(argc){return -argc;}")
testcase_ec "sub argc 3" 0 <(echo "main(argc){return 1-argc;}")
testcase_ec "add argc 1" 3 <(echo "main(argc){return argc+2;}")
testcase_ec "add argc 2" 3 <(echo "main(argc){return argc+4294967298;}")
testcase_ec "inv argc 1" 254 <(echo "main(argc){return ~argc;}")
testcase_ec "eq argc 1" 255 <(echo "main(argc){return -(argc==1);}")
testcase_ec "eq argc 2" 0 <(echo "main(argc){return -(argc==2);}")

# Test function calls.
testcase_ec "call 1" 0 <(echo "fn(){return 0;}main(){return fn();}")
testcase_ec "call 2" 2 <(echo "fn(){return 1;}main(){return fn()+fn();}")
testcase_ec "call 3" 9 <(echo "main(){return fn(1);}fn(a){return 10-a;}")
testcase_ec "call 4" 0 <(echo "main(){return fn(1,2,3);}fn(a,b,c){return a+b-c;}")
testcase_ec "call 5" 0 <(echo "f(){return;}main(){f();return 0;}")
testcase_ec "call 6" 13 <(echo "f(x){return x+1;}main(){return f(1==1)+f(10);}")
testcase_ec "call 7" 15 <(echo "f(a,b,c,d,e,f,g,h){return g+h;}main(){return f(1,2,3,4,5,6,7,8);}")
testcase_ec "call 8" 115 <(echo "f(a,b,c,d,e,f,g,h,i,j,k){return g+h+i+k;}main(){return f(1,2,3,4,5,6,7,8,20,40,80);}")
testcase_ec "call 9" 99 <(echo "f(a,b,c,d,e,f,g,h,i,j,k){register l=a+b;register m=c+d;register n=e+f;register o=g+h;register p=i+j;register q=k+l;return a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q;}main(){return f(1,2,3,4,5,6,7,8,20,40,80);}")

# Test auto, addrof, and subscript
testcase_ec "auto 0" 0 <(echo "main(){auto x=0;return x;}")
testcase_ec "auto 1" 8 <(echo "main(){auto x=2;auto y=x=4;return x+y;}")
testcase_ec "auto 2" 4 <(echo "main(){auto x=2;register y=&x;y[0]=4;return x;}")
testcase_ec "auto 3" 22 <(echo "func(a){a[0]=22;}main(){auto a=1;func(&a);return a;}")
testcase_ec "auto 4" 4 <(echo "main(){auto x=2;x=4;return x;}")
testcase_ec "auto 5" 5 <(echo "main(){auto x=2;register y=&x;y[0]=4;x=x+1;return x;}")
testcase_ec "addrof 1" 0 <(echo "main(){auto x=0;(&x)[2@2]=1;(&x)[1@1]=1;return x!=4294967552;}")
testcase_ec "addrof 2" 0 <(echo "main(){auto x=0;auto y=&x;return &x-y!=0;}")
testcase_ec "addrof 3" 8 <(echo "main(){auto x=1234;auto y=&x[1];return y-x;}")
testcase_ec "addrof 4" 4 <(echo "main(){auto x=1234;auto y=&x[1@4];return y-x;}")
testcase_ec "addrof 5" 2 <(echo "main(){auto x=1234;auto y=&x[1@2];return y-x;}")
testcase_ec "addrof 6" 2 <(echo "main(){auto x=1234;auto y=&x[-1@2];return x-y;}")
testcase_ec "addrof 7" 3 <(echo "main(){auto x=3;auto p=&x-8;return p[1];}")
testcase_ec "addrof 8" 2 <(echo "main(){auto x=516;auto p=&x;return p[1@1];}")
testcase_ec "addrof 9" 4 <(echo "main(){auto x=516;auto p=&x;return p[0@1];}")
testcase_ec "addrof 10" 10 <(echo "main(){auto x=516;auto p=&x+10;return p-&x;}")
testcase_ec "addrof 11" 10 <(echo "main(){auto x=516;auto p=10+&x;return p-&x;}")
testcase_ec "addrof 12" 246 <(echo "main(){auto x=516;auto p=10+&x;return &x-p;}")
testcase_ec "addrof 13" 10 <(echo "main(){auto x=516;auto p=(&x+&x)+10;return p-&x-&x;}")
testcase_ec "addrof 14" 12 <(echo "main(){auto x=12;register p=&x;auto q=p[0];x=0;return q;}")
testcase_ec "addrof 15" 2 <(echo "main(){auto x=254;register p=(&x)[0@1];x=0;return -p;}")
testcase_ec "sext 1" 0 <(echo "main(){auto x=128;auto p=&x;return p[0@1]+128;}")
testcase_ec "sext 2" 0 <(echo "main(){auto x=128;auto p=&x;return p[0@1]>0;}")
testcase_ec "sext 3" 0 <(echo "main(){auto x=32768;auto p=&x;return p[0@2]>0;}")
testcase_ec "sext 4" 0 <(echo "main(){auto x=32767;auto p=&x;return p[0@2]<0;}")
testcase_ec "sext 5" 0 <(echo "main(){auto x=2147483648;auto p=&x;return p[0@4]>0;}")
testcase_ec "sext 6" 0 <(echo "main(){auto x=2147483647;auto p=&x;return p[0@4]<0;}")
testcase_ec "addrof call 1" 4 <(echo "f(x){x[0]=x[0]+3;}main(){auto x=1;f(&x);return x;}")
testcase_ec "addrof call 2" 7 <(echo "f(x){x[0]=x[0]+3;}main(){auto x=1;auto y=&x;f(&x);f(y);return x;}")
testcase_ec "addrof call 3" 7 <(echo "f(x){x[0]=x[0]+3;}main(){auto x=1;register y=&x;f(&x);f(y);return x;}")
testcase_ec "addrof dyngep 1" 4 <(echo "f(i){auto x=117835012;return (&x)[i@1];}main(){return f(0);}")
testcase_ec "addrof dyngep 2" 5 <(echo "f(i){auto x=117835012;return (&x)[i@1];}main(){return f(1);}")
testcase_ec "addrof dyngep 3" 6 <(echo "f(i){auto x=117835012;return (&x)[i@1];}main(){return f(2);}")
testcase_ec "addrof dyngep 4" 7 <(echo "f(i){auto x=117835012;return (&x)[i@1];}main(){return f(3);}")
testcase_ec "addrof dyngep 5" 4 <(echo "f(i){auto x=117835012;return (&x)[i@2];}main(){return f(0);}")
testcase_ec "addrof dyngep 6" 6 <(echo "f(i){auto x=117835012;return (&x)[i@2];}main(){return f(1);}")
testcase_ec "addrof dyngep 7" 0 <(echo "f(i){auto x=117835012;return (&x)[i@2];}main(){return f(2);}")

# Test if.
testcase_ec "if 1" 10 <(echo "main(){if(1)return 10;return 20;}")
testcase_ec "if 2" 10 <(echo "main(){if(4)return 10;else return 20;}")
testcase_ec "if 3" 20 <(echo "main(){if(0)return 10;return 20;}")
testcase_ec "if 4" 20 <(echo "main(){if(0)return 10;else return 20;}")
testcase_ec "if 5" 10 <(echo "main(){if(1)return 10;return 20;return 30;}")
testcase_ec "if 6" 10 <(echo "main(){if(2)return 10;else return 20;return 30;}")
testcase_ec "if 7" 20 <(echo "main(){if(!2)return 10;else return 20;}")
testcase_ec "if 8" 20 <(echo "main(){if(~-1)return 10;else return 20;}")
testcase_ec "if 9" 10 <(echo "main(){if(1==1)return 10;else return 20;}")
testcase_ec "if 10" 20 <(echo "main(){if(1!=1)return 10;else return 20;}")
testcase_ec "if 11" 20 <(echo "main(){if(1!=1)return;else return 20;}")
testcase_ec "if 12" 20 <(echo "main(){if(1)return 20;else return;}")
testcase_ec "if 13" 20 <(echo "main(){if(1)return 20;return;}")
testcase_ec "if argc 1" 10 <(echo "main(argc){if(argc<2)return 10;else return 0;}")
testcase_ec "if argc 2" 0 <(echo "main(argc){if(argc>2)return 10;else return 0;}")
testcase_ec "if argc 3" 10 <(echo "main(argc){if(argc==1)return 10;else return 0;}")
testcase_ec "if argc 4" 0 <(echo "main(argc){if(argc==2)return 10;else return 0;}")
testcase_ec "if argc 5" 0 <(echo "main(argc){if(argc!=1)return 10;else return 0;}")
testcase_ec "if argc 6" 10 <(echo "main(argc){if(argc!=2)return 10;else return 0;}")
testcase_ec "if auto 1" 5 <(echo "main(){auto x=4;if(x==4)x=5;else x=7;return x;}")
testcase_ec "if auto 2" 7 <(echo "main(){auto x=4;if(x!=4)x=5;else x=7;return x;}")
testcase_ec "if auto 3" 15 <(echo "main(){auto x=4;if(x==4)x=5;else return x;return x+10;}")
testcase_ec "if auto 4" 4 <(echo "main(){auto x=4;if(x!=4)x=5;else return x;return x+10;}")
testcase_ec "if auto 5" 5 <(echo "main(){auto x=4;if(x==4)return 5;else x=7;return x;}")
testcase_ec "if auto 6" 7 <(echo "main(){auto x=4;if(x!=4)return 5;else x=7;return x;}")
testcase_ec "if auto 7" 5 <(echo "main(){auto x=4;if(x==4)return 5;else return x;}")
testcase_ec "if auto 8" 4 <(echo "main(){auto x=4;if(x!=4)return 5;else return x;}")

# Test register (PHI nodes) (shallow tests, could definitly be expanded to cover more corner cases).
testcase_ec "reg 1" 10 <(echo "main(){register x=0;register y=10;if(y==10)x=y;return x;}")
testcase_ec "reg 2" 10 <(echo "main(){register x=0;register y=10;if(y==10)x=y;else x=5;return x;}")
testcase_ec "reg 3" 5 <(echo "main(){register x=0;register y=10;if(y!=10)x=y;else x=5;return x;}")
testcase_ec "reg 4" 0 <(echo "main(){register y=6;while(y){y=y-1;}return y;}")
testcase_ec "reg 5" 15 <(echo "main(){register x=0;register y=5;while(y){x=x+y;y=y-1;}return x;}")
testcase_ec "reg 6" 25 <(echo "main(){register a=10;register x=0;register y=5;while(y){x=x+y;y=y-1;}return a+x;}")
testcase_ec "reg 7" 16 <(echo "main(){register a=10;register x=0;register y=5;while(y){x=x+y;y=y-1;a=1;}return a+x;}")
testcase_ec "reg 8" 6 <(echo "main(){register a=1;register x=0;register y=5;while(y){x=x+a;y=y-a;}return a+x;}")
testcase_ec "reg 9" 10 <(echo "phis(a, b){a = a + b;if (a > b + b) {register c = 1;while (a > 0)a = a - c;} else {a = b + b;}return a;}main(){return phis(3,5);}")
testcase_ec "reg 10" 0 <(echo "phis(a, b){a = a + b;if (a > b + b) {register c = 1;while (a > 0)a = a - c;} else {a = b + b;}return a;}main(){return phis(5,3);}")
testcase_ec "if reg 1" 5 <(echo "main(){register x=4;if(x==4)x=5;else x=7;return x;}")
testcase_ec "if reg 2" 7 <(echo "main(){register x=4;if(x!=4)x=5;else x=7;return x;}")
testcase_ec "if reg 3" 15 <(echo "main(){register x=4;if(x==4)x=5;else return x;return x+10;}")
testcase_ec "if reg 4" 4 <(echo "main(){register x=4;if(x!=4)x=5;else return x;return x+10;}")
testcase_ec "if reg 5" 5 <(echo "main(){register x=4;if(x==4)return 5;else x=7;return x;}")
testcase_ec "if reg 6" 7 <(echo "main(){register x=4;if(x!=4)return 5;else x=7;return x;}")
testcase_ec "if reg 7" 5 <(echo "main(){register x=4;if(x==4)return 5;else return x;}")
testcase_ec "if reg 8" 4 <(echo "main(){register x=4;if(x!=4)return 5;else return x;}")
testcase_ec "while reg 1" 2 <(echo "f(x){register a=1;register b=0;while(x){x=x-1;register t=a;a=b;b=t;}return a+a+b+b+b+b;}main(){return f(12);}")
testcase_ec "while reg 2" 4 <(echo "f(x){register a=1;register b=0;while(x){x=x-1;register t=a;a=b;b=t;}return a+a+b+b+b+b;}main(){return f(13);}")

# Test || and &&.
testcase_ec "oror 1" 2 <(echo "f(a){a[0]=a[0]+2;return 1;}g(a){a[0]=a[0]+4;return 0;}main(){auto a=0;f(&a)||g(&a);return a;}")
testcase_ec "oror 2" 6 <(echo "f(a){a[0]=a[0]+2;return 0;}g(a){a[0]=a[0]+4;return 0;}main(){auto a=0;f(&a)||g(&a);return a;}")
testcase_ec "oror 3" 10 <(echo "f(){return 0;}g(){return 0;}main(){return 10+(f()||g());}")
testcase_ec "oror 4" 11 <(echo "f(){return 1;}g(){return 0;}main(){return 10+(f()||g());}")
testcase_ec "oror 5" 11 <(echo "f(){return 0;}g(){return 1;}main(){return 10+(f()||g());}")
testcase_ec "oror 6" 11 <(echo "f(){return 1;}g(){return 1;}main(){return 10+(f()||g());}")
testcase_ec "andand 1" 6 <(echo "f(a){a[0]=a[0]+2;return 1;}g(a){a[0]=a[0]+4;return 0;}main(){auto a=0;f(&a)&&g(&a);return a;}")
testcase_ec "andand 2" 2 <(echo "f(a){a[0]=a[0]+2;return 0;}g(a){a[0]=a[0]+4;return 0;}main(){auto a=0;f(&a)&&g(&a);return a;}")
testcase_ec "andand 3" 10 <(echo "f(){return 0;}g(){return 0;}main(){return 10+(f()&&g());}")
testcase_ec "andand 4" 10 <(echo "f(){return 1;}g(){return 0;}main(){return 10+(f()&&g());}")
testcase_ec "andand 5" 10 <(echo "f(){return 0;}g(){return 1;}main(){return 10+(f()&&g());}")
testcase_ec "andand 6" 11 <(echo "f(){return 1;}g(){return 1;}main(){return 10+(f()&&g());}")

# Test ==
testcase_ec "eq dyn 1" 2 <(echo "f(a,b){return (a==b)+1;}main(){return f(1,1);}")
testcase_ec "eq dyn 2" 2 <(echo "f(a,b){return (a==b)+(a==b);}main(){return f(1,1);}")
testcase_ec "eq dyn 3" 2 <(echo "f(a,b,c){return ((a==b)==c)+1;}main(){return f(1,1,1);}")
testcase_ec "eq dyn 4" 3 <(echo "f(a,b,c){return ((a==b)==c)+3;}main(){return f(1,1,0);}")
testcase_ec "eq dyn 5" 4 <(echo "f(a,b,c){return ((a==b)==c)+3;}main(){return f(0,1,0);}")

# Test ! and ~
testcase_ec "not dyn 1" 10 <(echo "f(a){return 10+!a;}main(){return f(1);}")
testcase_ec "not dyn 2" 11 <(echo "f(a){return 10+!!a;}main(){return f(-2);}")
testcase_ec "not dyn 3" 11 <(echo "f(a){return 10+!a;}main(){return f(0);}")
testcase_ec "not dyn 4" 10 <(echo "f(a){return 10+!!a;}main(){return f(0);}")
testcase_ec "inv dyn 1" 8 <(echo "f(a){return 10+~a;}main(){return f(1);}")
testcase_ec "inv dyn 2" 8 <(echo "f(a){return 10+~~a;}main(){return f(-2);}")
testcase_ec "inv dyn 3" 10 <(echo "f(a){return 10+~a;}main(){return f(-1);}")
testcase_ec "inv dyn 4" 9 <(echo "f(a){return 10+~a;}main(){return f(0);}")
testcase_ec "inv dyn 5" 10 <(echo "f(a){return 10+~~a;}main(){return f(0);}")
testcase_ec "not inv dyn 1" 8 <(echo "f(a){return 10+~!a;}main(){return f(0);}")
testcase_ec "not inv dyn 2" 9 <(echo "f(a){return 10+~!a;}main(){return f(12);}")

# Test assignment side-effect, with auto
testcase_ec "if oror 1" 4 <(echo "f(a,b,c){if((a&&b)||c)return 2;else return 4;}main(){return f(0,0,0);}")
testcase_ec "if oror 2" 2 <(echo "f(a,b,c){if((a&&b)||c)return 2;else return 4;}main(){return f(0,0,1);}")
testcase_ec "if oror 3" 4 <(echo "f(a,b,c){if((a&&b)||c)return 2;else return 4;}main(){return f(0,1,0);}")
testcase_ec "if oror 4" 2 <(echo "f(a,b,c){if((a&&b)||c)return 2;else return 4;}main(){return f(0,1,1);}")
testcase_ec "if oror 5" 4 <(echo "f(a,b,c){if((a&&b)||c)return 2;else return 4;}main(){return f(1,0,0);}")
testcase_ec "if oror 6" 2 <(echo "f(a,b,c){if((a&&b)||c)return 2;else return 4;}main(){return f(1,0,1);}")
testcase_ec "if oror 7" 2 <(echo "f(a,b,c){if((a&&b)||c)return 2;else return 4;}main(){return f(1,1,0);}")
testcase_ec "if oror 8" 2 <(echo "f(a,b,c){if((a&&b)||c)return 2;else return 4;}main(){return f(1,1,1);}")
testcase_ec "if assign 1" 22 <(echo "f(a,b,c){auto x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(0,0,0);}")
testcase_ec "if assign 2" 22 <(echo "f(a,b,c){auto x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(0,0,1);}")
testcase_ec "if assign 3" 22 <(echo "f(a,b,c){auto x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(0,1,0);}")
testcase_ec "if assign 4" 22 <(echo "f(a,b,c){auto x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(0,1,1);}")
testcase_ec "if assign 5" 20 <(echo "f(a,b,c){auto x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(1,0,0);}")
testcase_ec "if assign 6" 20 <(echo "f(a,b,c){auto x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(1,0,1);}")
testcase_ec "if assign 7" 11 <(echo "f(a,b,c){auto x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(1,1,0);}")
testcase_ec "if assign 8" 15 <(echo "f(a,b,c){auto x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(1,1,1);}")

# Test while
testcase_ec "while 1" 5 <(echo "main(){while(0){return 1;}return 5;}")
testcase_ec "while 2" 0 <(echo "main(){auto x=1;while(x){x=0;}return x;}")
testcase_ec "while 3" 10 <(echo "main(){while(1){return 10;}return 5;}")
testcase_ec "while 4" 4 <(echo "main(){while(1){if(1)return 4;else return 11;}return 5;}")
testcase_ec "while 5" 4 <(echo "main(){while(1){if(1)return 4;}return 5;}")

# Test assignment side-effect, with register
testcase_ec "if assign reg 1" 22 <(echo "f(a,b,c){register x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(0,0,0);}")
testcase_ec "if assign reg 2" 22 <(echo "f(a,b,c){register x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(0,0,1);}")
testcase_ec "if assign reg 3" 22 <(echo "f(a,b,c){register x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(0,1,0);}")
testcase_ec "if assign reg 4" 22 <(echo "f(a,b,c){register x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(0,1,1);}")
testcase_ec "if assign reg 5" 20 <(echo "f(a,b,c){register x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(1,0,0);}")
testcase_ec "if assign reg 6" 20 <(echo "f(a,b,c){register x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(1,0,1);}")
testcase_ec "if assign reg 7" 11 <(echo "f(a,b,c){register x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(1,1,0);}")
testcase_ec "if assign reg 8" 15 <(echo "f(a,b,c){register x=2;if((a&&(x=b))&&(x=x+c+c+c+c))return 10+x;else return 20+x;}main(){return f(1,1,1);}")
# Test assignment side-effect, with parameter
testcase_ec "if assign param 1" 20 <(echo "f(a,b,c){if((a&&(a=b))&&(a=2+c+c+c+c))return 10+a;else return 20+a;}main(){return f(0,0,0);}")
testcase_ec "if assign param 2" 20 <(echo "f(a,b,c){if((a&&(a=b))&&(a=2+c+c+c+c))return 10+a;else return 20+a;}main(){return f(0,0,1);}")
testcase_ec "if assign param 3" 20 <(echo "f(a,b,c){if((a&&(a=b))&&(a=2+c+c+c+c))return 10+a;else return 20+a;}main(){return f(0,1,0);}")
testcase_ec "if assign param 4" 20 <(echo "f(a,b,c){if((a&&(a=b))&&(a=2+c+c+c+c))return 10+a;else return 20+a;}main(){return f(0,1,1);}")
testcase_ec "if assign param 5" 20 <(echo "f(a,b,c){if((a&&(a=b))&&(a=2+c+c+c+c))return 10+a;else return 20+a;}main(){return f(1,0,0);}")
testcase_ec "if assign param 6" 20 <(echo "f(a,b,c){if((a&&(a=b))&&(a=2+c+c+c+c))return 10+a;else return 20+a;}main(){return f(1,0,1);}")
testcase_ec "if assign param 7" 12 <(echo "f(a,b,c){if((a&&(a=b))&&(a=2+c+c+c+c))return 10+a;else return 20+a;}main(){return f(1,1,0);}")
testcase_ec "if assign param 8" 16 <(echo "f(a,b,c){if((a&&(a=b))&&(a=2+c+c+c+c))return 10+a;else return 20+a;}main(){return f(1,1,1);}")

testcase_ec "while assign reg" 0 <(echo "f(a,b){while(a=b){}return a;}main(){return f(1,0);}")
testcase_ec "gauss 1" 3 <(echo "f(c){register a=0;register b=0;while(a<c){a=a+1;b=b+a;}return b;}main(){return f(2);}")
testcase_ec "gauss 2" 10 <(echo "f(c){register a=0;register b=0;while(a<c){a=a+1;b=b+a;}return b;}main(){return f(4);}")
testcase_ec "gauss 3" 0 <(echo "f(c){register a=0;register b=0;while(a<c){a=a+1;b=b+a;}return b;}main(){return f(0);}")

testcase_ec "shadow 1" 3 <(echo "f(a,b){if(a<10){register a=a+b;return a;}else{auto b=b;return &b[1]-&b;}}main(){return f(1,2);}")
testcase_ec "shadow 2" 2 <(echo "f(a,b){if(a<10){register a=a+b;return a;}else{auto b=b;return (&b)[0];}}main(){return f(10,2);}")

# Calling external functions works
testcase_ec "malloc free" 123 <(echo "main(){register x=malloc(8);x[0]=123;return freeread(x);}freeread(p){register r=p[0];free(p);return r;}")
testcase_run_chk "puts" <(echo "main(){auto x=36762444129608;puts(&x);return 0;}") cmp - <(echo "Hello!")
testcase_run_chk "printf" <(echo "main(argc,argv){auto f1=44629835118;printf(&f1,argc);while(argc){puts(argv[0]);argv=&argv[1];argc=argc-1;}return 0;}") cmp - <(echo -e "n=1\n-")

# One auto variable shouldn't cause a stack overflow...
testcase_ec "allocaloop" 0 <(echo "allocaloop(x){while(x){auto y=x;x=x-1;}}main(){allocaloop(10000000);return 0;}")

# If multiplication and right shift are implemented:
testcase_run_chk "mandelbrot" <(cat <<EOF
mul(a, b) { return a * b >> 28; } // 4.28 fix-point multiplication
main(argc, argv) {
  register imax = 32;
  register scale = 0;
  if (argc > 1) imax = atol(argv[1]);
  if (argc > 2) scale = atol(argv[2]);
  register im = -352321536; // -(2<<28)+(22<<23) == -1.3125
  while (im < 352321537) { // <= -1.3125
    register re = -536870912; // -(2<<28) == -2.0
    while (re < 268435456) { // (2<<28)-(64<<22) == 1.0
      register i = 0;
      register reZ = re;
      register imZ = im;
      while (i < imax && mul(reZ, reZ) + mul(imZ, imZ) < 1073741825) { // <= 4.0
        register reim = mul(reZ, imZ);
        reZ = mul(reZ, reZ) - mul(imZ, imZ) + re;
        imZ = reim + reim + im;
        i = i + 1;
      }
      if (i > 26 || !(i < imax)) putchar(32 + 10 * (i < imax));
      else putchar(65 + i);
      re = re + (8388608 >> scale); // (4<<28)/128 == 1.0/32
    }
    putchar(10);
    im = im + (16777216 >> scale); // (4<<28)/64 == 1.0/16
  }
  return 0;
}
EOF
) cmp - <(base64 -d <<EOF | gunzip
H4sICEz+AWkAA3hhAL2XS3qDIBRG56yCcXaRKI/LhfiITdrufyEF1DYoqOnX23+QZBDPAS4InM9p
LsVUzyn/bRG2y6+285rgJfQxDSvwN2B1jFBSCBF/bkpYDr8H93ghJYCScnLURQdb8ffpHu8FSqOD
wXJZ11v9YCn/AH3mK21ca7T67sSsqLKCbXy9xEvtEHvOWwM61EIUFeyHf7jx0g+P6XjMifex2pOj
WinYLj+hyxA/OhrvfApo5Ystl4pEUManTbcAD6M1GGPsdTS8OTSAwaEUgFx3YhJs4scR8C2Hj/tp
uNsrTzPwzkBnjUUIvUgNrMh/Ys8DD3ji+Zza8OFQrgxRkKWLp8SRB25dXxDEdKBSQTUKLit2LWRY
pbF0cq4rtFvwkB7CqqhTgxdkhtzP86v2lVPaxS8/bTS+7Ql413ItFgY2dWAx0/17oLn1FrEZsEEA
P3GaXb4PrrrAztViqk/vAXDvnD/Gx94dWneEb51cLLjKCzJ4pRs3JI823SGBzgie8FM5H2jQ3hbP
fh7gd2beIxLBOOhxvYd6AthDrV2n1yoj+B0rkxbHDejfe0BfA/JZRL4OyFcy+buI/m1Kvh/Q72jk
ezL9qYL8XER/sqM/m9KfrunvB/Q3HPo72j/cMleKA5oyOi/4+5v+F68nnKNLEAAA
EOF
)
testcase_run_chk "mandelbrot color" <(cat <<EOF
mul(a, b) { return a * b >> 28; } // 4.28 fix-point multiplication
main(argc, argv) {
  register colfmt = malloc(16);
  colfmt[0] = 2682796531491560219; // "\033[48;5;%"
  colfmt[1] = 2125156; // "dm \0"
  auto resetfmt = 1831885595; // "\033[0m"

  register imax = -32;
  register scale = 0;
  register color = 0;
  if (argc > 1) imax = atol(argv[1]);
  if (imax < 0) {
    imax = -imax;
    color = 1;
  }
  if (argc > 2) scale = atol(argv[2]);
  register im = -352321536; // -(2<<28)+(22<<23) == -1.3125
  while (im < 352321537) { // <= -1.3125
    register re = -536870912; // -(2<<28) == -2.0
    while (re < 268435456) { // (2<<28)-(64<<22) == 1.0
      register i = 0;
      register reZ = re;
      register imZ = im;
      while (i < imax && mul(reZ, reZ) + mul(imZ, imZ) < 1073741825) { // <= 4.0
        register reim = mul(reZ, imZ);
        reZ = mul(reZ, reZ) - mul(imZ, imZ) + re;
        imZ = reim + reim + im;
        i = i + 1;
      }
      if (!color) {
        if (i > 26 || !(i < imax)) putchar(32 + 10 * (i < imax));
        else putchar(65 + i);
      } else {
        register col = 0;
        if (i < imax) col = 16 + i - 216 * ((i >> 3) * 159072863 >> 32); // 16+i%216
        printf(colfmt, col);
      }
      re = re + (8388608 >> scale); // (4<<28)/128 == 1.0/32
    }
    if (!color) putchar(10);
    else puts(&resetfmt);
    im = im + (16777216 >> scale); // (4<<28)/64 == 1.0/16
  }
  return 0;
}
EOF
) cmp - <(base64 -d <<EOF | gunzip
H4sIAAAAAAAAA+2dQXLrIBBE9/8K2fwj2EZ27MpRcobcf5uFU8Wk0jYGDdBA77pUWLIQ/RgGhN4+
t+vH+eN4+fr/NpJ8l3wir1ySoUokC+Xh6193t69HBgbbTicZHuyckhcSNFUki68iGRoXoySDhIzP
Lm975ekQ5SnKIywAZel/EFBGg4QYwCN3Gz+NAyOPUG5QYoqkgOJwF6JIN0iIARMxII2DJCQMA0KU
scGc4l0YdIRzPBobAbyC7w0vGoo0YIQQMDoCqoEBM8IgIN5mOMICAZ6sQaRRCx2MFKkFCeFgdAY4
4MBIY2YTHFyQDLHsAagHtNjgtTISHWyjFRpwuCJCMBgSBg4ESI4foplDLIAI8KrazuBgKAsrquGj
QaMhp4OQQM4BB8cnOYCRALMLASUPfNSDKAL/z+TtjYYMGjgIA329X9rbxyeEJw+CCf3xQD/AM5xT
0lw43sUuTgSczbzAy2+wQA5AcAE8A5OTJiWPLlz5wODNcUmwP+xNd/KxEW/GafERbnCywBTARveO
AnxUgKMPUxsQILbAOyxrjl7QGbICDEY+5EBhPRJ0c3etYT/sPLd6MT6nsug7vvqbZFK1cLKEhgqF
KGDwaX2nt/C068gfRgLmXKZni9WQmA2Q+h0zJFdqkXHgNSQkOTCE+Qv7a7wkLycRlZOeKjxZTlav
oKuTSkIAh1QZsx0U2YQnPEhCgMvC1dLq5pHe4NFk4gnb8rr7ZMkkPs7nR9nfRrMoExNAyNpHkRMS
9KUBRsD+zp83pZ6x6jaYp2+6WFMWp47wGc6JAg+ST1jCrH3o75LVlH1oQ4YDGAAE/q6WSc+Ipu2o
+Xl23EzE7epkbujatpHBIX1/H6yhcO37rqBuxYCk8aezOHS77YCN29FUU7fIEwah/f/XGsp6PmMd
9ECe7+ZuzxxYwN0lDLrNIw0ob86kNiX0GlEWLySotbEDi+Udxs6Fizlzkl94EGxsrH5R6gWPJ9Ow
89i9f21LSVVxsTEpzpmWbakyjrfVlUstrlbqyjVY//mZButS95aw0mBdOfn7UeXkpX5axfQ5eU3A
/7G/JuCl5p+A19K7uw+NJbX0TgqxYM6ld1p+/+eolt9LrbT8Xq/hPcOFXsNbSuk1vOF44MkOvZMv
da8ivZOvbXqyJQUdtE3PY6VtevaiYGkqMGQ1CgGhbfwe9O7axq8BFJbmQyVU+M6WaO9f7f3bgg/6
cAA5QBymWPThgJclxVoBmg8HiBOjI8N33Ya+OdSUA1WRUIsO+mjhRMzwxYc+WjgADNoiYj8tBA5y
hlRbKK6PH3fDQTdIuPJCFGGkiAMvYLrCxhxwRsWkPuEViGlAgwAyRjTAhSBCA5GswQieECjbO4QC
BzQWHxgSDOgQRToAxfq6wS4iigOmgwQDLwSUVSVD42KUvJAYDR3CjCw+qRwNEtPxYhEOMVSJZDkk
vgEbnzSL3K4AAA==
EOF
)

exit $FAILED