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 APInt GISelKnownBits::getKnownZeroes(Register R) {
  79   return getKnownBits(R).Zero;
  80 }
  81
  82 APInt GISelKnownBits::getKnownOnes(Register R) { return getKnownBits(R).One; }
  83
  84 void GISelKnownBits::computeKnownBitsImpl(Register R, KnownBits &Known,
  85                                           const APInt &DemandedElts,
  86                                           unsigned Depth) {
  87   MachineInstr &MI = *MRI.getVRegDef(R);
  88   unsigned Opcode = MI.getOpcode();
  89   LLT DstTy = MRI.getType(R);
  90
  91   unsigned BitWidth = DstTy.getSizeInBits();
  92   Known = KnownBits(BitWidth); // Don't know anything
  93
  94   if (DstTy.isVector())
  95     return; // TODO: Handle vectors.
  96
  97   if (Depth == getMaxDepth())
  98     return;
  99
 100   if (!DemandedElts)
 101     return; // No demanded elts, better to assume we don't know anything.
 102
 103   KnownBits Known2;
 104
 105   switch (Opcode) {
 106   default:
 107     TL.computeKnownBitsForTargetInstr(R, Known, DemandedElts, MRI, Depth);
 108     break;
 109   case TargetOpcode::G_CONSTANT: {
 110     auto CstVal = getConstantVRegVal(R, MRI);
 111     Known.One = *CstVal;
 112     Known.Zero = ~Known.One;
 113     break;
 114   }
 115   case TargetOpcode::G_FRAME_INDEX: {
 116     computeKnownBitsForFrameIndex(R, Known, DemandedElts);
 117     break;
 118   }
 119   case TargetOpcode::G_SUB: {
 120     // If low bits are known to be zero in both operands, then we know they are
 121     // going to be 0 in the result. Both addition and complement operations
 122     // preserve the low zero bits.
 123     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 124                          Depth + 1);
 125     unsigned KnownZeroLow = Known2.countMinTrailingZeros();
 126     if (KnownZeroLow == 0)
 127       break;
 128     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
 129                          Depth + 1);
 130     KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
 131     Known.Zero.setLowBits(KnownZeroLow);
 132     break;
 133   }
 134   case TargetOpcode::G_XOR: {
 135     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 136                          Depth + 1);
 137     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 138                          Depth + 1);
 139
 140     // Output known-0 bits are known if clear or set in both the LHS & RHS.
 141     APInt KnownZeroOut = (Known.Zero & Known2.Zero) | (Known.One & Known2.One);
 142     // Output known-1 are known to be set if set in only one of the LHS, RHS.
 143     Known.One = (Known.Zero & Known2.One) | (Known.One & Known2.Zero);
 144     Known.Zero = KnownZeroOut;
 145     break;
 146   }
 147   // G_GEP is like G_ADD. FIXME: Is this true for all targets?
 148   case TargetOpcode::G_GEP:
 149   case TargetOpcode::G_ADD: {
 150     // Output known-0 bits are known if clear or set in both the low clear bits
 151     // common to both LHS & RHS.  For example, 8+(X<<3) is known to have the
 152     // low 3 bits clear.
 153     // Output known-0 bits are also known if the top bits of each input are
 154     // known to be clear. For example, if one input has the top 10 bits clear
 155     // and the other has the top 8 bits clear, we know the top 7 bits of the
 156     // output must be clear.
 157     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 158                          Depth + 1);
 159     unsigned KnownZeroHigh = Known2.countMinLeadingZeros();
 160     unsigned KnownZeroLow = Known2.countMinTrailingZeros();
 161     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
 162                          Depth + 1);
 163     KnownZeroHigh = std::min(KnownZeroHigh, Known2.countMinLeadingZeros());
 164     KnownZeroLow = std::min(KnownZeroLow, Known2.countMinTrailingZeros());
 165     Known.Zero.setLowBits(KnownZeroLow);
 166     if (KnownZeroHigh > 1)
 167       Known.Zero.setHighBits(KnownZeroHigh - 1);
 168     break;
 169   }
 170   case TargetOpcode::G_AND: {
 171     // If either the LHS or the RHS are Zero, the result is zero.
 172     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 173                          Depth + 1);
 174     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 175                          Depth + 1);
 176
 177     // Output known-1 bits are only known if set in both the LHS & RHS.
 178     Known.One &= Known2.One;
 179     // Output known-0 are known to be clear if zero in either the LHS | RHS.
 180     Known.Zero |= Known2.Zero;
 181     break;
 182   }
 183   case TargetOpcode::G_OR: {
 184     // If either the LHS or the RHS are Zero, the result is zero.
 185     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 186                          Depth + 1);
 187     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 188                          Depth + 1);
 189
 190     // Output known-0 bits are only known if clear in both the LHS & RHS.
 191     Known.Zero &= Known2.Zero;
 192     // Output known-1 are known to be set if set in either the LHS | RHS.
 193     Known.One |= Known2.One;
 194     break;
 195   }
 196   case TargetOpcode::G_MUL: {
 197     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known, DemandedElts,
 198                          Depth + 1);
 199     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known2, DemandedElts,
 200                          Depth + 1);
 201     // If low bits are zero in either operand, output low known-0 bits.
 202     // Also compute a conservative estimate for high known-0 bits.
 203     // More trickiness is possible, but this is sufficient for the
 204     // interesting case of alignment computation.
 205     unsigned TrailZ =
 206         Known.countMinTrailingZeros() + Known2.countMinTrailingZeros();
 207     unsigned LeadZ =
 208         std::max(Known.countMinLeadingZeros() + Known2.countMinLeadingZeros(),
 209                  BitWidth) -
 210         BitWidth;
 211
 212     Known.resetAll();
 213     Known.Zero.setLowBits(std::min(TrailZ, BitWidth));
 214     Known.Zero.setHighBits(std::min(LeadZ, BitWidth));
 215     break;
 216   }
 217   case TargetOpcode::G_SELECT: {
 218     computeKnownBitsImpl(MI.getOperand(3).getReg(), Known, DemandedElts,
 219                          Depth + 1);
 220     // If we don't know any bits, early out.
 221     if (Known.isUnknown())
 222       break;
 223     computeKnownBitsImpl(MI.getOperand(2).getReg(), Known2, DemandedElts,
 224                          Depth + 1);
 225     // Only known if known in both the LHS and RHS.
 226     Known.One &= Known2.One;
 227     Known.Zero &= Known2.Zero;
 228     break;
 229   }
 230   case TargetOpcode::G_FCMP:
 231   case TargetOpcode::G_ICMP: {
 232     if (TL.getBooleanContents(DstTy.isVector(),
 233                               Opcode == TargetOpcode::G_FCMP) ==
 234             TargetLowering::ZeroOrOneBooleanContent &&
 235         BitWidth > 1)
 236       Known.Zero.setBitsFrom(1);
 237     break;
 238   }
 239   case TargetOpcode::G_SEXT: {
 240     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 241                          Depth + 1);
 242     // If the sign bit is known to be zero or one, then sext will extend
 243     // it to the top bits, else it will just zext.
 244     Known = Known.sext(BitWidth);
 245     break;
 246   }
 247   case TargetOpcode::G_ANYEXT: {
 248     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 249                          Depth + 1);
 250     Known = Known.zext(BitWidth, true /* ExtendedBitsAreKnownZero */);
 251     break;
 252   }
 253   case TargetOpcode::G_LOAD: {
 254     if (MI.hasOneMemOperand()) {
 255       const MachineMemOperand *MMO = *MI.memoperands_begin();
 256       if (const MDNode *Ranges = MMO->getRanges()) {
 257         computeKnownBitsFromRangeMetadata(*Ranges, Known);
 258       }
 259     }
 260     break;
 261   }
 262   case TargetOpcode::G_ZEXTLOAD: {
 263     // Everything above the retrieved bits is zero
 264     if (MI.hasOneMemOperand())
 265       Known.Zero.setBitsFrom((*MI.memoperands_begin())->getSizeInBits());
 266     break;
 267   }
 268   case TargetOpcode::G_ASHR:
 269   case TargetOpcode::G_LSHR:
 270   case TargetOpcode::G_SHL: {
 271     KnownBits RHSKnown;
 272     computeKnownBitsImpl(MI.getOperand(2).getReg(), RHSKnown, DemandedElts,
 273                          Depth + 1);
 274     if (!RHSKnown.isConstant()) {
 275       LLVM_DEBUG(
 276           MachineInstr *RHSMI = MRI.getVRegDef(MI.getOperand(2).getReg());
 277           dbgs() << '[' << Depth << "] Shift not known constant: " << *RHSMI);
 278       break;
 279     }
 280     uint64_t Shift = RHSKnown.getConstant().getZExtValue();
 281     LLVM_DEBUG(dbgs() << '[' << Depth << "] Shift is " << Shift << '\n');
 282
 283     computeKnownBitsImpl(MI.getOperand(1).getReg(), Known, DemandedElts,
 284                          Depth + 1);
 285
 286     switch (Opcode) {
 287     case TargetOpcode::G_ASHR:
 288       Known.Zero = Known.Zero.ashr(Shift);
 289       Known.One = Known.One.ashr(Shift);
 290       break;
 291     case TargetOpcode::G_LSHR:
 292       Known.Zero = Known.Zero.lshr(Shift);
 293       Known.One = Known.One.lshr(Shift);
 294       Known.Zero.setBitsFrom(Known.Zero.getBitWidth() - Shift);
 295       break;
 296     case TargetOpcode::G_SHL:
 297       Known.Zero = Known.Zero.shl(Shift);
 298       Known.One = Known.One.shl(Shift);
 299       Known.Zero.setBits(0, Shift);
 300       break;
 301     }
 302     break;
 303   }
 304   case TargetOpcode::G_INTTOPTR:
 305   case TargetOpcode::G_PTRTOINT:
 306     // Fall through and handle them the same as zext/trunc.
 307     LLVM_FALLTHROUGH;
 308   case TargetOpcode::G_ZEXT:
 309   case TargetOpcode::G_TRUNC: {
 310     Register SrcReg = MI.getOperand(1).getReg();
 311     LLT SrcTy = MRI.getType(SrcReg);
 312     unsigned SrcBitWidth = SrcTy.isPointer()
 313                                ? DL.getIndexSizeInBits(SrcTy.getAddressSpace())
 314                                : SrcTy.getSizeInBits();
 315     assert(SrcBitWidth && "SrcBitWidth can't be zero");
 316     Known = Known.zextOrTrunc(SrcBitWidth, true);
 317     computeKnownBitsImpl(SrcReg, Known, DemandedElts, Depth + 1);
 318     Known = Known.zextOrTrunc(BitWidth, true);
 319     if (BitWidth > SrcBitWidth)
 320       Known.Zero.setBitsFrom(SrcBitWidth);
 321     break;
 322   }
 323   }
 324
 325   assert(!Known.hasConflict() && "Bits known to be one AND zero?");
 326   LLVM_DEBUG(dbgs() << "[" << Depth << "] Compute known bits: " << MI << "["
 327                     << Depth << "] Computed for: " << MI << "[" << Depth
 328                     << "] Known: 0x"
 329                     << (Known.Zero | Known.One).toString(16, false) << "\n"
 330                     << "[" << Depth << "] Zero: 0x"
 331                     << Known.Zero.toString(16, false) << "\n"
 332                     << "[" << Depth << "] One:  0x"
 333                     << Known.One.toString(16, false) << "\n");
 334 }
 335
 336 void GISelKnownBitsAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 337   AU.setPreservesAll();
 338   MachineFunctionPass::getAnalysisUsage(AU);
 339 }
 340
 341 bool GISelKnownBitsAnalysis::runOnMachineFunction(MachineFunction &MF) {
 342   return false;
 343 }