1 //===- llvm/Support/KnownBits.h - Stores known zeros/ones -------*- C++ -*-===//
2 //
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
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file contains a class for representing known zeros and ones used by
10 // computeKnownBits.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef LLVM_SUPPORT_KNOWNBITS_H
15 #define LLVM_SUPPORT_KNOWNBITS_H
16 
17 #include "llvm/ADT/APInt.h"
18 
19 namespace llvm {
20 
21 // Struct for tracking the known zeros and ones of a value.
22 struct KnownBits {
23   APInt Zero;
24   APInt One;
25 
26 private:
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)) {}
30 
31 public:
32   // Default construct Zero and One.
33   KnownBits() {}
34 
35   /// Create a known bits object of BitWidth bits initialized to unknown.
36   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
37 
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();
43   }
44 
45   /// Returns true if there is conflicting information.
46   bool hasConflict() const { return Zero.intersects(One); }
47 
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();
52   }
53 
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");
58     return One;
59   }
60 
61   /// Returns true if we don't know any bits.
62   bool isUnknown() const { return Zero.isNullValue() && One.isNullValue(); }
63 
64   /// Resets the known state of all bits.
65   void resetAll() {
66     Zero.clearAllBits();
67     One.clearAllBits();
68   }
69 
70   /// Returns true if value is all zero.
71   bool isZero() const {
72     assert(!hasConflict() && "KnownBits conflict!");
73     return Zero.isAllOnesValue();
74   }
75 
76   /// Returns true if value is all one bits.
77   bool isAllOnes() const {
78     assert(!hasConflict() && "KnownBits conflict!");
79     return One.isAllOnesValue();
80   }
81 
82   /// Make all bits known to be zero and discard any previous information.
83   void setAllZero() {
84     Zero.setAllBits();
85     One.clearAllBits();
86   }
87 
88   /// Make all bits known to be one and discard any previous information.
89   void setAllOnes() {
90     Zero.clearAllBits();
91     One.setAllBits();
92   }
93 
94   /// Returns true if this value is known to be negative.
95   bool isNegative() const { return One.isSignBitSet(); }
96 
97   /// Returns true if this value is known to be non-negative.
98   bool isNonNegative() const { return Zero.isSignBitSet(); }
99 
100   /// Returns true if this value is known to be positive.
101   bool isStrictlyPositive() const { return Zero.isSignBitSet() && !One.isNullValue(); }
102 
103   /// Make this value negative.
104   void makeNegative() {
105     One.setSignBit();
106   }
107 
108   /// Make this value non-negative.
109   void makeNonNegative() {
110     Zero.setSignBit();
111   }
112 
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.
116     return One;
117   }
118 
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.
122     return ~Zero;
123   }
124 
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));
129   }
130 
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));
141   }
142 
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));
147   }
148 
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));
158   }
159 
160   /// Returns the minimum number of trailing zero bits.
161   unsigned countMinTrailingZeros() const {
162     return Zero.countTrailingOnes();
163   }
164 
165   /// Returns the minimum number of trailing one bits.
166   unsigned countMinTrailingOnes() const {
167     return One.countTrailingOnes();
168   }
169 
170   /// Returns the minimum number of leading zero bits.
171   unsigned countMinLeadingZeros() const {
172     return Zero.countLeadingOnes();
173   }
174 
175   /// Returns the minimum number of leading one bits.
176   unsigned countMinLeadingOnes() const {
177     return One.countLeadingOnes();
178   }
179 
180   /// Returns the number of times the sign bit is replicated into the other
181   /// bits.
182   unsigned countMinSignBits() const {
183     if (isNonNegative())
184       return countMinLeadingZeros();
185     if (isNegative())
186       return countMinLeadingOnes();
187     return 0;
188   }
189 
190   /// Returns the maximum number of trailing zero bits possible.
191   unsigned countMaxTrailingZeros() const {
192     return One.countTrailingZeros();
193   }
194 
195   /// Returns the maximum number of trailing one bits possible.
196   unsigned countMaxTrailingOnes() const {
197     return Zero.countTrailingZeros();
198   }
199 
200   /// Returns the maximum number of leading zero bits possible.
201   unsigned countMaxLeadingZeros() const {
202     return One.countLeadingZeros();
203   }
204 
205   /// Returns the maximum number of leading one bits possible.
206   unsigned countMaxLeadingOnes() const {
207     return Zero.countLeadingZeros();
208   }
209 
210   /// Returns the number of bits known to be one.
211   unsigned countMinPopulation() const {
212     return One.countPopulation();
213   }
214 
215   /// Returns the maximum number of bits that could be one.
216   unsigned countMaxPopulation() const {
217     return getBitWidth() - Zero.countPopulation();
218   }
219 
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);
223 
224   /// Compute known bits resulting from adding LHS and RHS.
225   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
226                                     KnownBits RHS);
227 };
228 
229 } // end namespace llvm
230 
231 #endif
232