# In-Class Exercise 4: Getting Started with LLVM

Write an LLVM-based compiler for Brainfuck. At first, only implement non-loop operations (i.e., `<>+-.,`). Once these work, you might look into implementing loops.

## Initialization

- Create a new basic block in `main` as program entry.
- Create an `llvm::IRBuilder<>` and position at the end of the entry block.
- In the entry block, place an alloca (`CreateAlloca`) and zero-initialize the memory (`CreateMemSet`).
- End the main function with a return (`CreateRet`).

Your program should now compile and emit valid LLVM-IR. Verify this by piping the output to `lli`: `./llvm-bf "+++++." | lli`


## Non-Loop Operations

- Keep track of the current SSA value representing the current pointer, initializing it with the result of the `alloca`.
- Implement the operations `<>+-.,` using appropriate LLVM-IR instructions.

This command should now work and print `3434`: `./llvm-bf "+++++++++++++++++++++++++++++++++++++++++++++++++++>++++++++++++++++++++++++++++++++++++++++++++++++++++<.>.<.>." | lli`


## Loops

### Simple: alloca

- Create a stack slot using `alloca` that holds the current pointer. Use `load`/`store` to fetch/update the pointer when encountering loop instructions.
- Keep track of loop nesting using a stack of basic block pairs (condition block and continuation block).
- For `[`, create a new basic block for the condition. Also create a new basic block for the loop body and update the `IRBuilder` insert point to point to the body block.
- For `]`, *un*conditionally branch back to the condition block, get it from the loop nesting stack. Update the `IRBuilder` insert point to point to the continuation block.

This command should print `Hello World!`: `./llvm-bf "++++++++[>++++[>++>+++>+++>+<<<<-]>+>->+>>+[<]<-]>>.>>---.+++++++..+++.>.<<-.>.+++.------.--------.>+.>++." | lli`

### Advanced: PHI nodes

- Propagate the current pointer using PHI nodes, do not use alloca/load/store for this.
- Keep track of loop nesting using a stack of tuples of two basic blocks and one PHI node.
- For `[`, create a new basic block for the condition with a PHI node for merging the value of the current pointer. Also create a new basic block for the body and update the `IRBuilder` insert point.
- For `]`, *un*conditionally branch back to the condition block and add the updated pointer value to the PHI node. Update the `IRBuilder` insert point to point to the continuation block.


## Optimizations

You might have noticed that the generated LLVM-IR is not exactly efficient. Pipe it through the optimizer (`... | opt -O3 -S`). How much does the code quality improve?


## Links

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)


## Appendix: Template

    // c++ -o llvm-bf llvm-bf.cc $(llvm-config --cppflags --ldflags --libs)
    #include <cstdlib>
    #include <llvm/IR/Instructions.h>
    #include <llvm/IR/IRBuilder.h>
    #include <llvm/IR/LLVMContext.h>
    #include <llvm/IR/Module.h>
    #include <llvm/IR/Verifier.h>
    #include <llvm/Support/raw_ostream.h>

    int main(int argc, char** argv) {
      if (argc < 2) abort();
      const char* program = argv[1];

      llvm::LLVMContext ctx;
      auto modUP = std::make_unique<llvm::Module>("mod", ctx);
      llvm::Type* voidTy = llvm::Type::getVoidTy(ctx);
      llvm::Type* i8Ty = llvm::Type::getInt8Ty(ctx);
      llvm::Type* ptrTy = llvm::PointerType::get(ctx, 0);

      // Declare putchar
      llvm::FunctionType* putTy = llvm::FunctionType::get(voidTy, {i8Ty}, false);
      llvm::Function* put = llvm::Function::Create(putTy, llvm::GlobalValue::ExternalLinkage,
                                                  "putchar", modUP.get());
      // Declare getchar
      llvm::FunctionType* getTy = llvm::FunctionType::get(i8Ty, {}, false);
      llvm::Function* get = llvm::Function::Create(getTy, llvm::GlobalValue::ExternalLinkage,
                                                  "getchar", modUP.get());

      // Prepare function main
      llvm::FunctionType* fnTy = llvm::FunctionType::get(i8Ty, {}, false);
      llvm::Function* fn = llvm::Function::Create(fnTy, llvm::GlobalValue::ExternalLinkage,
                                                  "main", modUP.get());

      // TODO: implement Brainfuck compiler here

      // Print module to stdout and run verifier
      modUP->print(llvm::outs(), nullptr);
      return !!llvm::verifyModule(*modUP, &llvm::errs());
    }

