24#define DEBUG_TYPE "gisel-known-bits"
31 "Analysis for ComputingKnownBits",
false,
true)
34 : MF(MF),
MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
39 switch (
MI->getOpcode()) {
40 case TargetOpcode::COPY:
42 case TargetOpcode::G_ASSERT_ALIGN: {
44 return Align(
MI->getOperand(2).getImm());
46 case TargetOpcode::G_FRAME_INDEX: {
47 int FrameIdx =
MI->getOperand(1).getIndex();
50 case TargetOpcode::G_INTRINSIC:
51 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
52 case TargetOpcode::G_INTRINSIC_CONVERGENT:
53 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
60 assert(
MI.getNumExplicitDefs() == 1 &&
61 "expected single return generic instruction");
75 assert(ComputeKnownBitsCache.empty() &&
"Cache should have been cleared");
79 ComputeKnownBitsCache.clear();
98 <<
"] Computed for: " <<
MI <<
"[" <<
Depth <<
"] Known: 0x"
109 const APInt &DemandedElts,
140 const APInt &DemandedElts,
143 unsigned Opcode =
MI.getOpcode();
156 auto CacheEntry = ComputeKnownBitsCache.find(R);
157 if (CacheEntry != ComputeKnownBitsCache.end()) {
158 Known = CacheEntry->second;
187 case TargetOpcode::G_BUILD_VECTOR: {
190 for (
unsigned i = 0, e =
MI.getNumOperands() - 1; i < e; ++i) {
191 if (!DemandedElts[i])
206 case TargetOpcode::COPY:
207 case TargetOpcode::G_PHI:
208 case TargetOpcode::PHI: {
214 assert(
MI.getOperand(0).getSubReg() == 0 &&
"Is this code in SSA?");
227 for (
unsigned Idx = 1;
Idx <
MI.getNumOperands();
Idx += 2) {
237 if (SrcReg.
isVirtual() && Src.getSubReg() == 0 &&
241 Depth + (Opcode != TargetOpcode::COPY));
255 case TargetOpcode::G_CONSTANT: {
262 case TargetOpcode::G_FRAME_INDEX: {
263 int FrameIdx =
MI.getOperand(1).getIndex();
267 case TargetOpcode::G_SUB: {
273 false, Known, Known2);
276 case TargetOpcode::G_XOR: {
285 case TargetOpcode::G_PTR_ADD: {
294 case TargetOpcode::G_ADD: {
300 false, Known, Known2);
303 case TargetOpcode::G_AND: {
313 case TargetOpcode::G_OR: {
323 case TargetOpcode::G_MUL: {
331 case TargetOpcode::G_SELECT: {
332 computeKnownBitsMin(
MI.getOperand(2).getReg(),
MI.getOperand(3).getReg(),
333 Known, DemandedElts,
Depth + 1);
336 case TargetOpcode::G_SMIN: {
346 case TargetOpcode::G_SMAX: {
356 case TargetOpcode::G_UMIN: {
359 DemandedElts,
Depth + 1);
361 DemandedElts,
Depth + 1);
365 case TargetOpcode::G_UMAX: {
368 DemandedElts,
Depth + 1);
370 DemandedElts,
Depth + 1);
374 case TargetOpcode::G_FCMP:
375 case TargetOpcode::G_ICMP: {
379 Opcode == TargetOpcode::G_FCMP) ==
385 case TargetOpcode::G_SEXT: {
393 case TargetOpcode::G_ASSERT_SEXT:
394 case TargetOpcode::G_SEXT_INREG: {
397 Known = Known.
sextInReg(
MI.getOperand(2).getImm());
400 case TargetOpcode::G_ANYEXT: {
406 case TargetOpcode::G_LOAD: {
414 case TargetOpcode::G_SEXTLOAD:
415 case TargetOpcode::G_ZEXTLOAD: {
422 Known = Opcode == TargetOpcode::G_SEXTLOAD
427 case TargetOpcode::G_ASHR: {
436 case TargetOpcode::G_LSHR: {
445 case TargetOpcode::G_SHL: {
454 case TargetOpcode::G_INTTOPTR:
455 case TargetOpcode::G_PTRTOINT:
460 case TargetOpcode::G_ASSERT_ZEXT:
461 case TargetOpcode::G_ZEXT:
462 case TargetOpcode::G_TRUNC: {
465 unsigned SrcBitWidth;
468 if (Opcode == TargetOpcode::G_ASSERT_ZEXT)
469 SrcBitWidth =
MI.getOperand(2).getImm();
475 assert(SrcBitWidth &&
"SrcBitWidth can't be zero");
483 case TargetOpcode::G_ASSERT_ALIGN: {
484 int64_t LogOfAlign =
Log2_64(
MI.getOperand(2).getImm());
493 case TargetOpcode::G_MERGE_VALUES: {
494 unsigned NumOps =
MI.getNumOperands();
497 for (
unsigned I = 0;
I != NumOps - 1; ++
I) {
500 DemandedElts,
Depth + 1);
505 case TargetOpcode::G_UNMERGE_VALUES: {
508 unsigned NumOps =
MI.getNumOperands();
509 Register SrcReg =
MI.getOperand(NumOps - 1).getReg();
518 for (; DstIdx != NumOps - 1 &&
MI.getOperand(DstIdx).
getReg() != R;
525 case TargetOpcode::G_BSWAP: {
531 case TargetOpcode::G_BITREVERSE: {
537 case TargetOpcode::G_CTPOP: {
549 case TargetOpcode::G_UBFX: {
550 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
560 case TargetOpcode::G_SBFX: {
561 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
573 false,
false,
false, ExtKnown, WidthKnown);
577 case TargetOpcode::G_UADDO:
578 case TargetOpcode::G_UADDE:
579 case TargetOpcode::G_SADDO:
580 case TargetOpcode::G_SADDE:
581 case TargetOpcode::G_USUBO:
582 case TargetOpcode::G_USUBE:
583 case TargetOpcode::G_SSUBO:
584 case TargetOpcode::G_SSUBE:
585 case TargetOpcode::G_UMULO:
586 case TargetOpcode::G_SMULO: {
587 if (
MI.getOperand(1).getReg() == R) {
597 case TargetOpcode::G_CTLZ:
598 case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
614 ComputeKnownBitsCache[R] = Known;
619 const APInt &DemandedElts,
623 if (Src1SignBits == 1)
629 const APInt &DemandedElts,
632 unsigned Opcode =
MI.getOpcode();
634 if (Opcode == TargetOpcode::G_CONSTANT)
635 return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
653 unsigned FirstAnswer = 1;
655 case TargetOpcode::COPY: {
657 if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
665 case TargetOpcode::G_SEXT: {
671 case TargetOpcode::G_ASSERT_SEXT:
672 case TargetOpcode::G_SEXT_INREG: {
675 unsigned SrcBits =
MI.getOperand(2).getImm();
676 unsigned InRegBits = TyBits - SrcBits + 1;
679 case TargetOpcode::G_SEXTLOAD: {
688 case TargetOpcode::G_ZEXTLOAD: {
697 case TargetOpcode::G_TRUNC: {
705 if (NumSrcSignBits > (NumSrcBits - DstTyBits))
706 return NumSrcSignBits - (NumSrcBits - DstTyBits);
709 case TargetOpcode::G_SELECT: {
710 return computeNumSignBitsMin(
MI.getOperand(2).getReg(),
711 MI.getOperand(3).getReg(), DemandedElts,
714 case TargetOpcode::G_SADDO:
715 case TargetOpcode::G_SADDE:
716 case TargetOpcode::G_UADDO:
717 case TargetOpcode::G_UADDE:
718 case TargetOpcode::G_SSUBO:
719 case TargetOpcode::G_SSUBE:
720 case TargetOpcode::G_USUBO:
721 case TargetOpcode::G_USUBE:
722 case TargetOpcode::G_SMULO:
723 case TargetOpcode::G_UMULO: {
727 if (
MI.getOperand(1).getReg() == R) {
735 case TargetOpcode::G_FCMP:
736 case TargetOpcode::G_ICMP: {
737 bool IsFP = Opcode == TargetOpcode::G_FCMP;
747 case TargetOpcode::G_INTRINSIC:
748 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
749 case TargetOpcode::G_INTRINSIC_CONVERGENT:
750 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
755 FirstAnswer = std::max(FirstAnswer, NumBits);
775 Mask <<= Mask.getBitWidth() - TyBits;
776 return std::max(FirstAnswer, Mask.countl_one());
799 Info = std::make_unique<GISelKnownBits>(MF,
MaxDepth);
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...
GISelKnownBits & get(MachineFunction &MF)
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
TypeSize getValue() 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.
const LLVMTargetMachine & getTarget() const
getTarget - Return the target machine this machine code is compiled with
Representation of each machine instruction.
A description of a memory reference used in the backend.
LLT getMemoryType() const
Return the memory type of the memory reference.
const MDNode * getRanges() const
Return the range tag for the memory reference.
LocationSize 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.
constexpr 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...
CodeGenOptLevel getOptLevel() const
Returns the optimization level: None, Less, Default, or Aggressive.
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 ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
bool isUnknown() const
Returns true if we don't know any bits.
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
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).
KnownBits zext(unsigned BitWidth) const
Return known bits for a zero extension of the value we're tracking.
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
KnownBits intersectWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for both this and RHS.
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.
static KnownBits computeForAddSub(bool Add, bool NSW, bool NUW, const KnownBits &LHS, const KnownBits &RHS)
Compute known bits resulting from adding LHS and RHS.
bool isNegative() const
Returns true if this value is known to be negative.
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
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 shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).