aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ValueTracking.cpp
AgeCommit message (Collapse)AuthorFilesLines
2020-11-10[ValueTracking] computeKnownBitsFromShiftOperator - always return with ↵Simon Pilgrim1-6/+5
Known2 containing the shifted value source. NFCI. As detailed on D90479, in most circumstances we will always call computeKnownBits for Op0, so always perform this by pulling out the duplicate calls.
2020-11-10[ValueTracking] computeKnownBitsFromShiftOperator - consistently use Known2 ↵Simon Pilgrim1-3/+3
for the shifted value. NFCI. Minor cleanup as part of getting D90479 moving again.
2020-11-06[InstCombine] computeKnownBitsMul - use KnownBits::isNonZero() helper.Simon Pilgrim1-4/+4
Avoid an expensive isKnownNonZero() call - this is a small cleanup before moving the extra NSW functionality from computeKnownBitsMul into KnownBits::computeForMul.
2020-11-05[KnownBits] Move ValueTracking SREM KnownBits handling to KnownBits::srem. NFCI.Simon Pilgrim1-32/+4
Move the ValueTracking implementation to KnownBits, the SelectionDAG version is more limited so I'm intending to replace that as a separate commit.
2020-11-05[KnownBits] Move ValueTracking/SelectionDAG UREM KnownBits handling to ↵Simon Pilgrim1-20/+2
KnownBits::urem. NFCI. Both these have the same implementation - so move them to a single KnownBits copy. GlobalISel will be able to use this as well with minimal effort.
2020-11-05[KnownBits] Move ValueTracking/SelectionDAG UDIV KnownBits handling to ↵Simon Pilgrim1-12/+2
KnownBits::udiv. NFCI. Both these have the same implementation - so move them to a single KnownBits copy. GlobalISel will be able to use this as well with minimal effort.
2020-10-31Reland "[SLP] Consider alternatives for cost of select instructions."Florian Hahn1-0/+40
This reverts the revert commit a1b53db32418cb6ed6f5b2054d15a22b5aa3aeb9. This patch includes a fix for a reported issue, caused by matchSelectPattern returning UMIN for selects of pointers in some cases by looking to some connected casts. For now, ensure integer instrinsics are only returned for selects of ints or int vectors.
2020-10-30Revert "[SLP] Consider alternatives for cost of select instructions."Florian Hahn1-39/+0
This reverts commit 19225704890632cd2552f41ada41600a20db1371. This appears to cause a crash in the following example a, b, c; l() { int e = a, f = l, g, h, i, j; float *d = c, *k = b; for (;;) for (; g < f; g++) { k[h] = d[i]; k[h - 1] = d[j]; h += e << 1; i += e; } } clang -cc1 -triple i386-unknown-linux-gnu -emit-obj -target-cpu pentium-m -O1 -vectorize-loops -vectorize-slp reduced.c llvm::Type *llvm::Type::getWithNewBitWidth(unsigned int) const: Assertion `isIntOrIntVectorTy() && "Original type expected to be a vector of integers or a scalar integer."' failed.
2020-10-29[SLP] Consider alternatives for cost of select instructions.Florian Hahn1-0/+39
Some architectures do not have general vector select instructions (e.g. AArch64). But some cmp/select patterns can be vectorized using other instructions/intrinsics. One example is using min/max instructions for certain patterns. This patch updates the cost calculations for selects in the SLP vectorizer to consider using min/max intrinsics. This patch does not change SLP vectorizer's codegen itself to actually generate those intrinsics, but relies on the backends to lower the vector cmps & selects. This keeps things simple on the SLP side and works well in practice for AArch64. This exposes additional SLP vectorization opportunities in some benchmarks on AArch64 (-O3 -flto). Metric: SLP.NumVectorInstructions Program base slp diff test-suite...ications/JM/ldecod/ldecod.test 502.00 697.00 38.8% test-suite...ications/JM/lencod/lencod.test 1023.00 1414.00 38.2% test-suite...-typeset/consumer-typeset.test 56.00 65.00 16.1% test-suite...6/464.h264ref/464.h264ref.test 804.00 822.00 2.2% test-suite...006/453.povray/453.povray.test 3335.00 3357.00 0.7% test-suite...CFP2000/177.mesa/177.mesa.test 2110.00 2121.00 0.5% test-suite...:: External/Povray/povray.test 2378.00 2382.00 0.2% Reviewed By: RKSimon, samparker Differential Revision: https://reviews.llvm.org/D89969
2020-10-27[ValueTracking][NFC] Use Log2(Align) instead of countTrailingZeroesAlex Richardson1-1/+1
The latter can probably be optimized to the same final code, but this might help -O0 builds.
2020-10-27[ValueTracking] Add tracking of the alignment assume bundleShimin Cui1-0/+8
This patch is to add the support of the value tracking of the alignment assume bundle. Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D88669
2020-10-23[ValueTracking] add range limits for cttzSanjay Patel1-0/+1
As discussed in D89952, instcombine can sometimes find a way to reduce similar patterns, but it is incomplete. InstSimplify uses the computeConstantRange() ValueTracking analysis via simplifyICmpWithConstant(), so we just need to fill in the max value of cttz to process any "icmp pred cttz(X), C" pattern (the min value is initialized to zero automatically). https://alive2.llvm.org/ce/z/Z_SLWZ Follow-up to D89976.
2020-10-23[ValueTracking] add range limits for ctlzSanjay Patel1-1/+2
As discussed in D89952, instcombine can sometimes find a way to reduce similar patterns, but it is incomplete. InstSimplify uses the computeConstantRange() ValueTracking analysis via simplifyICmpWithConstant(), so we just need to fill in the max value of ctlz to process any "icmp pred ctlz(X), C" pattern (the min value is initialized to zero automatically). Follow-up to D89976.
2020-10-23[ValueTracking] add range limits for ctpopSanjay Patel1-0/+5
As discussed in D89952, instcombine can sometimes find a way to reduce similar patterns, but it is incomplete. InstSimplify uses the computeConstantRange() ValueTracking analysis via simplifyICmpWithConstant(), so we just need to fill in the max value of ctpop to process any "icmp pred ctpop(X), C" pattern (the min value is initialized to zero automatically). Differential Revision: https://reviews.llvm.org/D89976
2020-10-21[ValueTracking] Interpret GEPs as a series of adds multiplied by the related ↵Quentin Colombet1-25/+65
scaling factor Prior to this patch, computeKnownBits would only try to deduce trailing zeros bits for getelementptrs. This patch adds the logic to treat geps as a series of add * scaling factor. Thanks to this patch, using a gep or performing an address computation directly "by hand" (ptrtoint followed by adds and mul followed by inttoptr) offers the same computeKnownBits information. Previously, the "by hand" approach would have given more information. This is related to https://llvm.org/PR47241. Differential Revision: https://reviews.llvm.org/D86364
2020-10-17Add support for !noundef metatdata on loadsJuneyoung Lee1-0/+4
This patch adds metadata !noundef and makes load instructions can optionally have it. A load with !noundef always return a well-defined value (has no undef bit or isn't poison). If the loaded value isn't well defined, the behavior is undefined. This metadata can be used to encode the assumption from C/C++ that certain reads of variables should have well-defined values. It is helpful for optimizing freeze instructions away, because freeze can be removed when its operand has well-defined value, and showing that a load from arbitrary location is well-defined is usually hard otherwise. The same information can be encoded with llvm.assume with operand bundle; using metadata is chosen because I wasn't sure whether code motion can be freely done when llvm.assume is inserted from clang instead. The existing codebase already is stripping unknown metadata when doing code motion, so using metadata is UB-safe as well. Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D89050
2020-10-16[ValueTracking] Clarify TypeSize comparisonsCullen Rhodes1-14/+15
TypeSize comparisons using overloaded operators should be replaced by the new isKnownXY comparators when the operands can be fixed-length or scalable vectors. In ValueTracking there are several uses of the overloaded operators in `isKnownNonZero` and `ComputeMultiple`. In the former we already bail out on scalable vectors since we currently have no way to represent DemandedElts, and the latter is operating on scalar integers, so we can assume fixed-size in both instances. Reviewed By: david-arm Differential Revision: https://reviews.llvm.org/D89387
2020-10-14[ValueTracking] Use assume's noundef operand bundleJuneyoung Lee1-9/+17
This patch updates `isGuaranteedNotToBeUndefOrPoison` to use `llvm.assume`'s `noundef` operand bundle. Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D89219
2020-10-11[ValueTracking] Use KnownBits::countMaxLeadingZeros/countMaxTrailingZeros to ↵Craig Topper1-2/+2
make code more readable. NFC
2020-10-08[KnownBits] Add a computeForMul methodQuentin Colombet1-74/+2
This patch refactors the logic in ValueTracking.cpp so that computeKnownBitsForMul now uses a helper function from KnownBits. NFC Differential Revision: https://reviews.llvm.org/D88935
2020-10-05[ValueTracking] canCreateUndefOrPoison - use APInt to check bounds instead ↵Simon Pilgrim1-3/+2
of getZExtValue(). Fixes OSS Fuzz #26135
2020-09-29[ValueTracking] Early exit known non zero for phisNikita Popov1-3/+1
After D88276 we no longer expect computeKnownBits() to prove non-zeroness for cases where isKnownNonZero() can't, so don't fall through to it.
2020-09-29[IsKnownNonZero] Handle the case with non-constant phi nodesSerguei Katkov1-4/+9
Handle the case when all inputs of phi are proven to be non zero. Constants are checked in beginning of this method before check for depth of recursion, so it is a partial case of non-constant phi. Recursion depth is already handled by the function. Reviewers: aqjune, nikic, efriedma Reviewed By: nikic Subscribers: dantrushin, hiraditya, jdoerfert, llvm-commits Differential Revision: https://reviews.llvm.org/D88276
2020-09-28[ValueTracking] Fix analyses to update CxtI to be phi's incoming edges' ↵Juneyoung Lee1-4/+19
terminators It was mentioned that D88276 that when a phi node is visited, terminators at their incoming edges should be used for CtxI. This is a patch that makes two functions (ComputeNumSignBitsImpl, isGuaranteedNotToBeUndefOrPoison) to do so. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D88360
2020-09-27[ValueTracking] enhance isKnownNeverInfinity to understand sitofpSanjay Patel1-5/+14
As discussed in D87877, instcombine already has this fold, but it was missing from the more general ValueTracking logic. https://alive2.llvm.org/ce/z/PumYZP
2020-09-25[ValueTracking] Make isGuaranteedNotToBeUndefOrPoison exit early when ↵Juneyoung Lee1-0/+3
MetadataAsValue is given It is set to conservatively return false, otherwise noundef attributes are added to function calls with metadata arguments.
2020-09-25[ValueTracking] Check uses of Argument if it is given to ↵Juneyoung Lee1-24/+32
isGuaranteedNotToBeUndefOrPoison This is a patch that allows isGuaranteedNotToBeUndefOrPoison to return more precise result when an argument is given, by looking through its uses at the entry block (and following blocks as well, if it is checking poison only). This is useful when there is a function call with noundef arguments at the entry block. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D88207
2020-09-10[ValueTracking] isKnownNonZero, computeKnownBits for freezeJuneyoung Lee1-0/+11
This implements support for isKnownNonZero, computeKnownBits when freeze is involved. ``` br (x != 0), BB1, BB2 BB1: y = freeze x ``` In the above program, we can say that y is non-zero. The reason is as follows: (1) If x was poison, `br (x != 0)` raised UB (2) If x was fully undef, the branch again raised UB (3) If x was non-zero partially undef, say `undef | 1`, `freeze x` will return a nondeterministic value which is also non-zero. (4) If x was just a concrete value, it is trivial Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D75808
2020-09-09[ValueTracking] Add UndefOrPoison/Poison-only version of relevant functionsJuneyoung Lee1-26/+81
This patch adds isGuaranteedNotToBePoison and programUndefinedIfUndefOrPoison. isGuaranteedNotToBePoison will be used at D75808. The latter function is used at isGuaranteedNotToBePoison. Reviewed By: nikic Differential Revision: https://reviews.llvm.org/D84242
2020-09-08[ValueTracking] Compute known bits of min/max intrinsicsNikita Popov1-0/+20
Implement known bits for the min/max intrinsics based on the recently added KnownBits primitives.
2020-09-07[KnownBits] Implement accurate unsigned and signed max and minJay Foad1-44/+26
Use the new implementation in ValueTracking, SelectionDAG and GlobalISel. Differential Revision: https://reviews.llvm.org/D87034
2020-09-06[ValueTracking] Avoid known bits fallback for non-zero get check (NFCI)Nikita Popov1-2/+1
The known bits fall back will never be able to infer a non-null value here, so don't bother.
2020-09-02[InstCombine] Fix a couple crashes with extractelement on a scalable vector.Eli Friedman1-5/+7
Differential Revision: https://reviews.llvm.org/D86989
2020-08-28[SVE] Make ElementCount members privateDavid Sherwood1-1/+2
This patch changes ElementCount so that the Min and Scalable members are now private and can only be accessed via the get functions getKnownMinValue() and isScalable(). In addition I've added some other member functions for more commonly used operations. Hopefully this makes the class more useful and will reduce the need for calling getKnownMinValue(). Differential Revision: https://reviews.llvm.org/D86065
2020-08-28[ValueTracking] Remove a stray semicolon. NFC.Martin Storsjö1-1/+1
This silences warnings when built with GCC at least.
2020-08-27[ValueTracking] Replace recursion with WorklistVitaly Buka1-48/+35
Now findAllocaForValue can handle nontrivial phi cycles.
2020-08-27[NFC][ValueTracking] Add OffsetZero into findAllocaForValueVitaly Buka1-15/+21
For StackLifetime after finding alloca we need to check that values ponting to the begining of alloca. Reviewed By: eugenis Differential Revision: https://reviews.llvm.org/D86692
2020-08-27[ValueTracking] Support select in findAllocaForValueVitaly Buka1-1/+8
2020-08-27[IR] Add NoUndef attribute to Intrinsics.tdJuneyoung Lee1-10/+0
This patch adds NoUndef to Intrinsics.td. The attribute is attached to llvm.assume's operand, because llvm.assume(undef) is UB. It is attached to pointer operands of several memory accessing intrinsics as well. This change makes ValueTracking::getGuaranteedNonPoisonOps' intrinsic check unnecessary, so it is removed. Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D86576
2020-08-26[ValueTracking] Let getGuaranteedNonPoisonOp find multiple non-poison operandsJuneyoung Lee1-12/+35
This patch helps getGuaranteedNonPoisonOp find multiple non-poison operands. Instead of special-casing llvm.assume, I think it is also a viable option to add noundef to Intrinsics.td. If it makes sense, I'll make a patch for that. Reviewed By: jdoerfert Differential Revision: https://reviews.llvm.org/D86477
2020-08-19[ValueTracking] define/use max recursion depth in headerSanjay Patel1-30/+26
There's a potential motivating case to increase this limit in PR47191: http://bugs.llvm.org/PR47191 But first we should make it less hacky. The limit in InstCombine is directly tied to this value because an increase there can cause asserts in the underlying value tracking calls if not changed together. The usage in VectorUtils is independent, but the comment suggests that we should use the same value unless there's a known reason to diverge. There are similar limits in codegen analysis, but I think we should leave those independent in case we intentionally want the optimization power/cost to be different there. Differential Revision: https://reviews.llvm.org/D86113
2020-08-12[ValueTracking] Add abs intrinsics support to computeConstantRange()Nikita Popov1-0/+8
Implementation is the same as for SPF_ABS.
2020-08-12[ValueTracking] Support min/max intrinsics in computeConstantRange()Nikita Popov1-0/+27
The implementation is the same as for the SPF_* case.
2020-08-06[GlobalISel] Fix computing known bits for loads with range metadataJessica Paquette1-3/+3
In GlobalISel, if you have a load into a small type with a range, you'll hit an assert if you try to compute known bits on it starting at a larger type. e.g. ``` %x:_(s8) = G_LOAD %whatever(p0) :: (load 1 ... !range !n) ... %y:_(s32) = G_SOMETHING %x ``` When we walk through G_SOMETHING and hit the load, the width of our known bits is 32. However, the width of the range is going to be 8. This will cause us to hit an assert. To fix this, make computeKnownBitsFromRangeMetadata zero extend or truncate the range type to match the bitwidth of the known bits we're calculating. Add a testcase in CodeGen/GlobalISel/KnownBitsTest.cpp to reflect that this works now. https://reviews.llvm.org/D85375
2020-07-31[ValueTracking] Improve llvm.abs handling in computeKnownBits.Craig Topper1-5/+16
Add the optimizations we have in the SelectionDAG version. Known non-negative copies all known bits. Any known one other than the sign bit makes result non-negative. Differential Revision: https://reviews.llvm.org/D85000
2020-07-31[ValueTracking] Add ComputeNumSignBits support for llvm.abs intrinsicCraig Topper1-0/+13
If absolute value needs turn a negative number into a positive number it reduces the number of sign bits by at most 1. Differential Revision: https://reviews.llvm.org/D84971
2020-07-31[NFC] Remove unused GetUnderlyingObject paramenterVitaly Buka1-8/+5
Depends on D84617. Differential Revision: https://reviews.llvm.org/D84621
2020-07-30[NFC] GetUnderlyingObject -> getUnderlyingObjectVitaly Buka1-7/+7
I am going to touch them in the next patch anyway
2020-07-30[ValueTracking] Remove AllocaForValue parameterVitaly Buka1-3/+7
findAllocaForValue uses AllocaForValue to cache resolved values. The function is used only to resolve arguments of lifetime intrinsic which usually are not fare for allocas. So result reuse is likely unnoticeable. In followup patches I'd like to replace the function with GetUnderlyingObjects. Depends on D84616. Differential Revision: https://reviews.llvm.org/D84617
2020-07-30[NFC] Move findAllocaForValue into ValueTracking.hVitaly Buka1-0/+35
Differential Revision: https://reviews.llvm.org/D84616
generated by cgit v1.1 at 2025-10-13 15:30:58 +0000