LLVM 17.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 performAnalysis();
481 for (auto &KV : AliveBits) {
482 Instruction *I = KV.first;
483 PrintDB(I, KV.second);
484
485 for (Use &OI : I->operands()) {
486 PrintDB(I, getDemandedBits(&OI), OI);
487 }
488 }
489}
490
491static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo,
492 const APInt &AOut,
493 const KnownBits &LHS,
494 const KnownBits &RHS,
495 bool CarryZero, bool CarryOne) {
496 assert(!(CarryZero && CarryOne) &&
497 "Carry can't be zero and one at the same time");
498
499 // The following check should be done by the caller, as it also indicates
500 // that LHS and RHS don't need to be computed.
501 //
502 // if (AOut.isMask())
503 // return AOut;
504
505 // Boundary bits' carry out is unaffected by their carry in.
506 APInt Bound = (LHS.Zero & RHS.Zero) | (LHS.One & RHS.One);
507
508 // First, the alive carry bits are determined from the alive output bits:
509 // Let demand ripple to the right but only up to any set bit in Bound.
510 // AOut = -1----
511 // Bound = ----1-
512 // ACarry&~AOut = --111-
513 APInt RBound = Bound.reverseBits();
514 APInt RAOut = AOut.reverseBits();
515 APInt RProp = RAOut + (RAOut | ~RBound);
516 APInt RACarry = RProp ^ ~RBound;
517 APInt ACarry = RACarry.reverseBits();
518
519 // Then, the alive input bits are determined from the alive carry bits:
520 APInt NeededToMaintainCarryZero;
521 APInt NeededToMaintainCarryOne;
522 if (OperandNo == 0) {
523 NeededToMaintainCarryZero = LHS.Zero | ~RHS.Zero;
524 NeededToMaintainCarryOne = LHS.One | ~RHS.One;
525 } else {
526 NeededToMaintainCarryZero = RHS.Zero | ~LHS.Zero;
527 NeededToMaintainCarryOne = RHS.One | ~LHS.One;
528 }
529
530 // As in computeForAddCarry
531 APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;
532 APInt PossibleSumOne = LHS.One + RHS.One + CarryOne;
533
534 // The below is simplified from
535 //
536 // APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
537 // APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
538 // APInt CarryUnknown = ~(CarryKnownZero | CarryKnownOne);
539 //
540 // APInt NeededToMaintainCarry =
541 // (CarryKnownZero & NeededToMaintainCarryZero) |
542 // (CarryKnownOne & NeededToMaintainCarryOne) |
543 // CarryUnknown;
544
545 APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &
546 (PossibleSumOne | NeededToMaintainCarryOne);
547
548 APInt AB = AOut | (ACarry & NeededToMaintainCarry);
549 return AB;
550}
551
553 const APInt &AOut,
554 const KnownBits &LHS,
555 const KnownBits &RHS) {
556 return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, RHS, true,
557 false);
558}
559
561 const APInt &AOut,
562 const KnownBits &LHS,
563 const KnownBits &RHS) {
564 KnownBits NRHS;
565 NRHS.Zero = RHS.One;
566 NRHS.One = RHS.Zero;
567 return determineLiveOperandBitsAddCarry(OperandNo, AOut, LHS, NRHS, false,
568 true);
569}
570
571AnalysisKey DemandedBitsAnalysis::Key;
572
575 auto &AC = AM.getResult<AssumptionAnalysis>(F);
576 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
577 return DemandedBits(F, AC, DT);
578}
579
583 return PreservedAnalyses::all();
584}
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file implements a class to represent arbitrary precision integral constant values and operations...
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.
print must be executed print the must be executed context for all instructions
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:75
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:214
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:973
unsigned getActiveBits() const
Compute the number of active bits in the value.
Definition: APInt.h:1467
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:898
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Definition: APInt.cpp:1664
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1443
APInt reverseBits() const
Definition: APInt.cpp:729
unsigned countr_zero() const
Count the number of trailing zero bits.
Definition: APInt.h:1596
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:463
bool isMask(unsigned numBits) const
Definition: APInt.h:476
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:861
APInt byteSwap() const
Definition: APInt.cpp:707
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:289
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:279
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:269
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:839
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:620
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
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:102
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:70
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
Definition: Instruction.h:168
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
Definition: Module.cpp:398
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:152
bool empty() const
Determine if the SetVector is empty or not.
Definition: SetVector.h:83
value_type pop_back_val()
Definition: SetVector.h:236
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:312
static Twine utohexstr(const uint64_t &Val)
Definition: Twine.h:404
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:235
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
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:278
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:292
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, OptimizationRemarkEmitter *ORE=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:184
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:265
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:271