# 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()));`; C: `LLVMVerifyModule`).

The recommended language is C++. There is no strict limitation on the programming language, but your submission must use the LLVM API directly (generating textual IR/bitcode manually or through some abstraction library is not permitted). In addition, the code should be human-readable and have minimal dependencies besides compiler, standard library, LLVM, and your parser. Use LLVM 15, 16, or 17.

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)


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


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

Generate at the LLVM-IR for some programs and verify its correctness (`llvm::verifyFunction(*fn, &llvm::errs())`). Also test possible corner cases from the example program above.

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

Send an e-mail to engelke+cghomework@in.tum.de until 2023-11-29, 23:59 with:

- Subject: "Homework 3: YourMatrNr YourName"
- A single(!) .tar.xz file attached named with "hw3-YourMatrNr-YourLastName.tar.xz", which contains a single folder "hw3-YourMatrNr-YourLastName", which contains your submission
- The message body can remain empty
- Include a Makefile with compilation directives s.t. `make` compiles the code
- Specify correct dependencies in the 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.
- Avoid external dependencies and complex build systems (no cmake, cargo, etc.)
- Put the source in a single source file (if easily possible)
- Include answers to theory questions as comments in the source file


# Appendix: Compiling LLVM-IR to Assembly from C++

    int llvmCodeGen(llvm::Module* mod) {
      llvm::InitializeNativeTarget();
      llvm::InitializeNativeTargetAsmPrinter();
      llvm::InitializeNativeTargetAsmParser();

      std::string triple = "x86_64-unknown-linux-gnu";

      std::string error;
      const llvm::Target* target = llvm::TargetRegistry::lookupTarget(triple, error);
      if (!target) {
        std::cerr << "could not get target: " << error << "\n";
        return 1;
      }

      llvm::TargetOptions target_options;
      llvm::TargetMachine* tm = target->createTargetMachine(
        /*TT=*/triple, /*CPU=*/"", /*Features=*/"", target_options,
        llvm::Reloc::PIC_, llvm::CodeModel::Small, llvm::CodeGenOpt::Aggressive,
        /*JIT=*/false
      );
      if (!tm) {
        std::cerr << "could not allocate target machine\n";
        return 1;
      }

      llvm::SmallVector<char, 8192> obj_buffer;
      llvm::raw_svector_ostream obj_stream(obj_buffer);
      llvm::legacy::PassManager pm;
      if (tm->addPassesToEmitFile(pm, obj_stream, nullptr, llvm::CGFT_AssemblyFile,
                                  false)) {
        std::cerr << "target doesn't support code gen\n";
        return 1;
      }

      pm.run(*mod);
      llvm::outs() << obj_buffer;
      return 0;
    }