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