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 19 namespace llvm { 20 21 // Struct for tracking the known zeros and ones of a value. 22 struct KnownBits { 23 APInt Zero; 24 APInt One; 25 26 private: 27 // Internal constructor for creating a KnownBits from two APInts. KnownBitsKnownBits28 KnownBits(APInt Zero, APInt One) 29 : Zero(std::move(Zero)), One(std::move(One)) {} 30 31 public: 32 // Default construct Zero and One. KnownBitsKnownBits33 KnownBits() {} 34 35 /// Create a known bits object of BitWidth bits initialized to unknown. KnownBitsKnownBits36 KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {} 37 38 /// Get the bit width of this value. getBitWidthKnownBits39 unsigned getBitWidth() const { 40 assert(Zero.getBitWidth() == One.getBitWidth() && 41 "Zero and One should have the same width!"); 42 return Zero.getBitWidth(); 43 } 44 45 /// Returns true if there is conflicting information. hasConflictKnownBits46 bool hasConflict() const { return Zero.intersects(One); } 47 48 /// Returns true if we know the value of all bits. isConstantKnownBits49 bool isConstant() const { 50 assert(!hasConflict() && "KnownBits conflict!"); 51 return Zero.countPopulation() + One.countPopulation() == getBitWidth(); 52 } 53 54 /// Returns the value when all bits have a known value. This just returns One 55 /// with a protective assertion. getConstantKnownBits56 const APInt &getConstant() const { 57 assert(isConstant() && "Can only get value when all bits are known"); 58 return One; 59 } 60 61 /// Returns true if we don't know any bits. isUnknownKnownBits62 bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); } 63 64 /// Resets the known state of all bits. resetAllKnownBits65 void resetAll() { 66 Zero.clearAllBits(); 67 One.clearAllBits(); 68 } 69 70 /// Returns true if value is all zero. isZeroKnownBits71 bool isZero() const { 72 assert(!hasConflict() && "KnownBits conflict!"); 73 return Zero.isAllOnesValue(); 74 } 75 76 /// Returns true if value is all one bits. isAllOnesKnownBits77 bool isAllOnes() const { 78 assert(!hasConflict() && "KnownBits conflict!"); 79 return One.isAllOnesValue(); 80 } 81 82 /// Make all bits known to be zero and discard any previous information. setAllZeroKnownBits83 void setAllZero() { 84 Zero.setAllBits(); 85 One.clearAllBits(); 86 } 87 88 /// Make all bits known to be one and discard any previous information. setAllOnesKnownBits89 void setAllOnes() { 90 Zero.clearAllBits(); 91 One.setAllBits(); 92 } 93 94 /// Returns true if this value is known to be negative. isNegativeKnownBits95 bool isNegative() const { return One.isSignBitSet(); } 96 97 /// Returns true if this value is known to be non-negative. isNonNegativeKnownBits98 bool isNonNegative() const { return Zero.isSignBitSet(); } 99 100 /// Returns true if this value is known to be positive. isStrictlyPositiveKnownBits101 bool isStrictlyPositive() const { return Zero.isSignBitSet() && !One.isNullValue(); } 102 103 /// Make this value negative. makeNegativeKnownBits104 void makeNegative() { 105 One.setSignBit(); 106 } 107 108 /// Make this value non-negative. makeNonNegativeKnownBits109 void makeNonNegative() { 110 Zero.setSignBit(); 111 } 112 113 /// Return the minimal value possible given these KnownBits. getMinValueKnownBits114 APInt getMinValue() const { 115 // Assume that all bits that aren't known-ones are zeros. 116 return One; 117 } 118 119 /// Return the maximal value possible given these KnownBits. getMaxValueKnownBits120 APInt getMaxValue() const { 121 // Assume that all bits that aren't known-zeros are ones. 122 return ~Zero; 123 } 124 125 /// Return known bits for a truncation of the value we're tracking. truncKnownBits126 KnownBits trunc(unsigned BitWidth) const { 127 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth)); 128 } 129 130 /// Return known bits for an "any" extension of the value we're tracking, 131 /// where we don't know anything about the extended bits. anyextKnownBits132 KnownBits anyext(unsigned BitWidth) const { 133 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth)); 134 } 135 136 /// Return known bits for a zero extension of the value we're tracking. zextKnownBits137 KnownBits zext(unsigned BitWidth) const { 138 unsigned OldBitWidth = getBitWidth(); 139 APInt NewZero = Zero.zext(BitWidth); 140 NewZero.setBitsFrom(OldBitWidth); 141 return KnownBits(NewZero, One.zext(BitWidth)); 142 } 143 144 /// Return known bits for a sign extension of the value we're tracking. sextKnownBits145 KnownBits sext(unsigned BitWidth) const { 146 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth)); 147 } 148 149 /// Return known bits for an "any" extension or truncation of the value we're 150 /// tracking. anyextOrTruncKnownBits151 KnownBits anyextOrTrunc(unsigned BitWidth) const { 152 if (BitWidth > getBitWidth()) 153 return anyext(BitWidth); 154 if (BitWidth < getBitWidth()) 155 return trunc(BitWidth); 156 return *this; 157 } 158 159 /// Return known bits for a zero extension or truncation of the value we're 160 /// tracking. zextOrTruncKnownBits161 KnownBits zextOrTrunc(unsigned BitWidth) const { 162 if (BitWidth > getBitWidth()) 163 return zext(BitWidth); 164 if (BitWidth < getBitWidth()) 165 return trunc(BitWidth); 166 return *this; 167 } 168 169 /// Return a KnownBits with the extracted bits 170 /// [bitPosition,bitPosition+numBits). extractBitsKnownBits171 KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const { 172 return KnownBits(Zero.extractBits(NumBits, BitPosition), 173 One.extractBits(NumBits, BitPosition)); 174 } 175 176 /// Returns the minimum number of trailing zero bits. countMinTrailingZerosKnownBits177 unsigned countMinTrailingZeros() const { 178 return Zero.countTrailingOnes(); 179 } 180 181 /// Returns the minimum number of trailing one bits. countMinTrailingOnesKnownBits182 unsigned countMinTrailingOnes() const { 183 return One.countTrailingOnes(); 184 } 185 186 /// Returns the minimum number of leading zero bits. countMinLeadingZerosKnownBits187 unsigned countMinLeadingZeros() const { 188 return Zero.countLeadingOnes(); 189 } 190 191 /// Returns the minimum number of leading one bits. countMinLeadingOnesKnownBits192 unsigned countMinLeadingOnes() const { 193 return One.countLeadingOnes(); 194 } 195 196 /// Returns the number of times the sign bit is replicated into the other 197 /// bits. countMinSignBitsKnownBits198 unsigned countMinSignBits() const { 199 if (isNonNegative()) 200 return countMinLeadingZeros(); 201 if (isNegative()) 202 return countMinLeadingOnes(); 203 return 0; 204 } 205 206 /// Returns the maximum number of trailing zero bits possible. countMaxTrailingZerosKnownBits207 unsigned countMaxTrailingZeros() const { 208 return One.countTrailingZeros(); 209 } 210 211 /// Returns the maximum number of trailing one bits possible. countMaxTrailingOnesKnownBits212 unsigned countMaxTrailingOnes() const { 213 return Zero.countTrailingZeros(); 214 } 215 216 /// Returns the maximum number of leading zero bits possible. countMaxLeadingZerosKnownBits217 unsigned countMaxLeadingZeros() const { 218 return One.countLeadingZeros(); 219 } 220 221 /// Returns the maximum number of leading one bits possible. countMaxLeadingOnesKnownBits222 unsigned countMaxLeadingOnes() const { 223 return Zero.countLeadingZeros(); 224 } 225 226 /// Returns the number of bits known to be one. countMinPopulationKnownBits227 unsigned countMinPopulation() const { 228 return One.countPopulation(); 229 } 230 231 /// Returns the maximum number of bits that could be one. countMaxPopulationKnownBits232 unsigned countMaxPopulation() const { 233 return getBitWidth() - Zero.countPopulation(); 234 } 235 236 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry. 237 static KnownBits computeForAddCarry( 238 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry); 239 240 /// Compute known bits resulting from adding LHS and RHS. 241 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, 242 KnownBits RHS); 243 244 /// Update known bits based on ANDing with RHS. 245 KnownBits &operator&=(const KnownBits &RHS); 246 247 /// Update known bits based on ORing with RHS. 248 KnownBits &operator|=(const KnownBits &RHS); 249 250 /// Update known bits based on XORing with RHS. 251 KnownBits &operator^=(const KnownBits &RHS); 252 }; 253 254 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) { 255 LHS &= RHS; 256 return LHS; 257 } 258 259 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) { 260 RHS &= LHS; 261 return std::move(RHS); 262 } 263 264 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) { 265 LHS |= RHS; 266 return LHS; 267 } 268 269 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) { 270 RHS |= LHS; 271 return std::move(RHS); 272 } 273 274 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) { 275 LHS ^= RHS; 276 return LHS; 277 } 278 279 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) { 280 RHS ^= LHS; 281 return std::move(RHS); 282 } 283 284 } // end namespace llvm 285 286 #endif 287