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"
18 #include "llvm/ADT/Optional.h"
22 // Struct for tracking the known zeros and ones of a value.
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)) {}
33 // Default construct Zero and One.
36 /// Create a known bits object of BitWidth bits initialized to unknown.
37 KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
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();
46 /// Returns true if there is conflicting information.
47 bool hasConflict() const { return Zero.intersects(One); }
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();
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");
62 /// Returns true if we don't know any bits.
63 bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); }
65 /// Resets the known state of all bits.
71 /// Returns true if value is all zero.
73 assert(!hasConflict() && "KnownBits conflict!");
74 return Zero.isAllOnesValue();
77 /// Returns true if value is all one bits.
78 bool isAllOnes() const {
79 assert(!hasConflict() && "KnownBits conflict!");
80 return One.isAllOnesValue();
83 /// Make all bits known to be zero and discard any previous information.
89 /// Make all bits known to be one and discard any previous information.
95 /// Returns true if this value is known to be negative.
96 bool isNegative() const { return One.isSignBitSet(); }
98 /// Returns true if this value is known to be non-negative.
99 bool isNonNegative() const { return Zero.isSignBitSet(); }
101 /// Returns true if this value is known to be non-zero.
102 bool isNonZero() const { return !One.isNullValue(); }
104 /// Returns true if this value is known to be positive.
105 bool isStrictlyPositive() const { return Zero.isSignBitSet() && !One.isNullValue(); }
107 /// Make this value negative.
108 void makeNegative() {
112 /// Make this value non-negative.
113 void makeNonNegative() {
117 /// Return the minimal unsigned value possible given these KnownBits.
118 APInt getMinValue() const {
119 // Assume that all bits that aren't known-ones are zeros.
123 /// Return the minimal signed value possible given these KnownBits.
124 APInt getSignedMinValue() const {
125 // Assume that all bits that aren't known-ones are zeros.
127 // Sign bit is unknown.
128 if (Zero.isSignBitClear())
133 /// Return the maximal unsigned value possible given these KnownBits.
134 APInt getMaxValue() const {
135 // Assume that all bits that aren't known-zeros are ones.
139 /// Return the maximal signed value possible given these KnownBits.
140 APInt getSignedMaxValue() const {
141 // Assume that all bits that aren't known-zeros are ones.
143 // Sign bit is unknown.
144 if (One.isSignBitClear())
149 /// Return known bits for a truncation of the value we're tracking.
150 KnownBits trunc(unsigned BitWidth) const {
151 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
154 /// Return known bits for an "any" extension of the value we're tracking,
155 /// where we don't know anything about the extended bits.
156 KnownBits anyext(unsigned BitWidth) const {
157 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
160 /// Return known bits for a zero extension of the value we're tracking.
161 KnownBits zext(unsigned BitWidth) const {
162 unsigned OldBitWidth = getBitWidth();
163 APInt NewZero = Zero.zext(BitWidth);
164 NewZero.setBitsFrom(OldBitWidth);
165 return KnownBits(NewZero, One.zext(BitWidth));
168 /// Return known bits for a sign extension of the value we're tracking.
169 KnownBits sext(unsigned BitWidth) const {
170 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
173 /// Return known bits for an "any" extension or truncation of the value we're
175 KnownBits anyextOrTrunc(unsigned BitWidth) const {
176 if (BitWidth > getBitWidth())
177 return anyext(BitWidth);
178 if (BitWidth < getBitWidth())
179 return trunc(BitWidth);
183 /// Return known bits for a zero extension or truncation of the value we're
185 KnownBits zextOrTrunc(unsigned BitWidth) const {
186 if (BitWidth > getBitWidth())
187 return zext(BitWidth);
188 if (BitWidth < getBitWidth())
189 return trunc(BitWidth);
193 /// Return known bits for a sign extension or truncation of the value we're
195 KnownBits sextOrTrunc(unsigned BitWidth) const {
196 if (BitWidth > getBitWidth())
197 return sext(BitWidth);
198 if (BitWidth < getBitWidth())
199 return trunc(BitWidth);
203 /// Return known bits for a in-register sign extension of the value we're
205 KnownBits sextInReg(unsigned SrcBitWidth) const;
207 /// Insert the bits from a smaller known bits starting at bitPosition.
208 void insertBits(const KnownBits &SubBits, unsigned BitPosition) {
209 Zero.insertBits(SubBits.Zero, BitPosition);
210 One.insertBits(SubBits.One, BitPosition);
213 /// Return a subset of the known bits from [bitPosition,bitPosition+numBits).
214 KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
215 return KnownBits(Zero.extractBits(NumBits, BitPosition),
216 One.extractBits(NumBits, BitPosition));
219 /// Return KnownBits based on this, but updated given that the underlying
220 /// value is known to be greater than or equal to Val.
221 KnownBits makeGE(const APInt &Val) const;
223 /// Returns the minimum number of trailing zero bits.
224 unsigned countMinTrailingZeros() const {
225 return Zero.countTrailingOnes();
228 /// Returns the minimum number of trailing one bits.
229 unsigned countMinTrailingOnes() const {
230 return One.countTrailingOnes();
233 /// Returns the minimum number of leading zero bits.
234 unsigned countMinLeadingZeros() const {
235 return Zero.countLeadingOnes();
238 /// Returns the minimum number of leading one bits.
239 unsigned countMinLeadingOnes() const {
240 return One.countLeadingOnes();
243 /// Returns the number of times the sign bit is replicated into the other
245 unsigned countMinSignBits() const {
247 return countMinLeadingZeros();
249 return countMinLeadingOnes();
253 /// Returns the maximum number of trailing zero bits possible.
254 unsigned countMaxTrailingZeros() const {
255 return One.countTrailingZeros();
258 /// Returns the maximum number of trailing one bits possible.
259 unsigned countMaxTrailingOnes() const {
260 return Zero.countTrailingZeros();
263 /// Returns the maximum number of leading zero bits possible.
264 unsigned countMaxLeadingZeros() const {
265 return One.countLeadingZeros();
268 /// Returns the maximum number of leading one bits possible.
269 unsigned countMaxLeadingOnes() const {
270 return Zero.countLeadingZeros();
273 /// Returns the number of bits known to be one.
274 unsigned countMinPopulation() const {
275 return One.countPopulation();
278 /// Returns the maximum number of bits that could be one.
279 unsigned countMaxPopulation() const {
280 return getBitWidth() - Zero.countPopulation();
283 /// Create known bits from a known constant.
284 static KnownBits makeConstant(const APInt &C) {
285 return KnownBits(~C, C);
288 /// Compute known bits common to LHS and RHS.
289 static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) {
290 return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One);
293 /// Return true if LHS and RHS have no common bits set.
294 static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
295 return (LHS.Zero | RHS.Zero).isAllOnesValue();
298 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
299 static KnownBits computeForAddCarry(
300 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
302 /// Compute known bits resulting from adding LHS and RHS.
303 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
306 /// Compute known bits resulting from multiplying LHS and RHS.
307 static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS);
309 /// Compute known bits from sign-extended multiply-hi.
310 static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
312 /// Compute known bits from zero-extended multiply-hi.
313 static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
315 /// Compute known bits for udiv(LHS, RHS).
316 static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
318 /// Compute known bits for urem(LHS, RHS).
319 static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
321 /// Compute known bits for srem(LHS, RHS).
322 static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);
324 /// Compute known bits for umax(LHS, RHS).
325 static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
327 /// Compute known bits for umin(LHS, RHS).
328 static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
330 /// Compute known bits for smax(LHS, RHS).
331 static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
333 /// Compute known bits for smin(LHS, RHS).
334 static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
336 /// Compute known bits for shl(LHS, RHS).
337 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
338 static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS);
340 /// Compute known bits for lshr(LHS, RHS).
341 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
342 static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS);
344 /// Compute known bits for ashr(LHS, RHS).
345 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
346 static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS);
348 /// Determine if these known bits always give the same ICMP_EQ result.
349 static Optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS);
351 /// Determine if these known bits always give the same ICMP_NE result.
352 static Optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS);
354 /// Determine if these known bits always give the same ICMP_UGT result.
355 static Optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS);
357 /// Determine if these known bits always give the same ICMP_UGE result.
358 static Optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS);
360 /// Determine if these known bits always give the same ICMP_ULT result.
361 static Optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS);
363 /// Determine if these known bits always give the same ICMP_ULE result.
364 static Optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS);
366 /// Determine if these known bits always give the same ICMP_SGT result.
367 static Optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS);
369 /// Determine if these known bits always give the same ICMP_SGE result.
370 static Optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS);
372 /// Determine if these known bits always give the same ICMP_SLT result.
373 static Optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS);
375 /// Determine if these known bits always give the same ICMP_SLE result.
376 static Optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS);
378 /// Update known bits based on ANDing with RHS.
379 KnownBits &operator&=(const KnownBits &RHS);
381 /// Update known bits based on ORing with RHS.
382 KnownBits &operator|=(const KnownBits &RHS);
384 /// Update known bits based on XORing with RHS.
385 KnownBits &operator^=(const KnownBits &RHS);
387 /// Compute known bits for the absolute value.
388 KnownBits abs(bool IntMinIsPoison = false) const;
390 KnownBits byteSwap() {
391 return KnownBits(Zero.byteSwap(), One.byteSwap());
394 KnownBits reverseBits() {
395 return KnownBits(Zero.reverseBits(), One.reverseBits());
398 void print(raw_ostream &OS) const;
402 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
407 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
409 return std::move(RHS);
412 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
417 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
419 return std::move(RHS);
422 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
427 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
429 return std::move(RHS);
432 } // end namespace llvm