| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
|
|
This introduces a new `ptrtoaddr` instruction which is similar to
`ptrtoint` but has two differences:
1) Unlike `ptrtoint`, `ptrtoaddr` does not capture provenance
2) `ptrtoaddr` only extracts (and then extends/truncates) the low
index-width bits of the pointer
For most architectures, difference 2) does not matter since index (address)
width and pointer representation width are the same, but this does make a
difference for architectures that have pointers that aren't just plain
integer addresses such as AMDGPU fat pointers or CHERI capabilities.
This commit introduces textual and bitcode IR support as well as basic code
generation, but optimization passes do not handle the new instruction yet
so it may result in worse code than using ptrtoint. Follow-up changes will
update capture tracking, etc. for the new instruction.
RFC: https://discourse.llvm.org/t/clarifiying-the-semantics-of-ptrtoint/83987/54
Reviewed By: nikic
Pull Request: https://github.com/llvm/llvm-project/pull/139357
|
|
Exhaustively test makeExactICmpRegion by comparing makeAllowedICmpRegion
against makeSatisfyingICmpRegion for all APInts.
|
|
Factor out some code that splits a ConstantRange into positive and
negative components, introducing ConstantRange::splitPosNeg.
|
|
(or) (#120352)
Fixes #118108.
Co-author: Yingwei Zheng (@dtcxzyw)
|
|
De-duplicate the functions getSignedPredicate and getUnsignedPredicate,
nearly identical versions of which were present in CmpInst and ICmpInst,
creating less confusion.
|
|
This handles the edge case where BitWidth is 1 and doing the
increment gets a value that's not valid in that width, while we
just want wrap-around.
Split out of https://github.com/llvm/llvm-project/pull/80309.
|
|
Closes https://github.com/dtcxzyw/llvm-tools/issues/22.
|
|
This patch adds initial support for `ConstantRange:: shlWithNoWrap` to
fold https://github.com/dtcxzyw/llvm-tools/issues/22. However, this
patch cannot fix the original issue. Improvements will be submitted in subsequent patches.
|
|
Alive2: https://alive2.llvm.org/ce/z/byzmsV
|
|
These are pretty hot code paths, so provide direct implementations
for them, instead of going through makeSatisfyingICmpRegion().
|
|
ConstantRange has queries for isAllNegative and isAllNonNegative, but
misses a query for isAllPositive. Add this function.
|
|
Extend `V & Mask != 0` for non-zero constants if satisfiable, when
retrieving constraint value information from a non-equality comparison.
Proof: https://alive2.llvm.org/ce/z/dc5BeT.
Motivating example: https://github.com/gcc-mirror/gcc/blob/master/gcc/testsuite/gcc.dg/tree-ssa/vrp76.c.
|
|
Allow KnownBits to represent "always poison" values via conflict.
close: #94436
|
|
Introduce support for computing multiplication ranges when nowrap
flags are known. This is achieved by intersecting the multiplication
range with the saturating one. Note that we may still conservatively
return overdefined when handling non-wrapped/non-sign-wrapped ranges.
|
|
We were passing the min and max values of the range to the ConstantRange
constructor, but the constructor expects the upper bound to 1 more than
the max value so we need to add 1.
We also need to use getNonEmpty so that passing 0, 0 to the constructor
creates a full range rather than an empty range. And passing smin,
smax+1 doesn't cause an assertion.
I believe this fixes at least some of the reason #79158 was reverted.
|
|
`ConstantRange::binaryXor` gives poor results as it currently depends on
`KnownBits::operator^`.
Since `sub A, B` is canonicalized into `xor A, B` if `B` is the subset
of `A`, this patch reverts the transform in `ConstantRange::binaryXor`,
which will give better results.
Alive2: https://alive2.llvm.org/ce/z/bmTMV9
Fixes #79696.
|
|
This patch adds support for `Intrinsic::cttz` in ConstantRange. It
calculates the range in O(1) with the LCP-based method.
Migrated from https://reviews.llvm.org/D153505.
|
|
This patch adds support for `Intrinsic::ctpop` in ConstantRange. It
calculates the range in O(1) with the LCP-based method.
Migrated from https://reviews.llvm.org/D153505.
|
|
Don't call makeExactMulNSWRegion() twice with the same value.
|
|
This differs from the positive case in that shifting by a larger
amount makes the result smaller, not larger.
|
|
These are pretty common in SCEV, so make sure we get a precise
result by mapping to the sub() operation.
|
|
Note that getMinSignedBits has been soft-deprecated in favor of
getSignificantBits.
|
|
|
|
Introduce ConstantRange support for ctlz intrinsic, including
exhaustive testing. Among other things, LVI may now be able to
propagate information about cltz constant ranges lattice values.
Differential Revision: https://reviews.llvm.org/D142234
|
|
For a full range input, we would produce an empty range instead
of a full range. The change to the SMin.isNonNegative() branch is
an optimality fix, because we should account for the potentially
discarded SMin value in the IntMinIsPoison case.
Change TestUnaryOpExhaustive to test both 4 and 1 bits, to both
cover this specific case in unit tests, and make sure all other
unary operations deal with 1-bit inputs correctly.
Fixes https://github.com/llvm/llvm-project/issues/59887.
|
|
|
|
The special case for V=1 was incorrect for one bit types, where
1 is also -1. Remove it, and use getNonEmpty() to handle the full
range case instead.
Adjust the exhaustive nowrap tests to test both 5 bit and 1 bit
types.
Fixes https://github.com/llvm/llvm-project/issues/59301.
|
|
Many llvm/IR/* files have been migrated by other contributors.
This migrates most remaining files.
|
|
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
|
|
Signed one bit values can only be -1 or 0, not positive. The code
was interpreting the 1 as -1 and intersecting with a full range
rather than an empty one.
Fixes https://github.com/llvm/llvm-project/issues/56333.
|
|
This recommits https://reviews.llvm.org/rG6990e7477d24ff585ae86549f5280f0be65422a6
as the problematic test has been updated updated in
https://reviews.llvm.org/rG3bd112c720dc614a59e3f34ebf9b45075037bfa0.
|
|
This reverts commit 6990e7477d24ff585ae86549f5280f0be65422a6.
This change was causing the test compiler-rt/test/fuzzer/merge_two_step.test to fail on
our internal bot as well as other build bots such as https://lab.llvm.org/buildbot/#/builders/179/builds/3712.
|
|
This diff adjusts binaryOr to take advantage of the analysis
based on KnownBits.
Differential revision: https://reviews.llvm.org/D125933
Test plan:
1/ ninja check-llvm
2/ ninja check-llvm-unit
|
|
Most clients only used these methods because they wanted to be able to
extend or truncate to the same bit width (which is a no-op). Now that
the standard zext, sext and trunc allow this, there is no reason to use
the OrSelf versions.
The OrSelf versions additionally have the strange behaviour of allowing
extending to a *smaller* width, or truncating to a *larger* width, which
are also treated as no-ops. A small amount of client code relied on this
(ConstantRange::castOp and MicrosoftCXXNameMangler::mangleNumber) and
needed rewriting.
Differential Revision: https://reviews.llvm.org/D125557
|
|
This diff adjusts binaryAnd to take advantage of the analysis
based on KnownBits.
Differential revision: https://reviews.llvm.org/D125603
Test plan:
1/ ninja check-llvm
2/ ninja check-llvm-unit
|
|
This allows us to compute known high bits. It's not optimal, but
better than nothing.
|
|
Add toKnownBits() method to mirror fromKnownBits(). We know the
top bits that are constant between min and max.
The return value for an empty range is chosen to be conservative.
|
|
For some optimizations on comparisons it's necessary that the
union/intersect is exact and not a superset. Add methods that
return Optional<ConstantRange> only if the result is exact.
For the sake of simplicity this is implemented by comparing
the subset and superset approximations for now, but it should be
possible to do this more directly, as unionWith() and intersectWith()
already distinguish the cases where the result is imprecise for the
preferred range type functionality.
|
|
From an API perspective, it does not make a lot of sense that 0
is not a valid argument to this function. Add the exact check needed
to support it.
|
|
Add a variant of getEquivalentICmp() that produces an optional
offset. This allows us to create an equivalent icmp for all ranges.
Use this in the with.overflow folding code, which was doing this
adjustment separately -- this clarifies that the fold will indeed
always apply.
|
|
For certain combination of LHS and RHS constant ranges,
the signedness of the relational comparison predicate is irrelevant.
This implements complete and precise model for all predicates,
as confirmed by the brute-force tests. I'm not sure if there are
some more cases that we can handle here.
In a follow-up, CVP will make use of this.
Reviewed By: nikic
Differential Revision: https://reviews.llvm.org/D90924
|
|
Base the implementation on the APInt smul_sat() implementation,
which is much more efficient than performing calculations in
double the bitwidth.
|
|
The multiply() implementation is very slow -- it performs six
multiplications in double the bitwidth, which means that it will
typically work on allocated APInts and bypass fast-path
implementations. Add an additional implementation that doesn't
try to produce anything better than a full range if overflow is
possible. At least for the BasicAA use-case, we really don't care
about more precise modeling of overflow behavior. The current
use of multiply() is fine while the implementation is limited to
a single index, but extending it to the multiple-index case makes
the compile-time impact untenable.
|
|
For the common case where the shift amount is constant (a single
element range) we can easily compute a precise range (up to
unsigned envelope), so do that.
|
|
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
|
|
Currently UREM & SREM on constant ranges produces overly pessimistic
results for single element constant ranges.
Delegate to APInt's implementation if both operands are single element
constant ranges. We already do something similar for other binary
operators, like binary AND.
Fixes PR49731.
Reviewed By: lebedev.ri
Differential Revision: https://reviews.llvm.org/D105115
|
|
"Does the predicate hold between two ranges?"
Not very surprisingly, some places were already doing this check,
without explicitly naming the algorithm, cleanup them all.
|
|
This reverts commit 17cf2c94230bc107e7294ef84fad3b47f4cd1b73.
|
