#!/bin/bash : <<'````````bash' # Programming Exercise 5: Instruction Selection **Important (2025-11-27):** Consider the announcement in the lecture before starting the homework. 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 LLVM-IR code that essentially just calls functions which represent machine instructions. Example: f(x, y) { auto a = 1; if (x > y) { x = y * y; a = &a; } else x = x * x; return x - a; } define i64 @f(i64 %0, i64 %1) { %fp = call i64 (i64, i64, ...) @FRAME_SETUP(i64 8, i64 0) call void @MOV64mi(i64 %fp, i64 1, i64 0, i64 -8, i64 1) call void @CMP64rr(i64 %0, i64 %1) %3 = call i1 @Jcc(i64 15) br i1 %3, label %4, label %7 4: ; preds = %2 %5 = call i64 @IMUL64rr(i64 %1, i64 %1) %6 = call i64 @LEA64rm(i64 %fp, i64 1, i64 0, i64 -8) call void @MOV64mr(i64 %fp, i64 1, i64 0, i64 -8, i64 %6) br label %9 7: ; preds = %2 %8 = call i64 @IMUL64rr(i64 %0, i64 %0) br label %9 9: ; preds = %7, %4 %10 = phi i64 [ %8, %7 ], [ %5, %4 ] %11 = call i64 @MOV64rm(i64 %fp, i64 1, i64 0, i64 -8) %12 = call i64 @SUB64rr(i64 %10, i64 %11) call void @FRAME_DESTROY(i64 %fp) ret i64 %12 } Here is another example that includes a function call: f(a,b,c,d,e,f,g,h) { return g+h; } main() { return f(1,2,3,4,5,6,7,8) + 1; } define i64 @f(i64 %0, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5, i64 %6, i64 %7) { %fp = call i64 (i64, i64, ...) @FRAME_SETUP(i64 0, i64 2, i64 %6, i64 %7) %9 = call i64 @MOV64rm(i64 %fp, i64 1, i64 0, i64 16) %10 = call i64 @MOV64rm(i64 %fp, i64 1, i64 0, i64 24) %11 = call i64 @ADD64rr(i64 %9, i64 %10) call void @FRAME_DESTROY(i64 %fp) ret i64 %11 } define i64 @main() { %fp = call i64 (i64, i64, ...) @FRAME_SETUP(i64 0, i64 0) %1 = call i64 @ADJCALLSTACKDOWN(i64 16) %2 = call i64 @MOV64ri(i64 1) %3 = call i64 @MOV64ri(i64 2) %4 = call i64 @MOV64ri(i64 3) %5 = call i64 @MOV64ri(i64 4) %6 = call i64 @MOV64ri(i64 5) %7 = call i64 @MOV64ri(i64 6) call void @MOV64mi(i64 %1, i64 1, i64 0, i64 0, i64 7) call void @MOV64mi(i64 %1, i64 1, i64 0, i64 8, i64 8) %8 = call i64 (ptr, i64, ...) @CALL(ptr @f, i64 %1, i64 %2, i64 %3, i64 %4, i64 %5, i64 %6, i64 %7) call void @ADJCALLSTACKUP(i64 %1, i64 16) %9 = call i64 @ADD64ri(i64 %8, i64 1) call void @FRAME_DESTROY(i64 %fp) ret i64 %9 } An LLVM basic block forms a DAG, so 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: - Generate instructions into a separate function. - Always generate flag-generating instructions together with flag-using instructions. - Use the combined size of all allocas as stack frame size. (Later, register allocation will need more, but this is easily adjustable.) - All instructions should have a type of `void` or `i64` (except `Jcc`, which has `i1`). - 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. - You can add further x86-64 instructions (add them to `bc2-rt.c` below). **Important:** If you do this, please consult with the lecturer before submitting, so that the grading script also gets these. ## 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 After the transformation, the rewritten function shall only consist of the following: - Arguments. The first six arguments can be treated as "register operands". - Calls to functions that represent a single machine code instruction. The result of the call is the result computed by the instruction, parameters are the input operands. Immediate operands shall be suitable constants in the LLVM-IR, register operands shall be "register operands". The result of a machine instruction call is treated as "register operand". Examples: - `i64 ADD64rr(i64 %r1, i64 %r2)`: add the two "register" operands; updates flags. - `void CMP64rr(i64 %r1, i64 %r2)`: subtract the two "register" operands; updates flags. `void`, as no register is modified. - `i64 IMUL64rri(i64 %r1, i64 %imm32)`: multiply first register operand with second immediate operand, shall be a constant that fits into 32 bits (sign-extended to 64 bits); updates flags. - `i64 MOV64rm(i64 %base, i64 %scale, i64 %index, i64 %disp32)`: load 64-bit from memory from address `base + scale*index + disp32`. `base` and `index` shall be register operands, `scale` shall be 1/2/4/8, `disp32` shall be a 32-bit immediate sign-extended to 64 bits. - `i64 MOV64ri(i64 %imm64)`: load 64-bit immediate into register. This is the only instruction that can handle 64-bit immediates. - `void MOV64mr(i64 %base, i64 %scale, i64 %index, i64 %disp32, i64 %r1)`: store 64-bit into memory, `r1` shall be a register. - `i64 SHL64rr(i64 %r1, i64 %r2)`: shift first register operand left by second register operand; might update flags. - `phi` instructions, which merge "register operands". `phi`s are treated as "register operands". - A single call to `i64 FRAME_SETUP(stackFrameSize, numStackArgs, stackArg0, stackArg1, ...)` at the beginning of the entry block. - This is a vararg function. - All function arguments that are passed on the stack (i.e., the 7th and all following arguments) shall be passed as arguments to this call. (This is a limitation from using LLVM-IR for this task.) - The result of this function acts as frame pointer and is usable as "register operand". - Arguments passed on the stack can be referred to by `fp+16`, `fp+24`, ... (up to `fp+16+8*numStackArgs`) - Stack slots (to replace `alloca`) by `fp-8`, `fp-16`, ... (up to `fp-stackFrameSize`). - `ret` instructions. The operand shall be a "register operand". Every `ret` instruction shall be immediately preceded by a call to `void FRAME_DESTROY(i64 %fp)` - `br` instructions. Conditional branches shall be immediately preceded by a call to `i1 Jcc(i64 %condcode)`, with `condcode` being an immediate indicating the jump condition. The result of such a call shall be the condition of the immediately succeeding conditional branch. - Regular function calls are transformed as follows: - Before the call, "i64 ADJSTACKDOWN(i64 %stackArgSize)" is called. This will allocate the specified number of bytes for arguments passed on the stack (i.e., arguments 7+). It returns the stack pointer, so the first stack argument has to be stored at `sp`, the second at `sp+8`, ... (up to `sp+stackArgSize`). - Then, stack arguments have to be stored. - The function call itself is done with `i64 CALL(ptr @theFunction, i64 %sp, args...)`. This is a vararg function. Only the 6 arguments that are passed in registers are arguments here, and all of them must be "register operands". - Immediately afterwards, `void ADJSTACKUP(i64 %sp, i64 %stackArgSize)` must be called to release the memory for the stack arguments. - No other LLVM-IR instructions are permitted. ## 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 `-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" | ./bc2-verify | env LD_PRELOAD=./bc2-rt.so lli; s="${PIPESTATUS[@]}"; [ "$s" != "0 0 $2" ]; \ then echo "FAILED: $1 (got [$s] expected [0 0 $2])"; FAILED=1; fi; } testcase_run_chk() { ./bc2 -i "$2" | ./bc2-verify | env LD_PRELOAD=./bc2-rt.so lli | "${@:3}" || { echo "FAILED: $1"; FAILED=1; }; } extract() { TMP=$(mktemp); cat > "$TMP"; cmp -s "$1" "$TMP" && rm "$TMP" || mv "$TMP" "$1"; } # Extract verification program extract bc2-verify.cc < #include #include #include #include #include #include static void abortWith(llvm::Value *V, llvm::StringRef Msg) { llvm::errs() << "ERROR: " << Msg << "\n" << *V << "\n"; exit(1); } static bool isRegOp(llvm::Value *V) { if (!V->getType()->isIntegerTy(64)) return false; if (auto *Arg = llvm::dyn_cast(V)) return Arg->getArgNo() < 6; if (!llvm::isa(V)) return false; return true; } static void validateFrameSetup(llvm::Value *I) { llvm::CallInst *CI = llvm::dyn_cast(I); if (!CI) abortWith(I, "expected FRAME_SETUP call"); if (auto *F = CI->getCalledFunction(); !F || F->getName() != "FRAME_SETUP") abortWith(I, "expected FRAME_SETUP call"); unsigned ArgCount = CI->arg_size(); if (ArgCount < 2 || !llvm::isa(CI->getArgOperand(0)) || !llvm::isa(CI->getArgOperand(1))) abortWith(I, "FRAME_SETUP call must have two constants as first arguments"); auto NA = llvm::cast(CI->getArgOperand(1))->getZExtValue(); if (NA + 2 != ArgCount) abortWith(I, "FRAME_SETUP arg count mismatch"); for (unsigned i = 0; i < NA; i++) { auto *Arg = llvm::dyn_cast(CI->getArgOperand(i + 2)); if (!Arg || Arg->getArgNo() != i + 6) abortWith(I, "FRAME_SETUP argument mismatch"); if (!Arg->hasOneUse()) abortWith(Arg, "stack argument must only have FRAME_SETUP use"); } } static void validateFrameDestroy(llvm::Instruction *I) { llvm::CallInst *CI = llvm::dyn_cast(I); if (!CI) abortWith(I, "expected FRAME_DESTROY call"); if (auto *F = CI->getCalledFunction(); !F || F->getName() != "FRAME_DESTROY") abortWith(I, "expected FRAME_DESTROY call"); if (CI->arg_size() != 1) abortWith(I, "FRAME_DESTROY must have a single argument"); validateFrameSetup(CI->getArgOperand(0)); if (!llvm::isa(CI->getNextNode())) abortWith(I, "FRAME_DESTROY must be followed by return"); } int main() { llvm::LLVMContext Ctx; llvm::SMDiagnostic Diag{}; auto M = llvm::parseIRFile("-", Diag, Ctx); if (!M) { Diag.print("bc2-verify", llvm::errs()); return 1; } for (auto &F : *M) { if (F.empty()) continue; validateFrameSetup(&*F.getEntryBlock().begin()); for (auto &BB : F) { for (auto &I : BB) { if (auto *Phi = llvm::dyn_cast(&I)) { if (!Phi->getType()->isIntegerTy(64)) abortWith(Phi, "phi must be i64"); for (auto &V : Phi->incoming_values()) if (!isRegOp(V.get())) abortWith(Phi, "phi operands must be registers"); } else if (auto *Ret = llvm::dyn_cast(&I)) { if (!Ret->getReturnValue() || !isRegOp(Ret->getReturnValue())) abortWith(Phi, "ret operand must be register"); validateFrameDestroy(I.getPrevNode()); } else if (auto *Br = llvm::dyn_cast(&I)) { if (Br->isUnconditional()) continue; auto *Cond = Br->getCondition(); llvm::CallInst *CI = llvm::dyn_cast(Cond); if (!CI) abortWith(Br, "expected Jcc as condition"); if (auto *F = CI->getCalledFunction(); !F || F->getName() != "Jcc") abortWith(Br, "expected Jcc as condition"); } else if (auto *CI = llvm::dyn_cast(&I)) { auto *F = CI->getCalledFunction(); if (!F) abortWith(CI, "expected direct function call"); // first nibble is return type, others are argument types // 0=void, 1=i1, 2=i64-reg, 3=scale, 4=idx, 5=i64-imm32, 6=i64-imm64 unsigned Signature = llvm::StringSwitch(F->getName()) .Case("FRAME_SETUP", 0x662) .Case("FRAME_DESTROY", 0x20) .Case("MOV64rm", 0x54322) .Default(-1u); // user-functions :( if (F->getName().front() >= 'a') { if (!CI->getType()->isIntegerTy(64)) abortWith(CI, "function call must return i64"); for (auto &Arg : CI->args()) if (!isRegOp(Arg)) abortWith(CI, "arguments must be registers"); } else { // XXX verify signature (void)Signature; } } else { abortWith(&I, "unexpected instruction"); } } } } M->print(llvm::outs(), nullptr); return 0; } EOF # Extract runtime extract bc2-rt.c < #include #include static struct { _Bool of, sf, zf, af, pf, cf; } eflags; static void eflags_set_logical(uint64_t a) { eflags.zf = !a; eflags.sf = (int64_t)a < 0; eflags.cf = eflags.of = 0; eflags.af = eflags.pf = 0; // FIXME } static void eflags_set_add(uint64_t a, uint64_t b) { eflags.zf = a == b; eflags.sf = (int64_t)(a + b) < 0; eflags.cf = a + b < a; int64_t tmp; eflags.of = __builtin_add_overflow((int64_t)a, (int64_t)b, &tmp); eflags.af = eflags.pf = 0; // FIXME } static void eflags_set_sub(uint64_t a, uint64_t b) { eflags.zf = a == b; eflags.sf = (int64_t)(a - b) < 0; eflags.cf = a < b; int64_t tmp; eflags.of = __builtin_sub_overflow((int64_t)a, (int64_t)b, &tmp); eflags.af = eflags.pf = 0; // FIXME } static void eflags_set_mul(uint64_t a, uint64_t b) { eflags.zf = !a|!b; eflags.sf = (int64_t)(a * b) < 0; int64_t tmp; eflags.cf = eflags.of = __builtin_mul_overflow((int64_t)a, (int64_t)b, &tmp); eflags.af = eflags.pf = 0; // FIXME } static void chki32(uint64_t a) { if ((int32_t)a != (int64_t)a) abort(); } static void *mem(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { if (!(b == 1 || b == 2 || b == 4 || b == 8) || (int32_t)d != (int64_t)d) abort(); return (void*)(a + b*c + d); } // "frame": (stack frame ..., ptr to self (for free), (unused), copy of args...) uint64_t FRAME_SETUP(uint64_t sz, uint64_t narg, ...) { sz = (sz + 7) / 8; uint64_t *fp = malloc((sz + 2 + narg) * sizeof(uint64_t)); fp[sz] = (uint64_t)fp; va_list ap; va_start(ap, narg); for (uint64_t i = 0; i < narg; i++) fp[sz + 2 + i] = va_arg(ap, uint64_t); va_end(ap); return (uint64_t)(fp + sz); } void FRAME_DESTROY(uint64_t fp) { free(*(void **)fp); } uint64_t ADJCALLSTACKDOWN(uint64_t size) { uint64_t *p = malloc(size + 16); // extra space for simple copying in CALL *p = size; return (uint64_t)(p + 1); } void ADJCALLSTACKUP(uint64_t pi, uint64_t size) { uint64_t *p = (uint64_t *)pi - 1; if (*p != size) abort(); free(p); } #if defined(__x86_64__) __asm__( ".intel_syntax noprefix; .global CALL; CALL:" "push rbp; mov rbp, rsp; mov r11, [rsi - 8]; add r11, 15; and r11, -16;" "sub rsp, r11; jmp 2f; 1: movups xmm0, [rsi + r11]; movaps [rsp + r11], xmm0;" "2: sub r11, 16; jns 1b;" "mov r11, rdi; mov rdi, rdx; mov rsi, rcx; mov rdx, r8; mov rcx, r9;" "mov r8, [rbp + 16]; mov r9, [rbp + 24]; call r11; leave; ret;" ".att_syntax prefix;" ); #elif defined(__aarch64__) __asm__( ".global CALL;CALL:" "stp x29, x30, [sp, #-16]!; mov x29, sp;" "ldr x8, [x1, #-8]; add x8, x8, #16; and x8, x8, #-16; sub sp, sp, x8;" // register argument, x16 = function, x17 = stack args (6+); x8 = stack size "mov x16, x0; mov x17, x1; mov x0, x2; mov x1, x3; mov x2, x4; mov x3, x5;" "mov x4, x6; mov x5, x7; ldp x6, x7, [x17], #16; sub x8, x8, #16;" // copy stack arguments in place "mov x9, #0; b 2f; 1: ldr x10, [x17, x9]; str x10, [sp, x9];" "add x9, x9, #8; 2: cmp x9, x8; b.lo 1b;" "blr x16; mov sp, x29; ldp x29, x30, [sp], #16; ret" ); #else #error "unsupported architecture" #endif uint64_t MOV64rr(uint64_t a) { return a; } uint64_t MOV64ri(uint64_t i) { return i; } uint64_t MOV32rr(uint64_t a) { return (uint32_t)a; } uint64_t MOV32ri(uint64_t i) { return (uint32_t)i; } void MOV64mr(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint64_t*)mem(a, b, c, d) = e; } void MOV64mi(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { chki32(e); *(uint64_t*)mem(a, b, c, d) = e; } void MOV32mr(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint32_t*)mem(a, b, c, d) = e; } void MOV32mi(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint32_t*)mem(a, b, c, d) = e; } void MOV16mr(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint16_t*)mem(a, b, c, d) = e; } void MOV16mi(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint16_t*)mem(a, b, c, d) = e; } void MOV8mr(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint8_t*)mem(a, b, c, d) = e; } void MOV8mi(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint8_t*)mem(a, b, c, d) = e; } uint64_t MOV64rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return *(uint64_t*)mem(a, b, c, d); } uint64_t MOV32rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return *(uint32_t*)mem(a, b, c, d); } uint64_t MOVZXB32rr(uint64_t a) { return (uint8_t)a; } uint64_t MOVZXB32rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return *(uint8_t*)mem(a, b, c, d); } uint64_t MOVZXW32rr(uint64_t a) { return (uint16_t)a; } uint64_t MOVZXW32rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return *(uint16_t*)mem(a, b, c, d); } uint64_t MOVSXB32rr(uint64_t a) { return (uint32_t)(int8_t)a; } uint64_t MOVSXB32rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return (uint32_t)*(int8_t*)mem(a, b, c, d); } uint64_t MOVSXB64rr(uint64_t a) { return (int8_t)a; } uint64_t MOVSXB64rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return *(int8_t*)mem(a, b, c, d); } uint64_t MOVSXW32rr(uint64_t a) { return (uint32_t)(int16_t)a; } uint64_t MOVSXW32rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return (uint32_t)*(int16_t*)mem(a, b, c, d); } uint64_t MOVSXW64rr(uint64_t a) { return (int16_t)a; } uint64_t MOVSXW64rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return *(int16_t*)mem(a, b, c, d); } uint64_t MOVSXD64rr(uint64_t a) { return (int32_t)a; } uint64_t MOVSXD64rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return *(int32_t*)mem(a, b, c, d); } uint64_t LEA64rm(uint64_t a, uint64_t b, uint64_t c, uint64_t d) { return (uint64_t)mem(a, b, c, d); } void CMP64rr(uint64_t a, uint64_t b) { eflags_set_sub(a, b); } void CMP64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_sub(a, b); } uint64_t SUB64rr(uint64_t a, uint64_t b) { eflags_set_sub(a, b); return a - b; } uint64_t SUB64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_sub(a, b); return a - b; } uint64_t ADD64rr(uint64_t a, uint64_t b) { eflags_set_add(a, b); return a + b; } uint64_t ADD64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_add(a, b); return a + b; } uint64_t IMUL64rr(uint64_t a, uint64_t b) { eflags_set_mul(a, b); return a * b; } uint64_t IMUL64rri(uint64_t a, uint64_t b) { chki32(b); eflags_set_mul(a, b); return a * b; } uint64_t AND64rr(uint64_t a, uint64_t b) { eflags_set_logical(a & b); return a & b; } uint64_t AND64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_logical(a & b); return a & b; } void TEST64rr(uint64_t a, uint64_t b) { eflags_set_logical(a & b); } void TEST64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_logical(a & b); } uint64_t OR64rr(uint64_t a, uint64_t b) { eflags_set_logical(a | b); return a | b; } uint64_t OR64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_logical(a | b); return a | b; } uint64_t XOR64rr(uint64_t a, uint64_t b) { eflags_set_logical(a ^ b); return a ^ b; } uint64_t XOR64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_logical(a ^ b); return a ^ b; } // FIXME: shift flags uint64_t SHL64rr(uint64_t a, uint64_t b) { return a << b; } uint64_t SHL64ri(uint64_t a, uint64_t b) { return a << (b & 63); } uint64_t SHR64rr(uint64_t a, uint64_t b) { return a >> b; } uint64_t SHR64ri(uint64_t a, uint64_t b) { return a >> (b & 63); } uint64_t SAR64rr(uint64_t a, uint64_t b) { return (int64_t)a >> b; } uint64_t SAR64ri(uint64_t a, uint64_t b) { return (int64_t)a >> (b & 63); } _Bool Jcc(unsigned cond) { switch (cond) { case 0: return eflags.of; case 1: return !eflags.of; case 2: return eflags.cf; case 3: return !eflags.cf; case 4: return eflags.zf; case 5: return !eflags.zf; case 6: return eflags.cf || eflags.zf; case 7: return !(eflags.cf || eflags.zf); case 8: return eflags.sf; case 9: return !eflags.sf; case 10: return eflags.pf; case 11: return !eflags.pf; case 12: return eflags.sf != eflags.of; case 13: return !(eflags.sf != eflags.of); case 14: return eflags.sf != eflags.of || eflags.zf; case 15: return !(eflags.sf != eflags.of || eflags.zf); } return 0; } uint64_t SETcc8r(unsigned cond) { return Jcc(cond) | 0xa5a5a5a5a5a5a500; } EOF gcc -shared -o bc2-rt.so bc2-rt.c -O2 CXX=clang++ CXXFLAGS="-O3 -Wall -Wextra -std=c++20 $(llvm-config --cppflags --ldflags | tr '\n' ' ')" \ LDLIBS="$(llvm-config --libs)" make bc2 bc2-verify 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 <