LLVM 19.0.0git
DemandedBits.cpp
Go to the documentation of this file.
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
22#include "llvm/ADT/APInt.h"
23#include "llvm/ADT/SetVector.h"
26#include "llvm/IR/DataLayout.h"
27#include "llvm/IR/Dominators.h"
29#include "llvm/IR/Instruction.h"
31#include "llvm/IR/Module.h"
32#include "llvm/IR/Operator.h"
33#include "llvm/IR/PassManager.h"
35#include "llvm/IR/Type.h"
36#include "llvm/IR/Use.h"
38#include "llvm/Support/Debug.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>(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->getModule()->getDataLayout();
73 Known = KnownBits(BitWidth);
74 computeKnownBits(V1, Known, DL, 0, &AC, UserI, &DT);
75
76 if (V2) {
77 Known2 = KnownBits(BitWidth);
78 computeKnownBits(V2, Known2, DL, 0, &AC, UserI, &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>(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);
106 std::min(BitWidth, 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);
116 std::min(BitWidth, 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).
126 AB = BitWidth - 1;
127 } else if (match(II->getOperand(2), m_APInt(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(BitWidth);
131 if (II->getIntrinsicID() == Intrinsic::fshr)
132 ShiftAmt = BitWidth - ShiftAmt;
133
134 if (OperandNo == 0)
135 AB = AOut.lshr(ShiftAmt);
136 else if (OperandNo == 1)
137 AB = AOut.shl(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.
148 break;
149 }
150 }
151 break;
152 case Instruction::Add:
153 if (AOut.isMask()) {
154 AB = AOut;
155 } else {
156 ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
157 AB = determineLiveOperandBitsAdd(OperandNo, AOut, Known, Known2);
158 }
159 break;
160 case Instruction::Sub:
161 if (AOut.isMask()) {
162 AB = AOut;
163 } else {
164 ComputeKnownBits(BitWidth, UserI->getOperand(0), UserI->getOperand(1));
165 AB = determineLiveOperandBitsSub(OperandNo, AOut, Known, 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).
173 break;
174 case Instruction::Shl:
175 if (OperandNo == 0) {
176 const APInt *ShiftAmtC;
177 if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
178 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
179 AB = AOut.lshr(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>(UserI);
184 if (S->hasNoSignedWrap())
185 AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt+1);
186 else if (S->hasNoUnsignedWrap())
187 AB |= APInt::getHighBitsSet(BitWidth, ShiftAmt);
188 }
189 }
190 break;
191 case Instruction::LShr:
192 if (OperandNo == 0) {
193 const APInt *ShiftAmtC;
194 if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
195 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
196 AB = AOut.shl(ShiftAmt);
197
198 // If the shift is exact, then the low bits are not dead
199 // (they must be zero).
200 if (cast<LShrOperator>(UserI)->isExact())
201 AB |= APInt::getLowBitsSet(BitWidth, ShiftAmt);
202 }
203 }
204 break;
205 case Instruction::AShr:
206 if (OperandNo == 0) {
207 const APInt *ShiftAmtC;
208 if (match(UserI->getOperand(1), m_APInt(ShiftAmtC))) {
209 uint64_t ShiftAmt = ShiftAmtC->getLimitedValue(BitWidth - 1);
210 AB = AOut.shl(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(BitWidth, 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>(UserI)->isExact())
221 AB |= APInt::getLowBitsSet(BitWidth, 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(0), UserI->getOperand(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(0), UserI->getOperand(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(BitWidth);
257 break;
258 case Instruction::ZExt:
259 AB = AOut.trunc(BitWidth);
260 break;
261 case Instruction::SExt:
262 AB = AOut.trunc(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(AOut.getBitWidth(),
267 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
298
299 // Collect the set of "root" instructions that are known live.
300 for (Instruction &I : instructions(F)) {
301 if (!isAlwaysLive(&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(&I, T->getScalarSizeInBits(), 0).second)
312 Worklist.insert(&I);
313
314 continue;
315 }
316
317 // Non-integer-typed instructions...
318 for (Use &OI : I.operands()) {
319 if (auto *J = dyn_cast<Instruction>(OI)) {
320 Type *T = J->getType();
321 if (T->isIntOrIntVectorTy())
322 AliveBits[J] = APInt::getAllOnes(T->getScalarSizeInBits());
323 else
324 Visited.insert(J);
325 Worklist.insert(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"
345
346 // If all bits of the output are dead, then all bits of the input
347 // are also dead.
348 InputIsKnownDead = !AOut && !isAlwaysLive(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>(OI);
361 if (!I && !isa<Argument>(OI))
362 continue;
363
364 Type *T = OI->getType();
365 if (T->isIntOrIntVectorTy()) {
366 unsigned BitWidth = T->getScalarSizeInBits();
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, OI, 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(&OI);
379 else
380 DeadUses.erase(&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(I);
388 if (Res.second || (AB |= Res.first->second) != Res.first->second) {
389 Res.first->second = std::move(AB);
390 Worklist.insert(I);
391 }
392 }
393 } else if (I && Visited.insert(I).second) {
394 Worklist.insert(I);
395 }
396 }
397 }
398}
399
401 performAnalysis();
402
403 auto Found = AliveBits.find(I);
404 if (Found != AliveBits.end())
405 return Found->second;
406
407 const DataLayout &DL = I->getModule()->getDataLayout();
408 return APInt::getAllOnes(DL.getTypeSizeInBits(I->getType()->getScalarType()));
409}
410
412 Type *T = (*U)->getType();
413 auto *UserI = cast<Instruction>(U->getUser());
414 const DataLayout &DL = UserI->getModule()->getDataLayout();
415 unsigned BitWidth = DL.getTypeSizeInBits(T->getScalarType());
416
417 // We only track integer uses, everything else produces a mask with all bits
418 // set
419 if (!T->isIntOrIntVectorTy())
421
422 if (isUseDead(U))
423 return APInt(BitWidth, 0);
424
425 performAnalysis();
426
427 APInt AOut = getDemandedBits(UserI);
429 KnownBits Known, Known2;
430 bool KnownBitsComputed = false;
431
432 determineLiveOperandBits(UserI, *U, U->getOperandNo(), AOut, AB, Known,
433 Known2, KnownBitsComputed);
434
435 return AB;
436}
437
439 performAnalysis();
440
441 return !Visited.count(I) && !AliveBits.contains(I) && !isAlwaysLive(I);
442}
443
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>(U->getUser());
451 if (isAlwaysLive(UserI))
452 return false;
453
454 performAnalysis();
455 if (DeadUses.count(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(UserI);
462 if (Found != AliveBits.end() && Found->second.isZero())
463 return true;
464 }
465
466 return false;
467}
468
470 auto PrintDB = [&](const Instruction *I, const APInt &A, Value *V = nullptr) {
471 OS << "DemandedBits: 0x" << Twine::utohexstr(A.getLimitedValue())
472 << " for ";
473 if (V) {
474 V->printAsOperand(OS, 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(&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
554 const APInt &AOut,
555 const KnownBits &LHS,
556 const KnownBits &RHS) {
557 return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS, true,
558 false);
559}
560
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, NRHS, false,
569 true);
570}
571
572AnalysisKey DemandedBitsAnalysis::Key;
573
576 auto &AC = AM.getResult<AssumptionAnalysis>(F);
577 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
578 return DemandedBits(F, AC, DT);
579}
580
584 return PreservedAnalyses::all();
585}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
#define LLVM_DEBUG(X)
Definition: Debug.h:101
static bool isAlwaysLive(Instruction *I)
static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
#define F(x, y, z)
Definition: MD5.cpp:55
#define I(x, y, z)
Definition: MD5.cpp:58
Module.h This file contains the declarations for the Module class.
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
This file implements a set that has insertion order iteration characteristics.
This defines the Use class.
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:76
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:212
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:981
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1463
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:906
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1672
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1439
APInt reverseBits() const
Definition: APInt.cpp:737
unsigned countr_zero() const
Count the number of trailing zero bits.
Definition: APInt.h:1589
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:453
bool isMask(unsigned numBits) const
Definition: APInt.h:466
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:851
APInt byteSwap() const
Definition: APInt.cpp:715
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:284
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:274
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:264
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:829
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:348
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:500
A function analysis which provides an AssumptionCache.
A parsed version of the target data layout string in and methods for querying it.
Definition: DataLayout.h:110
An analysis that produces DemandedBits for a function.
Definition: DemandedBits.h:101
DemandedBits run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce demanded bits information.
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
void print(raw_ostream &OS)
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
static APInt determineLiveOperandBitsAdd(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS)
Compute alive bits of one addition operand from alive output and known operand bits.
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
static APInt determineLiveOperandBitsSub(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS)
Compute alive bits of one subtraction operand from alive output and known operand bits.
bool isUseDead(Use *U)
Return whether this use is dead by means of not having any demanded bits.
Analysis pass which computes a DominatorTree.
Definition: Dominators.h:279
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
Definition: Instruction.cpp:80
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:251
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.h:287
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:93
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:162
value_type pop_back_val()
Definition: SetVector.h:285
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:370
static Twine utohexstr(const uint64_t &Val)
Definition: Twine.h:416
The instances of the Type class are immutable: once they are created, they are never changed.
Definition: Type.h:45
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
Definition: Type.h:234
A Use represents the edge between a Value definition and its users.
Definition: Use.h:43
op_range operands()
Definition: User.h:242
Value * getOperand(unsigned i) const
Definition: User.h:169
LLVM Value Representation.
Definition: Value.h:74
Type * getType() const
All values are typed, get the type of this value.
Definition: Value.h:255
StringRef getName() const
Return a constant reference to the value's name.
Definition: Value.cpp:309
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
bool match(Val *V, const Pattern &P)
Definition: PatternMatch.h:49
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
Definition: PatternMatch.h:294
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:264
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
void computeKnownBits(const Value *V, KnownBits &Known, const DataLayout &DL, unsigned Depth=0, AssumptionCache *AC=nullptr, const Instruction *CxtI=nullptr, const DominatorTree *DT=nullptr, bool UseInstrInfo=true)
Determine which bits of V are known to be either zero or one and return them in the KnownZero/KnownOn...
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:270
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:276