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 "llvm/ADT/Optional.h"
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.
29   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.
37   KnownBits(unsigned BitWidth) : Zero(BitWidth, 0), One(BitWidth, 0) {}
38 
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();
44   }
45 
46   /// Returns true if there is conflicting information.
47   bool hasConflict() const { return Zero.intersects(One); }
48 
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();
53   }
54 
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");
59     return One;
60   }
61 
62   /// Returns true if we don't know any bits.
63   bool isUnknown() const { return Zero.isZero() && One.isZero(); }
64 
65   /// Resets the known state of all bits.
66   void resetAll() {
67     Zero.clearAllBits();
68     One.clearAllBits();
69   }
70 
71   /// Returns true if value is all zero.
72   bool isZero() const {
73     assert(!hasConflict() && "KnownBits conflict!");
74     return Zero.isAllOnes();
75   }
76 
77   /// Returns true if value is all one bits.
78   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.
84   void setAllZero() {
85     Zero.setAllBits();
86     One.clearAllBits();
87   }
88 
89   /// Make all bits known to be one and discard any previous information.
90   void setAllOnes() {
91     Zero.clearAllBits();
92     One.setAllBits();
93   }
94 
95   /// Returns true if this value is known to be negative.
96   bool isNegative() const { return One.isSignBitSet(); }
97 
98   /// Returns true if this value is known to be non-negative.
99   bool isNonNegative() const { return Zero.isSignBitSet(); }
100 
101   /// Returns true if this value is known to be non-zero.
102   bool isNonZero() const { return !One.isZero(); }
103 
104   /// Returns true if this value is known to be positive.
105   bool isStrictlyPositive() const {
106     return Zero.isSignBitSet() && !One.isZero();
107   }
108 
109   /// Make this value negative.
110   void makeNegative() {
111     One.setSignBit();
112   }
113 
114   /// Make this value non-negative.
115   void makeNonNegative() {
116     Zero.setSignBit();
117   }
118 
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.
122     return One;
123   }
124 
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.
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.
136   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.
142   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.
152   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.
158   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.
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));
168   }
169 
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));
173   }
174 
175   /// Return known bits for an "any" extension or truncation of the value we're
176   /// tracking.
177   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.
187   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.
197   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.
210   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).
216   KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
217     return KnownBits(Zero.extractBits(NumBits, BitPosition),
218                      One.extractBits(NumBits, BitPosition));
219   }
220 
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;
224 
225   /// Returns the minimum number of trailing zero bits.
226   unsigned countMinTrailingZeros() const {
227     return Zero.countTrailingOnes();
228   }
229 
230   /// Returns the minimum number of trailing one bits.
231   unsigned countMinTrailingOnes() const {
232     return One.countTrailingOnes();
233   }
234 
235   /// Returns the minimum number of leading zero bits.
236   unsigned countMinLeadingZeros() const {
237     return Zero.countLeadingOnes();
238   }
239 
240   /// Returns the minimum number of leading one bits.
241   unsigned countMinLeadingOnes() const {
242     return One.countLeadingOnes();
243   }
244 
245   /// Returns the number of times the sign bit is replicated into the other
246   /// bits.
247   unsigned countMinSignBits() const {
248     if (isNonNegative())
249       return countMinLeadingZeros();
250     if (isNegative())
251       return countMinLeadingOnes();
252     // Every value has at least 1 sign bit.
253     return 1;
254   }
255 
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:
259   /// 110?? --> 4
260   /// 0000? --> 2
261   unsigned countMaxSignificantBits() const {
262     return getBitWidth() - countMinSignBits() + 1;
263   }
264 
265   /// Returns the maximum number of trailing zero bits possible.
266   unsigned countMaxTrailingZeros() const {
267     return One.countTrailingZeros();
268   }
269 
270   /// Returns the maximum number of trailing one bits possible.
271   unsigned countMaxTrailingOnes() const {
272     return Zero.countTrailingZeros();
273   }
274 
275   /// Returns the maximum number of leading zero bits possible.
276   unsigned countMaxLeadingZeros() const {
277     return One.countLeadingZeros();
278   }
279 
280   /// Returns the maximum number of leading one bits possible.
281   unsigned countMaxLeadingOnes() const {
282     return Zero.countLeadingZeros();
283   }
284 
285   /// Returns the number of bits known to be one.
286   unsigned countMinPopulation() const {
287     return One.countPopulation();
288   }
289 
290   /// Returns the maximum number of bits that could be one.
291   unsigned countMaxPopulation() const {
292     return getBitWidth() - Zero.countPopulation();
293   }
294 
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();
300   }
301 
302   /// Create known bits from a known constant.
303   static KnownBits makeConstant(const APInt &C) {
304     return KnownBits(~C, C);
305   }
306 
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);
310   }
311 
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();
315   }
316 
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);
320 
321   /// Compute known bits resulting from adding LHS and RHS.
322   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
323                                     KnownBits RHS);
324 
325   /// Compute known bits resulting from multiplying LHS and RHS.
326   static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS,
327                        bool NoUndefSelfMultiply = false);
328 
329   /// Compute known bits from sign-extended multiply-hi.
330   static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
331 
332   /// Compute known bits from zero-extended multiply-hi.
333   static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
334 
335   /// Compute known bits for udiv(LHS, RHS).
336   static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
337 
338   /// Compute known bits for urem(LHS, RHS).
339   static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
340 
341   /// Compute known bits for srem(LHS, RHS).
342   static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);
343 
344   /// Compute known bits for umax(LHS, RHS).
345   static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
346 
347   /// Compute known bits for umin(LHS, RHS).
348   static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
349 
350   /// Compute known bits for smax(LHS, RHS).
351   static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
352 
353   /// Compute known bits for smin(LHS, RHS).
354   static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
355 
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);
359 
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);
363 
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);
367 
368   /// Determine if these known bits always give the same ICMP_EQ result.
369   static Optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS);
370 
371   /// Determine if these known bits always give the same ICMP_NE result.
372   static Optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS);
373 
374   /// Determine if these known bits always give the same ICMP_UGT result.
375   static Optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS);
376 
377   /// Determine if these known bits always give the same ICMP_UGE result.
378   static Optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS);
379 
380   /// Determine if these known bits always give the same ICMP_ULT result.
381   static Optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS);
382 
383   /// Determine if these known bits always give the same ICMP_ULE result.
384   static Optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS);
385 
386   /// Determine if these known bits always give the same ICMP_SGT result.
387   static Optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS);
388 
389   /// Determine if these known bits always give the same ICMP_SGE result.
390   static Optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS);
391 
392   /// Determine if these known bits always give the same ICMP_SLT result.
393   static Optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS);
394 
395   /// Determine if these known bits always give the same ICMP_SLE result.
396   static Optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS);
397 
398   /// Update known bits based on ANDing with RHS.
399   KnownBits &operator&=(const KnownBits &RHS);
400 
401   /// Update known bits based on ORing with RHS.
402   KnownBits &operator|=(const KnownBits &RHS);
403 
404   /// Update known bits based on XORing with RHS.
405   KnownBits &operator^=(const KnownBits &RHS);
406 
407   /// Compute known bits for the absolute value.
408   KnownBits abs(bool IntMinIsPoison = false) const;
409 
410   KnownBits byteSwap() {
411     return KnownBits(Zero.byteSwap(), One.byteSwap());
412   }
413 
414   KnownBits reverseBits() {
415     return KnownBits(Zero.reverseBits(), One.reverseBits());
416   }
417 
418   bool operator==(const KnownBits &Other) const {
419     return Zero == Other.Zero && One == Other.One;
420   }
421 
422   bool operator!=(const KnownBits &Other) const { return !(*this == Other); }
423 
424   void print(raw_ostream &OS) const;
425   void dump() const;
426 };
427 
428 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
429   LHS &= RHS;
430   return LHS;
431 }
432 
433 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
434   RHS &= LHS;
435   return std::move(RHS);
436 }
437 
438 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
439   LHS |= RHS;
440   return LHS;
441 }
442 
443 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
444   RHS |= LHS;
445   return std::move(RHS);
446 }
447 
448 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
449   LHS ^= RHS;
450   return LHS;
451 }
452 
453 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
454   RHS ^= LHS;
455   return std::move(RHS);
456 }
457 
458 } // end namespace llvm
459 
460 #endif
461