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).isAllOnesValue()) { 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).isAllOnesValue()) 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() && 107 DB.getDemandedBits(&I).isNullValue() && 108 wouldInstructionBeTriviallyDead(&I))) { 109 salvageDebugInfo(I); 110 Worklist.push_back(&I); 111 I.dropAllReferences(); 112 Changed = true; 113 continue; 114 } 115 116 // Convert SExt into ZExt if none of the extension bits is required 117 if (SExtInst *SE = dyn_cast<SExtInst>(&I)) { 118 APInt Demanded = DB.getDemandedBits(SE); 119 const uint32_t SrcBitSize = SE->getSrcTy()->getScalarSizeInBits(); 120 auto *const DstTy = SE->getDestTy(); 121 const uint32_t DestBitSize = DstTy->getScalarSizeInBits(); 122 if (Demanded.countLeadingZeros() >= (DestBitSize - SrcBitSize)) { 123 clearAssumptionsOfUsers(SE, DB); 124 IRBuilder<> Builder(SE); 125 I.replaceAllUsesWith( 126 Builder.CreateZExt(SE->getOperand(0), DstTy, SE->getName())); 127 Worklist.push_back(SE); 128 Changed = true; 129 NumSExt2ZExt++; 130 continue; 131 } 132 } 133 134 for (Use &U : I.operands()) { 135 // DemandedBits only detects dead integer uses. 136 if (!U->getType()->isIntOrIntVectorTy()) 137 continue; 138 139 if (!isa<Instruction>(U) && !isa<Argument>(U)) 140 continue; 141 142 if (!DB.isUseDead(&U)) 143 continue; 144 145 LLVM_DEBUG(dbgs() << "BDCE: Trivializing: " << U << " (all bits dead)\n"); 146 147 clearAssumptionsOfUsers(&I, DB); 148 149 // FIXME: In theory we could substitute undef here instead of zero. 150 // This should be reconsidered once we settle on the semantics of 151 // undef, poison, etc. 152 U.set(ConstantInt::get(U->getType(), 0)); 153 ++NumSimplified; 154 Changed = true; 155 } 156 } 157 158 for (Instruction *&I : Worklist) { 159 ++NumRemoved; 160 I->eraseFromParent(); 161 } 162 163 return Changed; 164 } 165 166 PreservedAnalyses BDCEPass::run(Function &F, FunctionAnalysisManager &AM) { 167 auto &DB = AM.getResult<DemandedBitsAnalysis>(F); 168 if (!bitTrackingDCE(F, DB)) 169 return PreservedAnalyses::all(); 170 171 PreservedAnalyses PA; 172 PA.preserveSet<CFGAnalyses>(); 173 PA.preserve<GlobalsAA>(); 174 return PA; 175 } 176 177 namespace { 178 struct BDCELegacyPass : public FunctionPass { 179 static char ID; // Pass identification, replacement for typeid 180 BDCELegacyPass() : FunctionPass(ID) { 181 initializeBDCELegacyPassPass(*PassRegistry::getPassRegistry()); 182 } 183 184 bool runOnFunction(Function &F) override { 185 if (skipFunction(F)) 186 return false; 187 auto &DB = getAnalysis<DemandedBitsWrapperPass>().getDemandedBits(); 188 return bitTrackingDCE(F, DB); 189 } 190 191 void getAnalysisUsage(AnalysisUsage &AU) const override { 192 AU.setPreservesCFG(); 193 AU.addRequired<DemandedBitsWrapperPass>(); 194 AU.addPreserved<GlobalsAAWrapperPass>(); 195 } 196 }; 197 } 198 199 char BDCELegacyPass::ID = 0; 200 INITIALIZE_PASS_BEGIN(BDCELegacyPass, "bdce", 201 "Bit-Tracking Dead Code Elimination", false, false) 202 INITIALIZE_PASS_DEPENDENCY(DemandedBitsWrapperPass) 203 INITIALIZE_PASS_END(BDCELegacyPass, "bdce", 204 "Bit-Tracking Dead Code Elimination", false, false) 205 206 FunctionPass *llvm::createBitTrackingDCEPass() { return new BDCELegacyPass(); } 207