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
20namespace llvm {
21
22// Struct for tracking the known zeros and ones of a value.
23struct KnownBits {
24 APInt Zero;
25 APInt One;
26
27private:
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
32public:
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 extractBits(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
482private:
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
488inline KnownBits operator&(KnownBits LHS, const KnownBits &RHS) {
489 LHS &= RHS;
490 return LHS;
491}
492
493inline KnownBits operator&(const KnownBits &LHS, KnownBits &&RHS) {
494 RHS &= LHS;
495 return std::move(RHS);
496}
497
498inline KnownBits operator|(KnownBits LHS, const KnownBits &RHS) {
499 LHS |= RHS;
500 return LHS;
501}
502
503inline KnownBits operator|(const KnownBits &LHS, KnownBits &&RHS) {
504 RHS |= LHS;
505 return std::move(RHS);
506}
507
508inline KnownBits operator^(KnownBits LHS, const KnownBits &RHS) {
509 LHS ^= RHS;
510 return LHS;
511}
512
513inline KnownBits operator^(const KnownBits &LHS, KnownBits &&RHS) {
514 RHS ^= LHS;
515 return std::move(RHS);
516}
517
518inline 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

source code of llvm/include/llvm/Support/KnownBits.h