#!/bin/bash
: <<'````````bash'
# Programming Exercise 4: 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 in-place into 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
    }

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:

- 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`).
- Use `replaceAllUsedWith` to replace an instruction with a newly created function call.
- Be careful about folding memory operations into instructions: respect their ordering (correctness!) and avoid duplication.
- You can use `llvm::match` (from `<llvm/IR/PatternMatch.h>`) 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 authoritative 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(numStackArgs, stackFrameSize, 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 can remain as they are, but all parameters shall be "register operands".
- 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: 2024-12-11 23:59
- Submit using `curl --data-binary "@<your-submission-file>" 'https://db.in.tum.de/teaching/ws2425/codegen/submit.py?hw=4&matrno=<your-matrno>'`
- Write your solution in a single C++ file. (Default file name: `bc2.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 <submission> somedir; cd somedir; bash <hw4.txt>`
- 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 ./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; }

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

# Extract verification program
extract bc2-verify.cc <<EOF
#include <llvm/ADT/StringSwitch.h>
#include <llvm/IR/Constants.h>
#include <llvm/IR/Instruction.h>
#include <llvm/IR/Instructions.h>
#include <llvm/IR/Module.h>
#include <llvm/IRReader/IRReader.h>
#include <llvm/Support/SourceMgr.h>
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<llvm::Argument>(V))
    return Arg->getArgNo() < 6;
  if (!llvm::isa<llvm::CallInst, llvm::PHINode, llvm::UndefValue>(V))
    return false;
  return true;
}
static void validateFrameSetup(llvm::Value *I) {
  llvm::CallInst *CI = llvm::dyn_cast<llvm::CallInst>(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<llvm::ConstantInt>(CI->getArgOperand(0)) ||
      !llvm::isa<llvm::ConstantInt>(CI->getArgOperand(1)))
    abortWith(I, "FRAME_SETUP call must have two constants as first arguments");
  auto NA = llvm::cast<llvm::ConstantInt>(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<llvm::Argument>(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<llvm::CallInst>(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<llvm::ReturnInst>(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;
  }
  M->print(llvm::errs(), nullptr);
  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<llvm::PHINode>(&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<llvm::ReturnInst>(&I)) {
          if (!Ret->getReturnValue() || !isRegOp(Ret->getReturnValue()))
            abortWith(Phi, "ret operand must be register");
          validateFrameDestroy(I.getPrevNode());
        } else if (auto *Br = llvm::dyn_cast<llvm::BranchInst>(&I)) {
          if (Br->isUnconditional())
            continue;
          auto *Cond = Br->getCondition();
          llvm::CallInst *CI = llvm::dyn_cast<llvm::CallInst>(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<llvm::CallInst>(&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<unsigned>(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 <<EOF
#include <stdarg.h>
#include <stdint.h>
#include <stdlib.h>
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 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 MOVSXWD4rr(uint64_t a) { return (int32_t)a; }
uint64_t MOVSXWD4rm(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=g++ 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;}")

# 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;}")

# 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);}")

# 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);}")

# 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;}")
exit $FAILED