Age | Commit message (Collapse) | Author | Files | Lines |
|
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.
|
|
|
|
Rewrite the signed functions in terms of the unsigned ones which are
already optimal.
|
|
Adding optimality test to `add`, `sub`, `avgCeilU` and `avgFloorU`
|
|
|
|
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.
|
|
Allow KnownBits to represent "always poison" values via conflict.
close: #94436
|
|
This PR is to address the issue #84640
|
|
|
|
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
|
|
This de-duplicates the code that prints useful information when a test
fails.
|
|
Use bool instead of function_ref.
|
|
Fixes #84212
|
|
Fixes #84207
|
|
|
|
testBinaryOpExhaustive callbacks if we can just use the raw KnownBits/APIntOps function reference. NFCI.
|
|
-> 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
|
|
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.
|
|
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
|
|
Just some improvements that should hopefully strengthen analysis.
Closes #83580
|
|
|
|
|
|
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.
|
|
- [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>
|
|
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.
|
|
Differential Revision: https://reviews.llvm.org/D151456
|
|
Implement precise nuw/nsw support in the KnownBits implementation,
replacing the rather crude handling in ValueTracking.
Differential Revision: https://reviews.llvm.org/D151208
|
|
And make sure udiv() Exact does not produce conflicts.
|
|
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
|
|
`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
|
|
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
|
|
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
|
|
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.
|
|
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
|
|
|
|
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.
|
|
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D142519
|
|
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.
|
|
https://discourse.llvm.org/t/deprecating-llvm-optional-x-hasvalue-getvalue-getvalueor/63716
|
|
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
|
|
|
|
|
|
This reverts commit aa8feeefd3ac6c78ee8f67bf033976fc7d68bc6d.
|
|
|
|
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
|
|
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
|
|
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
|
|
|
|
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
|
|
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
|