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 #include <optional>
19 
20 namespace llvm {
21 
22 // Struct for tracking the known zeros and ones of a value.
23 struct KnownBits {
24   APInt Zero;
25   APInt One;
26 
27 private:
28   // Internal constructor for creating a KnownBits from two APInts.
KnownBitsKnownBits29   KnownBits(APInt Zero, APInt One)
30       : Zero(std::move(Zero)), One(std::move(One)) {}
31 
32 public:
33   // Default construct Zero and One.
34   KnownBits() = default;
35 
36   /// Create a known bits object of BitWidth bits initialized to unknown.
KnownBitsKnownBits37   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
38 
39   /// Get the bit width of this value.
getBitWidthKnownBits40   unsigned getBitWidth() const {
41     assert(Zero.getBitWidth() == One.getBitWidth() &&
42            "Zero and One should have the same width!");
43     return Zero.getBitWidth();
44   }
45 
46   /// Returns true if there is conflicting information.
hasConflictKnownBits47   bool hasConflict() const { return Zero.intersects(One); }
48 
49   /// Returns true if we know the value of all bits.
isConstantKnownBits50   bool isConstant() const {
51     assert(!hasConflict() && "KnownBits conflict!");
52     return Zero.countPopulation() + One.countPopulation() == getBitWidth();
53   }
54 
55   /// Returns the value when all bits have a known value. This just returns One
56   /// with a protective assertion.
getConstantKnownBits57   const APInt &getConstant() const {
58     assert(isConstant() && "Can only get value when all bits are known");
59     return One;
60   }
61 
62   /// Returns true if we don't know any bits.
isUnknownKnownBits63   bool isUnknown() const { return Zero.isZero() && One.isZero(); }
64 
65   /// Resets the known state of all bits.
resetAllKnownBits66   void resetAll() {
67     Zero.clearAllBits();
68     One.clearAllBits();
69   }
70 
71   /// Returns true if value is all zero.
isZeroKnownBits72   bool isZero() const {
73     assert(!hasConflict() && "KnownBits conflict!");
74     return Zero.isAllOnes();
75   }
76 
77   /// Returns true if value is all one bits.
isAllOnesKnownBits78   bool isAllOnes() const {
79     assert(!hasConflict() && "KnownBits conflict!");
80     return One.isAllOnes();
81   }
82 
83   /// Make all bits known to be zero and discard any previous information.
setAllZeroKnownBits84   void setAllZero() {
85     Zero.setAllBits();
86     One.clearAllBits();
87   }
88 
89   /// Make all bits known to be one and discard any previous information.
setAllOnesKnownBits90   void setAllOnes() {
91     Zero.clearAllBits();
92     One.setAllBits();
93   }
94 
95   /// Returns true if this value is known to be negative.
isNegativeKnownBits96   bool isNegative() const { return One.isSignBitSet(); }
97 
98   /// Returns true if this value is known to be non-negative.
isNonNegativeKnownBits99   bool isNonNegative() const { return Zero.isSignBitSet(); }
100 
101   /// Returns true if this value is known to be non-zero.
isNonZeroKnownBits102   bool isNonZero() const { return !One.isZero(); }
103 
104   /// Returns true if this value is known to be positive.
isStrictlyPositiveKnownBits105   bool isStrictlyPositive() const {
106     return Zero.isSignBitSet() && !One.isZero();
107   }
108 
109   /// Make this value negative.
makeNegativeKnownBits110   void makeNegative() {
111     One.setSignBit();
112   }
113 
114   /// Make this value non-negative.
makeNonNegativeKnownBits115   void makeNonNegative() {
116     Zero.setSignBit();
117   }
118 
119   /// Return the minimal unsigned value possible given these KnownBits.
getMinValueKnownBits120   APInt getMinValue() const {
121     // Assume that all bits that aren't known-ones are zeros.
122     return One;
123   }
124 
125   /// Return the minimal signed value possible given these KnownBits.
getSignedMinValueKnownBits126   APInt getSignedMinValue() const {
127     // Assume that all bits that aren't known-ones are zeros.
128     APInt Min = One;
129     // Sign bit is unknown.
130     if (Zero.isSignBitClear())
131       Min.setSignBit();
132     return Min;
133   }
134 
135   /// Return the maximal unsigned value possible given these KnownBits.
getMaxValueKnownBits136   APInt getMaxValue() const {
137     // Assume that all bits that aren't known-zeros are ones.
138     return ~Zero;
139   }
140 
141   /// Return the maximal signed value possible given these KnownBits.
getSignedMaxValueKnownBits142   APInt getSignedMaxValue() const {
143     // Assume that all bits that aren't known-zeros are ones.
144     APInt Max = ~Zero;
145     // Sign bit is unknown.
146     if (One.isSignBitClear())
147       Max.clearSignBit();
148     return Max;
149   }
150 
151   /// Return known bits for a truncation of the value we're tracking.
truncKnownBits152   KnownBits trunc(unsigned BitWidth) const {
153     return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
154   }
155 
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.
anyextKnownBits158   KnownBits anyext(unsigned BitWidth) const {
159     return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
160   }
161 
162   /// Return known bits for a zero extension of the value we're tracking.
zextKnownBits163   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));
168   }
169 
170   /// Return known bits for a sign extension of the value we're tracking.
sextKnownBits171   KnownBits sext(unsigned BitWidth) const {
172     return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
173   }
174 
175   /// Return known bits for an "any" extension or truncation of the value we're
176   /// tracking.
anyextOrTruncKnownBits177   KnownBits anyextOrTrunc(unsigned BitWidth) const {
178     if (BitWidth > getBitWidth())
179       return anyext(BitWidth);
180     if (BitWidth < getBitWidth())
181       return trunc(BitWidth);
182     return *this;
183   }
184 
185   /// Return known bits for a zero extension or truncation of the value we're
186   /// tracking.
zextOrTruncKnownBits187   KnownBits zextOrTrunc(unsigned BitWidth) const {
188     if (BitWidth > getBitWidth())
189       return zext(BitWidth);
190     if (BitWidth < getBitWidth())
191       return trunc(BitWidth);
192     return *this;
193   }
194 
195   /// Return known bits for a sign extension or truncation of the value we're
196   /// tracking.
sextOrTruncKnownBits197   KnownBits sextOrTrunc(unsigned BitWidth) const {
198     if (BitWidth > getBitWidth())
199       return sext(BitWidth);
200     if (BitWidth < getBitWidth())
201       return trunc(BitWidth);
202     return *this;
203   }
204 
205   /// Return known bits for a in-register sign extension of the value we're
206   /// tracking.
207   KnownBits sextInReg(unsigned SrcBitWidth) const;
208 
209   /// Insert the bits from a smaller known bits starting at bitPosition.
insertBitsKnownBits210   void insertBits(const KnownBits &SubBits, unsigned BitPosition) {
211     Zero.insertBits(SubBits.Zero, BitPosition);
212     One.insertBits(SubBits.One, BitPosition);
213   }
214 
215   /// Return a subset of the known bits from [bitPosition,bitPosition+numBits).
extractBitsKnownBits216   KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
217     return KnownBits(Zero.extractBits(NumBits, BitPosition),
218                      One.extractBits(NumBits, BitPosition));
219   }
220 
221   /// Concatenate the bits from \p Lo onto the bottom of *this.  This is
222   /// equivalent to:
223   ///   (this->zext(NewWidth) << Lo.getBitWidth()) | Lo.zext(NewWidth)
concatKnownBits224   KnownBits concat(const KnownBits &Lo) const {
225     return KnownBits(Zero.concat(Lo.Zero), One.concat(Lo.One));
226   }
227 
228   /// Return KnownBits based on this, but updated given that the underlying
229   /// value is known to be greater than or equal to Val.
230   KnownBits makeGE(const APInt &Val) const;
231 
232   /// Returns the minimum number of trailing zero bits.
countMinTrailingZerosKnownBits233   unsigned countMinTrailingZeros() const {
234     return Zero.countTrailingOnes();
235   }
236 
237   /// Returns the minimum number of trailing one bits.
countMinTrailingOnesKnownBits238   unsigned countMinTrailingOnes() const {
239     return One.countTrailingOnes();
240   }
241 
242   /// Returns the minimum number of leading zero bits.
countMinLeadingZerosKnownBits243   unsigned countMinLeadingZeros() const {
244     return Zero.countLeadingOnes();
245   }
246 
247   /// Returns the minimum number of leading one bits.
countMinLeadingOnesKnownBits248   unsigned countMinLeadingOnes() const {
249     return One.countLeadingOnes();
250   }
251 
252   /// Returns the number of times the sign bit is replicated into the other
253   /// bits.
countMinSignBitsKnownBits254   unsigned countMinSignBits() const {
255     if (isNonNegative())
256       return countMinLeadingZeros();
257     if (isNegative())
258       return countMinLeadingOnes();
259     // Every value has at least 1 sign bit.
260     return 1;
261   }
262 
263   /// Returns the maximum number of bits needed to represent all possible
264   /// signed values with these known bits. This is the inverse of the minimum
265   /// number of known sign bits. Examples for bitwidth 5:
266   /// 110?? --> 4
267   /// 0000? --> 2
countMaxSignificantBitsKnownBits268   unsigned countMaxSignificantBits() const {
269     return getBitWidth() - countMinSignBits() + 1;
270   }
271 
272   /// Returns the maximum number of trailing zero bits possible.
countMaxTrailingZerosKnownBits273   unsigned countMaxTrailingZeros() const {
274     return One.countTrailingZeros();
275   }
276 
277   /// Returns the maximum number of trailing one bits possible.
countMaxTrailingOnesKnownBits278   unsigned countMaxTrailingOnes() const {
279     return Zero.countTrailingZeros();
280   }
281 
282   /// Returns the maximum number of leading zero bits possible.
countMaxLeadingZerosKnownBits283   unsigned countMaxLeadingZeros() const {
284     return One.countLeadingZeros();
285   }
286 
287   /// Returns the maximum number of leading one bits possible.
countMaxLeadingOnesKnownBits288   unsigned countMaxLeadingOnes() const {
289     return Zero.countLeadingZeros();
290   }
291 
292   /// Returns the number of bits known to be one.
countMinPopulationKnownBits293   unsigned countMinPopulation() const {
294     return One.countPopulation();
295   }
296 
297   /// Returns the maximum number of bits that could be one.
countMaxPopulationKnownBits298   unsigned countMaxPopulation() const {
299     return getBitWidth() - Zero.countPopulation();
300   }
301 
302   /// Returns the maximum number of bits needed to represent all possible
303   /// unsigned values with these known bits. This is the inverse of the
304   /// minimum number of leading zeros.
countMaxActiveBitsKnownBits305   unsigned countMaxActiveBits() const {
306     return getBitWidth() - countMinLeadingZeros();
307   }
308 
309   /// Create known bits from a known constant.
makeConstantKnownBits310   static KnownBits makeConstant(const APInt &C) {
311     return KnownBits(~C, C);
312   }
313 
314   /// Compute known bits common to LHS and RHS.
commonBitsKnownBits315   static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) {
316     return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One);
317   }
318 
319   /// Return true if LHS and RHS have no common bits set.
haveNoCommonBitsSetKnownBits320   static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
321     return (LHS.Zero | RHS.Zero).isAllOnes();
322   }
323 
324   /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
325   static KnownBits computeForAddCarry(
326       const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
327 
328   /// Compute known bits resulting from adding LHS and RHS.
329   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
330                                     KnownBits RHS);
331 
332   /// Compute known bits resulting from multiplying LHS and RHS.
333   static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS,
334                        bool NoUndefSelfMultiply = false);
335 
336   /// Compute known bits from sign-extended multiply-hi.
337   static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
338 
339   /// Compute known bits from zero-extended multiply-hi.
340   static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
341 
342   /// Compute known bits for udiv(LHS, RHS).
343   static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
344 
345   /// Compute known bits for urem(LHS, RHS).
346   static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
347 
348   /// Compute known bits for srem(LHS, RHS).
349   static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);
350 
351   /// Compute known bits for umax(LHS, RHS).
352   static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
353 
354   /// Compute known bits for umin(LHS, RHS).
355   static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
356 
357   /// Compute known bits for smax(LHS, RHS).
358   static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
359 
360   /// Compute known bits for smin(LHS, RHS).
361   static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
362 
363   /// Compute known bits for shl(LHS, RHS).
364   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
365   static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS);
366 
367   /// Compute known bits for lshr(LHS, RHS).
368   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
369   static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS);
370 
371   /// Compute known bits for ashr(LHS, RHS).
372   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
373   static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS);
374 
375   /// Determine if these known bits always give the same ICMP_EQ result.
376   static std::optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS);
377 
378   /// Determine if these known bits always give the same ICMP_NE result.
379   static std::optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS);
380 
381   /// Determine if these known bits always give the same ICMP_UGT result.
382   static std::optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS);
383 
384   /// Determine if these known bits always give the same ICMP_UGE result.
385   static std::optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS);
386 
387   /// Determine if these known bits always give the same ICMP_ULT result.
388   static std::optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS);
389 
390   /// Determine if these known bits always give the same ICMP_ULE result.
391   static std::optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS);
392 
393   /// Determine if these known bits always give the same ICMP_SGT result.
394   static std::optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS);
395 
396   /// Determine if these known bits always give the same ICMP_SGE result.
397   static std::optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS);
398 
399   /// Determine if these known bits always give the same ICMP_SLT result.
400   static std::optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS);
401 
402   /// Determine if these known bits always give the same ICMP_SLE result.
403   static std::optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS);
404 
405   /// Update known bits based on ANDing with RHS.
406   KnownBits &operator&=(const KnownBits &RHS);
407 
408   /// Update known bits based on ORing with RHS.
409   KnownBits &operator|=(const KnownBits &RHS);
410 
411   /// Update known bits based on XORing with RHS.
412   KnownBits &operator^=(const KnownBits &RHS);
413 
414   /// Compute known bits for the absolute value.
415   KnownBits abs(bool IntMinIsPoison = false) const;
416 
byteSwapKnownBits417   KnownBits byteSwap() const {
418     return KnownBits(Zero.byteSwap(), One.byteSwap());
419   }
420 
reverseBitsKnownBits421   KnownBits reverseBits() const {
422     return KnownBits(Zero.reverseBits(), One.reverseBits());
423   }
424 
425   bool operator==(const KnownBits &Other) const {
426     return Zero == Other.Zero && One == Other.One;
427   }
428 
429   bool operator!=(const KnownBits &Other) const { return !(*this == Other); }
430 
431   void print(raw_ostream &OS) const;
432   void dump() const;
433 };
434 
435 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
436   LHS &= RHS;
437   return LHS;
438 }
439 
440 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
441   RHS &= LHS;
442   return std::move(RHS);
443 }
444 
445 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
446   LHS |= RHS;
447   return LHS;
448 }
449 
450 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
451   RHS |= LHS;
452   return std::move(RHS);
453 }
454 
455 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
456   LHS ^= RHS;
457   return LHS;
458 }
459 
460 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
461   RHS ^= LHS;
462   return std::move(RHS);
463 }
464 
465 } // end namespace llvm
466 
467 #endif
468