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");
78 assert(ComputeKnownBitsCache.empty() &&
"Cache should have been cleared");
82 ComputeKnownBitsCache.clear();
101 <<
"] Computed for: " <<
MI <<
"[" <<
Depth <<
"] Known: 0x"
112 const APInt &DemandedElts,
143 const APInt &DemandedElts,
146 unsigned Opcode =
MI.getOpcode();
159 auto CacheEntry = ComputeKnownBitsCache.find(R);
160 if (CacheEntry != ComputeKnownBitsCache.end()) {
161 Known = CacheEntry->second;
190 case TargetOpcode::G_BUILD_VECTOR: {
193 for (
unsigned i = 0, e =
MI.getNumOperands() - 1; i < e; ++i) {
194 if (!DemandedElts[i])
209 case TargetOpcode::COPY:
210 case TargetOpcode::G_PHI:
211 case TargetOpcode::PHI: {
217 assert(
MI.getOperand(0).getSubReg() == 0 &&
"Is this code in SSA?");
230 for (
unsigned Idx = 1;
Idx <
MI.getNumOperands();
Idx += 2) {
240 if (SrcReg.
isVirtual() && Src.getSubReg() == 0 &&
244 Depth + (Opcode != TargetOpcode::COPY));
258 case TargetOpcode::G_CONSTANT: {
265 case TargetOpcode::G_FRAME_INDEX: {
266 int FrameIdx =
MI.getOperand(1).getIndex();
270 case TargetOpcode::G_SUB: {
276 false, Known, Known2);
279 case TargetOpcode::G_XOR: {
288 case TargetOpcode::G_PTR_ADD: {
297 case TargetOpcode::G_ADD: {
303 false, Known, Known2);
306 case TargetOpcode::G_AND: {
316 case TargetOpcode::G_OR: {
326 case TargetOpcode::G_MUL: {
334 case TargetOpcode::G_SELECT: {
335 computeKnownBitsMin(
MI.getOperand(2).getReg(),
MI.getOperand(3).getReg(),
336 Known, DemandedElts,
Depth + 1);
339 case TargetOpcode::G_SMIN: {
349 case TargetOpcode::G_SMAX: {
359 case TargetOpcode::G_UMIN: {
362 DemandedElts,
Depth + 1);
364 DemandedElts,
Depth + 1);
368 case TargetOpcode::G_UMAX: {
371 DemandedElts,
Depth + 1);
373 DemandedElts,
Depth + 1);
377 case TargetOpcode::G_FCMP:
378 case TargetOpcode::G_ICMP: {
382 Opcode == TargetOpcode::G_FCMP) ==
388 case TargetOpcode::G_SEXT: {
396 case TargetOpcode::G_ASSERT_SEXT:
397 case TargetOpcode::G_SEXT_INREG: {
400 Known = Known.
sextInReg(
MI.getOperand(2).getImm());
403 case TargetOpcode::G_ANYEXT: {
409 case TargetOpcode::G_LOAD: {
417 case TargetOpcode::G_SEXTLOAD:
418 case TargetOpcode::G_ZEXTLOAD: {
425 Known = Opcode == TargetOpcode::G_SEXTLOAD
430 case TargetOpcode::G_ASHR: {
439 case TargetOpcode::G_LSHR: {
448 case TargetOpcode::G_SHL: {
457 case TargetOpcode::G_INTTOPTR:
458 case TargetOpcode::G_PTRTOINT:
463 case TargetOpcode::G_ASSERT_ZEXT:
464 case TargetOpcode::G_ZEXT:
465 case TargetOpcode::G_TRUNC: {
468 unsigned SrcBitWidth;
471 if (Opcode == TargetOpcode::G_ASSERT_ZEXT)
472 SrcBitWidth =
MI.getOperand(2).getImm();
478 assert(SrcBitWidth &&
"SrcBitWidth can't be zero");
486 case TargetOpcode::G_ASSERT_ALIGN: {
487 int64_t LogOfAlign =
Log2_64(
MI.getOperand(2).getImm());
496 case TargetOpcode::G_MERGE_VALUES: {
497 unsigned NumOps =
MI.getNumOperands();
500 for (
unsigned I = 0;
I != NumOps - 1; ++
I) {
503 DemandedElts,
Depth + 1);
508 case TargetOpcode::G_UNMERGE_VALUES: {
511 unsigned NumOps =
MI.getNumOperands();
512 Register SrcReg =
MI.getOperand(NumOps - 1).getReg();
521 for (; DstIdx != NumOps - 1 &&
MI.getOperand(DstIdx).
getReg() != R;
528 case TargetOpcode::G_BSWAP: {
534 case TargetOpcode::G_BITREVERSE: {
540 case TargetOpcode::G_CTPOP: {
552 case TargetOpcode::G_UBFX: {
553 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
563 case TargetOpcode::G_SBFX: {
564 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
576 false,
false,
false, ExtKnown, WidthKnown);
580 case TargetOpcode::G_UADDO:
581 case TargetOpcode::G_UADDE:
582 case TargetOpcode::G_SADDO:
583 case TargetOpcode::G_SADDE:
584 case TargetOpcode::G_USUBO:
585 case TargetOpcode::G_USUBE:
586 case TargetOpcode::G_SSUBO:
587 case TargetOpcode::G_SSUBE:
588 case TargetOpcode::G_UMULO:
589 case TargetOpcode::G_SMULO: {
590 if (
MI.getOperand(1).getReg() == R) {
600 case TargetOpcode::G_CTLZ:
601 case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
617 ComputeKnownBitsCache[R] = Known;
622 const APInt &DemandedElts,
626 if (Src1SignBits == 1)
632 const APInt &DemandedElts,
635 unsigned Opcode =
MI.getOpcode();
637 if (Opcode == TargetOpcode::G_CONSTANT)
638 return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
656 unsigned FirstAnswer = 1;
658 case TargetOpcode::COPY: {
660 if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
668 case TargetOpcode::G_SEXT: {
674 case TargetOpcode::G_ASSERT_SEXT:
675 case TargetOpcode::G_SEXT_INREG: {
678 unsigned SrcBits =
MI.getOperand(2).getImm();
679 unsigned InRegBits = TyBits - SrcBits + 1;
682 case TargetOpcode::G_SEXTLOAD: {
691 case TargetOpcode::G_ZEXTLOAD: {
700 case TargetOpcode::G_AND:
701 case TargetOpcode::G_OR:
702 case TargetOpcode::G_XOR: {
704 unsigned Src1NumSignBits =
706 if (Src1NumSignBits != 1) {
708 unsigned Src2NumSignBits =
710 FirstAnswer = std::min(Src1NumSignBits, Src2NumSignBits);
714 case TargetOpcode::G_TRUNC: {
722 if (NumSrcSignBits > (NumSrcBits - DstTyBits))
723 return NumSrcSignBits - (NumSrcBits - DstTyBits);
726 case TargetOpcode::G_SELECT: {
727 return computeNumSignBitsMin(
MI.getOperand(2).getReg(),
728 MI.getOperand(3).getReg(), DemandedElts,
731 case TargetOpcode::G_SADDO:
732 case TargetOpcode::G_SADDE:
733 case TargetOpcode::G_UADDO:
734 case TargetOpcode::G_UADDE:
735 case TargetOpcode::G_SSUBO:
736 case TargetOpcode::G_SSUBE:
737 case TargetOpcode::G_USUBO:
738 case TargetOpcode::G_USUBE:
739 case TargetOpcode::G_SMULO:
740 case TargetOpcode::G_UMULO: {
744 if (
MI.getOperand(1).getReg() == R) {
752 case TargetOpcode::G_FCMP:
753 case TargetOpcode::G_ICMP: {
754 bool IsFP = Opcode == TargetOpcode::G_FCMP;
764 case TargetOpcode::G_INTRINSIC:
765 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
766 case TargetOpcode::G_INTRINSIC_CONVERGENT:
767 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
772 FirstAnswer = std::max(FirstAnswer, NumBits);
792 Mask <<= Mask.getBitWidth() - TyBits;
793 return std::max(FirstAnswer, Mask.countl_one());
816 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
constexpr bool isFixedVector() const
Returns true if the LLT is a fixed vector.
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).