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
  21 #define DEBUG_TYPE "gisel-known-bits"
  22
  23 using namespace llvm;
  24
  25 char llvm::GISelKnownBitsAnalysis::ID = 0;
  26
  27 INITIALIZE_PASS_BEGIN(GISelKnownBitsAnalysis, DEBUG_TYPE,
  28                       "Analysis for ComputingKnownBits", false, true)
  29 INITIALIZE_PASS_END(GISelKnownBitsAnalysis, DEBUG_TYPE,
  30                     "Analysis for ComputingKnownBits", false, true)
  31
  32 GISelKnownBits::GISelKnownBits(MachineFunction &MF)
  33     : MF(MF), MRI(MF.getRegInfo()), TL(*MF.getSubtarget().getTargetLowering()),
  34       DL(MF.getFunction().getParent()->getDataLayout()) {}
  35
  36 unsigned GISelKnownBits::inferAlignmentForFrameIdx(int FrameIdx, int Offset,
  37                                                    const MachineFunction &MF) {
  38   const MachineFrameInfo &MFI = MF.getFrameInfo();
  39   return MinAlign(Offset, MFI.getObjectAlignment(FrameIdx));
  40   // TODO: How to handle cases with Base + Offset?
  41 }
  42
  43 unsigned GISelKnownBits::inferPtrAlignment(const MachineInstr &MI) {
  44   if (MI.getOpcode() == TargetOpcode::G_FRAME_INDEX) {
  45     int FrameIdx = MI.getOperand(1).getIndex();
  46     return inferAlignmentForFrameIdx(FrameIdx, 0, *MI.getMF());
  47   }
  48   return 0;
  49 }
  50
  51 void GISelKnownBits::computeKnownBitsForFrameIndex(Register R, KnownBits &Known,
  52                                                    const APInt &DemandedElts,
  53                                                    unsigned Depth) {
  54   const MachineInstr &MI = *MRI.getVRegDef(R);
  55   computeKnownBitsForAlignment(Known, inferPtrAlignment(MI));
  56 }
  57
  58 void GISelKnownBits::computeKnownBitsForAlignment(KnownBits &Known,
  59                                                   unsigned Align) {
  60   if (Align)
  61     // The low bits are known zero if the pointer is aligned.
  62     Known.Zero.setLowBits(Log2_32(Align));
  63 }
  64
  65 KnownBits GISelKnownBits::getKnownBits(MachineInstr &MI) {
  66   return getKnownBits(MI.getOperand(0).getReg());
  67 }
  68
  69 KnownBits GISelKnownBits::getKnownBits(Register R) {
  70   KnownBits Known;
  71   LLT Ty = MRI.getType(R);
  72   APInt DemandedElts =
  73       Ty.isVector() ? APInt::getAllOnesValue(Ty.getNumElements()) : APInt(1, 1);
  74   computeKnownBitsImpl(R, Known, DemandedElts);
  75   return Known;
  76 }
  77
  78 bool GISelKnownBits::signBitIsZero(Register R) {
  79   LLT Ty = MRI.getType(R);
  80   unsigned BitWidth = Ty.getScalarSizeInBits();
  81   return maskedValueIsZero(R, APInt::getSignMask(BitWidth));
  82 }
  83
  84 APInt GISelKnownBits::getKnownZeroes(Register R) {
  85   return getKnownBits(R).Zero;
  86 }
  87
  88 APInt GISelKnownBits::getKnownOnes(Register R) { return getKnownBits(R).One; }
  89
  90 void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known,
  91                                           const APInt &DemandedElts,
  92                                           unsigned Depth) {
  93   MachineInstr &MI = *MRI.getVRegDef(R);
  94   unsigned Opcode = MI.getOpcode();
  95   LLT DstTy = MRI.getType(R);
  96
  97   // Handle the case where this is called on a register that does not have a
  98   // type constraint (i.e. it has a register class constraint instead). This is
  99   // unlikely to occur except by looking through copies but it is possible for
 100   // the initial register being queried to be in this state.
 101   if (!DstTy.isValid()) {
 102     Known = KnownBits();
 103     return;
 104   }
 105
 106   unsigned BitWidth = DstTy.getSizeInBits();
 107   Known = KnownBits(BitWidth); // Don't know anything
 108
 109   if (DstTy.isVector())
 110     return; // TODO: Handle vectors.
 111
 112   if (Depth == getMaxDepth())
 113     return;
 114
 115   if (!DemandedElts)
 116     return; // No demanded elts, better to assume we don't know anything.
 117
 118   KnownBits Known2;
 119
 120   switch (Opcode) {
 121   default:
 122     TL.computeKnownBitsForTargetInstr(R, Known, DemandedElts, MRI, Depth);
 123     break;
 124   case TargetOpcode::COPY: {
 125     MachineOperand Dst = MI.getOperand(0);
 126     MachineOperand Src = MI.getOperand(1);
 127     // Look through trivial copies but don't look through trivial copies of the
 128     // form `%1:(s32) = OP %0:gpr32` known-bits analysis is currently unable to
 129     // determine the bit width of a register class.
 130     //
 131     // We can't use NoSubRegister by name as it's defined by each target but
 132     // it's always defined to be 0 by tablegen.
 133     if (Dst.getSubReg() == 0 /*NoSubRegister*/ && Src.getReg().isVirtual() &&
 134         Src.getSubReg() == 0 /*NoSubRegister*/ &&
 135         MRI.getType(Src.getReg()).isValid()) {
 136       // Don't increment Depth for this one since we didn't do any work.
 137       computeKnownBitsImpl(Src.getReg(), Known, DemandedElts, Depth);
 138     }
 139     break;
 140   }
 141   case TargetOpcode::G_CONSTANT: {
 142     auto CstVal = getConstantVRegVal(R, MRI);
 143     if (!CstVal)
 144       break;
 145     Known.One = *CstVal;
 146     Known.Zero = ~Known.One;
 147     break;
 148   }
 149   case TargetOpcode::G_FRAME_INDEX: {
 150     computeKnownBitsForFrameIndex(R, Known, DemandedElts);
 151     break;
 152   }
 153   case TargetOpcode::G_SUB: {
 154     // If low bits are known to be zero in both operands, then we know they are
 155     // going to be 0 in the result. Both addition and complement operations
 156     // preserve the low zero bits.
 157     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 158                          Depth + 1);
 159     unsigned KnownZeroLow = Known2.countMinTrailingZeros();
 160     if (KnownZeroLow == 0)
 161       break;
 162     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
 163                          Depth + 1);
 164     KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
 165     Known.Zero.setLowBits(KnownZeroLow);
 166     break;
 167   }
 168   case TargetOpcode::G_XOR: {
 169     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 170                          Depth + 1);
 171     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 172                          Depth + 1);
 173
 174     // Output known-0 bits are known if clear or set in both the LHS & RHS.
 175     APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
 176     // Output known-1 are known to be set if set in only one of the LHS, RHS.
 177     Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
 178     Known.Zero = KnownZeroOut;
 179     break;
 180   }
 181   case TargetOpcode::G_GEP: {
 182     // G_GEP is like G_ADD. FIXME: Is this true for all targets?
 183     LLT Ty = MRI.getType(MI.getOperand(1).getReg());
 184     if (DL.isNonIntegralAddressSpace(Ty.getAddressSpace()))
 185       break;
 186     LLVM_FALLTHROUGH;
 187   }
 188   case TargetOpcode::G_ADD: {
 189     // Output known-0 bits are known if clear or set in both the low clear bits
 190     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
 191     // low 3 bits clear.
 192     // Output known-0 bits are also known if the top bits of each input are
 193     // known to be clear. For example, if one input has the top 10 bits clear
 194     // and the other has the top 8 bits clear, we know the top 7 bits of the
 195     // output must be clear.
 196     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 197                          Depth + 1);
 198     unsigned KnownZeroHigh = Known2.countMinLeadingZeros();
 199     unsigned KnownZeroLow = Known2.countMinTrailingZeros();
 200     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
 201                          Depth + 1);
 202     KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros());
 203     KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
 204     Known.Zero.setLowBits(KnownZeroLow);
 205     if (KnownZeroHigh > 1)
 206       Known.Zero.setHighBits(KnownZeroHigh - 1);
 207     break;
 208   }
 209   case TargetOpcode::G_AND: {
 210     // If either the LHS or the RHS are Zero, the result is zero.
 211     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 212                          Depth + 1);
 213     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 214                          Depth + 1);
 215
 216     // Output known-1 bits are only known if set in both the LHS & RHS.
 217     Known.One &= Known2.One;
 218     // Output known-0 are known to be clear if zero in either the LHS | RHS.
 219     Known.Zero |= Known2.Zero;
 220     break;
 221   }
 222   case TargetOpcode::G_OR: {
 223     // If either the LHS or the RHS are Zero, the result is zero.
 224     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 225                          Depth + 1);
 226     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 227                          Depth + 1);
 228
 229     // Output known-0 bits are only known if clear in both the LHS & RHS.
 230     Known.Zero &= Known2.Zero;
 231     // Output known-1 are known to be set if set in either the LHS | RHS.
 232     Known.One |= Known2.One;
 233     break;
 234   }
 235   case TargetOpcode::G_MUL: {
 236     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 237                          Depth + 1);
 238     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 239                          Depth + 1);
 240     // If low bits are zero in either operand, output low known-0 bits.
 241     // Also compute a conservative estimate for high known-0 bits.
 242     // More trickiness is possible, but this is sufficient for the
 243     // interesting case of alignment computation.
 244     unsigned TrailZ =
 245         Known.countMinTrailingZeros() + Known2.countMinTrailingZeros();
 246     unsigned LeadZ =
 247         std::max(Known.countMinLeadingZeros() + Known2.countMinLeadingZeros(),
 248                  BitWidth) -
 249         BitWidth;
 250
 251     Known.resetAll();
 252     Known.Zero.setLowBits(std::min(TrailZ, BitWidth));
 253     Known.Zero.setHighBits(std::min(LeadZ, BitWidth));
 254     break;
 255   }
 256   case TargetOpcode::G_SELECT: {
 257     computeKnownBitsImpl(MI.getOperand(3).getReg(), Known, DemandedElts,
 258                          Depth + 1);
 259     // If we don't know any bits, early out.
 260     if (Known.isUnknown())
 261       break;
 262     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
 263                          Depth + 1);
 264     // Only known if known in both the LHS and RHS.
 265     Known.One &= Known2.One;
 266     Known.Zero &= Known2.Zero;
 267     break;
 268   }
 269   case TargetOpcode::G_FCMP:
 270   case TargetOpcode::G_ICMP: {
 271     if (TL.getBooleanContents(DstTy.isVector(),
 272                               Opcode == TargetOpcode::G_FCMP) ==
 273             TargetLowering::ZeroOrOneBooleanContent &&
 274         BitWidth > 1)
 275       Known.Zero.setBitsFrom(1);
 276     break;
 277   }
 278   case TargetOpcode::G_SEXT: {
 279     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 280                          Depth + 1);
 281     // If the sign bit is known to be zero or one, then sext will extend
 282     // it to the top bits, else it will just zext.
 283     Known = Known.sext(BitWidth);
 284     break;
 285   }
 286   case TargetOpcode::G_ANYEXT: {
 287     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 288                          Depth + 1);
 289     Known = Known.zext(BitWidth, true /* ExtendedBitsAreKnownZero */);
 290     break;
 291   }
 292   case TargetOpcode::G_LOAD: {
 293     if (MI.hasOneMemOperand()) {
 294       const MachineMemOperand *MMO = *MI.memoperands_begin();
 295       if (const MDNode *Ranges = MMO->getRanges()) {
 296         computeKnownBitsFromRangeMetadata(*Ranges, Known);
 297       }
 298     }
 299     break;
 300   }
 301   case TargetOpcode::G_ZEXTLOAD: {
 302     // Everything above the retrieved bits is zero
 303     if (MI.hasOneMemOperand())
 304       Known.Zero.setBitsFrom((*MI.memoperands_begin())->getSizeInBits());
 305     break;
 306   }
 307   case TargetOpcode::G_ASHR:
 308   case TargetOpcode::G_LSHR:
 309   case TargetOpcode::G_SHL: {
 310     KnownBits RHSKnown;
 311     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
 312                          Depth + 1);
 313     if (!RHSKnown.isConstant()) {
 314       LLVM_DEBUG(
 315           MachineInstr *RHSMI = MRI.getVRegDef(MI.getOperand(2).getReg());
 316           dbgs() << '[' << Depth << "] Shift not known constant: " << *RHSMI);
 317       break;
 318     }
 319     uint64_t Shift = RHSKnown.getConstant().getZExtValue();
 320     LLVM_DEBUG(dbgs() << '[' << Depth << "] Shift is " << Shift << '\n');
 321
 322     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 323                          Depth + 1);
 324
 325     switch (Opcode) {
 326     case TargetOpcode::G_ASHR:
 327       Known.Zero = Known.Zero.ashr(Shift);
 328       Known.One = Known.One.ashr(Shift);
 329       break;
 330     case TargetOpcode::G_LSHR:
 331       Known.Zero = Known.Zero.lshr(Shift);
 332       Known.One = Known.One.lshr(Shift);
 333       Known.Zero.setBitsFrom(Known.Zero.getBitWidth() - Shift);
 334       break;
 335     case TargetOpcode::G_SHL:
 336       Known.Zero = Known.Zero.shl(Shift);
 337       Known.One = Known.One.shl(Shift);
 338       Known.Zero.setBits(0, Shift);
 339       break;
 340     }
 341     break;
 342   }
 343   case TargetOpcode::G_INTTOPTR:
 344   case TargetOpcode::G_PTRTOINT:
 345     // Fall through and handle them the same as zext/trunc.
 346     LLVM_FALLTHROUGH;
 347   case TargetOpcode::G_ZEXT:
 348   case TargetOpcode::G_TRUNC: {
 349     Register SrcReg = MI.getOperand(1).getReg();
 350     LLT SrcTy = MRI.getType(SrcReg);
 351     unsigned SrcBitWidth = SrcTy.isPointer()
 352                                ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
 353                                : SrcTy.getSizeInBits();
 354     assert(SrcBitWidth && "SrcBitWidth can't be zero");
 355     Known = Known.zextOrTrunc(SrcBitWidth, true);
 356     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
 357     Known = Known.zextOrTrunc(BitWidth, true);
 358     if (BitWidth > SrcBitWidth)
 359       Known.Zero.setBitsFrom(SrcBitWidth);
 360     break;
 361   }
 362   }
 363
 364   assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 365   LLVM_DEBUG(dbgs() << "[" << Depth << "] Compute known bits: " << MI << "["
 366                     << Depth << "] Computed for: " << MI << "[" << Depth
 367                     << "] Known: 0x"
 368                     << (Known.Zero | Known.One).toString(16, false) << "\n"
 369                     << "[" << Depth << "] Zero: 0x"
 370                     << Known.Zero.toString(16, false) << "\n"
 371                     << "[" << Depth << "] One:  0x"
 372                     << Known.One.toString(16, false) << "\n");
 373 }
 374
 375 void GISelKnownBitsAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 376   AU.setPreservesAll();
 377   MachineFunctionPass::getAnalysisUsage(AU);
 378 }
 379
 380 bool GISelKnownBitsAnalysis::runOnMachineFunction(MachineFunction &MF) {
 381   return false;
 382 }