#!/bin/bash
: <<'````````bash'
# Programming Exercise 3: Generating LLVM-IR

This is the continuation of hw2. You can continue from your own code or use the parser from the website as starting point.

## Implementation

Generate a single (valid) LLVM-IR module from an AST and print it to standard output. For parameters and register-variables, construct SSA yourself/explicitly using the algorithm discussed in the lecture (Braun et al. 2013); for auto-variables, simply place `alloca`s in the entry block (why there?). Use `getelementptr` for subscripts. Declare external functions as required. Language semantics are described in the specification in hw2. Run the LLVM verifier to ensure your generated IR is valid (C++: `assert(!llvm::verifyModule(*mod, &llvm::errs()));`).

Your submission must use the LLVM API (C++ or C) directly. In addition, the code should be human-readable and have minimal dependencies besides compiler, standard library, LLVM, and your parser. Use LLVM 17, 18, or 19.

You might find these links helpful (as always, only parts of each page are actually relevant):

- https://llvm.org/docs/LangRef.html
- https://www.llvm.org/docs/ProgrammersManual.html (this also contains documentation on LLVM's custom data structures, which you might find useful, too)
- https://llvm.org/doxygen/classllvm_1_1IRBuilder.html (and other Doxygen pages)


## Command Line Interface

    usage: ./bc1 (-a|-c|-l) program_file
        B compiler. Exit with non-zero status code on invalid input.
        -a: print AST as S-Expressions.
        -c: syntax/semantic check only (build AST nonetheless). No output other than the exit code.
        -l: emit LLVM-IR.
        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 `-i`, `-r`, and `-S`, which will be used in subsequent homework.


## Example Program

    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;
    }

    deadcode(a, b, c) {
        if (a)
            return a;
        else
            return b;
        return c;
    }

    shortcircuit() {
        return fnA() && fnB() || fnC();
    }

    undef() { return; }

    main(argc, argv) {
        auto f1 = 44629835118;
        printf(&f1, argc);
        while (argc) {
            puts(argv[0]);
            argv = &argv[1];
            argc = argc - 1;
        }
        return 0;
    }


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

Can you reuse information from previous semantic analysis about variable scopes to improve the performance of your implementation?

Is there obvious potential for IR optimizations? Pipe the output to llc (or use the code snippet below) and check whether the machine code matches your expectation.


## Submission

- Submission deadline: 2024-11-27 23:59
- Submit using `curl --data-binary "@<your-submission-file>" 'https://db.in.tum.de/teaching/ws2425/codegen/submit.py?hw=3&matrno=<your-matrno>'`
- Write your solution in a single C++ file. (Default file name: `bc1.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 <hw3.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 ./bc1 -l "$3" | lli; s="${PIPESTATUS[@]}"; [ "$s" != "0 $2" ]; \
    then echo "FAILED: $1 (got [$s] expected [0 $2])"; FAILED=1; fi; }
testcase_chk() { ./bc1 -l "$2" | "${@:3}" || { echo "FAILED: $1"; FAILED=1; }; }
testcase_run_chk() { ./bc1 -l "$2" | lli | "${@:3}" || { echo "FAILED: $1"; FAILED=1; }; }

CXX=g++ CXXFLAGS="-O3 -Wall -Wextra -std=c++20 $(llvm-config --cppflags --ldflags | tr '\n' ' ')" \
    LDLIBS="$(llvm-config --libs)" make bc1

# testcase_ec checks the return status. 1 is used by lli, thus prohibited.

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

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

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

# Test auto, addrof, and subscript
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_chk "auto alloca" <(echo "main(){auto x=2;auto y=x=4;return x+y;}") grep -q alloca
testcase_chk "auto has no phi" <(echo "f(a){auto x=0;if(a>0)x=a+2;else x=a+1;return x;}") not grep -q phi
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];}")

# 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 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 || 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 register (shallow tests, could definitly be expanded to cover more corner cases)
testcase_chk "reg has phi" <(echo "f(a){register x=0;if(a>0)x=a+2;else x=a+1;return x;}") | grep -q phi
testcase_chk "reg has no alloca" <(echo "f(a){register x=0;if(a>0)x=a+2;else x=a+1;return x;}") not grep -q alloca

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

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

exit $FAILED