1//===- DemandedBits.cpp - Determine demanded bits -------------------------===//
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 pass implements a demanded bits analysis. A demanded bit is one that
10// contributes to a result; bits that are not demanded can be either zero or
11// one without affecting control or data flow. For example in this sequence:
12//
13// %1 = add i32 %x, %y
14// %2 = trunc i32 %1 to i16
15//
16// Only the lowest 16 bits of %1 are demanded; the rest are removed by the
17// trunc.
18//
19//===----------------------------------------------------------------------===//
20
21#include "llvm/Analysis/DemandedBits.h"
22#include "llvm/ADT/APInt.h"
23#include "llvm/ADT/SetVector.h"
24#include "llvm/Analysis/AssumptionCache.h"
25#include "llvm/Analysis/ValueTracking.h"
26#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/Dominators.h"
28#include "llvm/IR/InstIterator.h"
29#include "llvm/IR/Instruction.h"
30#include "llvm/IR/IntrinsicInst.h"
31#include "llvm/IR/Module.h"
32#include "llvm/IR/Operator.h"
33#include "llvm/IR/PassManager.h"
34#include "llvm/IR/PatternMatch.h"
35#include "llvm/IR/Type.h"
36#include "llvm/IR/Use.h"
37#include "llvm/Support/Casting.h"
38#include "llvm/Support/Debug.h"
39#include "llvm/Support/KnownBits.h"
40#include "llvm/Support/raw_ostream.h"
41#include <algorithm>
42#include <cstdint>
43
44using namespace llvm;
45using namespace llvm::PatternMatch;
46
47#define DEBUG_TYPE "demanded-bits"
48
49static bool isAlwaysLive(Instruction *I) {
50 return I->isTerminator() || isa<DbgInfoIntrinsic>(Val: I) || I->isEHPad() ||
51 I->mayHaveSideEffects();
52}
53
54void DemandedBits::determineLiveOperandBits(
55 const Instruction *UserI, const Value *Val, unsigned OperandNo,
56 const APInt &AOut, APInt &AB, KnownBits &Known, KnownBits &Known2,
57 bool &KnownBitsComputed) {
58 unsigned BitWidth = AB.getBitWidth();
59
60 // We're called once per operand, but for some instructions, we need to
61 // compute known bits of both operands in order to determine the live bits of
62 // either (when both operands are instructions themselves). We don't,
63 // however, want to do this twice, so we cache the result in APInts that live
64 // in the caller. For the two-relevant-operands case, both operand values are
65 // provided here.
66 auto ComputeKnownBits =
67 [&](unsigned BitWidth, const Value *V1, const Value *V2) {
68 if (KnownBitsComputed)
69 return;
70 KnownBitsComputed = true;
71
72 const DataLayout &DL = UserI->getDataLayout();
73 Known = KnownBits(BitWidth);
74 computeKnownBits(V: V1, Known, DL, Depth: 0, AC: &AC, CxtI: UserI, DT: &DT);
75
76 if (V2) {
77 Known2 = KnownBits(BitWidth);
78 computeKnownBits(V: V2, Known&: Known2, DL, Depth: 0, AC: &AC, CxtI: UserI, DT: &DT);
79 }
80 };
81
82 switch (UserI->getOpcode()) {
83 default: break;
84 case Instruction::Call:
85 case Instruction::Invoke:
86 if (const auto *II = dyn_cast<IntrinsicInst>(Val: UserI)) {
87 switch (II->getIntrinsicID()) {
88 default: break;
89 case Intrinsic::bswap:
90 // The alive bits of the input are the swapped alive bits of
91 // the output.
92 AB = AOut.byteSwap();
93 break;
94 case Intrinsic::bitreverse:
95 // The alive bits of the input are the reversed alive bits of
96 // the output.
97 AB = AOut.reverseBits();
98 break;
99 case Intrinsic::ctlz:
100 if (OperandNo == 0) {
101 // We need some output bits, so we need all bits of the
102 // input to the left of, and including, the leftmost bit
103 // known to be one.
104 ComputeKnownBits(BitWidth, Val, nullptr);
105 AB = APInt::getHighBitsSet(numBits: BitWidth,
106 hiBitsSet: std::min(a: BitWidth, b: Known.countMaxLeadingZeros()+1));
107 }
108 break;
109 case Intrinsic::cttz:
110 if (OperandNo == 0) {
111 // We need some output bits, so we need all bits of the
112 // input to the right of, and including, the rightmost bit
113 // known to be one.
114 ComputeKnownBits(BitWidth, Val, nullptr);
115 AB = APInt::getLowBitsSet(numBits: BitWidth,
116 loBitsSet: std::min(a: BitWidth, b: Known.countMaxTrailingZeros()+1));
117 }
118 break;
119 case Intrinsic::fshl:
120 case Intrinsic::fshr: {
121 const APInt *SA;
122 if (OperandNo == 2) {
123 // Shift amount is modulo the bitwidth. For powers of two we have
124 // SA % BW == SA & (BW - 1).
125 if (isPowerOf2_32(Value: BitWidth))
126 AB = BitWidth - 1;
127 } else if (match(V: II->getOperand(i_nocapture: 2), P: m_APInt(Res&: SA))) {
128 // Normalize to funnel shift left. APInt shifts of BitWidth are well-
129 // defined, so no need to special-case zero shifts here.
130 uint64_t ShiftAmt = SA->urem(RHS: BitWidth);
131 if (II->getIntrinsicID() == Intrinsic::fshr)
132 ShiftAmt = BitWidth - ShiftAmt;
133
134 if (OperandNo == 0)
135 AB = AOut.lshr(shiftAmt: ShiftAmt);
136 else if (OperandNo == 1)
137 AB = AOut.shl(shiftAmt: BitWidth - ShiftAmt);
138 }
139 break;
140 }
141 case Intrinsic::umax:
142 case Intrinsic::umin:
143 case Intrinsic::smax:
144 case Intrinsic::smin:
145 // If low bits of result are not demanded, they are also not demanded
146 // for the min/max operands.
147 AB = APInt::getBitsSetFrom(numBits: BitWidth, loBit: AOut.countr_zero());
148 break;
149 }
150 }
151 break;
152 case Instruction::Add:
153 if (AOut.isMask()) {
154 AB = AOut;
155 } else {
156 ComputeKnownBits(BitWidth, UserI->getOperand(i: 0), UserI->getOperand(i: 1));
157 AB = determineLiveOperandBitsAdd(OperandNo, AOut, LHS: Known, RHS: Known2);
158 }
159 break;
160 case Instruction::Sub:
161 if (AOut.isMask()) {
162 AB = AOut;
163 } else {
164 ComputeKnownBits(BitWidth, UserI->getOperand(i: 0), UserI->getOperand(i: 1));
165 AB = determineLiveOperandBitsSub(OperandNo, AOut, LHS: Known, RHS: Known2);
166 }
167 break;
168 case Instruction::Mul:
169 // Find the highest live output bit. We don't need any more input
170 // bits than that (adds, and thus subtracts, ripple only to the
171 // left).
172 AB = APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: AOut.getActiveBits());
173 break;
174 case Instruction::Shl:
175 if (OperandNo == 0) {
176 const APInt *ShiftAmtC;
177 if (match(V: UserI->getOperand(i: 1), P: m_APInt(Res&: ShiftAmtC))) {
178 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(Limit: BitWidth - 1);
179 AB = AOut.lshr(shiftAmt: ShiftAmt);
180
181 // If the shift is nuw/nsw, then the high bits are not dead
182 // (because we've promised that they *must* be zero).
183 const auto *S = cast<ShlOperator>(Val: UserI);
184 if (S->hasNoSignedWrap())
185 AB |= APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ShiftAmt+1);
186 else if (S->hasNoUnsignedWrap())
187 AB |= APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ShiftAmt);
188 }
189 }
190 break;
191 case Instruction::LShr:
192 if (OperandNo == 0) {
193 const APInt *ShiftAmtC;
194 if (match(V: UserI->getOperand(i: 1), P: m_APInt(Res&: ShiftAmtC))) {
195 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(Limit: BitWidth - 1);
196 AB = AOut.shl(shiftAmt: ShiftAmt);
197
198 // If the shift is exact, then the low bits are not dead
199 // (they must be zero).
200 if (cast<LShrOperator>(Val: UserI)->isExact())
201 AB |= APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: ShiftAmt);
202 }
203 }
204 break;
205 case Instruction::AShr:
206 if (OperandNo == 0) {
207 const APInt *ShiftAmtC;
208 if (match(V: UserI->getOperand(i: 1), P: m_APInt(Res&: ShiftAmtC))) {
209 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(Limit: BitWidth - 1);
210 AB = AOut.shl(shiftAmt: ShiftAmt);
211 // Because the high input bit is replicated into the
212 // high-order bits of the result, if we need any of those
213 // bits, then we must keep the highest input bit.
214 if ((AOut & APInt::getHighBitsSet(numBits: BitWidth, hiBitsSet: ShiftAmt))
215 .getBoolValue())
216 AB.setSignBit();
217
218 // If the shift is exact, then the low bits are not dead
219 // (they must be zero).
220 if (cast<AShrOperator>(Val: UserI)->isExact())
221 AB |= APInt::getLowBitsSet(numBits: BitWidth, loBitsSet: ShiftAmt);
222 }
223 }
224 break;
225 case Instruction::And:
226 AB = AOut;
227
228 // For bits that are known zero, the corresponding bits in the
229 // other operand are dead (unless they're both zero, in which
230 // case they can't both be dead, so just mark the LHS bits as
231 // dead).
232 ComputeKnownBits(BitWidth, UserI->getOperand(i: 0), UserI->getOperand(i: 1));
233 if (OperandNo == 0)
234 AB &= ~Known2.Zero;
235 else
236 AB &= ~(Known.Zero & ~Known2.Zero);
237 break;
238 case Instruction::Or:
239 AB = AOut;
240
241 // For bits that are known one, the corresponding bits in the
242 // other operand are dead (unless they're both one, in which
243 // case they can't both be dead, so just mark the LHS bits as
244 // dead).
245 ComputeKnownBits(BitWidth, UserI->getOperand(i: 0), UserI->getOperand(i: 1));
246 if (OperandNo == 0)
247 AB &= ~Known2.One;
248 else
249 AB &= ~(Known.One & ~Known2.One);
250 break;
251 case Instruction::Xor:
252 case Instruction::PHI:
253 AB = AOut;
254 break;
255 case Instruction::Trunc:
256 AB = AOut.zext(width: BitWidth);
257 break;
258 case Instruction::ZExt:
259 AB = AOut.trunc(width: BitWidth);
260 break;
261 case Instruction::SExt:
262 AB = AOut.trunc(width: BitWidth);
263 // Because the high input bit is replicated into the
264 // high-order bits of the result, if we need any of those
265 // bits, then we must keep the highest input bit.
266 if ((AOut & APInt::getHighBitsSet(numBits: AOut.getBitWidth(),
267 hiBitsSet: AOut.getBitWidth() - BitWidth))
268 .getBoolValue())
269 AB.setSignBit();
270 break;
271 case Instruction::Select:
272 if (OperandNo != 0)
273 AB = AOut;
274 break;
275 case Instruction::ExtractElement:
276 if (OperandNo == 0)
277 AB = AOut;
278 break;
279 case Instruction::InsertElement:
280 case Instruction::ShuffleVector:
281 if (OperandNo == 0 || OperandNo == 1)
282 AB = AOut;
283 break;
284 }
285}
286
287void DemandedBits::performAnalysis() {
288 if (Analyzed)
289 // Analysis already completed for this function.
290 return;
291 Analyzed = true;
292
293 Visited.clear();
294 AliveBits.clear();
295 DeadUses.clear();
296
297 SmallSetVector<Instruction*, 16> Worklist;
298
299 // Collect the set of "root" instructions that are known live.
300 for (Instruction &I : instructions(F)) {
301 if (!isAlwaysLive(I: &I))
302 continue;
303
304 LLVM_DEBUG(dbgs() << "DemandedBits: Root: " << I << "\n");
305 // For integer-valued instructions, set up an initial empty set of alive
306 // bits and add the instruction to the work list. For other instructions
307 // add their operands to the work list (for integer values operands, mark
308 // all bits as live).
309 Type *T = I.getType();
310 if (T->isIntOrIntVectorTy()) {
311 if (AliveBits.try_emplace(Key: &I, Args: T->getScalarSizeInBits(), Args: 0).second)
312 Worklist.insert(X: &I);
313
314 continue;
315 }
316
317 // Non-integer-typed instructions...
318 for (Use &OI : I.operands()) {
319 if (auto *J = dyn_cast<Instruction>(Val&: OI)) {
320 Type *T = J->getType();
321 if (T->isIntOrIntVectorTy())
322 AliveBits[J] = APInt::getAllOnes(numBits: T->getScalarSizeInBits());
323 else
324 Visited.insert(Ptr: J);
325 Worklist.insert(X: J);
326 }
327 }
328 // To save memory, we don't add I to the Visited set here. Instead, we
329 // check isAlwaysLive on every instruction when searching for dead
330 // instructions later (we need to check isAlwaysLive for the
331 // integer-typed instructions anyway).
332 }
333
334 // Propagate liveness backwards to operands.
335 while (!Worklist.empty()) {
336 Instruction *UserI = Worklist.pop_back_val();
337
338 LLVM_DEBUG(dbgs() << "DemandedBits: Visiting: " << *UserI);
339 APInt AOut;
340 bool InputIsKnownDead = false;
341 if (UserI->getType()->isIntOrIntVectorTy()) {
342 AOut = AliveBits[UserI];
343 LLVM_DEBUG(dbgs() << " Alive Out: 0x"
344 << Twine::utohexstr(AOut.getLimitedValue()));
345
346 // If all bits of the output are dead, then all bits of the input
347 // are also dead.
348 InputIsKnownDead = !AOut && !isAlwaysLive(I: UserI);
349 }
350 LLVM_DEBUG(dbgs() << "\n");
351
352 KnownBits Known, Known2;
353 bool KnownBitsComputed = false;
354 // Compute the set of alive bits for each operand. These are anded into the
355 // existing set, if any, and if that changes the set of alive bits, the
356 // operand is added to the work-list.
357 for (Use &OI : UserI->operands()) {
358 // We also want to detect dead uses of arguments, but will only store
359 // demanded bits for instructions.
360 auto *I = dyn_cast<Instruction>(Val&: OI);
361 if (!I && !isa<Argument>(Val: OI))
362 continue;
363
364 Type *T = OI->getType();
365 if (T->isIntOrIntVectorTy()) {
366 unsigned BitWidth = T->getScalarSizeInBits();
367 APInt AB = APInt::getAllOnes(numBits: BitWidth);
368 if (InputIsKnownDead) {
369 AB = APInt(BitWidth, 0);
370 } else {
371 // Bits of each operand that are used to compute alive bits of the
372 // output are alive, all others are dead.
373 determineLiveOperandBits(UserI, Val: OI, OperandNo: OI.getOperandNo(), AOut, AB,
374 Known, Known2, KnownBitsComputed);
375
376 // Keep track of uses which have no demanded bits.
377 if (AB.isZero())
378 DeadUses.insert(Ptr: &OI);
379 else
380 DeadUses.erase(Ptr: &OI);
381 }
382
383 if (I) {
384 // If we've added to the set of alive bits (or the operand has not
385 // been previously visited), then re-queue the operand to be visited
386 // again.
387 auto Res = AliveBits.try_emplace(Key: I);
388 if (Res.second || (AB |= Res.first->second) != Res.first->second) {
389 Res.first->second = std::move(AB);
390 Worklist.insert(X: I);
391 }
392 }
393 } else if (I && Visited.insert(Ptr: I).second) {
394 Worklist.insert(X: I);
395 }
396 }
397 }
398}
399
400APInt DemandedBits::getDemandedBits(Instruction *I) {
401 performAnalysis();
402
403 auto Found = AliveBits.find(Val: I);
404 if (Found != AliveBits.end())
405 return Found->second;
406
407 const DataLayout &DL = I->getDataLayout();
408 return APInt::getAllOnes(numBits: DL.getTypeSizeInBits(Ty: I->getType()->getScalarType()));
409}
410
411APInt DemandedBits::getDemandedBits(Use *U) {
412 Type *T = (*U)->getType();
413 auto *UserI = cast<Instruction>(Val: U->getUser());
414 const DataLayout &DL = UserI->getDataLayout();
415 unsigned BitWidth = DL.getTypeSizeInBits(Ty: T->getScalarType());
416
417 // We only track integer uses, everything else produces a mask with all bits
418 // set
419 if (!T->isIntOrIntVectorTy())
420 return APInt::getAllOnes(numBits: BitWidth);
421
422 if (isUseDead(U))
423 return APInt(BitWidth, 0);
424
425 performAnalysis();
426
427 APInt AOut = getDemandedBits(I: UserI);
428 APInt AB = APInt::getAllOnes(numBits: BitWidth);
429 KnownBits Known, Known2;
430 bool KnownBitsComputed = false;
431
432 determineLiveOperandBits(UserI, Val: *U, OperandNo: U->getOperandNo(), AOut, AB, Known,
433 Known2, KnownBitsComputed);
434
435 return AB;
436}
437
438bool DemandedBits::isInstructionDead(Instruction *I) {
439 performAnalysis();
440
441 return !Visited.count(Ptr: I) && !AliveBits.contains(Val: I) && !isAlwaysLive(I);
442}
443
444bool DemandedBits::isUseDead(Use *U) {
445 // We only track integer uses, everything else is assumed live.
446 if (!(*U)->getType()->isIntOrIntVectorTy())
447 return false;
448
449 // Uses by always-live instructions are never dead.
450 auto *UserI = cast<Instruction>(Val: U->getUser());
451 if (isAlwaysLive(I: UserI))
452 return false;
453
454 performAnalysis();
455 if (DeadUses.count(Ptr: U))
456 return true;
457
458 // If no output bits are demanded, no input bits are demanded and the use
459 // is dead. These uses might not be explicitly present in the DeadUses map.
460 if (UserI->getType()->isIntOrIntVectorTy()) {
461 auto Found = AliveBits.find(Val: UserI);
462 if (Found != AliveBits.end() && Found->second.isZero())
463 return true;
464 }
465
466 return false;
467}
468
469void DemandedBits::print(raw_ostream &OS) {
470 auto PrintDB = [&](const Instruction *I, const APInt &A, Value *V = nullptr) {
471 OS << "DemandedBits: 0x" << Twine::utohexstr(Val: A.getLimitedValue())
472 << " for ";
473 if (V) {
474 V->printAsOperand(O&: OS, PrintType: false);
475 OS << " in ";
476 }
477 OS << *I << '\n';
478 };
479
480 OS << "Printing analysis 'Demanded Bits Analysis' for function '" << F.getName() << "':\n";
481 performAnalysis();
482 for (auto &KV : AliveBits) {
483 Instruction *I = KV.first;
484 PrintDB(I, KV.second);
485
486 for (Use &OI : I->operands()) {
487 PrintDB(I, getDemandedBits(U: &OI), OI);
488 }
489 }
490}
491
492static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo,
493 const APInt &AOut,
494 const KnownBits &LHS,
495 const KnownBits &RHS,
496 bool CarryZero, bool CarryOne) {
497 assert(!(CarryZero && CarryOne) &&
498 "Carry can't be zero and one at the same time");
499
500 // The following check should be done by the caller, as it also indicates
501 // that LHS and RHS don't need to be computed.
502 //
503 // if (AOut.isMask())
504 // return AOut;
505
506 // Boundary bits' carry out is unaffected by their carry in.
507 APInt Bound = (LHS.Zero & RHS.Zero) | (LHS.One & RHS.One);
508
509 // First, the alive carry bits are determined from the alive output bits:
510 // Let demand ripple to the right but only up to any set bit in Bound.
511 // AOut = -1----
512 // Bound = ----1-
513 // ACarry&~AOut = --111-
514 APInt RBound = Bound.reverseBits();
515 APInt RAOut = AOut.reverseBits();
516 APInt RProp = RAOut + (RAOut | ~RBound);
517 APInt RACarry = RProp ^ ~RBound;
518 APInt ACarry = RACarry.reverseBits();
519
520 // Then, the alive input bits are determined from the alive carry bits:
521 APInt NeededToMaintainCarryZero;
522 APInt NeededToMaintainCarryOne;
523 if (OperandNo == 0) {
524 NeededToMaintainCarryZero = LHS.Zero | ~RHS.Zero;
525 NeededToMaintainCarryOne = LHS.One | ~RHS.One;
526 } else {
527 NeededToMaintainCarryZero = RHS.Zero | ~LHS.Zero;
528 NeededToMaintainCarryOne = RHS.One | ~LHS.One;
529 }
530
531 // As in computeForAddCarry
532 APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;
533 APInt PossibleSumOne = LHS.One + RHS.One + CarryOne;
534
535 // The below is simplified from
536 //
537 // APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
538 // APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
539 // APInt CarryUnknown = ~(CarryKnownZero | CarryKnownOne);
540 //
541 // APInt NeededToMaintainCarry =
542 // (CarryKnownZero & NeededToMaintainCarryZero) |
543 // (CarryKnownOne & NeededToMaintainCarryOne) |
544 // CarryUnknown;
545
546 APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &
547 (PossibleSumOne | NeededToMaintainCarryOne);
548
549 APInt AB = AOut | (ACarry & NeededToMaintainCarry);
550 return AB;
551}
552
553APInt DemandedBits::determineLiveOperandBitsAdd(unsigned OperandNo,
554 const APInt &AOut,
555 const KnownBits &LHS,
556 const KnownBits &RHS) {
557 return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS, CarryZero: true,
558 CarryOne: false);
559}
560
561APInt DemandedBits::determineLiveOperandBitsSub(unsigned OperandNo,
562 const APInt &AOut,
563 const KnownBits &LHS,
564 const KnownBits &RHS) {
565 KnownBits NRHS;
566 NRHS.Zero = RHS.One;
567 NRHS.One = RHS.Zero;
568 return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS: NRHS, CarryZero: false,
569 CarryOne: true);
570}
571
572AnalysisKey DemandedBitsAnalysis::Key;
573
574DemandedBits DemandedBitsAnalysis::run(Function &F,
575 FunctionAnalysisManager &AM) {
576 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
577 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
578 return DemandedBits(F, AC, DT);
579}
580
581PreservedAnalyses DemandedBitsPrinterPass::run(Function &F,
582 FunctionAnalysisManager &AM) {
583 AM.getResult<DemandedBitsAnalysis>(IR&: F).print(OS);
584 return PreservedAnalyses::all();
585}
586