#!/bin/bash : <<'````````bash' # Programming Exercise 5: Register Allocation This is the continuation of hw4. You can continue from your own code or use the parser from the website as starting point. ## Implementation Implement a register allocator by rewriting the instruction-selected LLVM-IR with operations that refer to actual register numbers. After register allocation, (almost) no SSA-definitions and no PHI nodes remain. There are no quality requirements for the generated code, except for correctness. 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) { call void (i64, i64, ...) @R_FRAME_SETUP(i64 16, i64 2, i64 %0, i64 %1) call void @R_MOV64mi(i64 5, i64 1, i64 16, i64 -8, i64 1) call void @R_CMP64rr(i64 7, i64 6) %3 = call i1 @Jcc(i64 15) br i1 %3, label %4, label %5 4: ; preds = %2 call void @R_MOV64rr(i64 0, i64 6) call void @R_IMUL64rr(i64 0, i64 6) call void @R_LEA64rm(i64 1, i64 5, i64 1, i64 16, i64 -8) call void @R_MOV64mr(i64 5, i64 1, i64 16, i64 -8, i64 1) call void @R_MOV64mr(i64 5, i64 1, i64 16, i64 -16, i64 0) br label %6 5: ; preds = %2 call void @R_MOV64rr(i64 0, i64 7) call void @R_IMUL64rr(i64 0, i64 7) call void @R_MOV64mr(i64 5, i64 1, i64 16, i64 -16, i64 0) br label %6 6: ; preds = %5, %4 call void @R_MOV64rm(i64 1, i64 5, i64 1, i64 16, i64 -8) call void @R_MOV64rm(i64 2, i64 5, i64 1, i64 16, i64 -16) call void @R_MOV64rr(i64 3, i64 2) call void @R_SUB64rr(i64 3, i64 1) call void @R_MOV64rr(i64 0, i64 3) %7 = call i64 @R_FRAME_DESTROY() ret i64 %7 } Comments: - You might find `llvm::SplitAllCriticalEdges` useful. - You can either modify the IR in-place (like the reference solution) or generate the code into a new function. Almost no instructions will remain. - Track the register assignment for the beginning and end of a basic block. - When inserting spill code, it is easiest to insert it directly after an instruction. - You will need extra spill slots, adjust the stackFrameSize of `FRAME_SETUP` accordingly. ## Output Specification After the transformation, the rewritten function shall only consist of the following: - Arguments. (Arguments are passed in registers 7, 6, 2, 1, 8, 9; return value goes to register 0.) - Calls to functions that represent a single machine code instruction, generally prefixed with `R_`. These calls have a void return type. The operands are either registers (constants 0--15, omitted for memory operands is 16) or immediates. Examples: - `void R_ADD64rr(i64 %r1, i64 %r2)`: `gpregs[r1] += gpregs[r2]`; updates flags. - A single call to `void R_FRAME_SETUP(stackFrameSize, numStackArgs, arg0, arg1, ...)` at the beginning of the entry block. - This is a vararg function. - All function arguments (including register arguments) shall be passed as arguments to this call. (This is a limitation from using LLVM-IR for this task.) - The function sets up the frame pointer (register 5). - 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 the result of `R_FRAME_DESTROY()`, which shall immediately preceed the `ret`. - `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, "void R_ADJSTACKDOWN(i64 %stackArgSize)" is called. This will allocate the specified number of bytes for arguments passed on the stack (i.e., arguments 7+ times 8 bytes). It adjusts the stack pointer (register 4), 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, arguments have to be moved in the parameter registers. - The function call itself is done with `void R_CALL(ptr @theFunction)`. - Immediately afterwards, `void R_ADJSTACKUP(i64 %stackArgSize)` must be called with the same size to release the memory for the stack arguments. - No other LLVM-IR instructions and no PHI nodes are permitted. ## Command Line Interface usage: ./bc3 (-a|-c|-l|-i|-r) 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. -r: emit register-allocated 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 `-S`, which will be used in subsequent homework. ## Submission - Submission deadline: 2025-01-08 23:59 - Submit using `curl --data-binary "@" 'https://db.in.tum.de/teaching/ws2425/codegen/submit.py?hw=5&matrno='` - Write your solution in a single C++ file. (Default file name: `bc3.cc`) - Include answers to theory questions as comments at the top of the source file. - Make sure your submission passes as many tests as possible from this test script. - Avoid dependencies, no build systems other than Makefile, etc. - If you need more than just the C++ file, combine all files s.t. this command sequence works: `split-file somedir; cd somedir; bash ` - If you write your own Makefile: - Use `$(LLVM_CONFIG) --cppflags --ldflags --libs` to find LLVM; note that libs must come after your object files when linking. - Default-initialize `LLVM_CONFIG := llvm-config`, so that `make LLVM_CONFIG=/path/to/llvm-config` overrides it. ````````bash set -euo pipefail FAILED=0 testcase_ec() { if ./bc3 -r "$3" | ./bc3-verify | env LD_PRELOAD=./bc3-rt.so lli; s="${PIPESTATUS[@]}"; [ "$s" != "0 0 $2" ]; \ then echo "FAILED: $1 (got [$s] expected [0 0 $2])"; FAILED=1; fi; } extract() { TMP=$(mktemp); cat > "$TMP"; cmp -s "$1" "$TMP" && rm "$TMP" || mv "$TMP" "$1"; } # Extract verification program extract bc3-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 R_FRAME_SETUP call"); if (auto *F = CI->getCalledFunction(); !F || F->getName() != "R_FRAME_SETUP") abortWith(I, "expected R_FRAME_SETUP call"); unsigned ArgCount = CI->arg_size(); if (ArgCount < 2 || !llvm::isa(CI->getArgOperand(0)) || !llvm::isa(CI->getArgOperand(1))) abortWith(I, "R_FRAME_SETUP call must have two constants as first arguments"); auto NA = llvm::cast(CI->getArgOperand(1))->getZExtValue(); if (NA + 2 != ArgCount) abortWith(I, "R_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) abortWith(I, "R_FRAME_SETUP argument mismatch"); if (!Arg->hasOneUse()) abortWith(Arg, "argument must only have R_FRAME_SETUP use"); } } static void validateFrameDestroy(llvm::Instruction *I) { llvm::CallInst *CI = llvm::dyn_cast(I); if (!CI) abortWith(I, "expected R_FRAME_DESTROY call"); if (auto *F = CI->getCalledFunction(); !F || F->getName() != "R_FRAME_DESTROY") abortWith(I, "expected R_FRAME_DESTROY call"); if (CI->arg_size() != 0) abortWith(I, "R_FRAME_DESTROY must have no arguments"); if (!CI->getType()->isIntegerTy(64)) abortWith(I, "R_FRAME_DESTROY must return i64"); } int main() { llvm::LLVMContext Ctx; llvm::SMDiagnostic Diag{}; auto M = llvm::parseIRFile("-", Diag, Ctx); if (!M) { Diag.print("bc3-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 *Ret = llvm::dyn_cast(&I)) { if (Ret->getReturnValue() != I.getPrevNode()) abortWith(Ret, "ret operand must be preceding R_FRAME_DESTROY"); 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 || CI != Br->getPrevNode()) abortWith(Br, "expected immediately preceding 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"); if (F->getName() == "R_FRAME_DESTROY") { if (!llvm::isa(CI->getNextNode())) abortWith(CI, "R_FRAME_DESTROY must be followed by return"); continue; // verified by return } if (F->getName() == "Jcc") continue; // TODO: verify jump condition? if (!CI->getType()->isVoidTy()) abortWith(CI, "all function except for Jcc/R_FRAME_DESTROY must be void!"); // TODO: verify signature } else { abortWith(&I, "unexpected instruction"); } } } } M->print(llvm::outs(), nullptr); return 0; } EOF # Extract runtime extract bc3-rt.c < #include #include #include static struct { _Bool of, sf, zf, af, pf, cf; } eflags; static uint64_t gpregs[16]; static uint64_t* gp(uint64_t n) { if (n >= 16) abort(); return &gpregs[n]; } 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 < 16 ? *gp(a) : 0) + b*(c < 16 ? *gp(c) : 0) + d); } // "frame": (stack frame ..., ptr to self (for free), (unused), copy of args...) void R_FRAME_SETUP(uint64_t sz, uint64_t narg, ...) { sz = (sz + 7) / 8 + 0x1000; uint64_t *fp = malloc((sz + 2 + narg) * sizeof(uint64_t)); fp[sz] = (uint64_t)fp; va_list ap; va_start(ap, narg); *gp(7) = va_arg(ap, uint64_t); *gp(6) = va_arg(ap, uint64_t); *gp(2) = va_arg(ap, uint64_t); *gp(1) = va_arg(ap, uint64_t); *gp(8) = va_arg(ap, uint64_t); *gp(9) = va_arg(ap, uint64_t); for (uint64_t i = 6; i < narg; i++) fp[sz + 2 + i - 6] = va_arg(ap, uint64_t); va_end(ap); *gp(5) = (uint64_t)(fp + sz); *gp(4) = (uint64_t)(fp + 0x1000); } uint64_t R_FRAME_DESTROY() { free(*(void **)*gp(5)); return *gp(0); } void R_ADJCALLSTACKDOWN(uint64_t size) { *gp(4) -= size; ((uint64_t*)*gp(4))[-1] = size; // needed for CALL } void R_ADJCALLSTACKUP(uint64_t size) { *gp(4) += size; } uint64_t CALL(void*, uint64_t sp, ...); #if defined(__x86_64__) #error "untested architecture" __asm__( "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" ); #elif defined(__aarch64__) __asm__( "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 void R_CALL(void* a) { uint64_t regSave[16]; memcpy(regSave, gpregs, sizeof(gpregs)); *gp(0) = CALL(a, *gp(4), *gp(7), *gp(6), *gp(2), *gp(1), *gp(8), *gp(9)); *gp(3) = regSave[3]; *gp(4) = regSave[4]; *gp(5) = regSave[5]; *gp(12) = regSave[12]; *gp(13) = regSave[13]; *gp(14) = regSave[14]; *gp(15) = regSave[15]; } void R_MOV64rr(uint64_t dst, uint64_t a) { *gp(dst) = *gp(a); } void R_MOV64ri(uint64_t dst, uint64_t i) { *gp(dst) = i; } void R_MOV32rr(uint64_t dst, uint64_t a) { *gp(dst) = (uint32_t)*gp(a); } void R_MOV32ri(uint64_t dst, uint64_t i) { *gp(dst) = (uint32_t)i; } void R_MOV64mr(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint64_t*)mem(a, b, c, d) = *gp(e); } void R_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 R_MOV32mr(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint32_t*)mem(a, b, c, d) = *gp(e); } void R_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 R_MOV16mr(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint16_t*)mem(a, b, c, d) = *gp(e); } void R_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 R_MOV8mr(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint8_t*)mem(a, b, c, d) = *gp(e); } void R_MOV8mi(uint64_t a, uint64_t b, uint64_t c, uint64_t d, uint64_t e) { *(uint8_t*)mem(a, b, c, d) = e; } void R_MOV64rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = *(uint64_t*)mem(a, b, c, d); } void R_MOV32rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = *(uint32_t*)mem(a, b, c, d); } void R_MOVZXB32rr(uint64_t dst, uint64_t a) { *gp(dst) = (uint8_t)*gp(a); } void R_MOVZXB32rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = *(uint8_t*)mem(a, b, c, d); } void R_MOVZXW32rr(uint64_t dst, uint64_t a) { *gp(dst) = (uint16_t)*gp(a); } void R_MOVZXW32rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = *(uint16_t*)mem(a, b, c, d); } void R_MOVSXB32rr(uint64_t dst, uint64_t a) { *gp(dst) = (uint32_t)(int8_t)*gp(a); } void R_MOVSXB32rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = (uint32_t)*(int8_t*)mem(a, b, c, d); } void R_MOVSXB64rr(uint64_t dst, uint64_t a) { *gp(dst) = (int8_t)*gp(a); } void R_MOVSXB64rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = *(int8_t*)mem(a, b, c, d); } void R_MOVSXW32rr(uint64_t dst, uint64_t a) { *gp(dst) = (uint32_t)(int16_t)*gp(a); } void R_MOVSXW32rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = (uint32_t)*(int16_t*)mem(a, b, c, d); } void R_MOVSXW64rr(uint64_t dst, uint64_t a) { *gp(dst) = (int16_t)*gp(a); } void R_MOVSXW64rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = *(int16_t*)mem(a, b, c, d); } void R_MOVSXWD4rr(uint64_t dst, uint64_t a) { *gp(dst) = (int32_t)*gp(a); } void R_MOVSXWD4rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = *(int32_t*)mem(a, b, c, d); } void R_LEA64rm(uint64_t dst, uint64_t a, uint64_t b, uint64_t c, uint64_t d) { *gp(dst) = (uint64_t)mem(a, b, c, d); } void R_CMP64rr(uint64_t a, uint64_t b) { eflags_set_sub(*gp(a), *gp(b)); } void R_CMP64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_sub(*gp(a), b); } void R_SUB64rr(uint64_t a, uint64_t b) { eflags_set_sub(*gp(a), *gp(b)); *gp(a) -= *gp(b); } void R_SUB64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_sub(*gp(a), b); *gp(a) -= b; } void R_ADD64rr(uint64_t a, uint64_t b) { eflags_set_add(*gp(a), *gp(b)); *gp(a) += *gp(b); } void R_ADD64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_add(*gp(a), b); *gp(a) += b; } void R_IMUL64rr(uint64_t a, uint64_t b) { eflags_set_mul(*gp(a), *gp(b)); *gp(a) *= *gp(b); } void R_IMUL64rri(uint64_t dst, uint64_t a, uint64_t b) { chki32(b); eflags_set_mul(*gp(a), b); *gp(dst) = *gp(a) * b; } void R_AND64rr(uint64_t a, uint64_t b) { eflags_set_logical(*gp(a) & *gp(b)); *gp(a) &= *gp(b); } void R_AND64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_logical(*gp(a) & b); *gp(a) &= b; } void R_TEST64rr(uint64_t a, uint64_t b) { eflags_set_logical(*gp(a) & *gp(b)); } void R_TEST64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_logical(*gp(a) & b); } void R_OR64rr(uint64_t a, uint64_t b) { eflags_set_logical(*gp(a) | *gp(b)); *gp(a) |= *gp(b); } void R_OR64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_logical(*gp(a) | b); *gp(a) |= b; } void R_XOR64rr(uint64_t a, uint64_t b) { eflags_set_logical(*gp(a) ^ *gp(b)); *gp(a) ^= *gp(b); } void R_XOR64ri(uint64_t a, uint64_t b) { chki32(b); eflags_set_logical(*gp(a) ^ b); *gp(a) ^= b; } // FIXME: shift flags void R_SHL64rr(uint64_t a) { *gp(a) <<= *gp(1) & 63; } void R_SHL64ri(uint64_t a, uint64_t b) { *gp(a) <<= (b & 63); } void R_SHR64rr(uint64_t a) { *gp(a) >>= *gp(1) & 63; } void R_SHR64ri(uint64_t a, uint64_t b) { *gp(a) >>= (b & 63); } void R_SAR64rr(uint64_t a) { *(int64_t*)gp(a) >>= *gp(1) & 63; } void R_SAR64ri(uint64_t a, uint64_t b) { *(int64_t*)gp(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; } void R_SETcc8r(uint64_t dst, unsigned cond) { *(uint8_t*)gp(dst) = Jcc(cond); } EOF gcc -shared -o bc3-rt.so bc3-rt.c -O2 CXX=g++ CXXFLAGS="-O3 -Wall -Wextra -std=c++20 $(llvm-config --cppflags --ldflags | tr '\n' ' ')" \ LDLIBS="$(llvm-config --libs)" make bc3 bc3-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;}") # Some basic binary operators testcase_ec "sub 1" 255 <(echo "main(argc){return 0-argc;}") testcase_ec "sub 2" 255 <(echo "main(argc){return -argc;}") testcase_ec "sub 3" 0 <(echo "main(argc){return 1-argc;}") testcase_ec "add 1" 3 <(echo "main(argc){return argc+2;}") testcase_ec "add 2" 3 <(echo "main(argc){return argc+4294967298;}") testcase_ec "inv 1" 254 <(echo "main(argc){return ~argc;}") testcase_ec "eq 1" 255 <(echo "main(argc){return -(argc==1);}") testcase_ec "eq 2" 0 <(echo "main(argc){return -(argc==2);}") testcase_ec "alloca 1" 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 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" 12 <(echo "main(){auto x=12;register p=&x;auto q=p[0];x=0;return q;}") testcase_ec "addrof 11" 2 <(echo "main(){auto x=254;register p=(&x)[0@1];x=0;return -p;}") # Test if testcase_ec "if 1" 10 <(echo "main(argc){if(argc<2)return 10;else return 0;}") testcase_ec "if 2" 0 <(echo "main(argc){if(argc>2)return 10;else return 0;}") testcase_ec "if 3" 10 <(echo "main(argc){if(argc==1)return 10;else return 0;}") testcase_ec "if 4" 0 <(echo "main(argc){if(argc==2)return 10;else return 0;}") testcase_ec "if 5" 0 <(echo "main(argc){if(argc!=1)return 10;else return 0;}") testcase_ec "if 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;}") # PHI nodes 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);}") # 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" 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 7" 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 8" 79 <(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 || 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 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);}")