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 } 721