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/BDCE.h" 18 #include "llvm/ADT/SmallPtrSet.h" 19 #include "llvm/ADT/SmallVector.h" 20 #include "llvm/ADT/Statistic.h" 21 #include "llvm/Analysis/DemandedBits.h" 22 #include "llvm/Analysis/GlobalsModRef.h" 23 #include "llvm/IR/CFG.h" 24 #include "llvm/IR/InstIterator.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/IR/IntrinsicInst.h" 27 #include "llvm/IR/Operator.h" 28 #include "llvm/Pass.h" 29 #include "llvm/Support/Debug.h" 30 #include "llvm/Support/raw_ostream.h" 31 #include "llvm/Transforms/Scalar.h" 32 using namespace llvm; 33 34 #define DEBUG_TYPE "bdce" 35 36 STATISTIC(NumRemoved, "Number of instructions removed (unused)"); 37 STATISTIC(NumSimplified, "Number of instructions trivialized (dead bits)"); 38 39 /// If an instruction is trivialized (dead), then the chain of users of that 40 /// instruction may need to be cleared of assumptions that can no longer be 41 /// guaranteed correct. 42 static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) { 43 assert(I->getType()->isIntegerTy() && "Trivializing a non-integer value?"); 44 45 // Initialize the worklist with eligible direct users. 46 SmallVector<Instruction *, 16> WorkList; 47 for (User *JU : I->users()) { 48 // If all bits of a user are demanded, then we know that nothing below that 49 // in the def-use chain needs to be changed. 50 auto *J = dyn_cast<Instruction>(JU); 51 if (J && !DB.getDemandedBits(J).isAllOnesValue()) 52 WorkList.push_back(J); 53 } 54 55 // DFS through subsequent users while tracking visits to avoid cycles. 56 SmallPtrSet<Instruction *, 16> Visited; 57 while (!WorkList.empty()) { 58 Instruction *J = WorkList.pop_back_val(); 59 60 // NSW, NUW, and exact are based on operands that might have changed. 61 J->dropPoisonGeneratingFlags(); 62 63 // We do not have to worry about llvm.assume or range metadata: 64 // 1. llvm.assume demands its operand, so trivializing can't change it. 65 // 2. range metadata only applies to memory accesses which demand all bits. 66 67 Visited.insert(J); 68 69 for (User *KU : J->users()) { 70 // If all bits of a user are demanded, then we know that nothing below 71 // that in the def-use chain needs to be changed. 72 auto *K = dyn_cast<Instruction>(KU); 73 if (K && !Visited.count(K) && !DB.getDemandedBits(K).isAllOnesValue()) 74 WorkList.push_back(K); 75 } 76 } 77 } 78 79 static bool bitTrackingDCE(Function &F, DemandedBits &DB) { 80 SmallVector<Instruction*, 128> Worklist; 81 bool Changed = false; 82 for (Instruction &I : instructions(F)) { 83 // If the instruction has side effects and no non-dbg uses, 84 // skip it. This way we avoid computing known bits on an instruction 85 // that will not help us. 86 if (I.mayHaveSideEffects() && I.use_empty()) 87 continue; 88 89 if (I.getType()->isIntegerTy() && 90 !DB.getDemandedBits(&I).getBoolValue()) { 91 // For live instructions that have all dead bits, first make them dead by 92 // replacing all uses with something else. Then, if they don't need to 93 // remain live (because they have side effects, etc.) we can remove them. 94 DEBUG(dbgs() << "BDCE: Trivializing: " << I << " (all bits dead)\n"); 95 96 clearAssumptionsOfUsers(&I, DB); 97 98 // FIXME: In theory we could substitute undef here instead of zero. 99 // This should be reconsidered once we settle on the semantics of 100 // undef, poison, etc. 101 Value *Zero = ConstantInt::get(I.getType(), 0); 102 ++NumSimplified; 103 I.replaceNonMetadataUsesWith(Zero); 104 Changed = true; 105 } 106 if (!DB.isInstructionDead(&I)) 107 continue; 108 109 Worklist.push_back(&I); 110 I.dropAllReferences(); 111 Changed = true; 112 } 113 114 for (Instruction *&I : Worklist) { 115 ++NumRemoved; 116 I->eraseFromParent(); 117 } 118 119 return Changed; 120 } 121 122 PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) { 123 auto &DB = AM.getResult<DemandedBitsAnalysis>(F); 124 if (!bitTrackingDCE(F, DB)) 125 return PreservedAnalyses::all(); 126 127 PreservedAnalyses PA; 128 PA.preserveSet<CFGAnalyses>(); 129 PA.preserve<GlobalsAA>(); 130 return PA; 131 } 132 133 namespace { 134 struct BDCELegacyPass : public FunctionPass { 135 static char ID; // Pass identification, replacement for typeid 136 BDCELegacyPass() : FunctionPass(ID) { 137 initializeBDCELegacyPassPass(*PassRegistry::getPassRegistry()); 138 } 139 140 bool runOnFunction(Function &F) override { 141 if (skipFunction(F)) 142 return false; 143 auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits(); 144 return bitTrackingDCE(F, DB); 145 } 146 147 void getAnalysisUsage(AnalysisUsage &AU) const override { 148 AU.setPreservesCFG(); 149 AU.addRequired<DemandedBitsWrapperPass>(); 150 AU.addPreserved<GlobalsAAWrapperPass>(); 151 } 152 }; 153 } 154 155 char BDCELegacyPass::ID = 0; 156 INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce", 157 "Bit-Tracking Dead Code Elimination", false, false) 158 INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass) 159 INITIALIZE_PASS_END(BDCELegacyPass, "bdce", 160 "Bit-Tracking Dead Code Elimination", false, false) 161 162 FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); } 163