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. |
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(RHS: 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.popcount() + One.popcount() == 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 | /// Returns true if we don't know the sign bit. |
66 | bool isSignUnknown() const { |
67 | return !Zero.isSignBitSet() && !One.isSignBitSet(); |
68 | } |
69 | |
70 | /// Resets the known state of all bits. |
71 | void resetAll() { |
72 | Zero.clearAllBits(); |
73 | One.clearAllBits(); |
74 | } |
75 | |
76 | /// Returns true if value is all zero. |
77 | bool isZero() const { |
78 | assert(!hasConflict() && "KnownBits conflict!" ); |
79 | return Zero.isAllOnes(); |
80 | } |
81 | |
82 | /// Returns true if value is all one bits. |
83 | bool isAllOnes() const { |
84 | assert(!hasConflict() && "KnownBits conflict!" ); |
85 | return One.isAllOnes(); |
86 | } |
87 | |
88 | /// Make all bits known to be zero and discard any previous information. |
89 | void setAllZero() { |
90 | Zero.setAllBits(); |
91 | One.clearAllBits(); |
92 | } |
93 | |
94 | /// Make all bits known to be one and discard any previous information. |
95 | void setAllOnes() { |
96 | Zero.clearAllBits(); |
97 | One.setAllBits(); |
98 | } |
99 | |
100 | /// Returns true if this value is known to be negative. |
101 | bool isNegative() const { return One.isSignBitSet(); } |
102 | |
103 | /// Returns true if this value is known to be non-negative. |
104 | bool isNonNegative() const { return Zero.isSignBitSet(); } |
105 | |
106 | /// Returns true if this value is known to be non-zero. |
107 | bool isNonZero() const { return !One.isZero(); } |
108 | |
109 | /// Returns true if this value is known to be positive. |
110 | bool isStrictlyPositive() const { |
111 | return Zero.isSignBitSet() && !One.isZero(); |
112 | } |
113 | |
114 | /// Make this value negative. |
115 | void makeNegative() { |
116 | One.setSignBit(); |
117 | } |
118 | |
119 | /// Make this value non-negative. |
120 | void makeNonNegative() { |
121 | Zero.setSignBit(); |
122 | } |
123 | |
124 | /// Return the minimal unsigned value possible given these KnownBits. |
125 | APInt getMinValue() const { |
126 | // Assume that all bits that aren't known-ones are zeros. |
127 | return One; |
128 | } |
129 | |
130 | /// Return the minimal signed value possible given these KnownBits. |
131 | APInt getSignedMinValue() const { |
132 | // Assume that all bits that aren't known-ones are zeros. |
133 | APInt Min = One; |
134 | // Sign bit is unknown. |
135 | if (Zero.isSignBitClear()) |
136 | Min.setSignBit(); |
137 | return Min; |
138 | } |
139 | |
140 | /// Return the maximal unsigned value possible given these KnownBits. |
141 | APInt getMaxValue() const { |
142 | // Assume that all bits that aren't known-zeros are ones. |
143 | return ~Zero; |
144 | } |
145 | |
146 | /// Return the maximal signed value possible given these KnownBits. |
147 | APInt getSignedMaxValue() const { |
148 | // Assume that all bits that aren't known-zeros are ones. |
149 | APInt Max = ~Zero; |
150 | // Sign bit is unknown. |
151 | if (One.isSignBitClear()) |
152 | Max.clearSignBit(); |
153 | return Max; |
154 | } |
155 | |
156 | /// Return known bits for a truncation of the value we're tracking. |
157 | KnownBits trunc(unsigned BitWidth) const { |
158 | return KnownBits(Zero.trunc(width: BitWidth), One.trunc(width: BitWidth)); |
159 | } |
160 | |
161 | /// Return known bits for an "any" extension of the value we're tracking, |
162 | /// where we don't know anything about the extended bits. |
163 | KnownBits anyext(unsigned BitWidth) const { |
164 | return KnownBits(Zero.zext(width: BitWidth), One.zext(width: BitWidth)); |
165 | } |
166 | |
167 | /// Return known bits for a zero extension of the value we're tracking. |
168 | KnownBits zext(unsigned BitWidth) const { |
169 | unsigned OldBitWidth = getBitWidth(); |
170 | APInt NewZero = Zero.zext(width: BitWidth); |
171 | NewZero.setBitsFrom(OldBitWidth); |
172 | return KnownBits(NewZero, One.zext(width: BitWidth)); |
173 | } |
174 | |
175 | /// Return known bits for a sign extension of the value we're tracking. |
176 | KnownBits sext(unsigned BitWidth) const { |
177 | return KnownBits(Zero.sext(width: BitWidth), One.sext(width: BitWidth)); |
178 | } |
179 | |
180 | /// Return known bits for an "any" extension or truncation of the value we're |
181 | /// tracking. |
182 | KnownBits anyextOrTrunc(unsigned BitWidth) const { |
183 | if (BitWidth > getBitWidth()) |
184 | return anyext(BitWidth); |
185 | if (BitWidth < getBitWidth()) |
186 | return trunc(BitWidth); |
187 | return *this; |
188 | } |
189 | |
190 | /// Return known bits for a zero extension or truncation of the value we're |
191 | /// tracking. |
192 | KnownBits zextOrTrunc(unsigned BitWidth) const { |
193 | if (BitWidth > getBitWidth()) |
194 | return zext(BitWidth); |
195 | if (BitWidth < getBitWidth()) |
196 | return trunc(BitWidth); |
197 | return *this; |
198 | } |
199 | |
200 | /// Return known bits for a sign extension or truncation of the value we're |
201 | /// tracking. |
202 | KnownBits sextOrTrunc(unsigned BitWidth) const { |
203 | if (BitWidth > getBitWidth()) |
204 | return sext(BitWidth); |
205 | if (BitWidth < getBitWidth()) |
206 | return trunc(BitWidth); |
207 | return *this; |
208 | } |
209 | |
210 | /// Return known bits for a in-register sign extension of the value we're |
211 | /// tracking. |
212 | KnownBits sextInReg(unsigned SrcBitWidth) const; |
213 | |
214 | /// Insert the bits from a smaller known bits starting at bitPosition. |
215 | void insertBits(const KnownBits &SubBits, unsigned BitPosition) { |
216 | Zero.insertBits(SubBits: SubBits.Zero, bitPosition: BitPosition); |
217 | One.insertBits(SubBits: SubBits.One, bitPosition: BitPosition); |
218 | } |
219 | |
220 | /// Return a subset of the known bits from [bitPosition,bitPosition+numBits). |
221 | KnownBits (unsigned NumBits, unsigned BitPosition) const { |
222 | return KnownBits(Zero.extractBits(numBits: NumBits, bitPosition: BitPosition), |
223 | One.extractBits(numBits: NumBits, bitPosition: BitPosition)); |
224 | } |
225 | |
226 | /// Concatenate the bits from \p Lo onto the bottom of *this. This is |
227 | /// equivalent to: |
228 | /// (this->zext(NewWidth) << Lo.getBitWidth()) | Lo.zext(NewWidth) |
229 | KnownBits concat(const KnownBits &Lo) const { |
230 | return KnownBits(Zero.concat(NewLSB: Lo.Zero), One.concat(NewLSB: Lo.One)); |
231 | } |
232 | |
233 | /// Return KnownBits based on this, but updated given that the underlying |
234 | /// value is known to be greater than or equal to Val. |
235 | KnownBits makeGE(const APInt &Val) const; |
236 | |
237 | /// Returns the minimum number of trailing zero bits. |
238 | unsigned countMinTrailingZeros() const { return Zero.countr_one(); } |
239 | |
240 | /// Returns the minimum number of trailing one bits. |
241 | unsigned countMinTrailingOnes() const { return One.countr_one(); } |
242 | |
243 | /// Returns the minimum number of leading zero bits. |
244 | unsigned countMinLeadingZeros() const { return Zero.countl_one(); } |
245 | |
246 | /// Returns the minimum number of leading one bits. |
247 | unsigned countMinLeadingOnes() const { return One.countl_one(); } |
248 | |
249 | /// Returns the number of times the sign bit is replicated into the other |
250 | /// bits. |
251 | unsigned countMinSignBits() const { |
252 | if (isNonNegative()) |
253 | return countMinLeadingZeros(); |
254 | if (isNegative()) |
255 | return countMinLeadingOnes(); |
256 | // Every value has at least 1 sign bit. |
257 | return 1; |
258 | } |
259 | |
260 | /// Returns the maximum number of bits needed to represent all possible |
261 | /// signed values with these known bits. This is the inverse of the minimum |
262 | /// number of known sign bits. Examples for bitwidth 5: |
263 | /// 110?? --> 4 |
264 | /// 0000? --> 2 |
265 | unsigned countMaxSignificantBits() const { |
266 | return getBitWidth() - countMinSignBits() + 1; |
267 | } |
268 | |
269 | /// Returns the maximum number of trailing zero bits possible. |
270 | unsigned countMaxTrailingZeros() const { return One.countr_zero(); } |
271 | |
272 | /// Returns the maximum number of trailing one bits possible. |
273 | unsigned countMaxTrailingOnes() const { return Zero.countr_zero(); } |
274 | |
275 | /// Returns the maximum number of leading zero bits possible. |
276 | unsigned countMaxLeadingZeros() const { return One.countl_zero(); } |
277 | |
278 | /// Returns the maximum number of leading one bits possible. |
279 | unsigned countMaxLeadingOnes() const { return Zero.countl_zero(); } |
280 | |
281 | /// Returns the number of bits known to be one. |
282 | unsigned countMinPopulation() const { return One.popcount(); } |
283 | |
284 | /// Returns the maximum number of bits that could be one. |
285 | unsigned countMaxPopulation() const { |
286 | return getBitWidth() - Zero.popcount(); |
287 | } |
288 | |
289 | /// Returns the maximum number of bits needed to represent all possible |
290 | /// unsigned values with these known bits. This is the inverse of the |
291 | /// minimum number of leading zeros. |
292 | unsigned countMaxActiveBits() const { |
293 | return getBitWidth() - countMinLeadingZeros(); |
294 | } |
295 | |
296 | /// Create known bits from a known constant. |
297 | static KnownBits makeConstant(const APInt &C) { |
298 | return KnownBits(~C, C); |
299 | } |
300 | |
301 | /// Returns KnownBits information that is known to be true for both this and |
302 | /// RHS. |
303 | /// |
304 | /// When an operation is known to return one of its operands, this can be used |
305 | /// to combine information about the known bits of the operands to get the |
306 | /// information that must be true about the result. |
307 | KnownBits intersectWith(const KnownBits &RHS) const { |
308 | return KnownBits(Zero & RHS.Zero, One & RHS.One); |
309 | } |
310 | |
311 | /// Returns KnownBits information that is known to be true for either this or |
312 | /// RHS or both. |
313 | /// |
314 | /// This can be used to combine different sources of information about the |
315 | /// known bits of a single value, e.g. information about the low bits and the |
316 | /// high bits of the result of a multiplication. |
317 | KnownBits unionWith(const KnownBits &RHS) const { |
318 | return KnownBits(Zero | RHS.Zero, One | RHS.One); |
319 | } |
320 | |
321 | /// Compute known bits common to LHS and RHS. |
322 | LLVM_DEPRECATED("use intersectWith instead" , "intersectWith" ) |
323 | static KnownBits commonBits(const KnownBits &LHS, const KnownBits &RHS) { |
324 | return LHS.intersectWith(RHS); |
325 | } |
326 | |
327 | /// Return true if LHS and RHS have no common bits set. |
328 | static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) { |
329 | return (LHS.Zero | RHS.Zero).isAllOnes(); |
330 | } |
331 | |
332 | /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry. |
333 | static KnownBits computeForAddCarry( |
334 | const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry); |
335 | |
336 | /// Compute known bits resulting from adding LHS and RHS. |
337 | static KnownBits computeForAddSub(bool Add, bool NSW, bool NUW, |
338 | const KnownBits &LHS, const KnownBits &RHS); |
339 | |
340 | /// Compute known bits results from subtracting RHS from LHS with 1-bit |
341 | /// Borrow. |
342 | static KnownBits computeForSubBorrow(const KnownBits &LHS, KnownBits RHS, |
343 | const KnownBits &Borrow); |
344 | |
345 | /// Compute knownbits resulting from llvm.sadd.sat(LHS, RHS) |
346 | static KnownBits sadd_sat(const KnownBits &LHS, const KnownBits &RHS); |
347 | |
348 | /// Compute knownbits resulting from llvm.uadd.sat(LHS, RHS) |
349 | static KnownBits uadd_sat(const KnownBits &LHS, const KnownBits &RHS); |
350 | |
351 | /// Compute knownbits resulting from llvm.ssub.sat(LHS, RHS) |
352 | static KnownBits ssub_sat(const KnownBits &LHS, const KnownBits &RHS); |
353 | |
354 | /// Compute knownbits resulting from llvm.usub.sat(LHS, RHS) |
355 | static KnownBits usub_sat(const KnownBits &LHS, const KnownBits &RHS); |
356 | |
357 | /// Compute known bits resulting from multiplying LHS and RHS. |
358 | static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, |
359 | bool NoUndefSelfMultiply = false); |
360 | |
361 | /// Compute known bits from sign-extended multiply-hi. |
362 | static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS); |
363 | |
364 | /// Compute known bits from zero-extended multiply-hi. |
365 | static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS); |
366 | |
367 | /// Compute known bits for sdiv(LHS, RHS). |
368 | static KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS, |
369 | bool Exact = false); |
370 | |
371 | /// Compute known bits for udiv(LHS, RHS). |
372 | static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, |
373 | bool Exact = false); |
374 | |
375 | /// Compute known bits for urem(LHS, RHS). |
376 | static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS); |
377 | |
378 | /// Compute known bits for srem(LHS, RHS). |
379 | static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS); |
380 | |
381 | /// Compute known bits for umax(LHS, RHS). |
382 | static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS); |
383 | |
384 | /// Compute known bits for umin(LHS, RHS). |
385 | static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS); |
386 | |
387 | /// Compute known bits for smax(LHS, RHS). |
388 | static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS); |
389 | |
390 | /// Compute known bits for smin(LHS, RHS). |
391 | static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS); |
392 | |
393 | /// Compute known bits for abdu(LHS, RHS). |
394 | static KnownBits abdu(const KnownBits &LHS, const KnownBits &RHS); |
395 | |
396 | /// Compute known bits for abds(LHS, RHS). |
397 | static KnownBits abds(KnownBits LHS, KnownBits RHS); |
398 | |
399 | /// Compute known bits for shl(LHS, RHS). |
400 | /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. |
401 | static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, |
402 | bool NUW = false, bool NSW = false, |
403 | bool ShAmtNonZero = false); |
404 | |
405 | /// Compute known bits for lshr(LHS, RHS). |
406 | /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. |
407 | static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, |
408 | bool ShAmtNonZero = false, bool Exact = false); |
409 | |
410 | /// Compute known bits for ashr(LHS, RHS). |
411 | /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS. |
412 | static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, |
413 | bool ShAmtNonZero = false, bool Exact = false); |
414 | |
415 | /// Determine if these known bits always give the same ICMP_EQ result. |
416 | static std::optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS); |
417 | |
418 | /// Determine if these known bits always give the same ICMP_NE result. |
419 | static std::optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS); |
420 | |
421 | /// Determine if these known bits always give the same ICMP_UGT result. |
422 | static std::optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS); |
423 | |
424 | /// Determine if these known bits always give the same ICMP_UGE result. |
425 | static std::optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS); |
426 | |
427 | /// Determine if these known bits always give the same ICMP_ULT result. |
428 | static std::optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS); |
429 | |
430 | /// Determine if these known bits always give the same ICMP_ULE result. |
431 | static std::optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS); |
432 | |
433 | /// Determine if these known bits always give the same ICMP_SGT result. |
434 | static std::optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS); |
435 | |
436 | /// Determine if these known bits always give the same ICMP_SGE result. |
437 | static std::optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS); |
438 | |
439 | /// Determine if these known bits always give the same ICMP_SLT result. |
440 | static std::optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS); |
441 | |
442 | /// Determine if these known bits always give the same ICMP_SLE result. |
443 | static std::optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS); |
444 | |
445 | /// Update known bits based on ANDing with RHS. |
446 | KnownBits &operator&=(const KnownBits &RHS); |
447 | |
448 | /// Update known bits based on ORing with RHS. |
449 | KnownBits &operator|=(const KnownBits &RHS); |
450 | |
451 | /// Update known bits based on XORing with RHS. |
452 | KnownBits &operator^=(const KnownBits &RHS); |
453 | |
454 | /// Compute known bits for the absolute value. |
455 | KnownBits abs(bool IntMinIsPoison = false) const; |
456 | |
457 | KnownBits byteSwap() const { |
458 | return KnownBits(Zero.byteSwap(), One.byteSwap()); |
459 | } |
460 | |
461 | KnownBits reverseBits() const { |
462 | return KnownBits(Zero.reverseBits(), One.reverseBits()); |
463 | } |
464 | |
465 | /// Compute known bits for X & -X, which has only the lowest bit set of X set. |
466 | /// The name comes from the X86 BMI instruction |
467 | KnownBits blsi() const; |
468 | |
469 | /// Compute known bits for X ^ (X - 1), which has all bits up to and including |
470 | /// the lowest set bit of X set. The name comes from the X86 BMI instruction. |
471 | KnownBits blsmsk() const; |
472 | |
473 | bool operator==(const KnownBits &Other) const { |
474 | return Zero == Other.Zero && One == Other.One; |
475 | } |
476 | |
477 | bool operator!=(const KnownBits &Other) const { return !(*this == Other); } |
478 | |
479 | void print(raw_ostream &OS) const; |
480 | void dump() const; |
481 | |
482 | private: |
483 | // Internal helper for getting the initial KnownBits for an `srem` or `urem` |
484 | // operation with the low-bits set. |
485 | static KnownBits remGetLowBits(const KnownBits &LHS, const KnownBits &RHS); |
486 | }; |
487 | |
488 | inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) { |
489 | LHS &= RHS; |
490 | return LHS; |
491 | } |
492 | |
493 | inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) { |
494 | RHS &= LHS; |
495 | return std::move(RHS); |
496 | } |
497 | |
498 | inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) { |
499 | LHS |= RHS; |
500 | return LHS; |
501 | } |
502 | |
503 | inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) { |
504 | RHS |= LHS; |
505 | return std::move(RHS); |
506 | } |
507 | |
508 | inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) { |
509 | LHS ^= RHS; |
510 | return LHS; |
511 | } |
512 | |
513 | inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) { |
514 | RHS ^= LHS; |
515 | return std::move(RHS); |
516 | } |
517 | |
518 | inline raw_ostream &operator<<(raw_ostream &OS, const KnownBits &Known) { |
519 | Known.print(OS); |
520 | return OS; |
521 | } |
522 | |
523 | } // end namespace llvm |
524 | |
525 | #endif |
526 | |