1 //===---- BDCE.cpp - Bit-tracking dead code elimination -------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 // 9 // This file implements the Bit-Tracking Dead Code Elimination pass. Some 10 // instructions (shifts, some ands, ors, etc.) kill some of their input bits. 11 // We track these dead bits and remove instructions that compute only these 12 // dead bits. We also simplify sext that generates unused extension bits, 13 // converting it to a zext. 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/IRBuilder.h" 24 #include "llvm/IR/InstIterator.h" 25 #include "llvm/IR/Instructions.h" 26 #include "llvm/InitializePasses.h" 27 #include "llvm/Pass.h" 28 #include "llvm/Support/Debug.h" 29 #include "llvm/Support/raw_ostream.h" 30 #include "llvm/Transforms/Scalar.h" 31 #include "llvm/Transforms/Utils/Local.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 STATISTIC(NumSExt2ZExt, 39 "Number of sign extension instructions converted to zero extension"); 40 41 /// If an instruction is trivialized (dead), then the chain of users of that 42 /// instruction may need to be cleared of assumptions that can no longer be 43 /// guaranteed correct. 44 static void clearAssumptionsOfUsers(Instruction *I, DemandedBits &DB) { 45 assert(I->getType()->isIntOrIntVectorTy() && 46 "Trivializing a non-integer value?"); 47 48 // Initialize the worklist with eligible direct users. 49 SmallPtrSet<Instruction *, 16> Visited; 50 SmallVector<Instruction *, 16> WorkList; 51 for (User *JU : I->users()) { 52 // If all bits of a user are demanded, then we know that nothing below that 53 // in the def-use chain needs to be changed. 54 auto *J = dyn_cast<Instruction>(JU); 55 if (J && J->getType()->isIntOrIntVectorTy() && 56 !DB.getDemandedBits(J).isAllOnes()) { 57 Visited.insert(J); 58 WorkList.push_back(J); 59 } 60 61 // Note that we need to check for non-int types above before asking for 62 // demanded bits. Normally, the only way to reach an instruction with an 63 // non-int type is via an instruction that has side effects (or otherwise 64 // will demand its input bits). However, if we have a readnone function 65 // that returns an unsized type (e.g., void), we must avoid asking for the 66 // demanded bits of the function call's return value. A void-returning 67 // readnone function is always dead (and so we can stop walking the use/def 68 // chain here), but the check is necessary to avoid asserting. 69 } 70 71 // DFS through subsequent users while tracking visits to avoid cycles. 72 while (!WorkList.empty()) { 73 Instruction *J = WorkList.pop_back_val(); 74 75 // NSW, NUW, and exact are based on operands that might have changed. 76 J->dropPoisonGeneratingFlags(); 77 78 // We do not have to worry about llvm.assume or range metadata: 79 // 1. llvm.assume demands its operand, so trivializing can't change it. 80 // 2. range metadata only applies to memory accesses which demand all bits. 81 82 for (User *KU : J->users()) { 83 // If all bits of a user are demanded, then we know that nothing below 84 // that in the def-use chain needs to be changed. 85 auto *K = dyn_cast<Instruction>(KU); 86 if (K && Visited.insert(K).second && K->getType()->isIntOrIntVectorTy() && 87 !DB.getDemandedBits(K).isAllOnes()) 88 WorkList.push_back(K); 89 } 90 } 91 } 92 93 static bool bitTrackingDCE(Function &F, DemandedBits &DB) { 94 SmallVector<Instruction*, 128> Worklist; 95 bool Changed = false; 96 for (Instruction &I : instructions(F)) { 97 // If the instruction has side effects and no non-dbg uses, 98 // skip it. This way we avoid computing known bits on an instruction 99 // that will not help us. 100 if (I.mayHaveSideEffects() && I.use_empty()) 101 continue; 102 103 // Remove instructions that are dead, either because they were not reached 104 // during analysis or have no demanded bits. 105 if (DB.isInstructionDead(&I) || 106 (I.getType()->isIntOrIntVectorTy() && DB.getDemandedBits(&I).isZero() && 107 wouldInstructionBeTriviallyDead(&I))) { 108 Worklist.push_back(&I); 109 Changed = true; 110 continue; 111 } 112 113 // Convert SExt into ZExt if none of the extension bits is required 114 if (SExtInst *SE = dyn_cast<SExtInst>(&I)) { 115 APInt Demanded = DB.getDemandedBits(SE); 116 const uint32_t SrcBitSize = SE->getSrcTy()->getScalarSizeInBits(); 117 auto *const DstTy = SE->getDestTy(); 118 const uint32_t DestBitSize = DstTy->getScalarSizeInBits(); 119 if (Demanded.countLeadingZeros() >= (DestBitSize - SrcBitSize)) { 120 clearAssumptionsOfUsers(SE, DB); 121 IRBuilder<> Builder(SE); 122 I.replaceAllUsesWith( 123 Builder.CreateZExt(SE->getOperand(0), DstTy, SE->getName())); 124 Worklist.push_back(SE); 125 Changed = true; 126 NumSExt2ZExt++; 127 continue; 128 } 129 } 130 131 for (Use &U : I.operands()) { 132 // DemandedBits only detects dead integer uses. 133 if (!U->getType()->isIntOrIntVectorTy()) 134 continue; 135 136 if (!isa<Instruction>(U) && !isa<Argument>(U)) 137 continue; 138 139 if (!DB.isUseDead(&U)) 140 continue; 141 142 LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n"); 143 144 clearAssumptionsOfUsers(&I, DB); 145 146 // FIXME: In theory we could substitute undef here instead of zero. 147 // This should be reconsidered once we settle on the semantics of 148 // undef, poison, etc. 149 U.set(ConstantInt::get(U->getType(), 0)); 150 ++NumSimplified; 151 Changed = true; 152 } 153 } 154 155 for (Instruction *&I : llvm::reverse(Worklist)) { 156 salvageDebugInfo(*I); 157 I->dropAllReferences(); 158 } 159 160 for (Instruction *&I : Worklist) { 161 ++NumRemoved; 162 I->eraseFromParent(); 163 } 164 165 return Changed; 166 } 167 168 PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) { 169 auto &DB = AM.getResult<DemandedBitsAnalysis>(F); 170 if (!bitTrackingDCE(F, DB)) 171 return PreservedAnalyses::all(); 172 173 PreservedAnalyses PA; 174 PA.preserveSet<CFGAnalyses>(); 175 return PA; 176 } 177 178 namespace { 179 struct BDCELegacyPass : public FunctionPass { 180 static char ID; // Pass identification, replacement for typeid 181 BDCELegacyPass() : FunctionPass(ID) { 182 initializeBDCELegacyPassPass(*PassRegistry::getPassRegistry()); 183 } 184 185 bool runOnFunction(Function &F) override { 186 if (skipFunction(F)) 187 return false; 188 auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits(); 189 return bitTrackingDCE(F, DB); 190 } 191 192 void getAnalysisUsage(AnalysisUsage &AU) const override { 193 AU.setPreservesCFG(); 194 AU.addRequired<DemandedBitsWrapperPass>(); 195 AU.addPreserved<GlobalsAAWrapperPass>(); 196 } 197 }; 198 } 199 200 char BDCELegacyPass::ID = 0; 201 INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce", 202 "Bit-Tracking Dead Code Elimination", false, false) 203 INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass) 204 INITIALIZE_PASS_END(BDCELegacyPass, "bdce", 205 "Bit-Tracking Dead Code Elimination", false, false) 206 207 FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); } 208