aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ValueTracking.cpp
AgeCommit message (Collapse)AuthorFilesLines
2021-09-13[value-tracking] see through returned attribute.Florian Mayer1-0/+6
Reviewed By: vitalybuka Differential Revision: https://reviews.llvm.org/D109675
2021-09-09[APInt] Normalize naming on keep constructors / predicate methods.Chris Lattner1-10/+10
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
2021-08-10[InstSimplify] fold min/max with limit constantSanjay Patel1-0/+10
This is already done within InstCombine: https://alive2.llvm.org/ce/z/MiGE22 ...but leaving it out of analysis makes it harder to avoid infinite loops there.
2021-08-10Revert "[InstSimplify] fold min/max with limit constant; NFC"Sanjay Patel1-10/+0
This reverts commit f43859b4370f978d2bc625643ccbe03775b99713. This is not NFC, so I'll try again without that mistake in the commit message.
2021-08-10[InstSimplify] fold min/max with limit constant; NFCSanjay Patel1-0/+10
This is already done within InstCombine: https://alive2.llvm.org/ce/z/MiGE22 ...but leaving it out of analysis makes it harder to avoid infinite loops there.
2021-08-02[ValueTracking] Fix computeConstantRange to use "may" instead of "always" ↵Chang-Sun Lin, Jr1-1/+1
semantics for llvm.assume ValueTracking should allow for value ranges that may satisfy llvm.assume, instead of restricting the ranges only to values that will always satisfy the condition. Differential Revision: https://reviews.llvm.org/D107298
2021-07-26[LLVM IR] Allow volatile stores to trap.Eli Friedman1-0/+4
Proposed alternative to D105338. This is ugly, but short-term I think it's the best way forward: first, let's formalize the hacks into a coherent model. Then we can consider extensions of that model (we could have different flavors of volatile with different rules). Differential Revision: https://reviews.llvm.org/D106309
2021-07-03[SimplifyCFG] simplifyUnreachable(): erase instructions iff they are ↵Roman Lebedev1-0/+13
guaranteed to transfer execution to unreachable This replaces the current ad-hoc implementation, by syncing the code from InstCombine's implementation in `InstCombinerImpl::visitUnreachableInst()`, with one exception that here in SimplifyCFG we are allowed to remove EH instructions. Effectively, this now allows SimplifyCFG to remove calls (iff they won't throw and will return), arithmetic/logic operations, etc. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D105374
2021-06-25[NFC] Prefer ConstantRange::makeExactICmpRegion over makeAllowedICmpRegionEli Friedman1-2/+1
The implementation is identical, but it makes the semantics a bit more obvious.
2021-06-23[ValueTracking] look through bitcast of vector in computeKnownBitsSanjay Patel1-0/+41
This borrows as much as possible from the SDAG version of the code (originally added with D27129 and since updated with big endian support). In IR, we can test more easily for correctness than we did in the original patch. I'm using the simplest cases that I could find for InstSimplify: we computeKnownBits on variable shift amounts to see if they are zero or in range. So shuffle constant elements into a vector, cast it, and shift it. The motivating x86 example from https://llvm.org/PR50123 is also here. We computeKnownBits in the caller code, but we only check if the shift amount is in range. That could be enhanced to catch the 2nd x86 test - if the shift amount is known too big, the result is 0. Alive2 understands the datalayout and agrees that the tests here are correct - example: https://alive2.llvm.org/ce/z/KZJFMZ Differential Revision: https://reviews.llvm.org/D104472
2021-05-03Recommit "Generalize getInvertibleOperand recurrence handling slightly"Philip Reames1-30/+34
This was reverted because of a reported problem. It turned out this patch didn't introduce said problem, it just exposed it more widely. 15a4233 fixes the root issue, so this simple a) rebases over that, and b) adds a much more extensive comment explaining why that weakened assert is correct. Original commit message follows: Follow up to D99912, specifically the revert, fix, and reapply thereof. This generalizes the invertible recurrence logic in two ways: * By allowing mismatching operand numbers of the phi, we can recurse through a pair of phi recurrences whose operand orders have not been canonicalized. * By allowing recurrences through operand 1, we can invert these odd (but legal) recurrence. Differential Revision: https://reviews.llvm.org/D100884
2021-05-03[ValueTracking] soften assert for invertible recurrence matchingSanjay Patel1-1/+2
There's a TODO comment in the code and discussion in D99912 about generalizing this, but I wasn't sure how to implement that, so just going with a potential minimal fix to avoid crashing. The test is a reduction beyond useful code (there's no user of %user...), but it is based on https://llvm.org/PR50191, so this is asserting on real code. Differential Revision: https://reviews.llvm.org/D101772
2021-05-02[ValueTracking] ctpop propagates poisonJuneyoung Lee1-0/+2
This is a patch that adds ctpop intrinsics to propagatesPoison. Splitted from D101191
2021-05-02[ValueTracking] Improve impliesPoison to look into overflow intrinsicsJuneyoung Lee1-1/+2
This update supports the following transformation: ``` select(extract(mul_with_overflow(a, _), _), (a == 0), false) => and(extract(mul_with_overflow(a, _), _), (a == 0)) ``` which is correct because if `a` was poison the select's condition was also poison. This update is splitted from D101423.
2021-04-30[ValueTracking] Slightly clean up programUndefinedIfUndefOrPoison() (NFC)Nikita Popov1-13/+8
Use contains() to check set membership, and adjust an oddly structured loop.
2021-04-30[ValueTracking] Limit scan when checking poison UB (PR50155)Nikita Popov1-2/+13
The current code can scan an unlimited number of instructions, if the containing basic block is very large. The test case from PR50155 contains a basic block with approximately 100k instructions. To avoid this, limit the number of instructions we inspect. At the same time, drop the limit on the number of basic blocks, as this will be implicitly limited by the number of instructions as well.
2021-04-29Revert "Generalize getInvertibleOperand recurrence handling slightly"Philip Reames1-27/+30
This reverts commit 0c01b37eeb18a51a7e9c9153330d8009de0f600e while a problem reported is investigated.
2021-04-29[RISCV] Teach computeKnownBits that vsetvli returns number less than 2^31.Craig Topper1-0/+8
This seems like a reasonable upper bound on VL. WG discussions for the V spec would probably allow us to use 2^16 as an upper bound on VLEN, but this is good enough for now. This allows us to remove sext and zext if user happens to assign the size_t result into an int and then uses it as a VL intrinsic argument which is size_t. Reviewed By: frasercrmck, rogfer01, arcbbb Differential Revision: https://reviews.llvm.org/D101472
2021-04-28Generalize getInvertibleOperand recurrence handling slightlyPhilip Reames1-30/+27
Follow up to D99912, specifically the revert, fix, and reapply thereof. This generalizes the invertible recurrence logic in two ways: * By allowing mismatching operand numbers of the phi, we can recurse through a pair of phi recurrences whose operand orders have not been canonicalized. * By allowing recurrences through operand 1, we can invert these odd (but legal) recurrence. Differential Revision: https://reviews.llvm.org/D100884
2021-04-20Reapply "Look through invertible recurrences in isKnownNonEqual"Philip Reames1-0/+29
I'd reverted this in commit 3b6acb179708ea2f3caf95ace0f134fcbc460333 due to buildbot failures. This patch contains the fix for said issue. I'd forgotten to handle the case where two phis in the same block have different operand order. We canonicalize away from this, but it's still valid IR. The tests included in this change (as opposed to simply having test output changed), crashed without the fix. Original commit message follows... This extends the phi handling in isKnownNonEqual with a special case based on invertible recurrences. If we can prove the recurrence is invertible (which many common ones are), we can recurse through the start operands of the recurrence skipping the phi cycle. (Side note: Instcombine currently does not push back through these cases. I will implement that in a follow up change w/separate review.) Differential Revision: https://reviews.llvm.org/D99912
2021-04-20Revert "Look through invertible recurrences in isKnownNonEqual"Philip Reames1-29/+0
This reverts commit be20eae25f50f5ef648aeefa1143e1c31e4410fc. It appears to have caused a crash on a buildbot (https://lab.llvm.org/buildbot#builders/77/builds/5653). Reverting while investigating.
2021-04-20Look through invertible recurrences in isKnownNonEqualPhilip Reames1-0/+29
This extends the phi handling in isKnownNonEqual with a special case based on invertible recurrences. If we can prove the recurrence is invertible (which many common ones are), we can recurse through the start operands of the recurrence skipping the phi cycle. (Side note: Instcombine currently does not push back through these cases. I will implement that in a follow up change w/separate review.) Differential Revision: https://reviews.llvm.org/D99912
2021-04-16[ValueTracking] don't recursively compute known bits using multiple llvm.assumesSanjay Patel1-55/+33
This is an alternative to D99759 to avoid the compile-time explosion seen in: https://llvm.org/PR49785 Another potential solution would make the exclusion logic stronger to avoid blowing up, but note that we reduced the complexity of the exclusion mechanism in D16204 because it was too costly. So I'm questioning the need for recursion/exclusion entirely - what is the optimization value vs. cost of recursively computing known bits based on assumptions? This was built into the implementation from the start with 60db058, and we have kept adding code/cost to deal with that capability. By clearing the query's AssumptionCache inside computeKnownBitsFromAssume(), this patch retains all existing assume functionality except refining known bits based on even more assumptions. We have 1 regression test that shows a difference in optimization power. Differential Revision: https://reviews.llvm.org/D100573
2021-04-14[ValueTracking] Don't require strictly positive for mul nsw recurrenceNikita Popov1-3/+2
Just like in the mul nuw case, it's sufficient that the step is non-zero. If the step is negative, then the values will jump between positive and negative, "crossing" zero, but the value of the recurrence is never actually zero.
2021-04-14[ValueTracking] Don't require non-zero step for add nuwNikita Popov1-5/+3
It's okay if the step is zero, we'll just stay at the same non-zero value in that case. The valuable part of this is that the step doesn't even need to be a constant anymore.
2021-04-14[ValueTracking] match negative-stepping non-zero recurrenceSanjay Patel1-4/+7
This is pulled out of D100408. This avoids a regression that would be exposed by making the calling code from InstSimplify more efficient.
2021-04-14[ValueTracking] reduce code duplication; NFCSanjay Patel1-9/+7
The start value can't be null for something to be a non-zero recurrence, so hoist that common check out of the switch. Subsequent checks may be incomplete or over-specified as noted in: D100408
2021-04-06[KnownBits] Rename KnownBits::computeForMul to KnownBits::mul. NFCI.Simon Pilgrim1-2/+2
As promised in D98866
2021-04-05Comment adjustments for a renamePhilip Reames1-3/+3
2021-04-05Exact ashr/lshr don't loose any set bits and are thus trivially invertiblePhilip Reames1-0/+11
Use that fact to improve isKnownNonEqual.
2021-04-05Address minor post commit feedback on 0e59ddPhilip Reames1-15/+15
2021-04-05Extract a helper for figuring out if an operator is invertible [nfc]Philip Reames1-52/+65
For use in an uncoming patch. Left out the phi case (which could otherwise fit in this framework) as it would cause infinite recursion in said patch. We can probably also leverage this in instcombine to ensure we keep the two sets of related analysis and transforms in sync.
2021-04-02[KnownBits] Add KnownBits::haveNoCommonBitsSet helper. NFCI.Simon Pilgrim1-1/+1
Include exhaustive test coverage.
2021-03-31[ValueTracking] Handle non-zero ashr/lshr recurrencesPhilip Reames1-0/+3
If we know we don't shift out bits (e.g. exact), all we need to know is that input is non-zero.
2021-04-01[ValueTracking] Add with.overflow intrinsics to poison analysis functionsJuneyoung Lee1-1/+23
This is a patch teaching ValueTracking that `s/u*.with.overflow` intrinsics do not create undef/poison and they propagate poison. I couldn't write a nice example like the one with ctpop; ValueTrackingTest.cpp were simply updated to check these instead. This patch helps reducing regression while fixing https://llvm.org/pr49688 . Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D99671
2021-03-26[ValueTracking] Handle shl pair in isKnownNonEqual()Nikita Popov1-0/+14
Handle (x << s) != (y << s) where x != y and the shifts are non-wrapping. Once again, this establishes parity with the corresponing mul fold that already exists. The shift case is more powerful because we don't need to guard against multiplies by zero.
2021-03-26[ValueTracking] Handle shl in isKnownNonEqual()Nikita Popov1-0/+16
This handles the pattern X != X << C for non-zero X and C and a non-overflowing shift. This establishes parity with the corresponing fold for multiplies.
2021-03-26[ValueTracking] Handle non-zero shl recurrenceNikita Popov1-6/+10
In this case we don't care about the step at all, and only require that the starting value is non-zero.
2021-03-26[ValueTracking] Handle non-zero add/mul recurrences more preciselyNikita Popov1-16/+28
This is mainly for clarity: It doesn't make sense to do any negative/positive checks when dealing with a nuw add/mul. These only make sense to nsw add/mul.
2021-03-25[ValueTracking] Handle two PHIs in isKnownNonEqual()Jingu Kang1-3/+41
loop: %cmp.0 = phi i32 [ 3, %entry ], [ %inc, %loop ] %pos.0 = phi i32 [ 1, %entry ], [ %cmp.0, %loop ] ... %inc = add i32 %cmp.0, 1 br label %loop On above example, %pos.0 uses previous iteration's %cmp.0 with backedge according to PHI's instruction's defintion. If the %inc is not same among iterations, we can say the two PHIs are not same. Differential Revision: https://reviews.llvm.org/D98422
2021-03-24Plumb TLI through isSafeToExecuteUnconditionally [NFC]Philip Reames1-2/+3
Split from D95815 to reduce patch size. Isn't (yet) used for anything, only the client side is wired up.
2021-03-24[ValueTracking] peek through min/max to find isKnownToBeAPowerOfTwoSanjay Patel1-0/+6
This is similar to the select logic just ahead of the new code. Min/max choose exactly one value from the inputs, so if both of those are a power-of-2, then the result must be a power-of-2. This might help with D98152, but we likely still need other pieces of the puzzle to avoid regressions. The change in PatternMatch.h is needed to build with clang. It's possible there is a better way to deal with the 'const' incompatibities. Differential Revision: https://reviews.llvm.org/D99276
2021-03-23[ValueTracking] Handle increasing mul recurrence in isKnownNonZero()Jingu Kang1-15/+13
Differential Revision: https://reviews.llvm.org/D99069
2021-03-23[ValueTracking] Teach canCreateUndefOrPoison that ctpop does not create ↵Craig Topper1-0/+8
undef or poison. This select of ctpop with 0 pattern can get left behind after loop idiom recognize converts a loop to ctpop. LLVM 10 was able to optimize this, but LLVM 11 and later is not. The difference seems to be that some select transforms are now limited based on canCreateUndefOrPoison. Teaching canCreateUndefOrPoison about ctpop restores the LLVM 10 codegen. Differential Revision: https://reviews.llvm.org/D99207
2021-03-21[ValueTracking] Improve mul handling in isKnownNonEqual()Nikita Popov1-0/+16
X != X * C is true if: * C is not 0 or 1 * X is not 0 * mul is nsw or nuw Proof: https://alive2.llvm.org/ce/z/uwF29z This is motivated by one of the cases in D98422.
2021-03-15Revert "[NFCI][ValueTracking] getUnderlyingObject(): gracefully handle cycles"Nikita Popov1-6/+0
This reverts commit aa440ba24dc25e4c95f6dcf8ff647024f3b12661. This has a non-trivial compile-time impact: https://llvm-compile-time-tracker.com/compare.php?from=0c5b789c7342ee8384507c3242fc256e23248c4d&to=aa440ba24dc25e4c95f6dcf8ff647024f3b12661&stat=instructions I don't believe this is the correct way to address the issue in this case.
2021-03-15[NFCI][ValueTracking] getUnderlyingObject(): gracefully handle cyclesRoman Lebedev1-0/+6
Normally, this function just doesn't bother about cycles, and hopes that the caller supplied small-enough depth so that at worst it will take a potentially large, but limited amount of time. But that obviously doesn't work if there is no depth limit. This reapples 36f1c3db66f7268ea3183bcf0bbf05b3e1c570b4, but without asserting, just bailout once cycle is detected.
2021-03-15Revert "[NFCI][ValueTracking] getUnderlyingObject(): assert that no cycles ↵Roman Lebedev1-4/+0
are encountered" This reverts commit 36f1c3db66f7268ea3183bcf0bbf05b3e1c570b4. Seems to make bots unhappy.
2021-03-15[NFCI][ValueTracking] getUnderlyingObject(): assert that no cycles are ↵Roman Lebedev1-0/+4
encountered Jeroen Dobbelaere in https://lists.llvm.org/pipermail/llvm-dev/2021-March/149206.html is reporting that this function can end up in an endless loop when called from SROA w/ full restrict patches. For now, simply ensure that such problems are caught earlier/easier.
2021-03-09[ValueTracking] Move matchSimpleRecurrence out of lineBenjamin Kramer1-0/+9
The header only has a forward declaration of PHINode available, and this function doesn't seem to get much out of inlining.
generated by cgit v1.1 at 2025-10-13 11:35:52 +0000