In this recipe, you will learn how to eliminate dead code from the program. By dead code elimination, we mean removing the code that has no effect whatsoever on the results that the source program outputs on executing. The main reasons to do so are reduction of the program size, which makes the code quality good and makes it easier to debug the code later on; and improving the run time of the program, as the unnecessary code is prevented from being executed. In this recipe, we will show you a variant of dead code elimination, called aggressive dead code elimination, that assumes every piece of code to be dead until proven otherwise. We will see how to implement this pass ourselves, and what modifications we need to make so that the pass can run just like other passes in the lib/Transforms/Scalar folder of the LLVM trunk.
To show the implementation of dead code elimination, we will need a piece of test code, on which we will run the aggressive dead code elimination pass:
$ cat testcode.ll declare i32 @strlen(i8*) readonly nounwind define void @test() { call i32 @strlen( i8* null ) ret void }
In this test code, we can see that a call to the strlen function is made in the test function, but the return value is not used. So, this should be treated as dead code by our pass.
In the file, include the InitializePasses.h file, located at /llvm/; and in the llvm namespace, add an entry for the pass that we are going to write:
namespace llvm {
…
…
void initializeMYADCEPass(PassRegistry&); // Add this lineIn the scalar.h file, located at include/llvm-c/scalar.h/Transform/, add the entry for the pass:
void LLVMAddMYAggressiveDCEPass(LLVMPassManagerRef PM);
In the include/llvm/Transform/scalar.h file, add the entry for the pass in the llvm namespace:
FunctionPass *createMYAggressiveDCEPass();
In the lib/Transforms/Scalar/scalar.cpp file, add the entry for the pass in two places. In the void llvm::initializeScalarOpts(PassRegistry &Registry) function, add the following code:
initializeMergedLoadStoreMotionPass(Registry); // already present in the file
initializeMYADCEPass(Registry); // add this line
initializeNaryReassociatePass(Registry); // already present in the file
…
…
void LLVMAddMemCpyOptPass(LLVMPassManagerRef PM) {
unwrap(PM)->add(createMemCpyOptPass());
}
// add the following three lines
void LLVMAddMYAggressiveDCEPass(LLVMPassManagerRef PM) {
unwrap(PM)->add(createMYAggressiveDCEPass());
}
void LLVMAddPartiallyInlineLibCallsPass(LLVMPassManagerRef PM) {
unwrap(PM)->add(createPartiallyInlineLibCallsPass());
}
…We will now write the code for the pass:
- Include the necessary header files:
#include "llvm/Transforms/Scalar.h" #include "llvm/ADT/DepthFirstIterator.h" #include "llvm/ADT/SmallPtrSet.h" #include "llvm/ADT/SmallVector.h" #include "llvm/ADT/Statistic.h" #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/InstIterator.h" #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/Pass.h" using namespace llvm;
- Declare the structure of our pass:
namespace { struct MYADCE : public FunctionPass { static char ID; // Pass identification, replacement for typeid MYADCE() : FunctionPass(ID) { initializeMYADCEPass(*PassRegistry::getPassRegistry()); } bool runOnFunction(Function& F) override; void getAnalysisUsage(AnalysisUsage& AU) const override { AU.setPreservesCFG(); } }; } - Initialize the pass and its ID:
char MYADCE::ID = 0; INITIALIZE_PASS(MYADCE, "myadce", "My Aggressive Dead Code Elimination", false, false)
- Implement the actual pass in the
runOnFunctionfunction:bool MYADCE::runOnFunction(Function& F) { if (skipOptnoneFunction(F)) return false; SmallPtrSet<Instruction*, 128> Alive; SmallVector<Instruction*, 128> Worklist; // Collect the set of "root" instructions that are known live. for (Instruction &I : inst_range(F)) { if (isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) || isa<LandingPadInst>(I) || I.mayHaveSideEffects()) { Alive.insert(&I); Worklist.push_back(&I); } } // Propagate liveness backwards to operands. while (!Worklist.empty()) { Instruction *Curr = Worklist.pop_back_val(); for (Use &OI : Curr->operands()) { if (Instruction *Inst = dyn_cast<Instruction>(OI)) if (Alive.insert(Inst).second) Worklist.push_back(Inst); } } // the instructions which are not in live set are considered dead in this pass. The instructions which do not effect the control flow, return value and do not have any side effects are hence deleted. for (Instruction &I : inst_range(F)) { if (!Alive.count(&I)) { Worklist.push_back(&I); I.dropAllReferences(); } } for (Instruction *&I : Worklist) { I->eraseFromParent(); } return !Worklist.empty(); } } FunctionPass *llvm::createMYAggressiveDCEPass() { return new MYADCE(); } - Run the preceding pass after compiling the
testcode.llfile, which can be found in the Getting ready section of this recipe:$ opt -myadce -S testcode.ll ; ModuleID = 'testcode.ll' ; Function Attrs: nounwind readonly declare i32 @strlen(i8*) #0 define void @test() { ret void }
The pass works by first collecting a list of all the root instructions that are live in the first for loop of the runOnFunction function.
Using this information, we move backwards, propagating liveness to the operands in the while (!Worklist.empty()) loop.
In the next for loop, we remove the instructions that are not live, that is, dead. Also, we check whether any reference was made to these values. If so, we drop all such references, which are also dead.
On running the the pass on the test code, we see the dead code; the call to the strlen function is removed.
Note that the code has been added to the LLVM trunk revision number 234045. So, when you are actually trying to implement it, some definitions might be updated. In this case, modify the code accordingly.