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/ADT/Optional.h" 19 20 namespace llvm { 21 22 // Struct for tracking the known zeros and ones of a value. 23 struct KnownBits { 24 APInt Zero; 25 APInt One; 26 27 private: 28 // Internal constructor for creating a KnownBits from two APInts. 29 KnownBits(APInt Zero, APInt One) 30 : Zero(std::move(Zero)), One(std::move(One)) {} 31 32 public: 33 // Default construct Zero and One. 34 KnownBits() {} 35 36 /// Create a known bits object of BitWidth bits initialized to unknown. 37 KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {} 38 39 /// Get the bit width of this value. 40 unsigned getBitWidth() const { 41 assert(Zero.getBitWidth() == One.getBitWidth() && 42 "Zero and One should have the same width!"); 43 return Zero.getBitWidth(); 44 } 45 46 /// Returns true if there is conflicting information. 47 bool hasConflict() const { return Zero.intersects(One); } 48 49 /// Returns true if we know the value of all bits. 50 bool isConstant() const { 51 assert(!hasConflict() && "KnownBits conflict!"); 52 return Zero.countPopulation() + One.countPopulation() == getBitWidth(); 53 } 54 55 /// Returns the value when all bits have a known value. This just returns One 56 /// with a protective assertion. 57 const APInt &getConstant() const { 58 assert(isConstant() && "Can only get value when all bits are known"); 59 return One; 60 } 61 62 /// Returns true if we don't know any bits. 63 bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); } 64 65 /// Resets the known state of all bits. 66 void resetAll() { 67 Zero.clearAllBits(); 68 One.clearAllBits(); 69 } 70 71 /// Returns true if value is all zero. 72 bool isZero() const { 73 assert(!hasConflict() && "KnownBits conflict!"); 74 return Zero.isAllOnesValue(); 75 } 76 77 /// Returns true if value is all one bits. 78 bool isAllOnes() const { 79 assert(!hasConflict() && "KnownBits conflict!"); 80 return One.isAllOnesValue(); 81 } 82 83 /// Make all bits known to be zero and discard any previous information. 84 void setAllZero() { 85 Zero.setAllBits(); 86 One.clearAllBits(); 87 } 88 89 /// Make all bits known to be one and discard any previous information. 90 void setAllOnes() { 91 Zero.clearAllBits(); 92 One.setAllBits(); 93 } 94 95 /// Returns true if this value is known to be negative. 96 bool isNegative() const { return One.isSignBitSet(); } 97 98 /// Returns true if this value is known to be non-negative. 99 bool isNonNegative() const { return Zero.isSignBitSet(); } 100 101 /// Returns true if this value is known to be non-zero. 102 bool isNonZero() const { return !One.isNullValue(); } 103 104 /// Returns true if this value is known to be positive. 105 bool isStrictlyPositive() const { return Zero.isSignBitSet() && !One.isNullValue(); } 106 107 /// Make this value negative. 108 void makeNegative() { 109 One.setSignBit(); 110 } 111 112 /// Make this value non-negative. 113 void makeNonNegative() { 114 Zero.setSignBit(); 115 } 116 117 /// Return the minimal unsigned value possible given these KnownBits. 118 APInt getMinValue() const { 119 // Assume that all bits that aren't known-ones are zeros. 120 return One; 121 } 122 123 /// Return the minimal signed value possible given these KnownBits. 124 APInt getSignedMinValue() const { 125 // Assume that all bits that aren't known-ones are zeros. 126 APInt Min = One; 127 // Sign bit is unknown. 128 if (Zero.isSignBitClear()) 129 Min.setSignBit(); 130 return Min; 131 } 132 133 /// Return the maximal unsigned value possible given these KnownBits. 134 APInt getMaxValue() const { 135 // Assume that all bits that aren't known-zeros are ones. 136 return ~Zero; 137 } 138 139 /// Return the maximal signed value possible given these KnownBits. 140 APInt getSignedMaxValue() const { 141 // Assume that all bits that aren't known-zeros are ones. 142 APInt Max = ~Zero; 143 // Sign bit is unknown. 144 if (One.isSignBitClear()) 145 Max.clearSignBit(); 146 return Max; 147 } 148 149 /// Return known bits for a truncation of the value we're tracking. 150 KnownBits trunc(unsigned BitWidth) const { 151 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth)); 152 } 153 154 /// Return known bits for an "any" extension of the value we're tracking, 155 /// where we don't know anything about the extended bits. 156 KnownBits anyext(unsigned BitWidth) const { 157 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth)); 158 } 159 160 /// Return known bits for a zero extension of the value we're tracking. 161 KnownBits zext(unsigned BitWidth) const { 162 unsigned OldBitWidth = getBitWidth(); 163 APInt NewZero = Zero.zext(BitWidth); 164 NewZero.setBitsFrom(OldBitWidth); 165 return KnownBits(NewZero, One.zext(BitWidth)); 166 } 167 168 /// Return known bits for a sign extension of the value we're tracking. 169 KnownBits sext(unsigned BitWidth) const { 170 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth)); 171 } 172 173 /// Return known bits for an "any" extension or truncation of the value we're 174 /// tracking. 175 KnownBits anyextOrTrunc(unsigned BitWidth) const { 176 if (BitWidth > getBitWidth()) 177 return anyext(BitWidth); 178 if (BitWidth < getBitWidth()) 179 return trunc(BitWidth); 180 return *this; 181 } 182 183 /// Return known bits for a zero extension or truncation of the value we're 184 /// tracking. 185 KnownBits zextOrTrunc(unsigned BitWidth) const { 186 if (BitWidth > getBitWidth()) 187 return zext(BitWidth); 188 if (BitWidth < getBitWidth()) 189 return trunc(BitWidth); 190 return *this; 191 } 192 193 /// Return known bits for a sign extension or truncation of the value we're 194 /// tracking. 195 KnownBits sextOrTrunc(unsigned BitWidth) const { 196 if (BitWidth > getBitWidth()) 197 return sext(BitWidth); 198 if (BitWidth < getBitWidth()) 199 return trunc(BitWidth); 200 return *this; 201 } 202 203 /// Return known bits for a in-register sign extension of the value we're 204 /// tracking. 205 KnownBits sextInReg(unsigned SrcBitWidth) const; 206 207 /// Insert the bits from a smaller known bits starting at bitPosition. 208 void insertBits(const KnownBits &SubBits, unsigned BitPosition) { 209 Zero.insertBits(SubBits.Zero, BitPosition); 210 One.insertBits(SubBits.One, BitPosition); 211 } 212 213 /// Return a subset of the known bits from [bitPosition,bitPosition+numBits). 214 KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const { 215 return KnownBits(Zero.extractBits(NumBits, BitPosition), 216 One.extractBits(NumBits, BitPosition)); 217 } 218 219 /// Return KnownBits based on this, but updated given that the underlying 220 /// value is known to be greater than or equal to Val. 221 KnownBits makeGE(const APInt &Val) const; 222 223 /// Returns the minimum number of trailing zero bits. 224 unsigned countMinTrailingZeros() const { 225 return Zero.countTrailingOnes(); 226 } 227 228 /// Returns the minimum number of trailing one bits. 229 unsigned countMinTrailingOnes() const { 230 return One.countTrailingOnes(); 231 } 232 233 /// Returns the minimum number of leading zero bits. 234 unsigned countMinLeadingZeros() const { 235 return Zero.countLeadingOnes(); 236 } 237 238 /// Returns the minimum number of leading one bits. 239 unsigned countMinLeadingOnes() const { 240 return One.countLeadingOnes(); 241 } 242 243 /// Returns the number of times the sign bit is replicated into the other 244 /// bits. 245 unsigned countMinSignBits() const { 246 if (isNonNegative()) 247 return countMinLeadingZeros(); 248 if (isNegative()) 249 return countMinLeadingOnes(); 250 return 0; 251 } 252 253 /// Returns the maximum number of trailing zero bits possible. 254 unsigned countMaxTrailingZeros() const { 255 return One.countTrailingZeros(); 256 } 257 258 /// Returns the maximum number of trailing one bits possible. 259 unsigned countMaxTrailingOnes() const { 260 return Zero.countTrailingZeros(); 261 } 262 263 /// Returns the maximum number of leading zero bits possible. 264 unsigned countMaxLeadingZeros() const { 265 return One.countLeadingZeros(); 266 } 267 268 /// Returns the maximum number of leading one bits possible. 269 unsigned countMaxLeadingOnes() const { 270 return Zero.countLeadingZeros(); 271 } 272 273 /// Returns the number of bits known to be one. 274 unsigned countMinPopulation() const { 275 return One.countPopulation(); 276 } 277 278 /// Returns the maximum number of bits that could be one. 279 unsigned countMaxPopulation() const { 280 return getBitWidth() - Zero.countPopulation(); 281 } 282 283 /// Create known bits from a known constant. 284 static KnownBits makeConstant(const APInt &C) { 285 return KnownBits(~C, C); 286 } 287 288 /// Compute known bits common to LHS and RHS. 289 static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) { 290 return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One); 291 } 292 293 /// Return true if LHS and RHS have no common bits set. 294 static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) { 295 return (LHS.Zero | RHS.Zero).isAllOnesValue(); 296 } 297 298 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry. 299 static KnownBits computeForAddCarry( 300 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry); 301 302 /// Compute known bits resulting from adding LHS and RHS. 303 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, 304 KnownBits RHS); 305 306 /// Compute known bits resulting from multiplying LHS and RHS. 307 static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS); 308 309 /// Compute known bits from sign-extended multiply-hi. 310 static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS); 311 312 /// Compute known bits from zero-extended multiply-hi. 313 static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS); 314 315 /// Compute known bits for udiv(LHS, RHS). 316 static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS); 317 318 /// Compute known bits for urem(LHS, RHS). 319 static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS); 320 321 /// Compute known bits for srem(LHS, RHS). 322 static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS); 323 324 /// Compute known bits for umax(LHS, RHS). 325 static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS); 326 327 /// Compute known bits for umin(LHS, RHS). 328 static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS); 329 330 /// Compute known bits for smax(LHS, RHS). 331 static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS); 332 333 /// Compute known bits for smin(LHS, RHS). 334 static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS); 335 336 /// Compute known bits for shl(LHS, RHS). 337 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. 338 static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS); 339 340 /// Compute known bits for lshr(LHS, RHS). 341 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. 342 static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS); 343 344 /// Compute known bits for ashr(LHS, RHS). 345 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. 346 static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS); 347 348 /// Determine if these known bits always give the same ICMP_EQ result. 349 static Optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS); 350 351 /// Determine if these known bits always give the same ICMP_NE result. 352 static Optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS); 353 354 /// Determine if these known bits always give the same ICMP_UGT result. 355 static Optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS); 356 357 /// Determine if these known bits always give the same ICMP_UGE result. 358 static Optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS); 359 360 /// Determine if these known bits always give the same ICMP_ULT result. 361 static Optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS); 362 363 /// Determine if these known bits always give the same ICMP_ULE result. 364 static Optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS); 365 366 /// Determine if these known bits always give the same ICMP_SGT result. 367 static Optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS); 368 369 /// Determine if these known bits always give the same ICMP_SGE result. 370 static Optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS); 371 372 /// Determine if these known bits always give the same ICMP_SLT result. 373 static Optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS); 374 375 /// Determine if these known bits always give the same ICMP_SLE result. 376 static Optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS); 377 378 /// Update known bits based on ANDing with RHS. 379 KnownBits &operator&=(const KnownBits &RHS); 380 381 /// Update known bits based on ORing with RHS. 382 KnownBits &operator|=(const KnownBits &RHS); 383 384 /// Update known bits based on XORing with RHS. 385 KnownBits &operator^=(const KnownBits &RHS); 386 387 /// Compute known bits for the absolute value. 388 KnownBits abs(bool IntMinIsPoison = false) const; 389 390 KnownBits byteSwap() { 391 return KnownBits(Zero.byteSwap(), One.byteSwap()); 392 } 393 394 KnownBits reverseBits() { 395 return KnownBits(Zero.reverseBits(), One.reverseBits()); 396 } 397 398 void print(raw_ostream &OS) const; 399 void dump() const; 400 }; 401 402 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) { 403 LHS &= RHS; 404 return LHS; 405 } 406 407 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) { 408 RHS &= LHS; 409 return std::move(RHS); 410 } 411 412 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) { 413 LHS |= RHS; 414 return LHS; 415 } 416 417 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) { 418 RHS |= LHS; 419 return std::move(RHS); 420 } 421 422 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) { 423 LHS ^= RHS; 424 return LHS; 425 } 426 427 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) { 428 RHS ^= LHS; 429 return std::move(RHS); 430 } 431 432 } // end namespace llvm 433 434 #endif 435