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