aboutsummaryrefslogtreecommitdiff
path: root/llvm/unittests/Support/KnownBitsTest.cpp
AgeCommit message (Collapse)AuthorFilesLines
2024-11-05[KnownBits] Make `{s,u}{add,sub}_sat` optimal (#113096)goldsteinn1-8/+4
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-22[KnownBits] Check that mul is optimal for low order bits (#113316)Jay Foad1-0/+34
2024-10-01[KnownBits] Make `avg{Ceil,Floor}S` optimal (#110688)Jay Foad1-4/+3
Rewrite the signed functions in terms of the unsigned ones which are already optimal.
2024-09-30[KnownBitsTest] Add optimality tests to some optimal impls; NFCNoah Goldstein1-10/+7
Adding optimality test to `add`, `sub`, `avgCeilU` and `avgFloorU`
2024-08-12[KnownBits] Add KnownBits::add and KnownBits::sub helper wrappers. (#99468)Simon Pilgrim1-0/+14
2024-06-10[KnownBits] re-introduce RefinePosionToZero in unittest (#94848)c8ef1-17/+24
Context: https://github.com/llvm/llvm-project/pull/94568/files#r1631349423 - Reintroduce the RefinePositionToZero path in the unittest. - Adjust some inline function argument hints to match the same style.
2024-06-07[KnownBits] Remove `hasConflict()` assertions (#94568)c8ef1-31/+46
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/+12
This PR is to address the issue #84640
2024-04-22[KnownBitsTest] Standardize variable names in exhaustive testsJay Foad1-41/+41
2024-04-22[KnownBitsTest] Print name of function when exhaustive tests fail (#89588)Jay Foad1-38/+68
When exhaustive unary/binary tests fail, print the name of the function being tested as well as the values of the inputs and outputs. Example of a simulated failure in testing "udiv exact": unittests/Support/KnownBitsTest.cpp:99: Failure Value of: checkResult(Name, Exact, Computed, {Known1, Known2}, CheckOptimality) Actual: false (udiv exact: Inputs = ???1, ????, Computed = ???1, Exact = 0???) Expected: true
2024-04-22[KnownBitsTest] Common up isCorrect and isOptimal. NFC. (#89585)Jay Foad1-40/+25
This de-duplicates the code that prints useful information when a test fails.
2024-04-19[KnownBits] Simplify optimality checking in unit tests. NFC. (#89368)Jay Foad1-43/+29
Use bool instead of function_ref.
2024-04-18[KnownBits] Make abdu and abds optimal (#89081)Jay Foad1-56/+2
Fixes #84212
2024-04-02[ADT] Add signed and unsigned mulh to APInt (#84719)Atousa Duprat1-8/+2
Fixes #84207
2024-03-19[KnownBits] Remove useless lambdas from unit testJay Foad1-12/+4
2024-03-14[Support] KnownBitsTest - don't bother creating lambdas in ↵Simon Pilgrim1-46/+12
testBinaryOpExhaustive callbacks if we can just use the raw KnownBits/APIntOps function reference. NFCI.
2024-03-12[Support] Add KnownBits::abds signed absolute difference and rename absdiff ↵Simon Pilgrim1-6/+38
-> 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-12[ADT] Add APIntOps::abds signed absolute difference and rename absdiff -> ↵Simon Pilgrim1-3/+1
abdu (#84791) When I created APIntOps::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 APIntOps::abds implementation and renamed APIntOps::absdiff to APIntOps::abdu. Given that APIntOps::absdiff is so young I don't think we need to create a deprecation wrapper, but I can if anyone thinks it important. I'll do a KnownBits rename patch after this.
2024-03-11[KnownBits] Implement knownbits `lshr`/`ashr` with exact flagNoah Goldstein1-0/+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-05[KnownBits] Make `nuw` and `nsw` support in `computeForAddSub` optimalNoah Goldstein1-12/+62
Just some improvements that should hopefully strengthen analysis. Closes #83580
2024-03-05[KnownBits] Add API for `nuw` flag in `computeForAddSub`; NFCNoah Goldstein1-3/+3
2024-03-01[unittest] Fix -Wsign-compare warnings in KnownBits.cpp after #82354Fangrui Song1-4/+4
2024-03-01[KnownBits] Add KnownBits::absdiff to compute the absolute difference of 2 ↵Simon Pilgrim1-1/+34
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/+31
- [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-05-31[KnownBits] Also test 1-bit values in exhaustive tests (NFC)Nikita Popov1-45/+48
Similar to what we do with ConstantRanges, also test 1-bit values in exhaustive tests, as these often expose special conditions. This would have exposed the assertion failure fixed in D151788 earlier.
2023-05-25[KnownBits] Check functions that return zero for poison resultsJay Foad1-14/+27
Differential Revision: https://reviews.llvm.org/D151456
2023-05-25[KnownBits] Add support for nuw/nsw on shiftsNikita Popov1-0/+35
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] 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-1/+32
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-14/+9
`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-16[KnownBits] Improve `KnownBits::udiv`Noah Goldstein1-0/+10
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/+21
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-0/+14
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] Make shl/lshr/ashr implementations optimalNikita Popov1-10/+0
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] Remove stray semicolonsJay Foad1-2/+2
2023-05-15[KnownBitsTest] Align with ConstantRange test infrastructure (NFC)Nikita Popov1-222/+257
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-02-18[KnownBits] Add blsi and blsmskJay Foad1-0/+20
Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D142519
2022-12-16std::optional::value => operator*/operator->Fangrui Song1-21/+21
value() has undesired exception checking semantics and calls __throw_bad_optional_access in libc++. Moreover, the API is unavailable without _LIBCPP_NO_EXCEPTIONS on older Mach-O platforms (see _LIBCPP_AVAILABILITY_BAD_OPTIONAL_ACCESS). This commit fixes LLVMAnalysis and its dependencies.
2022-12-16[Support] llvm::Optional => std::optionalFangrui Song1-10/+10
https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
2022-07-29[Support] Add KnownBits::concat methodSimon Pilgrim1-0/+25
Add a method for the various cases where we need to concatenate 2 KnownBits together (BUILD_PAIR and SHIFT_PARTS in particular) - uses the existing APInt::concat 'HiBits.concat(LoBits)' convention Differential Revision: https://reviews.llvm.org/D130557
2022-07-13[llvm] Use value instead of getValue (NFC)Kazu Hirata1-21/+21
2022-07-12[llvm] Use has_value instead of hasValue (NFC)Kazu Hirata1-32/+32
2022-06-25Revert "Don't use Optional::hasValue (NFC)"Kazu Hirata1-32/+32
This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d.
2022-06-25Don't use Optional::hasValue (NFC)Kazu Hirata1-32/+32
2022-05-17[KnownBits] Add operator==Nikita Popov1-24/+14
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-01-03[ValueTracking][SelectionDAG] Rename ↵Craig Topper1-3/+3
ComputeMinSignedBits->ComputeMaxSignificantBits. NFC This function returns an upper bound on the number of bits needed to represent the signed value. Use "Max" to match similar functions in KnownBits like countMaxActiveBits. Rename APInt::getMinSignedBits->getSignificantBits. Keeping the old name around to keep this patch size down. Will do a bulk rename as follow up. Rename KnownBits::countMaxSignedBits->countMaxSignificantBits. Reviewed By: lebedev.ri, RKSimon, spatel Differential Revision: https://reviews.llvm.org/D116522
2022-01-02[Support] Add KnownBits::countMaxSignedBits(). Make ↵Craig Topper1-0/+11
KnownBits::countMinSignBits() always return at least 1. Even if we don't have any known bits, we can assume that there is at least 1 sign bit. This is consistent with ComputeNumSignBits which always returns at least 1. Add KnownBits::countMaxSignedBits() which computes the number of bits needed to represent all signed values with those known bits. This is the signed equivalent of countMaxActiveBits(). Split from D116469. Reviewed By: lebedev.ri Differential Revision: https://reviews.llvm.org/D116500
2021-10-11[KnownBits] Introduce `countMaxActiveBits()` and use it in a few placesRoman Lebedev1-0/+11
2021-10-04[APInt] Stop using soft-deprecated constructors and methods in llvm. NFC.Jay Foad1-1/+1
Stop using APInt constructors and methods that were soft-deprecated in D109483. This fixes all the uses I found in llvm, except for the APInt unit tests which should still test the deprecated methods. Differential Revision: https://reviews.llvm.org/D110807
2021-09-09[APInt] Normalize naming on keep constructors / predicate methods.Chris Lattner1-2/+2
This renames the primary methods for creating a zero value to `getZero` instead of `getNullValue` and renames predicates like `isAllOnesValue` to simply `isAllOnes`. This achieves two things: 1) This starts standardizing predicates across the LLVM codebase, following (in this case) ConstantInt. The word "Value" doesn't convey anything of merit, and is missing in some of the other things. 2) Calling an integer "null" doesn't make any sense. The original sin here is mine and I've regretted it for years. This moves us to calling it "zero" instead, which is correct! APInt is widely used and I don't think anyone is keen to take massive source breakage on anything so core, at least not all in one go. As such, this doesn't actually delete any entrypoints, it "soft deprecates" them with a comment. Included in this patch are changes to a bunch of the codebase, but there are more. We should normalize SelectionDAG and other APIs as well, which would make the API change more mechanical. Differential Revision: https://reviews.llvm.org/D109483
generated by cgit v1.1 at 2025-07-25 04:55:58 +0000