#!/bin/bash : <<'````````bash' # Programming Exercise 5: Instruction Selection This is the continuation of hw3. You can continue from your own code or use the LLVM-IR generator from the website as starting point. ## Implementation Implement an instruction selector targeting x86-64 for the subset of LLVM-IR that you generate. Transform the LLVM-IR into a custom low-level IR, where the operations are machine instructions and an unlimited number of virtual registers and a PHI instruction are available. You can design the IR data structures to your preference; however, for testing, your program support emitting the fixed output format specified below. As a LLVM basic block forms a DAG, this task essentially requires some kind of DAG covering algorithm. Implement a "non-trivial" algorithm (i.e., anything that goes beyond trivial macro expansion) with a polynomial execution time and strive for "good" code within reasonable limits. Some examples: - Simple macro expansion with subsequent peephole optimization with data flow matching. (This is the minimum requirement.) - Tree pattern matching with aggressive splitting, greedy duplication, or some heuristic. Recommendations/comments: - Remain in SSA form. - Don't over-engineer your data structures. It is recommended to support inserting instructions at arbitrary points and modifying instruction operands for a later homework. - You can copy the `TARGET_OPS` macro from below into your code for information about supported instructions. - You can add further x86-64 instructions if you want/need them. However, please consult with the lecturer before submitting, so that this grading script also gets them. - Always generate flag-generating instructions together with flag-using instructions. - Be careful about folding memory operations into instructions: respect their ordering (correctness!) and avoid duplication. - You can use `llvm::match` (from ``) to match more complex LLVM-IR instruction patterns. ## Analysis (write answers as comment in your code) Provide some examples showcasing where your instruction selector generates "somewhat good" code (i.e., doesn't simply translate LLVM-IR instruction as-is, but performs some instruction folding). Also provide some examples where the code quality is exceptionally bad. ## Output Specification - The output is parsed line-wise. - A line ending with `:` marks the beginning of a new function with the given name. All other lines are instructions. - Functions are separated into basic blocks. The first basic block is started by the function beginning; all later basic blocks start after a terminator (`JMP`, `JCC`, `RET`). Basic blocks are numbered consecutively starting from 0. - Instructions and their operands are each separated by a single space. The first token is the instruction mnemonic; all other tokens are operands. - Instruction operands must be 64-bit signed integers, except for the second operand of `CALL`, which is the name of the called function. - The operand types of an instruction are implied by the mnemonic. See `TARGET_OPS` below for a full description of all currently implemented instructions. - Register operands denote a virtual register, which are numbered starting from zero. Virtual registers must be defined before they can be read (not verified right now). - For instructions that compute a value the first register operand is the destination. - Register constraints (tied-def, specific register numbers) are ignored (they are only relevant for register allocation). - x86-64 memory operands consist of four separate operands (base reg, scale 1/2/4/8, index reg, 32-bit displacement). The two registers are optional; specify `-1` to indicate absence. - Many instructions only support 32-bit immediates; these must be sign-extended to 64 bits. - The condition code of `JCC` and `SETCC` is an unsigned integer in the range of 0..15, which is interpreted as the lowest 4 bits of the instruction opcode (see ISA manual). - Basic block operands (`JMP`, `JCC`, `PseudoPhi`) are the block number. - `CALL` and `RET` are allowed to have fewer operands (e.g., fewer register parameters, undefined return value). - `JCC` takes three operands: condition code, then block, fall-through block. - Flags are implicit. - As there are no physical registers, instructions must be used to access stack pointer, frame pointer, and arguments passed in registers. - `PseudoFP` returns the value of the frame pointer `rbp` (see below). - `PseudoSP` returns the value of the stack pointer `rsp` (see below). - `PseudoRegArg ` returns the value value of the i-th register argument; i must be less than six. - `PseudoPhi` has the same semantics as a PHI instruction in SSA IRs, *except* that for every PHI node each pair of block and value must be printed as a separate instruction. (Recommendation: handle this as a special case when printing PHI instructions.) Stack frame layout: rsp rbp rbp+16 | | | V V V ------------------------------------------------------------------- | call args | ... | allocas, spills | rbp | ret | call args | ------------------------------------------------------------------- low addr high addr Output example: f(x, y) { auto a = 1; register b = 3; if (x > y) { x = y * y; a = &a; b = y; } else x = x * x; return b + x - a; } f: PseudoFP 4 PseudoRegArg 12 0 PseudoRegArg 8 1 MOV64mi 4 1 -1 -8 1 CMP64rr 12 8 JCC 15 1 2 IMUL64rr 7 8 8 LEA64rm 9 4 1 -1 -8 MOV64mr 4 1 -1 -8 9 JMP 3 IMUL64rr 10 12 12 MOV64ri 11 3 JMP 3 PseudoPhi 5 1 8 PseudoPhi 5 2 11 PseudoPhi 6 1 7 PseudoPhi 6 2 10 ADD64rr 2 5 6 MOV64rm 3 4 1 -1 -8 SUB64rr 1 2 3 RET 1 Here is another example that includes a function call: f(a,b,c,d,e,f,g,h) { return a+g+h; } g(a) { return a; } main() { return f(1,2,3,4,5,6,7,8) + g(1); } f: PseudoFP 1 PseudoRegArg 2 0 ADD64rm 3 2 1 0 0 16 ADD64rm 4 4 1 0 0 24 RET 4 g: PseudoRegArg 1 0 RET 1 main: PseudoSP 1 MOV64ri 12 6 MOV64ri 11 5 MOV64ri 10 4 MOV64ri 9 3 MOV64ri 8 2 MOV64ri 7 1 MOV64mi 1 0 0 8 8 MOV64mi 1 0 0 0 7 CALL 4 f 7 8 9 10 11 12 CALL 5 g 7 ADD64rr 3 4 5 RET 3 ## Command Line Interface usage: ./bc2 (-a|-c|-l|-i) 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 LLVM-IR. 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 `-L`, `-r`, and `-S`, which will be used in subsequent homework. ## Submission - Submission deadline: 2025-12-10 23:59 - Submit using `curl --data-binary "@" 'https://db.in.tum.de/teaching/ws2526/codegen/submit.py?hw=5&matrno='` ````````bash set -euo pipefail FAILED=0 testcase_ec() { if ./bc2 -i "$3" | ./cgmir; s="${PIPESTATUS[@]}"; [ "$s" != "0 $2" ]; \ then echo "FAILED: $1 (got [$s] expected [0 $2])"; FAILED=1; fi; } testcase_run_chk() { ./bc2 -i "$2" | ./cgmir | "${@: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 < #include #include #include #include #include #include #include #include #include #include #include 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(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 insts; std::vector blockStarts; void *native = nullptr; }; struct RunState { std::vector r; bool of = 0, sf = 0, zf = 0, af = 0, pf = 0, cf = 0; std::unordered_map funcDefs; std::vector> 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()); 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[0]]; return base + memOp[1] * index + memOp[3]; } template T load(const uint64_t *memOp) { T res; memcpy(&res, reinterpret_cast(addrgen(memOp)), sizeof(T)); if (verbose) std::cerr << "load " << addrgen(memOp) << "\n"; return res; } template void store(const uint64_t *memOp, T val) { if (verbose) std::cerr << "store " << addrgen(memOp) << " " << val << "\n"; memcpy(reinterpret_cast(addrgen(memOp)), &val, sizeof(T)); } template static void merge(uint64_t &rv, T val) { uint64_t mask = -T{1}; rv = (rv & ~mask) | (val & mask); } }; using RegArgs = std::array; 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 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> 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 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(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(&o[1]); break; case MOV64ri: r[o[0]] = o[1]; break; case MOV64mr: r.store(&o[0], r[o[4]]); break; case MOV64mi: r.store(&o[0], o[4]); break; case MOV32rr: r[o[0]] = uint32_t(r[o[1]]); break; case MOV32rm: r[o[0]] = r.load(&o[1]); break; case MOV32ri: r[o[0]] = uint32_t(o[1]); break; case MOV32mr: r.store(&o[0], r[o[4]]); break; case MOV32mi: r.store(&o[0], o[4]); break; case MOV16mr: r.store(&o[0], r[o[4]]); break; case MOV16mi: r.store(&o[0], o[4]); break; case MOV8mr: r.store(&o[0], r[o[4]]); break; case MOV8mi: r.store(&o[0], o[4]); break; case MOVZXB32rr: r[o[0]] = uint8_t(r[o[1]]); break; case MOVZXB32rm: r[o[0]] = r.load(&o[1]); break; case MOVZXW32rr: r[o[0]] = uint16_t(r[o[1]]); break; case MOVZXW32rm: r[o[0]] = r.load(&o[1]); break; case MOVSXB64rr: r[o[0]] = int8_t(r[o[1]]); break; case MOVSXB64rm: r[o[0]] = r.load(&o[1]); break; case MOVSXW64rr: r[o[0]] = int16_t(r[o[1]]); break; case MOVSXW64rm: r[o[0]] = r.load(&o[1]); break; case MOVSXD64rr: r[o[0]] = int32_t(r[o[1]]); break; case MOVSXD64rm: r[o[0]] = r.load(&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(&o[2]); r.flags_add(r[o[1]], t); r[o[0]] = r[o[1]] + t; break; case ADD64mr: t = r.load(&o[0]); r.flags_add(t, r[o[4]]); t += r[o[4]]; r.store(&o[0], t); break; case ADD64mi: t = r.load(&o[0]); r.flags_add(t, o[4]); t += o[4]; r.store(&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(&o[2]); r.flags_sub(r[o[1]], t); r[o[0]] = r[o[1]] - t; break; case SUB64mr: t = r.load(&o[0]); r.flags_sub(t, r[o[4]]); t -= r[o[4]]; r.store(&o[0], t); break; case SUB64mi: t = r.load(&o[0]); r.flags_sub(t, o[4]); t -= o[4]; r.store(&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(&o[2]); r.flags_logical(r[o[1]] ^ t); r[o[0]] = r[o[1]] ^ t; break; case XOR64mr: t = r.load(&o[0]); r.flags_logical(t ^ r[o[4]]); t ^= r[o[4]]; r.store(&o[0], t); break; case XOR64mi: t = r.load(&o[0]); r.flags_logical(t ^ o[4]); t ^= o[4]; r.store(&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(&o[2]); r.flags_logical(r[o[1]] & t); r[o[0]] = r[o[1]] & t; break; case AND64mr: t = r.load(&o[0]); r.flags_logical(t & r[o[4]]); t &= r[o[4]]; r.store(&o[0], t); break; case AND64mi: t = r.load(&o[0]); r.flags_logical(t & o[4]); t &= o[4]; r.store(&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(&o[2]); r.flags_logical(r[o[1]] | t); r[o[0]] = r[o[1]] | t; break; case OR64mr: t = r.load(&o[0]); r.flags_logical(t | r[o[4]]); t |= r[o[4]]; r.store(&o[0], t); break; case OR64mi: t = r.load(&o[0]); r.flags_logical(t | o[4]); t |= o[4]; r.store(&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(&o[1]); r.flags_sub(r[o[0]], t); break; case CMP64mr: t = r.load(&o[0]); r.flags_sub(t, r[o[4]]); t -= r[o[4]]; break; case CMP64mi: t = r.load(&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(&o[1]); r.flags_logical(r[o[0]] & t); break; case TEST64mr: t = r.load(&o[0]); r.flags_logical(t & r[o[4]]); t -= r[o[4]]; break; case TEST64mi: t = r.load(&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(&o[2]); r.flags_mul(r[o[1]], t); r[o[0]] = r[o[1]] * t; break; case IMUL64rmi: t = r.load(&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; while ((c = getopt(argc, argv, "vp")) != -1) { switch (c) { case 'v': verbose = 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 opcMap = {TARGET_OPS}; #undef TARGET_OP RunState r; std::string line; Func *fn = nullptr; 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); continue; } assert(fn); size_t split = line.find(' '); Inst inst{}; if (auto it = opcMap.find(line.substr(0, split)); it == opcMap.end()) { std::cerr << "invalid opcode " << line << "\n"; return 1; } else { inst.opc = it->second; } 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; } uint64_t op = inst.ops[nops++] = std::stoll(opStr); // errors... whatever switch (opType & 0xf) { case 1: if (!virtualRegs && op >= 16) abort(); assert(op < 0x10000 && "so many virtual regs?"); break; case 2: if (!virtualRegs && op != (opType >> 4)) abort(); break; case 3: // TODO: tied-def/opt reg break; case 4: if (int64_t(op) != int32_t(op)) abort(); break; case 5: break; case 6: if (op != 1 && op != 2 && op != 4 && op != 8) abort(); break; case 7: break; case 8: break; default: assert(0); } } fn->insts.push_back(inst); if (oi.ret == 0x04) fn->blockStarts.push_back(fn->insts.size()); } 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; } } } auto mainIt = r.funcDefs.find("main"); if (mainIt == r.funcDefs.end()) { std::cerr << "no main function\n"; return 1; } std::unique_ptr 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(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 bc2 cgmir 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;}") # 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 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 "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 <> 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 <> 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 <