1 //===- llvm/Support/KnownBits.h - Stores known zeros/ones -------*- 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 // This file contains a class for representing known zeros and ones used by 10 // computeKnownBits. 11 // 12 //===----------------------------------------------------------------------===// 13 14 #ifndef LLVM_SUPPORT_KNOWNBITS_H 15 #define LLVM_SUPPORT_KNOWNBITS_H 16 17 #include "llvm/ADT/APInt.h" 18 #include "llvm/Support/Compiler.h" 19 #include <optional> 20 21 namespace llvm { 22 23 // Struct for tracking the known zeros and ones of a value. 24 struct KnownBits { 25 APInt Zero; 26 APInt One; 27 28 private: 29 // Internal constructor for creating a KnownBits from two APInts. KnownBitsKnownBits30 KnownBits(APInt Zero, APInt One) 31 : Zero(std::move(Zero)), One(std::move(One)) {} 32 33 // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0, 0xFFFFFFFF] 34 static KnownBits flipSignBit(const KnownBits &Val); 35 36 public: 37 // Default construct Zero and One. 38 KnownBits() = default; 39 40 /// Create a known bits object of BitWidth bits initialized to unknown. KnownBitsKnownBits41 KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {} 42 43 /// Get the bit width of this value. getBitWidthKnownBits44 unsigned getBitWidth() const { 45 assert(Zero.getBitWidth() == One.getBitWidth() && 46 "Zero and One should have the same width!"); 47 return Zero.getBitWidth(); 48 } 49 50 /// Returns true if there is conflicting information. hasConflictKnownBits51 bool hasConflict() const { return Zero.intersects(One); } 52 53 /// Returns true if we know the value of all bits. isConstantKnownBits54 bool isConstant() const { 55 return Zero.popcount() + One.popcount() == getBitWidth(); 56 } 57 58 /// Returns the value when all bits have a known value. This just returns One 59 /// with a protective assertion. getConstantKnownBits60 const APInt &getConstant() const { 61 assert(isConstant() && "Can only get value when all bits are known"); 62 return One; 63 } 64 65 /// Returns true if we don't know any bits. isUnknownKnownBits66 bool isUnknown() const { return Zero.isZero() && One.isZero(); } 67 68 /// Returns true if we don't know the sign bit. isSignUnknownKnownBits69 bool isSignUnknown() const { 70 return !Zero.isSignBitSet() && !One.isSignBitSet(); 71 } 72 73 /// Resets the known state of all bits. resetAllKnownBits74 void resetAll() { 75 Zero.clearAllBits(); 76 One.clearAllBits(); 77 } 78 79 /// Returns true if value is all zero. isZeroKnownBits80 bool isZero() const { return Zero.isAllOnes(); } 81 82 /// Returns true if value is all one bits. isAllOnesKnownBits83 bool isAllOnes() const { return One.isAllOnes(); } 84 85 /// Make all bits known to be zero and discard any previous information. setAllZeroKnownBits86 void setAllZero() { 87 Zero.setAllBits(); 88 One.clearAllBits(); 89 } 90 91 /// Make all bits known to be one and discard any previous information. setAllOnesKnownBits92 void setAllOnes() { 93 Zero.clearAllBits(); 94 One.setAllBits(); 95 } 96 97 /// Returns true if this value is known to be negative. isNegativeKnownBits98 bool isNegative() const { return One.isSignBitSet(); } 99 100 /// Returns true if this value is known to be non-negative. isNonNegativeKnownBits101 bool isNonNegative() const { return Zero.isSignBitSet(); } 102 103 /// Returns true if this value is known to be non-zero. isNonZeroKnownBits104 bool isNonZero() const { return !One.isZero(); } 105 106 /// Returns true if this value is known to be positive. isStrictlyPositiveKnownBits107 bool isStrictlyPositive() const { 108 return Zero.isSignBitSet() && !One.isZero(); 109 } 110 111 /// Make this value negative. makeNegativeKnownBits112 void makeNegative() { 113 One.setSignBit(); 114 } 115 116 /// Make this value non-negative. makeNonNegativeKnownBits117 void makeNonNegative() { 118 Zero.setSignBit(); 119 } 120 121 /// Return the minimal unsigned value possible given these KnownBits. getMinValueKnownBits122 APInt getMinValue() const { 123 // Assume that all bits that aren't known-ones are zeros. 124 return One; 125 } 126 127 /// Return the minimal signed value possible given these KnownBits. getSignedMinValueKnownBits128 APInt getSignedMinValue() const { 129 // Assume that all bits that aren't known-ones are zeros. 130 APInt Min = One; 131 // Sign bit is unknown. 132 if (Zero.isSignBitClear()) 133 Min.setSignBit(); 134 return Min; 135 } 136 137 /// Return the maximal unsigned value possible given these KnownBits. getMaxValueKnownBits138 APInt getMaxValue() const { 139 // Assume that all bits that aren't known-zeros are ones. 140 return ~Zero; 141 } 142 143 /// Return the maximal signed value possible given these KnownBits. getSignedMaxValueKnownBits144 APInt getSignedMaxValue() const { 145 // Assume that all bits that aren't known-zeros are ones. 146 APInt Max = ~Zero; 147 // Sign bit is unknown. 148 if (One.isSignBitClear()) 149 Max.clearSignBit(); 150 return Max; 151 } 152 153 /// Return known bits for a truncation of the value we're tracking. truncKnownBits154 KnownBits trunc(unsigned BitWidth) const { 155 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth)); 156 } 157 158 /// Return known bits for an "any" extension of the value we're tracking, 159 /// where we don't know anything about the extended bits. anyextKnownBits160 KnownBits anyext(unsigned BitWidth) const { 161 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth)); 162 } 163 164 /// Return known bits for a zero extension of the value we're tracking. zextKnownBits165 KnownBits zext(unsigned BitWidth) const { 166 unsigned OldBitWidth = getBitWidth(); 167 APInt NewZero = Zero.zext(BitWidth); 168 NewZero.setBitsFrom(OldBitWidth); 169 return KnownBits(NewZero, One.zext(BitWidth)); 170 } 171 172 /// Return known bits for a sign extension of the value we're tracking. sextKnownBits173 KnownBits sext(unsigned BitWidth) const { 174 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth)); 175 } 176 177 /// Return known bits for an "any" extension or truncation of the value we're 178 /// tracking. anyextOrTruncKnownBits179 KnownBits anyextOrTrunc(unsigned BitWidth) const { 180 if (BitWidth > getBitWidth()) 181 return anyext(BitWidth); 182 if (BitWidth < getBitWidth()) 183 return trunc(BitWidth); 184 return *this; 185 } 186 187 /// Return known bits for a zero extension or truncation of the value we're 188 /// tracking. zextOrTruncKnownBits189 KnownBits zextOrTrunc(unsigned BitWidth) const { 190 if (BitWidth > getBitWidth()) 191 return zext(BitWidth); 192 if (BitWidth < getBitWidth()) 193 return trunc(BitWidth); 194 return *this; 195 } 196 197 /// Return known bits for a sign extension or truncation of the value we're 198 /// tracking. sextOrTruncKnownBits199 KnownBits sextOrTrunc(unsigned BitWidth) const { 200 if (BitWidth > getBitWidth()) 201 return sext(BitWidth); 202 if (BitWidth < getBitWidth()) 203 return trunc(BitWidth); 204 return *this; 205 } 206 207 /// Return known bits for a in-register sign extension of the value we're 208 /// tracking. 209 LLVM_ABI KnownBits sextInReg(unsigned SrcBitWidth) const; 210 211 /// Insert the bits from a smaller known bits starting at bitPosition. insertBitsKnownBits212 void insertBits(const KnownBits &SubBits, unsigned BitPosition) { 213 Zero.insertBits(SubBits.Zero, BitPosition); 214 One.insertBits(SubBits.One, BitPosition); 215 } 216 217 /// Return a subset of the known bits from [bitPosition,bitPosition+numBits). extractBitsKnownBits218 KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const { 219 return KnownBits(Zero.extractBits(NumBits, BitPosition), 220 One.extractBits(NumBits, BitPosition)); 221 } 222 223 /// Concatenate the bits from \p Lo onto the bottom of *this. This is 224 /// equivalent to: 225 /// (this->zext(NewWidth) << Lo.getBitWidth()) | Lo.zext(NewWidth) concatKnownBits226 KnownBits concat(const KnownBits &Lo) const { 227 return KnownBits(Zero.concat(Lo.Zero), One.concat(Lo.One)); 228 } 229 230 /// Return KnownBits based on this, but updated given that the underlying 231 /// value is known to be greater than or equal to Val. 232 LLVM_ABI KnownBits makeGE(const APInt &Val) const; 233 234 /// Returns the minimum number of trailing zero bits. countMinTrailingZerosKnownBits235 unsigned countMinTrailingZeros() const { return Zero.countr_one(); } 236 237 /// Returns the minimum number of trailing one bits. countMinTrailingOnesKnownBits238 unsigned countMinTrailingOnes() const { return One.countr_one(); } 239 240 /// Returns the minimum number of leading zero bits. countMinLeadingZerosKnownBits241 unsigned countMinLeadingZeros() const { return Zero.countl_one(); } 242 243 /// Returns the minimum number of leading one bits. countMinLeadingOnesKnownBits244 unsigned countMinLeadingOnes() const { return One.countl_one(); } 245 246 /// Returns the number of times the sign bit is replicated into the other 247 /// bits. countMinSignBitsKnownBits248 unsigned countMinSignBits() const { 249 if (isNonNegative()) 250 return countMinLeadingZeros(); 251 if (isNegative()) 252 return countMinLeadingOnes(); 253 // Every value has at least 1 sign bit. 254 return 1; 255 } 256 257 /// Returns the maximum number of bits needed to represent all possible 258 /// signed values with these known bits. This is the inverse of the minimum 259 /// number of known sign bits. Examples for bitwidth 5: 260 /// 110?? --> 4 261 /// 0000? --> 2 countMaxSignificantBitsKnownBits262 unsigned countMaxSignificantBits() const { 263 return getBitWidth() - countMinSignBits() + 1; 264 } 265 266 /// Returns the maximum number of trailing zero bits possible. countMaxTrailingZerosKnownBits267 unsigned countMaxTrailingZeros() const { return One.countr_zero(); } 268 269 /// Returns the maximum number of trailing one bits possible. countMaxTrailingOnesKnownBits270 unsigned countMaxTrailingOnes() const { return Zero.countr_zero(); } 271 272 /// Returns the maximum number of leading zero bits possible. countMaxLeadingZerosKnownBits273 unsigned countMaxLeadingZeros() const { return One.countl_zero(); } 274 275 /// Returns the maximum number of leading one bits possible. countMaxLeadingOnesKnownBits276 unsigned countMaxLeadingOnes() const { return Zero.countl_zero(); } 277 278 /// Returns the number of bits known to be one. countMinPopulationKnownBits279 unsigned countMinPopulation() const { return One.popcount(); } 280 281 /// Returns the maximum number of bits that could be one. countMaxPopulationKnownBits282 unsigned countMaxPopulation() const { 283 return getBitWidth() - Zero.popcount(); 284 } 285 286 /// Returns the maximum number of bits needed to represent all possible 287 /// unsigned values with these known bits. This is the inverse of the 288 /// minimum number of leading zeros. countMaxActiveBitsKnownBits289 unsigned countMaxActiveBits() const { 290 return getBitWidth() - countMinLeadingZeros(); 291 } 292 293 /// Create known bits from a known constant. makeConstantKnownBits294 static KnownBits makeConstant(const APInt &C) { 295 return KnownBits(~C, C); 296 } 297 298 /// Returns KnownBits information that is known to be true for both this and 299 /// RHS. 300 /// 301 /// When an operation is known to return one of its operands, this can be used 302 /// to combine information about the known bits of the operands to get the 303 /// information that must be true about the result. intersectWithKnownBits304 KnownBits intersectWith(const KnownBits &RHS) const { 305 return KnownBits(Zero & RHS.Zero, One & RHS.One); 306 } 307 308 /// Returns KnownBits information that is known to be true for either this or 309 /// RHS or both. 310 /// 311 /// This can be used to combine different sources of information about the 312 /// known bits of a single value, e.g. information about the low bits and the 313 /// high bits of the result of a multiplication. unionWithKnownBits314 KnownBits unionWith(const KnownBits &RHS) const { 315 return KnownBits(Zero | RHS.Zero, One | RHS.One); 316 } 317 318 /// Return true if LHS and RHS have no common bits set. haveNoCommonBitsSetKnownBits319 static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) { 320 return (LHS.Zero | RHS.Zero).isAllOnes(); 321 } 322 323 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry. 324 LLVM_ABI static KnownBits computeForAddCarry(const KnownBits &LHS, 325 const KnownBits &RHS, 326 const KnownBits &Carry); 327 328 /// Compute known bits resulting from adding LHS and RHS. 329 LLVM_ABI static KnownBits computeForAddSub(bool Add, bool NSW, bool NUW, 330 const KnownBits &LHS, 331 const KnownBits &RHS); 332 333 /// Compute known bits results from subtracting RHS from LHS with 1-bit 334 /// Borrow. 335 LLVM_ABI static KnownBits computeForSubBorrow(const KnownBits &LHS, 336 KnownBits RHS, 337 const KnownBits &Borrow); 338 339 /// Compute knownbits resulting from addition of LHS and RHS. 340 static KnownBits add(const KnownBits &LHS, const KnownBits &RHS, 341 bool NSW = false, bool NUW = false) { 342 return computeForAddSub(/*Add=*/true, NSW, NUW, LHS, RHS); 343 } 344 345 /// Compute knownbits resulting from subtraction of LHS and RHS. 346 static KnownBits sub(const KnownBits &LHS, const KnownBits &RHS, 347 bool NSW = false, bool NUW = false) { 348 return computeForAddSub(/*Add=*/false, NSW, NUW, LHS, RHS); 349 } 350 351 /// Compute knownbits resulting from llvm.sadd.sat(LHS, RHS) 352 LLVM_ABI static KnownBits sadd_sat(const KnownBits &LHS, 353 const KnownBits &RHS); 354 355 /// Compute knownbits resulting from llvm.uadd.sat(LHS, RHS) 356 LLVM_ABI static KnownBits uadd_sat(const KnownBits &LHS, 357 const KnownBits &RHS); 358 359 /// Compute knownbits resulting from llvm.ssub.sat(LHS, RHS) 360 LLVM_ABI static KnownBits ssub_sat(const KnownBits &LHS, 361 const KnownBits &RHS); 362 363 /// Compute knownbits resulting from llvm.usub.sat(LHS, RHS) 364 LLVM_ABI static KnownBits usub_sat(const KnownBits &LHS, 365 const KnownBits &RHS); 366 367 /// Compute knownbits resulting from APIntOps::avgFloorS 368 LLVM_ABI static KnownBits avgFloorS(const KnownBits &LHS, 369 const KnownBits &RHS); 370 371 /// Compute knownbits resulting from APIntOps::avgFloorU 372 LLVM_ABI static KnownBits avgFloorU(const KnownBits &LHS, 373 const KnownBits &RHS); 374 375 /// Compute knownbits resulting from APIntOps::avgCeilS 376 LLVM_ABI static KnownBits avgCeilS(const KnownBits &LHS, 377 const KnownBits &RHS); 378 379 /// Compute knownbits resulting from APIntOps::avgCeilU 380 LLVM_ABI static KnownBits avgCeilU(const KnownBits &LHS, 381 const KnownBits &RHS); 382 383 /// Compute known bits resulting from multiplying LHS and RHS. 384 LLVM_ABI static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, 385 bool NoUndefSelfMultiply = false); 386 387 /// Compute known bits from sign-extended multiply-hi. 388 LLVM_ABI static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS); 389 390 /// Compute known bits from zero-extended multiply-hi. 391 LLVM_ABI static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS); 392 393 /// Compute known bits for sdiv(LHS, RHS). 394 LLVM_ABI static KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS, 395 bool Exact = false); 396 397 /// Compute known bits for udiv(LHS, RHS). 398 LLVM_ABI static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, 399 bool Exact = false); 400 401 /// Compute known bits for urem(LHS, RHS). 402 LLVM_ABI static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS); 403 404 /// Compute known bits for srem(LHS, RHS). 405 LLVM_ABI static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS); 406 407 /// Compute known bits for umax(LHS, RHS). 408 LLVM_ABI static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS); 409 410 /// Compute known bits for umin(LHS, RHS). 411 LLVM_ABI static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS); 412 413 /// Compute known bits for smax(LHS, RHS). 414 LLVM_ABI static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS); 415 416 /// Compute known bits for smin(LHS, RHS). 417 LLVM_ABI static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS); 418 419 /// Compute known bits for abdu(LHS, RHS). 420 LLVM_ABI static KnownBits abdu(const KnownBits &LHS, const KnownBits &RHS); 421 422 /// Compute known bits for abds(LHS, RHS). 423 LLVM_ABI static KnownBits abds(KnownBits LHS, KnownBits RHS); 424 425 /// Compute known bits for shl(LHS, RHS). 426 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. 427 LLVM_ABI static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, 428 bool NUW = false, bool NSW = false, 429 bool ShAmtNonZero = false); 430 431 /// Compute known bits for lshr(LHS, RHS). 432 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. 433 LLVM_ABI static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, 434 bool ShAmtNonZero = false, bool Exact = false); 435 436 /// Compute known bits for ashr(LHS, RHS). 437 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. 438 LLVM_ABI static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, 439 bool ShAmtNonZero = false, bool Exact = false); 440 441 /// Determine if these known bits always give the same ICMP_EQ result. 442 LLVM_ABI static std::optional<bool> eq(const KnownBits &LHS, 443 const KnownBits &RHS); 444 445 /// Determine if these known bits always give the same ICMP_NE result. 446 LLVM_ABI static std::optional<bool> ne(const KnownBits &LHS, 447 const KnownBits &RHS); 448 449 /// Determine if these known bits always give the same ICMP_UGT result. 450 LLVM_ABI static std::optional<bool> ugt(const KnownBits &LHS, 451 const KnownBits &RHS); 452 453 /// Determine if these known bits always give the same ICMP_UGE result. 454 LLVM_ABI static std::optional<bool> uge(const KnownBits &LHS, 455 const KnownBits &RHS); 456 457 /// Determine if these known bits always give the same ICMP_ULT result. 458 LLVM_ABI static std::optional<bool> ult(const KnownBits &LHS, 459 const KnownBits &RHS); 460 461 /// Determine if these known bits always give the same ICMP_ULE result. 462 LLVM_ABI static std::optional<bool> ule(const KnownBits &LHS, 463 const KnownBits &RHS); 464 465 /// Determine if these known bits always give the same ICMP_SGT result. 466 LLVM_ABI static std::optional<bool> sgt(const KnownBits &LHS, 467 const KnownBits &RHS); 468 469 /// Determine if these known bits always give the same ICMP_SGE result. 470 LLVM_ABI static std::optional<bool> sge(const KnownBits &LHS, 471 const KnownBits &RHS); 472 473 /// Determine if these known bits always give the same ICMP_SLT result. 474 LLVM_ABI static std::optional<bool> slt(const KnownBits &LHS, 475 const KnownBits &RHS); 476 477 /// Determine if these known bits always give the same ICMP_SLE result. 478 LLVM_ABI static std::optional<bool> sle(const KnownBits &LHS, 479 const KnownBits &RHS); 480 481 /// Update known bits based on ANDing with RHS. 482 LLVM_ABI KnownBits &operator&=(const KnownBits &RHS); 483 484 /// Update known bits based on ORing with RHS. 485 LLVM_ABI KnownBits &operator|=(const KnownBits &RHS); 486 487 /// Update known bits based on XORing with RHS. 488 LLVM_ABI KnownBits &operator^=(const KnownBits &RHS); 489 490 /// Compute known bits for the absolute value. 491 LLVM_ABI KnownBits abs(bool IntMinIsPoison = false) const; 492 byteSwapKnownBits493 KnownBits byteSwap() const { 494 return KnownBits(Zero.byteSwap(), One.byteSwap()); 495 } 496 reverseBitsKnownBits497 KnownBits reverseBits() const { 498 return KnownBits(Zero.reverseBits(), One.reverseBits()); 499 } 500 501 /// Compute known bits for X & -X, which has only the lowest bit set of X set. 502 /// The name comes from the X86 BMI instruction 503 LLVM_ABI KnownBits blsi() const; 504 505 /// Compute known bits for X ^ (X - 1), which has all bits up to and including 506 /// the lowest set bit of X set. The name comes from the X86 BMI instruction. 507 LLVM_ABI KnownBits blsmsk() const; 508 509 bool operator==(const KnownBits &Other) const { 510 return Zero == Other.Zero && One == Other.One; 511 } 512 513 bool operator!=(const KnownBits &Other) const { return !(*this == Other); } 514 515 LLVM_ABI void print(raw_ostream &OS) const; 516 517 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 518 LLVM_DUMP_METHOD void dump() const; 519 #endif 520 521 private: 522 // Internal helper for getting the initial KnownBits for an `srem` or `urem` 523 // operation with the low-bits set. 524 static KnownBits remGetLowBits(const KnownBits &LHS, const KnownBits &RHS); 525 }; 526 527 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) { 528 LHS &= RHS; 529 return LHS; 530 } 531 532 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) { 533 RHS &= LHS; 534 return std::move(RHS); 535 } 536 537 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) { 538 LHS |= RHS; 539 return LHS; 540 } 541 542 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) { 543 RHS |= LHS; 544 return std::move(RHS); 545 } 546 547 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) { 548 LHS ^= RHS; 549 return LHS; 550 } 551 552 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) { 553 RHS ^= LHS; 554 return std::move(RHS); 555 } 556 557 inline raw_ostream &operator<<(raw_ostream &OS, const KnownBits &Known) { 558 Known.print(OS); 559 return OS; 560 } 561 562 } // end namespace llvm 563 564 #endif 565