1 //===- llvm/Support/KnownBits.h - Stores known zeros/ones -------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file contains a class for representing known zeros and ones used by 11 // computeKnownBits. 12 // 13 //===----------------------------------------------------------------------===// 14 15 #ifndef LLVM_SUPPORT_KNOWNBITS_H 16 #define LLVM_SUPPORT_KNOWNBITS_H 17 18 #include "llvm/ADT/APInt.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 /// Make this value negative. 102 void makeNegative() { 103 One.setSignBit(); 104 } 105 106 /// Make this value non-negative. 107 void makeNonNegative() { 108 Zero.setSignBit(); 109 } 110 111 /// Truncate the underlying known Zero and One bits. This is equivalent 112 /// to truncating the value we're tracking. 113 KnownBits trunc(unsigned BitWidth) { 114 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth)); 115 } 116 117 /// Zero extends the underlying known Zero and One bits. This is equivalent 118 /// to zero extending the value we're tracking. 119 KnownBits zext(unsigned BitWidth) { 120 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth)); 121 } 122 123 /// Sign extends the underlying known Zero and One bits. This is equivalent 124 /// to sign extending the value we're tracking. 125 KnownBits sext(unsigned BitWidth) { 126 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth)); 127 } 128 129 /// Zero extends or truncates the underlying known Zero and One bits. This is 130 /// equivalent to zero extending or truncating the value we're tracking. 131 KnownBits zextOrTrunc(unsigned BitWidth) { 132 return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth)); 133 } 134 135 /// Returns the minimum number of trailing zero bits. 136 unsigned countMinTrailingZeros() const { 137 return Zero.countTrailingOnes(); 138 } 139 140 /// Returns the minimum number of trailing one bits. 141 unsigned countMinTrailingOnes() const { 142 return One.countTrailingOnes(); 143 } 144 145 /// Returns the minimum number of leading zero bits. 146 unsigned countMinLeadingZeros() const { 147 return Zero.countLeadingOnes(); 148 } 149 150 /// Returns the minimum number of leading one bits. 151 unsigned countMinLeadingOnes() const { 152 return One.countLeadingOnes(); 153 } 154 155 /// Returns the number of times the sign bit is replicated into the other 156 /// bits. 157 unsigned countMinSignBits() const { 158 if (isNonNegative()) 159 return countMinLeadingZeros(); 160 if (isNegative()) 161 return countMinLeadingOnes(); 162 return 0; 163 } 164 165 /// Returns the maximum number of trailing zero bits possible. 166 unsigned countMaxTrailingZeros() const { 167 return One.countTrailingZeros(); 168 } 169 170 /// Returns the maximum number of trailing one bits possible. 171 unsigned countMaxTrailingOnes() const { 172 return Zero.countTrailingZeros(); 173 } 174 175 /// Returns the maximum number of leading zero bits possible. 176 unsigned countMaxLeadingZeros() const { 177 return One.countLeadingZeros(); 178 } 179 180 /// Returns the maximum number of leading one bits possible. 181 unsigned countMaxLeadingOnes() const { 182 return Zero.countLeadingZeros(); 183 } 184 185 /// Returns the number of bits known to be one. 186 unsigned countMinPopulation() const { 187 return One.countPopulation(); 188 } 189 190 /// Returns the maximum number of bits that could be one. 191 unsigned countMaxPopulation() const { 192 return getBitWidth() - Zero.countPopulation(); 193 } 194 195 /// Compute known bits resulting from adding LHS and RHS. 196 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, 197 KnownBits RHS); 198 }; 199 200 } // end namespace llvm 201 202 #endif 203