# 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 (solution to hw3) as starting point.

## Implementation

Implement an instruction selector for the subset of LLVM-IR that you generate. After the transformation, the rewritten function shall only consist of calls which represent a machine code instruction (or a fixed sequence thereof) and calls to other functions (these need no modifications). Take care of constant operands, ISAs frequently have severely limited encoding capabilities for immediate operands -- these may demand an extra move operation to construct the constant. For basic blocks with a conditional terminator, the conditional branch instruction shall return the `i1` that is used as LLVM branch condition. Here is an example for AArch64:

    define i64 @abs(i64 %0) {
      %2 = call i64 (...) @CMPXrr_CSETc(i64 %0, i64 0, i64 0)
      %3 = call i1 (...) @CBNZX(i64 %2)
      br i1 %3, label %4, label %6

    4:                                                ; preds = %1
      %5 = call i64 (...) @SUBXrr(i64 0, i64 %0)
      ret i64 %5

    6:                                                ; preds = %1
      ret i64 %0
    }

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. There, you can use a greedy strategy for matching (easiest) or a more advanced approach.

NOTE: if you find yourself spending too much time implementing an algorithm, consider using a more simple approach (or contact the instructor for advice).


## ISA Selection

You may choose a target ISA, but I would strongly suggest an ISA that I am (or can be easily made) familiar with (including, but not limited to: x86-64, AArch64, rv64, MIPS). I would recommend x86-64 or AArch64, so that you can eventually execute the result of your compiler.

For an ISA with a flags register, consider merging flag-setting and flag-using instructions into one macro-op to avoid handling flag allocation later on. (The flags register cannot be spilled (easily) and must be recomputed after destruction, which in turn affects life time of other values.)


## Testing

Testing is not easy, but also not impossible. You can write software implementations of your machine code instructions in C and link against these. If you do write such implementations, please include them in your submission. Example:

    long SUBXrr(long a, long b) { return a - b; }
    _Bool CBNZX(long n) { return !!n; }
    long CMPXrr_CSETc(long a, long b, long cond) {
      switch (cond) {
      case 0: return a < b;
      case 1: return a >= b;
      // ...
      }
    }


# Submission

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

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