22#define DEBUG_TYPE "gisel-known-bits"
29 "Analysis for ComputingKnownBits",
false,
true)
32 : MF(MF),
MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
37 switch (
MI->getOpcode()) {
38 case TargetOpcode::COPY:
40 case TargetOpcode::G_ASSERT_ALIGN: {
42 return Align(
MI->getOperand(2).getImm());
44 case TargetOpcode::G_FRAME_INDEX: {
45 int FrameIdx =
MI->getOperand(1).getIndex();
48 case TargetOpcode::G_INTRINSIC:
49 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
56 assert(
MI.getNumExplicitDefs() == 1 &&
57 "expected single return generic instruction");
71 assert(ComputeKnownBitsCache.empty() &&
"Cache should have been cleared");
75 ComputeKnownBitsCache.clear();
94 <<
"] Computed for: " <<
MI <<
"[" <<
Depth <<
"] Known: 0x"
105 const APInt &DemandedElts,
136 const APInt &DemandedElts,
139 unsigned Opcode =
MI.getOpcode();
152 auto CacheEntry = ComputeKnownBitsCache.find(R);
153 if (CacheEntry != ComputeKnownBitsCache.end()) {
154 Known = CacheEntry->second;
183 case TargetOpcode::G_BUILD_VECTOR: {
186 for (
unsigned i = 0, e =
MI.getNumOperands() - 1; i < e; ++i) {
187 if (!DemandedElts[i])
202 case TargetOpcode::COPY:
203 case TargetOpcode::G_PHI:
204 case TargetOpcode::PHI: {
210 assert(
MI.getOperand(0).getSubReg() == 0 &&
"Is this code in SSA?");
223 for (
unsigned Idx = 1;
Idx <
MI.getNumOperands();
Idx += 2) {
233 if (SrcReg.
isVirtual() && Src.getSubReg() == 0 &&
237 Depth + (Opcode != TargetOpcode::COPY));
241 if (Known.
One == 0 && Known.
Zero == 0)
251 case TargetOpcode::G_CONSTANT: {
258 case TargetOpcode::G_FRAME_INDEX: {
259 int FrameIdx =
MI.getOperand(1).getIndex();
263 case TargetOpcode::G_SUB: {
272 case TargetOpcode::G_XOR: {
281 case TargetOpcode::G_PTR_ADD: {
290 case TargetOpcode::G_ADD: {
299 case TargetOpcode::G_AND: {
309 case TargetOpcode::G_OR: {
319 case TargetOpcode::G_MUL: {
327 case TargetOpcode::G_SELECT: {
328 computeKnownBitsMin(
MI.getOperand(2).getReg(),
MI.getOperand(3).getReg(),
329 Known, DemandedElts,
Depth + 1);
332 case TargetOpcode::G_SMIN: {
342 case TargetOpcode::G_SMAX: {
352 case TargetOpcode::G_UMIN: {
355 DemandedElts,
Depth + 1);
357 DemandedElts,
Depth + 1);
361 case TargetOpcode::G_UMAX: {
364 DemandedElts,
Depth + 1);
366 DemandedElts,
Depth + 1);
370 case TargetOpcode::G_FCMP:
371 case TargetOpcode::G_ICMP: {
375 Opcode == TargetOpcode::G_FCMP) ==
381 case TargetOpcode::G_SEXT: {
389 case TargetOpcode::G_ASSERT_SEXT:
390 case TargetOpcode::G_SEXT_INREG: {
393 Known = Known.
sextInReg(
MI.getOperand(2).getImm());
396 case TargetOpcode::G_ANYEXT: {
402 case TargetOpcode::G_LOAD: {
410 case TargetOpcode::G_ZEXTLOAD: {
417 case TargetOpcode::G_ASHR: {
426 case TargetOpcode::G_LSHR: {
435 case TargetOpcode::G_SHL: {
444 case TargetOpcode::G_INTTOPTR:
445 case TargetOpcode::G_PTRTOINT:
450 case TargetOpcode::G_ASSERT_ZEXT:
451 case TargetOpcode::G_ZEXT:
452 case TargetOpcode::G_TRUNC: {
455 unsigned SrcBitWidth;
458 if (Opcode == TargetOpcode::G_ASSERT_ZEXT)
459 SrcBitWidth =
MI.getOperand(2).getImm();
465 assert(SrcBitWidth &&
"SrcBitWidth can't be zero");
473 case TargetOpcode::G_ASSERT_ALIGN: {
474 int64_t LogOfAlign =
Log2_64(
MI.getOperand(2).getImm());
483 case TargetOpcode::G_MERGE_VALUES: {
484 unsigned NumOps =
MI.getNumOperands();
487 for (
unsigned I = 0;
I != NumOps - 1; ++
I) {
490 DemandedElts,
Depth + 1);
495 case TargetOpcode::G_UNMERGE_VALUES: {
498 unsigned NumOps =
MI.getNumOperands();
499 Register SrcReg =
MI.getOperand(NumOps - 1).getReg();
508 for (; DstIdx != NumOps - 1 &&
MI.getOperand(DstIdx).
getReg() != R;
515 case TargetOpcode::G_BSWAP: {
521 case TargetOpcode::G_BITREVERSE: {
527 case TargetOpcode::G_CTPOP: {
539 case TargetOpcode::G_UBFX: {
540 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
550 case TargetOpcode::G_SBFX: {
551 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
563 false,
false, ExtKnown, WidthKnown);
567 case TargetOpcode::G_UADDO:
568 case TargetOpcode::G_UADDE:
569 case TargetOpcode::G_SADDO:
570 case TargetOpcode::G_SADDE:
571 case TargetOpcode::G_USUBO:
572 case TargetOpcode::G_USUBE:
573 case TargetOpcode::G_SSUBO:
574 case TargetOpcode::G_SSUBE:
575 case TargetOpcode::G_UMULO:
576 case TargetOpcode::G_SMULO: {
577 if (
MI.getOperand(1).getReg() == R) {
593 ComputeKnownBitsCache[R] = Known;
598 const APInt &DemandedElts,
602 if (Src1SignBits == 1)
608 const APInt &DemandedElts,
611 unsigned Opcode =
MI.getOpcode();
613 if (Opcode == TargetOpcode::G_CONSTANT)
614 return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
632 unsigned FirstAnswer = 1;
634 case TargetOpcode::COPY: {
636 if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
644 case TargetOpcode::G_SEXT: {
650 case TargetOpcode::G_ASSERT_SEXT:
651 case TargetOpcode::G_SEXT_INREG: {
654 unsigned SrcBits =
MI.getOperand(2).getImm();
655 unsigned InRegBits = TyBits - SrcBits + 1;
658 case TargetOpcode::G_SEXTLOAD: {
667 case TargetOpcode::G_ZEXTLOAD: {
676 case TargetOpcode::G_TRUNC: {
684 if (NumSrcSignBits > (NumSrcBits - DstTyBits))
685 return NumSrcSignBits - (NumSrcBits - DstTyBits);
688 case TargetOpcode::G_SELECT: {
689 return computeNumSignBitsMin(
MI.getOperand(2).getReg(),
690 MI.getOperand(3).getReg(), DemandedElts,
693 case TargetOpcode::G_SADDO:
694 case TargetOpcode::G_SADDE:
695 case TargetOpcode::G_UADDO:
696 case TargetOpcode::G_UADDE:
697 case TargetOpcode::G_SSUBO:
698 case TargetOpcode::G_SSUBE:
699 case TargetOpcode::G_USUBO:
700 case TargetOpcode::G_USUBE:
701 case TargetOpcode::G_SMULO:
702 case TargetOpcode::G_UMULO: {
706 if (
MI.getOperand(1).getReg() == R) {
714 case TargetOpcode::G_FCMP:
715 case TargetOpcode::G_ICMP: {
716 bool IsFP = Opcode == TargetOpcode::G_FCMP;
726 case TargetOpcode::G_INTRINSIC:
727 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
732 FirstAnswer = std::max(FirstAnswer, NumBits);
752 Mask <<= Mask.getBitWidth() - TyBits;
753 return std::max(FirstAnswer, Mask.countl_one());
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
static const Function * getParent(const Value *V)
#define LLVM_ATTRIBUTE_UNUSED
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
static Function * getFunction(Constant *C)
static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown, const KnownBits &OffsetKnown, const KnownBits &WidthKnown)
#define DEBUG_TYPE
Provides analysis for querying information about KnownBits during GISel passes.
static LLVM_ATTRIBUTE_UNUSED void dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth)
Provides analysis for querying information about KnownBits during GISel passes.
static const unsigned MaxDepth
static unsigned getReg(const MCDisassembler *D, unsigned RC, unsigned RegNo)
Module.h This file contains the declarations for the Module class.
#define INITIALIZE_PASS(passName, arg, name, cfg, analysis)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file describes how to lower LLVM code to machine code.
Class for arbitrary precision integers.
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
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.
void setAllBits()
Set every bit to 1.
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Represent the analysis usage information of a pass.
void setPreservesAll()
Set by analyses that do not transform their input at all.
bool isNonIntegralAddressSpace(unsigned AddrSpace) const
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
To use KnownBitsInfo analysis in a pass, KnownBitsInfo &Info = getAnalysis<GISelKnownBitsInfoAnalysis...
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
virtual void computeKnownBitsImpl(Register R, KnownBits &Known, const APInt &DemandedElts, unsigned Depth=0)
Align computeKnownAlignment(Register R, unsigned Depth=0)
APInt getKnownOnes(Register R)
unsigned computeNumSignBits(Register R, const APInt &DemandedElts, unsigned Depth=0)
KnownBits getKnownBits(Register R)
bool maskedValueIsZero(Register Val, const APInt &Mask)
unsigned getMaxDepth() const
bool signBitIsZero(Register Op)
APInt getKnownZeroes(Register R)
constexpr unsigned getScalarSizeInBits() const
constexpr bool isValid() const
constexpr uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
constexpr bool isVector() const
constexpr TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
constexpr bool isPointer() const
constexpr unsigned getAddressSpace() const
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Representation of each machine instruction.
A description of a memory reference used in the backend.
const MDNode * getRanges() const
Return the range tag for the memory reference.
uint64_t getSizeInBits() const
Return the size in bits of the memory reference.
MachineOperand class - Representation of each machine instruction operand.
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
Wrapper class representing virtual and physical registers.
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
BooleanContent getBooleanContents(bool isVec, bool isFloat) const
For targets without i1 registers, this gives the nature of the high-bits of boolean values held in ty...
@ ZeroOrOneBooleanContent
@ ZeroOrNegativeOneBooleanContent
virtual void computeKnownBitsForFrameIndex(int FIOp, KnownBits &Known, const MachineFunction &MF) const
Determine which of the bits of FrameIndex FIOp are known to be 0.
virtual unsigned computeNumSignBitsForTargetInstr(GISelKnownBits &Analysis, Register R, const APInt &DemandedElts, const MachineRegisterInfo &MRI, unsigned Depth=0) const
This method can be implemented by targets that want to expose additional information about sign bits ...
virtual Align computeKnownAlignForTargetInstr(GISelKnownBits &Analysis, Register R, const MachineRegisterInfo &MRI, unsigned Depth=0) const
Determine the known alignment for the pointer value R.
virtual void computeKnownBitsForTargetInstr(GISelKnownBits &Analysis, Register R, KnownBits &Known, const APInt &DemandedElts, const MachineRegisterInfo &MRI, unsigned Depth=0) const
Determine which of the bits specified in Mask are known to be either zero or one and return them in t...
std::optional< const char * > toString(const std::optional< DWARFFormValue > &V)
Take an optional DWARFFormValue and try to extract a string value from it.
This is an optimization pass for GlobalISel generic memory operations.
std::optional< APInt > getIConstantVRegVal(Register VReg, const MachineRegisterInfo &MRI)
If VReg is defined by a G_CONSTANT, return the corresponding value.
int bit_width(T Value)
Returns the number of bits needed to represent Value if Value is nonzero.
unsigned Log2_64(uint64_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
constexpr unsigned BitWidth
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
This struct is a compact representation of a valid (non-zero power of two) alignment.
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
KnownBits sextInReg(unsigned SrcBitWidth) const
Return known bits for a in-register sign extension of the value we're tracking.
static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smax(LHS, RHS).
bool isNonNegative() const
Returns true if this value is known to be non-negative.
static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits common to LHS and RHS.
bool isUnknown() const
Returns true if we don't know any bits.
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for shl(LHS, RHS).
KnownBits byteSwap() const
bool hasConflict() const
Returns true if there is conflicting information.
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
KnownBits reverseBits() const
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for lshr(LHS, RHS).
unsigned getBitWidth() const
Get the bit width of this value.
static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umax(LHS, RHS).
static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for ashr(LHS, RHS).
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
KnownBits sext(unsigned BitWidth) const
Return known bits for a sign extension of the value we're tracking.
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smin(LHS, RHS).
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
bool isNegative() const
Returns true if this value is known to be negative.
void insertBits(const KnownBits &SubBits, unsigned BitPosition)
Insert the bits from a smaller known bits starting at bitPosition.
static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
KnownBits anyext(unsigned BitWidth) const
Return known bits for an "any" extension of the value we're tracking, where we don't know anything ab...
static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS)
Compute known bits resulting from adding LHS and RHS.
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).