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() {}
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.isNullValue() && One.isNullValue(); }
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.isAllOnesValue();
75   }
76 
77   /// Returns true if value is all one bits.
78   bool isAllOnes() const {
79     assert(!hasConflict() && "KnownBits conflict!");
80     return One.isAllOnesValue();
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.isNullValue(); }
103 
104   /// Returns true if this value is known to be positive.
105   bool isStrictlyPositive() const { return Zero.isSignBitSet() && !One.isNullValue(); }
106 
107   /// Make this value negative.
108   void makeNegative() {
109     One.setSignBit();
110   }
111 
112   /// Make this value non-negative.
113   void makeNonNegative() {
114     Zero.setSignBit();
115   }
116 
117   /// Return the minimal unsigned value possible given these KnownBits.
118   APInt getMinValue() const {
119     // Assume that all bits that aren't known-ones are zeros.
120     return One;
121   }
122 
123   /// Return the minimal signed value possible given these KnownBits.
124   APInt getSignedMinValue() const {
125     // Assume that all bits that aren't known-ones are zeros.
126     APInt Min = One;
127     // Sign bit is unknown.
128     if (Zero.isSignBitClear())
129       Min.setSignBit();
130     return Min;
131   }
132 
133   /// Return the maximal unsigned value possible given these KnownBits.
134   APInt getMaxValue() const {
135     // Assume that all bits that aren't known-zeros are ones.
136     return ~Zero;
137   }
138 
139   /// Return the maximal signed value possible given these KnownBits.
140   APInt getSignedMaxValue() const {
141     // Assume that all bits that aren't known-zeros are ones.
142     APInt Max = ~Zero;
143     // Sign bit is unknown.
144     if (One.isSignBitClear())
145       Max.clearSignBit();
146     return Max;
147   }
148 
149   /// Return known bits for a truncation of the value we're tracking.
150   KnownBits trunc(unsigned BitWidth) const {
151     return KnownBits(Zero.trunc(BitWidth), One.trunc(BitWidth));
152   }
153 
154   /// Return known bits for an "any" extension of the value we're tracking,
155   /// where we don't know anything about the extended bits.
156   KnownBits anyext(unsigned BitWidth) const {
157     return KnownBits(Zero.zext(BitWidth), One.zext(BitWidth));
158   }
159 
160   /// Return known bits for a zero extension of the value we're tracking.
161   KnownBits zext(unsigned BitWidth) const {
162     unsigned OldBitWidth = getBitWidth();
163     APInt NewZero = Zero.zext(BitWidth);
164     NewZero.setBitsFrom(OldBitWidth);
165     return KnownBits(NewZero, One.zext(BitWidth));
166   }
167 
168   /// Return known bits for a sign extension of the value we're tracking.
169   KnownBits sext(unsigned BitWidth) const {
170     return KnownBits(Zero.sext(BitWidth), One.sext(BitWidth));
171   }
172 
173   /// Return known bits for an "any" extension or truncation of the value we're
174   /// tracking.
175   KnownBits anyextOrTrunc(unsigned BitWidth) const {
176     if (BitWidth > getBitWidth())
177       return anyext(BitWidth);
178     if (BitWidth < getBitWidth())
179       return trunc(BitWidth);
180     return *this;
181   }
182 
183   /// Return known bits for a zero extension or truncation of the value we're
184   /// tracking.
185   KnownBits zextOrTrunc(unsigned BitWidth) const {
186     if (BitWidth > getBitWidth())
187       return zext(BitWidth);
188     if (BitWidth < getBitWidth())
189       return trunc(BitWidth);
190     return *this;
191   }
192 
193   /// Return known bits for a sign extension or truncation of the value we're
194   /// tracking.
195   KnownBits sextOrTrunc(unsigned BitWidth) const {
196     if (BitWidth > getBitWidth())
197       return sext(BitWidth);
198     if (BitWidth < getBitWidth())
199       return trunc(BitWidth);
200     return *this;
201   }
202 
203   /// Return known bits for a in-register sign extension of the value we're
204   /// tracking.
205   KnownBits sextInReg(unsigned SrcBitWidth) const;
206 
207   /// Insert the bits from a smaller known bits starting at bitPosition.
208   void insertBits(const KnownBits &SubBits, unsigned BitPosition) {
209     Zero.insertBits(SubBits.Zero, BitPosition);
210     One.insertBits(SubBits.One, BitPosition);
211   }
212 
213   /// Return a subset of the known bits from [bitPosition,bitPosition+numBits).
214   KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const {
215     return KnownBits(Zero.extractBits(NumBits, BitPosition),
216                      One.extractBits(NumBits, BitPosition));
217   }
218 
219   /// Return KnownBits based on this, but updated given that the underlying
220   /// value is known to be greater than or equal to Val.
221   KnownBits makeGE(const APInt &Val) const;
222 
223   /// Returns the minimum number of trailing zero bits.
224   unsigned countMinTrailingZeros() const {
225     return Zero.countTrailingOnes();
226   }
227 
228   /// Returns the minimum number of trailing one bits.
229   unsigned countMinTrailingOnes() const {
230     return One.countTrailingOnes();
231   }
232 
233   /// Returns the minimum number of leading zero bits.
234   unsigned countMinLeadingZeros() const {
235     return Zero.countLeadingOnes();
236   }
237 
238   /// Returns the minimum number of leading one bits.
239   unsigned countMinLeadingOnes() const {
240     return One.countLeadingOnes();
241   }
242 
243   /// Returns the number of times the sign bit is replicated into the other
244   /// bits.
245   unsigned countMinSignBits() const {
246     if (isNonNegative())
247       return countMinLeadingZeros();
248     if (isNegative())
249       return countMinLeadingOnes();
250     return 0;
251   }
252 
253   /// Returns the maximum number of trailing zero bits possible.
254   unsigned countMaxTrailingZeros() const {
255     return One.countTrailingZeros();
256   }
257 
258   /// Returns the maximum number of trailing one bits possible.
259   unsigned countMaxTrailingOnes() const {
260     return Zero.countTrailingZeros();
261   }
262 
263   /// Returns the maximum number of leading zero bits possible.
264   unsigned countMaxLeadingZeros() const {
265     return One.countLeadingZeros();
266   }
267 
268   /// Returns the maximum number of leading one bits possible.
269   unsigned countMaxLeadingOnes() const {
270     return Zero.countLeadingZeros();
271   }
272 
273   /// Returns the number of bits known to be one.
274   unsigned countMinPopulation() const {
275     return One.countPopulation();
276   }
277 
278   /// Returns the maximum number of bits that could be one.
279   unsigned countMaxPopulation() const {
280     return getBitWidth() - Zero.countPopulation();
281   }
282 
283   /// Create known bits from a known constant.
284   static KnownBits makeConstant(const APInt &C) {
285     return KnownBits(~C, C);
286   }
287 
288   /// Compute known bits common to LHS and RHS.
289   static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) {
290     return KnownBits(LHS.Zero & RHS.Zero, LHS.One & RHS.One);
291   }
292 
293   /// Return true if LHS and RHS have no common bits set.
294   static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
295     return (LHS.Zero | RHS.Zero).isAllOnesValue();
296   }
297 
298   /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
299   static KnownBits computeForAddCarry(
300       const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
301 
302   /// Compute known bits resulting from adding LHS and RHS.
303   static KnownBits computeForAddSub(bool Add, bool NSW, const KnownBits &LHS,
304                                     KnownBits RHS);
305 
306   /// Compute known bits resulting from multiplying LHS and RHS.
307   static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS);
308 
309   /// Compute known bits from sign-extended multiply-hi.
310   static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
311 
312   /// Compute known bits from zero-extended multiply-hi.
313   static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
314 
315   /// Compute known bits for udiv(LHS, RHS).
316   static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS);
317 
318   /// Compute known bits for urem(LHS, RHS).
319   static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
320 
321   /// Compute known bits for srem(LHS, RHS).
322   static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);
323 
324   /// Compute known bits for umax(LHS, RHS).
325   static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
326 
327   /// Compute known bits for umin(LHS, RHS).
328   static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
329 
330   /// Compute known bits for smax(LHS, RHS).
331   static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
332 
333   /// Compute known bits for smin(LHS, RHS).
334   static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
335 
336   /// Compute known bits for shl(LHS, RHS).
337   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
338   static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS);
339 
340   /// Compute known bits for lshr(LHS, RHS).
341   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
342   static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS);
343 
344   /// Compute known bits for ashr(LHS, RHS).
345   /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
346   static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS);
347 
348   /// Determine if these known bits always give the same ICMP_EQ result.
349   static Optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS);
350 
351   /// Determine if these known bits always give the same ICMP_NE result.
352   static Optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS);
353 
354   /// Determine if these known bits always give the same ICMP_UGT result.
355   static Optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS);
356 
357   /// Determine if these known bits always give the same ICMP_UGE result.
358   static Optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS);
359 
360   /// Determine if these known bits always give the same ICMP_ULT result.
361   static Optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS);
362 
363   /// Determine if these known bits always give the same ICMP_ULE result.
364   static Optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS);
365 
366   /// Determine if these known bits always give the same ICMP_SGT result.
367   static Optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS);
368 
369   /// Determine if these known bits always give the same ICMP_SGE result.
370   static Optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS);
371 
372   /// Determine if these known bits always give the same ICMP_SLT result.
373   static Optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS);
374 
375   /// Determine if these known bits always give the same ICMP_SLE result.
376   static Optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS);
377 
378   /// Update known bits based on ANDing with RHS.
379   KnownBits &operator&=(const KnownBits &RHS);
380 
381   /// Update known bits based on ORing with RHS.
382   KnownBits &operator|=(const KnownBits &RHS);
383 
384   /// Update known bits based on XORing with RHS.
385   KnownBits &operator^=(const KnownBits &RHS);
386 
387   /// Compute known bits for the absolute value.
388   KnownBits abs(bool IntMinIsPoison = false) const;
389 
390   KnownBits byteSwap() {
391     return KnownBits(Zero.byteSwap(), One.byteSwap());
392   }
393 
394   KnownBits reverseBits() {
395     return KnownBits(Zero.reverseBits(), One.reverseBits());
396   }
397 
398   void print(raw_ostream &OS) const;
399   void dump() const;
400 };
401 
402 inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
403   LHS &= RHS;
404   return LHS;
405 }
406 
407 inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
408   RHS &= LHS;
409   return std::move(RHS);
410 }
411 
412 inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
413   LHS |= RHS;
414   return LHS;
415 }
416 
417 inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
418   RHS |= LHS;
419   return std::move(RHS);
420 }
421 
422 inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
423   LHS ^= RHS;
424   return LHS;
425 }
426 
427 inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
428   RHS ^= LHS;
429   return std::move(RHS);
430 }
431 
432 } // end namespace llvm
433 
434 #endif
435