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 line
In 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 "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;
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(); } }; }
char MYADCE::ID = 0; INITIALIZE_PASS(MYADCE, "myadce", "My Aggressive Dead Code Elimination", false, false)
runOnFunction
function: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(); }
testcode.ll
file, 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.
3.144.37.38