aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Support/KnownBits.cpp
AgeCommit message (Collapse)AuthorFilesLines
10 days[KnownBits] Add setAllConflict to set all bits in Zero and One. NFC (#159815)Craig Topper1-6/+3
This is a common pattern to initialize Knownbits that occurs before loops that call intersectWith.
2025-08-28[KnownBits] Add operator<<=(unsigned) and operator>>=(unsigned). NFC (#155751)Craig Topper1-2/+1
Add operators to shift left or right and insert unknown bits.
2025-08-11[InstCombine] Add additional known bits info for self multiply (#151202)Macsen Casaus1-5/+13
Closes #151043 https://alive2.llvm.org/ce/z/JyMSk8
2025-05-14[llvm] properly guard dump methods in Support lib classes (#139938)Andrew Rogers1-1/+4
## Purpose Add proper preprocessor guards for all `dump()` methods in the LLVM support library. This change ensures these methods are not part of the public ABI for release builds. ## Overview * Annotates all `dump` methods in Support and ADT source with the `LLVM_DUMP_METHOD` macro. * Conditionally includes all `dump` method definitions in Support and ADT source so they are only present on debug/assert builds and when `LLVM_ENABLE_DUMP` is explicitly defined. NOTE: For many of these `dump` methods, the implementation was already properly guarded but the declaration in the header file was not. ## Background This PR is a redo of #139804 with some changes to fix clang and unit test build breaks. This issue was raised in comments on #136629. I am addressing it as a separate change since it is independent from the changes being made in that PR. According to [this documentation](https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Support/Compiler.h#L637), `dump` methods should be annotated with `LLVM_DUMP_METHOD` and conditionally included as follows: ``` #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void dump() const; #endif ``` ## Validation * Local release build succeeds. * CI
2025-05-14Revert "[llvm] properly guard dump methods in Support lib classes" (#139927)Andrew Rogers1-4/+1
Reverts llvm/llvm-project#139804
2025-05-14[llvm] properly guard dump methods in Support lib classes (#139804)Andrew Rogers1-1/+4
## Purpose Add proper preprocessor guards for all `dump()` methods in the LLVM support library. This change ensures these methods are not part of the public ABI for release builds. ## Overview * Annotates all `dump` methods in Support and ADT source with the `LLVM_DUMP_METHOD` macro. * Conditionally includes all `dump` method definitions in Support and ADT source so they are only present on debug/assert builds and when `LLVM_ENABLE_DUMP` is explicitly defined. NOTE: For many of these `dump` methods, the implementation was already properly guarded but the declaration in the header file was not. ## Background This issue was raised in comments on #136629. I am addressing it as a separate change since it is independent from the changes being made in that PR. According to [this documentation](https://github.com/llvm/llvm-project/blob/main/llvm/include/llvm/Support/Compiler.h#L637), `dump` methods should be annotated with `LLVM_DUMP_METHOD` and conditionally included as follows: ``` #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) LLVM_DUMP_METHOD void dump() const; #endif ``` ## Validation * Local release build succeeds. * CI
2024-11-05[KnownBits] Make `{s,u}{add,sub}_sat` optimal (#113096)goldsteinn1-65/+77
Changes are: 1) Make signed-overflow detection optimal 2) For signed-overflow, try to rule out direction even if we can't totally rule out overflow. 3) Intersect add/sub assuming no overflow with possible overflow clamping values as opposed to add/sub without the assumption.
2024-10-01[KnownBits] Make `avg{Ceil,Floor}S` optimal (#110688)Jay Foad1-22/+17
Rewrite the signed functions in terms of the unsigned ones which are already optimal.
2024-09-27KnownBits: refine srem for high-bits (#109121)Ramkumar Ramachandra1-3/+7
KnownBits::srem does not correctly set the leader zero-bits, omitting the fact that LHS may be known-negative or known-non-negative. Fix this. Alive2 proof: https://alive2.llvm.org/ce/z/Ugh-Dq
2024-06-13[KnownBits] avgCompute - don't create on-the-fly Carry. NFC.Simon Pilgrim1-2/+2
Use the internal computeForAddCarry directly since we know the exact values of the carry bit.
2024-06-07[KnownBits] Remove `hasConflict()` assertions (#94568)c8ef1-28/+5
Allow KnownBits to represent "always poison" values via conflict. close: #94436
2024-05-19[llvm] Add KnownBits implementations for avgFloor and avgCeil (#86445)Nhat Nguyen1-0/+31
This PR is to address the issue #84640
2024-04-18[KnownBits] Make abdu and abds optimal (#89081)Jay Foad1-27/+39
Fixes #84212
2024-03-12[Support] Add KnownBits::abds signed absolute difference and rename absdiff ↵Simon Pilgrim1-2/+21
-> abdu (#84897) When I created KnownBits::absdiff, I totally missed that we already have ISD::ABDS/ABDU nodes, and we use this term in other places/targets as well. I've added the KnownBits::abds implementation and renamed KnownBits::absdiff to KnownBits::abdu. Followup to #84791
2024-03-11[KnownBits] Implement knownbits `lshr`/`ashr` with exact flagNoah Goldstein1-2/+26
The exact flag basically allows us to set an upper bound on shift amount when we have a known 1 in `LHS`. Typically we deduce exact using knownbits (on non-exact incoming shifts), so this is particularly impactful, but may be useful in some circumstances. Closes #84254
2024-03-11[KnownBits] Add API support for `exact` in `lshr`/`ashr`; NFCNoah Goldstein1-2/+2
2024-03-05[KnownBits] Make `nuw` and `nsw` support in `computeForAddSub` optimalNoah Goldstein1-23/+78
Just some improvements that should hopefully strengthen analysis. Closes #83580
2024-03-05[KnownBits] Add API for `nuw` flag in `computeForAddSub`; NFCNoah Goldstein1-6/+10
2024-03-01[KnownBits] Add KnownBits::absdiff to compute the absolute difference of 2 ↵Simon Pilgrim1-0/+16
unsigned values (#82354) Equivalent to "umax(A, B) - umin(A, B)" This is just an initial correctness implementation, hopefully we can make this optimal in the future.
2023-10-18[Support] Add KnownBits::computeForSubBorrow (#67788)Christian Kissig1-0/+12
- [Support] Add KnownBits::computeForSubBorrow - [CodeGen] Implement USUBC, USUBO_CARRY, and SSUBO_CARRY with KnownBits::computeForSubBorrow - [CodeGen] Compute unknown bits for Carry/Borrow for ADD/SUB - [CodeGen] Compute known bits of Carry/Borrow for UADDO, SADDO, USUBO, and SSUBO Fixes #65893 --------- Co-authored-by: Shafik Yaghmour <shafik@users.noreply.github.com>
2023-06-06[KnownBits] Factor out and improve the lowbit computation for {u,s}divNoah Goldstein1-28/+38
There are some new cases if the division is `exact`: 1: If `TZ(LHS) == TZ(RHS)` then the result is always Odd 2: If `TZ(LHS) > TZ(RHS)` then the `TZ(LHS)-TZ(RHS)` bits of the result are zero. Proofs: https://alive2.llvm.org/ce/z/3rAZqF As well, return zero in known poison cases to be consistent rather than just working about the bits we are changing. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D150923
2023-06-06[KnownBits] Return `0` for poison {s,u}div inputsNoah Goldstein1-0/+14
It seems consistent to always return zero for known poison rather than varying the value. We do the same elsewhere. Differential Revision: https://reviews.llvm.org/D150922
2023-06-06[KnownBits] Cleanup some misspelling / logic in {u,s}divNoah Goldstein1-31/+31
Chronically misspelled 'denominator' as 'denuminator' and a few other cases. On the logic side, no longer require `RHS` to be strictly positive in `sdiv`. This in turn means we need to handle a possible zero `denom` in the APInt division. Differential Revision: https://reviews.llvm.org/D150921
2023-06-01[ValueTracking] Directly use KnownBits shift functionsNikita Popov1-3/+11
Make ValueTracking directly call the KnownBits shift helpers, which provides more precise results. Unfortunately, ValueTracking has a special case where sometimes we determine non-zero shift amounts using isKnownNonZero(). I have my doubts about the usefulness of that special-case (it is only tested in a single unit test), but I've reproduced the special-case via an extra parameter to the KnownBits methods. Differential Revision: https://reviews.llvm.org/D151816
2023-05-26[KnownBits] Partially synchronize shift implementations (NFC)Nikita Popov1-80/+44
And remove some bits of effectively dead code.
2023-05-26[KnownBits] Add fast-path for shl with unknown shift amount (NFC)Nikita Popov1-27/+41
We currently don't call into KnownBits::shl() from ValueTracking if the shift amount is unknown. If we do try to do so, we get significant compile-time regressions, because evaluating all 64 shift amounts if quite expensive, and mostly pointless in this case. Add a fast-path for the case where the shift amount is the full [0, BitWidth-1] range. This primarily requires a more accurate estimate of the max shift amount, to avoid taking the fast-path in too many cases. Differential Revision: https://reviews.llvm.org/D151540
2023-05-25[KnownBits] Simplify shl. NFCI.Jay Foad1-47/+33
Differential Revision: https://reviews.llvm.org/D151421
2023-05-25[KnownBits] Add support for nuw/nsw on shiftsNikita Popov1-13/+50
Implement precise nuw/nsw support in the KnownBits implementation, replacing the rather crude handling in ValueTracking. Differential Revision: https://reviews.llvm.org/D151208
2023-05-24[KnownBits] Reduce number of overflow checks for uadd/sub_sat (NFCI)Nikita Popov1-15/+11
Only check for overflow on the min/max values, don't also check for predicates in addition to that.
2023-05-24[KnownBits] Use early return for unknown LHS for shifts (NFC)Nikita Popov1-94/+91
Make it clear that the leading/trailing zeros handling is only relevant for the unknown LHS case, which is a fast path to avoid the full shift amount loop in cases where it would not produce better results.
2023-05-24[KnownBits] Check for conflict-freedom in exhaustive testsNikita Popov1-0/+2
And make sure udiv() Exact does not produce conflicts.
2023-05-23[KnownBits] Add implementations for saturating add/sub functionsNoah Goldstein1-0/+165
These where previously missing. Even in the case where overflow is indeterminate we can still deduce some of the low/high bits. Reviewed By: RKSimon Differential Revision: https://reviews.llvm.org/D150102
2023-05-23[KnownBits] Improve implementation of `KnownBits::abs`Noah Goldstein1-8/+47
`abs` preserves the lowest set bit, so if we know the lowest set bit, set it in the output. As well, implement the case where the operand is known negative. Reviewed By: foad, RKSimon Differential Revision: https://reviews.llvm.org/D150100
2023-05-23[KnownBits] Return zero instead of unknown for always poison shiftsNikita Popov1-6/+12
For always poison shifts, any KnownBits return value is valid. Currently we return unknown, but returning zero is generally more profitable. We had some code in ValueTracking that tried to do this, but was actually dead code. Differential Revision: https://reviews.llvm.org/D150648
2023-05-16[KnownBits] Improve `KnownBits::udiv`Noah Goldstein1-9/+21
We can more precisely determine the upper bits doing `MaxNum / MinDenum` as opposed to only using the MSB. As well, if the `exact` flag is set, we can sometimes determine some of the low-bits. Differential Revision: https://reviews.llvm.org/D150094
2023-05-16[KnownBits] Add implementation for `KnownBits::sdiv`Noah Goldstein1-0/+68
Can figure out some of the upper bits (similiar to `udiv`) if we know the sign of the inputs. As well, if we have the `exact` flag we can sometimes determine some low-bits. Differential Revision: https://reviews.llvm.org/D150093
2023-05-16[KnownBits] Handle shifts over wide typesNikita Popov1-6/+6
Do not assert if the bit width is larger than 64 bits. This case is currently hidden from the IR layer by other checks, but gets exposed with future changes.
2023-05-16[KnownBits] Define and use intersectWith and unionWithJay Foad1-4/+4
Define intersectWith and unionWith as two complementary ways of combining KnownBits. The names are chosen for consistency with ConstantRange. Deprecate commonBits as a synonym for intersectWith. Differential Revision: https://reviews.llvm.org/D150443
2023-05-16[KnownBits] Make shl/lshr/ashr implementations optimalNikita Popov1-24/+32
The implementations for shifts were suboptimal in the case where the max shift amount was >= bitwidth. In that case we should still use the usual code clamped to BitWidth-1 rather than just giving up entirely. Additionally, there was an implementation bug where the known zero bits for the individual shift amounts were not set in the shl/lshr implementations. I think after these changes, we'll be able to drop some of the code in ValueTracking which *also* evaluates all possible shift amounts and has been papering over this issue. For the "all poison" case I've opted to return an unknown value for now. It would be better to return zero, but this has fairly substantial test fallout, so I figured it's best to not mix it into this change. (The "correct" return value would be a conflict, but given that a lot of our APIs assert conflict-freedom, that's probably not the best idea to actually return.) Differential Revision: https://reviews.llvm.org/D150587
2023-05-15[KnownBitsTest] Align with ConstantRange test infrastructure (NFC)Nikita Popov1-1/+12
Align the way we perform exhaustive tests for KnownBits with what we do for ConstantRange. Test each case separately by specifying a function on KnownBits and one on APInts. Additionally, specify a callback that determines which cases are supposed to be optimal, rather than only correct. Unlike the ConstantRange case there is a well-defined, unique notion of optimality for KnownBits. If a failure occurs, print out the inputs, computed result and exact result. Adjust the printing function to produce the output in a format that is meaningful for KnownBits, i.e. print the actual known bits, using ? to signify unknowns and ! to signify conflicts.
2023-05-07[KnownBits] Improve `KnownBits::rem(X, Y)` in cases where we can deduce ↵Noah Goldstein1-12/+19
low-bits of output The first `cttz(Y)` bits in `X` are translated 1-1 in the output. Alive2 Links: https://alive2.llvm.org/ce/z/Qc47p7 https://alive2.llvm.org/ce/z/19ut5H Reviewed By: RKSimon Differential Revision: https://reviews.llvm.org/D149421
2023-02-19Use APInt::count{l,r}_{zero,one} (NFC)Kazu Hirata1-4/+4
2023-02-18[KnownBits] Add blsi and blsmskJay Foad1-0/+21
Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D142519
2022-12-16[Support] llvm::Optional => std::optionalFangrui Song1-22/+22
https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
2022-12-02[llvm] Use std::nullopt instead of None (NFC)Kazu Hirata1-6/+6
This patch mechanically replaces None with std::nullopt where the compiler would warn if None were deprecated. The intent is to reduce the amount of manual work required in migrating from Optional to std::optional. This is part of an effort to migrate from llvm::Optional to std::optional: https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
2022-06-20[llvm] Don't use Optional::getValue (NFC)Kazu Hirata1-3/+3
2022-05-17[KnownBits] Add operator==Nikita Popov1-3/+2
Checking whether two KnownBits are the same is somewhat common, mainly in test code. I don't think there is a lot of room for confusion with "determine what the KnownBits for an icmp eq would be", as that has a different result type (this is what the eq() method implements, which returns Optional<bool>). Differential Revision: https://reviews.llvm.org/D125692
2022-02-06[KnownBits] Add support for X*X self-multiplication (update)Simon Pilgrim1-4/+5
Rename the SelfMultiply argument to make it clearer that the argument must not be undef Differential Revision: https://reviews.llvm.org/D108992
2021-12-20[Support] improve known bits analysis for leading zeros of multiplySanjay Patel1-11/+12
Instead of summing leading zeros on the input operands, multiply the max possible values of those inputs and count the leading zeros of the result. This can give us an extra zero bit (typically in cases where one of the operands is a known constant). This allows folding away the remaining 'add' ops in the motivating bug (modeled in the PhaseOrdering IR test): https://github.com/llvm/llvm-project/issues/48399 Fixes #48399 Differential Revision: https://reviews.llvm.org/D115969
2021-12-08[Support] improve known bits analysis for multiply by power-of-2 (1 set bit)Sanjay Patel1-1/+8
This can be viewed as recognizing that multiply-by-power-of-2 doesn't have a carry into the top bit of an M-bit * N-bit number. Enhancing canonicalization of mul -> select might also handle some of these if we were ok with increasing instruction count with casts in some cases. This doesn't help https://llvm.org/PR49055 , but it's a simpler pattern that we miss. Note: "-sccp" already gets these examples using a constant range analysis. Differential Revision: https://reviews.llvm.org/D114962
generated by cgit v1.1 at 2025-09-29 17:03:53 +0000