Go to the documentation of this file.
49 #define DEBUG_TYPE "demanded-bits"
54 "Demanded bits analysis",
false,
false)
76 return I->isTerminator() || isa<DbgInfoIntrinsic>(
I) ||
I->isEHPad() ||
77 I->mayHaveSideEffects();
80 void DemandedBits::determineLiveOperandBits(
83 bool &KnownBitsComputed) {
92 auto ComputeKnownBits =
94 if (KnownBitsComputed)
96 KnownBitsComputed =
true;
111 case Instruction::Invoke:
112 if (
const IntrinsicInst *II = dyn_cast<IntrinsicInst>(UserI)) {
113 switch (II->getIntrinsicID()) {
115 case Intrinsic::bswap:
120 case Intrinsic::bitreverse:
125 case Intrinsic::ctlz:
126 if (OperandNo == 0) {
130 ComputeKnownBits(
BitWidth, Val,
nullptr);
135 case Intrinsic::cttz:
136 if (OperandNo == 0) {
140 ComputeKnownBits(
BitWidth, Val,
nullptr);
145 case Intrinsic::fshl:
146 case Intrinsic::fshr: {
148 if (OperandNo == 2) {
157 if (II->getIntrinsicID() == Intrinsic::fshr)
162 else if (OperandNo == 1)
183 AB = determineLiveOperandBitsAdd(OperandNo, AOut, Known, Known2);
186 case Instruction::Sub:
191 AB = determineLiveOperandBitsSub(OperandNo, AOut, Known, Known2);
200 case Instruction::Shl:
201 if (OperandNo == 0) {
202 const APInt *ShiftAmtC;
210 if (
S->hasNoSignedWrap())
212 else if (
S->hasNoUnsignedWrap())
217 case Instruction::LShr:
218 if (OperandNo == 0) {
219 const APInt *ShiftAmtC;
222 AB = AOut.
shl(ShiftAmt);
226 if (cast<LShrOperator>(UserI)->isExact())
231 case Instruction::AShr:
232 if (OperandNo == 0) {
233 const APInt *ShiftAmtC;
236 AB = AOut.
shl(ShiftAmt);
246 if (cast<AShrOperator>(UserI)->isExact())
251 case Instruction::And:
264 case Instruction::Or:
277 case Instruction::Xor:
281 case Instruction::Trunc:
284 case Instruction::ZExt:
287 case Instruction::SExt:
301 case Instruction::ExtractElement:
305 case Instruction::InsertElement:
306 case Instruction::ShuffleVector:
307 if (OperandNo == 0 || OperandNo == 1)
314 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
315 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
316 DB.emplace(
F, AC, DT);
324 void DemandedBits::performAnalysis() {
347 if (
T->isIntOrIntVectorTy()) {
348 if (AliveBits.try_emplace(&
I,
T->getScalarSizeInBits(), 0).second)
355 for (
Use &OI :
I.operands()) {
357 Type *
T = J->getType();
358 if (
T->isIntOrIntVectorTy())
372 while (!Worklist.
empty()) {
377 bool InputIsKnownDead =
false;
379 AOut = AliveBits[UserI];
390 bool KnownBitsComputed =
false;
398 if (!
I && !isa<Argument>(OI))
401 Type *
T = OI->getType();
402 if (
T->isIntOrIntVectorTy()) {
403 unsigned BitWidth =
T->getScalarSizeInBits();
405 if (InputIsKnownDead) {
410 determineLiveOperandBits(UserI, OI, OI.getOperandNo(), AOut, AB,
411 Known, Known2, KnownBitsComputed);
415 DeadUses.insert(&OI);
424 auto Res = AliveBits.try_emplace(
I);
425 if (Res.second || (AB |= Res.first->second) != Res.first->second) {
430 }
else if (
I && Visited.insert(
I).second) {
440 auto Found = AliveBits.find(
I);
441 if (Found != AliveBits.end())
442 return Found->second;
449 Type *
T = (*U)->getType();
450 Instruction *UserI = cast<Instruction>(U->getUser());
452 unsigned BitWidth =
DL.getTypeSizeInBits(
T->getScalarType());
456 if (!
T->isIntOrIntVectorTy())
464 APInt AOut = getDemandedBits(UserI);
467 bool KnownBitsComputed =
false;
469 determineLiveOperandBits(UserI, *U, U->getOperandNo(), AOut, AB, Known,
470 Known2, KnownBitsComputed);
478 return !Visited.count(
I) && AliveBits.find(
I) == AliveBits.end() &&
484 if (!(*U)->getType()->isIntOrIntVectorTy())
488 Instruction *UserI = cast<Instruction>(U->getUser());
493 if (DeadUses.count(U))
499 auto Found = AliveBits.find(UserI);
500 if (Found != AliveBits.end() && Found->second.isZero())
512 V->printAsOperand(OS,
false);
519 for (
auto &KV : AliveBits) {
521 PrintDB(
I, KV.second);
523 for (
Use &OI :
I->operands()) {
524 PrintDB(
I, getDemandedBits(&OI), OI);
533 bool CarryZero,
bool CarryOne) {
534 assert(!(CarryZero && CarryOne) &&
535 "Carry can't be zero and one at the same time");
553 APInt RProp = RAOut + (RAOut | ~RBound);
554 APInt RACarry = RProp ^ ~RBound;
558 APInt NeededToMaintainCarryZero;
559 APInt NeededToMaintainCarryOne;
560 if (OperandNo == 0) {
561 NeededToMaintainCarryZero =
LHS.Zero | ~
RHS.Zero;
562 NeededToMaintainCarryOne =
LHS.One | ~
RHS.One;
564 NeededToMaintainCarryZero =
RHS.Zero | ~
LHS.Zero;
565 NeededToMaintainCarryOne =
RHS.One | ~
LHS.One;
569 APInt PossibleSumZero = ~
LHS.Zero + ~
RHS.Zero + !CarryZero;
570 APInt PossibleSumOne =
LHS.One +
RHS.One + CarryOne;
583 APInt NeededToMaintainCarry = (~PossibleSumZero | NeededToMaintainCarryZero) &
584 (PossibleSumOne | NeededToMaintainCarryOne);
586 APInt AB = AOut | (ACarry & NeededToMaintainCarry);
A set of analyses that are preserved following a run of a transformation pass.
APInt reverseBits() const
This is an optimization pass for GlobalISel generic memory operations.
const Module * getModule() const
Return the module owning the function this instruction belongs to or nullptr it the function does not...
A parsed version of the target data layout string in and methods for querying it.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
bool isMask(unsigned numBits) const
An analysis that produces DemandedBits for a function.
The instances of the Type class are immutable: once they are created, they are never changed.
unsigned getBitWidth() const
Return the number of bits in the APInt.
static bool isAlwaysLive(Instruction *I)
INITIALIZE_PASS_BEGIN(DemandedBitsWrapperPass, "demanded-bits", "Demanded bits analysis", false, false) INITIALIZE_PASS_END(DemandedBitsWrapperPass
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
bool runOnFunction(Function &F) override
runOnFunction - Virtual method overriden by subclasses to do the per-function processing of the pass.
apint_match m_APInt(const APInt *&Res)
Match a ConstantInt or splatted ConstantVector, binding the specified pointer to the contained APInt.
unsigned getOpcode() const
Returns a member of one of the enums like Instruction::Add.
static PassRegistry * getPassRegistry()
getPassRegistry - Access the global registry object, which is automatically initialized at applicatio...
bool match(Val *V, const Pattern &P)
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Represent the analysis usage information of a pass.
void print(raw_ostream &OS, const Module *M) const override
print - Print out the internal state of the pass.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
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.
FunctionPass * createDemandedBitsWrapperPass()
Create a demanded bits analysis pass.
Legacy analysis pass which computes a DominatorTree.
This class implements an extremely fast bulk output stream that can only output to a stream.
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
demanded Demanded bits analysis
static APInt determineLiveOperandBitsAddCarry(unsigned OperandNo, const APInt &AOut, const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
unsigned countTrailingZeros() const
Count the number of trailing zero bits.
bool empty() const
Determine if the SetVector is empty or not.
unsigned ID
LLVM IR allows to use arbitrary numbers as calling convention identifiers.
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
void print(raw_ostream &OS)
inst_range instructions(Function *F)
static Twine utohexstr(const uint64_t &Val)
A function analysis which provides an AssumptionCache.
INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
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.
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
A special type used by analysis passes to provide an address that identifies that particular analysis...
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...
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
A Module instance is used to store all the information related to an LLVM module.
APInt urem(const APInt &RHS) const
Unsigned remainder operation.
Class for arbitrary precision integers.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Printable print(const GCNRegPressure &RP, const GCNSubtarget *ST=nullptr)
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
An immutable pass that tracks lazily created AssumptionCache objects.
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
void setPreservesCFG()
This function should be called by the pass, iff they do not:
Type * getType() const
All values are typed, get the type of this value.
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
APInt zext(unsigned width) const
Zero extend to a new width.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
const APInt & umax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be unsigned.
bool isInstructionDead(Instruction *I)
Return true if, during analysis, I could not be reached.
APInt trunc(unsigned width) const
Truncate to new width.
void setPreservesAll()
Set by analyses that do not transform their input at all.
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.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
bool isIntOrIntVectorTy() const
Return true if this is an integer type or a vector of integer types.
constexpr unsigned BitWidth
void releaseMemory() override
Clean up memory in between runs.
APInt getDemandedBits(Instruction *I)
Return the bits demanded from instruction I.
A wrapper class for inspecting calls to intrinsic functions.
Analysis pass which computes a DominatorTree.
unsigned getActiveBits() const
Compute the number of active bits in the value.
void initializeDemandedBitsWrapperPassPass(PassRegistry &)
bool isUseDead(Use *U)
Return whether this use is dead by means of not having any demanded bits.
const DataLayout & getDataLayout() const
Get the data layout for the module's target platform.
A SetVector that performs no allocations if smaller than a certain size.
A container for analyses that lazily runs them and caches their results.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
FunctionPass class - This class is used to implement most global optimizations.
DemandedBits run(Function &F, FunctionAnalysisManager &AM)
Run the analysis pass over a function and produce demanded bits information.
AnalysisUsage & addRequired()
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
APInt shl(unsigned shiftAmt) const
Left-shift function.
Value * getOperand(unsigned i) const
LLVM Value Representation.
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
A Use represents the edge between a Value definition and its users.