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 /// Truncate the underlying known Zero and One bits. This is equivalent 126 /// to truncating the value we're tracking. truncKnownBits127 KnownBits trunc(unsigned BitWidth) const { 128 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth)); 129 } 130 131 /// Extends the underlying known Zero and One bits. 132 /// By setting ExtendedBitsAreKnownZero=true this will be equivalent to 133 /// zero extending the value we're tracking. 134 /// With ExtendedBitsAreKnownZero=false the extended bits are set to unknown. zextKnownBits135 KnownBits zext(unsigned BitWidth, bool ExtendedBitsAreKnownZero) const { 136 unsigned OldBitWidth = getBitWidth(); 137 APInt NewZero = Zero.zext(BitWidth); 138 if (ExtendedBitsAreKnownZero) 139 NewZero.setBitsFrom(OldBitWidth); 140 return KnownBits(NewZero, One.zext(BitWidth)); 141 } 142 143 /// Sign extends the underlying known Zero and One bits. This is equivalent 144 /// to sign extending the value we're tracking. sextKnownBits145 KnownBits sext(unsigned BitWidth) const { 146 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth)); 147 } 148 149 /// Extends or truncates the underlying known Zero and One bits. When 150 /// extending the extended bits can either be set as known zero (if 151 /// ExtendedBitsAreKnownZero=true) or as unknown (if 152 /// ExtendedBitsAreKnownZero=false). zextOrTruncKnownBits153 KnownBits zextOrTrunc(unsigned BitWidth, 154 bool ExtendedBitsAreKnownZero) const { 155 if (BitWidth > getBitWidth()) 156 return zext(BitWidth, ExtendedBitsAreKnownZero); 157 return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth)); 158 } 159 160 /// Returns the minimum number of trailing zero bits. countMinTrailingZerosKnownBits161 unsigned countMinTrailingZeros() const { 162 return Zero.countTrailingOnes(); 163 } 164 165 /// Returns the minimum number of trailing one bits. countMinTrailingOnesKnownBits166 unsigned countMinTrailingOnes() const { 167 return One.countTrailingOnes(); 168 } 169 170 /// Returns the minimum number of leading zero bits. countMinLeadingZerosKnownBits171 unsigned countMinLeadingZeros() const { 172 return Zero.countLeadingOnes(); 173 } 174 175 /// Returns the minimum number of leading one bits. countMinLeadingOnesKnownBits176 unsigned countMinLeadingOnes() const { 177 return One.countLeadingOnes(); 178 } 179 180 /// Returns the number of times the sign bit is replicated into the other 181 /// bits. countMinSignBitsKnownBits182 unsigned countMinSignBits() const { 183 if (isNonNegative()) 184 return countMinLeadingZeros(); 185 if (isNegative()) 186 return countMinLeadingOnes(); 187 return 0; 188 } 189 190 /// Returns the maximum number of trailing zero bits possible. countMaxTrailingZerosKnownBits191 unsigned countMaxTrailingZeros() const { 192 return One.countTrailingZeros(); 193 } 194 195 /// Returns the maximum number of trailing one bits possible. countMaxTrailingOnesKnownBits196 unsigned countMaxTrailingOnes() const { 197 return Zero.countTrailingZeros(); 198 } 199 200 /// Returns the maximum number of leading zero bits possible. countMaxLeadingZerosKnownBits201 unsigned countMaxLeadingZeros() const { 202 return One.countLeadingZeros(); 203 } 204 205 /// Returns the maximum number of leading one bits possible. countMaxLeadingOnesKnownBits206 unsigned countMaxLeadingOnes() const { 207 return Zero.countLeadingZeros(); 208 } 209 210 /// Returns the number of bits known to be one. countMinPopulationKnownBits211 unsigned countMinPopulation() const { 212 return One.countPopulation(); 213 } 214 215 /// Returns the maximum number of bits that could be one. countMaxPopulationKnownBits216 unsigned countMaxPopulation() const { 217 return getBitWidth() - Zero.countPopulation(); 218 } 219 220 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry. 221 static KnownBits computeForAddCarry( 222 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry); 223 224 /// Compute known bits resulting from adding LHS and RHS. 225 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, 226 KnownBits RHS); 227 }; 228 229 } // end namespace llvm 230 231 #endif 232