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 20namespace llvm { 21 22// Struct for tracking the known zeros and ones of a value. 23struct KnownBits { 24 APInt Zero; 25 APInt One; 26 27private: 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 32public: 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 assert(!isNonNegative() && "Can't make a non-negative value negative"); 104 One.setSignBit(); 105 } 106 107 /// Make this value negative. 108 void makeNonNegative() { 109 assert(!isNegative() && "Can't make a negative value non-negative"); 110 Zero.setSignBit(); 111 } 112 113 /// Truncate the underlying known Zero and One bits. This is equivalent 114 /// to truncating the value we're tracking. 115 KnownBits trunc(unsigned BitWidth) { 116 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth)); 117 } 118 119 /// Zero extends the underlying known Zero and One bits. This is equivalent 120 /// to zero extending the value we're tracking. 121 KnownBits zext(unsigned BitWidth) { 122 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth)); 123 } 124 125 /// Sign extends the underlying known Zero and One bits. This is equivalent 126 /// to sign extending the value we're tracking. 127 KnownBits sext(unsigned BitWidth) { 128 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth)); 129 } 130 131 /// Zero extends or truncates the underlying known Zero and One bits. This is 132 /// equivalent to zero extending or truncating the value we're tracking. 133 KnownBits zextOrTrunc(unsigned BitWidth) { 134 return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth)); 135 } 136 137 /// Returns the minimum number of trailing zero bits. 138 unsigned countMinTrailingZeros() const { 139 return Zero.countTrailingOnes(); 140 } 141 142 /// Returns the minimum number of trailing one bits. 143 unsigned countMinTrailingOnes() const { 144 return One.countTrailingOnes(); 145 } 146 147 /// Returns the minimum number of leading zero bits. 148 unsigned countMinLeadingZeros() const { 149 return Zero.countLeadingOnes(); 150 } 151 152 /// Returns the minimum number of leading one bits. 153 unsigned countMinLeadingOnes() const { 154 return One.countLeadingOnes(); 155 } 156 157 /// Returns the number of times the sign bit is replicated into the other 158 /// bits. 159 unsigned countMinSignBits() const { 160 if (isNonNegative()) 161 return countMinLeadingZeros(); 162 if (isNegative()) 163 return countMinLeadingOnes(); 164 return 0; 165 } 166 167 /// Returns the maximum number of trailing zero bits possible. 168 unsigned countMaxTrailingZeros() const { 169 return One.countTrailingZeros(); 170 } 171 172 /// Returns the maximum number of trailing one bits possible. 173 unsigned countMaxTrailingOnes() const { 174 return Zero.countTrailingZeros(); 175 } 176 177 /// Returns the maximum number of leading zero bits possible. 178 unsigned countMaxLeadingZeros() const { 179 return One.countLeadingZeros(); 180 } 181 182 /// Returns the maximum number of leading one bits possible. 183 unsigned countMaxLeadingOnes() const { 184 return Zero.countLeadingZeros(); 185 } 186 187 /// Returns the number of bits known to be one. 188 unsigned countMinPopulation() const { 189 return One.countPopulation(); 190 } 191 192 /// Returns the maximum number of bits that could be one. 193 unsigned countMaxPopulation() const { 194 return getBitWidth() - Zero.countPopulation(); 195 } 196 197 /// Compute known bits resulting from adding LHS and RHS. 198 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS, 199 KnownBits RHS); 200}; 201 202} // end namespace llvm 203 204#endif 205