# In-Class Exercise 5: LLVM-IR Optimizations

## Writing a Simple DCE Pass

Implement a simple dead code elimination pass plug-in that works as follows. (Why does this algorithm work correctly?)

- Traverse the blocks of the dominator tree in post-order:
- Traverse instructions in reverse order:
- Determine whether the instruction is trivially dead and thus safe to remove (i.e., no side effects and no users) and if so, erase it.


Additional notes regarding the implementation:

- You might find print-debugging (e.g., on an llvm::Value or an llvm::DominatorTree) helpful.
- Get the `llvm::DominatorTree` from the `llvm::FunctionAnalysisManager`.
- Consider using `llvm::post_order` for post-order traversal.
- Be careful when iterating over instructions as you remove them.
  (Spoiler: `echo bGx2bTo6bWFrZV9lYXJseV9pbmNfcmFuZ2UK | base64 -d`)
- Check for useful methods of llvm::Instruction to determine side effects.
- Be sure to use the correct method for eliminating an instruction.


Use the code snippet below as starting point. Compile and test with:

    c++ $(llvm-config --cppflags) -shared -g -o llvm-customdce.so llvm-customdce.cc -fPIC
    opt -load-pass-plugin=$PWD/llvm-customdce.so -passes=cdce input.ll

Generate suitable LLVM-IR input files to test your code. You might find the following command helpful to generate SSA-based LLVM-IR functions from C code:

    clang -emit-llvm -o - -c test.c -Xclang -disable-O0-optnone | opt  -passes=mem2reg | llvm-dis


## opt

Run the following command to see the default -O3 pipeline:

    opt -passes="default<O3>" -print-pipeline-passes </dev/null

Use the reference to find out more about some passes: https://llvm.org/docs/Passes.html

You can dump the IR after each pass using `-print-after-all` or `-print-after=PASS`.


## Appendix: Pass Plug-in Template

    #include "llvm/IR/PassManager.h"
    #include "llvm/Passes/PassBuilder.h"
    #include "llvm/Passes/PassPlugin.h"

    class CustomDCE : public llvm::PassInfoMixin<CustomDCE> {
    public:
      llvm::PreservedAnalyses run(llvm::Function &F, llvm::FunctionAnalysisManager &AM) {
        return llvm::PreservedAnalyses::none();
      }
    };

    extern "C" ::llvm::PassPluginLibraryInfo LLVM_ATTRIBUTE_WEAK
    llvmGetPassPluginInfo() {
      return { LLVM_PLUGIN_API_VERSION, "CustomDCE", "v1",
        [] (llvm::PassBuilder &PB) {
          PB.registerPipelineParsingCallback(
            [] (llvm::StringRef Name, llvm::FunctionPassManager &FPM,
                llvm::ArrayRef<llvm::PassBuilder::PipelineElement>) {
              if (Name == "cdce") {
                FPM.addPass(CustomDCE());
                return true;
              }
              return false;
            }
          );
        }
      };
    }


## Example Input

