LLVM  10.0.0svn
GISelKnownBits.cpp
Go to the documentation of this file.
1 //===- lib/CodeGen/GlobalISel/GISelKnownBits.cpp --------------*- C++ *-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 /// Provides analysis for querying information about KnownBits during GISel
10 /// passes.
11 //
12 //===------------------
20 
21 #define DEBUG_TYPE "gisel-known-bits"
22 
23 using namespace llvm;
24 
26 
28  "Analysis for ComputingKnownBits", false, true)
30  "Analysis for ComputingKnownBits", false, true)
31 
33  : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
34  DL(MF.getFunction().getParent()->getDataLayout()) {}
35 
37  const MachineFunction &MF) {
38  const MachineFrameInfo &MFI = MF.getFrameInfo();
39  return MinAlign(Offset, MFI.getObjectAlignment(FrameIdx));
40  // TODO: How to handle cases with Base + Offset?
41 }
42 
44  if (MI.getOpcode() == TargetOpcode::G_FRAME_INDEX) {
45  int FrameIdx = MI.getOperand(1).getIndex();
46  return inferAlignmentForFrameIdx(FrameIdx, 0, *MI.getMF());
47  }
48  return 0;
49 }
50 
52  const APInt &DemandedElts,
53  unsigned Depth) {
54  const MachineInstr &MI = *MRI.getVRegDef(R);
56 }
57 
59  unsigned Align) {
60  if (Align)
61  // The low bits are known zero if the pointer is aligned.
62  Known.Zero.setLowBits(Log2_32(Align));
63 }
64 
66  return getKnownBits(MI.getOperand(0).getReg());
67 }
68 
70  KnownBits Known;
71  LLT Ty = MRI.getType(R);
72  APInt DemandedElts =
74  computeKnownBitsImpl(R, Known, DemandedElts);
75  return Known;
76 }
77 
79  LLT Ty = MRI.getType(R);
80  unsigned BitWidth = Ty.getScalarSizeInBits();
81  return maskedValueIsZero(R, APInt::getSignMask(BitWidth));
82 }
83 
85  return getKnownBits(R).Zero;
86 }
87 
89 
91  const APInt &DemandedElts,
92  unsigned Depth) {
93  MachineInstr &MI = *MRI.getVRegDef(R);
94  unsigned Opcode = MI.getOpcode();
95  LLT DstTy = MRI.getType(R);
96 
97  // Handle the case where this is called on a register that does not have a
98  // type constraint (i.e. it has a register class constraint instead). This is
99  // unlikely to occur except by looking through copies but it is possible for
100  // the initial register being queried to be in this state.
101  if (!DstTy.isValid()) {
102  Known = KnownBits();
103  return;
104  }
105 
106  unsigned BitWidth = DstTy.getSizeInBits();
107  Known = KnownBits(BitWidth); // Don't know anything
108 
109  if (DstTy.isVector())
110  return; // TODO: Handle vectors.
111 
112  if (Depth == getMaxDepth())
113  return;
114 
115  if (!DemandedElts)
116  return; // No demanded elts, better to assume we don't know anything.
117 
118  KnownBits Known2;
119 
120  switch (Opcode) {
121  default:
122  TL.computeKnownBitsForTargetInstr(R, Known, DemandedElts, MRI, Depth);
123  break;
124  case TargetOpcode::COPY: {
125  MachineOperand Dst = MI.getOperand(0);
126  MachineOperand Src = MI.getOperand(1);
127  // Look through trivial copies but don't look through trivial copies of the
128  // form `%1:(s32) = OP %0:gpr32` known-bits analysis is currently unable to
129  // determine the bit width of a register class.
130  //
131  // We can't use NoSubRegister by name as it's defined by each target but
132  // it's always defined to be 0 by tablegen.
133  if (Dst.getSubReg() == 0 /*NoSubRegister*/ && Src.getReg().isVirtual() &&
134  Src.getSubReg() == 0 /*NoSubRegister*/ &&
135  MRI.getType(Src.getReg()).isValid()) {
136  // Don't increment Depth for this one since we didn't do any work.
137  computeKnownBitsImpl(Src.getReg(), Known, DemandedElts, Depth);
138  }
139  break;
140  }
141  case TargetOpcode::G_CONSTANT: {
142  auto CstVal = getConstantVRegVal(R, MRI);
143  if (!CstVal)
144  break;
145  Known.One = *CstVal;
146  Known.Zero = ~Known.One;
147  break;
148  }
149  case TargetOpcode::G_FRAME_INDEX: {
150  computeKnownBitsForFrameIndex(R, Known, DemandedElts);
151  break;
152  }
153  case TargetOpcode::G_SUB: {
154  // If low bits are known to be zero in both operands, then we know they are
155  // going to be 0 in the result. Both addition and complement operations
156  // preserve the low zero bits.
157  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
158  Depth + 1);
159  unsigned KnownZeroLow = Known2.countMinTrailingZeros();
160  if (KnownZeroLow == 0)
161  break;
162  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
163  Depth + 1);
164  KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
165  Known.Zero.setLowBits(KnownZeroLow);
166  break;
167  }
168  case TargetOpcode::G_XOR: {
169  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
170  Depth + 1);
171  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
172  Depth + 1);
173 
174  // Output known-0 bits are known if clear or set in both the LHS & RHS.
175  APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
176  // Output known-1 are known to be set if set in only one of the LHS, RHS.
177  Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
178  Known.Zero = KnownZeroOut;
179  break;
180  }
181  case TargetOpcode::G_GEP: {
182  // G_GEP is like G_ADD. FIXME: Is this true for all targets?
183  LLT Ty = MRI.getType(MI.getOperand(1).getReg());
185  break;
187  }
188  case TargetOpcode::G_ADD: {
189  // Output known-0 bits are known if clear or set in both the low clear bits
190  // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
191  // low 3 bits clear.
192  // Output known-0 bits are also known if the top bits of each input are
193  // known to be clear. For example, if one input has the top 10 bits clear
194  // and the other has the top 8 bits clear, we know the top 7 bits of the
195  // output must be clear.
196  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
197  Depth + 1);
198  unsigned KnownZeroHigh = Known2.countMinLeadingZeros();
199  unsigned KnownZeroLow = Known2.countMinTrailingZeros();
200  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
201  Depth + 1);
202  KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros());
203  KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
204  Known.Zero.setLowBits(KnownZeroLow);
205  if (KnownZeroHigh > 1)
206  Known.Zero.setHighBits(KnownZeroHigh - 1);
207  break;
208  }
209  case TargetOpcode::G_AND: {
210  // If either the LHS or the RHS are Zero, the result is zero.
211  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
212  Depth + 1);
213  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
214  Depth + 1);
215 
216  // Output known-1 bits are only known if set in both the LHS & RHS.
217  Known.One &= Known2.One;
218  // Output known-0 are known to be clear if zero in either the LHS | RHS.
219  Known.Zero |= Known2.Zero;
220  break;
221  }
222  case TargetOpcode::G_OR: {
223  // If either the LHS or the RHS are Zero, the result is zero.
224  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
225  Depth + 1);
226  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
227  Depth + 1);
228 
229  // Output known-0 bits are only known if clear in both the LHS & RHS.
230  Known.Zero &= Known2.Zero;
231  // Output known-1 are known to be set if set in either the LHS | RHS.
232  Known.One |= Known2.One;
233  break;
234  }
235  case TargetOpcode::G_MUL: {
236  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
237  Depth + 1);
238  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
239  Depth + 1);
240  // If low bits are zero in either operand, output low known-0 bits.
241  // Also compute a conservative estimate for high known-0 bits.
242  // More trickiness is possible, but this is sufficient for the
243  // interesting case of alignment computation.
244  unsigned TrailZ =
245  Known.countMinTrailingZeros() + Known2.countMinTrailingZeros();
246  unsigned LeadZ =
248  BitWidth) -
249  BitWidth;
250 
251  Known.resetAll();
252  Known.Zero.setLowBits(std::min(TrailZ, BitWidth));
253  Known.Zero.setHighBits(std::min(LeadZ, BitWidth));
254  break;
255  }
256  case TargetOpcode::G_SELECT: {
257  computeKnownBitsImpl(MI.getOperand(3).getReg(), Known, DemandedElts,
258  Depth + 1);
259  // If we don't know any bits, early out.
260  if (Known.isUnknown())
261  break;
262  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
263  Depth + 1);
264  // Only known if known in both the LHS and RHS.
265  Known.One &= Known2.One;
266  Known.Zero &= Known2.Zero;
267  break;
268  }
269  case TargetOpcode::G_FCMP:
270  case TargetOpcode::G_ICMP: {
271  if (TL.getBooleanContents(DstTy.isVector(),
272  Opcode == TargetOpcode::G_FCMP) ==
274  BitWidth > 1)
275  Known.Zero.setBitsFrom(1);
276  break;
277  }
278  case TargetOpcode::G_SEXT: {
279  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
280  Depth + 1);
281  // If the sign bit is known to be zero or one, then sext will extend
282  // it to the top bits, else it will just zext.
283  Known = Known.sext(BitWidth);
284  break;
285  }
286  case TargetOpcode::G_ANYEXT: {
287  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
288  Depth + 1);
289  Known = Known.zext(BitWidth, true /* ExtendedBitsAreKnownZero */);
290  break;
291  }
292  case TargetOpcode::G_LOAD: {
293  if (MI.hasOneMemOperand()) {
294  const MachineMemOperand *MMO = *MI.memoperands_begin();
295  if (const MDNode *Ranges = MMO->getRanges()) {
296  computeKnownBitsFromRangeMetadata(*Ranges, Known);
297  }
298  }
299  break;
300  }
301  case TargetOpcode::G_ZEXTLOAD: {
302  // Everything above the retrieved bits is zero
303  if (MI.hasOneMemOperand())
305  break;
306  }
307  case TargetOpcode::G_ASHR:
308  case TargetOpcode::G_LSHR:
309  case TargetOpcode::G_SHL: {
310  KnownBits RHSKnown;
311  computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
312  Depth + 1);
313  if (!RHSKnown.isConstant()) {
314  LLVM_DEBUG(
315  MachineInstr *RHSMI = MRI.getVRegDef(MI.getOperand(2).getReg());
316  dbgs() << '[' << Depth << "] Shift not known constant: " << *RHSMI);
317  break;
318  }
319  uint64_t Shift = RHSKnown.getConstant().getZExtValue();
320  LLVM_DEBUG(dbgs() << '[' << Depth << "] Shift is " << Shift << '\n');
321 
322  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
323  Depth + 1);
324 
325  switch (Opcode) {
326  case TargetOpcode::G_ASHR:
327  Known.Zero = Known.Zero.ashr(Shift);
328  Known.One = Known.One.ashr(Shift);
329  break;
330  case TargetOpcode::G_LSHR:
331  Known.Zero = Known.Zero.lshr(Shift);
332  Known.One = Known.One.lshr(Shift);
333  Known.Zero.setBitsFrom(Known.Zero.getBitWidth() - Shift);
334  break;
335  case TargetOpcode::G_SHL:
336  Known.Zero = Known.Zero.shl(Shift);
337  Known.One = Known.One.shl(Shift);
338  Known.Zero.setBits(0, Shift);
339  break;
340  }
341  break;
342  }
343  case TargetOpcode::G_INTTOPTR:
344  case TargetOpcode::G_PTRTOINT:
345  // Fall through and handle them the same as zext/trunc.
347  case TargetOpcode::G_ZEXT:
348  case TargetOpcode::G_TRUNC: {
349  Register SrcReg = MI.getOperand(1).getReg();
350  LLT SrcTy = MRI.getType(SrcReg);
351  unsigned SrcBitWidth = SrcTy.isPointer()
352  ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
353  : SrcTy.getSizeInBits();
354  assert(SrcBitWidth && "SrcBitWidth can't be zero");
355  Known = Known.zextOrTrunc(SrcBitWidth, true);
356  computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
357  Known = Known.zextOrTrunc(BitWidth, true);
358  if (BitWidth > SrcBitWidth)
359  Known.Zero.setBitsFrom(SrcBitWidth);
360  break;
361  }
362  }
363 
364  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
365  LLVM_DEBUG(dbgs() << "[" << Depth << "] Compute known bits: " << MI << "["
366  << Depth << "] Computed for: " << MI << "[" << Depth
367  << "] Known: 0x"
368  << (Known.Zero | Known.One).toString(16, false) << "\n"
369  << "[" << Depth << "] Zero: 0x"
370  << Known.Zero.toString(16, false) << "\n"
371  << "[" << Depth << "] One: 0x"
372  << Known.One.toString(16, false) << "\n");
373 }
374 
376  AU.setPreservesAll();
378 }
379 
381  return false;
382 }
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
Definition: DataLayout.h:399
bool maskedValueIsZero(Register Val, const APInt &Mask)
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1571
GCNRegPressure max(const GCNRegPressure &P1, const GCNRegPressure &P2)
static APInt getAllOnesValue(unsigned numBits)
Get the all-ones value.
Definition: APInt.h:561
void setBits(unsigned loBit, unsigned hiBit)
Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
Definition: APInt.h:1417
const MachineFunction * getMF() const
Return the function that contains the basic block that this instruction belongs to.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
unsigned getScalarSizeInBits() const
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:46
Analysis for ComputingKnownBits
unsigned getSizeInBits(Register Reg, const MachineRegisterInfo &MRI, const TargetRegisterInfo &TRI) const
Get the size in bits of Reg.
unsigned getSubReg() const
LLT getType(unsigned Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register...
bool isNonIntegralAddressSpace(unsigned AddrSpace) const
Definition: DataLayout.h:372
Metadata node.
Definition: Metadata.h:863
block Block Frequency true
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...
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
Definition: APInt.h:1436
static unsigned inferAlignmentForFrameIdx(int FrameIdx, int Offset, const MachineFunction &MF)
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1517
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:146
bool isVector() const
A description of a memory reference used in the backend.
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
Definition: APInt.h:1446
unsigned getMaxDepth() const
APInt shl(unsigned shiftAmt) const
Left-shift function.
Definition: APInt.h:992
const MDNode * getRanges() const
Return the range tag for the memory reference.
#define DEBUG_TYPE
Provides analysis for querying information about KnownBits during GISel passes.
The MachineFrameInfo class represents an abstract stack frame until prolog/epilog code is inserted...
unsigned getOpcode() const
Returns the opcode of this MachineInstr.
Definition: MachineInstr.h:411
KnownBits zextOrTrunc(unsigned BitWidth, bool ExtendedBitsAreKnownZero) const
Extends or truncates the underlying known Zero and One bits.
Definition: KnownBits.h:138
MachineInstr * getVRegDef(unsigned Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
void computeKnownBitsForFrameIndex(Register R, KnownBits &Known, const APInt &DemandedElts, unsigned Depth=0)
INITIALIZE_PASS_BEGIN(GISelKnownBitsAnalysis, DEBUG_TYPE, "Analysis for ComputingKnownBits", false, true) INITIALIZE_PASS_END(GISelKnownBitsAnalysis
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:89
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:258
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
To use KnownBitsInfo analysis in a pass, KnownBitsInfo &Info = getAnalysis<GISelKnownBitsInfoAnalysis...
APInt getKnownZeroes(Register R)
constexpr uint64_t MinAlign(uint64_t A, uint64_t B)
A and B are either alignments or offsets.
Definition: MathExtras.h:614
bool signBitIsZero(Register Op)
unsigned getObjectAlignment(int ObjectIdx) const
Return the alignment of the specified stack object.
unsigned const MachineRegisterInfo * MRI
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
KnownBits zext(unsigned BitWidth, bool ExtendedBitsAreKnownZero) const
Extends the underlying known Zero and One bits.
Definition: KnownBits.h:120
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
void resetAll()
Resets the known state of all bits.
Definition: KnownBits.h:65
const APInt & getConstant() const
Returns the value when all bits have a known value.
Definition: KnownBits.h:56
KnownBits getKnownBits(Register R)
Represent the analysis usage information of a pass.
bool hasOneMemOperand() const
Return true if this instruction has exactly one MachineMemOperand.
Definition: MachineInstr.h:567
bool isConstant() const
Returns true if we know the value of all bits.
Definition: KnownBits.h:49
bool isValid() const
unsigned getAddressSpace() const
INITIALIZE_PASS_END(RegBankSelect, DEBUG_TYPE, "Assign register bank of generic virtual registers", false, false) RegBankSelect
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:40
APInt lshr(unsigned shiftAmt) const
Logical right-shift function.
Definition: APInt.h:970
APInt getKnownOnes(Register R)
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:554
APInt ashr(unsigned ShiftAmt) const
Arithmetic right-shift function.
Definition: APInt.h:946
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:552
MachineOperand class - Representation of each machine instruction operand.
unsigned getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
KnownBits sext(unsigned BitWidth) const
Sign extends the underlying known Zero and One bits.
Definition: KnownBits.h:130
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:538
static unsigned inferPtrAlignment(const MachineInstr &MI)
Class for arbitrary precision integers.
Definition: APInt.h:69
void setPreservesAll()
Set by analyses that do not transform their input at all.
Optional< int64_t > getConstantVRegVal(unsigned VReg, const MachineRegisterInfo &MRI)
If VReg is defined by a G_CONSTANT fits in int64_t returns it.
Definition: Utils.cpp:207
bool isPointer() const
bool isUnknown() const
Returns true if we don&#39;t know any bits.
Definition: KnownBits.h:62
virtual void computeKnownBitsImpl(Register R, KnownBits &Known, const APInt &DemandedElts, unsigned Depth=0)
Representation of each machine instruction.
Definition: MachineInstr.h:64
static void computeKnownBitsForAlignment(KnownBits &Known, unsigned Align)
virtual void computeKnownBitsForTargetInstr(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...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:265
static const Function * getParent(const Value *V)
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:156
IRTranslator LLVM IR MI
Register getReg() const
getReg - Returns the register number.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
for(unsigned i=Desc.getNumOperands(), e=OldMI.getNumOperands();i !=e;++i)
const MachineOperand & getOperand(unsigned i) const
Definition: MachineInstr.h:416
void toString(SmallVectorImpl< char > &Str, unsigned Radix, bool Signed, bool formatAsCLiteral=false) const
Converts an APInt to a string and append it to Str.
Definition: APInt.cpp:2103
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
Definition: APInt.h:1441
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
This file describes how to lower LLVM code to machine code.