1 //===---- DemandedBits.cpp - Determine demanded bits ----------------------===// 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 pass implements a demanded bits analysis. A demanded bit is one that 11 // contributes to a result; bits that are not demanded can be either zero or 12 // one without affecting control or data flow. For example in this sequence: 13 // 14 // %1 = add i32 %x, %y 15 // %2 = trunc i32 %1 to i16 16 // 17 // Only the lowest 16 bits of %1 are demanded; the rest are removed by the 18 // trunc. 19 // 20 //===----------------------------------------------------------------------===// 21 22 #include "llvm/Analysis/DemandedBits.h" 23 #include "llvm/ADT/DepthFirstIterator.h" 24 #include "llvm/ADT/SmallPtrSet.h" 25 #include "llvm/ADT/SmallVector.h" 26 #include "llvm/ADT/StringExtras.h" 27 #include "llvm/Analysis/AssumptionCache.h" 28 #include "llvm/Analysis/ValueTracking.h" 29 #include "llvm/IR/BasicBlock.h" 30 #include "llvm/IR/CFG.h" 31 #include "llvm/IR/DataLayout.h" 32 #include "llvm/IR/Dominators.h" 33 #include "llvm/IR/InstIterator.h" 34 #include "llvm/IR/Instructions.h" 35 #include "llvm/IR/IntrinsicInst.h" 36 #include "llvm/IR/Module.h" 37 #include "llvm/IR/Operator.h" 38 #include "llvm/Pass.h" 39 #include "llvm/Support/Debug.h" 40 #include "llvm/Support/raw_ostream.h" 41 using namespace llvm; 42 43 #define DEBUG_TYPE "demanded-bits" 44 45 char DemandedBitsWrapperPass::ID = 0; 46 INITIALIZE_PASS_BEGIN(DemandedBitsWrapperPass, "demanded-bits", 47 "Demanded bits analysis", false, false) 48 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker) 49 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 50 INITIALIZE_PASS_END(DemandedBitsWrapperPass, "demanded-bits", 51 "Demanded bits analysis", false, false) 52 53 DemandedBitsWrapperPass::DemandedBitsWrapperPass() : FunctionPass(ID) { 54 initializeDemandedBitsWrapperPassPass(*PassRegistry::getPassRegistry()); 55 } 56 57 void DemandedBitsWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { 58 AU.setPreservesCFG(); 59 AU.addRequired<AssumptionCacheTracker>(); 60 AU.addRequired<DominatorTreeWrapperPass>(); 61 AU.setPreservesAll(); 62 } 63 64 void DemandedBitsWrapperPass::print(raw_ostream &OS, const Module *M) const { 65 DB->print(OS); 66 } 67 68 static bool isAlwaysLive(Instruction *I) { 69 return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) || 70 I->isEHPad() || I->mayHaveSideEffects(); 71 } 72 73 void DemandedBits::determineLiveOperandBits( 74 const Instruction *UserI, const Instruction *I, unsigned OperandNo, 75 const APInt &AOut, APInt &AB, APInt &KnownZero, APInt &KnownOne, 76 APInt &KnownZero2, APInt &KnownOne2) { 77 unsigned BitWidth = AB.getBitWidth(); 78 79 // We're called once per operand, but for some instructions, we need to 80 // compute known bits of both operands in order to determine the live bits of 81 // either (when both operands are instructions themselves). We don't, 82 // however, want to do this twice, so we cache the result in APInts that live 83 // in the caller. For the two-relevant-operands case, both operand values are 84 // provided here. 85 auto ComputeKnownBits = 86 [&](unsigned BitWidth, const Value *V1, const Value *V2) { 87 const DataLayout &DL = I->getModule()->getDataLayout(); 88 KnownZero = APInt(BitWidth, 0); 89 KnownOne = APInt(BitWidth, 0); 90 computeKnownBits(const_cast<Value *>(V1), KnownZero, KnownOne, DL, 0, 91 &AC, UserI, &DT); 92 93 if (V2) { 94 KnownZero2 = APInt(BitWidth, 0); 95 KnownOne2 = APInt(BitWidth, 0); 96 computeKnownBits(const_cast<Value *>(V2), KnownZero2, KnownOne2, DL, 97 0, &AC, UserI, &DT); 98 } 99 }; 100 101 switch (UserI->getOpcode()) { 102 default: break; 103 case Instruction::Call: 104 case Instruction::Invoke: 105 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI)) 106 switch (II->getIntrinsicID()) { 107 default: break; 108 case Intrinsic::bswap: 109 // The alive bits of the input are the swapped alive bits of 110 // the output. 111 AB = AOut.byteSwap(); 112 break; 113 case Intrinsic::ctlz: 114 if (OperandNo == 0) { 115 // We need some output bits, so we need all bits of the 116 // input to the left of, and including, the leftmost bit 117 // known to be one. 118 ComputeKnownBits(BitWidth, I, nullptr); 119 AB = APInt::getHighBitsSet(BitWidth, 120 std::min(BitWidth, KnownOne.countLeadingZeros()+1)); 121 } 122 break; 123 case Intrinsic::cttz: 124 if (OperandNo == 0) { 125 // We need some output bits, so we need all bits of the 126 // input to the right of, and including, the rightmost bit 127 // known to be one. 128 ComputeKnownBits(BitWidth, I, nullptr); 129 AB = APInt::getLowBitsSet(BitWidth, 130 std::min(BitWidth, KnownOne.countTrailingZeros()+1)); 131 } 132 break; 133 } 134 break; 135 case Instruction::Add: 136 case Instruction::Sub: 137 case Instruction::Mul: 138 // Find the highest live output bit. We don't need any more input 139 // bits than that (adds, and thus subtracts, ripple only to the 140 // left). 141 AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits()); 142 break; 143 case Instruction::Shl: 144 if (OperandNo == 0) 145 if (ConstantInt *CI = 146 dyn_cast<ConstantInt>(UserI->getOperand(1))) { 147 uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1); 148 AB = AOut.lshr(ShiftAmt); 149 150 // If the shift is nuw/nsw, then the high bits are not dead 151 // (because we've promised that they *must* be zero). 152 const ShlOperator *S = cast<ShlOperator>(UserI); 153 if (S->hasNoSignedWrap()) 154 AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1); 155 else if (S->hasNoUnsignedWrap()) 156 AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt); 157 } 158 break; 159 case Instruction::LShr: 160 if (OperandNo == 0) 161 if (ConstantInt *CI = 162 dyn_cast<ConstantInt>(UserI->getOperand(1))) { 163 uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1); 164 AB = AOut.shl(ShiftAmt); 165 166 // If the shift is exact, then the low bits are not dead 167 // (they must be zero). 168 if (cast<LShrOperator>(UserI)->isExact()) 169 AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 170 } 171 break; 172 case Instruction::AShr: 173 if (OperandNo == 0) 174 if (ConstantInt *CI = 175 dyn_cast<ConstantInt>(UserI->getOperand(1))) { 176 uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1); 177 AB = AOut.shl(ShiftAmt); 178 // Because the high input bit is replicated into the 179 // high-order bits of the result, if we need any of those 180 // bits, then we must keep the highest input bit. 181 if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt)) 182 .getBoolValue()) 183 AB.setBit(BitWidth-1); 184 185 // If the shift is exact, then the low bits are not dead 186 // (they must be zero). 187 if (cast<AShrOperator>(UserI)->isExact()) 188 AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt); 189 } 190 break; 191 case Instruction::And: 192 AB = AOut; 193 194 // For bits that are known zero, the corresponding bits in the 195 // other operand are dead (unless they're both zero, in which 196 // case they can't both be dead, so just mark the LHS bits as 197 // dead). 198 if (OperandNo == 0) { 199 ComputeKnownBits(BitWidth, I, UserI->getOperand(1)); 200 AB &= ~KnownZero2; 201 } else { 202 if (!isa<Instruction>(UserI->getOperand(0))) 203 ComputeKnownBits(BitWidth, UserI->getOperand(0), I); 204 AB &= ~(KnownZero & ~KnownZero2); 205 } 206 break; 207 case Instruction::Or: 208 AB = AOut; 209 210 // For bits that are known one, the corresponding bits in the 211 // other operand are dead (unless they're both one, in which 212 // case they can't both be dead, so just mark the LHS bits as 213 // dead). 214 if (OperandNo == 0) { 215 ComputeKnownBits(BitWidth, I, UserI->getOperand(1)); 216 AB &= ~KnownOne2; 217 } else { 218 if (!isa<Instruction>(UserI->getOperand(0))) 219 ComputeKnownBits(BitWidth, UserI->getOperand(0), I); 220 AB &= ~(KnownOne & ~KnownOne2); 221 } 222 break; 223 case Instruction::Xor: 224 case Instruction::PHI: 225 AB = AOut; 226 break; 227 case Instruction::Trunc: 228 AB = AOut.zext(BitWidth); 229 break; 230 case Instruction::ZExt: 231 AB = AOut.trunc(BitWidth); 232 break; 233 case Instruction::SExt: 234 AB = AOut.trunc(BitWidth); 235 // Because the high input bit is replicated into the 236 // high-order bits of the result, if we need any of those 237 // bits, then we must keep the highest input bit. 238 if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(), 239 AOut.getBitWidth() - BitWidth)) 240 .getBoolValue()) 241 AB.setBit(BitWidth-1); 242 break; 243 case Instruction::Select: 244 if (OperandNo != 0) 245 AB = AOut; 246 break; 247 } 248 } 249 250 bool DemandedBitsWrapperPass::runOnFunction(Function &F) { 251 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F); 252 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 253 DB.emplace(F, AC, DT); 254 return false; 255 } 256 257 void DemandedBitsWrapperPass::releaseMemory() { 258 DB.reset(); 259 } 260 261 void DemandedBits::performAnalysis() { 262 if (Analyzed) 263 // Analysis already completed for this function. 264 return; 265 Analyzed = true; 266 267 Visited.clear(); 268 AliveBits.clear(); 269 270 SmallVector<Instruction*, 128> Worklist; 271 272 // Collect the set of "root" instructions that are known live. 273 for (Instruction &I : instructions(F)) { 274 if (!isAlwaysLive(&I)) 275 continue; 276 277 DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n"); 278 // For integer-valued instructions, set up an initial empty set of alive 279 // bits and add the instruction to the work list. For other instructions 280 // add their operands to the work list (for integer values operands, mark 281 // all bits as live). 282 if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) { 283 if (!AliveBits.count(&I)) { 284 AliveBits[&I] = APInt(IT->getBitWidth(), 0); 285 Worklist.push_back(&I); 286 } 287 288 continue; 289 } 290 291 // Non-integer-typed instructions... 292 for (Use &OI : I.operands()) { 293 if (Instruction *J = dyn_cast<Instruction>(OI)) { 294 if (IntegerType *IT = dyn_cast<IntegerType>(J->getType())) 295 AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth()); 296 Worklist.push_back(J); 297 } 298 } 299 // To save memory, we don't add I to the Visited set here. Instead, we 300 // check isAlwaysLive on every instruction when searching for dead 301 // instructions later (we need to check isAlwaysLive for the 302 // integer-typed instructions anyway). 303 } 304 305 // Propagate liveness backwards to operands. 306 while (!Worklist.empty()) { 307 Instruction *UserI = Worklist.pop_back_val(); 308 309 DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI); 310 APInt AOut; 311 if (UserI->getType()->isIntegerTy()) { 312 AOut = AliveBits[UserI]; 313 DEBUG(dbgs() << " Alive Out: " << AOut); 314 } 315 DEBUG(dbgs() << "\n"); 316 317 if (!UserI->getType()->isIntegerTy()) 318 Visited.insert(UserI); 319 320 APInt KnownZero, KnownOne, KnownZero2, KnownOne2; 321 // Compute the set of alive bits for each operand. These are anded into the 322 // existing set, if any, and if that changes the set of alive bits, the 323 // operand is added to the work-list. 324 for (Use &OI : UserI->operands()) { 325 if (Instruction *I = dyn_cast<Instruction>(OI)) { 326 if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) { 327 unsigned BitWidth = IT->getBitWidth(); 328 APInt AB = APInt::getAllOnesValue(BitWidth); 329 if (UserI->getType()->isIntegerTy() && !AOut && 330 !isAlwaysLive(UserI)) { 331 AB = APInt(BitWidth, 0); 332 } else { 333 // If all bits of the output are dead, then all bits of the input 334 // Bits of each operand that are used to compute alive bits of the 335 // output are alive, all others are dead. 336 determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB, 337 KnownZero, KnownOne, 338 KnownZero2, KnownOne2); 339 } 340 341 // If we've added to the set of alive bits (or the operand has not 342 // been previously visited), then re-queue the operand to be visited 343 // again. 344 APInt ABPrev(BitWidth, 0); 345 auto ABI = AliveBits.find(I); 346 if (ABI != AliveBits.end()) 347 ABPrev = ABI->second; 348 349 APInt ABNew = AB | ABPrev; 350 if (ABNew != ABPrev || ABI == AliveBits.end()) { 351 AliveBits[I] = std::move(ABNew); 352 Worklist.push_back(I); 353 } 354 } else if (!Visited.count(I)) { 355 Worklist.push_back(I); 356 } 357 } 358 } 359 } 360 } 361 362 APInt DemandedBits::getDemandedBits(Instruction *I) { 363 performAnalysis(); 364 365 const DataLayout &DL = I->getParent()->getModule()->getDataLayout(); 366 if (AliveBits.count(I)) 367 return AliveBits[I]; 368 return APInt::getAllOnesValue(DL.getTypeSizeInBits(I->getType())); 369 } 370 371 bool DemandedBits::isInstructionDead(Instruction *I) { 372 performAnalysis(); 373 374 return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() && 375 !isAlwaysLive(I); 376 } 377 378 void DemandedBits::print(raw_ostream &OS) { 379 performAnalysis(); 380 for (auto &KV : AliveBits) { 381 OS << "DemandedBits: 0x" << utohexstr(KV.second.getLimitedValue()) << " for " 382 << *KV.first << "\n"; 383 } 384 } 385 386 FunctionPass *llvm::createDemandedBitsWrapperPass() { 387 return new DemandedBitsWrapperPass(); 388 } 389 390 char DemandedBitsAnalysis::PassID; 391 392 DemandedBits DemandedBitsAnalysis::run(Function &F, 393 AnalysisManager<Function> &AM) { 394 auto &AC = AM.getResult<AssumptionAnalysis>(F); 395 auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 396 return DemandedBits(F, AC, DT); 397 } 398 399 PreservedAnalyses DemandedBitsPrinterPass::run(Function &F, 400 FunctionAnalysisManager &AM) { 401 AM.getResult<DemandedBitsAnalysis>(F).print(OS); 402 return PreservedAnalyses::all(); 403 } 404