LLVM 20.0.0git
KnownBits.h
Go to the documentation of this file.
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 {
26
27private:
28 // Internal constructor for creating a KnownBits from two APInts.
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 {
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 return Zero.popcount() + One.popcount() == getBitWidth();
52 }
53
54 /// Returns the value when all bits have a known value. This just returns One
55 /// with a protective assertion.
56 const APInt &getConstant() const {
57 assert(isConstant() && "Can only get value when all bits are known");
58 return One;
59 }
60
61 /// Returns true if we don't know any bits.
62 bool isUnknown() const { return Zero.isZero() && One.isZero(); }
63
64 /// Returns true if we don't know the sign bit.
65 bool isSignUnknown() const {
66 return !Zero.isSignBitSet() && !One.isSignBitSet();
67 }
68
69 /// Resets the known state of all bits.
70 void resetAll() {
73 }
74
75 /// Returns true if value is all zero.
76 bool isZero() const { return Zero.isAllOnes(); }
77
78 /// Returns true if value is all one bits.
79 bool isAllOnes() const { return One.isAllOnes(); }
80
81 /// Make all bits known to be zero and discard any previous information.
82 void setAllZero() {
85 }
86
87 /// Make all bits known to be one and discard any previous information.
88 void setAllOnes() {
91 }
92
93 /// Returns true if this value is known to be negative.
94 bool isNegative() const { return One.isSignBitSet(); }
95
96 /// Returns true if this value is known to be non-negative.
97 bool isNonNegative() const { return Zero.isSignBitSet(); }
98
99 /// Returns true if this value is known to be non-zero.
100 bool isNonZero() const { return !One.isZero(); }
101
102 /// Returns true if this value is known to be positive.
103 bool isStrictlyPositive() const {
104 return Zero.isSignBitSet() && !One.isZero();
105 }
106
107 /// Make this value negative.
109 One.setSignBit();
110 }
111
112 /// Make this value non-negative.
115 }
116
117 /// Return the minimal unsigned value possible given these KnownBits.
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.
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.
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.
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 {
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 {
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 {
171 }
172
173 /// Return known bits for an "any" extension or truncation of the value we're
174 /// tracking.
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.
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.
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 /// Concatenate the bits from \p Lo onto the bottom of *this. This is
220 /// equivalent to:
221 /// (this->zext(NewWidth) << Lo.getBitWidth()) | Lo.zext(NewWidth)
222 KnownBits concat(const KnownBits &Lo) const {
223 return KnownBits(Zero.concat(Lo.Zero), One.concat(Lo.One));
224 }
225
226 /// Return KnownBits based on this, but updated given that the underlying
227 /// value is known to be greater than or equal to Val.
228 KnownBits makeGE(const APInt &Val) const;
229
230 /// Returns the minimum number of trailing zero bits.
231 unsigned countMinTrailingZeros() const { return Zero.countr_one(); }
232
233 /// Returns the minimum number of trailing one bits.
234 unsigned countMinTrailingOnes() const { return One.countr_one(); }
235
236 /// Returns the minimum number of leading zero bits.
237 unsigned countMinLeadingZeros() const { return Zero.countl_one(); }
238
239 /// Returns the minimum number of leading one bits.
240 unsigned countMinLeadingOnes() const { return One.countl_one(); }
241
242 /// Returns the number of times the sign bit is replicated into the other
243 /// bits.
244 unsigned countMinSignBits() const {
245 if (isNonNegative())
246 return countMinLeadingZeros();
247 if (isNegative())
248 return countMinLeadingOnes();
249 // Every value has at least 1 sign bit.
250 return 1;
251 }
252
253 /// Returns the maximum number of bits needed to represent all possible
254 /// signed values with these known bits. This is the inverse of the minimum
255 /// number of known sign bits. Examples for bitwidth 5:
256 /// 110?? --> 4
257 /// 0000? --> 2
258 unsigned countMaxSignificantBits() const {
259 return getBitWidth() - countMinSignBits() + 1;
260 }
261
262 /// Returns the maximum number of trailing zero bits possible.
263 unsigned countMaxTrailingZeros() const { return One.countr_zero(); }
264
265 /// Returns the maximum number of trailing one bits possible.
266 unsigned countMaxTrailingOnes() const { return Zero.countr_zero(); }
267
268 /// Returns the maximum number of leading zero bits possible.
269 unsigned countMaxLeadingZeros() const { return One.countl_zero(); }
270
271 /// Returns the maximum number of leading one bits possible.
272 unsigned countMaxLeadingOnes() const { return Zero.countl_zero(); }
273
274 /// Returns the number of bits known to be one.
275 unsigned countMinPopulation() const { return One.popcount(); }
276
277 /// Returns the maximum number of bits that could be one.
278 unsigned countMaxPopulation() const {
279 return getBitWidth() - Zero.popcount();
280 }
281
282 /// Returns the maximum number of bits needed to represent all possible
283 /// unsigned values with these known bits. This is the inverse of the
284 /// minimum number of leading zeros.
285 unsigned countMaxActiveBits() const {
287 }
288
289 /// Create known bits from a known constant.
290 static KnownBits makeConstant(const APInt &C) {
291 return KnownBits(~C, C);
292 }
293
294 /// Returns KnownBits information that is known to be true for both this and
295 /// RHS.
296 ///
297 /// When an operation is known to return one of its operands, this can be used
298 /// to combine information about the known bits of the operands to get the
299 /// information that must be true about the result.
301 return KnownBits(Zero & RHS.Zero, One & RHS.One);
302 }
303
304 /// Returns KnownBits information that is known to be true for either this or
305 /// RHS or both.
306 ///
307 /// This can be used to combine different sources of information about the
308 /// known bits of a single value, e.g. information about the low bits and the
309 /// high bits of the result of a multiplication.
311 return KnownBits(Zero | RHS.Zero, One | RHS.One);
312 }
313
314 /// Return true if LHS and RHS have no common bits set.
315 static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS) {
316 return (LHS.Zero | RHS.Zero).isAllOnes();
317 }
318
319 /// Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
321 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry);
322
323 /// Compute known bits resulting from adding LHS and RHS.
324 static KnownBits computeForAddSub(bool Add, bool NSW, bool NUW,
325 const KnownBits &LHS, const KnownBits &RHS);
326
327 /// Compute known bits results from subtracting RHS from LHS with 1-bit
328 /// Borrow.
330 const KnownBits &Borrow);
331
332 /// Compute knownbits resulting from addition of LHS and RHS.
333 static KnownBits add(const KnownBits &LHS, const KnownBits &RHS,
334 bool NSW = false, bool NUW = false) {
335 return computeForAddSub(/*Add=*/true, NSW, NUW, LHS, RHS);
336 }
337
338 /// Compute knownbits resulting from subtraction of LHS and RHS.
339 static KnownBits sub(const KnownBits &LHS, const KnownBits &RHS,
340 bool NSW = false, bool NUW = false) {
341 return computeForAddSub(/*Add=*/false, NSW, NUW, LHS, RHS);
342 }
343
344 /// Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
345 static KnownBits sadd_sat(const KnownBits &LHS, const KnownBits &RHS);
346
347 /// Compute knownbits resulting from llvm.uadd.sat(LHS, RHS)
348 static KnownBits uadd_sat(const KnownBits &LHS, const KnownBits &RHS);
349
350 /// Compute knownbits resulting from llvm.ssub.sat(LHS, RHS)
351 static KnownBits ssub_sat(const KnownBits &LHS, const KnownBits &RHS);
352
353 /// Compute knownbits resulting from llvm.usub.sat(LHS, RHS)
354 static KnownBits usub_sat(const KnownBits &LHS, const KnownBits &RHS);
355
356 /// Compute knownbits resulting from APIntOps::avgFloorS
357 static KnownBits avgFloorS(const KnownBits &LHS, const KnownBits &RHS);
358
359 /// Compute knownbits resulting from APIntOps::avgFloorU
360 static KnownBits avgFloorU(const KnownBits &LHS, const KnownBits &RHS);
361
362 /// Compute knownbits resulting from APIntOps::avgCeilS
363 static KnownBits avgCeilS(const KnownBits &LHS, const KnownBits &RHS);
364
365 /// Compute knownbits resulting from APIntOps::avgCeilU
366 static KnownBits avgCeilU(const KnownBits &LHS, const KnownBits &RHS);
367
368 /// Compute known bits resulting from multiplying LHS and RHS.
369 static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS,
370 bool NoUndefSelfMultiply = false);
371
372 /// Compute known bits from sign-extended multiply-hi.
373 static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS);
374
375 /// Compute known bits from zero-extended multiply-hi.
376 static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS);
377
378 /// Compute known bits for sdiv(LHS, RHS).
379 static KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS,
380 bool Exact = false);
381
382 /// Compute known bits for udiv(LHS, RHS).
383 static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS,
384 bool Exact = false);
385
386 /// Compute known bits for urem(LHS, RHS).
387 static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS);
388
389 /// Compute known bits for srem(LHS, RHS).
390 static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS);
391
392 /// Compute known bits for umax(LHS, RHS).
393 static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS);
394
395 /// Compute known bits for umin(LHS, RHS).
396 static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS);
397
398 /// Compute known bits for smax(LHS, RHS).
399 static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS);
400
401 /// Compute known bits for smin(LHS, RHS).
402 static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS);
403
404 /// Compute known bits for abdu(LHS, RHS).
405 static KnownBits abdu(const KnownBits &LHS, const KnownBits &RHS);
406
407 /// Compute known bits for abds(LHS, RHS).
409
410 /// Compute known bits for shl(LHS, RHS).
411 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
412 static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS,
413 bool NUW = false, bool NSW = false,
414 bool ShAmtNonZero = false);
415
416 /// Compute known bits for lshr(LHS, RHS).
417 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
418 static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS,
419 bool ShAmtNonZero = false, bool Exact = false);
420
421 /// Compute known bits for ashr(LHS, RHS).
422 /// NOTE: RHS (shift amount) bitwidth doesn't need to be the same as LHS.
423 static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS,
424 bool ShAmtNonZero = false, bool Exact = false);
425
426 /// Determine if these known bits always give the same ICMP_EQ result.
427 static std::optional<bool> eq(const KnownBits &LHS, const KnownBits &RHS);
428
429 /// Determine if these known bits always give the same ICMP_NE result.
430 static std::optional<bool> ne(const KnownBits &LHS, const KnownBits &RHS);
431
432 /// Determine if these known bits always give the same ICMP_UGT result.
433 static std::optional<bool> ugt(const KnownBits &LHS, const KnownBits &RHS);
434
435 /// Determine if these known bits always give the same ICMP_UGE result.
436 static std::optional<bool> uge(const KnownBits &LHS, const KnownBits &RHS);
437
438 /// Determine if these known bits always give the same ICMP_ULT result.
439 static std::optional<bool> ult(const KnownBits &LHS, const KnownBits &RHS);
440
441 /// Determine if these known bits always give the same ICMP_ULE result.
442 static std::optional<bool> ule(const KnownBits &LHS, const KnownBits &RHS);
443
444 /// Determine if these known bits always give the same ICMP_SGT result.
445 static std::optional<bool> sgt(const KnownBits &LHS, const KnownBits &RHS);
446
447 /// Determine if these known bits always give the same ICMP_SGE result.
448 static std::optional<bool> sge(const KnownBits &LHS, const KnownBits &RHS);
449
450 /// Determine if these known bits always give the same ICMP_SLT result.
451 static std::optional<bool> slt(const KnownBits &LHS, const KnownBits &RHS);
452
453 /// Determine if these known bits always give the same ICMP_SLE result.
454 static std::optional<bool> sle(const KnownBits &LHS, const KnownBits &RHS);
455
456 /// Update known bits based on ANDing with RHS.
458
459 /// Update known bits based on ORing with RHS.
461
462 /// Update known bits based on XORing with RHS.
464
465 /// Compute known bits for the absolute value.
466 KnownBits abs(bool IntMinIsPoison = false) const;
467
469 return KnownBits(Zero.byteSwap(), One.byteSwap());
470 }
471
474 }
475
476 /// Compute known bits for X & -X, which has only the lowest bit set of X set.
477 /// The name comes from the X86 BMI instruction
478 KnownBits blsi() const;
479
480 /// Compute known bits for X ^ (X - 1), which has all bits up to and including
481 /// the lowest set bit of X set. The name comes from the X86 BMI instruction.
482 KnownBits blsmsk() const;
483
484 bool operator==(const KnownBits &Other) const {
485 return Zero == Other.Zero && One == Other.One;
486 }
487
488 bool operator!=(const KnownBits &Other) const { return !(*this == Other); }
489
490 void print(raw_ostream &OS) const;
491 void dump() const;
492
493private:
494 // Internal helper for getting the initial KnownBits for an `srem` or `urem`
495 // operation with the low-bits set.
496 static KnownBits remGetLowBits(const KnownBits &LHS, const KnownBits &RHS);
497};
498
500 LHS &= RHS;
501 return LHS;
502}
503
505 RHS &= LHS;
506 return std::move(RHS);
507}
508
510 LHS |= RHS;
511 return LHS;
512}
513
515 RHS |= LHS;
516 return std::move(RHS);
517}
518
520 LHS ^= RHS;
521 return LHS;
522}
523
525 RHS ^= LHS;
526 return std::move(RHS);
527}
528
530 Known.print(OS);
531 return OS;
532}
533
534} // end namespace llvm
535
536#endif
This file implements a class to represent arbitrary precision integral constant values and operations...
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:78
APInt zext(unsigned width) const
Zero extend to a new width.
Definition: APInt.cpp:981
unsigned popcount() const
Count the number of bits set.
Definition: APInt.h:1629
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
Definition: APInt.h:1366
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:906
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:351
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:360
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1320
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition: APInt.h:1448
APInt concat(const APInt &NewLSB) const
Concatenate the bits from "NewLSB" onto the bottom of *this.
Definition: APInt.h:927
bool intersects(const APInt &RHS) const
This operation tests if there are any pairs of corresponding bits between this APInt and RHS that are...
Definition: APInt.h:1229
void clearAllBits()
Set every bit to 0.
Definition: APInt.h:1377
APInt reverseBits() const
Definition: APInt.cpp:737
unsigned countr_zero() const
Count the number of trailing zero bits.
Definition: APInt.h:1598
unsigned countl_zero() const
The APInt version of std::countl_zero.
Definition: APInt.h:1557
unsigned countl_one() const
Count the number of leading one bits.
Definition: APInt.h:1574
void insertBits(const APInt &SubBits, unsigned bitPosition)
Insert the bits from a smaller APInt starting at bitPosition.
Definition: APInt.cpp:368
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1299
APInt sext(unsigned width) const
Sign extend to a new width.
Definition: APInt.cpp:954
APInt byteSwap() const
Definition: APInt.cpp:715
bool isSignBitSet() const
Determine if sign bit of this APInt is set.
Definition: APInt.h:321
APInt extractBits(unsigned numBits, unsigned bitPosition) const
Return an APInt with the extracted bits [bitPosition,bitPosition+numBits).
Definition: APInt.cpp:453
unsigned countr_one() const
Count the number of trailing one bits.
Definition: APInt.h:1615
bool isSignBitClear() const
Determine if sign bit of this APInt is clear.
Definition: APInt.h:328
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
APInt operator&(APInt a, const APInt &b)
Definition: APInt.h:2072
APInt operator^(APInt a, const APInt &b)
Definition: APInt.h:2112
@ Other
Any other memory.
@ Add
Sum of integers.
raw_ostream & operator<<(raw_ostream &OS, const APFixedPoint &FX)
Definition: APFixedPoint.h:293
constexpr unsigned BitWidth
Definition: BitmaskEnum.h:191
OutputIt move(R &&Range, OutputIt Out)
Provide wrappers to std::move which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1849
APInt operator|(APInt a, const APInt &b)
Definition: APInt.h:2092
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
Definition: KnownBits.h:290
static KnownBits sadd_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
Definition: KnownBits.cpp:753
unsigned countMaxTrailingOnes() const
Returns the maximum number of trailing one bits possible.
Definition: KnownBits.h:266
static std::optional< bool > eq(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_EQ result.
Definition: KnownBits.cpp:488
KnownBits anyextOrTrunc(unsigned BitWidth) const
Return known bits for an "any" extension or truncation of the value we're tracking.
Definition: KnownBits.h:175
KnownBits sextInReg(unsigned SrcBitWidth) const
Return known bits for a in-register sign extension of the value we're tracking.
Definition: KnownBits.cpp:149
static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from zero-extended multiply-hi.
Definition: KnownBits.cpp:902
unsigned countMinSignBits() const
Returns the number of times the sign bit is replicated into the other bits.
Definition: KnownBits.h:244
static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smax(LHS, RHS).
Definition: KnownBits.cpp:202
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:97
bool isZero() const
Returns true if value is all zero.
Definition: KnownBits.h:76
KnownBits blsi() const
Compute known bits for X & -X, which has only the lowest bit set of X set.
Definition: KnownBits.cpp:1109
void makeNonNegative()
Make this value non-negative.
Definition: KnownBits.h:113
static KnownBits usub_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.usub.sat(LHS, RHS)
Definition: KnownBits.cpp:762
unsigned countMinLeadingOnes() const
Returns the minimum number of leading one bits.
Definition: KnownBits.h:240
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:231
static KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
Definition: KnownBits.cpp:428
static KnownBits ssub_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.ssub.sat(LHS, RHS)
Definition: KnownBits.cpp:756
static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for urem(LHS, RHS).
Definition: KnownBits.cpp:1042
bool isUnknown() const
Returns true if we don't know any bits.
Definition: KnownBits.h:62
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:263
static std::optional< bool > ne(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_NE result.
Definition: KnownBits.cpp:496
KnownBits makeGE(const APInt &Val) const
Return KnownBits based on this, but updated given that the underlying value is known to be greater th...
Definition: KnownBits.cpp:166
APInt getSignedMaxValue() const
Return the maximal signed value possible given these KnownBits.
Definition: KnownBits.h:140
KnownBits blsmsk() const
Compute known bits for X ^ (X - 1), which has all bits up to and including the lowest set bit of X se...
Definition: KnownBits.cpp:1120
void makeNegative()
Make this value negative.
Definition: KnownBits.h:108
KnownBits trunc(unsigned BitWidth) const
Return known bits for a truncation of the value we're tracking.
Definition: KnownBits.h:150
KnownBits byteSwap() const
Definition: KnownBits.h:468
bool hasConflict() const
Returns true if there is conflicting information.
Definition: KnownBits.h:47
static std::optional< bool > sge(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGE result.
Definition: KnownBits.cpp:536
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
Definition: KnownBits.h:278
void setAllZero()
Make all bits known to be zero and discard any previous information.
Definition: KnownBits.h:82
KnownBits reverseBits() const
Definition: KnownBits.h:472
KnownBits & operator|=(const KnownBits &RHS)
Update known bits based on ORing with RHS.
Definition: KnownBits.cpp:1092
void print(raw_ostream &OS) const
Definition: KnownBits.cpp:1130
KnownBits concat(const KnownBits &Lo) const
Concatenate the bits from Lo onto the bottom of *this.
Definition: KnownBits.h:222
unsigned getBitWidth() const
Get the bit width of this value.
Definition: KnownBits.h:40
static KnownBits umax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umax(LHS, RHS).
Definition: KnownBits.cpp:178
KnownBits zext(unsigned BitWidth) const
Return known bits for a zero extension of the value we're tracking.
Definition: KnownBits.h:161
bool isConstant() const
Returns true if we know the value of all bits.
Definition: KnownBits.h:50
void resetAll()
Resets the known state of all bits.
Definition: KnownBits.h:70
KnownBits unionWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for either this or RHS or both.
Definition: KnownBits.h:310
static KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
Definition: KnownBits.cpp:370
bool isSignUnknown() const
Returns true if we don't know the sign bit.
Definition: KnownBits.h:65
bool isNonZero() const
Returns true if this value is known to be non-zero.
Definition: KnownBits.h:100
static KnownBits abdu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for abdu(LHS, RHS).
Definition: KnownBits.cpp:228
bool operator==(const KnownBits &Other) const
Definition: KnownBits.h:484
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
Definition: KnownBits.h:214
unsigned countMaxActiveBits() const
Returns the maximum number of bits needed to represent all possible unsigned values with these known ...
Definition: KnownBits.h:285
static KnownBits avgFloorU(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from APIntOps::avgFloorU.
Definition: KnownBits.cpp:782
KnownBits intersectWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for both this and RHS.
Definition: KnownBits.h:300
KnownBits sext(unsigned BitWidth) const
Return known bits for a sign extension of the value we're tracking.
Definition: KnownBits.h:169
unsigned countMinTrailingOnes() const
Returns the minimum number of trailing one bits.
Definition: KnownBits.h:234
static KnownBits computeForSubBorrow(const KnownBits &LHS, KnownBits RHS, const KnownBits &Borrow)
Compute known bits results from subtracting RHS from LHS with 1-bit Borrow.
Definition: KnownBits.cpp:137
static KnownBits add(const KnownBits &LHS, const KnownBits &RHS, bool NSW=false, bool NUW=false)
Compute knownbits resulting from addition of LHS and RHS.
Definition: KnownBits.h:333
KnownBits zextOrTrunc(unsigned BitWidth) const
Return known bits for a zero extension or truncation of the value we're tracking.
Definition: KnownBits.h:185
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:237
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition: KnownBits.h:134
KnownBits()=default
static KnownBits abds(KnownBits LHS, KnownBits RHS)
Compute known bits for abds(LHS, RHS).
Definition: KnownBits.cpp:247
static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smin(LHS, RHS).
Definition: KnownBits.cpp:215
KnownBits & operator&=(const KnownBits &RHS)
Update known bits based on ANDing with RHS.
Definition: KnownBits.cpp:1084
static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from sign-extended multiply-hi.
Definition: KnownBits.cpp:894
static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for srem(LHS, RHS).
Definition: KnownBits.cpp:1059
static std::optional< bool > ugt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_UGT result.
Definition: KnownBits.cpp:502
static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for udiv(LHS, RHS).
Definition: KnownBits.cpp:1002
static std::optional< bool > slt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLT result.
Definition: KnownBits.cpp:542
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
Definition: KnownBits.h:118
static KnownBits computeForAddSub(bool Add, bool NSW, bool NUW, const KnownBits &LHS, const KnownBits &RHS)
Compute known bits resulting from adding LHS and RHS.
Definition: KnownBits.cpp:51
void dump() const
Definition: KnownBits.cpp:1144
bool isStrictlyPositive() const
Returns true if this value is known to be positive.
Definition: KnownBits.h:103
static KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for sdiv(LHS, RHS).
Definition: KnownBits.cpp:946
static std::optional< bool > ult(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_ULT result.
Definition: KnownBits.cpp:518
static KnownBits avgFloorS(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from APIntOps::avgFloorS.
Definition: KnownBits.cpp:777
bool operator!=(const KnownBits &Other) const
Definition: KnownBits.h:488
static std::optional< bool > ule(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_ULE result.
Definition: KnownBits.cpp:522
static bool haveNoCommonBitsSet(const KnownBits &LHS, const KnownBits &RHS)
Return true if LHS and RHS have no common bits set.
Definition: KnownBits.h:315
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:94
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry)
Compute known bits resulting from adding LHS, RHS and a 1-bit Carry.
Definition: KnownBits.cpp:44
static KnownBits sub(const KnownBits &LHS, const KnownBits &RHS, bool NSW=false, bool NUW=false)
Compute knownbits resulting from subtraction of LHS and RHS.
Definition: KnownBits.h:339
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition: KnownBits.h:269
void setAllOnes()
Make all bits known to be one and discard any previous information.
Definition: KnownBits.h:88
void insertBits(const KnownBits &SubBits, unsigned BitPosition)
Insert the bits from a smaller known bits starting at bitPosition.
Definition: KnownBits.h:208
static KnownBits avgCeilU(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from APIntOps::avgCeilU.
Definition: KnownBits.cpp:792
static KnownBits uadd_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.uadd.sat(LHS, RHS)
Definition: KnownBits.cpp:759
static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
Definition: KnownBits.cpp:797
KnownBits anyext(unsigned BitWidth) const
Return known bits for an "any" extension of the value we're tracking, where we don't know anything ab...
Definition: KnownBits.h:156
KnownBits abs(bool IntMinIsPoison=false) const
Compute known bits for the absolute value.
Definition: KnownBits.cpp:550
static std::optional< bool > sle(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLE result.
Definition: KnownBits.cpp:546
unsigned countMaxSignificantBits() const
Returns the maximum number of bits needed to represent all possible signed values with these known bi...
Definition: KnownBits.h:258
static std::optional< bool > sgt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGT result.
Definition: KnownBits.cpp:526
unsigned countMinPopulation() const
Returns the number of bits known to be one.
Definition: KnownBits.h:275
static std::optional< bool > uge(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_UGE result.
Definition: KnownBits.cpp:512
KnownBits(unsigned BitWidth)
Create a known bits object of BitWidth bits initialized to unknown.
Definition: KnownBits.h:37
unsigned countMaxLeadingOnes() const
Returns the maximum number of leading one bits possible.
Definition: KnownBits.h:272
APInt getSignedMinValue() const
Return the minimal signed value possible given these KnownBits.
Definition: KnownBits.h:124
KnownBits & operator^=(const KnownBits &RHS)
Update known bits based on XORing with RHS.
Definition: KnownBits.cpp:1100
static KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
Definition: KnownBits.cpp:285
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).
Definition: KnownBits.cpp:196
bool isAllOnes() const
Returns true if value is all one bits.
Definition: KnownBits.h:79
KnownBits sextOrTrunc(unsigned BitWidth) const
Return known bits for a sign extension or truncation of the value we're tracking.
Definition: KnownBits.h:195
static KnownBits avgCeilS(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from APIntOps::avgCeilS.
Definition: KnownBits.cpp:787
const APInt & getConstant() const
Returns the value when all bits have a known value.
Definition: KnownBits.h:56