aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ValueTracking.cpp
AgeCommit message (Collapse)AuthorFilesLines
2023-10-24[IR] Require that ptrmask mask matches pointer index size (#69343)Nikita Popov1-2/+2
Currently, we specify that the ptrmask intrinsic allows the mask to have any size, which will be zero-extended or truncated to the pointer size. However, what semantics of the specified GEP expansion actually imply is that the mask is only meaningful up to the pointer type *index* size -- any higher bits of the pointer will always be preserved. In other words, the mask gets 1-extended from the index size to the pointer size. This is also the behavior we want for CHERI architectures. This PR makes two changes: * It spells out the interaction with the pointer type index size more explicitly. * It requires that the mask matches the pointer type index size. The intention here is to make handling of this intrinsic more robust, to avoid accidental mix-ups of pointer size and index size in code generating this intrinsic. If a zero-extend or truncate of the mask is desired, it should just be done explicitly in IR. This also cuts down on the amount of testing we have to do, and things transforms needs to check for. As far as I can tell, we don't actually support pointers with different index type size at the SDAG level, so I'm just asserting the sizes match there for now. Out-of-tree targets using different index sizes may need to adjust that code.
2023-10-20[ValueTracking] Implement sdiv/udiv support for ↵Dhruv Chawla1-0/+4
isKnownNonNullFromDominatingCondition (#67282) The second operand of a sdiv/udiv has to be non-null, as division by zero is UB. Proofs: https://alive2.llvm.org/ce/z/WttZbb Fixes https://github.com/llvm/llvm-project/issues/64240.
2023-10-17[InstCombine] Create a class to lazily track computed known bits (#66611)Dhruv Chawla1-38/+37
This patch adds a new class "WithCache" which stores a pointer to any type passable to computeKnownBits along with KnownBits information which is computed on-demand when getKnownBits() is called. This allows reusing the known bits information when it is passed as an argument to multiple functions. It also changes a few functions to accept WithCache(s) so that known bits information computed in some callees can be propagated to others from the top level visitAddSub caller. This gives a speedup of 0.14%: https://llvm-compile-time-tracker.com/compare.php?from=499d41cef2e7bbb65804f6a815b9fa8b27efce0f&to=fbea87f1f1e6d5552e2bc309f8e201a3af6d28ec&stat=instructions:u
2023-10-16Revert "[ValueTracking] Remove by-ref computeKnownBits() overloads (NFC)"Nikita Popov1-5/+27
This reverts commit b5743d4798b250506965e07ebab806a3c2d767cc. This causes some minor compile-time impact. Revert for now, better to do the change more gradually.
2023-10-16[ValueTracking] Remove by-ref computeKnownBits() overloads (NFC)Nikita Popov1-27/+5
Remove the old overloads that accept KnownBits by reference, in favor of those that return it by value.
2023-10-12[ValueTracking] Do more thorough non-zero check in `isKnownToBePowerOfTwo` ↵Noah Goldstein1-13/+12
when `OrZero` is no set. We can cover more cases by directly checking if the result is known-nonzero for common patterns when they are missing `OrZero`. This patch add `isKnownNonZero` checks for `shl`, `lshr`, `and`, and `mul`. Differential Revision: https://reviews.llvm.org/D157309
2023-10-12[ValueTracking] Add support for non-splat vecs in cmpExcludesZeroNoah Goldstein1-3/+16
Just a small QOL change.
2023-10-12[ValueTracking] Add better support for ConstantRange(And)Noah Goldstein1-0/+5
The fairly common power of two pattern `X & -X` can be capped at the highest power of 2 (signbit set).
2023-10-12[ValueTracking] Add better support for ConstantRange(Shl)Noah Goldstein1-0/+13
1) If LHS is constant: - The low bits of the LHS is set, the lower bound is non-zero - The upper bound can be capped at popcount(LHS) high bits 2) If RHS is constant: - The upper bound can be capped at (Width - RHS) high bits
2023-10-10[ValueTracking] Use SimplifyQuery in haveNoCommonBitsSet() (NFC)Nikita Popov1-5/+3
Pass SimplifyQuery instead of unpacked list of arguments.
2023-10-10[ValueTracking] Use SimplifyQuery for the overflow APIs (NFC)Nikita Popov1-79/+53
Accept a SimplifyQuery instead of an unpacked list of arguments.
2023-10-05ValueTracking: Use fcAllFlags for unknown value (#66393)Matt Arsenault1-8/+8
In the failure case we return null, which callers are checking. We were also returning an fcNone which was unused. It's more consistent to return fcAllFlags as any possible value, such that the value is always directly usable without checking the returned value.
2023-10-05[ValueTracking] Try to infer range of select from true and false values. ↵Mikhail Gudim1-3/+8
(#68256) When computing range of `select` instruction, first compute the union of ranges of "True" and "False" operands of the `select` instruction.
2023-10-05[ValueTracking] Add SimplifyQuery ctor without TLI (NFC)Nikita Popov1-35/+29
While we pretty much always want to pass DT, AC and CxtI, most places don't care about TLI. Add an overload where this is not one of the first parameters.
2023-10-05[ValueTracking] Return ConstantRange instead of setting limits (NFC)Nikita Popov1-37/+27
Same as previously done for intrinsics.
2023-09-29[ValueTracking] Avoid use of ConstantExpr::getCast()Nikita Popov1-3/+5
Use the constant folding API instead.
2023-09-29[ValueTracking] Simplify uaddo pattern (#65910)Yingwei Zheng1-0/+23
This patch simplifies the overflow check of unsigned addition. `a + b <u a` implies `a + b <u b` `a + b >=u a` implies `a + b >=u b` Alive2: https://alive2.llvm.org/ce/z/H8oK8n Fixes #65863.
2023-09-18[ValueTracking] Remove unused Depth parameter (NFC)Nikita Popov1-11/+12
Clarify that the Depth is always 0 in this function for a future change.
2023-09-08[NFC][ValueTracking] Simplify check in llvm::isBitwiseValue() (#65817)Tyler Lanphear1-1/+1
Change `!isNonZero()` to `isZero()` for a minor readability improvement.
2023-09-01ValueTracking: exp10 does not introduce poisonMatt Arsenault1-0/+1
2023-09-01ValueTracking: Handle exp10 in computeKnownFPClassMatt Arsenault1-1/+2
It's the same as the other exps. https://reviews.llvm.org/D157891
2023-09-01Revert "Revert "InstSimplify: Use correct interested FP classes when ↵Philip Reames1-1/+7
simplifying fcmp"" This reverts commit 89f0314ee14a4d7f5a92fd63574ba545863df016. Change does not build.
2023-09-01Revert "InstSimplify: Use correct interested FP classes when simplifying fcmp"Zequan Wu1-7/+1
Revert "InstSimplify: Add baseline tests for reported regression" Revert "InstSimplify: Start cleaning up simplifyFCmpInst" This reverts commit 0637b00041c7d6a191d51d9966c4f5f41fb97ab5. This reverts commit 239fb206de35935416e652b89725d5f3193f78f5. This reverts commit ddb3f12c428bc4bd5a98913d74dfd7f2402bdfd8. These commits causes crashes when compiling chromium code, attached reduced ir at: https://reviews.llvm.org/D151887#4634914
2023-09-01[ValueTracking] Handle conflicts when computing knownbits of PHI nodes in ↵Noah Goldstein1-1/+11
deadcode; PR65022 Bug was introduced in: https://reviews.llvm.org/D157807 The prior logic assumed that the information from the knownbits returned from analyzing the `icmp` and its operands in the context basicblock would be consistent. This is not necessarily the case if we are analyzing deadcode. For example with `(icmp sgt (select cond, 0, 1), -1)`. If we take knownbits for the `select` using knownbits from the operator, we will know the signbit is zero. If we are analyzing a not-taken from based on the `icmp` (deadcode), we will also "know" that the `select` must be negative (signbit is one). This will result in a conflict in knownbits. The fix is to just give up on analying the phi-node if its deadcode. We 1) don't want to waste time continuing to analyze it and 2) will be removing it (and its dependencies) later. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D158960
2023-08-30InstSimplify: Start cleaning up simplifyFCmpInstMatt Arsenault1-1/+7
Also picks up a few improvements (Some of the fcmp.ll test names imply they aren't quite testing what was intended. Checking the sign bit can't be performed with a compare to a 0). Much of the logic in here is the same as the class detection logic of fcmpToClassTest. We could unify more with a weaker version of fcmpToClassTest which returns implied classes rather than exact class-like compares. Also could unify more with detection of possible classes in non-splat vectors. One problem here is we now only perform folds that used to always work now require a context instruction. This is because fcmpToClassTest requires the parent function. Either fcmpToClassTest could tolerate a missing context function, or we could require passing in one to simplifyFCmpInst. Without this it's possible to hit the !isNan assert (which feels like an unnecessary assert). In any case, these cases don't appear in any tests. https://reviews.llvm.org/D151887
2023-08-25[Attributor] Filter potential callees based on `noundef` argumentsJohannes Doerfert1-0/+2
If a potential callee has more arguments than the call site, the values passed will be `poison`. If the potential callee would exhibit UB for such `undef` argument, e.g., they are marked `noundef`, we can rule the potential callee out.
2023-08-24[ValueTracking] Compute `sdiv` as non-zero if `abs(num) u>= abs(denum)`Noah Goldstein1-15/+22
Just covering an additional case. Proof: https://alive2.llvm.org/ce/z/MJz9fT Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D157302
2023-08-22[ValueTracking] Strengthen analysis in `computeKnownBits` of phiNoah Goldstein1-3/+5
Use the comparison based analysis to strengthen the standard knownbits analysis rather than choosing either/or. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D157807
2023-08-22[ValueTracking] Use predicates for incoming phi-edges to deduce non-zeroNoah Goldstein1-0/+17
This is basically a copy and paste of the same logic we do in `computeKnownBits` but adapts it for just `isKnownNonZero`. Differential Revision: https://reviews.llvm.org/D157801
2023-08-22[ValueTracking] Improve analysis of knownbits from incoming phi edges.Noah Goldstein1-15/+3
Just fill in missing cases (TODO) for `ugt`, `uge`, `sgt`, `sge`, `slt`, and `sle`. These are all in the same spirit as `ult`/`uge`, but each of the other conditions have different constraints. Proofs: https://alive2.llvm.org/ce/z/gnj4o- Differential Revision: https://reviews.llvm.org/D157800
2023-08-16[NFC][ValueTracking] Remove calls to computeKnownBits for non-intrinsic ↵Dhruv Chawla1-1/+6
CallInsts in isKnownNonZeroFromOperator For non-intrinsic CallInsts, computeKnownBits only handles range metadata and checking getReturnedArgOperand(). Both of these are now handled in isKnownNonZero, so there is no need to fall through to a call to computeKnownBits anymore. Differential Revision: https://reviews.llvm.org/D158095
2023-08-14[ValueTracking] Dereferenceable and !NullPointerIsDefined imply non-zeroluxufan1-4/+10
Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D157253
2023-08-11ValueTracking: frexp never introduces poisonMatt Arsenault1-0/+1
2023-08-11ValueTracking: ldexp never introduces poisonMatt Arsenault1-0/+1
2023-08-09[ValueTracking] Check likely to be canonicalized constant operands first in ↵Noah Goldstein1-2/+2
; NFC Checking operands that a likely to be canonicalized constants first makes sense from a compile time perspective as it puts whats expected to be a cheaper check first. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D157313
2023-08-09[ValueTracking] In `isKnownToBeAPowerOfTwo` an `i1` value is always true if ↵Noah Goldstein1-0/+4
`OrZero` is set This is trivially true. Differential Revision: https://reviews.llvm.org/D157310
2023-08-09[ValueTracking] Add support for `mul` in `isKnownToBeAPowerOfTwo`Noah Goldstein1-0/+4
pow2 * pow2 is a power of 2 or zero. Proof: https://alive2.llvm.org/ce/z/FNiiXd Differential Revision: https://reviews.llvm.org/D157308
2023-08-09[ValueTracking] Add support for `fshl`/`fshr` in `isKnownToBeAPowerOfTwo`Noah Goldstein1-0/+6
If the funnel shifts are rotates (op0 == op1) then the number of 1s/0s don't change so we can just look through op0/op1. Proofs: https://alive2.llvm.org/ce/z/Pja5yu Differential Revision: https://reviews.llvm.org/D157307
2023-08-09[ValueTracking] Add support for `bswap` and `bitreverse` in ↵Noah Goldstein1-0/+5
`isKnownToBeAPowerOfTwo` Both of these intrinsics don't change the number of 1s/0s so we can look directly through them. Proofs: https://alive2.llvm.org/ce/z/gnZuwC Differential Revision: https://reviews.llvm.org/D157306
2023-08-09[ValueTracking] Use switch for Intrinsics in `isKnownToBePowerOfTwo`; NFCNoah Goldstein1-4/+13
Differential Revision: https://reviews.llvm.org/D157305
2023-08-09[ValueTracking] If `OrZero` is set, look through `trunc` in ↵Noah Goldstein1-0/+2
`isKnownToBePowerOfTwo` Just move coverage. Proof: https://alive2.llvm.org/ce/z/H37tVX Differential Revision: https://reviews.llvm.org/D157304
2023-08-08Revert "[AggressiveInstCombine] Fold strcmp for short string literals"Alexander Kornienko1-7/+0
This reverts commit 5dde755188e34c0ba5304365612904476c8adfda, cbfcf90152de5392a36d0a0241eef25f5e159eef and 8981520b19f2d2fe3d2bc80cf26318ee6b5b7473 due to a miscompile introduced in 8981520b19f2d2fe3d2bc80cf26318ee6b5b7473 (see https://reviews.llvm.org/D154725#4568845 for details) Differential Revision: https://reviews.llvm.org/D157430
2023-08-07ValueTracking: Reduce indentation in computeKnownFPClassMatt Arsenault1-361/+354
2023-08-07Revert "[ValueTracking] Improve the coverage of isKnownToBeAPowerOfTwo for ↵Noah Goldstein1-2/+1
vscale" Logic is incorrect. Shift can make non-zero pow2 zero. This reverts commit 9c837b7d0e2e2dffae804f3df49c4aeefe4743c0.
2023-08-07[ValueTracking] Support non-zero pow2 for shl with nowrap flagsNikita Popov1-3/+2
If the shl has either nuw or nsw flags, then we know that bits cannot be shifted out, so a power of two cannot become zero. Proofs: https://alive2.llvm.org/ce/z/4QfebE
2023-08-07[ValueTracking] Switch over opcode in isKnownToBeAPowerOfTwo() (NFC)Nikita Popov1-65/+68
Similar to the other ValueTracking function, switch over the instruction opcode instead of doing a long sequence of match()es.
2023-08-07ValueTracking: Really remove CannotBeOrderedLessThanZeroMatt Arsenault1-5/+3
6640df94f9abd4f9fef0263afbf7978ac55832b8 did not actually remove it, just its final user. cannotBeOrderedLessThanZeroImpl still has a user which needs to be updated before it can be removed. The users of SignBitMustBeZero currently have broken expectations for nan handling, so requires more work to replace.
2023-08-07[ValueTracking] Dereferenceable ret attributes implys noundefluxufan1-1/+3
Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D156510
2023-08-04[ValueTracking] Improve the coverage of isKnownToBeAPowerOfTwo for vscaleZhongyunde1-1/+2
this PR tries to match the following pattern, seperate from D156881 ``` %vscale = call i64 @llvm.vscale.i64() %shift = shl nuw nsw i64 %vscale, 11 ``` Now, we only check the shl recursively when the OrZero is true. Reviewed By: goldstein.w.n Differential Revision: https://reviews.llvm.org/D157062
2023-07-26[NFC][ValueTracking]: Move some code from isKnownNonZero to ↵Dhruv Chawla1-11/+12
isKnownNonZeroFromOperator There is some pointer simplification code originally from isKnownNonNull that is now better suited to be in isKnownNonZeroFromOperator. Differential Revision: https://reviews.llvm.org/D156141
generated by cgit v1.1 at 2025-10-11 15:58:50 +0000