llvm/lib/CodeGen/GlobalISel/GISelKnownBits.cpp

   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 //===----------------------------------------------------------------------===//
  13 #include "llvm/CodeGen/GlobalISel/GISelKnownBits.h"
  14 #include "llvm/ADT/StringExtras.h"
  15 #include "llvm/Analysis/ValueTracking.h"
  16 #include "llvm/CodeGen/GlobalISel/Utils.h"
  17 #include "llvm/CodeGen/MachineFrameInfo.h"
  18 #include "llvm/CodeGen/MachineRegisterInfo.h"
  19 #include "llvm/CodeGen/TargetLowering.h"
  20 #include "llvm/CodeGen/TargetOpcodes.h"
  21 #include "llvm/IR/Module.h"
  22 #include "llvm/Target/TargetMachine.h"
  23
  24 #define DEBUG_TYPE "gisel-known-bits"
  25
  26 using namespace llvm;
  27
  28 char llvm::GISelKnownBitsAnalysis::ID = 0;
  29
  30 INITIALIZE_PASS(GISelKnownBitsAnalysis, DEBUG_TYPE,
  31                 "Analysis for ComputingKnownBits", false, true)
  32
  33 GISelKnownBits::GISelKnownBits(MachineFunction &MF, unsigned MaxDepth)
  34     : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
  35       DL(MF.getFunction().getParent()->getDataLayout()), MaxDepth(MaxDepth) {}
  36
  37 Align GISelKnownBits::computeKnownAlignment(Register R, unsigned Depth) {
  38   const MachineInstr *MI = MRI.getVRegDef(R);
  39   switch (MI->getOpcode()) {
  40   case TargetOpcode::COPY:
  41     return computeKnownAlignment(MI->getOperand(1).getReg(), Depth);
  42   case TargetOpcode::G_ASSERT_ALIGN: {
  43     // TODO: Min with source
  44     return Align(MI->getOperand(2).getImm());
  45   }
  46   case TargetOpcode::G_FRAME_INDEX: {
  47     int FrameIdx = MI->getOperand(1).getIndex();
  48     return MF.getFrameInfo().getObjectAlign(FrameIdx);
  49   }
  50   case TargetOpcode::G_INTRINSIC:
  51   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
  52   case TargetOpcode::G_INTRINSIC_CONVERGENT:
  53   case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
  54   default:
  55     return TL.computeKnownAlignForTargetInstr(*this, R, MRI, Depth + 1);
  56   }
  57 }
  58
  59 KnownBits GISelKnownBits::getKnownBits(MachineInstr &MI) {
  60   assert(MI.getNumExplicitDefs() == 1 &&
  61          "expected single return generic instruction");
  62   return getKnownBits(MI.getOperand(0).getReg());
  63 }
  64
  65 KnownBits GISelKnownBits::getKnownBits(Register R) {
  66   const LLT Ty = MRI.getType(R);
  67   APInt DemandedElts =
  68       Ty.isVector() ? APInt::getAllOnes(Ty.getNumElements()) : APInt(1, 1);
  69   return getKnownBits(R, DemandedElts);
  70 }
  71
  72 KnownBits GISelKnownBits::getKnownBits(Register R, const APInt &DemandedElts,
  73                                        unsigned Depth) {
  74   // For now, we only maintain the cache during one request.
  75   assert(ComputeKnownBitsCache.empty() && "Cache should have been cleared");
  76
  77   KnownBits Known;
  78   computeKnownBitsImpl(R, Known, DemandedElts, Depth);
  79   ComputeKnownBitsCache.clear();
  80   return Known;
  81 }
  82
  83 bool GISelKnownBits::signBitIsZero(Register R) {
  84   LLT Ty = MRI.getType(R);
  85   unsigned BitWidth = Ty.getScalarSizeInBits();
  86   return maskedValueIsZero(R, APInt::getSignMask(BitWidth));
  87 }
  88
  89 APInt GISelKnownBits::getKnownZeroes(Register R) {
  90   return getKnownBits(R).Zero;
  91 }
  92
  93 APInt GISelKnownBits::getKnownOnes(Register R) { return getKnownBits(R).One; }
  94
  95 LLVM_ATTRIBUTE_UNUSED static void
  96 dumpResult(const MachineInstr &MI, const KnownBits &Known, unsigned Depth) {
  97   dbgs() << "[" << Depth << "] Compute known bits: " << MI << "[" << Depth
  98          << "] Computed for: " << MI << "[" << Depth << "] Known: 0x"
  99          << toString(Known.Zero | Known.One, 16, false) << "\n"
 100          << "[" << Depth << "] Zero: 0x" << toString(Known.Zero, 16, false)
 101          << "\n"
 102          << "[" << Depth << "] One:  0x" << toString(Known.One, 16, false)
 103          << "\n";
 104 }
 105
 106 /// Compute known bits for the intersection of \p Src0 and \p Src1
 107 void GISelKnownBits::computeKnownBitsMin(Register Src0, Register Src1,
 108                                          KnownBits &Known,
 109                                          const APInt &DemandedElts,
 110                                          unsigned Depth) {
 111   // Test src1 first, since we canonicalize simpler expressions to the RHS.
 112   computeKnownBitsImpl(Src1, Known, DemandedElts, Depth);
 113
 114   // If we don't know any bits, early out.
 115   if (Known.isUnknown())
 116     return;
 117
 118   KnownBits Known2;
 119   computeKnownBitsImpl(Src0, Known2, DemandedElts, Depth);
 120
 121   // Only known if known in both the LHS and RHS.
 122   Known = Known.intersectWith(Known2);
 123 }
 124
 125 // Bitfield extract is computed as (Src >> Offset) & Mask, where Mask is
 126 // created using Width. Use this function when the inputs are KnownBits
 127 // objects. TODO: Move this KnownBits.h if this is usable in more cases.
 128 static KnownBits extractBits(unsigned BitWidth, const KnownBits &SrcOpKnown,
 129                              const KnownBits &OffsetKnown,
 130                              const KnownBits &WidthKnown) {
 131   KnownBits Mask(BitWidth);
 132   Mask.Zero = APInt::getBitsSetFrom(
 133       BitWidth, WidthKnown.getMaxValue().getLimitedValue(BitWidth));
 134   Mask.One = APInt::getLowBitsSet(
 135       BitWidth, WidthKnown.getMinValue().getLimitedValue(BitWidth));
 136   return KnownBits::lshr(SrcOpKnown, OffsetKnown) & Mask;
 137 }
 138
 139 void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known,
 140                                           const APInt &DemandedElts,
 141                                           unsigned Depth) {
 142   MachineInstr &MI = *MRI.getVRegDef(R);
 143   unsigned Opcode = MI.getOpcode();
 144   LLT DstTy = MRI.getType(R);
 145
 146   // Handle the case where this is called on a register that does not have a
 147   // type constraint (i.e. it has a register class constraint instead). This is
 148   // unlikely to occur except by looking through copies but it is possible for
 149   // the initial register being queried to be in this state.
 150   if (!DstTy.isValid()) {
 151     Known = KnownBits();
 152     return;
 153   }
 154
 155   unsigned BitWidth = DstTy.getScalarSizeInBits();
 156   auto CacheEntry = ComputeKnownBitsCache.find(R);
 157   if (CacheEntry != ComputeKnownBitsCache.end()) {
 158     Known = CacheEntry->second;
 159     LLVM_DEBUG(dbgs() << "Cache hit at ");
 160     LLVM_DEBUG(dumpResult(MI, Known, Depth));
 161     assert(Known.getBitWidth() == BitWidth && "Cache entry size doesn't match");
 162     return;
 163   }
 164   Known = KnownBits(BitWidth); // Don't know anything
 165
 166   // Depth may get bigger than max depth if it gets passed to a different
 167   // GISelKnownBits object.
 168   // This may happen when say a generic part uses a GISelKnownBits object
 169   // with some max depth, but then we hit TL.computeKnownBitsForTargetInstr
 170   // which creates a new GISelKnownBits object with a different and smaller
 171   // depth. If we just check for equality, we would never exit if the depth
 172   // that is passed down to the target specific GISelKnownBits object is
 173   // already bigger than its max depth.
 174   if (Depth >= getMaxDepth())
 175     return;
 176
 177   if (!DemandedElts)
 178     return; // No demanded elts, better to assume we don't know anything.
 179
 180   KnownBits Known2;
 181
 182   switch (Opcode) {
 183   default:
 184     TL.computeKnownBitsForTargetInstr(*this, R, Known, DemandedElts, MRI,
 185                                       Depth);
 186     break;
 187   case TargetOpcode::G_BUILD_VECTOR: {
 188     // Collect the known bits that are shared by every demanded vector element.
 189     Known.Zero.setAllBits(); Known.One.setAllBits();
 190     for (unsigned i = 0, e = MI.getNumOperands() - 1; i < e; ++i) {
 191       if (!DemandedElts[i])
 192         continue;
 193
 194       computeKnownBitsImpl(MI.getOperand(i + 1).getReg(), Known2, DemandedElts,
 195                            Depth + 1);
 196
 197       // Known bits are the values that are shared by every demanded element.
 198       Known = Known.intersectWith(Known2);
 199
 200       // If we don't know any bits, early out.
 201       if (Known.isUnknown())
 202         break;
 203     }
 204     break;
 205   }
 206   case TargetOpcode::COPY:
 207   case TargetOpcode::G_PHI:
 208   case TargetOpcode::PHI: {
 209     Known.One = APInt::getAllOnes(BitWidth);
 210     Known.Zero = APInt::getAllOnes(BitWidth);
 211     // Destination registers should not have subregisters at this
 212     // point of the pipeline, otherwise the main live-range will be
 213     // defined more than once, which is against SSA.
 214     assert(MI.getOperand(0).getSubReg() == 0 && "Is this code in SSA?");
 215     // Record in the cache that we know nothing for MI.
 216     // This will get updated later and in the meantime, if we reach that
 217     // phi again, because of a loop, we will cut the search thanks to this
 218     // cache entry.
 219     // We could actually build up more information on the phi by not cutting
 220     // the search, but that additional information is more a side effect
 221     // than an intended choice.
 222     // Therefore, for now, save on compile time until we derive a proper way
 223     // to derive known bits for PHIs within loops.
 224     ComputeKnownBitsCache[R] = KnownBits(BitWidth);
 225     // PHI's operand are a mix of registers and basic blocks interleaved.
 226     // We only care about the register ones.
 227     for (unsigned Idx = 1; Idx < MI.getNumOperands(); Idx += 2) {
 228       const MachineOperand &Src = MI.getOperand(Idx);
 229       Register SrcReg = Src.getReg();
 230       // Look through trivial copies and phis but don't look through trivial
 231       // copies or phis of the form `%1:(s32) = OP %0:gpr32`, known-bits
 232       // analysis is currently unable to determine the bit width of a
 233       // register class.
 234       //
 235       // We can't use NoSubRegister by name as it's defined by each target but
 236       // it's always defined to be 0 by tablegen.
 237       if (SrcReg.isVirtual() && Src.getSubReg() == 0 /*NoSubRegister*/ &&
 238           MRI.getType(SrcReg).isValid()) {
 239         // For COPYs we don't do anything, don't increase the depth.
 240         computeKnownBitsImpl(SrcReg, Known2, DemandedElts,
 241                              Depth + (Opcode != TargetOpcode::COPY));
 242         Known = Known.intersectWith(Known2);
 243         // If we reach a point where we don't know anything
 244         // just stop looking through the operands.
 245         if (Known.isUnknown())
 246           break;
 247       } else {
 248         // We know nothing.
 249         Known = KnownBits(BitWidth);
 250         break;
 251       }
 252     }
 253     break;
 254   }
 255   case TargetOpcode::G_CONSTANT: {
 256     auto CstVal = getIConstantVRegVal(R, MRI);
 257     if (!CstVal)
 258       break;
 259     Known = KnownBits::makeConstant(*CstVal);
 260     break;
 261   }
 262   case TargetOpcode::G_FRAME_INDEX: {
 263     int FrameIdx = MI.getOperand(1).getIndex();
 264     TL.computeKnownBitsForFrameIndex(FrameIdx, Known, MF);
 265     break;
 266   }
 267   case TargetOpcode::G_SUB: {
 268     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 269                          Depth + 1);
 270     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
 271                          Depth + 1);
 272     Known = KnownBits::computeForAddSub(/*Add*/ false, /*NSW*/ false, Known,
 273                                         Known2);
 274     break;
 275   }
 276   case TargetOpcode::G_XOR: {
 277     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 278                          Depth + 1);
 279     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 280                          Depth + 1);
 281
 282     Known ^= Known2;
 283     break;
 284   }
 285   case TargetOpcode::G_PTR_ADD: {
 286     if (DstTy.isVector())
 287       break;
 288     // G_PTR_ADD is like G_ADD. FIXME: Is this true for all targets?
 289     LLT Ty = MRI.getType(MI.getOperand(1).getReg());
 290     if (DL.isNonIntegralAddressSpace(Ty.getAddressSpace()))
 291       break;
 292     [[fallthrough]];
 293   }
 294   case TargetOpcode::G_ADD: {
 295     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 296                          Depth + 1);
 297     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
 298                          Depth + 1);
 299     Known =
 300         KnownBits::computeForAddSub(/*Add*/ true, /*NSW*/ false, Known, Known2);
 301     break;
 302   }
 303   case TargetOpcode::G_AND: {
 304     // If either the LHS or the RHS are Zero, the result is zero.
 305     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 306                          Depth + 1);
 307     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 308                          Depth + 1);
 309
 310     Known &= Known2;
 311     break;
 312   }
 313   case TargetOpcode::G_OR: {
 314     // If either the LHS or the RHS are Zero, the result is zero.
 315     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 316                          Depth + 1);
 317     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 318                          Depth + 1);
 319
 320     Known |= Known2;
 321     break;
 322   }
 323   case TargetOpcode::G_MUL: {
 324     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 325                          Depth + 1);
 326     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 327                          Depth + 1);
 328     Known = KnownBits::mul(Known, Known2);
 329     break;
 330   }
 331   case TargetOpcode::G_SELECT: {
 332     computeKnownBitsMin(MI.getOperand(2).getReg(), MI.getOperand(3).getReg(),
 333                         Known, DemandedElts, Depth + 1);
 334     break;
 335   }
 336   case TargetOpcode::G_SMIN: {
 337     // TODO: Handle clamp pattern with number of sign bits
 338     KnownBits KnownRHS;
 339     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 340                          Depth + 1);
 341     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
 342                          Depth + 1);
 343     Known = KnownBits::smin(Known, KnownRHS);
 344     break;
 345   }
 346   case TargetOpcode::G_SMAX: {
 347     // TODO: Handle clamp pattern with number of sign bits
 348     KnownBits KnownRHS;
 349     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 350                          Depth + 1);
 351     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS, DemandedElts,
 352                          Depth + 1);
 353     Known = KnownBits::smax(Known, KnownRHS);
 354     break;
 355   }
 356   case TargetOpcode::G_UMIN: {
 357     KnownBits KnownRHS;
 358     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
 359                          DemandedElts, Depth + 1);
 360     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
 361                          DemandedElts, Depth + 1);
 362     Known = KnownBits::umin(Known, KnownRHS);
 363     break;
 364   }
 365   case TargetOpcode::G_UMAX: {
 366     KnownBits KnownRHS;
 367     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known,
 368                          DemandedElts, Depth + 1);
 369     computeKnownBitsImpl(MI.getOperand(2).getReg(), KnownRHS,
 370                          DemandedElts, Depth + 1);
 371     Known = KnownBits::umax(Known, KnownRHS);
 372     break;
 373   }
 374   case TargetOpcode::G_FCMP:
 375   case TargetOpcode::G_ICMP: {
 376     if (DstTy.isVector())
 377       break;
 378     if (TL.getBooleanContents(DstTy.isVector(),
 379                               Opcode == TargetOpcode::G_FCMP) ==
 380             TargetLowering::ZeroOrOneBooleanContent &&
 381         BitWidth > 1)
 382       Known.Zero.setBitsFrom(1);
 383     break;
 384   }
 385   case TargetOpcode::G_SEXT: {
 386     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 387                          Depth + 1);
 388     // If the sign bit is known to be zero or one, then sext will extend
 389     // it to the top bits, else it will just zext.
 390     Known = Known.sext(BitWidth);
 391     break;
 392   }
 393   case TargetOpcode::G_ASSERT_SEXT:
 394   case TargetOpcode::G_SEXT_INREG: {
 395     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 396                          Depth + 1);
 397     Known = Known.sextInReg(MI.getOperand(2).getImm());
 398     break;
 399   }
 400   case TargetOpcode::G_ANYEXT: {
 401     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 402                          Depth + 1);
 403     Known = Known.anyext(BitWidth);
 404     break;
 405   }
 406   case TargetOpcode::G_LOAD: {
 407     const MachineMemOperand *MMO = *MI.memoperands_begin();
 408     if (const MDNode *Ranges = MMO->getRanges()) {
 409       computeKnownBitsFromRangeMetadata(*Ranges, Known);
 410     }
 411
 412     break;
 413   }
 414   case TargetOpcode::G_ZEXTLOAD: {
 415     if (DstTy.isVector())
 416       break;
 417     // Everything above the retrieved bits is zero
 418     Known.Zero.setBitsFrom((*MI.memoperands_begin())->getSizeInBits());
 419     break;
 420   }
 421   case TargetOpcode::G_ASHR: {
 422     KnownBits LHSKnown, RHSKnown;
 423     computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
 424                          Depth + 1);
 425     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
 426                          Depth + 1);
 427     Known = KnownBits::ashr(LHSKnown, RHSKnown);
 428     break;
 429   }
 430   case TargetOpcode::G_LSHR: {
 431     KnownBits LHSKnown, RHSKnown;
 432     computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
 433                          Depth + 1);
 434     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
 435                          Depth + 1);
 436     Known = KnownBits::lshr(LHSKnown, RHSKnown);
 437     break;
 438   }
 439   case TargetOpcode::G_SHL: {
 440     KnownBits LHSKnown, RHSKnown;
 441     computeKnownBitsImpl(MI.getOperand(1).getReg(), LHSKnown, DemandedElts,
 442                          Depth + 1);
 443     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
 444                          Depth + 1);
 445     Known = KnownBits::shl(LHSKnown, RHSKnown);
 446     break;
 447   }
 448   case TargetOpcode::G_INTTOPTR:
 449   case TargetOpcode::G_PTRTOINT:
 450     if (DstTy.isVector())
 451       break;
 452     // Fall through and handle them the same as zext/trunc.
 453     [[fallthrough]];
 454   case TargetOpcode::G_ASSERT_ZEXT:
 455   case TargetOpcode::G_ZEXT:
 456   case TargetOpcode::G_TRUNC: {
 457     Register SrcReg = MI.getOperand(1).getReg();
 458     LLT SrcTy = MRI.getType(SrcReg);
 459     unsigned SrcBitWidth;
 460
 461     // G_ASSERT_ZEXT stores the original bitwidth in the immediate operand.
 462     if (Opcode == TargetOpcode::G_ASSERT_ZEXT)
 463       SrcBitWidth = MI.getOperand(2).getImm();
 464     else {
 465       SrcBitWidth = SrcTy.isPointer()
 466                         ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
 467                         : SrcTy.getSizeInBits();
 468     }
 469     assert(SrcBitWidth && "SrcBitWidth can't be zero");
 470     Known = Known.zextOrTrunc(SrcBitWidth);
 471     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
 472     Known = Known.zextOrTrunc(BitWidth);
 473     if (BitWidth > SrcBitWidth)
 474       Known.Zero.setBitsFrom(SrcBitWidth);
 475     break;
 476   }
 477   case TargetOpcode::G_ASSERT_ALIGN: {
 478     int64_t LogOfAlign = Log2_64(MI.getOperand(2).getImm());
 479
 480     // TODO: Should use maximum with source
 481     // If a node is guaranteed to be aligned, set low zero bits accordingly as
 482     // well as clearing one bits.
 483     Known.Zero.setLowBits(LogOfAlign);
 484     Known.One.clearLowBits(LogOfAlign);
 485     break;
 486   }
 487   case TargetOpcode::G_MERGE_VALUES: {
 488     unsigned NumOps = MI.getNumOperands();
 489     unsigned OpSize = MRI.getType(MI.getOperand(1).getReg()).getSizeInBits();
 490
 491     for (unsigned I = 0; I != NumOps - 1; ++I) {
 492       KnownBits SrcOpKnown;
 493       computeKnownBitsImpl(MI.getOperand(I + 1).getReg(), SrcOpKnown,
 494                            DemandedElts, Depth + 1);
 495       Known.insertBits(SrcOpKnown, I * OpSize);
 496     }
 497     break;
 498   }
 499   case TargetOpcode::G_UNMERGE_VALUES: {
 500     if (DstTy.isVector())
 501       break;
 502     unsigned NumOps = MI.getNumOperands();
 503     Register SrcReg = MI.getOperand(NumOps - 1).getReg();
 504     if (MRI.getType(SrcReg).isVector())
 505       return; // TODO: Handle vectors.
 506
 507     KnownBits SrcOpKnown;
 508     computeKnownBitsImpl(SrcReg, SrcOpKnown, DemandedElts, Depth + 1);
 509
 510     // Figure out the result operand index
 511     unsigned DstIdx = 0;
 512     for (; DstIdx != NumOps - 1 && MI.getOperand(DstIdx).getReg() != R;
 513          ++DstIdx)
 514       ;
 515
 516     Known = SrcOpKnown.extractBits(BitWidth, BitWidth * DstIdx);
 517     break;
 518   }
 519   case TargetOpcode::G_BSWAP: {
 520     Register SrcReg = MI.getOperand(1).getReg();
 521     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
 522     Known = Known.byteSwap();
 523     break;
 524   }
 525   case TargetOpcode::G_BITREVERSE: {
 526     Register SrcReg = MI.getOperand(1).getReg();
 527     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
 528     Known = Known.reverseBits();
 529     break;
 530   }
 531   case TargetOpcode::G_CTPOP: {
 532     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 533                          Depth + 1);
 534     // We can bound the space the count needs.  Also, bits known to be zero can't
 535     // contribute to the population.
 536     unsigned BitsPossiblySet = Known2.countMaxPopulation();
 537     unsigned LowBits = llvm::bit_width(BitsPossiblySet);
 538     Known.Zero.setBitsFrom(LowBits);
 539     // TODO: we could bound Known.One using the lower bound on the number of
 540     // bits which might be set provided by popcnt KnownOne2.
 541     break;
 542   }
 543   case TargetOpcode::G_UBFX: {
 544     KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
 545     computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
 546                          Depth + 1);
 547     computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
 548                          Depth + 1);
 549     computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
 550                          Depth + 1);
 551     Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
 552     break;
 553   }
 554   case TargetOpcode::G_SBFX: {
 555     KnownBits SrcOpKnown, OffsetKnown, WidthKnown;
 556     computeKnownBitsImpl(MI.getOperand(1).getReg(), SrcOpKnown, DemandedElts,
 557                          Depth + 1);
 558     computeKnownBitsImpl(MI.getOperand(2).getReg(), OffsetKnown, DemandedElts,
 559                          Depth + 1);
 560     computeKnownBitsImpl(MI.getOperand(3).getReg(), WidthKnown, DemandedElts,
 561                          Depth + 1);
 562     Known = extractBits(BitWidth, SrcOpKnown, OffsetKnown, WidthKnown);
 563     // Sign extend the extracted value using shift left and arithmetic shift
 564     // right.
 565     KnownBits ExtKnown = KnownBits::makeConstant(APInt(BitWidth, BitWidth));
 566     KnownBits ShiftKnown = KnownBits::computeForAddSub(
 567         /*Add*/ false, /*NSW*/ false, ExtKnown, WidthKnown);
 568     Known = KnownBits::ashr(KnownBits::shl(Known, ShiftKnown), ShiftKnown);
 569     break;
 570   }
 571   case TargetOpcode::G_UADDO:
 572   case TargetOpcode::G_UADDE:
 573   case TargetOpcode::G_SADDO:
 574   case TargetOpcode::G_SADDE:
 575   case TargetOpcode::G_USUBO:
 576   case TargetOpcode::G_USUBE:
 577   case TargetOpcode::G_SSUBO:
 578   case TargetOpcode::G_SSUBE:
 579   case TargetOpcode::G_UMULO:
 580   case TargetOpcode::G_SMULO: {
 581     if (MI.getOperand(1).getReg() == R) {
 582       // If we know the result of a compare has the top bits zero, use this
 583       // info.
 584       if (TL.getBooleanContents(DstTy.isVector(), false) ==
 585               TargetLowering::ZeroOrOneBooleanContent &&
 586           BitWidth > 1)
 587         Known.Zero.setBitsFrom(1);
 588     }
 589     break;
 590   }
 591   }
 592
 593   assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 594   LLVM_DEBUG(dumpResult(MI, Known, Depth));
 595
 596   // Update the cache.
 597   ComputeKnownBitsCache[R] = Known;
 598 }
 599
 600 /// Compute number of sign bits for the intersection of \p Src0 and \p Src1
 601 unsigned GISelKnownBits::computeNumSignBitsMin(Register Src0, Register Src1,
 602                                                const APInt &DemandedElts,
 603                                                unsigned Depth) {
 604   // Test src1 first, since we canonicalize simpler expressions to the RHS.
 605   unsigned Src1SignBits = computeNumSignBits(Src1, DemandedElts, Depth);
 606   if (Src1SignBits == 1)
 607     return 1;
 608   return std::min(computeNumSignBits(Src0, DemandedElts, Depth), Src1SignBits);
 609 }
 610
 611 unsigned GISelKnownBits::computeNumSignBits(Register R,
 612                                             const APInt &DemandedElts,
 613                                             unsigned Depth) {
 614   MachineInstr &MI = *MRI.getVRegDef(R);
 615   unsigned Opcode = MI.getOpcode();
 616
 617   if (Opcode == TargetOpcode::G_CONSTANT)
 618     return MI.getOperand(1).getCImm()->getValue().getNumSignBits();
 619
 620   if (Depth == getMaxDepth())
 621     return 1;
 622
 623   if (!DemandedElts)
 624     return 1; // No demanded elts, better to assume we don't know anything.
 625
 626   LLT DstTy = MRI.getType(R);
 627   const unsigned TyBits = DstTy.getScalarSizeInBits();
 628
 629   // Handle the case where this is called on a register that does not have a
 630   // type constraint. This is unlikely to occur except by looking through copies
 631   // but it is possible for the initial register being queried to be in this
 632   // state.
 633   if (!DstTy.isValid())
 634     return 1;
 635
 636   unsigned FirstAnswer = 1;
 637   switch (Opcode) {
 638   case TargetOpcode::COPY: {
 639     MachineOperand &Src = MI.getOperand(1);
 640     if (Src.getReg().isVirtual() && Src.getSubReg() == 0 &&
 641         MRI.getType(Src.getReg()).isValid()) {
 642       // Don't increment Depth for this one since we didn't do any work.
 643       return computeNumSignBits(Src.getReg(), DemandedElts, Depth);
 644     }
 645
 646     return 1;
 647   }
 648   case TargetOpcode::G_SEXT: {
 649     Register Src = MI.getOperand(1).getReg();
 650     LLT SrcTy = MRI.getType(Src);
 651     unsigned Tmp = DstTy.getScalarSizeInBits() - SrcTy.getScalarSizeInBits();
 652     return computeNumSignBits(Src, DemandedElts, Depth + 1) + Tmp;
 653   }
 654   case TargetOpcode::G_ASSERT_SEXT:
 655   case TargetOpcode::G_SEXT_INREG: {
 656     // Max of the input and what this extends.
 657     Register Src = MI.getOperand(1).getReg();
 658     unsigned SrcBits = MI.getOperand(2).getImm();
 659     unsigned InRegBits = TyBits - SrcBits + 1;
 660     return std::max(computeNumSignBits(Src, DemandedElts, Depth + 1), InRegBits);
 661   }
 662   case TargetOpcode::G_SEXTLOAD: {
 663     // FIXME: We need an in-memory type representation.
 664     if (DstTy.isVector())
 665       return 1;
 666
 667     // e.g. i16->i32 = '17' bits known.
 668     const MachineMemOperand *MMO = *MI.memoperands_begin();
 669     return TyBits - MMO->getSizeInBits() + 1;
 670   }
 671   case TargetOpcode::G_ZEXTLOAD: {
 672     // FIXME: We need an in-memory type representation.
 673     if (DstTy.isVector())
 674       return 1;
 675
 676     // e.g. i16->i32 = '16' bits known.
 677     const MachineMemOperand *MMO = *MI.memoperands_begin();
 678     return TyBits - MMO->getSizeInBits();
 679   }
 680   case TargetOpcode::G_TRUNC: {
 681     Register Src = MI.getOperand(1).getReg();
 682     LLT SrcTy = MRI.getType(Src);
 683
 684     // Check if the sign bits of source go down as far as the truncated value.
 685     unsigned DstTyBits = DstTy.getScalarSizeInBits();
 686     unsigned NumSrcBits = SrcTy.getScalarSizeInBits();
 687     unsigned NumSrcSignBits = computeNumSignBits(Src, DemandedElts, Depth + 1);
 688     if (NumSrcSignBits > (NumSrcBits - DstTyBits))
 689       return NumSrcSignBits - (NumSrcBits - DstTyBits);
 690     break;
 691   }
 692   case TargetOpcode::G_SELECT: {
 693     return computeNumSignBitsMin(MI.getOperand(2).getReg(),
 694                                  MI.getOperand(3).getReg(), DemandedElts,
 695                                  Depth + 1);
 696   }
 697   case TargetOpcode::G_SADDO:
 698   case TargetOpcode::G_SADDE:
 699   case TargetOpcode::G_UADDO:
 700   case TargetOpcode::G_UADDE:
 701   case TargetOpcode::G_SSUBO:
 702   case TargetOpcode::G_SSUBE:
 703   case TargetOpcode::G_USUBO:
 704   case TargetOpcode::G_USUBE:
 705   case TargetOpcode::G_SMULO:
 706   case TargetOpcode::G_UMULO: {
 707     // If compares returns 0/-1, all bits are sign bits.
 708     // We know that we have an integer-based boolean since these operations
 709     // are only available for integer.
 710     if (MI.getOperand(1).getReg() == R) {
 711       if (TL.getBooleanContents(DstTy.isVector(), false) ==
 712           TargetLowering::ZeroOrNegativeOneBooleanContent)
 713         return TyBits;
 714     }
 715
 716     break;
 717   }
 718   case TargetOpcode::G_FCMP:
 719   case TargetOpcode::G_ICMP: {
 720     bool IsFP = Opcode == TargetOpcode::G_FCMP;
 721     if (TyBits == 1)
 722       break;
 723     auto BC = TL.getBooleanContents(DstTy.isVector(), IsFP);
 724     if (BC == TargetLoweringBase::ZeroOrNegativeOneBooleanContent)
 725       return TyBits; // All bits are sign bits.
 726     if (BC == TargetLowering::ZeroOrOneBooleanContent)
 727       return TyBits - 1; // Every always-zero bit is a sign bit.
 728     break;
 729   }
 730   case TargetOpcode::G_INTRINSIC:
 731   case TargetOpcode::G_INTRINSIC_W_SIDE_EFFECTS:
 732   case TargetOpcode::G_INTRINSIC_CONVERGENT:
 733   case TargetOpcode::G_INTRINSIC_CONVERGENT_W_SIDE_EFFECTS:
 734   default: {
 735     unsigned NumBits =
 736       TL.computeNumSignBitsForTargetInstr(*this, R, DemandedElts, MRI, Depth);
 737     if (NumBits > 1)
 738       FirstAnswer = std::max(FirstAnswer, NumBits);
 739     break;
 740   }
 741   }
 742
 743   // Finally, if we can prove that the top bits of the result are 0's or 1's,
 744   // use this information.
 745   KnownBits Known = getKnownBits(R, DemandedElts, Depth);
 746   APInt Mask;
 747   if (Known.isNonNegative()) {        // sign bit is 0
 748     Mask = Known.Zero;
 749   } else if (Known.isNegative()) {  // sign bit is 1;
 750     Mask = Known.One;
 751   } else {
 752     // Nothing known.
 753     return FirstAnswer;
 754   }
 755
 756   // Okay, we know that the sign bit in Mask is set.  Use CLO to determine
 757   // the number of identical bits in the top of the input value.
 758   Mask <<= Mask.getBitWidth() - TyBits;
 759   return std::max(FirstAnswer, Mask.countl_one());
 760 }
 761
 762 unsigned GISelKnownBits::computeNumSignBits(Register R, unsigned Depth) {
 763   LLT Ty = MRI.getType(R);
 764   APInt DemandedElts =
 765       Ty.isVector() ? APInt::getAllOnes(Ty.getNumElements()) : APInt(1, 1);
 766   return computeNumSignBits(R, DemandedElts, Depth);
 767 }
 768
 769 void GISelKnownBitsAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 770   AU.setPreservesAll();
 771   MachineFunctionPass::getAnalysisUsage(AU);
 772 }
 773
 774 bool GISelKnownBitsAnalysis::runOnMachineFunction(MachineFunction &MF) {
 775   return false;
 776 }
 777
 778 GISelKnownBits &GISelKnownBitsAnalysis::get(MachineFunction &MF) {
 779   if (!Info) {
 780     unsigned MaxDepth =
 781         MF.getTarget().getOptLevel() == CodeGenOptLevel::None ? 2 : 6;
 782     Info = std::make_unique<GISelKnownBits>(MF, MaxDepth);
 783   }
 784   return *Info.get();
 785 }