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.
34 KnownBits() = default;
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.isZero() && One.isZero(); }
65 /// Resets the known state of all bits.
71 /// Returns true if value is all zero.
73 assert(!hasConflict() && "KnownBits conflict!");
74 return Zero.isAllOnes();
77 /// Returns true if value is all one bits.
78 bool isAllOnes() const {
79 assert(!hasConflict() && "KnownBits conflict!");
80 return One.isAllOnes();
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.isZero(); }
104 /// Returns true if this value is known to be positive.
105 bool isStrictlyPositive() const {
106 return Zero.isSignBitSet() && !One.isZero();
109 /// Make this value negative.
110 void makeNegative() {
114 /// Make this value non-negative.
115 void makeNonNegative() {
119 /// Return the minimal unsigned value possible given these KnownBits.
120 APInt getMinValue() const {
121 // Assume that all bits that aren't known-ones are zeros.
125 /// Return the minimal signed value possible given these KnownBits.
126 APInt getSignedMinValue() const {
127 // Assume that all bits that aren't known-ones are zeros.
129 // Sign bit is unknown.
130 if (Zero.isSignBitClear())
135 /// Return the maximal unsigned value possible given these KnownBits.
136 APInt getMaxValue() const {
137 // Assume that all bits that aren't known-zeros are ones.
141 /// Return the maximal signed value possible given these KnownBits.
142 APInt getSignedMaxValue() const {
143 // Assume that all bits that aren't known-zeros are ones.
145 // Sign bit is unknown.
146 if (One.isSignBitClear())
151 /// Return known bits for a truncation of the value we're tracking.
152 KnownBits trunc(unsigned BitWidth) const {
153 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
156 /// Return known bits for an "any" extension of the value we're tracking,
157 /// where we don't know anything about the extended bits.
158 KnownBits anyext(unsigned BitWidth) const {
159 return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
162 /// Return known bits for a zero extension of the value we're tracking.
163 KnownBits zext(unsigned BitWidth) const {
164 unsigned OldBitWidth = getBitWidth();
165 APInt NewZero = Zero.zext(BitWidth);
166 NewZero.setBitsFrom(OldBitWidth);
167 return KnownBits(NewZero, One.zext(BitWidth));
170 /// Return known bits for a sign extension of the value we're tracking.
171 KnownBits sext(unsigned BitWidth) const {
172 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
175 /// Return known bits for an "any" extension or truncation of the value we're
177 KnownBits anyextOrTrunc(unsigned BitWidth) const {
178 if (BitWidth > getBitWidth())
179 return anyext(BitWidth);
180 if (BitWidth < getBitWidth())
181 return trunc(BitWidth);
185 /// Return known bits for a zero extension or truncation of the value we're
187 KnownBits zextOrTrunc(unsigned BitWidth) const {
188 if (BitWidth > getBitWidth())
189 return zext(BitWidth);
190 if (BitWidth < getBitWidth())
191 return trunc(BitWidth);
195 /// Return known bits for a sign extension or truncation of the value we're
197 KnownBits sextOrTrunc(unsigned BitWidth) const {
198 if (BitWidth > getBitWidth())
199 return sext(BitWidth);
200 if (BitWidth < getBitWidth())
201 return trunc(BitWidth);
205 /// Return known bits for a in-register sign extension of the value we're
207 KnownBits sextInReg(unsigned SrcBitWidth) const;
209 /// Insert the bits from a smaller known bits starting at bitPosition.
210 void insertBits(const KnownBits &SubBits, unsigned BitPosition) {
211 Zero.insertBits(SubBits.Zero, BitPosition);
212 One.insertBits(SubBits.One, BitPosition);
215 /// Return a subset of the known bits from [bitPosition,bitPosition+numBits).
216 KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
217 return KnownBits(Zero.extractBits(NumBits, BitPosition),
218 One.extractBits(NumBits, BitPosition));
221 /// Return KnownBits based on this, but updated given that the underlying
222 /// value is known to be greater than or equal to Val.
223 KnownBits makeGE(const APInt &Val) const;
225 /// Returns the minimum number of trailing zero bits.
226 unsigned countMinTrailingZeros() const {
227 return Zero.countTrailingOnes();
230 /// Returns the minimum number of trailing one bits.
231 unsigned countMinTrailingOnes() const {
232 return One.countTrailingOnes();
235 /// Returns the minimum number of leading zero bits.
236 unsigned countMinLeadingZeros() const {
237 return Zero.countLeadingOnes();
240 /// Returns the minimum number of leading one bits.
241 unsigned countMinLeadingOnes() const {
242 return One.countLeadingOnes();
245 /// Returns the number of times the sign bit is replicated into the other
247 unsigned countMinSignBits() const {
249 return countMinLeadingZeros();
251 return countMinLeadingOnes();
252 // Every value has at least 1 sign bit.
256 /// Returns the maximum number of bits needed to represent all possible
257 /// signed values with these known bits. This is the inverse of the minimum
258 /// number of known sign bits. Examples for bitwidth 5:
261 unsigned countMaxSignificantBits() const {
262 return getBitWidth() - countMinSignBits() + 1;
265 /// Returns the maximum number of trailing zero bits possible.
266 unsigned countMaxTrailingZeros() const {
267 return One.countTrailingZeros();
270 /// Returns the maximum number of trailing one bits possible.
271 unsigned countMaxTrailingOnes() const {
272 return Zero.countTrailingZeros();
275 /// Returns the maximum number of leading zero bits possible.
276 unsigned countMaxLeadingZeros() const {
277 return One.countLeadingZeros();
280 /// Returns the maximum number of leading one bits possible.
281 unsigned countMaxLeadingOnes() const {
282 return Zero.countLeadingZeros();
285 /// Returns the number of bits known to be one.
286 unsigned countMinPopulation() const {
287 return One.countPopulation();
290 /// Returns the maximum number of bits that could be one.
291 unsigned countMaxPopulation() const {
292 return getBitWidth() - Zero.countPopulation();
295 /// Returns the maximum number of bits needed to represent all possible
296 /// unsigned values with these known bits. This is the inverse of the
297 /// minimum number of leading zeros.
298 unsigned countMaxActiveBits() const {
299 return getBitWidth() - countMinLeadingZeros();
302 /// Create known bits from a known constant.
303 static KnownBits makeConstant(const APInt &C) {
304 return KnownBits(~C, C);
307 /// Compute known bits common to LHS and RHS.
308 static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) {
309 return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One);
312 /// Return true if LHS and RHS have no common bits set.
313 static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
314 return (LHS.Zero | RHS.Zero).isAllOnes();
317 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
318 static KnownBits computeForAddCarry(
319 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
321 /// Compute known bits resulting from adding LHS and RHS.
322 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
325 /// Compute known bits resulting from multiplying LHS and RHS.
326 static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS,
327 bool NoUndefSelfMultiply = false);
329 /// Compute known bits from sign-extended multiply-hi.
330 static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
332 /// Compute known bits from zero-extended multiply-hi.
333 static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
335 /// Compute known bits for udiv(LHS, RHS).
336 static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
338 /// Compute known bits for urem(LHS, RHS).
339 static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
341 /// Compute known bits for srem(LHS, RHS).
342 static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);
344 /// Compute known bits for umax(LHS, RHS).
345 static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
347 /// Compute known bits for umin(LHS, RHS).
348 static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
350 /// Compute known bits for smax(LHS, RHS).
351 static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
353 /// Compute known bits for smin(LHS, RHS).
354 static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
356 /// Compute known bits for shl(LHS, RHS).
357 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
358 static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS);
360 /// Compute known bits for lshr(LHS, RHS).
361 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
362 static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS);
364 /// Compute known bits for ashr(LHS, RHS).
365 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
366 static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS);
368 /// Determine if these known bits always give the same ICMP_EQ result.
369 static Optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS);
371 /// Determine if these known bits always give the same ICMP_NE result.
372 static Optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS);
374 /// Determine if these known bits always give the same ICMP_UGT result.
375 static Optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS);
377 /// Determine if these known bits always give the same ICMP_UGE result.
378 static Optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS);
380 /// Determine if these known bits always give the same ICMP_ULT result.
381 static Optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS);
383 /// Determine if these known bits always give the same ICMP_ULE result.
384 static Optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS);
386 /// Determine if these known bits always give the same ICMP_SGT result.
387 static Optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS);
389 /// Determine if these known bits always give the same ICMP_SGE result.
390 static Optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS);
392 /// Determine if these known bits always give the same ICMP_SLT result.
393 static Optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS);
395 /// Determine if these known bits always give the same ICMP_SLE result.
396 static Optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS);
398 /// Update known bits based on ANDing with RHS.
399 KnownBits &operator&=(const KnownBits &RHS);
401 /// Update known bits based on ORing with RHS.
402 KnownBits &operator|=(const KnownBits &RHS);
404 /// Update known bits based on XORing with RHS.
405 KnownBits &operator^=(const KnownBits &RHS);
407 /// Compute known bits for the absolute value.
408 KnownBits abs(bool IntMinIsPoison = false) const;
410 KnownBits byteSwap() {
411 return KnownBits(Zero.byteSwap(), One.byteSwap());
414 KnownBits reverseBits() {
415 return KnownBits(Zero.reverseBits(), One.reverseBits());
418 bool operator==(const KnownBits &Other) const {
419 return Zero == Other.Zero && One == Other.One;
422 bool operator!=(const KnownBits &Other) const { return !(*this == Other); }
424 void print(raw_ostream &OS) const;
428 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
433 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
435 return std::move(RHS);
438 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
443 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
445 return std::move(RHS);
448 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
453 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
455 return std::move(RHS);
458 } // end namespace llvm