## Solution

```
base64 -d <<EOF | gunzip
H4sIAAAAAAAAA7VWUW/iOBB+51f4ug+b0ADltDpVgUNa0F4Pia5Q2evLaoVMYiDCsXOOQ1tV/Pcd
24E4rUNvdbt5qIpnvm++GY/Hbr1LWESLmKBhlMuYJqtRq1rak0hyYa9Quk9707velOVSFJFMOMu7
W6fH3bhIaEyE2zyb3d9OOJPkUbodbnlcUOKwLYos40L2BH5YclBBcKq8WgmTKMUJ89Q/WGyiAEVb
LNpt9WPvo+cWQskaecqEhuh3H+EV8Hj+AAwR5CGNP8oE3wicoj818Gv/26AFHip2GFqyUSQfFRQX
kqOUx//MAQE1DMMU78iyYMm/BRkamElm5F2A30WgkDqqMX55ykgb7XkSf3kCimoxDDdE3ut1zwVJ
rl2AKZPXDYBMCgsx51ApIk5ABQnQlW+l+1fB9B6X8EJacNtm8CaFAD0rYYcArTHNiSXiiNBMr3jC
cAJ7KYmnwwSl9YbyFab3mBYQ5NMj6GWYzhK2wxsSAPOPfBfArLYYdkDvV1eJ9h0CTbpgPZuuyhKS
PZso+DUnqgP8kkSB2ZloQ6Zr9r8TXbPmPBX9L0lTHffmHMc4T6Ix5dGujQiT4mk8PmmsbCeVuvsv
tCNwrpmh6vVKhJasjxCQrFlnBPE+io13ZZXjNPOGI5SIlVdGtTxqLODSNcE/UpCCy0KrZXOO//jg
9a/gMz1aud+SdAHZAovtfQ1aAqQBareMfjOm0YzzbMrWXE9BV4FgAMbj8aDBSgFet87/nn7msUll
vk2U6TDQ8WAAmntjeAw60viFxNFOa3rYJpQgr10OWr8UlT8k0LXV+uXl0RLhnKD3o/fhq8JN1Ny+
+TTvL6FWpny6Kn1/gFbgsRtYBMMfIOg4GS6BocIuIEniWbsYx9avGcdxxejXd6rv+2bZEaTzs4J0
zkXp1qJMMKVq8Krh3UR+cNEEZ8VqWpDTLOMr4J/Lc9/UlW+fWuV3PLRNXKaH3+ZSfm9xZYLsNZdK
9UaVOydCaqN3glVlGAvPZFKzLY44fRG/9HAes1rrgs3TN3oAj5kjzPh1RjiOpyziacI2Zk4YyRX9
8UR2syLfLlfwn3c8r89GSlCWLChJy4nSIN/42jpAbDUc1Gdt/sFqgW9WC6gHWiWNpJl8gqFuv9Qa
G0X+x0aR1nRX32k0UlXeKrguiatePFu+sCXdxrK7GsTdIcDydpO8dqrdK8pW65Fp/rmAI+g80yfZ
LkETFcW0bVBWVyNebLO7j+WrRjjFauwF9ffQKt/ov53rgdpVeKfeJ7Ur0HjoN0FnlAldNV0jXsjc
g0nEoCJ6Gik/QWQhGLoatA6t7x/+/NUNDQAA
EOF
```