```
base64 -d <<EOF | gunzip
H4sIAAAAAAAAA6VUTW/bMAy9+1cwHoK2iGVY/kjcdB02YCiww047DkWg2LIjTJYNSW6yFf3vo+w0
aRr0UDQwZIbvkbSeKN7Az7bsJf/xHW7h4rOxpVBfLjzT9rrgq0pIrljDEfNt04WF71mma26hZJZJ
9rftrcM4aZacdPEiWiYxPs6kRzNezlN8iBhfVR4taZwTlS/p3LHQ9wsdh+RWi04ORXf5fIWo5uWG
WSKF6nekVr3veTdw16vCilbBN2u1WYJqhUIGR6NXW6FK6LeWrSX3Sl45f2nalWwLJkEkMXy13NhL
Zzk+UmAaXcGnCB49gLUGydZcwjT2vHgJ7/zdQIefbHAHU5oEuGDKaRjF6Og2Yij/GyIHwH2A5vTa
2Qncjzz6Jm9xwnuTRtMXvARpomg6MNIOXIxEOBq3KSgygufdpgeLZp6XfmTjsaudodX0EpTZPpem
wbA6dP4azY7YAjFWlueRDszP0wYwFLw+D4sxLHcYjc6UQN2zow40Om6fHk1sAUrfK8ULJdKThhrS
vbulXnaU0+FVzgRzJh/JOYhH03P1AqCn9yGAiZQPTSjbtoNJioWzDxR2dTU/9CX1njyP4X0W6x7v
p7uOt/D49tUGv9I4n0iHBMu1f+szKX3wG6GI5DWT5IEXttVkK0q7QThCULXEatZ1QtWkYYPb6p4j
Yiwr/pBOt3aMWvdVxTUx4h9HUo6McUKRouvRgdOJzNOjt+LM9pobhGbFLg9m1c7oYNY0u2BmDB+W
OJjt8oWL6RXf56m54loUPuDmR3GbYSiHlWS1k2nyOMGDmODBT+KnPUWUXNkRS1xcNNhOR0fzt8WG
6dXw5cGgboqB9MBZOM5exD3BZY5PCafiHmnJWNcvJFM1PHBt3BymWRiFC7i842Wr2f4vicOqSBZX
Poa59iqFsQIHt4vHaTPJ0J/t0x36Kmx6Y/EYahTTYOR/NkWUXaYGAAA=
EOF
```


## Solution

```
base64 -d <<EOF | gunzip
H4sIAAAAAAAAA4VUXY/aOhB9z6+Yy61Q2BJQX9MFia/tRRe2EaTtQ1Uhk0yoVceObActavnvnXyS
vbvV5WFZe86cOZ45w3gM0du38MYV4px6kZIJP4HnRVmWCHYyA/DMd6YxBk9BBcmNVWkc4ci8uIki
8JJgvXDGY1CZBU8oFnsZM8bLRH7icvIm+LIcv+QpMWgm7SVwmeV2JAT8qorE3DjO31xGIo8ResXd
eLYMx4Ey9qOOUa8tamaVHn3vvYbbh5vVk9XMvBJf78ZLlXJZpP8hHpC+LZPshK8VCEr15dc85yL+
P1BQNqPAOJGgMyzKdy8XK/Ahy4+CR+Wrfb9Ar2WitvyJy/sWNoWfToXzHWigGg3qM8YzycSFSoHO
pVvFHnIZWa4k9B+G8PyqQvPmddCfbQfEDtDwtq0JNSLcLUOYFKDRCe0OTS7s/Su4hnXqPgzel2Rk
iWXoTTPNpa1VodbGHdTxRGlwW6aC41HFOGcGa376l0dzoaIf0zuQFKNeVZGMPHBQhQncZTho1Df6
b3l3cDyS+CLXm5L88tKt6wOw3CogecYSqMpN2Q88aCZP6B6P3lQfkebmDoZQnlDGrfxnD1gTh87L
9vahJPS7hMi0uBzIHTV1WbOjG4An4BaXI272LMFQ7TBVZ3QH0O/DX2UkZZd/2Bn3PMZVkmBkTRUt
gzk54YBpZi8ksGWFKkh7YvBBqzSgxaZhtC+4Ore/Gm2u5Z+s5ftSSawyr871vePgE+2fhN6iB75/
827l9A0/aqYvhZFhs/m8PczCcLeefwpXhy+r2b9Ogf+A9pZQIN2qIbWQn1VisPn0Yf14mAXrw+fV
br/++Dikms1a9Ohwftcbli/4+q0ZR2cvoR/Mb40O5iNNEzUkPeAZCi6RemK4PC2YEEdG7mibd6Pb
WxrYaYcJPLIU/7tPnV8K2rZgO+y0v7HkTGt2IYL7F/roUAtZCUxpOtOuLSpjFFVhMoFeRD+Uvedx
ACo5YnFccLptYzo2rT51V8ml2A1cnReQhAnTwTSImq840vivzm9PyQWWSAYAAA==
EOF
```