26#define DEBUG_TYPE "gisel-known-bits"
33 "Analysis for ComputingKnownBits",
false,
true)
36 : MF(MF),
MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
41 switch (
MI->getOpcode()) {
42 case TargetOpcode::COPY:
44 case TargetOpcode::G_ASSERT_ALIGN: {
46 return Align(
MI->getOperand(2).getImm());
48 case TargetOpcode::G_FRAME_INDEX: {
49 int FrameIdx =
MI->getOperand(1).getIndex();
52 case TargetOpcode::G_INTRINSIC:
53 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
54 case TargetOpcode::G_INTRINSIC_CONVERGENT:
55 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
62 assert(
MI.getNumExplicitDefs() == 1 &&
63 "expected single return generic instruction");
80 assert(ComputeKnownBitsCache.empty() &&
"Cache should have been cleared");
84 ComputeKnownBitsCache.clear();
103 <<
"] Computed for: " <<
MI <<
"[" <<
Depth <<
"] Known: 0x"
114 const APInt &DemandedElts,
145 const APInt &DemandedElts,
148 unsigned Opcode =
MI.getOpcode();
161 auto CacheEntry = ComputeKnownBitsCache.find(R);
162 if (CacheEntry != ComputeKnownBitsCache.end()) {
163 Known = CacheEntry->second;
192 case TargetOpcode::G_BUILD_VECTOR: {
195 for (
unsigned i = 0, e =
MI.getNumOperands() - 1; i < e; ++i) {
196 if (!DemandedElts[i])
211 case TargetOpcode::COPY:
212 case TargetOpcode::G_PHI:
213 case TargetOpcode::PHI: {
219 assert(
MI.getOperand(0).getSubReg() == 0 &&
"Is this code in SSA?");
232 for (
unsigned Idx = 1;
Idx <
MI.getNumOperands();
Idx += 2) {
242 if (SrcReg.
isVirtual() && Src.getSubReg() == 0 &&
246 Depth + (Opcode != TargetOpcode::COPY));
260 case TargetOpcode::G_CONSTANT: {
264 case TargetOpcode::G_FRAME_INDEX: {
265 int FrameIdx =
MI.getOperand(1).getIndex();
269 case TargetOpcode::G_SUB: {
275 false, Known, Known2);
278 case TargetOpcode::G_XOR: {
287 case TargetOpcode::G_PTR_ADD: {
296 case TargetOpcode::G_ADD: {
302 false, Known, Known2);
305 case TargetOpcode::G_AND: {
315 case TargetOpcode::G_OR: {
325 case TargetOpcode::G_MUL: {
333 case TargetOpcode::G_SELECT: {
334 computeKnownBitsMin(
MI.getOperand(2).getReg(),
MI.getOperand(3).getReg(),
335 Known, DemandedElts,
Depth + 1);
338 case TargetOpcode::G_SMIN: {
348 case TargetOpcode::G_SMAX: {
358 case TargetOpcode::G_UMIN: {
361 DemandedElts,
Depth + 1);
363 DemandedElts,
Depth + 1);
367 case TargetOpcode::G_UMAX: {
370 DemandedElts,
Depth + 1);
372 DemandedElts,
Depth + 1);
376 case TargetOpcode::G_FCMP:
377 case TargetOpcode::G_ICMP: {
381 Opcode == TargetOpcode::G_FCMP) ==
387 case TargetOpcode::G_SEXT: {
395 case TargetOpcode::G_ASSERT_SEXT:
396 case TargetOpcode::G_SEXT_INREG: {
399 Known = Known.
sextInReg(
MI.getOperand(2).getImm());
402 case TargetOpcode::G_ANYEXT: {
408 case TargetOpcode::G_LOAD: {
416 case TargetOpcode::G_SEXTLOAD:
417 case TargetOpcode::G_ZEXTLOAD: {
424 Known = Opcode == TargetOpcode::G_SEXTLOAD
429 case TargetOpcode::G_ASHR: {
438 case TargetOpcode::G_LSHR: {
447 case TargetOpcode::G_SHL: {
456 case TargetOpcode::G_INTTOPTR:
457 case TargetOpcode::G_PTRTOINT:
462 case TargetOpcode::G_ASSERT_ZEXT:
463 case TargetOpcode::G_ZEXT:
464 case TargetOpcode::G_TRUNC: {
467 unsigned SrcBitWidth;
470 if (Opcode == TargetOpcode::G_ASSERT_ZEXT)
471 SrcBitWidth =
MI.getOperand(2).getImm();
477 assert(SrcBitWidth &&
"SrcBitWidth can't be zero");
485 case TargetOpcode::G_ASSERT_ALIGN: {
486 int64_t LogOfAlign =
Log2_64(
MI.getOperand(2).getImm());
495 case TargetOpcode::G_MERGE_VALUES: {
496 unsigned NumOps =
MI.getNumOperands();
499 for (
unsigned I = 0;
I != NumOps - 1; ++
I) {
502 DemandedElts,
Depth + 1);
507 case TargetOpcode::G_UNMERGE_VALUES: {
510 unsigned NumOps =
MI.getNumOperands();
511 Register SrcReg =
MI.getOperand(NumOps - 1).getReg();
520 for (; DstIdx != NumOps - 1 &&
MI.getOperand(DstIdx).
getReg() != R;
527 case TargetOpcode::G_BSWAP: {
533 case TargetOpcode::G_BITREVERSE: {
539 case TargetOpcode::G_CTPOP: {
551 case TargetOpcode::G_UBFX: {
552 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
562 case TargetOpcode::G_SBFX: {
563 KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
575 false,
false,
false, ExtKnown, WidthKnown);
579 case TargetOpcode::G_UADDO:
580 case TargetOpcode::G_UADDE:
581 case TargetOpcode::G_SADDO:
582 case TargetOpcode::G_SADDE:
583 case TargetOpcode::G_USUBO:
584 case TargetOpcode::G_USUBE:
585 case TargetOpcode::G_SSUBO:
586 case TargetOpcode::G_SSUBE:
587 case TargetOpcode::G_UMULO:
588 case TargetOpcode::G_SMULO: {
589 if (
MI.getOperand(1).getReg() == R) {
599 case TargetOpcode::G_CTLZ:
600 case TargetOpcode::G_CTLZ_ZERO_UNDEF: {
615 ComputeKnownBitsCache[R] = Known;
620 const APInt &DemandedElts,
624 if (Src1SignBits == 1)
641 case TargetOpcode::G_SEXTLOAD:
644 case TargetOpcode::G_ZEXTLOAD:
657 const APInt &DemandedElts,
660 unsigned Opcode =
MI.getOpcode();
662 if (Opcode == TargetOpcode::G_CONSTANT)
663 return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
681 unsigned FirstAnswer = 1;
683 case TargetOpcode::COPY: {
685 if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
693 case TargetOpcode::G_SEXT: {
699 case TargetOpcode::G_ASSERT_SEXT:
700 case TargetOpcode::G_SEXT_INREG: {
703 unsigned SrcBits =
MI.getOperand(2).getImm();
704 unsigned InRegBits = TyBits - SrcBits + 1;
707 case TargetOpcode::G_LOAD: {
714 case TargetOpcode::G_SEXTLOAD: {
729 case TargetOpcode::G_ZEXTLOAD: {
744 case TargetOpcode::G_AND:
745 case TargetOpcode::G_OR:
746 case TargetOpcode::G_XOR: {
748 unsigned Src1NumSignBits =
750 if (Src1NumSignBits != 1) {
752 unsigned Src2NumSignBits =
754 FirstAnswer = std::min(Src1NumSignBits, Src2NumSignBits);
758 case TargetOpcode::G_TRUNC: {
766 if (NumSrcSignBits > (NumSrcBits - DstTyBits))
767 return NumSrcSignBits - (NumSrcBits - DstTyBits);
770 case TargetOpcode::G_SELECT: {
771 return computeNumSignBitsMin(
MI.getOperand(2).getReg(),
772 MI.getOperand(3).getReg(), DemandedElts,
775 case TargetOpcode::G_SADDO:
776 case TargetOpcode::G_SADDE:
777 case TargetOpcode::G_UADDO:
778 case TargetOpcode::G_UADDE:
779 case TargetOpcode::G_SSUBO:
780 case TargetOpcode::G_SSUBE:
781 case TargetOpcode::G_USUBO:
782 case TargetOpcode::G_USUBE:
783 case TargetOpcode::G_SMULO:
784 case TargetOpcode::G_UMULO: {
788 if (
MI.getOperand(1).getReg() == R) {
796 case TargetOpcode::G_FCMP:
797 case TargetOpcode::G_ICMP: {
798 bool IsFP = Opcode == TargetOpcode::G_FCMP;
808 case TargetOpcode::G_INTRINSIC:
809 case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
810 case TargetOpcode::G_INTRINSIC_CONVERGENT:
811 case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
816 FirstAnswer = std::max(FirstAnswer, NumBits);
836 Mask <<= Mask.getBitWidth() - TyBits;
837 return std::max(FirstAnswer, Mask.countl_one());
860 Info = std::make_unique<GISelKnownBits>(MF,
MaxDepth);
unsigned const MachineRegisterInfo * MRI
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
#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 unsigned computeNumSignBitsFromRangeMetadata(const GAnyLoad *Ld, unsigned TyBits)
Compute the known number of sign bits with attached range metadata in the memory operand.
static LLVM_ATTRIBUTE_UNUSED void dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth)
Provides analysis for querying information about KnownBits during GISel passes.
Declares convenience wrapper classes for interpreting MachineInstr instances as specific generic oper...
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.
unsigned getNumSignBits() const
Computes the number of leading bits of this APInt that are equal to its sign bit.
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.
This class represents a range of values.
ConstantRange zeroExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
APInt getSignedMin() const
Return the smallest signed value contained in the ConstantRange.
ConstantRange signExtend(uint32_t BitWidth) const
Return a new range in the specified integer type, which must be strictly larger than the current type...
APInt getSignedMax() const
Return the largest signed value contained in the ConstantRange.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
bool isNonIntegralAddressSpace(unsigned AddrSpace) const
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
Represents any generic load, including sign/zero extending variants.
const MDNode * getRanges() const
Returns the Ranges that describes the dereference.
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...
const DataLayout & getDataLayout() const
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.
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
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.
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.
ConstantRange getConstantRangeFromMetadata(const MDNode &RangeMD)
Parse out a conservative ConstantRange from !range metadata.
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
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).