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