1 //===---- DemandedBits.cpp - Determine demanded bits -----------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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:
14 // %1 = add i32 %x, %y
15 // %2 = trunc i32 %1 to i16
17 // Only the lowest 16 bits of %1 are demanded; the rest are removed by the
20 //===----------------------------------------------------------------------===//
22 #include "llvm/Analysis/DemandedBits.h"
23 #include "llvm/Transforms/Scalar.h"
24 #include "llvm/ADT/DenseMap.h"
25 #include "llvm/ADT/DepthFirstIterator.h"
26 #include "llvm/ADT/SmallPtrSet.h"
27 #include "llvm/ADT/SmallVector.h"
28 #include "llvm/Analysis/AssumptionCache.h"
29 #include "llvm/Analysis/ValueTracking.h"
30 #include "llvm/IR/BasicBlock.h"
31 #include "llvm/IR/CFG.h"
32 #include "llvm/IR/DataLayout.h"
33 #include "llvm/IR/Dominators.h"
34 #include "llvm/IR/InstIterator.h"
35 #include "llvm/IR/Instructions.h"
36 #include "llvm/IR/IntrinsicInst.h"
37 #include "llvm/IR/Module.h"
38 #include "llvm/IR/Operator.h"
39 #include "llvm/Pass.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Support/raw_ostream.h"
44 #define DEBUG_TYPE "demanded-bits"
46 char DemandedBits::ID = 0;
47 INITIALIZE_PASS_BEGIN(DemandedBits, "demanded-bits", "Demanded bits analysis",
49 INITIALIZE_PASS_DEPENDENCY(AssumptionCacheTracker)
50 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
51 INITIALIZE_PASS_END(DemandedBits, "demanded-bits", "Demanded bits analysis",
54 DemandedBits::DemandedBits() : FunctionPass(ID) {
55 initializeDemandedBitsPass(*PassRegistry::getPassRegistry());
59 void DemandedBits::getAnalysisUsage(AnalysisUsage& AU) const {
61 AU.addRequired<AssumptionCacheTracker>();
62 AU.addRequired<DominatorTreeWrapperPass>();
66 static bool isAlwaysLive(Instruction *I) {
67 return isa<TerminatorInst>(I) || isa<DbgInfoIntrinsic>(I) ||
68 I->isEHPad() || I->mayHaveSideEffects();
72 DemandedBits::determineLiveOperandBits(const Instruction *UserI,
73 const Instruction *I, unsigned OperandNo,
74 const APInt &AOut, APInt &AB,
75 APInt &KnownZero, APInt &KnownOne,
76 APInt &KnownZero2, APInt &KnownOne2) {
77 unsigned BitWidth = AB.getBitWidth();
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
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,
94 KnownZero2 = APInt(BitWidth, 0);
95 KnownOne2 = APInt(BitWidth, 0);
96 computeKnownBits(const_cast<Value *>(V2), KnownZero2, KnownOne2, DL,
101 switch (UserI->getOpcode()) {
103 case Instruction::Call:
104 case Instruction::Invoke:
105 if (const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI))
106 switch (II->getIntrinsicID()) {
108 case Intrinsic::bswap:
109 // The alive bits of the input are the swapped alive bits of
111 AB = AOut.byteSwap();
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
118 ComputeKnownBits(BitWidth, I, nullptr);
119 AB = APInt::getHighBitsSet(BitWidth,
120 std::min(BitWidth, KnownOne.countLeadingZeros()+1));
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
128 ComputeKnownBits(BitWidth, I, nullptr);
129 AB = APInt::getLowBitsSet(BitWidth,
130 std::min(BitWidth, KnownOne.countTrailingZeros()+1));
135 case Instruction::Add:
136 case Instruction::Sub:
137 // Find the highest live output bit. We don't need any more input
138 // bits than that (adds, and thus subtracts, ripple only to the
140 AB = APInt::getLowBitsSet(BitWidth, AOut.getActiveBits());
142 case Instruction::Shl:
144 if (ConstantInt *CI =
145 dyn_cast<ConstantInt>(UserI->getOperand(1))) {
146 uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
147 AB = AOut.lshr(ShiftAmt);
149 // If the shift is nuw/nsw, then the high bits are not dead
150 // (because we've promised that they *must* be zero).
151 const ShlOperator *S = cast<ShlOperator>(UserI);
152 if (S->hasNoSignedWrap())
153 AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
154 else if (S->hasNoUnsignedWrap())
155 AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
158 case Instruction::LShr:
160 if (ConstantInt *CI =
161 dyn_cast<ConstantInt>(UserI->getOperand(1))) {
162 uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
163 AB = AOut.shl(ShiftAmt);
165 // If the shift is exact, then the low bits are not dead
166 // (they must be zero).
167 if (cast<LShrOperator>(UserI)->isExact())
168 AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
171 case Instruction::AShr:
173 if (ConstantInt *CI =
174 dyn_cast<ConstantInt>(UserI->getOperand(1))) {
175 uint64_t ShiftAmt = CI->getLimitedValue(BitWidth-1);
176 AB = AOut.shl(ShiftAmt);
177 // Because the high input bit is replicated into the
178 // high-order bits of the result, if we need any of those
179 // bits, then we must keep the highest input bit.
180 if ((AOut & APInt::getHighBitsSet(BitWidth, ShiftAmt))
182 AB.setBit(BitWidth-1);
184 // If the shift is exact, then the low bits are not dead
185 // (they must be zero).
186 if (cast<AShrOperator>(UserI)->isExact())
187 AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
190 case Instruction::And:
193 // For bits that are known zero, the corresponding bits in the
194 // other operand are dead (unless they're both zero, in which
195 // case they can't both be dead, so just mark the LHS bits as
197 if (OperandNo == 0) {
198 ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
201 if (!isa<Instruction>(UserI->getOperand(0)))
202 ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
203 AB &= ~(KnownZero & ~KnownZero2);
206 case Instruction::Or:
209 // For bits that are known one, the corresponding bits in the
210 // other operand are dead (unless they're both one, in which
211 // case they can't both be dead, so just mark the LHS bits as
213 if (OperandNo == 0) {
214 ComputeKnownBits(BitWidth, I, UserI->getOperand(1));
217 if (!isa<Instruction>(UserI->getOperand(0)))
218 ComputeKnownBits(BitWidth, UserI->getOperand(0), I);
219 AB &= ~(KnownOne & ~KnownOne2);
222 case Instruction::Xor:
223 case Instruction::PHI:
226 case Instruction::Trunc:
227 AB = AOut.zext(BitWidth);
229 case Instruction::ZExt:
230 AB = AOut.trunc(BitWidth);
232 case Instruction::SExt:
233 AB = AOut.trunc(BitWidth);
234 // Because the high input bit is replicated into the
235 // high-order bits of the result, if we need any of those
236 // bits, then we must keep the highest input bit.
237 if ((AOut & APInt::getHighBitsSet(AOut.getBitWidth(),
238 AOut.getBitWidth() - BitWidth))
240 AB.setBit(BitWidth-1);
242 case Instruction::Select:
249 bool DemandedBits::runOnFunction(Function& F) {
250 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
251 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
256 SmallVector<Instruction*, 128> Worklist;
258 // Collect the set of "root" instructions that are known live.
259 for (Instruction &I : instructions(F)) {
260 if (!isAlwaysLive(&I))
263 DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
264 // For integer-valued instructions, set up an initial empty set of alive
265 // bits and add the instruction to the work list. For other instructions
266 // add their operands to the work list (for integer values operands, mark
267 // all bits as live).
268 if (IntegerType *IT = dyn_cast<IntegerType>(I.getType())) {
269 if (!AliveBits.count(&I)) {
270 AliveBits[&I] = APInt(IT->getBitWidth(), 0);
271 Worklist.push_back(&I);
277 // Non-integer-typed instructions...
278 for (Use &OI : I.operands()) {
279 if (Instruction *J = dyn_cast<Instruction>(OI)) {
280 if (IntegerType *IT = dyn_cast<IntegerType>(J->getType()))
281 AliveBits[J] = APInt::getAllOnesValue(IT->getBitWidth());
282 Worklist.push_back(J);
285 // To save memory, we don't add I to the Visited set here. Instead, we
286 // check isAlwaysLive on every instruction when searching for dead
287 // instructions later (we need to check isAlwaysLive for the
288 // integer-typed instructions anyway).
291 // Propagate liveness backwards to operands.
292 while (!Worklist.empty()) {
293 Instruction *UserI = Worklist.pop_back_val();
295 DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
297 if (UserI->getType()->isIntegerTy()) {
298 AOut = AliveBits[UserI];
299 DEBUG(dbgs() << " Alive Out: " << AOut);
301 DEBUG(dbgs() << "\n");
303 if (!UserI->getType()->isIntegerTy())
304 Visited.insert(UserI);
306 APInt KnownZero, KnownOne, KnownZero2, KnownOne2;
307 // Compute the set of alive bits for each operand. These are anded into the
308 // existing set, if any, and if that changes the set of alive bits, the
309 // operand is added to the work-list.
310 for (Use &OI : UserI->operands()) {
311 if (Instruction *I = dyn_cast<Instruction>(OI)) {
312 if (IntegerType *IT = dyn_cast<IntegerType>(I->getType())) {
313 unsigned BitWidth = IT->getBitWidth();
314 APInt AB = APInt::getAllOnesValue(BitWidth);
315 if (UserI->getType()->isIntegerTy() && !AOut &&
316 !isAlwaysLive(UserI)) {
317 AB = APInt(BitWidth, 0);
319 // If all bits of the output are dead, then all bits of the input
320 // Bits of each operand that are used to compute alive bits of the
321 // output are alive, all others are dead.
322 determineLiveOperandBits(UserI, I, OI.getOperandNo(), AOut, AB,
324 KnownZero2, KnownOne2);
327 // If we've added to the set of alive bits (or the operand has not
328 // been previously visited), then re-queue the operand to be visited
330 APInt ABPrev(BitWidth, 0);
331 auto ABI = AliveBits.find(I);
332 if (ABI != AliveBits.end())
333 ABPrev = ABI->second;
335 APInt ABNew = AB | ABPrev;
336 if (ABNew != ABPrev || ABI == AliveBits.end()) {
337 AliveBits[I] = std::move(ABNew);
338 Worklist.push_back(I);
340 } else if (!Visited.count(I)) {
341 Worklist.push_back(I);
350 APInt DemandedBits::getDemandedBits(Instruction *I) {
351 const DataLayout &DL = I->getParent()->getModule()->getDataLayout();
352 if (AliveBits.count(I))
354 return APInt::getAllOnesValue(DL.getTypeSizeInBits(I->getType()));
357 bool DemandedBits::isInstructionDead(Instruction *I) {
358 return !Visited.count(I) && AliveBits.find(I) == AliveBits.end() &&
362 FunctionPass *llvm::createDemandedBitsPass() {
363 return new DemandedBits();