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 commonAlignment(Align(MFI.getObjectAlignment(FrameIdx)), Offset);
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 None;
49 }
50 
52  const APInt &DemandedElts,
53  unsigned Depth) {
54  const MachineInstr &MI = *MRI.getVRegDef(R);
56 }
57 
59  MaybeAlign Alignment) {
60  if (Alignment)
61  // The low bits are known zero if the pointer is aligned.
62  Known.Zero.setLowBits(Log2(Alignment));
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(*this, R, Known, DemandedElts, MRI,
123  Depth);
124  break;
125  case TargetOpcode::COPY: {
126  MachineOperand Dst = MI.getOperand(0);
127  MachineOperand Src = MI.getOperand(1);
128  // Look through trivial copies but don't look through trivial copies of the
129  // form `%1:(s32) = OP %0:gpr32` known-bits analysis is currently unable to
130  // determine the bit width of a register class.
131  //
132  // We can't use NoSubRegister by name as it's defined by each target but
133  // it's always defined to be 0 by tablegen.
134  if (Dst.getSubReg() == 0 /*NoSubRegister*/ && Src.getReg().isVirtual() &&
135  Src.getSubReg() == 0 /*NoSubRegister*/ &&
136  MRI.getType(Src.getReg()).isValid()) {
137  // Don't increment Depth for this one since we didn't do any work.
138  computeKnownBitsImpl(Src.getReg(), Known, DemandedElts, Depth);
139  }
140  break;
141  }
142  case TargetOpcode::G_CONSTANT: {
143  auto CstVal = getConstantVRegVal(R, MRI);
144  if (!CstVal)
145  break;
146  Known.One = *CstVal;
147  Known.Zero = ~Known.One;
148  break;
149  }
150  case TargetOpcode::G_FRAME_INDEX: {
151  computeKnownBitsForFrameIndex(R, Known, DemandedElts);
152  break;
153  }
154  case TargetOpcode::G_SUB: {
155  // If low bits are known to be zero in both operands, then we know they are
156  // going to be 0 in the result. Both addition and complement operations
157  // preserve the low zero bits.
158  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
159  Depth + 1);
160  unsigned KnownZeroLow = Known2.countMinTrailingZeros();
161  if (KnownZeroLow == 0)
162  break;
163  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
164  Depth + 1);
165  KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
166  Known.Zero.setLowBits(KnownZeroLow);
167  break;
168  }
169  case TargetOpcode::G_XOR: {
170  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
171  Depth + 1);
172  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
173  Depth + 1);
174 
175  // Output known-0 bits are known if clear or set in both the LHS & RHS.
176  APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
177  // Output known-1 are known to be set if set in only one of the LHS, RHS.
178  Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
179  Known.Zero = KnownZeroOut;
180  break;
181  }
182  case TargetOpcode::G_GEP: {
183  // G_GEP is like G_ADD. FIXME: Is this true for all targets?
184  LLT Ty = MRI.getType(MI.getOperand(1).getReg());
186  break;
188  }
189  case TargetOpcode::G_ADD: {
190  // Output known-0 bits are known if clear or set in both the low clear bits
191  // common to both LHS & RHS. For example, 8+(X<<3) is known to have the
192  // low 3 bits clear.
193  // Output known-0 bits are also known if the top bits of each input are
194  // known to be clear. For example, if one input has the top 10 bits clear
195  // and the other has the top 8 bits clear, we know the top 7 bits of the
196  // output must be clear.
197  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
198  Depth + 1);
199  unsigned KnownZeroHigh = Known2.countMinLeadingZeros();
200  unsigned KnownZeroLow = Known2.countMinTrailingZeros();
201  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
202  Depth + 1);
203  KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros());
204  KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
205  Known.Zero.setLowBits(KnownZeroLow);
206  if (KnownZeroHigh > 1)
207  Known.Zero.setHighBits(KnownZeroHigh - 1);
208  break;
209  }
210  case TargetOpcode::G_AND: {
211  // If either the LHS or the RHS are Zero, the result is zero.
212  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
213  Depth + 1);
214  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
215  Depth + 1);
216 
217  // Output known-1 bits are only known if set in both the LHS & RHS.
218  Known.One &= Known2.One;
219  // Output known-0 are known to be clear if zero in either the LHS | RHS.
220  Known.Zero |= Known2.Zero;
221  break;
222  }
223  case TargetOpcode::G_OR: {
224  // If either the LHS or the RHS are Zero, the result is zero.
225  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
226  Depth + 1);
227  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
228  Depth + 1);
229 
230  // Output known-0 bits are only known if clear in both the LHS & RHS.
231  Known.Zero &= Known2.Zero;
232  // Output known-1 are known to be set if set in either the LHS | RHS.
233  Known.One |= Known2.One;
234  break;
235  }
236  case TargetOpcode::G_MUL: {
237  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
238  Depth + 1);
239  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
240  Depth + 1);
241  // If low bits are zero in either operand, output low known-0 bits.
242  // Also compute a conservative estimate for high known-0 bits.
243  // More trickiness is possible, but this is sufficient for the
244  // interesting case of alignment computation.
245  unsigned TrailZ =
246  Known.countMinTrailingZeros() + Known2.countMinTrailingZeros();
247  unsigned LeadZ =
249  BitWidth) -
250  BitWidth;
251 
252  Known.resetAll();
253  Known.Zero.setLowBits(std::min(TrailZ, BitWidth));
254  Known.Zero.setHighBits(std::min(LeadZ, BitWidth));
255  break;
256  }
257  case TargetOpcode::G_SELECT: {
258  computeKnownBitsImpl(MI.getOperand(3).getReg(), Known, DemandedElts,
259  Depth + 1);
260  // If we don't know any bits, early out.
261  if (Known.isUnknown())
262  break;
263  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
264  Depth + 1);
265  // Only known if known in both the LHS and RHS.
266  Known.One &= Known2.One;
267  Known.Zero &= Known2.Zero;
268  break;
269  }
270  case TargetOpcode::G_FCMP:
271  case TargetOpcode::G_ICMP: {
272  if (TL.getBooleanContents(DstTy.isVector(),
273  Opcode == TargetOpcode::G_FCMP) ==
275  BitWidth > 1)
276  Known.Zero.setBitsFrom(1);
277  break;
278  }
279  case TargetOpcode::G_SEXT: {
280  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
281  Depth + 1);
282  // If the sign bit is known to be zero or one, then sext will extend
283  // it to the top bits, else it will just zext.
284  Known = Known.sext(BitWidth);
285  break;
286  }
287  case TargetOpcode::G_ANYEXT: {
288  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
289  Depth + 1);
290  Known = Known.zext(BitWidth, true /* ExtendedBitsAreKnownZero */);
291  break;
292  }
293  case TargetOpcode::G_LOAD: {
294  if (MI.hasOneMemOperand()) {
295  const MachineMemOperand *MMO = *MI.memoperands_begin();
296  if (const MDNode *Ranges = MMO->getRanges()) {
297  computeKnownBitsFromRangeMetadata(*Ranges, Known);
298  }
299  }
300  break;
301  }
302  case TargetOpcode::G_ZEXTLOAD: {
303  // Everything above the retrieved bits is zero
304  if (MI.hasOneMemOperand())
306  break;
307  }
308  case TargetOpcode::G_ASHR:
309  case TargetOpcode::G_LSHR:
310  case TargetOpcode::G_SHL: {
311  KnownBits RHSKnown;
312  computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
313  Depth + 1);
314  if (!RHSKnown.isConstant()) {
315  LLVM_DEBUG(
316  MachineInstr *RHSMI = MRI.getVRegDef(MI.getOperand(2).getReg());
317  dbgs() << '[' << Depth << "] Shift not known constant: " << *RHSMI);
318  break;
319  }
320  uint64_t Shift = RHSKnown.getConstant().getZExtValue();
321  LLVM_DEBUG(dbgs() << '[' << Depth << "] Shift is " << Shift << '\n');
322 
323  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
324  Depth + 1);
325 
326  switch (Opcode) {
327  case TargetOpcode::G_ASHR:
328  Known.Zero = Known.Zero.ashr(Shift);
329  Known.One = Known.One.ashr(Shift);
330  break;
331  case TargetOpcode::G_LSHR:
332  Known.Zero = Known.Zero.lshr(Shift);
333  Known.One = Known.One.lshr(Shift);
334  Known.Zero.setBitsFrom(Known.Zero.getBitWidth() - Shift);
335  break;
336  case TargetOpcode::G_SHL:
337  Known.Zero = Known.Zero.shl(Shift);
338  Known.One = Known.One.shl(Shift);
339  Known.Zero.setBits(0, Shift);
340  break;
341  }
342  break;
343  }
344  case TargetOpcode::G_INTTOPTR:
345  case TargetOpcode::G_PTRTOINT:
346  // Fall through and handle them the same as zext/trunc.
348  case TargetOpcode::G_ZEXT:
349  case TargetOpcode::G_TRUNC: {
350  Register SrcReg = MI.getOperand(1).getReg();
351  LLT SrcTy = MRI.getType(SrcReg);
352  unsigned SrcBitWidth = SrcTy.isPointer()
353  ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
354  : SrcTy.getSizeInBits();
355  assert(SrcBitWidth && "SrcBitWidth can't be zero");
356  Known = Known.zextOrTrunc(SrcBitWidth, true);
357  computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
358  Known = Known.zextOrTrunc(BitWidth, true);
359  if (BitWidth > SrcBitWidth)
360  Known.Zero.setBitsFrom(SrcBitWidth);
361  break;
362  }
363  }
364 
365  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
366  LLVM_DEBUG(dbgs() << "[" << Depth << "] Compute known bits: " << MI << "["
367  << Depth << "] Computed for: " << MI << "[" << Depth
368  << "] Known: 0x"
369  << (Known.Zero | Known.One).toString(16, false) << "\n"
370  << "[" << Depth << "] Zero: 0x"
371  << Known.Zero.toString(16, false) << "\n"
372  << "[" << Depth << "] One: 0x"
373  << Known.One.toString(16, false) << "\n");
374 }
375 
377  AU.setPreservesAll();
379 }
380 
382  return false;
383 }
unsigned Log2(Align A)
Returns the log2 of the alignment.
Definition: Alignment.h:204
constexpr char Align[]
Key for Kernel::Arg::Metadata::mAlign.
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
Definition: DataLayout.h:402
bool maskedValueIsZero(Register Val, const APInt &Mask)
uint64_t getZExtValue() const
Get zero extended value.
Definition: APInt.h:1571
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:375
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
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.
static MaybeAlign inferPtrAlignment(const MachineInstr &MI)
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.
static void computeKnownBitsForAlignment(KnownBits &Known, MaybeAlign Alignment)
#define DEBUG_TYPE
Provides analysis for querying information about KnownBits during GISel passes.
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...
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:410
Align commonAlignment(Align A, Align B)
Returns the alignment that satisfies both alignments.
Definition: Alignment.h:215
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)
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:566
bool isConstant() const
Returns true if we know the value of all bits.
Definition: KnownBits.h:49
bool isValid() const
static Align inferAlignmentForFrameIdx(int FrameIdx, int Offset, const MachineFunction &MF)
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
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:390
mmo_iterator memoperands_begin() const
Access to memory operands of the instruction.
Definition: MachineInstr.h:551
This struct is a compact representation of a valid (power of two) or undefined (0) alignment...
Definition: Alignment.h:117
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
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:63
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:273
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:415
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.