# 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 and annotate your instruction-selected-LLVM-IR with the allocation, inserting appropriate spill code and register moves (if necessary). There is no requirement on the complexity of the algorithm, it should "just work". Note that this process involves SSA destruction and "elimination" of phi nodes. Annotate the output of each instruction with metadata to indicate the register. At function calls, the arguments and return value have fixed locations and observe that the calling convention may permit the callee to clobber more registers. You may assume that all parameters are passed in registers (you don't need to handle functions requiring parameters to be passed on the stack).

Some comments:

- You can use the following snippet to attach metadata to an instruction:

  ```c++
  auto val = llvm::ValueAsMetadata::get(llvm::ConstantInt::get(i64ty, regidx));
  inst->setMetadata("reg", llvm::MDNode::get(ctx, {val}));
  ```

- You might find `llvm::SplitAllCriticalEdges` useful.
- It will be necessary to insert new instructions, modify existing instructions, and to insert allocas (for stack spills). Be careful with IR modifications while iterating over it at the same time.
- You can move a value to a different register using an appropriate move instruction.
- If you allocate a register to a phi node, make sure that all incoming values are actually stored in that register (i.e., the `reg` metadata of all incoming values and the phi node are identical).
- If you choose to implement a more advanced algorithm, it might be easier to first restrict yourself to block-local allocation and assignment.

# Submission

Send an e-mail to engelke+cghomework@in.tum.de until 2024-01-24, 23:59 with:

- Subject: "Homework 5: YourMatrNr YourName"
- A single(!) .tar.xz file attached named with "hw5-YourMatrNr-YourLastName.tar.xz", which contains a single folder "hw5-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.
- 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