1 //===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file implements the Bit-Tracking Dead Code Elimination pass. Some 11 // instructions (shifts, some ands, ors, etc.) kill some of their input bits. 12 // We track these dead bits and remove instructions that compute only these 13 // dead bits. 14 // 15 //===----------------------------------------------------------------------===// 16 17 #include "llvm/Transforms/Scalar.h" 18 #include "llvm/ADT/SmallVector.h" 19 #include "llvm/ADT/Statistic.h" 20 #include "llvm/Analysis/GlobalsModRef.h" 21 #include "llvm/Analysis/DemandedBits.h" 22 #include "llvm/IR/CFG.h" 23 #include "llvm/IR/InstIterator.h" 24 #include "llvm/IR/Instructions.h" 25 #include "llvm/IR/IntrinsicInst.h" 26 #include "llvm/IR/Operator.h" 27 #include "llvm/Pass.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.h" 30 using namespace llvm; 31 32 #define DEBUG_TYPE "bdce" 33 34 STATISTIC(NumRemoved, "Number of instructions removed (unused)"); 35 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)"); 36 37 namespace { 38 struct BDCE : public FunctionPass { 39 static char ID; // Pass identification, replacement for typeid 40 BDCE() : FunctionPass(ID) { 41 initializeBDCEPass(*PassRegistry::getPassRegistry()); 42 } 43 44 bool runOnFunction(Function& F) override; 45 46 void getAnalysisUsage(AnalysisUsage& AU) const override { 47 AU.setPreservesCFG(); 48 AU.addRequired<DemandedBits>(); 49 AU.addPreserved<GlobalsAAWrapperPass>(); 50 } 51 }; 52 } 53 54 char BDCE::ID = 0; 55 INITIALIZE_PASS_BEGIN(BDCE, "bdce", "Bit-Tracking Dead Code Elimination", 56 false, false) 57 INITIALIZE_PASS_DEPENDENCY(DemandedBits) 58 INITIALIZE_PASS_END(BDCE, "bdce", "Bit-Tracking Dead Code Elimination", 59 false, false) 60 61 bool BDCE::runOnFunction(Function& F) { 62 if (skipOptnoneFunction(F)) 63 return false; 64 DemandedBits &DB = getAnalysis<DemandedBits>(); 65 66 SmallVector<Instruction*, 128> Worklist; 67 bool Changed = false; 68 for (Instruction &I : instructions(F)) { 69 if (I.getType()->isIntegerTy() && 70 !DB.getDemandedBits(&I).getBoolValue()) { 71 // For live instructions that have all dead bits, first make them dead by 72 // replacing all uses with something else. Then, if they don't need to 73 // remain live (because they have side effects, etc.) we can remove them. 74 DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n"); 75 // FIXME: In theory we could substitute undef here instead of zero. 76 // This should be reconsidered once we settle on the semantics of 77 // undef, poison, etc. 78 Value *Zero = ConstantInt::get(I.getType(), 0); 79 ++NumSimplified; 80 I.replaceAllUsesWith(Zero); 81 Changed = true; 82 } 83 if (!DB.isInstructionDead(&I)) 84 continue; 85 86 Worklist.push_back(&I); 87 I.dropAllReferences(); 88 Changed = true; 89 } 90 91 for (Instruction *&I : Worklist) { 92 ++NumRemoved; 93 I->eraseFromParent(); 94 } 95 96 return Changed; 97 } 98 99 FunctionPass *llvm::createBitTrackingDCEPass() { 100 return new BDCE(); 101 } 102 103
