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 /// Truncate the underlying known Zero and One bits. This is equivalent
126 /// to truncating the value we're tracking.
127 KnownBits trunc(unsigned BitWidth) const {
128 return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
131 /// Extends the underlying known Zero and One bits.
132 /// By setting ExtendedBitsAreKnownZero=true this will be equivalent to
133 /// zero extending the value we're tracking.
134 /// With ExtendedBitsAreKnownZero=false the extended bits are set to unknown.
135 KnownBits zext(unsigned BitWidth, bool ExtendedBitsAreKnownZero) const {
136 unsigned OldBitWidth = getBitWidth();
137 APInt NewZero = Zero.zext(BitWidth);
138 if (ExtendedBitsAreKnownZero)
139 NewZero.setBitsFrom(OldBitWidth);
140 return KnownBits(NewZero, One.zext(BitWidth));
143 /// Sign extends the underlying known Zero and One bits. This is equivalent
144 /// to sign extending the value we're tracking.
145 KnownBits sext(unsigned BitWidth) const {
146 return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
149 /// Extends or truncates the underlying known Zero and One bits. When
150 /// extending the extended bits can either be set as known zero (if
151 /// ExtendedBitsAreKnownZero=true) or as unknown (if
152 /// ExtendedBitsAreKnownZero=false).
153 KnownBits zextOrTrunc(unsigned BitWidth,
154 bool ExtendedBitsAreKnownZero) const {
155 if (BitWidth > getBitWidth())
156 return zext(BitWidth, ExtendedBitsAreKnownZero);
157 return KnownBits(Zero.zextOrTrunc(BitWidth), One.zextOrTrunc(BitWidth));
160 /// Returns the minimum number of trailing zero bits.
161 unsigned countMinTrailingZeros() const {
162 return Zero.countTrailingOnes();
165 /// Returns the minimum number of trailing one bits.
166 unsigned countMinTrailingOnes() const {
167 return One.countTrailingOnes();
170 /// Returns the minimum number of leading zero bits.
171 unsigned countMinLeadingZeros() const {
172 return Zero.countLeadingOnes();
175 /// Returns the minimum number of leading one bits.
176 unsigned countMinLeadingOnes() const {
177 return One.countLeadingOnes();
180 /// Returns the number of times the sign bit is replicated into the other
182 unsigned countMinSignBits() const {
184 return countMinLeadingZeros();
186 return countMinLeadingOnes();
190 /// Returns the maximum number of trailing zero bits possible.
191 unsigned countMaxTrailingZeros() const {
192 return One.countTrailingZeros();
195 /// Returns the maximum number of trailing one bits possible.
196 unsigned countMaxTrailingOnes() const {
197 return Zero.countTrailingZeros();
200 /// Returns the maximum number of leading zero bits possible.
201 unsigned countMaxLeadingZeros() const {
202 return One.countLeadingZeros();
205 /// Returns the maximum number of leading one bits possible.
206 unsigned countMaxLeadingOnes() const {
207 return Zero.countLeadingZeros();
210 /// Returns the number of bits known to be one.
211 unsigned countMinPopulation() const {
212 return One.countPopulation();
215 /// Returns the maximum number of bits that could be one.
216 unsigned countMaxPopulation() const {
217 return getBitWidth() - Zero.countPopulation();
220 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
221 static KnownBits computeForAddCarry(
222 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
224 /// Compute known bits resulting from adding LHS and RHS.
225 static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
229 } // end namespace llvm