LLVM  14.0.0git
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 #include "llvm/IR/Module.h"
21 
22 #define DEBUG_TYPE "gisel-known-bits"
23 
24 using namespace llvm;
25 
27 
29  "Analysis for ComputingKnownBits", false, true)
30 
32  : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
33  DL(MF.getFunction().getParent()->getDataLayout()), MaxDepth(MaxDepth) {}
34 
36  const MachineInstr *MI = MRI.getVRegDef(R);
37  switch (MI->getOpcode()) {
38  case TargetOpcode::COPY:
39  return computeKnownAlignment(MI->getOperand(1).getReg(), Depth);
40  case TargetOpcode::G_FRAME_INDEX: {
41  int FrameIdx = MI->getOperand(1).getIndex();
42  return MF.getFrameInfo().getObjectAlign(FrameIdx);
43  }
44  case TargetOpcode::G_INTRINSIC:
45  case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
46  default:
47  return TL.computeKnownAlignForTargetInstr(*this, R, MRI, Depth + 1);
48  }
49 }
50 
52  assert(MI.getNumExplicitDefs() == 1 &&
53  "expected single return generic instruction");
54  return getKnownBits(MI.getOperand(0).getReg());
55 }
56 
58  const LLT Ty = MRI.getType(R);
59  APInt DemandedElts =
60  Ty.isVector() ? APInt::getAllOnes(Ty.getNumElements()) : APInt(1, 1);
61  return getKnownBits(R, DemandedElts);
62 }
63 
65  unsigned Depth) {
66  // For now, we only maintain the cache during one request.
67  assert(ComputeKnownBitsCache.empty() && "Cache should have been cleared");
68 
69  KnownBits Known;
70  computeKnownBitsImpl(R, Known, DemandedElts);
71  ComputeKnownBitsCache.clear();
72  return Known;
73 }
74 
76  LLT Ty = MRI.getType(R);
77  unsigned BitWidth = Ty.getScalarSizeInBits();
79 }
80 
82  return getKnownBits(R).Zero;
83 }
84 
86 
87 LLVM_ATTRIBUTE_UNUSED static void
88 dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth) {
89  dbgs() << "[" << Depth << "] Compute known bits: " << MI << "[" << Depth
90  << "] Computed for: " << MI << "[" << Depth << "] Known: 0x"
91  << toString(Known.Zero | Known.One, 16, false) << "\n"
92  << "[" << Depth << "] Zero: 0x" << toString(Known.Zero, 16, false)
93  << "\n"
94  << "[" << Depth << "] One: 0x" << toString(Known.One, 16, false)
95  << "\n";
96 }
97 
98 /// Compute known bits for the intersection of \p Src0 and \p Src1
99 void GISelKnownBits::computeKnownBitsMin(Register Src0, Register Src1,
100  KnownBits &Known,
101  const APInt &DemandedElts,
102  unsigned Depth) {
103  // Test src1 first, since we canonicalize simpler expressions to the RHS.
104  computeKnownBitsImpl(Src1, Known, DemandedElts, Depth);
105 
106  // If we don't know any bits, early out.
107  if (Known.isUnknown())
108  return;
109 
110  KnownBits Known2;
111  computeKnownBitsImpl(Src0, Known2, DemandedElts, Depth);
112 
113  // Only known if known in both the LHS and RHS.
114  Known = KnownBits::commonBits(Known, Known2);
115 }
116 
117 // Bitfield extract is computed as (Src >> Offset) & Mask, where Mask is
118 // created using Width. Use this function when the inputs are KnownBits
119 // objects. TODO: Move this KnownBits.h if this is usable in more cases.
120 static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown,
121  const KnownBits &OffsetKnown,
122  const KnownBits &WidthKnown) {
128  return KnownBits::lshr(SrcOpKnown, OffsetKnown) & Mask;
129 }
130 
132  const APInt &DemandedElts,
133  unsigned Depth) {
134  MachineInstr &MI = *MRI.getVRegDef(R);
135  unsigned Opcode = MI.getOpcode();
136  LLT DstTy = MRI.getType(R);
137 
138  // Handle the case where this is called on a register that does not have a
139  // type constraint (i.e. it has a register class constraint instead). This is
140  // unlikely to occur except by looking through copies but it is possible for
141  // the initial register being queried to be in this state.
142  if (!DstTy.isValid()) {
143  Known = KnownBits();
144  return;
145  }
146 
147  unsigned BitWidth = DstTy.getScalarSizeInBits();
148  auto CacheEntry = ComputeKnownBitsCache.find(R);
149  if (CacheEntry != ComputeKnownBitsCache.end()) {
150  Known = CacheEntry->second;
151  LLVM_DEBUG(dbgs() << "Cache hit at ");
152  LLVM_DEBUG(dumpResult(MI, Known, Depth));
153  assert(Known.getBitWidth() == BitWidth && "Cache entry size doesn't match");
154  return;
155  }
156  Known = KnownBits(BitWidth); // Don't know anything
157 
158  // Depth may get bigger than max depth if it gets passed to a different
159  // GISelKnownBits object.
160  // This may happen when say a generic part uses a GISelKnownBits object
161  // with some max depth, but then we hit TL.computeKnownBitsForTargetInstr
162  // which creates a new GISelKnownBits object with a different and smaller
163  // depth. If we just check for equality, we would never exit if the depth
164  // that is passed down to the target specific GISelKnownBits object is
165  // already bigger than its max depth.
166  if (Depth >= getMaxDepth())
167  return;
168 
169  if (!DemandedElts)
170  return; // No demanded elts, better to assume we don't know anything.
171 
172  KnownBits Known2;
173 
174  switch (Opcode) {
175  default:
176  TL.computeKnownBitsForTargetInstr(*this, R, Known, DemandedElts, MRI,
177  Depth);
178  break;
179  case TargetOpcode::G_BUILD_VECTOR: {
180  // Collect the known bits that are shared by every demanded vector element.
181  Known.Zero.setAllBits(); Known.One.setAllBits();
182  for (unsigned i = 0, e = MI.getNumOperands() - 1; i < e; ++i) {
183  if (!DemandedElts[i])
184  continue;
185 
186  computeKnownBitsImpl(MI.getOperand(i + 1).getReg(), Known2, DemandedElts,
187  Depth + 1);
188 
189  // Known bits are the values that are shared by every demanded element.
190  Known = KnownBits::commonBits(Known, Known2);
191 
192  // If we don't know any bits, early out.
193  if (Known.isUnknown())
194  break;
195  }
196  break;
197  }
198  case TargetOpcode::COPY:
199  case TargetOpcode::G_PHI:
200  case TargetOpcode::PHI: {
201  Known.One = APInt::getAllOnes(BitWidth);
203  // Destination registers should not have subregisters at this
204  // point of the pipeline, otherwise the main live-range will be
205  // defined more than once, which is against SSA.
206  assert(MI.getOperand(0).getSubReg() == 0 && "Is this code in SSA?");
207  // Record in the cache that we know nothing for MI.
208  // This will get updated later and in the meantime, if we reach that
209  // phi again, because of a loop, we will cut the search thanks to this
210  // cache entry.
211  // We could actually build up more information on the phi by not cutting
212  // the search, but that additional information is more a side effect
213  // than an intended choice.
214  // Therefore, for now, save on compile time until we derive a proper way
215  // to derive known bits for PHIs within loops.
216  ComputeKnownBitsCache[R] = KnownBits(BitWidth);
217  // PHI's operand are a mix of registers and basic blocks interleaved.
218  // We only care about the register ones.
219  for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
220  const MachineOperand &Src = MI.getOperand(Idx);
221  Register SrcReg = Src.getReg();
222  // Look through trivial copies and phis but don't look through trivial
223  // copies or phis of the form `%1:(s32) = OP %0:gpr32`, known-bits
224  // analysis is currently unable to determine the bit width of a
225  // register class.
226  //
227  // We can't use NoSubRegister by name as it's defined by each target but
228  // it's always defined to be 0 by tablegen.
229  if (SrcReg.isVirtual() && Src.getSubReg() == 0 /*NoSubRegister*/ &&
230  MRI.getType(SrcReg).isValid()) {
231  // For COPYs we don't do anything, don't increase the depth.
232  computeKnownBitsImpl(SrcReg, Known2, DemandedElts,
233  Depth + (Opcode != TargetOpcode::COPY));
234  Known = KnownBits::commonBits(Known, Known2);
235  // If we reach a point where we don't know anything
236  // just stop looking through the operands.
237  if (Known.One == 0 && Known.Zero == 0)
238  break;
239  } else {
240  // We know nothing.
241  Known = KnownBits(BitWidth);
242  break;
243  }
244  }
245  break;
246  }
247  case TargetOpcode::G_CONSTANT: {
248  auto CstVal = getIConstantVRegVal(R, MRI);
249  if (!CstVal)
250  break;
251  Known = KnownBits::makeConstant(*CstVal);
252  break;
253  }
254  case TargetOpcode::G_FRAME_INDEX: {
255  int FrameIdx = MI.getOperand(1).getIndex();
256  TL.computeKnownBitsForFrameIndex(FrameIdx, Known, MF);
257  break;
258  }
259  case TargetOpcode::G_SUB: {
260  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
261  Depth + 1);
262  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
263  Depth + 1);
264  Known = KnownBits::computeForAddSub(/*Add*/ false, /*NSW*/ false, Known,
265  Known2);
266  break;
267  }
268  case TargetOpcode::G_XOR: {
269  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
270  Depth + 1);
271  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
272  Depth + 1);
273 
274  Known ^= Known2;
275  break;
276  }
277  case TargetOpcode::G_PTR_ADD: {
278  if (DstTy.isVector())
279  break;
280  // G_PTR_ADD is like G_ADD. FIXME: Is this true for all targets?
281  LLT Ty = MRI.getType(MI.getOperand(1).getReg());
283  break;
285  }
286  case TargetOpcode::G_ADD: {
287  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
288  Depth + 1);
289  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
290  Depth + 1);
291  Known =
292  KnownBits::computeForAddSub(/*Add*/ true, /*NSW*/ false, Known, Known2);
293  break;
294  }
295  case TargetOpcode::G_AND: {
296  // If either the LHS or the RHS are Zero, the result is zero.
297  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
298  Depth + 1);
299  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
300  Depth + 1);
301 
302  Known &= Known2;
303  break;
304  }
305  case TargetOpcode::G_OR: {
306  // If either the LHS or the RHS are Zero, the result is zero.
307  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
308  Depth + 1);
309  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
310  Depth + 1);
311 
312  Known |= Known2;
313  break;
314  }
315  case TargetOpcode::G_MUL: {
316  computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
317  Depth + 1);
318  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
319  Depth + 1);
320  Known = KnownBits::mul(Known, Known2);
321  break;
322  }
323  case TargetOpcode::G_SELECT: {
324  computeKnownBitsMin(MI.getOperand(2).getReg(), MI.getOperand(3).getReg(),
325  Known, DemandedElts, Depth + 1);
326  break;
327  }
328  case TargetOpcode::G_SMIN: {
329  // TODO: Handle clamp pattern with number of sign bits
330  KnownBits KnownRHS;
331  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
332  Depth + 1);
333  computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
334  Depth + 1);
335  Known = KnownBits::smin(Known, KnownRHS);
336  break;
337  }
338  case TargetOpcode::G_SMAX: {
339  // TODO: Handle clamp pattern with number of sign bits
340  KnownBits KnownRHS;
341  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
342  Depth + 1);
343  computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
344  Depth + 1);
345  Known = KnownBits::smax(Known, KnownRHS);
346  break;
347  }
348  case TargetOpcode::G_UMIN: {
349  KnownBits KnownRHS;
350  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
351  DemandedElts, Depth + 1);
352  computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
353  DemandedElts, Depth + 1);
354  Known = KnownBits::umin(Known, KnownRHS);
355  break;
356  }
357  case TargetOpcode::G_UMAX: {
358  KnownBits KnownRHS;
359  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
360  DemandedElts, Depth + 1);
361  computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
362  DemandedElts, Depth + 1);
363  Known = KnownBits::umax(Known, KnownRHS);
364  break;
365  }
366  case TargetOpcode::G_FCMP:
367  case TargetOpcode::G_ICMP: {
368  if (DstTy.isVector())
369  break;
370  if (TL.getBooleanContents(DstTy.isVector(),
371  Opcode == TargetOpcode::G_FCMP) ==
373  BitWidth > 1)
374  Known.Zero.setBitsFrom(1);
375  break;
376  }
377  case TargetOpcode::G_SEXT: {
378  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
379  Depth + 1);
380  // If the sign bit is known to be zero or one, then sext will extend
381  // it to the top bits, else it will just zext.
382  Known = Known.sext(BitWidth);
383  break;
384  }
385  case TargetOpcode::G_ASSERT_SEXT:
386  case TargetOpcode::G_SEXT_INREG: {
387  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
388  Depth + 1);
389  Known = Known.sextInReg(MI.getOperand(2).getImm());
390  break;
391  }
392  case TargetOpcode::G_ANYEXT: {
393  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
394  Depth + 1);
395  Known = Known.anyext(BitWidth);
396  break;
397  }
398  case TargetOpcode::G_LOAD: {
399  const MachineMemOperand *MMO = *MI.memoperands_begin();
400  if (const MDNode *Ranges = MMO->getRanges()) {
401  computeKnownBitsFromRangeMetadata(*Ranges, Known);
402  }
403 
404  break;
405  }
406  case TargetOpcode::G_ZEXTLOAD: {
407  if (DstTy.isVector())
408  break;
409  // Everything above the retrieved bits is zero
410  Known.Zero.setBitsFrom((*MI.memoperands_begin())->getSizeInBits());
411  break;
412  }
413  case TargetOpcode::G_ASHR: {
414  KnownBits LHSKnown, RHSKnown;
415  computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
416  Depth + 1);
417  computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
418  Depth + 1);
419  Known = KnownBits::ashr(LHSKnown, RHSKnown);
420  break;
421  }
422  case TargetOpcode::G_LSHR: {
423  KnownBits LHSKnown, RHSKnown;
424  computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
425  Depth + 1);
426  computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
427  Depth + 1);
428  Known = KnownBits::lshr(LHSKnown, RHSKnown);
429  break;
430  }
431  case TargetOpcode::G_SHL: {
432  KnownBits LHSKnown, RHSKnown;
433  computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
434  Depth + 1);
435  computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
436  Depth + 1);
437  Known = KnownBits::shl(LHSKnown, RHSKnown);
438  break;
439  }
440  case TargetOpcode::G_INTTOPTR:
441  case TargetOpcode::G_PTRTOINT:
442  if (DstTy.isVector())
443  break;
444  // Fall through and handle them the same as zext/trunc.
446  case TargetOpcode::G_ASSERT_ZEXT:
447  case TargetOpcode::G_ZEXT:
448  case TargetOpcode::G_TRUNC: {
449  Register SrcReg = MI.getOperand(1).getReg();
450  LLT SrcTy = MRI.getType(SrcReg);
451  unsigned SrcBitWidth;
452 
453  // G_ASSERT_ZEXT stores the original bitwidth in the immediate operand.
454  if (Opcode == TargetOpcode::G_ASSERT_ZEXT)
455  SrcBitWidth = MI.getOperand(2).getImm();
456  else {
457  SrcBitWidth = SrcTy.isPointer()
458  ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
459  : SrcTy.getSizeInBits();
460  }
461  assert(SrcBitWidth && "SrcBitWidth can't be zero");
462  Known = Known.zextOrTrunc(SrcBitWidth);
463  computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
464  Known = Known.zextOrTrunc(BitWidth);
465  if (BitWidth > SrcBitWidth)
466  Known.Zero.setBitsFrom(SrcBitWidth);
467  break;
468  }
469  case TargetOpcode::G_MERGE_VALUES: {
470  unsigned NumOps = MI.getNumOperands();
471  unsigned OpSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
472 
473  for (unsigned I = 0; I != NumOps - 1; ++I) {
474  KnownBits SrcOpKnown;
475  computeKnownBitsImpl(MI.getOperand(I + 1).getReg(), SrcOpKnown,
476  DemandedElts, Depth + 1);
477  Known.insertBits(SrcOpKnown, I * OpSize);
478  }
479  break;
480  }
481  case TargetOpcode::G_UNMERGE_VALUES: {
482  if (DstTy.isVector())
483  break;
484  unsigned NumOps = MI.getNumOperands();
485  Register SrcReg = MI.getOperand(NumOps - 1).getReg();
486  if (MRI.getType(SrcReg).isVector())
487  return; // TODO: Handle vectors.
488 
489  KnownBits SrcOpKnown;
490  computeKnownBitsImpl(SrcReg, SrcOpKnown, DemandedElts, Depth + 1);
491 
492  // Figure out the result operand index
493  unsigned DstIdx = 0;
494  for (; DstIdx != NumOps - 1 && MI.getOperand(DstIdx).getReg() != R;
495  ++DstIdx)
496  ;
497 
498  Known = SrcOpKnown.extractBits(BitWidth, BitWidth * DstIdx);
499  break;
500  }
501  case TargetOpcode::G_BSWAP: {
502  Register SrcReg = MI.getOperand(1).getReg();
503  computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
504  Known = Known.byteSwap();
505  break;
506  }
507  case TargetOpcode::G_BITREVERSE: {
508  Register SrcReg = MI.getOperand(1).getReg();
509  computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
510  Known = Known.reverseBits();
511  break;
512  }
513  case TargetOpcode::G_CTPOP: {
514  computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
515  Depth + 1);
516  // We can bound the space the count needs. Also, bits known to be zero can't
517  // contribute to the population.
518  unsigned BitsPossiblySet = Known2.countMaxPopulation();
519  unsigned LowBits = Log2_32(BitsPossiblySet)+1;
520  Known.Zero.setBitsFrom(LowBits);
521  // TODO: we could bound Known.One using the lower bound on the number of
522  // bits which might be set provided by popcnt KnownOne2.
523  break;
524  }
525  case TargetOpcode::G_UBFX: {
526  KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
527  computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
528  Depth + 1);
529  computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
530  Depth + 1);
531  computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
532  Depth + 1);
533  Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
534  break;
535  }
536  case TargetOpcode::G_SBFX: {
537  KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
538  computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
539  Depth + 1);
540  computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
541  Depth + 1);
542  computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
543  Depth + 1);
544  Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
545  // Sign extend the extracted value using shift left and arithmetic shift
546  // right.
549  /*Add*/ false, /*NSW*/ false, ExtKnown, WidthKnown);
550  Known = KnownBits::ashr(KnownBits::shl(Known, ShiftKnown), ShiftKnown);
551  break;
552  }
553  }
554 
555  assert(!Known.hasConflict() && "Bits known to be one AND zero?");
556  LLVM_DEBUG(dumpResult(MI, Known, Depth));
557 
558  // Update the cache.
559  ComputeKnownBitsCache[R] = Known;
560 }
561 
562 /// Compute number of sign bits for the intersection of \p Src0 and \p Src1
563 unsigned GISelKnownBits::computeNumSignBitsMin(Register Src0, Register Src1,
564  const APInt &DemandedElts,
565  unsigned Depth) {
566  // Test src1 first, since we canonicalize simpler expressions to the RHS.
567  unsigned Src1SignBits = computeNumSignBits(Src1, DemandedElts, Depth);
568  if (Src1SignBits == 1)
569  return 1;
570  return std::min(computeNumSignBits(Src0, DemandedElts, Depth), Src1SignBits);
571 }
572 
574  const APInt &DemandedElts,
575  unsigned Depth) {
576  MachineInstr &MI = *MRI.getVRegDef(R);
577  unsigned Opcode = MI.getOpcode();
578 
579  if (Opcode == TargetOpcode::G_CONSTANT)
580  return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
581 
582  if (Depth == getMaxDepth())
583  return 1;
584 
585  if (!DemandedElts)
586  return 1; // No demanded elts, better to assume we don't know anything.
587 
588  LLT DstTy = MRI.getType(R);
589  const unsigned TyBits = DstTy.getScalarSizeInBits();
590 
591  // Handle the case where this is called on a register that does not have a
592  // type constraint. This is unlikely to occur except by looking through copies
593  // but it is possible for the initial register being queried to be in this
594  // state.
595  if (!DstTy.isValid())
596  return 1;
597 
598  unsigned FirstAnswer = 1;
599  switch (Opcode) {
600  case TargetOpcode::COPY: {
601  MachineOperand &Src = MI.getOperand(1);
602  if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
603  MRI.getType(Src.getReg()).isValid()) {
604  // Don't increment Depth for this one since we didn't do any work.
605  return computeNumSignBits(Src.getReg(), DemandedElts, Depth);
606  }
607 
608  return 1;
609  }
610  case TargetOpcode::G_SEXT: {
611  Register Src = MI.getOperand(1).getReg();
612  LLT SrcTy = MRI.getType(Src);
613  unsigned Tmp = DstTy.getScalarSizeInBits() - SrcTy.getScalarSizeInBits();
614  return computeNumSignBits(Src, DemandedElts, Depth + 1) + Tmp;
615  }
616  case TargetOpcode::G_ASSERT_SEXT:
617  case TargetOpcode::G_SEXT_INREG: {
618  // Max of the input and what this extends.
619  Register Src = MI.getOperand(1).getReg();
620  unsigned SrcBits = MI.getOperand(2).getImm();
621  unsigned InRegBits = TyBits - SrcBits + 1;
622  return std::max(computeNumSignBits(Src, DemandedElts, Depth + 1), InRegBits);
623  }
624  case TargetOpcode::G_SEXTLOAD: {
625  // FIXME: We need an in-memory type representation.
626  if (DstTy.isVector())
627  return 1;
628 
629  // e.g. i16->i32 = '17' bits known.
630  const MachineMemOperand *MMO = *MI.memoperands_begin();
631  return TyBits - MMO->getSizeInBits() + 1;
632  }
633  case TargetOpcode::G_ZEXTLOAD: {
634  // FIXME: We need an in-memory type representation.
635  if (DstTy.isVector())
636  return 1;
637 
638  // e.g. i16->i32 = '16' bits known.
639  const MachineMemOperand *MMO = *MI.memoperands_begin();
640  return TyBits - MMO->getSizeInBits();
641  }
642  case TargetOpcode::G_TRUNC: {
643  Register Src = MI.getOperand(1).getReg();
644  LLT SrcTy = MRI.getType(Src);
645 
646  // Check if the sign bits of source go down as far as the truncated value.
647  unsigned DstTyBits = DstTy.getScalarSizeInBits();
648  unsigned NumSrcBits = SrcTy.getScalarSizeInBits();
649  unsigned NumSrcSignBits = computeNumSignBits(Src, DemandedElts, Depth + 1);
650  if (NumSrcSignBits > (NumSrcBits - DstTyBits))
651  return NumSrcSignBits - (NumSrcBits - DstTyBits);
652  break;
653  }
654  case TargetOpcode::G_SELECT: {
655  return computeNumSignBitsMin(MI.getOperand(2).getReg(),
656  MI.getOperand(3).getReg(), DemandedElts,
657  Depth + 1);
658  }
659  case TargetOpcode::G_INTRINSIC:
660  case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
661  default: {
662  unsigned NumBits =
663  TL.computeNumSignBitsForTargetInstr(*this, R, DemandedElts, MRI, Depth);
664  if (NumBits > 1)
665  FirstAnswer = std::max(FirstAnswer, NumBits);
666  break;
667  }
668  }
669 
670  // Finally, if we can prove that the top bits of the result are 0's or 1's,
671  // use this information.
672  KnownBits Known = getKnownBits(R, DemandedElts, Depth);
673  APInt Mask;
674  if (Known.isNonNegative()) { // sign bit is 0
675  Mask = Known.Zero;
676  } else if (Known.isNegative()) { // sign bit is 1;
677  Mask = Known.One;
678  } else {
679  // Nothing known.
680  return FirstAnswer;
681  }
682 
683  // Okay, we know that the sign bit in Mask is set. Use CLO to determine
684  // the number of identical bits in the top of the input value.
685  Mask <<= Mask.getBitWidth() - TyBits;
686  return std::max(FirstAnswer, Mask.countLeadingOnes());
687 }
688 
690  LLT Ty = MRI.getType(R);
691  APInt DemandedElts =
692  Ty.isVector() ? APInt::getAllOnes(Ty.getNumElements()) : APInt(1, 1);
693  return computeNumSignBits(R, DemandedElts, Depth);
694 }
695 
697  AU.setPreservesAll();
699 }
700 
702  return false;
703 }
i
i
Definition: README.txt:29
llvm::KnownBits::anyext
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...
Definition: KnownBits.h:158
llvm::KnownBits::shl
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for shl(LHS, RHS).
Definition: KnownBits.cpp:167
llvm::APInt::setAllBits
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1261
llvm::KnownBits::lshr
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for lshr(LHS, RHS).
Definition: KnownBits.cpp:221
MI
IRTranslator LLVM IR MI
Definition: IRTranslator.cpp:103
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::GISelKnownBits::maskedValueIsZero
bool maskedValueIsZero(Register Val, const APInt &Mask)
Definition: GISelKnownBits.h:78
llvm::LLT::getScalarSizeInBits
unsigned getScalarSizeInBits() const
Definition: LowLevelTypeImpl.h:213
llvm::GISelKnownBits
Definition: GISelKnownBits.h:29
llvm::KnownBits::getMinValue
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
Definition: KnownBits.h:120
getFunction
static Function * getFunction(Constant *C)
Definition: Evaluator.cpp:255
llvm::KnownBits::insertBits
void insertBits(const KnownBits &SubBits, unsigned BitPosition)
Insert the bits from a smaller known bits starting at bitPosition.
Definition: KnownBits.h:210
llvm::KnownBits::byteSwap
KnownBits byteSwap()
Definition: KnownBits.h:393
llvm::TargetLowering::computeKnownBitsForFrameIndex
virtual void computeKnownBitsForFrameIndex(int FIOp, KnownBits &Known, const MachineFunction &MF) const
Determine which of the bits of FrameIndex FIOp are known to be 0.
Definition: TargetLowering.cpp:2965
llvm::KnownBits::Zero
APInt Zero
Definition: KnownBits.h:24
llvm::toString
std::string toString(Error E)
Write all error messages (if any) in E to a string.
Definition: Error.h:1020
llvm::KnownBits::isUnknown
bool isUnknown() const
Returns true if we don't know any bits.
Definition: KnownBits.h:63
GISelKnownBits.h
ValueTracking.h
llvm::MachineMemOperand::getSizeInBits
uint64_t getSizeInBits() const
Return the size in bits of the memory reference.
Definition: MachineMemOperand.h:241
llvm::Depth
@ Depth
Definition: SIMachineScheduler.h:36
extractBits
static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown, const KnownBits &OffsetKnown, const KnownBits &WidthKnown)
Definition: GISelKnownBits.cpp:120
Module.h
llvm::MachineMemOperand
A description of a memory reference used in the backend.
Definition: MachineMemOperand.h:128
llvm::LLT::isValid
bool isValid() const
Definition: LowLevelTypeImpl.h:117
dumpResult
static LLVM_ATTRIBUTE_UNUSED void dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth)
Definition: GISelKnownBits.cpp:88
llvm::GISelKnownBits::signBitIsZero
bool signBitIsZero(Register Op)
Definition: GISelKnownBits.cpp:75
LLVM_ATTRIBUTE_UNUSED
#define LLVM_ATTRIBUTE_UNUSED
Definition: Compiler.h:188
llvm::TargetLoweringBase::getBooleanContents
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...
Definition: TargetLowering.h:828
llvm::KnownBits::mul
static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool SelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
Definition: KnownBits.cpp:415
llvm::BitmaskEnumDetail::Mask
std::underlying_type_t< E > Mask()
Get a bitmask with 1s in all places up to the high-order bit of E's largest value.
Definition: BitmaskEnum.h:80
llvm::MachineFunctionPass::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - Subclasses that override getAnalysisUsage must call this.
Definition: MachineFunctionPass.cpp:102
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
llvm::computeKnownBitsFromRangeMetadata
void computeKnownBitsFromRangeMetadata(const MDNode &Ranges, KnownBits &Known)
Compute known bits from the range metadata.
Definition: ValueTracking.cpp:448
MachineRegisterInfo.h
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
llvm::GISelKnownBitsAnalysis::ID
static char ID
Definition: GISelKnownBits.h:117
llvm::DataLayout::getIndexSizeInBits
unsigned getIndexSizeInBits(unsigned AS) const
Size in bits of index used for address calculation in getelementptr.
Definition: DataLayout.h:418
TargetLowering.h
llvm::KnownBits::isNonNegative
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:99
llvm::GISelKnownBitsAnalysis
To use KnownBitsInfo analysis in a pass, KnownBitsInfo &Info = getAnalysis<GISelKnownBitsInfoAnalysis...
Definition: GISelKnownBits.h:113
llvm::GISelKnownBits::getKnownBits
KnownBits getKnownBits(Register R)
Definition: GISelKnownBits.cpp:57
llvm::KnownBits::umax
static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umax(LHS, RHS).
Definition: KnownBits.cpp:117
llvm::KnownBits::One
APInt One
Definition: KnownBits.h:25
llvm::LLT::getSizeInBits
TypeSize getSizeInBits() const
Returns the total size of the type. Must only be called on sized types.
Definition: LowLevelTypeImpl.h:153
llvm::AnalysisUsage
Represent the analysis usage information of a pass.
Definition: PassAnalysisSupport.h:47
llvm::KnownBits::smin
static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smin(LHS, RHS).
Definition: KnownBits.cpp:154
llvm::APInt::getAllOnes
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition: APInt.h:216
Utils.h
llvm::KnownBits::hasConflict
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:47
llvm::APInt::getLimitedValue
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.
Definition: APInt.h:449
TargetOpcodes.h
llvm::Log2_32
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:596
llvm::MachineOperand
MachineOperand class - Representation of each machine instruction operand.
Definition: MachineOperand.h:49
llvm::KnownBits::isNegative
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:96
llvm::KnownBits::sext
KnownBits sext(unsigned BitWidth) const
Return known bits for a sign extension of the value we're tracking.
Definition: KnownBits.h:171
llvm::Align
This struct is a compact representation of a valid (non-zero power of two) alignment.
Definition: Alignment.h:39
llvm::MachineRegisterInfo::getVRegDef
MachineInstr * getVRegDef(Register Reg) const
getVRegDef - Return the machine instr that defines the specified virtual register or null if none is ...
Definition: MachineRegisterInfo.cpp:400
DEBUG_TYPE
#define DEBUG_TYPE
Provides analysis for querying information about KnownBits during GISel passes.
Definition: GISelKnownBits.cpp:22
llvm::LLT::getAddressSpace
unsigned getAddressSpace() const
Definition: LowLevelTypeImpl.h:227
llvm::Register::isVirtual
bool isVirtual() const
Return true if the specified register number is in the virtual register namespace.
Definition: Register.h:91
llvm::KnownBits::reverseBits
KnownBits reverseBits()
Definition: KnownBits.h:397
llvm::GISelKnownBits::computeNumSignBits
unsigned computeNumSignBits(Register R, const APInt &DemandedElts, unsigned Depth=0)
Definition: GISelKnownBits.cpp:573
llvm::MachineInstr
Representation of each machine instruction.
Definition: MachineInstr.h:64
llvm::GISelKnownBits::getMaxDepth
unsigned getMaxDepth() const
Definition: GISelKnownBits.h:102
llvm::numbers::e
constexpr double e
Definition: MathExtras.h:57
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::GISelKnownBits::getKnownZeroes
APInt getKnownZeroes(Register R)
Definition: GISelKnownBits.cpp:81
llvm::MachineFrameInfo::getObjectAlign
Align getObjectAlign(int ObjectIdx) const
Return the alignment of the specified stack object.
Definition: MachineFrameInfo.h:467
llvm::KnownBits::extractBits
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
Definition: KnownBits.h:216
llvm::LLT::isVector
bool isVector() const
Definition: LowLevelTypeImpl.h:123
llvm::LLT::getNumElements
uint16_t getNumElements() const
Returns the number of elements in a vector LLT.
Definition: LowLevelTypeImpl.h:127
llvm::KnownBits::getMaxValue
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition: KnownBits.h:136
llvm::GISelKnownBits::getKnownOnes
APInt getKnownOnes(Register R)
Definition: GISelKnownBits.cpp:85
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::LLT::isPointer
bool isPointer() const
Definition: LowLevelTypeImpl.h:121
llvm::MachineFunction::getFrameInfo
MachineFrameInfo & getFrameInfo()
getFrameInfo - Return the frame info object for the current function.
Definition: MachineFunction.h:642
llvm::KnownBits::countMaxPopulation
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
Definition: KnownBits.h:281
llvm::getIConstantVRegVal
Optional< APInt > getIConstantVRegVal(Register VReg, const MachineRegisterInfo &MRI)
If VReg is defined by a G_CONSTANT, return the corresponding value.
Definition: Utils.cpp:271
llvm::MDNode
Metadata node.
Definition: Metadata.h:906
llvm::GISelKnownBitsAnalysis::getAnalysisUsage
void getAnalysisUsage(AnalysisUsage &AU) const override
getAnalysisUsage - This function should be overriden by passes that need analysis information to do t...
Definition: GISelKnownBits.cpp:696
llvm::KnownBits::ashr
static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for ashr(LHS, RHS).
Definition: KnownBits.cpp:274
llvm::KnownBits::computeForAddSub
static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, KnownBits RHS)
Compute known bits resulting from adding LHS and RHS.
Definition: KnownBits.cpp:57
llvm::APInt
Class for arbitrary precision integers.
Definition: APInt.h:75
llvm::MachineFunction
Definition: MachineFunction.h:230
llvm::KnownBits::sextInReg
KnownBits sextInReg(unsigned SrcBitWidth) const
Return known bits for a in-register sign extension of the value we're tracking.
Definition: KnownBits.cpp:88
llvm::DataLayout::isNonIntegralAddressSpace
bool isNonIntegralAddressSpace(unsigned AddrSpace) const
Definition: DataLayout.h:391
llvm::GISelKnownBits::computeKnownAlignment
Align computeKnownAlignment(Register R, unsigned Depth=0)
Definition: GISelKnownBits.cpp:35
llvm::min
Expected< ExpressionValue > min(const ExpressionValue &Lhs, const ExpressionValue &Rhs)
Definition: FileCheck.cpp:357
getParent
static const Function * getParent(const Value *V)
Definition: BasicAliasAnalysis.cpp:814
DL
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
Definition: AArch64SLSHardening.cpp:76
llvm::TargetLowering::computeKnownAlignForTargetInstr
virtual Align computeKnownAlignForTargetInstr(GISelKnownBits &Analysis, Register R, const MachineRegisterInfo &MRI, unsigned Depth=0) const
Determine the known alignment for the pointer value R.
Definition: TargetLowering.cpp:2971
LLVM_FALLTHROUGH
#define LLVM_FALLTHROUGH
LLVM_FALLTHROUGH - Mark fallthrough cases in switch statements.
Definition: Compiler.h:273
llvm::KnownBits::smax
static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smax(LHS, RHS).
Definition: KnownBits.cpp:141
MRI
unsigned const MachineRegisterInfo * MRI
Definition: AArch64AdvSIMDScalarPass.cpp:105
llvm::Register
Wrapper class representing virtual and physical registers.
Definition: Register.h:19
MaxDepth
static const unsigned MaxDepth
Definition: InstCombineMulDivRem.cpp:870
llvm::KnownBits::zextOrTrunc
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
Definition: KnownBits.h:187
llvm::KnownBits
Definition: KnownBits.h:23
llvm::AnalysisUsage::setPreservesAll
void setPreservesAll()
Set by analyses that do not transform their input at all.
Definition: PassAnalysisSupport.h:130
MachineFrameInfo.h
llvm::BitWidth
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:147
llvm::TargetLoweringBase::ZeroOrOneBooleanContent
@ ZeroOrOneBooleanContent
Definition: TargetLowering.h:233
INITIALIZE_PASS
INITIALIZE_PASS(GISelKnownBitsAnalysis, DEBUG_TYPE, "Analysis for ComputingKnownBits", false, true) GISelKnownBits
Definition: GISelKnownBits.cpp:28
llvm::APInt::getSignMask
static APInt getSignMask(unsigned BitWidth)
Get the SignMask for a specific bit width.
Definition: APInt.h:211
llvm::GISelKnownBitsAnalysis::runOnMachineFunction
bool runOnMachineFunction(MachineFunction &MF) override
runOnMachineFunction - This method must be overloaded to perform the desired machine code transformat...
Definition: GISelKnownBits.cpp:701
llvm::KnownBits::umin
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).
Definition: KnownBits.cpp:135
llvm::MachineRegisterInfo::getType
LLT getType(Register Reg) const
Get the low-level type of Reg or LLT{} if Reg is not a generic (target independent) virtual register.
Definition: MachineRegisterInfo.h:732
llvm::TargetLowering::computeKnownBitsForTargetInstr
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...
Definition: TargetLowering.cpp:2958
llvm::KnownBits::commonBits
static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits common to LHS and RHS.
Definition: KnownBits.h:291
llvm::max
Align max(MaybeAlign Lhs, Align Rhs)
Definition: Alignment.h:340
llvm::KnownBits::makeConstant
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
Definition: KnownBits.h:286
llvm::TargetLowering::computeNumSignBitsForTargetInstr
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 ...
Definition: TargetLowering.cpp:2992
llvm::APInt::getLowBitsSet
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:291
llvm::GISelKnownBits::computeKnownBitsImpl
virtual void computeKnownBitsImpl(Register R, KnownBits &Known, const APInt &DemandedElts, unsigned Depth=0)
Definition: GISelKnownBits.cpp:131
llvm::KnownBits::getBitWidth
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
llvm::APInt::setBitsFrom
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
Definition: APInt.h:1328
llvm::APInt::getBitsSetFrom
static APInt getBitsSetFrom(unsigned numBits, unsigned loBit)
Constructs an APInt value that has a contiguous range of bits set.
Definition: APInt.h:271
llvm::MachineMemOperand::getRanges
const MDNode * getRanges() const
Return the range tag for the memory reference.
Definition: MachineMemOperand.h:261
getReg
static unsigned getReg(const void *D, unsigned RC, unsigned RegNo)
Definition: MipsDisassembler.cpp:572
llvm::LLT
Definition: LowLevelTypeImpl.h:40