aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Analysis/ValueTracking.cpp
AgeCommit message (Collapse)AuthorFilesLines
2016-08-24The patch improves ValueTracking on left shift with nsw flag.Evgeny Stupachenko1-5/+23
Summary: The patch fixes PR28946. Reviewers: majnemer, sanjoy Differential Revision: http://reviews.llvm.org/D23296 From: Li Huang llvm-svn: 279684
2016-08-23[ValueTracking] Use a function_ref to avoid multiple instantiationsDavid Majnemer1-5/+5
No functional change intended, this should just be a code size improvement. llvm-svn: 279563
2016-08-22Revert -r278267 [ValueTracking] An improvement to IR ValueTracking on ↵Artur Pilipenko1-37/+1
Non-negative Integers This change cause performance regression on MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt from LNT and some other bechmarks. See https://reviews.llvm.org/D18777 for details. llvm-svn: 279433
2016-08-17Replace a few more "fall through" comments with LLVM_FALLTHROUGHJustin Bogner1-2/+3
Follow up to r278902. I had missed "fall through", with a space. llvm-svn: 278970
2016-08-15Revert "[ValueTracking] Improve ValueTracking on left shift with nsw flag"Sanjoy Das1-13/+4
This reverts commit r278172. It causes PR28946. llvm-svn: 278740
2016-08-13Constify ValueTracking. NFC.Pete Cooper1-99/+125
Almost all of the method here are only analysing Value's as opposed to mutating them. Mark all of the easy ones as const. llvm-svn: 278585
2016-08-12Refactor isValidAssumeForContext to reduce duplication and indentation. NFC.Pete Cooper1-27/+21
This method had some duplicate code when we did or did not have a dom tree. Refactor it to remove the duplication, but also clean up the control flow to have less duplication. llvm-svn: 278450
2016-08-11Remove unnecessary extra version of isValidAssumeForContext. NFC.Pete Cooper1-11/+5
There were 2 versions of this method. A public one which takes a const Instruction* and a private implementation which takes a mutable Value* and casts to an Instruction*. There was no need for the 2 versions as all callers pass a const Instruction* and there was no need for a mutable pointer as we only do analysis here. llvm-svn: 278434
2016-08-11Use range algorithms instead of unpacking begin/endDavid Majnemer1-3/+2
No functionality change is intended. llvm-svn: 278417
2016-08-10[ValueTracking] An improvement to IR ValueTracking on Non-negative IntegersAndrew Kaylor1-1/+37
Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18777 llvm-svn: 278267
2016-08-09[ValueTracking] Improve ValueTracking on left shift with nsw flagAndrew Kaylor1-4/+13
Patch by Li Huang Differential Revison: https://reviews.llvm.org/D23296 llvm-svn: 278172
2016-08-06[ValueTracking] Teach computeKnownBits about [su]min/maxDavid Majnemer1-1/+50
Reasoning about a select in terms of a min or max allows us to derive a tigher bound on the result. llvm-svn: 277914
2016-07-14[ValueTracking] Use Instruction::getFunction; NFCSanjoy Das1-4/+2
llvm-svn: 275465
2016-07-11Teach computeKnownBits to look through returned-argument functionsHal Finkel1-3/+8
If a function is known to return one of its arguments, we can use that in order to compute known bits of the return value. Differential Revision: http://reviews.llvm.org/D9397 llvm-svn: 275036
2016-07-11BasicAA should look through functions with returned argumentsHal Finkel1-0/+6
Motivated by the work on the llvm.noalias intrinsic, teach BasicAA to look through returned-argument functions when answering queries. This is essential so that we don't loose all other AA information when supplementing with llvm.noalias. Differential Revision: http://reviews.llvm.org/D9383 llvm-svn: 275035
2016-07-02Remove dead TLI arg of isKnownNonNull and propagate deadness. NFC.Sean Silva1-7/+6
This actually uncovered a surprisingly large chain of ultimately unused TLI args. From what I can gather, this argument is a remnant of when isKnownNonNull would look at the TLI directly. The current approach seems to be that InferFunctionAttrs runs early in the pipeline and uses TLI to annotate the TLI-dependent non-null information as return attributes. This also removes the dependence of functionattrs on TLI altogether. llvm-svn: 274455
2016-06-29Revert "[ValueTracking] Teach computeKnownBits for PHI nodes to compute sign ↵Craig Topper1-12/+0
bit for a recurrence with a NSW addition." This is breaking an optimizaton remark test in clang. I've identified a couple fixes for that, but want to understand it better before I commit to anything. llvm-svn: 274102
2016-06-29[ValueTracking] Teach computeKnownBits for PHI nodes to compute sign bit for ↵Craig Topper1-0/+12
a recurrence with a NSW addition. If a operation for a recurrence is an addition with no signed wrap and both input sign bits are 0, then the result sign bit must also be 0. Similar for the negative case. I found this deficiency while playing around with a loop in the x86 backend that contained a signed division that could be optimized into an unsigned division if we could prove both inputs were positive. One of them being the loop induction variable. With this patch we can perform the conversion for this case. One of the test cases here is a contrived variation of the loop I was looking at. Differential revision: http://reviews.llvm.org/D21493 llvm-svn: 274098
2016-06-23[ValueTracking] simplify logic in ComputeNumSignBits (NFCI)Sanjay Patel1-16/+9
This was noted in http://reviews.llvm.org/D21610 . The previous code predated the use of APInt ( http://reviews.llvm.org/rL47654 ), so it had to account for the fixed width of uint64_t. Now that we're using the variable width APInt, we can remove some complexity. llvm-svn: 273584
2016-06-22[ValueTracking] improve ComputeNumSignBits for vector constantsSanjay Patel1-4/+33
This is similar to the computeKnownBits improvement in rL268479. There's probably more we can do for vector logic instructions, but this should let us see non-splat constant masking ops that can become vector selects instead of and/andn/or sequences. Differential Revision: http://reviews.llvm.org/D21610 llvm-svn: 273459
2016-06-14[ValueTracking] Calls to @llvm.assume always returnSanjoy Das1-1/+2
This change teaches llvm::isGuaranteedToTransferExecutionToSuccessor that calls to @llvm.assume always terminate. Most other relevant intrinsics should be covered by the "CS.onlyReadsMemory() || CS.onlyAccessesArgMemory()" bit but we were missing @llvm.assumes because we state that it clobbers memory. Added an LICM test case, but this change is not specific to LICM. llvm-svn: 272703
2016-06-11[LICM] Make isGuaranteedToExecute more accurate.Eli Friedman1-13/+39
Summary: Make isGuaranteedToExecute use the isGuaranteedToTransferExecutionToSuccessor helper, and make that helper a bit more accurate. There's a potential performance impact here from assuming that arbitrary calls might not return. This probably has little impact on loads and stores to a pointer because most things alias analysis can reason about are dereferenceable anyway. The other impacts, like less aggressive hoisting of sdiv by a variable and less aggressive hoisting around volatile memory operations, are unlikely to matter for real code. This also impacts SCEV, which uses the same helper. It's a minor improvement there because we can tell that, for example, memcpy always returns normally. Strictly speaking, it's also introducing a bug, but it's not any worse than everywhere else we assume readonly functions terminate. Fixes http://llvm.org/PR27857. Reviewers: hfinkel, reames, chandlerc, sanjoy Subscribers: broune, llvm-commits Differential Revision: http://reviews.llvm.org/D21167 llvm-svn: 272489
2016-06-08Teach isGuarantdToTransferExecToSuccessor about debug info intrinsicsSanjoy Das1-3/+6
Calls to `@llvm.dbg.*` can be assumed to terminate. llvm-svn: 272180
2016-06-08Avoid copies of std::strings and APInt/APFloats where we only read from itBenjamin Kramer1-1/+1
As suggested by clang-tidy's performance-unnecessary-copy-initialization. This can easily hit lifetime issues, so I audited every change and ran the tests under asan, which came back clean. llvm-svn: 272126
2016-06-02transform obscured FP sign bit ops into a fabs/fneg using TLI hookSanjay Patel1-10/+2
This is effectively a revert of: http://reviews.llvm.org/rL249702 - [InstCombine] transform masking off of an FP sign bit into a fabs() intrinsic call (PR24886) and: http://reviews.llvm.org/rL249701 - [ValueTracking] teach computeKnownBits that a fabs() clears sign bits and a reimplementation as a DAG combine for targets that have IEEE754-compliant fabs/fneg instructions. This is intended to resolve the objections raised on the dev list: http://lists.llvm.org/pipermail/llvm-dev/2016-April/098154.html and: https://llvm.org/bugs/show_bug.cgi?id=24886#c4 In the interest of patch minimalism, I've only partly enabled AArch64. PowerPC, MIPS, x86 and others can enable later. Differential Revision: http://reviews.llvm.org/D19391 llvm-svn: 271573
2016-05-29[SCEV] See through op.with.overflow intrinsics (re-apply)Sanjoy Das1-0/+61
Summary: This change teaches SCEV to see reduce `(extractvalue 0 (op.with.overflow X Y))` into `op X Y` (with a no-wrap tag if possible). This was first checked in at r265912 but reverted in r265950 because it exposed some issues around how SCEV handled post-inc add recurrences. Those issues have now been fixed. Reviewers: atrick, regehr Subscribers: mcrosier, mzolotukhin, llvm-commits Differential Revision: http://reviews.llvm.org/D18684 llvm-svn: 271152
2016-05-29[ValueTracking] ICmp instructions propagate poisonSanjoy Das1-0/+5
This is a stripped down version of D19211, leaving out the questionable "branching in poison is UB" bit. llvm-svn: 271150
2016-05-24[ValueTracking, InstSimplify] extend isKnownNonZero() to handle vector constantsSanjay Patel1-1/+14
Similar in spirit to D20497 : If all elements of a constant vector are known non-zero, then we can say that the whole vector is known non-zero. It seems like we could extend this to FP scalar/vector too, but isKnownNonZero() says it only works for integers and pointers for now. Differential Revision: http://reviews.llvm.org/D20544 llvm-svn: 270562
2016-05-23fix formatting; NFCSanjay Patel1-4/+2
llvm-svn: 270465
2016-05-22use 'auto' with 'dyn_cast'; fix formatting; NFCSanjay Patel1-10/+8
llvm-svn: 270370
2016-05-22[ValueTracking, InstCombine] extend isKnownToBeAPowerOfTwo() to handle ↵Sanjay Patel1-3/+4
vector splat constants We could try harder to handle non-splat vector constants too, but that seems much rarer to me. Note that the div test isn't resolved because there's a check for isIntegerTy() guarding that transform. Differential Revision: http://reviews.llvm.org/D20497 llvm-svn: 270369
2016-05-10[ValueTracking] Use guards to prove non-nullness of a valueSanjoy Das1-9/+11
Reviewers: apilipenko, majnemer, reames Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20044 llvm-svn: 269008
2016-05-07[ValueTracking] Hoist some computation out of a loop; NFCSanjoy Das1-20/+11
There is no need to match the comparison instruction repeatedly. llvm-svn: 268836
2016-05-07Clean up comment; NFCSanjoy Das1-1/+1
llvm-svn: 268835
2016-05-07Delete trailing whitespace; NFCSanjoy Das1-8/+8
llvm-svn: 268834
2016-05-05[ValueTracking] Early exit when further analysis won't be fruitful.Chad Rosier1-15/+30
This should have NFC in the context of codegen, but may have positive implications on compile-time. llvm-svn: 268651
2016-05-05[ValueTracking] Improve isImpliedCondition for matching LHS and Imm RHSs.Chad Rosier1-0/+29
llvm-svn: 268636
2016-05-04[ConstantFolding, ValueTracking] Fold constants involving bitcasts of ↵David Majnemer1-2/+21
ConstantVector We assumed that ConstantVectors would be rather uninteresting from the perspective of analysis. However, this is not the case due to a quirk of how LLVM handles vectors of i1. Vectors of i1 are not ConstantDataVectors like vectors of i8, i16, i32 or i64 because i1's SizeInBits differs from it's StoreSizeInBytes. This leads to it being categorized as a ConstantVector instead of a ConstantDataVector. Instead, treat ConstantVector more uniformly. This fixes PR27591. llvm-svn: 268479
2016-04-29[ValueTracking] Make the code in lookThroughCastDavid Majnemer1-16/+9
No functionality change is intended. llvm-svn: 268108
2016-04-29[InstCombine] Determine the result of a select based on a dominating condition.Chad Rosier1-1/+4
Differential Revision: http://reviews.llvm.org/D19550 llvm-svn: 268104
2016-04-29[ValueTracking] matchSelectPattern needs to be more careful around FPDavid Majnemer1-19/+31
matchSelectPattern attempts to see through casts which mask min/max patterns from being more obvious. Under certain circumstances, it would misidentify a sequence of instructions as a min/max because it assumed that folding casts would preserve the result. This is not the case for floating point <-> integer casts. This fixes PR27575. llvm-svn: 268086
2016-04-27[TLI] Unify LibFunc signature checking. NFCI.Ahmed Bougacha1-60/+23
I tried to be as close as possible to the strongest check that existed before; cleaning these up properly is left for future work. Differential Revision: http://reviews.llvm.org/D19469 llvm-svn: 267758
2016-04-25[ValueTracking] Improve isImpliedCondition when the dominating cond is false.Chad Rosier1-3/+6
llvm-svn: 267430
2016-04-22Have isKnownNotFullPoison be smarter around control flowSanjoy Das1-14/+32
Summary: (... while still not using a PostDomTree) The way we use isKnownNotFullPoison from SCEV today, the new CFG walking logic will not trigger for any realistic cases -- it will kick in only for situations where we could have merged the contiguous basic blocks anyway[0], since the poison generating instruction dominates all of its non-PHI uses (which are the only uses we consider right now). However, having this change in place will allow a later bugfix to break fewer llvm-lit tests. [0]: i.e. cases where block A branches to block B and B is A's only successor and A is B's only predecessor. Reviewers: broune, bjarke.roune Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D19212 llvm-svn: 267175
2016-04-21Address Philip's post-commit feedback for r266987. NFC.Chad Rosier1-2/+2
llvm-svn: 266998
2016-04-21Refactor implied condition logic from ValueTracking directly into CmpInst. NFC.Chad Rosier1-52/+2
Differential Revision: http://reviews.llvm.org/D19330 llvm-svn: 266987
2016-04-21Add optimization for 'icmp slt (or A, B), A' and some related idioms based ↵Nick Lewycky1-28/+8
on knowledge of the sign bit for A and B. No matter what value you OR in to A, the result of (or A, B) is going to be UGE A. When A and B are positive, it's SGE too. If A is negative, OR'ing a value into it can't make it positive, but can increase its value closer to -1, therefore (or A, B) is SGE A. Working through all possible combinations produces this truth table: ``` A is +, -, +/- F F F + B is T F ? - ? F ? +/- ``` The related optimizations are flipping the 'slt' for 'sge' which always NOTs the result (if the result is known), and swapping the LHS and RHS while swapping the comparison predicate. There are more idioms left to implement (aren't there always!) but I've stopped here because any more would risk becoming unreasonable for reviewers. llvm-svn: 266939
2016-04-20[ValueTracking] Make isImpliedCondition return an Optional<bool>. NFC.Chad Rosier1-61/+52
Phabricator Revision: http://reviews.llvm.org/D19277 llvm-svn: 266904
2016-04-19[ValueTracking, VectorUtils] Refactor getIntrinsicIDForCallDavid Majnemer1-2/+149
The functionality contained within getIntrinsicIDForCall is two-fold: it checks if a CallInst's callee is a vectorizable intrinsic. If it isn't an intrinsic, it attempts to map the call's target to a suitable intrinsic. Move the mapping functionality into getIntrinsicForCallSite and rename getIntrinsicIDForCall to getVectorIntrinsicIDForCall while reimplementing it in terms of getIntrinsicForCallSite. llvm-svn: 266801
2016-04-19[ValueTracking] Improve isImpliedCondition for conditions with matching ↵Chad Rosier1-5/+99
operands. This patch improves SimplifyCFG to catch cases like: if (a < b) { if (a > b) <- known to be false unreachable; } Phabricator Revision: http://reviews.llvm.org/D18905 llvm-svn: 266767
generated by cgit v1.1 at 2025-10-16 06:42:13 +0000