47#define DEBUG_TYPE "demanded-bits"
50 return I->isTerminator() || isa<DbgInfoIntrinsic>(
I) ||
I->isEHPad() ||
51 I->mayHaveSideEffects();
54void DemandedBits::determineLiveOperandBits(
57 bool &KnownBitsComputed) {
66 auto ComputeKnownBits =
68 if (KnownBitsComputed)
70 KnownBitsComputed =
true;
84 case Instruction::Call:
85 case Instruction::Invoke:
86 if (
const auto *
II = dyn_cast<IntrinsicInst>(UserI)) {
87 switch (
II->getIntrinsicID()) {
89 case Intrinsic::bswap:
94 case Intrinsic::bitreverse:
100 if (OperandNo == 0) {
104 ComputeKnownBits(
BitWidth, Val,
nullptr);
109 case Intrinsic::cttz:
110 if (OperandNo == 0) {
114 ComputeKnownBits(
BitWidth, Val,
nullptr);
119 case Intrinsic::fshl:
120 case Intrinsic::fshr: {
122 if (OperandNo == 2) {
131 if (
II->getIntrinsicID() == Intrinsic::fshr)
136 else if (OperandNo == 1)
141 case Intrinsic::umax:
142 case Intrinsic::umin:
143 case Intrinsic::smax:
144 case Intrinsic::smin:
152 case Instruction::Add:
160 case Instruction::Sub:
168 case Instruction::Mul:
174 case Instruction::Shl:
175 if (OperandNo == 0) {
176 const APInt *ShiftAmtC;
183 const auto *S = cast<ShlOperator>(UserI);
184 if (S->hasNoSignedWrap())
186 else if (S->hasNoUnsignedWrap())
191 case Instruction::LShr:
192 if (OperandNo == 0) {
193 const APInt *ShiftAmtC;
196 AB = AOut.
shl(ShiftAmt);
200 if (cast<LShrOperator>(UserI)->isExact())
205 case Instruction::AShr:
206 if (OperandNo == 0) {
207 const APInt *ShiftAmtC;
210 AB = AOut.
shl(ShiftAmt);
220 if (cast<AShrOperator>(UserI)->isExact())
225 case Instruction::And:
236 AB &= ~(Known.
Zero & ~Known2.Zero);
238 case Instruction::Or:
249 AB &= ~(Known.
One & ~Known2.One);
251 case Instruction::Xor:
252 case Instruction::PHI:
255 case Instruction::Trunc:
258 case Instruction::ZExt:
261 case Instruction::SExt:
271 case Instruction::Select:
275 case Instruction::ExtractElement:
279 case Instruction::InsertElement:
280 case Instruction::ShuffleVector:
281 if (OperandNo == 0 || OperandNo == 1)
287void DemandedBits::performAnalysis() {
310 if (
T->isIntOrIntVectorTy()) {
311 if (AliveBits.try_emplace(&
I,
T->getScalarSizeInBits(), 0).second)
318 for (
Use &OI :
I.operands()) {
319 if (
auto *J = dyn_cast<Instruction>(OI)) {
320 Type *
T = J->getType();
321 if (
T->isIntOrIntVectorTy())
335 while (!Worklist.
empty()) {
340 bool InputIsKnownDead =
false;
342 AOut = AliveBits[UserI];
353 bool KnownBitsComputed =
false;
360 auto *
I = dyn_cast<Instruction>(OI);
361 if (!
I && !isa<Argument>(OI))
364 Type *
T = OI->getType();
365 if (
T->isIntOrIntVectorTy()) {
366 unsigned BitWidth =
T->getScalarSizeInBits();
368 if (InputIsKnownDead) {
373 determineLiveOperandBits(UserI, OI, OI.getOperandNo(), AOut, AB,
374 Known, Known2, KnownBitsComputed);
378 DeadUses.insert(&OI);
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);
393 }
else if (
I && Visited.insert(
I).second) {
403 auto Found = AliveBits.find(
I);
404 if (Found != AliveBits.end())
405 return Found->second;
412 Type *
T = (*U)->getType();
413 auto *UserI = cast<Instruction>(U->getUser());
415 unsigned BitWidth =
DL.getTypeSizeInBits(
T->getScalarType());
419 if (!
T->isIntOrIntVectorTy())
430 bool KnownBitsComputed =
false;
432 determineLiveOperandBits(UserI, *U, U->getOperandNo(), AOut, AB, Known,
433 Known2, KnownBitsComputed);
441 return !Visited.count(
I) && !AliveBits.contains(
I) && !
isAlwaysLive(
I);
446 if (!(*U)->getType()->isIntOrIntVectorTy())
450 auto *UserI = cast<Instruction>(U->getUser());
455 if (DeadUses.count(U))
461 auto Found = AliveBits.find(UserI);
462 if (Found != AliveBits.end() && Found->second.isZero())
474 V->printAsOperand(
OS,
false);
480 OS <<
"Printing analysis 'Demanded Bits Analysis' for function '" << F.
getName() <<
"':\n";
482 for (
auto &KV : AliveBits) {
484 PrintDB(
I, KV.second);
486 for (
Use &OI :
I->operands()) {
496 bool CarryZero,
bool CarryOne) {
497 assert(!(CarryZero && CarryOne) &&
498 "Carry can't be zero and one at the same time");
516 APInt RProp = RAOut + (RAOut | ~RBound);
517 APInt RACarry = RProp ^ ~RBound;
521 APInt NeededToMaintainCarryZero;
522 APInt NeededToMaintainCarryOne;
523 if (OperandNo == 0) {
524 NeededToMaintainCarryZero =
LHS.Zero | ~RHS.Zero;
525 NeededToMaintainCarryOne =
LHS.One | ~RHS.One;
527 NeededToMaintainCarryZero =
RHS.Zero | ~LHS.Zero;
528 NeededToMaintainCarryOne =
RHS.One | ~LHS.One;
532 APInt PossibleSumZero = ~LHS.Zero + ~RHS.Zero + !CarryZero;
533 APInt PossibleSumOne =
LHS.One +
RHS.One + CarryOne;
546 APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &
547 (PossibleSumOne | NeededToMaintainCarryOne);
549 APInt AB = AOut | (ACarry & NeededToMaintainCarry);
This file implements a class to represent arbitrary precision integral constant values and operations...
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Expand Atomic instructions
static GCRegistry::Add< ErlangGC > A("erlang", "erlang-compatible garbage collector")
static bool isAlwaysLive(Instruction *I)
static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
This defines the Use class.
Module.h This file contains the declarations for the Module class.
uint64_t IntrinsicInst * II
This header defines various interfaces for pass management in LLVM.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file implements a set that has insertion order iteration characteristics.
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
APInt zext(unsigned width) const
Zero extend to a new width.
unsigned getActiveBits() const
Compute the number of active bits in the value.
APInt trunc(unsigned width) const
Truncate to new width.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
unsigned getBitWidth() const
Return the number of bits in the APInt.
APInt reverseBits() const
unsigned countr_zero() const
Count the number of trailing zero bits.
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.
bool isMask(unsigned numBits) const
APInt shl(unsigned shiftAmt) const
Left-shift function.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
A container for analyses that lazily runs them and caches their results.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
A function analysis which provides an AssumptionCache.
A parsed version of the target data layout string in and methods for querying it.
An analysis that produces DemandedBits for a function.
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.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
const DataLayout & getDataLayout() const
Get the data layout of the module this instruction belongs to.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool empty() const
Determine if the SetVector is empty or not.
bool insert(const value_type &X)
Insert a new element into the SetVector.
value_type pop_back_val()
A SetVector that performs no allocations if smaller than a certain size.
static Twine utohexstr(const uint64_t &Val)
The instances of the Type class are immutable: once they are created, they are never changed.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
A Use represents the edge between a Value definition and its users.
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
StringRef getName() const
Return a constant reference to the value's name.
This class implements an extremely fast bulk output stream that can only output to a stream.
bool match(Val *V, const Pattern &P)
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
This is an optimization pass for GlobalISel generic memory operations.
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.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
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
A special type used by analysis passes to provide an address that identifies that particular analysis...
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.