LLVM 24.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/ADT/Sequence.h"
16#include "llvm/ADT/bit.h"
17#include "llvm/Support/Debug.h"
19#include <cassert>
20
21using namespace llvm;
22
23KnownBits KnownBits::flipSignBit(const KnownBits &Val) {
24 unsigned SignBitPosition = Val.getBitWidth() - 1;
25 APInt Zero = Val.Zero;
26 APInt One = Val.One;
27 Zero.setBitVal(SignBitPosition, Val.One[SignBitPosition]);
28 One.setBitVal(SignBitPosition, Val.Zero[SignBitPosition]);
29 return KnownBits(Zero, One);
30}
31
33 bool CarryZero, bool CarryOne) {
34
35 APInt PossibleSumZero = LHS.getMaxValue() + RHS.getMaxValue() + !CarryZero;
36 APInt PossibleSumOne = LHS.getMinValue() + RHS.getMinValue() + CarryOne;
37
38 // Compute known bits of the carry.
39 APInt CarryKnownZero = ~(PossibleSumZero ^ LHS.Zero ^ RHS.Zero);
40 APInt CarryKnownOne = PossibleSumOne ^ LHS.One ^ RHS.One;
41
42 // Compute set of known bits (where all three relevant bits are known).
43 APInt LHSKnownUnion = LHS.Zero | LHS.One;
44 APInt RHSKnownUnion = RHS.Zero | RHS.One;
45 APInt CarryKnownUnion = std::move(CarryKnownZero) | CarryKnownOne;
46 APInt Known = std::move(LHSKnownUnion) & RHSKnownUnion & CarryKnownUnion;
47
48 // Compute known bits of the result.
49 KnownBits KnownOut;
50 KnownOut.Zero = ~std::move(PossibleSumZero) & Known;
51 KnownOut.One = std::move(PossibleSumOne) & Known;
52 return KnownOut;
53}
54
56 const KnownBits &LHS, const KnownBits &RHS, const KnownBits &Carry) {
57 assert(Carry.getBitWidth() == 1 && "Carry must be 1-bit");
58 return ::computeForAddCarry(
59 LHS, RHS, Carry.Zero.getBoolValue(), Carry.One.getBoolValue());
60}
61
62KnownBits KnownBits::computeForAddSub(bool Add, bool NSW, bool NUW,
63 const KnownBits &LHS,
64 const KnownBits &RHS) {
65 unsigned BitWidth = LHS.getBitWidth();
66 KnownBits KnownOut(BitWidth);
67 // This can be a relatively expensive helper, so optimistically save some
68 // work.
69 if (LHS.isUnknown() && RHS.isUnknown())
70 return KnownOut;
71
72 if (!LHS.isUnknown() && !RHS.isUnknown()) {
73 if (Add) {
74 // Sum = LHS + RHS + 0
75 KnownOut = ::computeForAddCarry(LHS, RHS, /*CarryZero=*/true,
76 /*CarryOne=*/false);
77 } else {
78 // Sum = LHS + ~RHS + 1
79 KnownBits NotRHS = RHS;
80 std::swap(NotRHS.Zero, NotRHS.One);
81 KnownOut = ::computeForAddCarry(LHS, NotRHS, /*CarryZero=*/false,
82 /*CarryOne=*/true);
83 }
84 }
85
86 // Handle add/sub given nsw and/or nuw.
87 if (NUW) {
88 if (Add) {
89 // (add nuw X, Y)
90 APInt MinVal = LHS.getMinValue().uadd_sat(RHS.getMinValue());
91 // None of the adds can end up overflowing, so min consecutive highbits
92 // in minimum possible of X + Y must all remain set.
93 if (NSW) {
94 unsigned NumBits = MinVal.trunc(BitWidth - 1).countl_one();
95 // If we have NSW as well, we also know we can't overflow the signbit so
96 // can start counting from 1 bit back.
97 KnownOut.One.setBits(BitWidth - 1 - NumBits, BitWidth - 1);
98 }
99 KnownOut.One.setHighBits(MinVal.countl_one());
100 } else {
101 // (sub nuw X, Y)
102 APInt MaxVal = LHS.getMaxValue().usub_sat(RHS.getMinValue());
103 // None of the subs can overflow at any point, so any common high bits
104 // will subtract away and result in zeros.
105 if (NSW) {
106 // If we have NSW as well, we also know we can't overflow the signbit so
107 // can start counting from 1 bit back.
108 unsigned NumBits = MaxVal.trunc(BitWidth - 1).countl_zero();
109 KnownOut.Zero.setBits(BitWidth - 1 - NumBits, BitWidth - 1);
110 }
111 KnownOut.Zero.setHighBits(MaxVal.countl_zero());
112 }
113 }
114
115 if (NSW) {
116 APInt MinVal;
117 APInt MaxVal;
118 if (Add) {
119 // (add nsw X, Y)
120 MinVal = LHS.getSignedMinValue().sadd_sat(RHS.getSignedMinValue());
121 MaxVal = LHS.getSignedMaxValue().sadd_sat(RHS.getSignedMaxValue());
122 } else {
123 // (sub nsw X, Y)
124 MinVal = LHS.getSignedMinValue().ssub_sat(RHS.getSignedMaxValue());
125 MaxVal = LHS.getSignedMaxValue().ssub_sat(RHS.getSignedMinValue());
126 }
127 if (MinVal.isNonNegative()) {
128 // If min is non-negative, result will always be non-neg (can't overflow
129 // around).
130 unsigned NumBits = MinVal.trunc(BitWidth - 1).countl_one();
131 KnownOut.One.setBits(BitWidth - 1 - NumBits, BitWidth - 1);
132 KnownOut.Zero.setSignBit();
133 }
134 if (MaxVal.isNegative()) {
135 // If max is negative, result will always be neg (can't overflow around).
136 unsigned NumBits = MaxVal.trunc(BitWidth - 1).countl_zero();
137 KnownOut.Zero.setBits(BitWidth - 1 - NumBits, BitWidth - 1);
138 KnownOut.One.setSignBit();
139 }
140 }
141
142 // Just return 0 if the nsw/nuw is violated and we have poison.
143 if (KnownOut.hasConflict())
144 KnownOut.setAllZero();
145 return KnownOut;
146}
147
148KnownBits KnownBits::computeForSubBorrow(const KnownBits &LHS, KnownBits RHS,
149 const KnownBits &Borrow) {
150 assert(Borrow.getBitWidth() == 1 && "Borrow must be 1-bit");
151
152 // LHS - RHS = LHS + ~RHS + 1
153 // Carry 1 - Borrow in ::computeForAddCarry
154 std::swap(RHS.Zero, RHS.One);
155 return ::computeForAddCarry(LHS, RHS,
156 /*CarryZero=*/Borrow.One.getBoolValue(),
157 /*CarryOne=*/Borrow.Zero.getBoolValue());
158}
159
160KnownBits KnownBits::truncSSat(unsigned BitWidth) const {
161 unsigned InputBits = getBitWidth();
162 APInt MinInRange = APInt::getSignedMinValue(BitWidth).sext(InputBits);
163 APInt MaxInRange = APInt::getSignedMaxValue(BitWidth).sext(InputBits);
164 APInt InputMin = getSignedMinValue();
165 APInt InputMax = getSignedMaxValue();
166 KnownBits Known(BitWidth);
167
168 // Case 1: All values fit - just truncate
169 if (InputMin.sge(MinInRange) && InputMax.sle(MaxInRange)) {
171 }
172 // Case 2: All saturate to min
173 else if (InputMax.slt(MinInRange)) {
175 }
176 // Case 3: All saturate to max
177 else if (InputMin.sgt(MaxInRange)) {
179 }
180 // Case 4: All non-negative, some fit, some saturate to max
181 else if (InputMin.isNonNegative()) {
182 // Output: truncated OR max saturation
183 // Max saturation has only sign bit as 0
184 Known.Zero = APInt(BitWidth, 0);
185 Known.Zero.setBit(BitWidth - 1); // Sign bit always 0
186 // Max saturation has all lower bits as 1, so preserve InputOneLower
187 Known.One = One.trunc(BitWidth);
188 Known.One.clearBit(BitWidth - 1); // Sign bit is 0, not 1
189 }
190 // Case 5: All negative, some fit, some saturate to min
191 else if (InputMax.isNegative()) {
192 // Output: truncated OR min saturation
193 // Min saturation has all lower bits as 0, so preserve InputZeroLower
194 Known.Zero = Zero.trunc(BitWidth);
195 Known.Zero.clearBit(BitWidth - 1); // Sign bit is 1, not 0
196 // Min saturation has only sign bit as 1
197 Known.One = APInt(BitWidth, 0);
198 Known.One.setBit(BitWidth - 1); // Sign bit always 1
199 }
200 // Case 6: Mixed positive and negative
201 else {
202 // Output: min saturation, truncated, or max saturation
203 APInt InputZeroLower = Zero.trunc(BitWidth);
204 APInt InputOneLower = One.trunc(BitWidth);
207 KnownBits MinSatKB = KnownBits::makeConstant(MinSat);
208 KnownBits MaxSatKB = KnownBits::makeConstant(MaxSat);
209 if (InputMax.sle(MaxInRange)) {
210 // Positive values fit, only negatives saturate to min
211 Known.Zero = InputZeroLower & MinSatKB.Zero;
212 Known.One = InputOneLower & MinSatKB.One;
213 } else if (InputMin.sge(MinInRange)) {
214 // Negative values fit, only positives saturate to max
215 Known.Zero = InputZeroLower & MaxSatKB.Zero;
216 Known.One = InputOneLower & MaxSatKB.One;
217 } else {
218 // Both positive and negative values might saturate
219 Known.Zero = InputZeroLower & MinSatKB.Zero & MaxSatKB.Zero;
220 Known.One = InputOneLower & MinSatKB.One & MaxSatKB.One;
221 }
222 }
223 return Known;
224}
225
226KnownBits KnownBits::truncSSatU(unsigned BitWidth) const {
227 unsigned InputBits = getBitWidth();
228 APInt MaxInRange = APInt::getAllOnes(BitWidth).zext(InputBits);
229 APInt InputMin = getSignedMinValue();
230 APInt InputMax = getSignedMaxValue();
231 KnownBits Known(BitWidth);
232
233 if (isNegative()) {
234 Known.setAllZero();
235 } else if (InputMin.isNonNegative() && InputMax.ule(MaxInRange)) {
237 } else if (InputMin.isNonNegative() && InputMin.ugt(MaxInRange)) {
238 Known.setAllOnes();
239 } else if (InputMin.isNonNegative()) {
240 // All non-negative but mixed: some fit, some saturate to all-ones
241 // No common zero bits (saturation is all-ones)
242 Known.Zero = APInt(BitWidth, 0);
243 // Common one bits: bits that are 1 in input stay 1
244 Known.One = One.trunc(BitWidth);
245 } else {
246 // Mixed: sign bit unknown
247 if (InputMax.ule(MaxInRange)) {
248 // Positive values all fit (no saturation to all-ones)
249 // Output: all-zeros (negatives) OR truncated (positives)
250 Known.Zero = Zero.trunc(BitWidth);
251 Known.One = APInt(BitWidth, 0);
252 } else {
253 // Positive values might saturate to all-ones
254 // Output: all-zeros OR truncated OR all-ones
255 // No common bits
256 Known.Zero = APInt(BitWidth, 0);
257 Known.One = APInt(BitWidth, 0);
258 }
259 }
260 return Known;
261}
262
263KnownBits KnownBits::truncUSat(unsigned BitWidth) const {
264 unsigned InputBits = getBitWidth();
265 APInt MaxInRange = APInt::getLowBitsSet(InputBits, BitWidth);
266 APInt InputMax = getMaxValue();
267 APInt InputMin = getMinValue();
268 KnownBits Known(BitWidth);
269
270 if (InputMax.ule(MaxInRange)) {
272 } else if (InputMin.ugt(MaxInRange)) {
273 Known.setAllOnes();
274 } else {
275 Known.resetAll();
276 Known.One = One.trunc(BitWidth);
277 }
278 return Known;
279}
280
281KnownBits KnownBits::sextInReg(unsigned SrcBitWidth) const {
282 unsigned BitWidth = getBitWidth();
283 assert(0 < SrcBitWidth && SrcBitWidth <= BitWidth &&
284 "Illegal sext-in-register");
285
286 if (SrcBitWidth == BitWidth)
287 return *this;
288
289 unsigned ExtBits = BitWidth - SrcBitWidth;
290 KnownBits Result;
291 Result.One = One << ExtBits;
292 Result.Zero = Zero << ExtBits;
293 Result.One.ashrInPlace(ExtBits);
294 Result.Zero.ashrInPlace(ExtBits);
295 return Result;
296}
297
298KnownBits KnownBits::makeGE(const APInt &Val) const {
299 // Count the number of leading bit positions where our underlying value is
300 // known to be less than or equal to Val.
301 unsigned N = (Zero | Val).countl_one();
302
303 // For each of those bit positions, if Val has a 1 in that bit then our
304 // underlying value must also have a 1.
305 APInt MaskedVal(Val);
306 MaskedVal.clearLowBits(getBitWidth() - N);
307 return KnownBits(Zero, One | MaskedVal);
308}
309
310KnownBits KnownBits::umax(const KnownBits &LHS, const KnownBits &RHS) {
311 // If we can prove that LHS >= RHS then use LHS as the result. Likewise for
312 // RHS. Ideally our caller would already have spotted these cases and
313 // optimized away the umax operation, but we handle them here for
314 // completeness.
315 if (LHS.getMinValue().uge(RHS.getMaxValue()))
316 return LHS;
317 if (RHS.getMinValue().uge(LHS.getMaxValue()))
318 return RHS;
319
320 // If the result of the umax is LHS then it must be greater than or equal to
321 // the minimum possible value of RHS. Likewise for RHS. Any known bits that
322 // are common to these two values are also known in the result.
323 KnownBits L = LHS.makeGE(RHS.getMinValue());
324 KnownBits R = RHS.makeGE(LHS.getMinValue());
325 return L.intersectWith(R);
326}
327
328KnownBits KnownBits::umin(const KnownBits &LHS, const KnownBits &RHS) {
329 // Flip the range of values: [0, 0xFFFFFFFF] <-> [0xFFFFFFFF, 0]
330 auto Flip = [](const KnownBits &Val) { return KnownBits(Val.One, Val.Zero); };
331 return Flip(umax(Flip(LHS), Flip(RHS)));
332}
333
334KnownBits KnownBits::smax(const KnownBits &LHS, const KnownBits &RHS) {
335 return flipSignBit(umax(flipSignBit(LHS), flipSignBit(RHS)));
336}
337
338KnownBits KnownBits::smin(const KnownBits &LHS, const KnownBits &RHS) {
339 return flipSignBit(umin(flipSignBit(LHS), flipSignBit(RHS)));
340}
341
342KnownBits KnownBits::abdu(const KnownBits &LHS, const KnownBits &RHS) {
343 // If we know which argument is larger, return (sub LHS, RHS) or
344 // (sub RHS, LHS) directly.
345 if (LHS.getMinValue().uge(RHS.getMaxValue()))
346 return computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, LHS,
347 RHS);
348 if (RHS.getMinValue().uge(LHS.getMaxValue()))
349 return computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/false, RHS,
350 LHS);
351
352 // By construction, the subtraction in abdu never has unsigned overflow.
353 // Find the common bits between (sub nuw LHS, RHS) and (sub nuw RHS, LHS).
354 KnownBits Diff0 =
355 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, LHS, RHS);
356 KnownBits Diff1 =
357 computeForAddSub(/*Add=*/false, /*NSW=*/false, /*NUW=*/true, RHS, LHS);
358 return Diff0.intersectWith(Diff1);
359}
360
361KnownBits KnownBits::abds(KnownBits LHS, KnownBits RHS) {
362 // Shift both arguments from the signed range to the unsigned range, e.g. from
363 // [-0x80, 0x7F] to [0, 0xFF].
364 return abdu(flipSignBit(LHS), flipSignBit(RHS));
365}
366
367static unsigned getMaxShiftAmount(const APInt &MaxValue, unsigned BitWidth) {
369 // Clamp to the shift amount's width: a narrower amount is already
370 // < BitWidth, so this stays a valid upper bound.
371 return MaxValue.extractBitsAsZExtValue(
372 std::min(Log2_32(BitWidth), MaxValue.getBitWidth()), 0);
373 // This is only an approximate upper bound.
374 return MaxValue.getLimitedValue(BitWidth - 1);
375}
376
377KnownBits KnownBits::shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW,
378 bool NSW, bool ShAmtNonZero) {
379 unsigned BitWidth = LHS.getBitWidth();
380 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
381 KnownBits Known;
382 bool ShiftedOutZero, ShiftedOutOne;
383 Known.Zero = LHS.Zero.ushl_ov(ShiftAmt, ShiftedOutZero);
384 Known.Zero.setLowBits(ShiftAmt);
385 Known.One = LHS.One.ushl_ov(ShiftAmt, ShiftedOutOne);
386
387 // All cases returning poison have been handled by MaxShiftAmount already.
388 if (NSW) {
389 if (NUW && ShiftAmt != 0)
390 // NUW means we can assume anything shifted out was a zero.
391 ShiftedOutZero = true;
392
393 if (ShiftedOutZero)
394 Known.makeNonNegative();
395 else if (ShiftedOutOne)
396 Known.makeNegative();
397 }
398 return Known;
399 };
400
401 // Fast path for a common case when LHS is completely unknown.
402 KnownBits Known(BitWidth);
403 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);
404 if (MinShiftAmount == 0 && ShAmtNonZero)
405 MinShiftAmount = 1;
406 if (LHS.isUnknown()) {
407 Known.Zero.setLowBits(MinShiftAmount);
408 if (NUW && NSW && MinShiftAmount != 0)
409 Known.makeNonNegative();
410 return Known;
411 }
412
413 // Determine maximum shift amount, taking NUW/NSW flags into account.
414 APInt MaxValue = RHS.getMaxValue();
415 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);
416 if (NUW && NSW)
417 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros() - 1);
418 if (NUW)
419 MaxShiftAmount = std::min(MaxShiftAmount, LHS.countMaxLeadingZeros());
420 if (NSW)
421 MaxShiftAmount = std::min(
422 MaxShiftAmount,
423 std::max(LHS.countMaxLeadingZeros(), LHS.countMaxLeadingOnes()) - 1);
424
425 // Fast path for common case where the shift amount is unknown.
426 if (MinShiftAmount == 0 && MaxShiftAmount == BitWidth - 1 &&
428 Known.Zero.setLowBits(LHS.countMinTrailingZeros());
429 if (LHS.isAllOnes())
430 Known.One.setSignBit();
431 if (NSW) {
432 if (LHS.isNonNegative())
433 Known.makeNonNegative();
434 if (LHS.isNegative())
435 Known.makeNegative();
436 }
437 return Known;
438 }
439
440 // Find the common bits from all possible shifts.
441 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();
442 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();
443 Known.setAllConflict();
444 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
445 ++ShiftAmt) {
446 // Skip if the shift amount is impossible.
447 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
448 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
449 continue;
450 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
451 if (Known.isUnknown())
452 break;
453 }
454
455 // All shift amounts may result in poison.
456 if (Known.hasConflict())
457 Known.setAllZero();
458 return Known;
459}
460
461KnownBits KnownBits::lshr(const KnownBits &LHS, const KnownBits &RHS,
462 bool ShAmtNonZero, bool Exact) {
463 unsigned BitWidth = LHS.getBitWidth();
464 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
465 KnownBits Known = LHS;
466 Known >>= ShiftAmt;
467 // High bits are known zero.
468 Known.Zero.setHighBits(ShiftAmt);
469 return Known;
470 };
471
472 // Fast path for a common case when LHS is completely unknown.
473 KnownBits Known(BitWidth);
474 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);
475 if (MinShiftAmount == 0 && ShAmtNonZero)
476 MinShiftAmount = 1;
477 if (LHS.isUnknown()) {
478 Known.Zero.setHighBits(MinShiftAmount);
479 return Known;
480 }
481
482 // Find the common bits from all possible shifts.
483 APInt MaxValue = RHS.getMaxValue();
484 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);
485
486 // If exact, bound MaxShiftAmount to first known 1 in LHS.
487 if (Exact) {
488 unsigned FirstOne = LHS.countMaxTrailingZeros();
489 if (FirstOne < MinShiftAmount) {
490 // Always poison. Return zero because we don't like returning conflict.
491 Known.setAllZero();
492 return Known;
493 }
494 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);
495 }
496
497 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();
498 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();
499 Known.setAllConflict();
500 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
501 ++ShiftAmt) {
502 // Skip if the shift amount is impossible.
503 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
504 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
505 continue;
506 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
507 if (Known.isUnknown())
508 break;
509 }
510
511 // All shift amounts may result in poison.
512 if (Known.hasConflict())
513 Known.setAllZero();
514 return Known;
515}
516
517KnownBits KnownBits::ashr(const KnownBits &LHS, const KnownBits &RHS,
518 bool ShAmtNonZero, bool Exact) {
519 unsigned BitWidth = LHS.getBitWidth();
520 auto ShiftByConst = [&](const KnownBits &LHS, unsigned ShiftAmt) {
521 KnownBits Known = LHS;
522 Known.Zero.ashrInPlace(ShiftAmt);
523 Known.One.ashrInPlace(ShiftAmt);
524 return Known;
525 };
526
527 // Fast path for a common case when LHS is completely unknown.
528 KnownBits Known(BitWidth);
529 unsigned MinShiftAmount = RHS.getMinValue().getLimitedValue(BitWidth);
530 if (MinShiftAmount == 0 && ShAmtNonZero)
531 MinShiftAmount = 1;
532 if (LHS.isUnknown()) {
533 if (MinShiftAmount == BitWidth) {
534 // Always poison. Return zero because we don't like returning conflict.
535 Known.setAllZero();
536 return Known;
537 }
538 return Known;
539 }
540
541 // Find the common bits from all possible shifts.
542 APInt MaxValue = RHS.getMaxValue();
543 unsigned MaxShiftAmount = getMaxShiftAmount(MaxValue, BitWidth);
544
545 // If exact, bound MaxShiftAmount to first known 1 in LHS.
546 if (Exact) {
547 unsigned FirstOne = LHS.countMaxTrailingZeros();
548 if (FirstOne < MinShiftAmount) {
549 // Always poison. Return zero because we don't like returning conflict.
550 Known.setAllZero();
551 return Known;
552 }
553 MaxShiftAmount = std::min(MaxShiftAmount, FirstOne);
554 }
555
556 unsigned ShiftAmtZeroMask = RHS.Zero.zextOrTrunc(32).getZExtValue();
557 unsigned ShiftAmtOneMask = RHS.One.zextOrTrunc(32).getZExtValue();
558 Known.setAllConflict();
559 for (unsigned ShiftAmt = MinShiftAmount; ShiftAmt <= MaxShiftAmount;
560 ++ShiftAmt) {
561 // Skip if the shift amount is impossible.
562 if ((ShiftAmtZeroMask & ShiftAmt) != 0 ||
563 (ShiftAmtOneMask | ShiftAmt) != ShiftAmt)
564 continue;
565 Known = Known.intersectWith(ShiftByConst(LHS, ShiftAmt));
566 if (Known.isUnknown())
567 break;
568 }
569
570 // All shift amounts may result in poison.
571 if (Known.hasConflict())
572 Known.setAllZero();
573 return Known;
574}
575
576KnownBits KnownBits::fshl(const KnownBits &LHS, const KnownBits &RHS,
577 const APInt &Amt) {
578 return KnownBits(APIntOps::fshl(LHS.Zero, RHS.Zero, Amt),
579 APIntOps::fshl(LHS.One, RHS.One, Amt));
580}
581
582KnownBits KnownBits::fshr(const KnownBits &LHS, const KnownBits &RHS,
583 const APInt &Amt) {
584 return KnownBits(APIntOps::fshr(LHS.Zero, RHS.Zero, Amt),
585 APIntOps::fshr(LHS.One, RHS.One, Amt));
586}
587
588KnownBits KnownBits::clmul(const KnownBits &LHS, const KnownBits &RHS) {
589 KnownBits Res =
590 makeConstant(APIntOps::clmul(LHS.getMinValue(), RHS.getMinValue()));
591
592 // This is the same operation as clmul except it accumulates the result with
593 // an OR instead of an XOR.
594 auto ClMulOr = [](const APInt &LHS, const APInt &RHS) {
595 unsigned BW = LHS.getBitWidth();
596 assert(BW == RHS.getBitWidth() && "Operand mismatch");
597 APInt Result(BW, 0);
598 for (unsigned I :
599 seq(std::min(RHS.getActiveBits(), BW - LHS.countr_zero())))
600 if (RHS[I])
601 Result |= LHS << I;
602 return Result;
603 };
604
605 // Bits in the result are known if, for every corresponding pair of input
606 // bits, both input bits are known or either input bit is known to be zero.
607 APInt Known = ~(ClMulOr(~LHS.Zero & ~LHS.One, ~RHS.Zero) |
608 ClMulOr(~LHS.Zero, ~RHS.Zero & ~RHS.One));
609 Res.Zero &= Known;
610 Res.One &= Known;
611
612 return Res;
613}
614
615KnownBits KnownBits::pext(const KnownBits &Val, const KnownBits &Mask) {
616 unsigned BitWidth = Val.getBitWidth();
617 KnownBits Res(BitWidth);
618 // We start by asserting that bits cannot be 0 and cannot be 1, then clear
619 // Res bits where we know a bit could have some value.
620 Res.setAllConflict();
621
622 // For each source position I where Mask[I] could be 1, the output position J
623 // lies in [M0, M1], where M0 and M1 track the range of possible 1-bit counts
624 // seen so far in Mask. Note that M0=M1 as long as bits in Mask are known;
625 // otherwise, the range of possible output positions widens.
626 unsigned M0 = 0, M1 = 0;
627 for (unsigned I = 0; I < BitWidth; ++I) {
628 if (!Mask.Zero[I]) {
629 // Mask[I] could be 1, so we decide what value the Res bits could have.
630 if (!Val.Zero[I])
631 // Val[I] could be 1 => Res[J] for J in [M0, M1] could be 1
632 Res.Zero.clearBits(M0, M1 + 1);
633 if (!Val.One[I])
634 // Val[I] could be 0 => Res[J] for J in [M0, M1] could be 0
635 Res.One.clearBits(M0, M1 + 1);
636 }
637 if (Mask.One[I])
638 ++M0, ++M1;
639 else if (!Mask.Zero[I])
640 ++M1;
641 }
642
643 // Output bits at J >= M0 may have no source (popcount(Mask) may be <= J), so
644 // they may be 0.
645 Res.One.clearBits(M0, BitWidth);
646 return Res;
647}
648
649KnownBits KnownBits::pdep(const KnownBits &Val, const KnownBits &Mask) {
650 unsigned BitWidth = Val.getBitWidth();
651 KnownBits Res(BitWidth);
652 // We start by asserting that bits cannot be 0 and cannot be 1, then clear
653 // Res bits where we know a bit could have some value.
654 Res.setAllConflict();
655
656 // For each output position I where Mask[I] could be 1, the source position J
657 // lies in [M0, M1], where M0 and M1 track the range of possible 1-bit counts
658 // seen so far in Mask. Note that M0=M1 as long as bits in Mask are known;
659 // otherwise, the range of possible source positions widens.
660 unsigned M0 = 0, M1 = 0;
661 for (unsigned I = 0; I < BitWidth; ++I) {
662 if (!Mask.One[I])
663 // Mask[I] could be 0 => Res[I] could be 0
664 Res.One.clearBit(I);
665 if (!Mask.Zero[I]) {
666 // Mask[I] could be 1, so we check what value the Val bits could have.
668 if (!Range.isSubsetOf(Val.One))
669 // Any Val[J] for J in [M0, M1] could be 0 => Res[I] could be 0
670 Res.One.clearBit(I);
671 if (!Range.isSubsetOf(Val.Zero))
672 // Any Val[J] for J in [M0, M1] could be 1 => Res[I] could be 1
673 Res.Zero.clearBit(I);
674 }
675 if (Mask.One[I])
676 ++M0, ++M1;
677 else if (!Mask.Zero[I])
678 ++M1;
679 }
680 return Res;
681}
682
683std::optional<bool> KnownBits::eq(const KnownBits &LHS, const KnownBits &RHS) {
684 if (LHS.isConstant() && RHS.isConstant())
685 return LHS.getConstant() == RHS.getConstant();
686 if (LHS.One.intersects(RHS.Zero) || RHS.One.intersects(LHS.Zero))
687 return false;
688 return std::nullopt;
689}
690
691std::optional<bool> KnownBits::ne(const KnownBits &LHS, const KnownBits &RHS) {
692 if (std::optional<bool> KnownEQ = eq(LHS, RHS))
693 return !*KnownEQ;
694 return std::nullopt;
695}
696
697std::optional<bool> KnownBits::ugt(const KnownBits &LHS, const KnownBits &RHS) {
698 // LHS >u RHS -> false if umax(LHS) <= umax(RHS)
699 if (LHS.getMaxValue().ule(RHS.getMinValue()))
700 return false;
701 // LHS >u RHS -> true if umin(LHS) > umax(RHS)
702 if (LHS.getMinValue().ugt(RHS.getMaxValue()))
703 return true;
704 return std::nullopt;
705}
706
707std::optional<bool> KnownBits::uge(const KnownBits &LHS, const KnownBits &RHS) {
708 if (std::optional<bool> IsUGT = ugt(RHS, LHS))
709 return !*IsUGT;
710 return std::nullopt;
711}
712
713std::optional<bool> KnownBits::ult(const KnownBits &LHS, const KnownBits &RHS) {
714 return ugt(RHS, LHS);
715}
716
717std::optional<bool> KnownBits::ule(const KnownBits &LHS, const KnownBits &RHS) {
718 return uge(RHS, LHS);
719}
720
721std::optional<bool> KnownBits::sgt(const KnownBits &LHS, const KnownBits &RHS) {
722 // LHS >s RHS -> false if smax(LHS) <= smax(RHS)
723 if (LHS.getSignedMaxValue().sle(RHS.getSignedMinValue()))
724 return false;
725 // LHS >s RHS -> true if smin(LHS) > smax(RHS)
726 if (LHS.getSignedMinValue().sgt(RHS.getSignedMaxValue()))
727 return true;
728 return std::nullopt;
729}
730
731std::optional<bool> KnownBits::sge(const KnownBits &LHS, const KnownBits &RHS) {
732 if (std::optional<bool> KnownSGT = sgt(RHS, LHS))
733 return !*KnownSGT;
734 return std::nullopt;
735}
736
737std::optional<bool> KnownBits::slt(const KnownBits &LHS, const KnownBits &RHS) {
738 return sgt(RHS, LHS);
739}
740
741std::optional<bool> KnownBits::sle(const KnownBits &LHS, const KnownBits &RHS) {
742 return sge(RHS, LHS);
743}
744
745KnownBits KnownBits::abs(bool IntMinIsPoison) const {
746 // If the source's MSB is zero then we know the rest of the bits already.
747 if (isNonNegative())
748 return *this;
749
750 // Absolute value preserves trailing zero count.
751 KnownBits KnownAbs(getBitWidth());
752
753 // If the input is negative, then abs(x) == -x.
754 if (isNegative()) {
755 KnownBits Tmp = *this;
756 // Special case for IntMinIsPoison. We know the sign bit is set and we know
757 // all the rest of the bits except one to be zero. Since we have
758 // IntMinIsPoison, that final bit MUST be a one, as otherwise the input is
759 // INT_MIN.
760 if (IntMinIsPoison && (Zero.popcount() + 2) == getBitWidth())
762
763 KnownAbs = computeForAddSub(
764 /*Add*/ false, IntMinIsPoison, /*NUW=*/false,
766
767 // One more special case for IntMinIsPoison. If we don't know any ones other
768 // than the signbit, we know for certain that all the unknowns can't be
769 // zero. So if we know high zero bits, but have unknown low bits, we know
770 // for certain those high-zero bits will end up as one. This is because,
771 // the low bits can't be all zeros, so the +1 in (~x + 1) cannot carry up
772 // to the high bits. If we know a known INT_MIN input skip this. The result
773 // is poison anyways.
774 if (IntMinIsPoison && Tmp.countMinPopulation() == 1 &&
775 Tmp.countMaxPopulation() != 1) {
776 Tmp.One.clearSignBit();
777 Tmp.Zero.setSignBit();
778 KnownAbs.One.setBits(getBitWidth() - Tmp.countMinLeadingZeros(),
779 getBitWidth() - 1);
780 }
781
782 } else {
783 unsigned MaxTZ = countMaxTrailingZeros();
784 unsigned MinTZ = countMinTrailingZeros();
785
786 KnownAbs.Zero.setLowBits(MinTZ);
787 // If we know the lowest set 1, then preserve it.
788 if (MaxTZ == MinTZ && MaxTZ < getBitWidth())
789 KnownAbs.One.setBit(MaxTZ);
790
791 // We only know that the absolute values's MSB will be zero if INT_MIN is
792 // poison, or there is a set bit that isn't the sign bit (otherwise it could
793 // be INT_MIN).
794 if (IntMinIsPoison || (!One.isZero() && !One.isMinSignedValue())) {
795 KnownAbs.One.clearSignBit();
796 KnownAbs.Zero.setSignBit();
797 }
798 }
799
800 return KnownAbs;
801}
802
803KnownBits KnownBits::ctlz(bool ZeroIsPoison) const {
804 unsigned BitWidth = getBitWidth();
805 unsigned MaxLZ = countMaxLeadingZeros();
806 if (ZeroIsPoison)
807 MaxLZ = std::min(MaxLZ, BitWidth - 1);
808
809 KnownBits Result(BitWidth);
810 Result.Zero.setBitsFrom(llvm::bit_width(MaxLZ));
811 return Result;
812}
813
814KnownBits KnownBits::reduceAdd(unsigned NumElts) const {
815 if (NumElts == 0)
816 return KnownBits(getBitWidth());
817
818 unsigned BitWidth = getBitWidth();
819 KnownBits Result(BitWidth);
820
821 if (isConstant())
822 // If all elements are the same constant, we can simply compute it
823 return KnownBits::makeConstant(NumElts * getConstant());
824
825 // The main idea is as follows.
826 //
827 // If KnownBits for each element has L leading zeros then
828 // X_i < 2^(W - L) for every i from [1, N].
829 //
830 // ADD X_i <= ADD max(X_i) = N * max(X_i)
831 // < N * 2^(W - L)
832 // < 2^(W - L + ceil(log2(N)))
833 //
834 // As the result, we can conclude that
835 //
836 // L' = L - ceil(log2(N))
837 //
838 // Similar logic can be applied to leading ones.
839 unsigned LostBits = Log2_32_Ceil(NumElts);
840
841 if (isNonNegative()) {
842 unsigned LeadingZeros = countMinLeadingZeros();
843 LeadingZeros = LeadingZeros > LostBits ? LeadingZeros - LostBits : 0;
844 Result.Zero.setHighBits(LeadingZeros);
845 } else if (isNegative()) {
846 unsigned LeadingOnes = countMinLeadingOnes();
847 LeadingOnes = LeadingOnes > LostBits ? LeadingOnes - LostBits : 0;
848 Result.One.setHighBits(LeadingOnes);
849 }
850
851 return Result;
852}
853
855 const KnownBits &LHS,
856 const KnownBits &RHS) {
857 // We don't see NSW even for sadd/ssub as we want to check if the result has
858 // signed overflow.
859 unsigned BitWidth = LHS.getBitWidth();
860
861 std::optional<bool> Overflow;
862 // Even if we can't entirely rule out overflow, we may be able to rule out
863 // overflow in one direction. This allows us to potentially keep some of the
864 // add/sub bits. I.e if we can't overflow in the positive direction we won't
865 // clamp to INT_MAX so we can keep low 0s from the add/sub result.
866 bool MayNegClamp = true;
867 bool MayPosClamp = true;
868 if (Signed) {
869 // Easy cases we can rule out any overflow.
870 if (Add && ((LHS.isNegative() && RHS.isNonNegative()) ||
871 (LHS.isNonNegative() && RHS.isNegative())))
872 Overflow = false;
873 else if (!Add && (((LHS.isNegative() && RHS.isNegative()) ||
874 (LHS.isNonNegative() && RHS.isNonNegative()))))
875 Overflow = false;
876 else {
877 // Check if we may overflow. If we can't rule out overflow then check if
878 // we can rule out a direction at least.
879 KnownBits UnsignedLHS = LHS;
880 KnownBits UnsignedRHS = RHS;
881 // Get version of LHS/RHS with clearer signbit. This allows us to detect
882 // how the addition/subtraction might overflow into the signbit. Then
883 // using the actual known signbits of LHS/RHS, we can figure out which
884 // overflows are/aren't possible.
885 UnsignedLHS.One.clearSignBit();
886 UnsignedLHS.Zero.setSignBit();
887 UnsignedRHS.One.clearSignBit();
888 UnsignedRHS.Zero.setSignBit();
889 KnownBits Res =
890 KnownBits::computeForAddSub(Add, /*NSW=*/false,
891 /*NUW=*/false, UnsignedLHS, UnsignedRHS);
892 if (Add) {
893 if (Res.isNegative()) {
894 // Only overflow scenario is Pos + Pos.
895 MayNegClamp = false;
896 // Pos + Pos will overflow with extra signbit.
897 if (LHS.isNonNegative() && RHS.isNonNegative())
898 Overflow = true;
899 } else if (Res.isNonNegative()) {
900 // Only overflow scenario is Neg + Neg
901 MayPosClamp = false;
902 // Neg + Neg will overflow without extra signbit.
903 if (LHS.isNegative() && RHS.isNegative())
904 Overflow = true;
905 }
906 // We will never clamp to the opposite sign of N-bit result.
907 if (LHS.isNegative() || RHS.isNegative())
908 MayPosClamp = false;
909 if (LHS.isNonNegative() || RHS.isNonNegative())
910 MayNegClamp = false;
911 } else {
912 if (Res.isNegative()) {
913 // Only overflow scenario is Neg - Pos.
914 MayPosClamp = false;
915 // Neg - Pos will overflow with extra signbit.
916 if (LHS.isNegative() && RHS.isNonNegative())
917 Overflow = true;
918 } else if (Res.isNonNegative()) {
919 // Only overflow scenario is Pos - Neg.
920 MayNegClamp = false;
921 // Pos - Neg will overflow without extra signbit.
922 if (LHS.isNonNegative() && RHS.isNegative())
923 Overflow = true;
924 }
925 // We will never clamp to the opposite sign of N-bit result.
926 if (LHS.isNegative() || RHS.isNonNegative())
927 MayPosClamp = false;
928 if (LHS.isNonNegative() || RHS.isNegative())
929 MayNegClamp = false;
930 }
931 }
932 // If we have ruled out all clamping, we will never overflow.
933 if (!MayNegClamp && !MayPosClamp)
934 Overflow = false;
935 } else if (Add) {
936 // uadd.sat
937 bool Of;
938 (void)LHS.getMaxValue().uadd_ov(RHS.getMaxValue(), Of);
939 if (!Of) {
940 Overflow = false;
941 } else {
942 (void)LHS.getMinValue().uadd_ov(RHS.getMinValue(), Of);
943 if (Of)
944 Overflow = true;
945 }
946 } else {
947 // usub.sat
948 bool Of;
949 (void)LHS.getMinValue().usub_ov(RHS.getMaxValue(), Of);
950 if (!Of) {
951 Overflow = false;
952 } else {
953 (void)LHS.getMaxValue().usub_ov(RHS.getMinValue(), Of);
954 if (Of)
955 Overflow = true;
956 }
957 }
958
960 /*NUW=*/!Signed, LHS, RHS);
961
962 if (Overflow) {
963 // We know whether or not we overflowed.
964 if (!(*Overflow)) {
965 // No overflow.
966 return Res;
967 }
968
969 // We overflowed
970 APInt C;
971 if (Signed) {
972 // sadd.sat / ssub.sat
973 assert(!LHS.isSignUnknown() &&
974 "We somehow know overflow without knowing input sign");
975 C = LHS.isNegative() ? APInt::getSignedMinValue(BitWidth)
977 } else if (Add) {
978 // uadd.sat
980 } else {
981 // uadd.sat
983 }
984
985 Res.One = C;
986 Res.Zero = ~C;
987 return Res;
988 }
989
990 // We don't know if we overflowed.
991 if (Signed) {
992 // sadd.sat/ssub.sat
993 // We can keep our information about the sign bits.
994 if (MayPosClamp)
995 Res.Zero.clearLowBits(BitWidth - 1);
996 if (MayNegClamp)
997 Res.One.clearLowBits(BitWidth - 1);
998 } else if (Add) {
999 // uadd.sat
1000 // We need to clear all the known zeros as we can only use the leading ones.
1001 Res.Zero.clearAllBits();
1002 } else {
1003 // usub.sat
1004 // We need to clear all the known ones as we can only use the leading zero.
1005 Res.One.clearAllBits();
1006 }
1007
1008 return Res;
1009}
1010
1011KnownBits KnownBits::sadd_sat(const KnownBits &LHS, const KnownBits &RHS) {
1012 return computeForSatAddSub(/*Add*/ true, /*Signed*/ true, LHS, RHS);
1013}
1014KnownBits KnownBits::ssub_sat(const KnownBits &LHS, const KnownBits &RHS) {
1015 return computeForSatAddSub(/*Add*/ false, /*Signed*/ true, LHS, RHS);
1016}
1017KnownBits KnownBits::uadd_sat(const KnownBits &LHS, const KnownBits &RHS) {
1018 return computeForSatAddSub(/*Add*/ true, /*Signed*/ false, LHS, RHS);
1019}
1020KnownBits KnownBits::usub_sat(const KnownBits &LHS, const KnownBits &RHS) {
1021 return computeForSatAddSub(/*Add*/ false, /*Signed*/ false, LHS, RHS);
1022}
1023
1025 unsigned BitWidth = LHS.getBitWidth();
1026 LHS = LHS.zext(BitWidth + 1);
1027 RHS = RHS.zext(BitWidth + 1);
1028 LHS =
1029 computeForAddCarry(LHS, RHS, /*CarryZero*/ !IsCeil, /*CarryOne*/ IsCeil);
1030 LHS = LHS.extractBits(BitWidth, 1);
1031 return LHS;
1032}
1033
1034KnownBits KnownBits::avgFloorS(const KnownBits &LHS, const KnownBits &RHS) {
1035 return flipSignBit(avgFloorU(flipSignBit(LHS), flipSignBit(RHS)));
1036}
1037
1038KnownBits KnownBits::avgFloorU(const KnownBits &LHS, const KnownBits &RHS) {
1039 return avgComputeU(LHS, RHS, /*IsCeil=*/false);
1040}
1041
1042KnownBits KnownBits::avgCeilS(const KnownBits &LHS, const KnownBits &RHS) {
1043 return flipSignBit(avgCeilU(flipSignBit(LHS), flipSignBit(RHS)));
1044}
1045
1046KnownBits KnownBits::avgCeilU(const KnownBits &LHS, const KnownBits &RHS) {
1047 return avgComputeU(LHS, RHS, /*IsCeil=*/true);
1048}
1049
1050KnownBits KnownBits::mul(const KnownBits &LHS, const KnownBits &RHS,
1051 bool NoUndefSelfMultiply) {
1052 unsigned BitWidth = LHS.getBitWidth();
1053 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");
1054 assert((!NoUndefSelfMultiply || LHS == RHS) &&
1055 "Self multiplication knownbits mismatch");
1056
1057 // Compute the high known-0 bits by multiplying the unsigned max of each side.
1058 // Conservatively, M active bits * N active bits results in M + N bits in the
1059 // result. But if we know a value is a power-of-2 for example, then this
1060 // computes one more leading zero.
1061 // TODO: This could be generalized to number of sign bits (negative numbers).
1062 APInt UMaxLHS = LHS.getMaxValue();
1063 APInt UMaxRHS = RHS.getMaxValue();
1064
1065 // For leading zeros in the result to be valid, the unsigned max product must
1066 // fit in the bitwidth (it must not overflow).
1067 bool HasOverflow;
1068 APInt UMaxResult = UMaxLHS.umul_ov(UMaxRHS, HasOverflow);
1069 unsigned LeadZ = HasOverflow ? 0 : UMaxResult.countl_zero();
1070
1071 // The result of the bottom bits of an integer multiply can be
1072 // inferred by looking at the bottom bits of both operands and
1073 // multiplying them together.
1074 // We can infer at least the minimum number of known trailing bits
1075 // of both operands. Depending on number of trailing zeros, we can
1076 // infer more bits, because (a*b) <=> ((a/m) * (b/n)) * (m*n) assuming
1077 // a and b are divisible by m and n respectively.
1078 // We then calculate how many of those bits are inferrable and set
1079 // the output. For example, the i8 mul:
1080 // a = XXXX1100 (12)
1081 // b = XXXX1110 (14)
1082 // We know the bottom 3 bits are zero since the first can be divided by
1083 // 4 and the second by 2, thus having ((12/4) * (14/2)) * (2*4).
1084 // Applying the multiplication to the trimmed arguments gets:
1085 // XX11 (3)
1086 // X111 (7)
1087 // -------
1088 // XX11
1089 // XX11
1090 // XX11
1091 // XX11
1092 // -------
1093 // XXXXX01
1094 // Which allows us to infer the 2 LSBs. Since we're multiplying the result
1095 // by 8, the bottom 3 bits will be 0, so we can infer a total of 5 bits.
1096 // The proof for this can be described as:
1097 // Pre: (C1 >= 0) && (C1 < (1 << C5)) && (C2 >= 0) && (C2 < (1 << C6)) &&
1098 // (C7 == (1 << (umin(countTrailingZeros(C1), C5) +
1099 // umin(countTrailingZeros(C2), C6) +
1100 // umin(C5 - umin(countTrailingZeros(C1), C5),
1101 // C6 - umin(countTrailingZeros(C2), C6)))) - 1)
1102 // %aa = shl i8 %a, C5
1103 // %bb = shl i8 %b, C6
1104 // %aaa = or i8 %aa, C1
1105 // %bbb = or i8 %bb, C2
1106 // %mul = mul i8 %aaa, %bbb
1107 // %mask = and i8 %mul, C7
1108 // =>
1109 // %mask = i8 ((C1*C2)&C7)
1110 // Where C5, C6 describe the known bits of %a, %b
1111 // C1, C2 describe the known bottom bits of %a, %b.
1112 // C7 describes the mask of the known bits of the result.
1113
1114 // How many times we'd be able to divide each argument by 2 (shr by 1).
1115 // This gives us the number of trailing zeros on the multiplication result.
1116 unsigned TrailBitsKnownLHS = (LHS.Zero | LHS.One).countr_one();
1117 unsigned TrailBitsKnownRHS = (RHS.Zero | RHS.One).countr_one();
1118 unsigned TrailZeroLHS = LHS.countMinTrailingZeros();
1119 unsigned TrailZeroRHS = RHS.countMinTrailingZeros();
1120 unsigned TrailZ = TrailZeroLHS + TrailZeroRHS;
1121
1122 // Figure out the fewest known-bits operand.
1123 unsigned SmallestOperand = std::min(TrailBitsKnownLHS - TrailZeroLHS,
1124 TrailBitsKnownRHS - TrailZeroRHS);
1125 unsigned ResultBitsKnown = std::min(SmallestOperand + TrailZ, BitWidth);
1126
1127 // The lower ResultBitsKnown bits of this are known.
1128 APInt BottomKnown = LHS.One * RHS.One;
1129
1130 KnownBits Res(BitWidth);
1131 Res.Zero.setHighBits(LeadZ);
1132 Res.Zero |= (~BottomKnown).getLoBits(ResultBitsKnown);
1133 Res.One = BottomKnown.getLoBits(ResultBitsKnown);
1134
1135 if (NoUndefSelfMultiply) {
1136 // If X has at least TZ trailing zeroes, then bit (2 * TZ + 1) must be zero.
1137 unsigned TwoTZP1 = 2 * TrailZeroLHS + 1;
1138 if (TwoTZP1 < BitWidth)
1139 Res.Zero.setBit(TwoTZP1);
1140
1141 // If X has exactly TZ trailing zeros, then bit (2 * TZ + 2) must also be
1142 // zero.
1143 if (TrailZeroLHS < BitWidth && LHS.One[TrailZeroLHS]) {
1144 unsigned TwoTZP2 = TwoTZP1 + 1;
1145 if (TwoTZP2 < BitWidth)
1146 Res.Zero.setBit(TwoTZP2);
1147 }
1148 }
1149
1150 return Res;
1151}
1152
1153KnownBits KnownBits::mulhs(const KnownBits &LHS, const KnownBits &RHS) {
1154 unsigned BitWidth = LHS.getBitWidth();
1155 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");
1156 KnownBits WideLHS = LHS.sext(2 * BitWidth);
1157 KnownBits WideRHS = RHS.sext(2 * BitWidth);
1158 return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);
1159}
1160
1161KnownBits KnownBits::mulhu(const KnownBits &LHS, const KnownBits &RHS) {
1162 unsigned BitWidth = LHS.getBitWidth();
1163 assert(BitWidth == RHS.getBitWidth() && "Operand mismatch");
1164 KnownBits WideLHS = LHS.zext(2 * BitWidth);
1165 KnownBits WideRHS = RHS.zext(2 * BitWidth);
1166 return mul(WideLHS, WideRHS).extractBits(BitWidth, BitWidth);
1167}
1168
1170 const KnownBits &RHS, bool Exact) {
1171
1172 if (!Exact)
1173 return Known;
1174
1175 // If LHS is Odd, the result is Odd no matter what.
1176 // Odd / Odd -> Odd
1177 // Odd / Even -> Impossible (because its exact division)
1178 if (LHS.One[0])
1179 Known.One.setBit(0);
1180
1181 int MinTZ =
1182 (int)LHS.countMinTrailingZeros() - (int)RHS.countMaxTrailingZeros();
1183 int MaxTZ =
1184 (int)LHS.countMaxTrailingZeros() - (int)RHS.countMinTrailingZeros();
1185 if (MinTZ >= 0) {
1186 // Result has at least MinTZ trailing zeros.
1187 Known.Zero.setLowBits(MinTZ);
1188 if (MinTZ == MaxTZ) {
1189 // Result has exactly MinTZ trailing zeros.
1190 Known.One.setBit(MinTZ);
1191 }
1192 } else if (MaxTZ < 0) {
1193 // Poison Result
1194 Known.setAllZero();
1195 }
1196
1197 // In the KnownBits exhaustive tests, we have poison inputs for exact values
1198 // a LOT. If we have a conflict, just return all zeros.
1199 if (Known.hasConflict())
1200 Known.setAllZero();
1201
1202 return Known;
1203}
1204
1205KnownBits KnownBits::sdiv(const KnownBits &LHS, const KnownBits &RHS,
1206 bool Exact) {
1207 // Equivalent of `udiv`. We must have caught this before it was folded.
1208 if (LHS.isNonNegative() && RHS.isNonNegative())
1209 return udiv(LHS, RHS, Exact);
1210
1211 unsigned BitWidth = LHS.getBitWidth();
1212 KnownBits Known(BitWidth);
1213
1214 if (LHS.isZero() || RHS.isZero()) {
1215 // Result is either known Zero or UB. Return Zero either way.
1216 // Checking this earlier saves us a lot of special cases later on.
1217 Known.setAllZero();
1218 return Known;
1219 }
1220
1221 std::optional<APInt> Res;
1222 if (LHS.isNegative() && RHS.isNegative()) {
1223 // Result non-negative.
1224 APInt Denom = RHS.getSignedMaxValue();
1225 APInt Num = LHS.getSignedMinValue();
1226 // INT_MIN/-1 would be a poison result (impossible). Estimate the division
1227 // as signed max (we will only set sign bit in the result).
1228 Res = (Num.isMinSignedValue() && Denom.isAllOnes())
1230 : Num.sdiv(Denom);
1231 } else if (LHS.isNegative() && RHS.isNonNegative()) {
1232 // Result is negative if Exact OR -LHS u>= RHS.
1233 if (Exact || (-LHS.getSignedMaxValue()).uge(RHS.getSignedMaxValue())) {
1234 APInt Denom = RHS.getSignedMinValue();
1235 APInt Num = LHS.getSignedMinValue();
1236 // If the denominator may be zero, use the lowest unknown bit as the
1237 // minimum non-zero denominator, matching udiv.
1238 if (Denom.isZero())
1239 Denom.setBit(RHS.countMinTrailingZeros());
1240 Res = Num.sdiv(Denom);
1241 }
1242 } else if (LHS.isStrictlyPositive() && RHS.isNegative()) {
1243 // Result is negative if Exact OR LHS u>= -RHS.
1244 if (Exact || LHS.getSignedMinValue().uge(-RHS.getSignedMinValue())) {
1245 APInt Denom = RHS.getSignedMaxValue();
1246 APInt Num = LHS.getSignedMaxValue();
1247 Res = Num.sdiv(Denom);
1248 }
1249 }
1250
1251 if (Res) {
1252 if (Res->isNonNegative()) {
1253 unsigned LeadZ = Res->countLeadingZeros();
1254 Known.Zero.setHighBits(LeadZ);
1255 } else {
1256 unsigned LeadO = Res->countLeadingOnes();
1257 Known.One.setHighBits(LeadO);
1258 }
1259 }
1260
1261 Known = divComputeLowBit(Known, LHS, RHS, Exact);
1262 return Known;
1263}
1264
1265KnownBits KnownBits::udiv(const KnownBits &LHS, const KnownBits &RHS,
1266 bool Exact) {
1267 unsigned BitWidth = LHS.getBitWidth();
1268 KnownBits Known(BitWidth);
1269
1270 if (LHS.isZero() || RHS.isZero()) {
1271 // Result is either known Zero or UB. Return Zero either way.
1272 // Checking this earlier saves us a lot of special cases later on.
1273 Known.setAllZero();
1274 return Known;
1275 }
1276
1277 // A zero denominator is UB, so the minimum attainable denominator is the
1278 // smallest non-zero value consistent with the known bits.
1279 APInt MinDenom = RHS.getMinValue();
1280 if (MinDenom.isZero())
1281 MinDenom.setBit(RHS.countMinTrailingZeros());
1282
1283 // The quotient grows when the numerator grows and shrinks when the
1284 // denominator grows, and all four operand bounds are attainable, so the
1285 // result is in [MinNum / MaxDenom, MaxNum / MinDenom]. If the division is
1286 // exact we tighten the bounds on minimum result, so we round up the lower
1287 // bound to its ceiling. Keep the common leading bits of the two bounds (as
1288 // ConstantRange::toKnownBits does), which can include leading ones, not
1289 // just leading zeros.
1290 APInt MaxDenom = RHS.getMaxValue();
1291 APInt MaxRes = LHS.getMaxValue().udiv(MinDenom);
1292 APInt MinRes = Exact ? APIntOps::RoundingUDiv(LHS.getMinValue(), MaxDenom,
1294 : LHS.getMinValue().udiv(MaxDenom);
1295
1297 if (std::optional<unsigned> DifferentBit =
1299 Known.Zero.clearLowBits(*DifferentBit + 1);
1300 Known.One.clearLowBits(*DifferentBit + 1);
1301 }
1302
1303 Known = divComputeLowBit(Known, LHS, RHS, Exact);
1304
1305 return Known;
1306}
1307
1308KnownBits KnownBits::remGetLowBits(const KnownBits &LHS, const KnownBits &RHS) {
1309 unsigned BitWidth = LHS.getBitWidth();
1310 if (!RHS.isZero() && RHS.Zero[0]) {
1311 // rem X, Y where Y[0:N] is zero will preserve X[0:N] in the result.
1312 unsigned RHSZeros = RHS.countMinTrailingZeros();
1313 APInt Mask = APInt::getLowBitsSet(BitWidth, RHSZeros);
1314 APInt OnesMask = LHS.One & Mask;
1315 APInt ZerosMask = LHS.Zero & Mask;
1316 return KnownBits(ZerosMask, OnesMask);
1317 }
1318 return KnownBits(BitWidth);
1319}
1320
1321KnownBits KnownBits::urem(const KnownBits &LHS, const KnownBits &RHS) {
1322 // L % R for L < R is L. (A zero divisor is UB, and if MinR is zero this
1323 // condition cannot hold anyway.)
1324 if (LHS.getMaxValue().ult(RHS.getMinValue()))
1325 return LHS;
1326
1327 KnownBits Known = remGetLowBits(LHS, RHS);
1328
1329 // L % R is at most L and, since a zero divisor is UB, strictly less than
1330 // R, so the result has at least as many leading zeros as
1331 // umin(MaxL, MaxR - 1), as in ConstantRange::urem. For a power-of-two
1332 // constant R this computes the exact L & (R - 1): remGetLowBits preserved
1333 // the low bits and this clears the bits from log2(R) up. If R is known to
1334 // be zero, MaxR - 1 wraps around, which is harmless: every input is UB.
1335 APInt MaxRes = APIntOps::umin(LHS.getMaxValue(), RHS.getMaxValue() - 1);
1336 Known.Zero.setHighBits(MaxRes.countLeadingZeros());
1337 return Known;
1338}
1339
1340KnownBits KnownBits::srem(const KnownBits &LHS, const KnownBits &RHS) {
1341 KnownBits Known = remGetLowBits(LHS, RHS);
1342 if (RHS.isConstant() && RHS.getConstant().isPowerOf2()) {
1343 // NB: Low bits are set in `remGetLowBits`.
1344 APInt LowBits = RHS.getConstant() - 1;
1345 // If the first operand is non-negative or has all low bits zero, then
1346 // the upper bits are all zero.
1347 if (LHS.isNonNegative() || LowBits.isSubsetOf(LHS.Zero))
1348 Known.Zero |= ~LowBits;
1349
1350 // If the first operand is negative and not all low bits are zero, then
1351 // the upper bits are all one.
1352 if (LHS.isNegative() && LowBits.intersects(LHS.One))
1353 Known.One |= ~LowBits;
1354 return Known;
1355 }
1356
1357 // The sign bit is the LHS's sign bit, except when the result of the
1358 // remainder is zero. The magnitude of the result should be less than or
1359 // equal to the magnitude of either operand.
1360 if (LHS.isNegative() && Known.isNonZero())
1361 Known.One.setHighBits(
1362 std::max(LHS.countMinLeadingOnes(), RHS.countMinSignBits()));
1363 else if (LHS.isNonNegative())
1364 Known.Zero.setHighBits(
1365 std::max(LHS.countMinLeadingZeros(), RHS.countMinSignBits()));
1366 return Known;
1367}
1368
1369KnownBits &KnownBits::operator&=(const KnownBits &RHS) {
1370 // Result bit is 0 if either operand bit is 0.
1371 Zero |= RHS.Zero;
1372 // Result bit is 1 if both operand bits are 1.
1373 One &= RHS.One;
1374 return *this;
1375}
1376
1377KnownBits &KnownBits::operator|=(const KnownBits &RHS) {
1378 // Result bit is 0 if both operand bits are 0.
1379 Zero &= RHS.Zero;
1380 // Result bit is 1 if either operand bit is 1.
1381 One |= RHS.One;
1382 return *this;
1383}
1384
1385KnownBits &KnownBits::operator^=(const KnownBits &RHS) {
1386 // Result bit is 0 if both operand bits are 0 or both are 1.
1387 APInt Z = (Zero & RHS.Zero) | (One & RHS.One);
1388 // Result bit is 1 if one operand bit is 0 and the other is 1.
1389 One = (Zero & RHS.One) | (One & RHS.Zero);
1390 Zero = std::move(Z);
1391 return *this;
1392}
1393
1394KnownBits KnownBits::blsi() const {
1395 unsigned BitWidth = getBitWidth();
1396 KnownBits Known(Zero, APInt(BitWidth, 0));
1397 unsigned Max = countMaxTrailingZeros();
1398 Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));
1399 unsigned Min = countMinTrailingZeros();
1400 if (Max == Min && Max < BitWidth)
1401 Known.One.setBit(Max);
1402 return Known;
1403}
1404
1405KnownBits KnownBits::blsmsk() const {
1406 unsigned BitWidth = getBitWidth();
1407 KnownBits Known(BitWidth);
1408 unsigned Max = countMaxTrailingZeros();
1409 Known.Zero.setBitsFrom(std::min(Max + 1, BitWidth));
1410 unsigned Min = countMinTrailingZeros();
1411 Known.One.setLowBits(std::min(Min + 1, BitWidth));
1412 return Known;
1413}
1414
1416 unsigned BitWidth = getBitWidth();
1417 for (unsigned I = 0; I < BitWidth; ++I) {
1418 unsigned N = BitWidth - I - 1;
1419 if (Zero[N] && One[N])
1420 OS << "!";
1421 else if (Zero[N])
1422 OS << "0";
1423 else if (One[N])
1424 OS << "1";
1425 else
1426 OS << "?";
1427 }
1428}
1429
1430#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
1432 print(dbgs());
1433 dbgs() << "\n";
1434}
1435#endif
1436
1437unsigned llvm::SignBitsOps::rot(unsigned SrcSignBits, unsigned BitWidth,
1438 std::optional<APInt> RotAmt,
1439 bool IsRotateRight) {
1440 // If we're rotating an 0/-1 value, then it stays an 0/-1 value.
1441 if (SrcSignBits == BitWidth)
1442 return BitWidth;
1443
1444 if (!RotAmt)
1445 return 1;
1446
1447 unsigned Amt = RotAmt->urem(BitWidth);
1448
1449 // Handle rotate right by N like a rotate left by BitWidth-N.
1450 if (IsRotateRight)
1451 Amt = (BitWidth - Amt) % BitWidth;
1452
1453 // If we aren't rotating out all of the known-in sign bits, return the
1454 // number that are left. This handles rotl(sext(x), 1) for example.
1455 if (SrcSignBits > Amt + 1)
1456 return SrcSignBits - Amt;
1457 return 1;
1458}
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
static GCRegistry::Add< ShadowStackGC > C("shadow-stack", "Very portable GC for uncooperative code generators")
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition Compiler.h:702
static KnownBits avgComputeU(KnownBits LHS, KnownBits RHS, bool IsCeil)
static KnownBits computeForSatAddSub(bool Add, bool Signed, const KnownBits &LHS, const KnownBits &RHS)
static KnownBits divComputeLowBit(KnownBits Known, const KnownBits &LHS, const KnownBits &RHS, bool Exact)
static KnownBits computeForAddCarry(const KnownBits &LHS, const KnownBits &RHS, bool CarryZero, bool CarryOne)
Definition KnownBits.cpp:32
static unsigned getMaxShiftAmount(const APInt &MaxValue, unsigned BitWidth)
#define I(x, y, z)
Definition MD5.cpp:57
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
Provides some synthesis utilities to produce sequences of values.
Value * RHS
Value * LHS
This file implements the C++20 <bit> header.
Class for arbitrary precision integers.
Definition APInt.h:78
LLVM_ABI APInt umul_ov(const APInt &RHS, bool &Overflow) const
Definition APInt.cpp:2018
LLVM_ABI APInt usub_sat(const APInt &RHS) const
Definition APInt.cpp:2102
LLVM_ABI APInt udiv(const APInt &RHS) const
Unsigned division operation.
Definition APInt.cpp:1602
static APInt getAllOnes(unsigned numBits)
Return an APInt of a specified width with all bits set.
Definition APInt.h:230
LLVM_ABI APInt getLoBits(unsigned numBits) const
Compute an APInt containing numBits lowbits from this APInt.
Definition APInt.cpp:641
void clearBit(unsigned BitPosition)
Set a given bit to 0.
Definition APInt.h:1426
LLVM_ABI APInt zext(unsigned width) const
Zero extend to a new width.
Definition APInt.cpp:1057
bool isMinSignedValue() const
Determine if this is the smallest signed value.
Definition APInt.h:419
void setHighBits(unsigned hiBits)
Set the top hiBits bits.
Definition APInt.h:1411
LLVM_ABI uint64_t extractBitsAsZExtValue(unsigned numBits, unsigned bitPosition) const
Definition APInt.cpp:517
LLVM_ABI APInt trunc(unsigned width) const
Truncate to new width.
Definition APInt.cpp:970
static APInt getMaxValue(unsigned numBits)
Gets maximum unsigned value of APInt for specific bit width.
Definition APInt.h:202
void setBit(unsigned BitPosition)
Set the given bit to 1 whose position is given as "bitPosition".
Definition APInt.h:1350
LLVM_ABI APInt sadd_sat(const APInt &RHS) const
Definition APInt.cpp:2073
bool sgt(const APInt &RHS) const
Signed greater than comparison.
Definition APInt.h:1205
bool isAllOnes() const
Determine if all bits are set. This is true for zero-width values.
Definition APInt.h:367
bool ugt(const APInt &RHS) const
Unsigned greater than comparison.
Definition APInt.h:1186
static APInt getBitsSet(unsigned numBits, unsigned loBit, unsigned hiBit)
Get a value with a block of bits set.
Definition APInt.h:254
bool isZero() const
Determine if this value is zero, i.e. all bits are clear.
Definition APInt.h:376
void setSignBit()
Set the sign bit to 1.
Definition APInt.h:1360
unsigned getBitWidth() const
Return the number of bits in the APInt.
Definition APInt.h:1508
static APInt getSignedMaxValue(unsigned numBits)
Gets maximum signed value of APInt for a specific bit width.
Definition APInt.h:205
static APInt getMinValue(unsigned numBits)
Gets minimum unsigned value of APInt for a specific bit width.
Definition APInt.h:212
bool isNegative() const
Determine sign of this APInt.
Definition APInt.h:325
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:1253
LLVM_ABI APInt sdiv(const APInt &RHS) const
Signed division function for APInt.
Definition APInt.cpp:1673
void clearAllBits()
Set every bit to 0.
Definition APInt.h:1416
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition APInt.h:1170
unsigned countl_zero() const
The APInt version of std::countl_zero.
Definition APInt.h:1618
static APInt getSignedMinValue(unsigned numBits)
Gets minimum signed value of APInt for a specific bit width.
Definition APInt.h:215
unsigned countLeadingZeros() const
Definition APInt.h:1626
unsigned countl_one() const
Count the number of leading one bits.
Definition APInt.h:1635
void clearLowBits(unsigned loBits)
Set bottom loBits bits to 0.
Definition APInt.h:1455
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:471
LLVM_ABI APInt uadd_sat(const APInt &RHS) const
Definition APInt.cpp:2083
bool getBoolValue() const
Convert APInt to a boolean value.
Definition APInt.h:467
bool isNonNegative() const
Determine if this APInt Value is non-negative (>= 0)
Definition APInt.h:330
bool ule(const APInt &RHS) const
Unsigned less or equal comparison.
Definition APInt.h:1154
LLVM_ABI APInt sext(unsigned width) const
Sign extend to a new width.
Definition APInt.cpp:1030
void setBits(unsigned loBit, unsigned hiBit)
Set the bits from loBit (inclusive) to hiBit (exclusive) to 1.
Definition APInt.h:1387
bool isSubsetOf(const APInt &RHS) const
This operation checks that all bits set in this APInt are also set in RHS.
Definition APInt.h:1261
static APInt getLowBitsSet(unsigned numBits, unsigned loBitsSet)
Constructs an APInt value that has the bottom loBitsSet bits set.
Definition APInt.h:302
void clearBits(unsigned LoBit, unsigned HiBit)
Clear the bits from LoBit (inclusive) to HiBit (exclusive) to 0.
Definition APInt.h:1437
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition APInt.h:1134
void setLowBits(unsigned loBits)
Set the bottom loBits bits.
Definition APInt.h:1408
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition APInt.h:1241
void clearSignBit()
Set the sign bit to 0.
Definition APInt.h:1469
LLVM_ABI APInt ssub_sat(const APInt &RHS) const
Definition APInt.cpp:2092
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition raw_ostream.h:53
LLVM_ABI std::optional< unsigned > GetMostSignificantDifferentBit(const APInt &A, const APInt &B)
Compare two values, and if they are different, return the position of the most significant bit that i...
Definition APInt.cpp:3045
LLVM_ABI APInt RoundingUDiv(const APInt &A, const APInt &B, APInt::Rounding RM)
Return A unsign-divided by B, rounded by the given rounding mode.
Definition APInt.cpp:2810
LLVM_ABI APInt fshr(const APInt &Hi, const APInt &Lo, const APInt &Shift)
Perform a funnel shift right.
Definition APInt.cpp:3235
LLVM_ABI APInt clmul(const APInt &LHS, const APInt &RHS)
Perform a carry-less multiply, also known as XOR multiplication, and return low-bits.
Definition APInt.cpp:3244
const APInt & umin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be unsigned.
Definition APInt.h:2284
LLVM_ABI APInt fshl(const APInt &Hi, const APInt &Lo, const APInt &Shift)
Perform a funnel shift left.
Definition APInt.cpp:3226
LLVM_ABI unsigned rot(unsigned SrcSignBits, unsigned BitWidth, std::optional< APInt > RotAmt, bool IsRotateRight)
Compute the number of sign bits after rotating a value.
This is an optimization pass for GlobalISel generic memory operations.
unsigned Log2_32_Ceil(uint32_t Value)
Return the ceil log base 2 of the specified value, 32 if the value is zero.
Definition MathExtras.h:339
@ Known
Known to have no common set bits.
int countr_one(T Value)
Count the number of ones from the least significant bit to the first zero bit.
Definition bit.h:315
int bit_width(T Value)
Returns the number of bits needed to represent Value if Value is nonzero.
Definition bit.h:325
unsigned M1(unsigned Val)
Definition VE.h:394
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:326
constexpr bool isPowerOf2_32(uint32_t Value)
Return true if the argument is a power of two > 0.
Definition MathExtras.h:280
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition Debug.cpp:209
int countl_one(T Value)
Count the number of ones from the most significant bit to the first zero bit.
Definition bit.h:302
@ Add
Sum of integers.
unsigned M0(unsigned Val)
Definition VE.h:393
constexpr unsigned BitWidth
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:1933
constexpr auto seq(T Begin, T End)
Iterate over an integral type from Begin up to - but not including - End.
Definition Sequence.h:341
Implement std::hash so that hash_code can be used in STL containers.
Definition BitVector.h:879
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition BitVector.h:881
#define N
static KnownBits makeConstant(const APInt &C)
Create known bits from a known constant.
Definition KnownBits.h:315
static LLVM_ABI KnownBits sadd_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.sadd.sat(LHS, RHS)
static LLVM_ABI std::optional< bool > eq(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_EQ result.
LLVM_ABI KnownBits sextInReg(unsigned SrcBitWidth) const
Return known bits for a in-register sign extension of the value we're tracking.
static LLVM_ABI KnownBits mulhu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from zero-extended multiply-hi.
static LLVM_ABI KnownBits smax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smax(LHS, RHS).
bool isNonNegative() const
Returns true if this value is known to be non-negative.
Definition KnownBits.h:106
LLVM_ABI KnownBits blsi() const
Compute known bits for X & -X, which has only the lowest bit set of X set.
static LLVM_ABI KnownBits usub_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.usub.sat(LHS, RHS)
unsigned countMinLeadingOnes() const
Returns the minimum number of leading one bits.
Definition KnownBits.h:265
LLVM_ABI KnownBits reduceAdd(unsigned NumElts) const
Compute known bits for horizontal add for a vector with NumElts elements, where each element has the ...
unsigned countMinTrailingZeros() const
Returns the minimum number of trailing zero bits.
Definition KnownBits.h:256
static LLVM_ABI KnownBits ashr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for ashr(LHS, RHS).
static LLVM_ABI KnownBits ssub_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.ssub.sat(LHS, RHS)
static LLVM_ABI KnownBits urem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for urem(LHS, RHS).
unsigned countMaxTrailingZeros() const
Returns the maximum number of trailing zero bits possible.
Definition KnownBits.h:288
static LLVM_ABI std::optional< bool > ne(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_NE result.
LLVM_ABI KnownBits makeGE(const APInt &Val) const
Return KnownBits based on this, but updated given that the underlying value is known to be greater th...
APInt getSignedMaxValue() const
Return the maximal signed value possible given these KnownBits.
Definition KnownBits.h:152
LLVM_ABI 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...
LLVM_ABI KnownBits ctlz(bool ZeroIsPoison=false) const
Compute known bits for the count of leading zeros.
void setAllConflict()
Make all bits known to be both zero and one.
Definition KnownBits.h:97
KnownBits trunc(unsigned BitWidth) const
Return known bits for a truncation of the value we're tracking.
Definition KnownBits.h:165
bool hasConflict() const
Returns true if there is conflicting information.
Definition KnownBits.h:51
static LLVM_ABI KnownBits fshl(const KnownBits &LHS, const KnownBits &RHS, const APInt &Amt)
Compute known bits for fshl(LHS, RHS, Amt).
static LLVM_ABI std::optional< bool > sge(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGE result.
unsigned countMaxPopulation() const
Returns the maximum number of bits that could be one.
Definition KnownBits.h:303
void setAllZero()
Make all bits known to be zero and discard any previous information.
Definition KnownBits.h:84
LLVM_ABI KnownBits & operator|=(const KnownBits &RHS)
Update known bits based on ORing with RHS.
LLVM_ABI void print(raw_ostream &OS) const
unsigned getBitWidth() const
Get the bit width of this value.
Definition KnownBits.h:44
static LLVM_ABI KnownBits umax(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umax(LHS, RHS).
bool isConstant() const
Returns true if we know the value of all bits.
Definition KnownBits.h:54
LLVM_DUMP_METHOD void dump() const
static LLVM_ABI KnownBits lshr(const KnownBits &LHS, const KnownBits &RHS, bool ShAmtNonZero=false, bool Exact=false)
Compute known bits for lshr(LHS, RHS).
static LLVM_ABI KnownBits abdu(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for abdu(LHS, RHS).
KnownBits extractBits(unsigned NumBits, unsigned BitPosition) const
Return a subset of the known bits from [bitPosition,bitPosition+numBits).
Definition KnownBits.h:239
static LLVM_ABI KnownBits pdep(const KnownBits &Val, const KnownBits &Mask)
Compute known bits for pdep(Val, Mask).
static LLVM_ABI KnownBits avgFloorU(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from APIntOps::avgFloorU.
KnownBits intersectWith(const KnownBits &RHS) const
Returns KnownBits information that is known to be true for both this and RHS.
Definition KnownBits.h:325
static LLVM_ABI KnownBits computeForSubBorrow(const KnownBits &LHS, KnownBits RHS, const KnownBits &Borrow)
Compute known bits results from subtracting RHS from LHS with 1-bit Borrow.
unsigned countMinLeadingZeros() const
Returns the minimum number of leading zero bits.
Definition KnownBits.h:262
APInt getMaxValue() const
Return the maximal unsigned value possible given these KnownBits.
Definition KnownBits.h:146
static LLVM_ABI KnownBits fshr(const KnownBits &LHS, const KnownBits &RHS, const APInt &Amt)
Compute known bits for fshr(LHS, RHS, Amt).
KnownBits()=default
static LLVM_ABI KnownBits abds(KnownBits LHS, KnownBits RHS)
Compute known bits for abds(LHS, RHS).
static LLVM_ABI KnownBits smin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for smin(LHS, RHS).
LLVM_ABI KnownBits & operator&=(const KnownBits &RHS)
Update known bits based on ANDing with RHS.
static LLVM_ABI KnownBits mulhs(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits from sign-extended multiply-hi.
static LLVM_ABI KnownBits srem(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for srem(LHS, RHS).
static LLVM_ABI std::optional< bool > ugt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_UGT result.
static LLVM_ABI KnownBits udiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for udiv(LHS, RHS).
static LLVM_ABI std::optional< bool > slt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLT result.
APInt getMinValue() const
Return the minimal unsigned value possible given these KnownBits.
Definition KnownBits.h:130
static LLVM_ABI 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:62
static LLVM_ABI KnownBits sdiv(const KnownBits &LHS, const KnownBits &RHS, bool Exact=false)
Compute known bits for sdiv(LHS, RHS).
static LLVM_ABI std::optional< bool > ult(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_ULT result.
static LLVM_ABI KnownBits avgFloorS(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from APIntOps::avgFloorS.
static LLVM_ABI std::optional< bool > ule(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_ULE result.
bool isNegative() const
Returns true if this value is known to be negative.
Definition KnownBits.h:103
LLVM_ABI KnownBits truncSSat(unsigned BitWidth) const
Truncate with signed saturation (signed input -> signed output)
static LLVM_ABI 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:55
unsigned countMaxLeadingZeros() const
Returns the maximum number of leading zero bits possible.
Definition KnownBits.h:294
static LLVM_ABI KnownBits avgCeilU(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from APIntOps::avgCeilU.
static LLVM_ABI KnownBits uadd_sat(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from llvm.uadd.sat(LHS, RHS)
static LLVM_ABI KnownBits mul(const KnownBits &LHS, const KnownBits &RHS, bool NoUndefSelfMultiply=false)
Compute known bits resulting from multiplying LHS and RHS.
static LLVM_ABI KnownBits clmul(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for clmul(LHS, RHS).
LLVM_ABI KnownBits abs(bool IntMinIsPoison=false) const
Compute known bits for the absolute value.
static LLVM_ABI std::optional< bool > sle(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SLE result.
static LLVM_ABI std::optional< bool > sgt(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_SGT result.
unsigned countMinPopulation() const
Returns the number of bits known to be one.
Definition KnownBits.h:300
LLVM_ABI KnownBits truncUSat(unsigned BitWidth) const
Truncate with unsigned saturation (unsigned input -> unsigned output)
static LLVM_ABI std::optional< bool > uge(const KnownBits &LHS, const KnownBits &RHS)
Determine if these known bits always give the same ICMP_UGE result.
APInt getSignedMinValue() const
Return the minimal signed value possible given these KnownBits.
Definition KnownBits.h:136
LLVM_ABI KnownBits & operator^=(const KnownBits &RHS)
Update known bits based on XORing with RHS.
static LLVM_ABI KnownBits shl(const KnownBits &LHS, const KnownBits &RHS, bool NUW=false, bool NSW=false, bool ShAmtNonZero=false)
Compute known bits for shl(LHS, RHS).
static LLVM_ABI KnownBits umin(const KnownBits &LHS, const KnownBits &RHS)
Compute known bits for umin(LHS, RHS).
LLVM_ABI KnownBits truncSSatU(unsigned BitWidth) const
Truncate with signed saturation to unsigned (signed input -> unsigned output)
static LLVM_ABI KnownBits pext(const KnownBits &Val, const KnownBits &Mask)
Compute known bits for pext(Val, Mask).
static LLVM_ABI KnownBits avgCeilS(const KnownBits &LHS, const KnownBits &RHS)
Compute knownbits resulting from APIntOps::avgCeilS.
const APInt & getConstant() const
Returns the value when all bits have a known value.
Definition KnownBits.h:58