1 //===- llvm/Support/KnownBits.h - Stores known zeros/ones -------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file contains a class for representing known zeros and ones used by
12 //===----------------------------------------------------------------------===//
14 #ifndef LLVM_SUPPORT_KNOWNBITS_H
15 #define LLVM_SUPPORT_KNOWNBITS_H
17 #include "llvm/ADT/APInt.h"
21 // Struct for tracking the known zeros and ones of a value.
27 // Internal constructor for creating a KnownBits from two APInts.
28 KnownBits(APInt Zero, APInt One)
29 : Zero(std::move(Zero)), One(std::move(One)) {}
32 // Default construct Zero and One.
35 /// Create a known bits object of BitWidth bits initialized to unknown.
36 KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
38 /// Get the bit width of this value.
39 unsigned getBitWidth() const {
40 assert(Zero.getBitWidth() == One.getBitWidth() &&
41 "Zero and One should have the same width!");
42 return Zero.getBitWidth();
45 /// Returns true if there is conflicting information.
46 bool hasConflict() const { return Zero.intersects(One); }
48 /// Returns true if we know the value of all bits.
49 bool isConstant() const {
50 assert(!hasConflict() && "KnownBits conflict!");
51 return Zero.countPopulation() + One.countPopulation() == getBitWidth();
54 /// Returns the value when all bits have a known value. This just returns One
55 /// with a protective assertion.
56 const APInt &getConstant() const {
57 assert(isConstant() && "Can only get value when all bits are known");
61 /// Returns true if we don't know any bits.
62 bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); }
64 /// Resets the known state of all bits.
70 /// Returns true if value is all zero.
72 assert(!hasConflict() && "KnownBits conflict!");
73 return Zero.isAllOnesValue();
76 /// Returns true if value is all one bits.
77 bool isAllOnes() const {
78 assert(!hasConflict() && "KnownBits conflict!");
79 return One.isAllOnesValue();
82 /// Make all bits known to be zero and discard any previous information.
88 /// Make all bits known to be one and discard any previous information.
94 /// Returns true if this value is known to be negative.
95 bool isNegative() const { return One.isSignBitSet(); }
97 /// Returns true if this value is known to be non-negative.
98 bool isNonNegative() const { return Zero.isSignBitSet(); }
100 /// Returns true if this value is known to be positive.
101 bool isStrictlyPositive() const { return Zero.isSignBitSet() && !One.isNullValue(); }
103 /// Make this value negative.
104 void makeNegative() {
108 /// Make this value non-negative.
109 void makeNonNegative() {
113 /// Return the minimal value possible given these KnownBits.
114 APInt getMinValue() const {
115 // Assume that all bits that aren't known-ones are zeros.
119 /// Return the maximal value possible given these KnownBits.
120 APInt getMaxValue() const {
121 // Assume that all bits that aren't known-zeros are ones.
125 /// Return known bits for a truncation of the value we're tracking.
126 KnownBits trunc(unsigned BitWidth) const {
127 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
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.
132 KnownBits anyext(unsigned BitWidth) const {
133 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
136 /// Return known bits for a zero extension of the value we're tracking.
137 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));
144 /// Return known bits for a sign extension of the value we're tracking.
145 KnownBits sext(unsigned BitWidth) const {
146 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
149 /// Return known bits for an "any" extension or truncation of the value we're
151 KnownBits anyextOrTrunc(unsigned BitWidth) const {
152 if (BitWidth > getBitWidth())
153 return anyext(BitWidth);
154 if (BitWidth < getBitWidth())
155 return trunc(BitWidth);
159 /// Return known bits for a zero extension or truncation of the value we're
161 KnownBits zextOrTrunc(unsigned BitWidth) const {
162 if (BitWidth > getBitWidth())
163 return zext(BitWidth);
164 if (BitWidth < getBitWidth())
165 return trunc(BitWidth);
169 /// Return a KnownBits with the extracted bits
170 /// [bitPosition,bitPosition+numBits).
171 KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
172 return KnownBits(Zero.extractBits(NumBits, BitPosition),
173 One.extractBits(NumBits, BitPosition));
176 /// Returns the minimum number of trailing zero bits.
177 unsigned countMinTrailingZeros() const {
178 return Zero.countTrailingOnes();
181 /// Returns the minimum number of trailing one bits.
182 unsigned countMinTrailingOnes() const {
183 return One.countTrailingOnes();
186 /// Returns the minimum number of leading zero bits.
187 unsigned countMinLeadingZeros() const {
188 return Zero.countLeadingOnes();
191 /// Returns the minimum number of leading one bits.
192 unsigned countMinLeadingOnes() const {
193 return One.countLeadingOnes();
196 /// Returns the number of times the sign bit is replicated into the other
198 unsigned countMinSignBits() const {
200 return countMinLeadingZeros();
202 return countMinLeadingOnes();
206 /// Returns the maximum number of trailing zero bits possible.
207 unsigned countMaxTrailingZeros() const {
208 return One.countTrailingZeros();
211 /// Returns the maximum number of trailing one bits possible.
212 unsigned countMaxTrailingOnes() const {
213 return Zero.countTrailingZeros();
216 /// Returns the maximum number of leading zero bits possible.
217 unsigned countMaxLeadingZeros() const {
218 return One.countLeadingZeros();
221 /// Returns the maximum number of leading one bits possible.
222 unsigned countMaxLeadingOnes() const {
223 return Zero.countLeadingZeros();
226 /// Returns the number of bits known to be one.
227 unsigned countMinPopulation() const {
228 return One.countPopulation();
231 /// Returns the maximum number of bits that could be one.
232 unsigned countMaxPopulation() const {
233 return getBitWidth() - Zero.countPopulation();
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);
240 /// Compute known bits resulting from adding LHS and RHS.
241 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
244 /// Update known bits based on ANDing with RHS.
245 KnownBits &operator&=(const KnownBits &RHS);
247 /// Update known bits based on ORing with RHS.
248 KnownBits &operator|=(const KnownBits &RHS);
250 /// Update known bits based on XORing with RHS.
251 KnownBits &operator^=(const KnownBits &RHS);
254 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
259 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
261 return std::move(RHS);
264 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
269 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
271 return std::move(RHS);
274 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
279 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
281 return std::move(RHS);
284 } // end namespace llvm