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