# Programming Exercise 6: Instruction Selection

This is the continuation of hw04. You can continue from your own code or use the LLVM-IR generator from the website 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).


You may choose a target ISA, but I would strongly suggest an ISA with a three-address instruction form (i.e., source operands are not destroyed) to ease register allocation later on. 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 [1].

[1]: The flags register cannot be spilled (easily) and must be recomputed after destruction, which in turn affects life time of other values.


# Submission

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

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