# 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 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 cdce.so cdce.cc -fPIC
    opt -load-pass-plugin=$PWD/cdce.so -passes=cdce input.ll | llvm-dis

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 | opt -force-remove-attribute=FUNCNAME:optnone -passes=forceattrs,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;
            }
          );
        }
      };
    }