aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ValueTracking.cpp
AgeCommit message (Collapse)AuthorFilesLines
2021-03-08[ValueTracking] move/add helper to get inverse min/max; NFCSanjay Patel1-0/+10
We will need to this functionality to improve min/max folds in instcombine when we canonicalize to intrinsics.
2021-03-08constify getUnderlyingObject implementation [nfc]Philip Reames1-3/+3
2021-03-07[ValueTracking] update directlyImpliesPoison to look into select's conditionJuneyoung Lee1-0/+4
This is a minor update in directlyImpliesPoison and makes it look into select's condition. Splitted from https://reviews.llvm.org/D96945
2021-02-26Be more mathematicly precise about definition of recurrence [NFC]Philip Reames1-18/+10
This clarifies the interface of the matchSimpleRecurrence helper introduced in 8020be0b8 for non-commutative operators. After ebd3aeba, I realized the original way I framed the routine was inconsistent. For shifts, we only matched the the LHS form, but for sub we matched both and the caller wanted that information. So, instead, we now consistently match both forms for non-commutative operators and the caller becomes responsible for filtering if needed. I tried to put a clear warning in the header because I suspect the RHS form of e.g. a sub recurrence is non-obvious for most folks. (It was for me.)
2021-02-26Use helper introduced in 8020be0b8 to simplify ValueTracking [NFC]Philip Reames1-126/+105
Direct rewrite of the code the helper was extracted from.
2021-02-26Add a helper for matching simple recurrence cyclesPhilip Reames1-0/+64
This helper came up in another review, and I've got about 4 different patches with copies of this copied into it. Time to precommit the routine. :)
2021-02-24Revert rGd65ddca83ff85c7345fe9a0f5a15750f01e38420 - "[ValueTracking] ↵Simon Pilgrim1-13/+26
ComputeKnownBits - minimum leading/trailing zero bits in LSHR/SHL (PR44526)" This is causing sanitizer test failures that I haven't been able to fix yet.
2021-02-24Revert "[ValueTracking] computeKnownBitsFromShiftOperator - remove non-zero ↵Nico Weber1-1/+17
shift amount handling." This reverts commit d37400168ce2f1f9ccc91847431f5b8c020a7d67. Breaks Analysis/./AnalysisTests/ComputeKnownBitsTest.KnownNonZeroShift
2021-02-24[ValueTracking] computeKnownBitsFromShiftOperator - remove non-zero shift ↵Simon Pilgrim1-17/+1
amount handling. This no longer affects any tests after the improvements to the KnownBits shift helpers.
2021-02-24[ValueTracking] ComputeKnownBits - minimum leading/trailing zero bits in ↵Simon Pilgrim1-26/+13
LSHR/SHL (PR44526) Followup to D72573 - as detailed in https://blog.regehr.org/archives/1709 we don't make use of the known leading/trailing zeros for shifted values in cases where we don't know the shift amount value. Stop ValueTracking returning zero for poison shift patterns and use the KnownBits shift helpers directly. Extend KnownBits::shl to combine all possible shifted combinations if both min/max shift amount values are in range. Differential Revision: https://reviews.llvm.org/D90479
2021-02-22[ValueTracking] Improve ComputeNumSignBits for SRem.Craig Topper1-23/+20
The result will have the same sign as the dividend unless the result is 0. The magnitude of the result will always be less than or equal to the dividend. So the result will have at least as many sign bits as the dividend. Previously we would do this if the divisor was a positive constant, but that isn't required. Reviewed By: RKSimon Differential Revision: https://reviews.llvm.org/D97170
2021-02-20[ValueTracking] Improve impliesPoisonJuneyoung Lee1-5/+13
This patch improves ValueTracking's impliesPoison(V1, V2) to do this reasoning: ``` %res = call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b) %overflow = extractvalue { i64, i1 } %res, 1 %mul = extractvalue { i64, i1 } %res, 0 ; If %mul is poison, %overflow is also poison, and vice versa. ``` This improvement leads to supporting this optimization under `-instcombine-unsafe-select-transform=0`: ``` define i1 @test2_logical(i64 %a, i64 %b, i64* %ptr) { ; CHECK-LABEL: @test2_logical( ; CHECK-NEXT: [[MUL:%.*]] = mul i64 [[A:%.*]], [[B:%.*]] ; CHECK-NEXT: [[TMP1:%.*]] = icmp ne i64 [[A]], 0 ; CHECK-NEXT: [[TMP2:%.*]] = icmp ne i64 [[B]], 0 ; CHECK-NEXT: [[OVERFLOW_1:%.*]] = and i1 [[TMP1]], [[TMP2]] ; CHECK-NEXT: [[NEG:%.*]] = sub i64 0, [[MUL]] ; CHECK-NEXT: store i64 [[NEG]], i64* [[PTR:%.*]], align 8 ; CHECK-NEXT: ret i1 [[OVERFLOW_1]] ; %res = tail call { i64, i1 } @llvm.umul.with.overflow.i64(i64 %a, i64 %b) %overflow = extractvalue { i64, i1 } %res, 1 %mul = extractvalue { i64, i1 } %res, 0 %cmp = icmp ne i64 %mul, 0 %overflow.1 = select i1 %overflow, i1 true, i1 %cmp %neg = sub i64 0, %mul store i64 %neg, i64* %ptr, align 8 ret i1 %overflow.1 } ``` Previously, this didn't happen because the flag prevented `select i1 %overflow, i1 true, i1 %cmp` from being `or i1 %overflow, %cmp`. Note that the select -> or conversion happens only when `impliesPoison(%cmp, %overflow)` returns true. This improvement allows `impliesPoison` to do the reasoning. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D96929
2021-02-19[ValueTracking] Add a two argument form of safeCtxI [NFC]Philip Reames1-1/+19
The existing implementation was relying on order of evaluation to achieve a particular result. This got really confusing when wanting to change the handling for arguments in a later patch.
2021-02-19[IR] Move willReturn() to InstructionNikita Popov1-25/+3
This moves the willReturn() helper from CallBase to Instruction, so that it can be used in a more generic manner. This will make it easier to fix additional passes (ADCE and BDCE), and will give us one place to change if additional instructions should become non-willreturn (e.g. there has been talk about handling volatile operations this way). I have also included the IntrinsicInst workaround directly in here, so that it gets applied consistently. (As such this change is not entirely NFC -- FuncAttrs will now use this as well.) Differential Revision: https://reviews.llvm.org/D96992
2021-02-15[ValueTracking] add scan limit for assumesSanjay Patel1-1/+5
In the motivating example from https://llvm.org/PR49171 and reduced test here, we would unroll and clone assumes so much that compile-time effectively became infinite while analyzing all of those assumes.
2021-02-14[ValueTracking] Dereferenced pointers are noundefaqjune1-21/+31
This is a follow-up of D95238's LangRef update. This patch updates `programUndefinedIfUndefOrPoison(V)` to return true if `V` is used by any memory-accessing instruction. Interestingly, this affected many tests in Attributors, mainly about adding noundefs. The tests are updated using llvm/utils/update_test_checks.py. I checked that the diffs are about updating noundefs. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D96642
2021-02-11[knownbits] Preserve known bits for small shift recurrencesPhilip Reames1-0/+45
The motivation for this is that I'm looking at an example that uses shifts as induction variables. There's lots of other omissions, but one of the first I noticed is that we can't compute tight known bits. (This indirectly causes SCEV's range analysis to produce very poor results as well.) Differential Revision: https://reviews.llvm.org/D96440
2021-02-11Move implementation of isAssumeLikeIntrinsic into IntrinsicInstStanislav Mekhanoshin1-21/+2
This is remove dependency on ValueTracking in the future patch. Differential Revision: https://reviews.llvm.org/D96079
2021-02-09[ValueTracking] improve analysis for "C << X" and "C >> X"Sanjay Patel1-0/+8
This is based on the example/comments in: https://llvm.org/PR48984 I tried just lifting the restriction in computeKnownBitsFromShiftOperator() as suggested in the bug report, but that doesn't catch all of the cases shown here. I didn't step through to see exactly why that happened. But it seems like a reasonable compromise to cheaply check the special-case of shifting a constant. There's a slight regression on a cmp transform as noted, but this is likely the more important/common pattern, so we can fix that icmp pattern later if needed. Differential Revision: https://reviews.llvm.org/D95959
2021-02-06[Analysis] Use range-based for loops (NFC)Kazu Hirata1-2/+2
2021-01-24[ValueTracking] Don't assume readonly function will returnNikita Popov1-17/+4
This is similar to D94106, but for the isGuaranteedToTransferExecutionToSuccessor() helper. We should not assume that readonly functions will return, as this is only true for mustprogress functions (in which case we already infer willreturn). As with the DCE change, for now continue assuming that readonly intrinsics will return, as not all target intrinsics have been annotated yet. Differential Revision: https://reviews.llvm.org/D95288
2021-01-22[Analysis] Use llvm::append_range (NFC)Kazu Hirata1-5/+2
2021-01-20Allow nonnull/align attribute to accept poisonJuneyoung Lee1-1/+2
Currently LLVM is relying on ValueTracking's `isKnownNonZero` to attach `nonnull`, which can return true when the value is poison. To make the semantics of `nonnull` consistent with the behavior of `isKnownNonZero`, this makes the semantics of `nonnull` to accept poison, and return poison if the input pointer isn't null. This makes many transformations like below legal: ``` %p = gep inbounds %x, 1 ; % p is non-null pointer or poison call void @f(%p) ; instcombine converts this to call void @f(nonnull %p) ``` Instead, this semantics makes propagation of `nonnull` to caller illegal. The reason is that, passing poison to `nonnull` does not immediately raise UB anymore, so such program is still well defined, if the callee does not use the argument. Having `noundef` attribute there re-allows this. ``` define void @f(i8* %p) { ; functionattr cannot mark %p nonnull here anymore call void @g(i8* nonnull %p) ; .. because @g never raises UB if it never uses %p. ret void } ``` Another attribute that needs to be updated is `align`. This patch updates the semantics of align to accept poison as well. Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D90529
2021-01-19[noalias.decl] Look through llvm.experimental.noalias.scope.declJeroen Dobbelaere1-0/+1
Just like llvm.assume, there are a lot of cases where we can just ignore llvm.experimental.noalias.scope.decl. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D93042
2021-01-19[ValueTracking] Strengthen impliesPoison reasoningNikita Popov1-48/+33
Split impliesPoison into two recursive walks, one over V, the other over ValAssumedPoison. This allows us to reason about poison implications in a number of additional cases that are important in practice. This is a generalized form of D94859, which handles the cmp to cmp implication in particular. Differential Revision: https://reviews.llvm.org/D94866
2021-01-17[ValueTracking] Fix isSafeToSpeculativelyExecute for sdiv (PR48778)Nikita Popov1-1/+1
The != -1 check does not work correctly for all bitwidths. Use isAllOnesValue() instead.
2021-01-14[Analysis,CodeGen] Make use of KnownBits::makeConstant. NFC.Jay Foad1-7/+4
Differential Revision: https://reviews.llvm.org/D94588
2021-01-13[ValueTracking] Fix one s/dyn_cast/dyn_cast_or_null/Markus Lavin1-1/+1
Handle if Constant::getAggregateElement() returns nullptr in canCreateUndefOrPoison(). Differential Revision: https://reviews.llvm.org/D94494
2021-01-06[Constant] Add containsPoisonElementJuneyoung Lee1-3/+4
This patch - Adds containsPoisonElement that checks existence of poison in constant vector elements, - Renames containsUndefElement to containsUndefOrPoisonElement to clarify its behavior & updates its uses properly With this patch, isGuaranteedNotToBeUndefOrPoison's tests w.r.t constant vectors are added because its analysis is improved. Thanks! Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D94053
2021-01-05[ValueTracking] isGuaranteedNotToBePoison should return true on undefJuneyoung Lee1-1/+1
This is a one-line fix to isGuaranteedNotToBePoison to return true if undef is given.
2020-12-29[ValueTracking] Implement impliesPoisonJuneyoung Lee1-0/+58
This PR adds impliesPoison(ValAssumedPoison, V) that returns true if V is poison under the assumption that ValAssumedPoison is poison. For example, impliesPoison('icmp X, 10', 'icmp X, Y') return true because 'icmp X, Y' is poison if 'icmp X, 10' is poison. impliesPoison can be used for sound optimization of select, as discussed in D77868. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D78152
2020-12-28[ValueTracking] Fix isKnownNonEqual() with constexpr mulNikita Popov1-5/+6
Confusingly, BinaryOperator is not an Operator, OverflowingBinaryOperator is... We were implicitly assuming that the multiply is an Instruction here. This fixes the assertion failure reported in https://reviews.llvm.org/D92726#2472827.
2020-12-28[ValueTracking] Use m_LogicalAnd/Or to look into conditionsJuneyoung Lee1-23/+23
This patch updates isImpliedCondition/isKnownNonZero to look into select form of and/or as well. See llvm.org/pr48353 and D93065 for more context Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D93845
2020-12-26[ValueTracking] Handle more non-trivial conditions in isKnownNonZero()Nikita Popov1-1/+1
In 35676a4f9a536a2aab768af63ddbb15bc722d7f9 I've added handling for non-trivial dominating conditions that imply non-zero on the true branch. This adds the same support for the false branch. The changes in pr45360.ll change block ordering and naming, but don't change the control flow. The urem is still guaraded by a non-zero check correctly.
2020-12-25[InstCombine] Generalize icmp handling in isKnownNonZero()Nikita Popov1-40/+37
The dominating condition handling in isKnownNonZero() currently only takes into account conditions of the form "x != 0" or "x == 0". However, there are plenty of other conditions that imply non-zero, a common one being "x s> 0". Peculiarly, the handling for assumes was already dealing with more general non-zero-ness conditions, so this just reuses the same logic for the dominating condition case.
2020-12-07Teach isKnownNonEqual how to recurse through invertible multipliesPhilip Reames1-1/+21
Build on the work started in 8f07629, and add the multiply case. In the process, more clearly describe the requirement for the operation we're looking through. Differential Revision: https://reviews.llvm.org/D92726
2020-12-05Add recursive decomposition reasoning to isKnownNonEqualPhilip Reames1-8/+40
The basic idea is that by looking through operand instructions which don't change the equality result that we can push the existing known bits comparison down past instructions which would obscure them. We have analogous handling in InstSimplify for most - though weirdly not all - of these cases starting from an icmp root. It's a bit unfortunate to duplicate logic, but since my actual goal is to extend BasicAA, the icmp logic doesn't help. (And just makes it hard to test here.) The BasicAA change will be posted separately for review. Differential Revision: https://reviews.llvm.org/D92698
2020-11-27[ValueTracking] Fix assert on shufflevector of pointersNikita Popov1-2/+1
In this case getScalarSizeInBits() is not well-defined. Use the existing TyBits variable that handles vectors of pointers correctly.
2020-11-22[ValueTracking][MemCpyOpt] avoid crash on inttoptr with vector pointer type ↵Sanjay Patel1-6/+7
(PR48075)
2020-11-20[Analysis] Use llvm::is_contained (NFC)Kazu Hirata1-3/+2
2020-11-20[CSSPGO] IR intrinsic for pseudo-probe block instrumentationHongtao Yu1-0/+1
This change introduces a new IR intrinsic named `llvm.pseudoprobe` for pseudo-probe block instrumentation. Please refer to https://reviews.llvm.org/D86193 for the whole story. A pseudo probe is used to collect the execution count of the block where the probe is instrumented. This requires a pseudo probe to be persisting. The LLVM PGO instrumentation also instruments in similar places by placing a counter in the form of atomic read/write operations or runtime helper calls. While these operations are very persisting or optimization-resilient, in theory we can borrow the atomic read/write implementation from PGO counters and cut it off at the end of compilation with all the atomics converted into binary data. This was our initial design and we’ve seen promising sample correlation quality with it. However, the atomics approach has a couple issues: 1. IR Optimizations are blocked unexpectedly. Those atomic instructions are not going to be physically present in the binary code, but since they are on the IR till very end of compilation, they can still prevent certain IR optimizations and result in lower code quality. 2. The counter atomics may not be fully cleaned up from the code stream eventually. 3. Extra work is needed for re-targeting. We choose to implement pseudo probes based on a special LLVM intrinsic, which is expected to have most of the semantics that comes with an atomic operation but does not block desired optimizations as much as possible. More specifically the semantics associated with the new intrinsic enforces a pseudo probe to be virtually executed exactly the same number of times before and after an IR optimization. The intrinsic also comes with certain flags that are carefully chosen so that the places they are probing are not going to be messed up by the optimizer while most of the IR optimizations still work. The core flags given to the special intrinsic is `IntrInaccessibleMemOnly`, which means the intrinsic accesses memory and does have a side effect so that it is not removable, but is does not access memory locations that are accessible by any original instructions. This way the intrinsic does not alias with any original instruction and thus it does not block optimizations as much as an atomic operation does. We also assign a function GUID and a block index to an intrinsic so that they are uniquely identified and not merged in order to achieve good correlation quality. Let's now look at an example. Given the following LLVM IR: ``` define internal void @foo2(i32 %x, void (i32)* %f) !dbg !4 { bb0: %cmp = icmp eq i32 %x, 0 br i1 %cmp, label %bb1, label %bb2 bb1: br label %bb3 bb2: br label %bb3 bb3: ret void } ``` The instrumented IR will look like below. Note that each `llvm.pseudoprobe` intrinsic call represents a pseudo probe at a block, of which the first parameter is the GUID of the probe’s owner function and the second parameter is the probe’s ID. ``` define internal void @foo2(i32 %x, void (i32)* %f) !dbg !4 { bb0: %cmp = icmp eq i32 %x, 0 call void @llvm.pseudoprobe(i64 837061429793323041, i64 1) br i1 %cmp, label %bb1, label %bb2 bb1: call void @llvm.pseudoprobe(i64 837061429793323041, i64 2) br label %bb3 bb2: call void @llvm.pseudoprobe(i64 837061429793323041, i64 3) br label %bb3 bb3: call void @llvm.pseudoprobe(i64 837061429793323041, i64 4) ret void } ``` Reviewed By: wmi Differential Revision: https://reviews.llvm.org/D86490
2020-11-19[ValueTracking] computeKnownBitsFromShiftOperator - move shift amount ↵Simon Pilgrim1-8/+10
analysis to top of the function. NFCI. These are all lightweight to compute and helps avoid issues with Known being used to hold both the shift amount and then the shifted result. Minor cleanup for D90479.
2020-11-13[KnownBits] Combine abs() implementationsNikita Popov1-20/+4
ValueTracking was using a more powerful abs() implementation. Roll it into KnownBits::abs(). Also add an exhaustive test for abs(), in both the poisoning and non-poisoning variants.
2020-11-13[ValueTracking] Don't set nsw flag for inbounds additionNikita Popov1-7/+4
When computing the known bits for a GEP, don't set the nsw flag when adding an offset to an address. The nsw flag only applies to pure offset additions (see also D90708). The nsw flag is only used in a very minor way by the code, to the point that I was not able to come up with a test case where it makes a difference. Differential Revision: https://reviews.llvm.org/D90637
2020-11-13[ValueTracking] computeKnownBitsFromShiftOperator use KnownBits direct for ↵Simon Pilgrim1-2/+1
constant shift amounts. Let KnownBits shift handlers deal with out-of-range shift amounts.
2020-11-12[ValueTracking] Update computeKnownBitsFromShiftOperator callbacks to take ↵Simon Pilgrim1-14/+12
KnownBits shift amount. NFCI. We were creating this internally, but will need to support general KnownBits amounts as part of D90479.
2020-11-12[KnownBits] Add KnownBits::makeConstant helper. NFCI.Simon Pilgrim1-12/+3
Helper for cases where we need to create a KnownBits from a (fully known) constant value.
2020-11-12[ValueTracking] Update computeKnownBitsFromShiftOperator callbacks to use ↵Simon Pilgrim1-18/+15
KnownBits shift handling. NFCI.
2020-11-11[ValueTracking] computeKnownBitsFromShiftOperator - merge zero/one callbacks ↵Simon Pilgrim1-45/+35
to single KnownBits callback. NFCI. Another cleanup for D90479 - handle the Known Ones/Zeros in a single callback, which will make it much easier to jump over to the KnownBits shift handling.
2020-11-11[KnownBits] Add KnownBits::commonBits helper. NFCI.Simon Pilgrim1-9/+5
We have a frequent pattern where we're merging two KnownBits to get the common/shared bits, and I just fell for the gotcha where I tried to use the & operator to merge them........
generated by cgit v1.1 at 2025-10-13 13:35:53 +0000