LLVM 19.0.0git
KnownBits.cpp
Go to the documentation of this file.
1//===-- KnownBits.cpp - Stores known zeros/ones ---------------------------===//
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
15#include "llvm/Support/Debug.h"
17#include <cassert>
18
19using namespace llvm;
20
22 const KnownBits &LHS, const KnownBits &RHS,
23 bool CarryZero, bool CarryOne) {
24 assert(!(CarryZero && CarryOne) &&
25 "Carry can't be zero and one at the same time");
26
27 APInt PossibleSumZero = LHS.getMaxValue() + RHS.getMaxValue() + !CarryZero;
28 APInt PossibleSumOne = LHS.getMinValue() + RHS.getMinValue() + CarryOne;
29
30 // Compute known bits of the carry.
31 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
32 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
33
34 // Compute set of known bits (where all three relevant bits are known).
35 APInt LHSKnownUnion = LHS.Zero | LHS.One;
36 APInt RHSKnownUnion = RHS.Zero | RHS.One;
37 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;
38 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;
39
40 assert((PossibleSumZero & Known) == (PossibleSumOne & Known) &&
41 "known bits of sum differ");
42
43 // Compute known bits of the result.
44 KnownBits KnownOut;
45 KnownOut.Zero = ~std::move(PossibleSumZero) & Known;
46 KnownOut.One = std::move(PossibleSumOne) & Known;
47 return KnownOut;
48}
49
51 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {
52 assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit");
53 return ::computeForAddCarry(
54 LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());
55}
56
57KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, bool NUW,
58 const KnownBits &LHS,
59 const KnownBits &RHS) {
60 unsigned BitWidth = LHS.getBitWidth();
61 KnownBits KnownOut(BitWidth);
62 // This can be a relatively expensive helper, so optimistically save some
63 // work.
64 if (LHS.isUnknown() && RHS.isUnknown())
65 return KnownOut;
66
67 if (!LHS.isUnknown() && !RHS.isUnknown()) {
68 if (Add) {
69 // Sum = LHS + RHS + 0
70 KnownOut = ::computeForAddCarry(LHS, RHS, /*CarryZero=*/true,
71 /*CarryOne=*/false);
72 } else {
73 // Sum = LHS + ~RHS + 1
74 KnownBits NotRHS = RHS;
75 std::swap(NotRHS.Zero, NotRHS.One);
76 KnownOut = ::computeForAddCarry(LHS, NotRHS, /*CarryZero=*/false,
77 /*CarryOne=*/true);
78 }
79 }
80
81 // Handle add/sub given nsw and/or nuw.
82 if (NUW) {
83 if (Add) {
84 // (add nuw X, Y)
85 APInt MinVal = LHS.getMinValue().uadd_sat(RHS.getMinValue());
86 // None of the adds can end up overflowing, so min consecutive highbits
87 // in minimum possible of X + Y must all remain set.
88 if (NSW) {
89 unsigned NumBits = MinVal.trunc(BitWidth - 1).countl_one();
90 // If we have NSW as well, we also know we can't overflow the signbit so
91 // can start counting from 1 bit back.
92 KnownOut.One.setBits(BitWidth - 1 - NumBits, BitWidth - 1);
93 }
94 KnownOut.One.setHighBits(MinVal.countl_one());
95 } else {
96 // (sub nuw X, Y)
97 APInt MaxVal = LHS.getMaxValue().usub_sat(RHS.getMinValue());
98 // None of the subs can overflow at any point, so any common high bits
99 // will subtract away and result in zeros.
100 if (NSW) {
101 // If we have NSW as well, we also know we can't overflow the signbit so
102 // can start counting from 1 bit back.
103 unsigned NumBits = MaxVal.trunc(BitWidth - 1).countl_zero();
104 KnownOut.Zero.setBits(BitWidth - 1 - NumBits, BitWidth - 1);
105 }
106 KnownOut.Zero.setHighBits(MaxVal.countl_zero());
107 }
108 }
109
110 if (NSW) {
111 APInt MinVal;
112 APInt MaxVal;
113 if (Add) {
114 // (add nsw X, Y)
115 MinVal = LHS.getSignedMinValue().sadd_sat(RHS.getSignedMinValue());
116 MaxVal = LHS.getSignedMaxValue().sadd_sat(RHS.getSignedMaxValue());
117 } else {
118 // (sub nsw X, Y)
119 MinVal = LHS.getSignedMinValue().ssub_sat(RHS.getSignedMaxValue());
120 MaxVal = LHS.getSignedMaxValue().ssub_sat(RHS.getSignedMinValue());
121 }
122 if (MinVal.isNonNegative()) {
123 // If min is non-negative, result will always be non-neg (can't overflow
124 // around).
125 unsigned NumBits = MinVal.trunc(BitWidth - 1).countl_one();
126 KnownOut.One.setBits(BitWidth - 1 - NumBits, BitWidth - 1);
127 KnownOut.Zero.setSignBit();
128 }
129 if (MaxVal.isNegative()) {
130 // If max is negative, result will always be neg (can't overflow around).
131 unsigned NumBits = MaxVal.trunc(BitWidth - 1).countl_zero();
132 KnownOut.Zero.setBits(BitWidth - 1 - NumBits, BitWidth - 1);
133 KnownOut.One.setSignBit();
134 }
135 }
136
137 // Just return 0 if the nsw/nuw is violated and we have poison.
138 if (KnownOut.hasConflict())
139 KnownOut.setAllZero();
140 return KnownOut;
141}
142
144 const KnownBits &Borrow) {
145 assert(Borrow.getBitWidth() == 1 && "Borrow must be 1-bit");
146
147 // LHS - RHS = LHS + ~RHS + 1
148 // Carry 1 - Borrow in ::computeForAddCarry
149 std::swap(RHS.Zero, RHS.One);
150 return ::computeForAddCarry(LHS, RHS,
151 /*CarryZero=*/Borrow.One.getBoolValue(),
152 /*CarryOne=*/Borrow.Zero.getBoolValue());
153}
154
155KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const {
156 unsigned BitWidth = getBitWidth();
157 assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth &&
158 "Illegal sext-in-register");
159
160 if (SrcBitWidth == BitWidth)
161 return *this;
162
163 unsigned ExtBits = BitWidth - SrcBitWidth;
164 KnownBits Result;
165 Result.One = One << ExtBits;
166 Result.Zero = Zero << ExtBits;
167 Result.One.ashrInPlace(ExtBits);
168 Result.Zero.ashrInPlace(ExtBits);
169 return Result;
170}
171
173 // Count the number of leading bit positions where our underlying value is
174 // known to be less than or equal to Val.
175 unsigned N = (Zero | Val).countl_one();
176
177 // For each of those bit positions, if Val has a 1 in that bit then our
178 // underlying value must also have a 1.
179 APInt MaskedVal(Val);
180 MaskedVal.clearLowBits(getBitWidth() - N);
181 return KnownBits(Zero, One | MaskedVal);
182}
183
185 // If we can prove that LHS >= RHS then use LHS as the result. Likewise for
186 // RHS. Ideally our caller would already have spotted these cases and
187 // optimized away the umax operation, but we handle them here for
188 // completeness.
189 if (LHS.getMinValue().uge(RHS.getMaxValue()))
190 return LHS;
191 if (RHS.getMinValue().uge(LHS.getMaxValue()))
192 return RHS;
193
194 // If the result of the umax is LHS then it must be greater than or equal to
195 // the minimum possible value of RHS. Likewise for RHS. Any known bits that
196 // are common to these two values are also known in the result.
197 KnownBits L = LHS.makeGE(RHS.getMinValue());
198 KnownBits R = RHS.makeGE(LHS.getMinValue());
199 return L.intersectWith(R);
200}
201
203 // Flip the range of values: [0, 0xFFFFFFFF] <-> [0xFFFFFFFF, 0]
204 auto Flip = [](const KnownBits &Val) { return KnownBits(Val.One, Val.Zero); };
205 return Flip(umax(Flip(LHS), Flip(RHS)));
206}
207
209 // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0, 0xFFFFFFFF]
210 auto Flip = [](const KnownBits &Val) {
211 unsigned SignBitPosition = Val.getBitWidth() - 1;
212 APInt Zero = Val.Zero;
213 APInt One = Val.One;
214 Zero.setBitVal(SignBitPosition, Val.One[SignBitPosition]);
215 One.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
216 return KnownBits(Zero, One);
217 };
218 return Flip(umax(Flip(LHS), Flip(RHS)));
219}
220
222 // Flip the range of values: [-0x80000000, 0x7FFFFFFF] <-> [0xFFFFFFFF, 0]
223 auto Flip = [](const KnownBits &Val) {
224 unsigned SignBitPosition = Val.getBitWidth() - 1;
225 APInt Zero = Val.One;
226 APInt One = Val.Zero;
227 Zero.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
228 One.setBitVal(SignBitPosition, Val.One[SignBitPosition]);
229 return KnownBits(Zero, One);
230 };
231 return Flip(umax(Flip(LHS), Flip(RHS)));
232}
233
235 // abdu(LHS,RHS) = sub(umax(LHS,RHS), umin(LHS,RHS)).
236 KnownBits UMaxValue = umax(LHS, RHS);
237 KnownBits UMinValue = umin(LHS, RHS);
238 KnownBits MinMaxDiff = computeForAddSub(/*Add=*/false, /*NSW=*/false,
239 /*NUW=*/true, UMaxValue, UMinValue);
240
241 // find the common bits between sub(LHS,RHS) and sub(RHS,LHS).
242 KnownBits Diff0 =
243 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, LHS, RHS);
244 KnownBits Diff1 =
245 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, RHS, LHS);
246 KnownBits SubDiff = Diff0.intersectWith(Diff1);
247
248 KnownBits KnownAbsDiff = MinMaxDiff.unionWith(SubDiff);
249 assert(!KnownAbsDiff.hasConflict() && "Bad Output");
250 return KnownAbsDiff;
251}
252
254 // abds(LHS,RHS) = sub(smax(LHS,RHS), smin(LHS,RHS)).
255 KnownBits SMaxValue = smax(LHS, RHS);
256 KnownBits SMinValue = smin(LHS, RHS);
257 KnownBits MinMaxDiff = computeForAddSub(/*Add=*/false, /*NSW=*/false,
258 /*NUW=*/false, SMaxValue, SMinValue);
259
260 // find the common bits between sub(LHS,RHS) and sub(RHS,LHS).
261 KnownBits Diff0 =
262 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, LHS, RHS);
263 KnownBits Diff1 =
264 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, RHS, LHS);
265 KnownBits SubDiff = Diff0.intersectWith(Diff1);
266
267 KnownBits KnownAbsDiff = MinMaxDiff.unionWith(SubDiff);
268 assert(!KnownAbsDiff.hasConflict() && "Bad Output");
269 return KnownAbsDiff;
270}
271
272static unsigned getMaxShiftAmount(const APInt &MaxValue, unsigned BitWidth) {
274 return MaxValue.extractBitsAsZExtValue(Log2_32(BitWidth), 0);
275 // This is only an approximate upper bound.
276 return MaxValue.getLimitedValue(BitWidth - 1);
277}
278
279KnownBits KnownBits::shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW,
280 bool NSW, bool ShAmtNonZero) {
281 unsigned BitWidth = LHS.getBitWidth();
282 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
283 KnownBits Known;
284 bool ShiftedOutZero, ShiftedOutOne;
285 Known.Zero = LHS.Zero.ushl_ov(ShiftAmt, ShiftedOutZero);
286 Known.Zero.setLowBits(ShiftAmt);
287 Known.One = LHS.One.ushl_ov(ShiftAmt, ShiftedOutOne);
288
289 // All cases returning poison have been handled by MaxShiftAmount already.
290 if (NSW) {
291 if (NUW && ShiftAmt != 0)
292 // NUW means we can assume anything shifted out was a zero.
293 ShiftedOutZero = true;
294
295 if (ShiftedOutZero)
296 Known.makeNonNegative();
297 else if (ShiftedOutOne)
298 Known.makeNegative();
299 }
300 return Known;
301 };
302
303 // Fast path for a common case when LHS is completely unknown.
304 KnownBits Known(BitWidth);
305 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);
306 if (MinShiftAmount == 0 && ShAmtNonZero)
307 MinShiftAmount = 1;
308 if (LHS.isUnknown()) {
309 Known.Zero.setLowBits(MinShiftAmount);
310 if (NUW && NSW && MinShiftAmount != 0)
311 Known.makeNonNegative();
312 return Known;
313 }
314
315 // Determine maximum shift amount, taking NUW/NSW flags into account.
316 APInt MaxValue = RHS.getMaxValue();
317 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);
318 if (NUW && NSW)
319 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros() - 1);
320 if (NUW)
321 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros());
322 if (NSW)
323 MaxShiftAmount = std::min(
324 MaxShiftAmount,
325 std::max(LHS.countMaxLeadingZeros(), LHS.countMaxLeadingOnes()) - 1);
326
327 // Fast path for common case where the shift amount is unknown.
328 if (MinShiftAmount == 0 && MaxShiftAmount == BitWidth - 1 &&
330 Known.Zero.setLowBits(LHS.countMinTrailingZeros());
331 if (LHS.isAllOnes())
332 Known.One.setSignBit();
333 if (NSW) {
334 if (LHS.isNonNegative())
335 Known.makeNonNegative();
336 if (LHS.isNegative())
337 Known.makeNegative();
338 }
339 return Known;
340 }
341
342 // Find the common bits from all possible shifts.
343 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();
344 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();
345 Known.Zero.setAllBits();
346 Known.One.setAllBits();
347 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
348 ++ShiftAmt) {
349 // Skip if the shift amount is impossible.
350 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
351 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
352 continue;
353 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
354 if (Known.isUnknown())
355 break;
356 }
357
358 // All shift amounts may result in poison.
359 if (Known.hasConflict())
360 Known.setAllZero();
361 return Known;
362}
363
365 bool ShAmtNonZero, bool Exact) {
366 unsigned BitWidth = LHS.getBitWidth();
367 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
368 KnownBits Known = LHS;
369 Known.Zero.lshrInPlace(ShiftAmt);
370 Known.One.lshrInPlace(ShiftAmt);
371 // High bits are known zero.
372 Known.Zero.setHighBits(ShiftAmt);
373 return Known;
374 };
375
376 // Fast path for a common case when LHS is completely unknown.
377 KnownBits Known(BitWidth);
378 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);
379 if (MinShiftAmount == 0 && ShAmtNonZero)
380 MinShiftAmount = 1;
381 if (LHS.isUnknown()) {
382 Known.Zero.setHighBits(MinShiftAmount);
383 return Known;
384 }
385
386 // Find the common bits from all possible shifts.
387 APInt MaxValue = RHS.getMaxValue();
388 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);
389
390 // If exact, bound MaxShiftAmount to first known 1 in LHS.
391 if (Exact) {
392 unsigned FirstOne = LHS.countMaxTrailingZeros();
393 if (FirstOne < MinShiftAmount) {
394 // Always poison. Return zero because we don't like returning conflict.
395 Known.setAllZero();
396 return Known;
397 }
398 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);
399 }
400
401 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();
402 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();
403 Known.Zero.setAllBits();
404 Known.One.setAllBits();
405 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
406 ++ShiftAmt) {
407 // Skip if the shift amount is impossible.
408 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
409 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
410 continue;
411 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
412 if (Known.isUnknown())
413 break;
414 }
415
416 // All shift amounts may result in poison.
417 if (Known.hasConflict())
418 Known.setAllZero();
419 return Known;
420}
421
423 bool ShAmtNonZero, bool Exact) {
424 unsigned BitWidth = LHS.getBitWidth();
425 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
426 KnownBits Known = LHS;
427 Known.Zero.ashrInPlace(ShiftAmt);
428 Known.One.ashrInPlace(ShiftAmt);
429 return Known;
430 };
431
432 // Fast path for a common case when LHS is completely unknown.
433 KnownBits Known(BitWidth);
434 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);
435 if (MinShiftAmount == 0 && ShAmtNonZero)
436 MinShiftAmount = 1;
437 if (LHS.isUnknown()) {
438 if (MinShiftAmount == BitWidth) {
439 // Always poison. Return zero because we don't like returning conflict.
440 Known.setAllZero();
441 return Known;
442 }
443 return Known;
444 }
445
446 // Find the common bits from all possible shifts.
447 APInt MaxValue = RHS.getMaxValue();
448 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);
449
450 // If exact, bound MaxShiftAmount to first known 1 in LHS.
451 if (Exact) {
452 unsigned FirstOne = LHS.countMaxTrailingZeros();
453 if (FirstOne < MinShiftAmount) {
454 // Always poison. Return zero because we don't like returning conflict.
455 Known.setAllZero();
456 return Known;
457 }
458 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);
459 }
460
461 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();
462 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();
463 Known.Zero.setAllBits();
464 Known.One.setAllBits();
465 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
466 ++ShiftAmt) {
467 // Skip if the shift amount is impossible.
468 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
469 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
470 continue;
471 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
472 if (Known.isUnknown())
473 break;
474 }
475
476 // All shift amounts may result in poison.
477 if (Known.hasConflict())
478 Known.setAllZero();
479 return Known;
480}
481
482std::optional<bool> KnownBits::eq(const KnownBits &LHS, const KnownBits &RHS) {
483 if (LHS.isConstant() && RHS.isConstant())
484 return std::optional<bool>(LHS.getConstant() == RHS.getConstant());
485 if (LHS.One.intersects(RHS.Zero) || RHS.One.intersects(LHS.Zero))
486 return std::optional<bool>(false);
487 return std::nullopt;
488}
489
490std::optional<bool> KnownBits::ne(const KnownBits &LHS, const KnownBits &RHS) {
491 if (std::optional<bool> KnownEQ = eq(LHS, RHS))
492 return std::optional<bool>(!*KnownEQ);
493 return std::nullopt;
494}
495
496std::optional<bool> KnownBits::ugt(const KnownBits &LHS, const KnownBits &RHS) {
497 // LHS >u RHS -> false if umax(LHS) <= umax(RHS)
498 if (LHS.getMaxValue().ule(RHS.getMinValue()))
499 return std::optional<bool>(false);
500 // LHS >u RHS -> true if umin(LHS) > umax(RHS)
501 if (LHS.getMinValue().ugt(RHS.getMaxValue()))
502 return std::optional<bool>(true);
503 return std::nullopt;
504}
505
506std::optional<bool> KnownBits::uge(const KnownBits &LHS, const KnownBits &RHS) {
507 if (std::optional<bool> IsUGT = ugt(RHS, LHS))
508 return std::optional<bool>(!*IsUGT);
509 return std::nullopt;
510}
511
512std::optional<bool> KnownBits::ult(const KnownBits &LHS, const KnownBits &RHS) {
513 return ugt(RHS, LHS);
514}
515
516std::optional<bool> KnownBits::ule(const KnownBits &LHS, const KnownBits &RHS) {
517 return uge(RHS, LHS);
518}
519
520std::optional<bool> KnownBits::sgt(const KnownBits &LHS, const KnownBits &RHS) {
521 // LHS >s RHS -> false if smax(LHS) <= smax(RHS)
522 if (LHS.getSignedMaxValue().sle(RHS.getSignedMinValue()))
523 return std::optional<bool>(false);
524 // LHS >s RHS -> true if smin(LHS) > smax(RHS)
525 if (LHS.getSignedMinValue().sgt(RHS.getSignedMaxValue()))
526 return std::optional<bool>(true);
527 return std::nullopt;
528}
529
530std::optional<bool> KnownBits::sge(const KnownBits &LHS, const KnownBits &RHS) {
531 if (std::optional<bool> KnownSGT = sgt(RHS, LHS))
532 return std::optional<bool>(!*KnownSGT);
533 return std::nullopt;
534}
535
536std::optional<bool> KnownBits::slt(const KnownBits &LHS, const KnownBits &RHS) {
537 return sgt(RHS, LHS);
538}
539
540std::optional<bool> KnownBits::sle(const KnownBits &LHS, const KnownBits &RHS) {
541 return sge(RHS, LHS);
542}
543
544KnownBits KnownBits::abs(bool IntMinIsPoison) const {
545 // If the source's MSB is zero then we know the rest of the bits already.
546 if (isNonNegative())
547 return *this;
548
549 // Absolute value preserves trailing zero count.
550 KnownBits KnownAbs(getBitWidth());
551
552 // If the input is negative, then abs(x) == -x.
553 if (isNegative()) {
554 KnownBits Tmp = *this;
555 // Special case for IntMinIsPoison. We know the sign bit is set and we know
556 // all the rest of the bits except one to be zero. Since we have
557 // IntMinIsPoison, that final bit MUST be a one, as otherwise the input is
558 // INT_MIN.
559 if (IntMinIsPoison && (Zero.popcount() + 2) == getBitWidth())
561
562 KnownAbs = computeForAddSub(
563 /*Add*/ false, IntMinIsPoison, /*NUW=*/false,
565
566 // One more special case for IntMinIsPoison. If we don't know any ones other
567 // than the signbit, we know for certain that all the unknowns can't be
568 // zero. So if we know high zero bits, but have unknown low bits, we know
569 // for certain those high-zero bits will end up as one. This is because,
570 // the low bits can't be all zeros, so the +1 in (~x + 1) cannot carry up
571 // to the high bits. If we know a known INT_MIN input skip this. The result
572 // is poison anyways.
573 if (IntMinIsPoison && Tmp.countMinPopulation() == 1 &&
574 Tmp.countMaxPopulation() != 1) {
575 Tmp.One.clearSignBit();
576 Tmp.Zero.setSignBit();
577 KnownAbs.One.setBits(getBitWidth() - Tmp.countMinLeadingZeros(),
578 getBitWidth() - 1);
579 }
580
581 } else {
582 unsigned MaxTZ = countMaxTrailingZeros();
583 unsigned MinTZ = countMinTrailingZeros();
584
585 KnownAbs.Zero.setLowBits(MinTZ);
586 // If we know the lowest set 1, then preserve it.
587 if (MaxTZ == MinTZ && MaxTZ < getBitWidth())
588 KnownAbs.One.setBit(MaxTZ);
589
590 // We only know that the absolute values's MSB will be zero if INT_MIN is
591 // poison, or there is a set bit that isn't the sign bit (otherwise it could
592 // be INT_MIN).
593 if (IntMinIsPoison || (!One.isZero() && !One.isMinSignedValue())) {
594 KnownAbs.One.clearSignBit();
595 KnownAbs.Zero.setSignBit();
596 }
597 }
598
599 assert(!KnownAbs.hasConflict() && "Bad Output");
600 return KnownAbs;
601}
602
604 const KnownBits &LHS,
605 const KnownBits &RHS) {
606 assert(!LHS.hasConflict() && !RHS.hasConflict() && "Bad inputs");
607 // We don't see NSW even for sadd/ssub as we want to check if the result has
608 // signed overflow.
609 KnownBits Res =
610 KnownBits::computeForAddSub(Add, /*NSW=*/false, /*NUW=*/false, LHS, RHS);
611 unsigned BitWidth = Res.getBitWidth();
612 auto SignBitKnown = [&](const KnownBits &K) {
613 return K.Zero[BitWidth - 1] || K.One[BitWidth - 1];
614 };
615 std::optional<bool> Overflow;
616
617 if (Signed) {
618 // If we can actually detect overflow do so. Otherwise leave Overflow as
619 // nullopt (we assume it may have happened).
620 if (SignBitKnown(LHS) && SignBitKnown(RHS) && SignBitKnown(Res)) {
621 if (Add) {
622 // sadd.sat
623 Overflow = (LHS.isNonNegative() == RHS.isNonNegative() &&
624 Res.isNonNegative() != LHS.isNonNegative());
625 } else {
626 // ssub.sat
627 Overflow = (LHS.isNonNegative() != RHS.isNonNegative() &&
628 Res.isNonNegative() != LHS.isNonNegative());
629 }
630 }
631 } else if (Add) {
632 // uadd.sat
633 bool Of;
634 (void)LHS.getMaxValue().uadd_ov(RHS.getMaxValue(), Of);
635 if (!Of) {
636 Overflow = false;
637 } else {
638 (void)LHS.getMinValue().uadd_ov(RHS.getMinValue(), Of);
639 if (Of)
640 Overflow = true;
641 }
642 } else {
643 // usub.sat
644 bool Of;
645 (void)LHS.getMinValue().usub_ov(RHS.getMaxValue(), Of);
646 if (!Of) {
647 Overflow = false;
648 } else {
649 (void)LHS.getMaxValue().usub_ov(RHS.getMinValue(), Of);
650 if (Of)
651 Overflow = true;
652 }
653 }
654
655 if (Signed) {
656 if (Add) {
657 if (LHS.isNonNegative() && RHS.isNonNegative()) {
658 // Pos + Pos -> Pos
659 Res.One.clearSignBit();
660 Res.Zero.setSignBit();
661 }
662 if (LHS.isNegative() && RHS.isNegative()) {
663 // Neg + Neg -> Neg
664 Res.One.setSignBit();
665 Res.Zero.clearSignBit();
666 }
667 } else {
668 if (LHS.isNegative() && RHS.isNonNegative()) {
669 // Neg - Pos -> Neg
670 Res.One.setSignBit();
671 Res.Zero.clearSignBit();
672 } else if (LHS.isNonNegative() && RHS.isNegative()) {
673 // Pos - Neg -> Pos
674 Res.One.clearSignBit();
675 Res.Zero.setSignBit();
676 }
677 }
678 } else {
679 // Add: Leading ones of either operand are preserved.
680 // Sub: Leading zeros of LHS and leading ones of RHS are preserved
681 // as leading zeros in the result.
682 unsigned LeadingKnown;
683 if (Add)
684 LeadingKnown =
685 std::max(LHS.countMinLeadingOnes(), RHS.countMinLeadingOnes());
686 else
687 LeadingKnown =
688 std::max(LHS.countMinLeadingZeros(), RHS.countMinLeadingOnes());
689
690 // We select between the operation result and all-ones/zero
691 // respectively, so we can preserve known ones/zeros.
692 APInt Mask = APInt::getHighBitsSet(BitWidth, LeadingKnown);
693 if (Add) {
694 Res.One |= Mask;
695 Res.Zero &= ~Mask;
696 } else {
697 Res.Zero |= Mask;
698 Res.One &= ~Mask;
699 }
700 }
701
702 if (Overflow) {
703 // We know whether or not we overflowed.
704 if (!(*Overflow)) {
705 // No overflow.
706 assert(!Res.hasConflict() && "Bad Output");
707 return Res;
708 }
709
710 // We overflowed
711 APInt C;
712 if (Signed) {
713 // sadd.sat / ssub.sat
714 assert(SignBitKnown(LHS) &&
715 "We somehow know overflow without knowing input sign");
716 C = LHS.isNegative() ? APInt::getSignedMinValue(BitWidth)
718 } else if (Add) {
719 // uadd.sat
721 } else {
722 // uadd.sat
724 }
725
726 Res.One = C;
727 Res.Zero = ~C;
728 assert(!Res.hasConflict() && "Bad Output");
729 return Res;
730 }
731
732 // We don't know if we overflowed.
733 if (Signed) {
734 // sadd.sat/ssub.sat
735 // We can keep our information about the sign bits.
736 Res.Zero.clearLowBits(BitWidth - 1);
737 Res.One.clearLowBits(BitWidth - 1);
738 } else if (Add) {
739 // uadd.sat
740 // We need to clear all the known zeros as we can only use the leading ones.
741 Res.Zero.clearAllBits();
742 } else {
743 // usub.sat
744 // We need to clear all the known ones as we can only use the leading zero.
745 Res.One.clearAllBits();
746 }
747
748 assert(!Res.hasConflict() && "Bad Output");
749 return Res;
750}
751
753 return computeForSatAddSub(/*Add*/ true, /*Signed*/ true, LHS, RHS);
754}
756 return computeForSatAddSub(/*Add*/ false, /*Signed*/ true, LHS, RHS);
757}
759 return computeForSatAddSub(/*Add*/ true, /*Signed*/ false, LHS, RHS);
760}
762 return computeForSatAddSub(/*Add*/ false, /*Signed*/ false, LHS, RHS);
763}
764
766 bool NoUndefSelfMultiply) {
767 unsigned BitWidth = LHS.getBitWidth();
768 assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
769 !RHS.hasConflict() && "Operand mismatch");
770 assert((!NoUndefSelfMultiply || LHS == RHS) &&
771 "Self multiplication knownbits mismatch");
772
773 // Compute the high known-0 bits by multiplying the unsigned max of each side.
774 // Conservatively, M active bits * N active bits results in M + N bits in the
775 // result. But if we know a value is a power-of-2 for example, then this
776 // computes one more leading zero.
777 // TODO: This could be generalized to number of sign bits (negative numbers).
778 APInt UMaxLHS = LHS.getMaxValue();
779 APInt UMaxRHS = RHS.getMaxValue();
780
781 // For leading zeros in the result to be valid, the unsigned max product must
782 // fit in the bitwidth (it must not overflow).
783 bool HasOverflow;
784 APInt UMaxResult = UMaxLHS.umul_ov(UMaxRHS, HasOverflow);
785 unsigned LeadZ = HasOverflow ? 0 : UMaxResult.countl_zero();
786
787 // The result of the bottom bits of an integer multiply can be
788 // inferred by looking at the bottom bits of both operands and
789 // multiplying them together.
790 // We can infer at least the minimum number of known trailing bits
791 // of both operands. Depending on number of trailing zeros, we can
792 // infer more bits, because (a*b) <=> ((a/m) * (b/n)) * (m*n) assuming
793 // a and b are divisible by m and n respectively.
794 // We then calculate how many of those bits are inferrable and set
795 // the output. For example, the i8 mul:
796 // a = XXXX1100 (12)
797 // b = XXXX1110 (14)
798 // We know the bottom 3 bits are zero since the first can be divided by
799 // 4 and the second by 2, thus having ((12/4) * (14/2)) * (2*4).
800 // Applying the multiplication to the trimmed arguments gets:
801 // XX11 (3)
802 // X111 (7)
803 // -------
804 // XX11
805 // XX11
806 // XX11
807 // XX11
808 // -------
809 // XXXXX01
810 // Which allows us to infer the 2 LSBs. Since we're multiplying the result
811 // by 8, the bottom 3 bits will be 0, so we can infer a total of 5 bits.
812 // The proof for this can be described as:
813 // Pre: (C1 >= 0) && (C1 < (1 << C5)) && (C2 >= 0) && (C2 < (1 << C6)) &&
814 // (C7 == (1 << (umin(countTrailingZeros(C1), C5) +
815 // umin(countTrailingZeros(C2), C6) +
816 // umin(C5 - umin(countTrailingZeros(C1), C5),
817 // C6 - umin(countTrailingZeros(C2), C6)))) - 1)
818 // %aa = shl i8 %a, C5
819 // %bb = shl i8 %b, C6
820 // %aaa = or i8 %aa, C1
821 // %bbb = or i8 %bb, C2
822 // %mul = mul i8 %aaa, %bbb
823 // %mask = and i8 %mul, C7
824 // =>
825 // %mask = i8 ((C1*C2)&C7)
826 // Where C5, C6 describe the known bits of %a, %b
827 // C1, C2 describe the known bottom bits of %a, %b.
828 // C7 describes the mask of the known bits of the result.
829 const APInt &Bottom0 = LHS.One;
830 const APInt &Bottom1 = RHS.One;
831
832 // How many times we'd be able to divide each argument by 2 (shr by 1).
833 // This gives us the number of trailing zeros on the multiplication result.
834 unsigned TrailBitsKnown0 = (LHS.Zero | LHS.One).countr_one();
835 unsigned TrailBitsKnown1 = (RHS.Zero | RHS.One).countr_one();
836 unsigned TrailZero0 = LHS.countMinTrailingZeros();
837 unsigned TrailZero1 = RHS.countMinTrailingZeros();
838 unsigned TrailZ = TrailZero0 + TrailZero1;
839
840 // Figure out the fewest known-bits operand.
841 unsigned SmallestOperand =
842 std::min(TrailBitsKnown0 - TrailZero0, TrailBitsKnown1 - TrailZero1);
843 unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ, BitWidth);
844
845 APInt BottomKnown =
846 Bottom0.getLoBits(TrailBitsKnown0) * Bottom1.getLoBits(TrailBitsKnown1);
847
848 KnownBits Res(BitWidth);
849 Res.Zero.setHighBits(LeadZ);
850 Res.Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);
851 Res.One = BottomKnown.getLoBits(ResultBitsKnown);
852
853 // If we're self-multiplying then bit[1] is guaranteed to be zero.
854 if (NoUndefSelfMultiply && BitWidth > 1) {
855 assert(Res.One[1] == 0 &&
856 "Self-multiplication failed Quadratic Reciprocity!");
857 Res.Zero.setBit(1);
858 }
859
860 return Res;
861}
862
864 unsigned BitWidth = LHS.getBitWidth();
865 assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
866 !RHS.hasConflict() && "Operand mismatch");
867 KnownBits WideLHS = LHS.sext(2 * BitWidth);
868 KnownBits WideRHS = RHS.sext(2 * BitWidth);
869 return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);
870}
871
873 unsigned BitWidth = LHS.getBitWidth();
874 assert(BitWidth == RHS.getBitWidth() && !LHS.hasConflict() &&
875 !RHS.hasConflict() && "Operand mismatch");
876 KnownBits WideLHS = LHS.zext(2 * BitWidth);
877 KnownBits WideRHS = RHS.zext(2 * BitWidth);
878 return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);
879}
880
882 const KnownBits &RHS, bool Exact) {
883
884 if (!Exact)
885 return Known;
886
887 // If LHS is Odd, the result is Odd no matter what.
888 // Odd / Odd -> Odd
889 // Odd / Even -> Impossible (because its exact division)
890 if (LHS.One[0])
891 Known.One.setBit(0);
892
893 int MinTZ =
894 (int)LHS.countMinTrailingZeros() - (int)RHS.countMaxTrailingZeros();
895 int MaxTZ =
896 (int)LHS.countMaxTrailingZeros() - (int)RHS.countMinTrailingZeros();
897 if (MinTZ >= 0) {
898 // Result has at least MinTZ trailing zeros.
899 Known.Zero.setLowBits(MinTZ);
900 if (MinTZ == MaxTZ) {
901 // Result has exactly MinTZ trailing zeros.
902 Known.One.setBit(MinTZ);
903 }
904 } else if (MaxTZ < 0) {
905 // Poison Result
906 Known.setAllZero();
907 }
908
909 // In the KnownBits exhaustive tests, we have poison inputs for exact values
910 // a LOT. If we have a conflict, just return all zeros.
911 if (Known.hasConflict())
912 Known.setAllZero();
913
914 return Known;
915}
916
918 bool Exact) {
919 // Equivalent of `udiv`. We must have caught this before it was folded.
920 if (LHS.isNonNegative() && RHS.isNonNegative())
921 return udiv(LHS, RHS, Exact);
922
923 unsigned BitWidth = LHS.getBitWidth();
924 assert(!LHS.hasConflict() && !RHS.hasConflict() && "Bad inputs");
925 KnownBits Known(BitWidth);
926
927 if (LHS.isZero() || RHS.isZero()) {
928 // Result is either known Zero or UB. Return Zero either way.
929 // Checking this earlier saves us a lot of special cases later on.
930 Known.setAllZero();
931 return Known;
932 }
933
934 std::optional<APInt> Res;
935 if (LHS.isNegative() && RHS.isNegative()) {
936 // Result non-negative.
937 APInt Denom = RHS.getSignedMaxValue();
938 APInt Num = LHS.getSignedMinValue();
939 // INT_MIN/-1 would be a poison result (impossible). Estimate the division
940 // as signed max (we will only set sign bit in the result).
941 Res = (Num.isMinSignedValue() && Denom.isAllOnes())
943 : Num.sdiv(Denom);
944 } else if (LHS.isNegative() && RHS.isNonNegative()) {
945 // Result is negative if Exact OR -LHS u>= RHS.
946 if (Exact || (-LHS.getSignedMaxValue()).uge(RHS.getSignedMaxValue())) {
947 APInt Denom = RHS.getSignedMinValue();
948 APInt Num = LHS.getSignedMinValue();
949 Res = Denom.isZero() ? Num : Num.sdiv(Denom);
950 }
951 } else if (LHS.isStrictlyPositive() && RHS.isNegative()) {
952 // Result is negative if Exact OR LHS u>= -RHS.
953 if (Exact || LHS.getSignedMinValue().uge(-RHS.getSignedMinValue())) {
954 APInt Denom = RHS.getSignedMaxValue();
955 APInt Num = LHS.getSignedMaxValue();
956 Res = Num.sdiv(Denom);
957 }
958 }
959
960 if (Res) {
961 if (Res->isNonNegative()) {
962 unsigned LeadZ = Res->countLeadingZeros();
963 Known.Zero.setHighBits(LeadZ);
964 } else {
965 unsigned LeadO = Res->countLeadingOnes();
966 Known.One.setHighBits(LeadO);
967 }
968 }
969
970 Known = divComputeLowBit(Known, LHS, RHS, Exact);
971
972 assert(!Known.hasConflict() && "Bad Output");
973 return Known;
974}
975
977 bool Exact) {
978 unsigned BitWidth = LHS.getBitWidth();
979 assert(!LHS.hasConflict() && !RHS.hasConflict());
980 KnownBits Known(BitWidth);
981
982 if (LHS.isZero() || RHS.isZero()) {
983 // Result is either known Zero or UB. Return Zero either way.
984 // Checking this earlier saves us a lot of special cases later on.
985 Known.setAllZero();
986 return Known;
987 }
988
989 // We can figure out the minimum number of upper zero bits by doing
990 // MaxNumerator / MinDenominator. If the Numerator gets smaller or Denominator
991 // gets larger, the number of upper zero bits increases.
992 APInt MinDenom = RHS.getMinValue();
993 APInt MaxNum = LHS.getMaxValue();
994 APInt MaxRes = MinDenom.isZero() ? MaxNum : MaxNum.udiv(MinDenom);
995
996 unsigned LeadZ = MaxRes.countLeadingZeros();
997
998 Known.Zero.setHighBits(LeadZ);
999 Known = divComputeLowBit(Known, LHS, RHS, Exact);
1000
1001 assert(!Known.hasConflict() && "Bad Output");
1002 return Known;
1003}
1004
1005KnownBits KnownBits::remGetLowBits(const KnownBits &LHS, const KnownBits &RHS) {
1006 unsigned BitWidth = LHS.getBitWidth();
1007 if (!RHS.isZero() && RHS.Zero[0]) {
1008 // rem X, Y where Y[0:N] is zero will preserve X[0:N] in the result.
1009 unsigned RHSZeros = RHS.countMinTrailingZeros();
1010 APInt Mask = APInt::getLowBitsSet(BitWidth, RHSZeros);
1011 APInt OnesMask = LHS.One & Mask;
1012 APInt ZerosMask = LHS.Zero & Mask;
1013 return KnownBits(ZerosMask, OnesMask);
1014 }
1015 return KnownBits(BitWidth);
1016}
1017
1019 assert(!LHS.hasConflict() && !RHS.hasConflict());
1020
1021 KnownBits Known = remGetLowBits(LHS, RHS);
1022 if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) {
1023 // NB: Low bits set in `remGetLowBits`.
1024 APInt HighBits = ~(RHS.getConstant() - 1);
1025 Known.Zero |= HighBits;
1026 return Known;
1027 }
1028
1029 // Since the result is less than or equal to either operand, any leading
1030 // zero bits in either operand must also exist in the result.
1031 uint32_t Leaders =
1032 std::max(LHS.countMinLeadingZeros(), RHS.countMinLeadingZeros());
1033 Known.Zero.setHighBits(Leaders);
1034 return Known;
1035}
1036
1038 assert(!LHS.hasConflict() && !RHS.hasConflict());
1039
1040 KnownBits Known = remGetLowBits(LHS, RHS);
1041 if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) {
1042 // NB: Low bits are set in `remGetLowBits`.
1043 APInt LowBits = RHS.getConstant() - 1;
1044 // If the first operand is non-negative or has all low bits zero, then
1045 // the upper bits are all zero.
1046 if (LHS.isNonNegative() || LowBits.isSubsetOf(LHS.Zero))
1047 Known.Zero |= ~LowBits;
1048
1049 // If the first operand is negative and not all low bits are zero, then
1050 // the upper bits are all one.
1051 if (LHS.isNegative() && LowBits.intersects(LHS.One))
1052 Known.One |= ~LowBits;
1053 return Known;
1054 }
1055
1056 // The sign bit is the LHS's sign bit, except when the result of the
1057 // remainder is zero. The magnitude of the result should be less than or
1058 // equal to the magnitude of the LHS. Therefore any leading zeros that exist
1059 // in the left hand side must also exist in the result.
1060 Known.Zero.setHighBits(LHS.countMinLeadingZeros());
1061 return Known;
1062}
1063
1065 // Result bit is 0 if either operand bit is 0.
1066 Zero |= RHS.Zero;
1067 // Result bit is 1 if both operand bits are 1.
1068 One &= RHS.One;
1069 return *this;
1070}
1071
1073 // Result bit is 0 if both operand bits are 0.
1074 Zero &= RHS.Zero;
1075 // Result bit is 1 if either operand bit is 1.
1076 One |= RHS.One;
1077 return *this;
1078}
1079
1081 // Result bit is 0 if both operand bits are 0 or both are 1.
1082 APInt Z = (Zero & RHS.Zero) | (One & RHS.One);
1083 // Result bit is 1 if one operand bit is 0 and the other is 1.
1084 One = (Zero & RHS.One) | (One & RHS.Zero);
1085 Zero = std::move(Z);
1086 return *this;
1087}
1088
1090 unsigned BitWidth = getBitWidth();
1091 KnownBits Known(Zero, APInt(BitWidth, 0));
1092 unsigned Max = countMaxTrailingZeros();
1093 Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));
1094 unsigned Min = countMinTrailingZeros();
1095 if (Max == Min && Max < BitWidth)
1096 Known.One.setBit(Max);
1097 return Known;
1098}
1099
1101 unsigned BitWidth = getBitWidth();
1102 KnownBits Known(BitWidth);
1103 unsigned Max = countMaxTrailingZeros();
1104 Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));
1105 unsigned Min = countMinTrailingZeros();
1106 Known.One.setLowBits(std::min(Min + 1, BitWidth));
1107 return Known;
1108}
1109
1111 unsigned BitWidth = getBitWidth();
1112 for (unsigned I = 0; I < BitWidth; ++I) {
1113 unsigned N = BitWidth - I - 1;
1114 if (Zero[N] && One[N])
1115 OS << "!";
1116 else if (Zero[N])
1117 OS << "0";
1118 else if (One[N])
1119 OS << "1";
1120 else
1121 OS << "?";
1122 }
1123}
1124void KnownBits::dump() const {
1125 print(dbgs());
1126 dbgs() << "\n";
1127}
static KnownBits computeForSatAddSub(bool Add, bool Signed, const KnownBits &LHS, const KnownBits &RHS)
Definition: KnownBits.cpp:603
static KnownBits divComputeLowBit(KnownBits Known, const KnownBits &LHS, const KnownBits &RHS, bool Exact)
Definition: KnownBits.cpp:881
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
Definition: KnownBits.cpp:21
static unsigned getMaxShiftAmount(const APInt &MaxValue, unsigned BitWidth)
Definition: KnownBits.cpp:272
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * RHS
Value * LHS
Class for arbitrary precision integers.
Definition: APInt.h:76
APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition: APInt.cpp:1977
APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition: APInt.cpp:1579
APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
Definition: APInt.cpp:613
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition: APInt.h:401
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
Definition: APInt.h:1370
unsigned popcount() const
Count the number of bits set.
Definition: APInt.h:1620
void setBitsFrom(unsigned loBit)
Set the top bits starting from loBit.
Definition: APInt.h:1364
uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const
Definition: APInt.cpp:489
APInt trunc(unsigned width) const
Truncate to new width.
Definition: APInt.cpp:906
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition: APInt.h:184
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
Definition: APInt.h:1308
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition: APInt.h:349
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition: APInt.h:358
void setSignBit()
Set the sign bit to 1.
Definition: APInt.h:1318
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition: APInt.h:187
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition: APInt.h:194
bool isNegative() const
Determine sign of this APInt.
Definition: APInt.h:307
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:1227
APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition: APInt.cpp:1650
void clearAllBits()
Set every bit to 0.
Definition: APInt.h:1375
void ashrInPlace(unsigned ShiftAmt)
Arithmetic right-shift this APInt by ShiftAmt in place.
Definition: APInt.h:812
unsigned countl_zero() const
The APInt version of std::countl_zero.
Definition: APInt.h:1548
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition: APInt.h:197
unsigned countLeadingZeros() const
Definition: APInt.h:1556
unsigned countl_one() const
Count the number of leading one bits.
Definition: APInt.h:1565
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
Definition: APInt.h:1395
uint64_t getLimitedValue(uint64_t Limit=UINT64_MAX) const
If this value is smaller than the specified limit, return it, otherwise return the limit value.
Definition: APInt.h:453
void setAllBits()
Set every bit to 1.
Definition: APInt.h:1297
bool getBoolValue() const
Convert APInt to a boolean value.
Definition: APInt.h:449
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition: APInt.h:312
void setBits(unsigned loBit, unsigned hiBit)
Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
Definition: APInt.h:1345
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition: APInt.h:1235
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition: APInt.h:284
static APInt getHighBitsSet(unsigned numBits, unsigned hiBitsSet)
Constructs an APInt value that has the top hiBitsSet bits set.
Definition: APInt.h:274
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
Definition: APInt.h:1367
void lshrInPlace(unsigned ShiftAmt)
Logical right-shift this APInt by ShiftAmt in place.
Definition: APInt.h:836
void setBitVal(unsigned BitPosition, bool BitValue)
Set a given bit to a given value.
Definition: APInt.h:1321
void clearSignBit()
Set the sign bit to 0.
Definition: APInt.h:1402
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
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
Definition: bit.h:307
unsigned Log2_32(uint32_t Value)
Return the floor log base 2 of the specified value, -1 if the value is zero.
Definition: MathExtras.h:313
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition: MathExtras.h:264
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
int countl_one(T Value)
Count the number of ones from the most significant bit to the first zero bit.
Definition: bit.h:294
@ Add
Sum of integers.
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:1858
Implement std::hash so that hash_code can be used in STL containers.
Definition: BitVector.h:858
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860
#define N
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
Definition: KnownBits.h:297
static KnownBits sadd_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
Definition: KnownBits.cpp:752
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:482
KnownBits sextInReg(unsigned SrcBitWidth) const
Return known bits for a in-register sign extension of the value we're tracking.
Definition: KnownBits.cpp:155
static KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from zero-extended multiply-hi.
Definition: KnownBits.cpp:872
static KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smax(LHS, RHS).
Definition: KnownBits.cpp:208
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition: KnownBits.h:104
KnownBits blsi() const
Compute known bits for X & -X, which has only the lowest bit set of X set.
Definition: KnownBits.cpp:1089
void makeNonNegative()
Make this value non-negative.
Definition: KnownBits.h:120
static KnownBits usub_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.usub.sat(LHS, RHS)
Definition: KnownBits.cpp:761
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition: KnownBits.h:238
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:422
static KnownBits ssub_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.ssub.sat(LHS, RHS)
Definition: KnownBits.cpp:755
static KnownBits urem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for urem(LHS, RHS).
Definition: KnownBits.cpp:1018
bool isUnknown() const
Returns true if we don't know any bits.
Definition: KnownBits.h:63
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition: KnownBits.h:270
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:490
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:172
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:1100
void makeNegative()
Make this value negative.
Definition: KnownBits.h:115
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:530
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
Definition: KnownBits.h:285
void setAllZero()
Make all bits known to be zero and discard any previous information.
Definition: KnownBits.h:89
KnownBits & operator|=(const KnownBits &RHS)
Update known bits based on ORing with RHS.
Definition: KnownBits.cpp:1072
void print(raw_ostream &OS) const
Definition: KnownBits.cpp:1110
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:184
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:317
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:364
static KnownBits abdu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for abdu(LHS, RHS).
Definition: KnownBits.cpp:234
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
Definition: KnownBits.h:221
KnownBits intersectWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for both this and RHS.
Definition: KnownBits.h:307
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:143
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition: KnownBits.h:244
KnownBits()=default
static KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smin(LHS, RHS).
Definition: KnownBits.cpp:221
KnownBits & operator&=(const KnownBits &RHS)
Update known bits based on ANDing with RHS.
Definition: KnownBits.cpp:1064
static KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from sign-extended multiply-hi.
Definition: KnownBits.cpp:863
static KnownBits srem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for srem(LHS, RHS).
Definition: KnownBits.cpp:1037
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:496
static KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for udiv(LHS, RHS).
Definition: KnownBits.cpp:976
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:536
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:57
void dump() const
Definition: KnownBits.cpp:1124
static KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for sdiv(LHS, RHS).
Definition: KnownBits.cpp:917
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:512
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:516
bool isNegative() const
Returns true if this value is known to be negative.
Definition: KnownBits.h:101
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:50
static KnownBits uadd_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.uadd.sat(LHS, RHS)
Definition: KnownBits.cpp:758
static KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
Definition: KnownBits.cpp:765
KnownBits abs(bool IntMinIsPoison=false) const
Compute known bits for the absolute value.
Definition: KnownBits.cpp:544
static KnownBits abds(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for abds(LHS, RHS).
Definition: KnownBits.cpp:253
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:540
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:520
unsigned countMinPopulation() const
Returns the number of bits known to be one.
Definition: KnownBits.h:282
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:506
KnownBits & operator^=(const KnownBits &RHS)
Update known bits based on XORing with RHS.
Definition: KnownBits.cpp:1080
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:279
static KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).
Definition: KnownBits.cpp:202