summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ValueTracking.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [ValueTracking] Use a function_ref to avoid multiple instantiationsDavid Majnemer2016-08-231-5/+5
| | | | | | | No functional change intended, this should just be a code size improvement. llvm-svn: 279563
* Revert -r278267 [ValueTracking] An improvement to IR ValueTracking on ↵Artur Pilipenko2016-08-221-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
* Replace a few more "fall through" comments with LLVM_FALLTHROUGHJustin Bogner2016-08-171-2/+3
| | | | | | Follow up to r278902. I had missed "fall through", with a space. llvm-svn: 278970
* Revert "[ValueTracking] Improve ValueTracking on left shift with nsw flag"Sanjoy Das2016-08-151-13/+4
| | | | | | This reverts commit r278172. It causes PR28946. llvm-svn: 278740
* Constify ValueTracking. NFC.Pete Cooper2016-08-131-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
* Refactor isValidAssumeForContext to reduce duplication and indentation. NFC.Pete Cooper2016-08-121-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
* Remove unnecessary extra version of isValidAssumeForContext. NFC.Pete Cooper2016-08-111-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
* Use range algorithms instead of unpacking begin/endDavid Majnemer2016-08-111-3/+2
| | | | | | No functionality change is intended. llvm-svn: 278417
* [ValueTracking] An improvement to IR ValueTracking on Non-negative IntegersAndrew Kaylor2016-08-101-1/+37
| | | | | | | | Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18777 llvm-svn: 278267
* [ValueTracking] Improve ValueTracking on left shift with nsw flagAndrew Kaylor2016-08-091-4/+13
| | | | | | | | Patch by Li Huang Differential Revison: https://reviews.llvm.org/D23296 llvm-svn: 278172
* [ValueTracking] Teach computeKnownBits about [su]min/maxDavid Majnemer2016-08-061-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
* [ValueTracking] Use Instruction::getFunction; NFCSanjoy Das2016-07-141-4/+2
| | | | llvm-svn: 275465
* Teach computeKnownBits to look through returned-argument functionsHal Finkel2016-07-111-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
* BasicAA should look through functions with returned argumentsHal Finkel2016-07-111-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
* Remove dead TLI arg of isKnownNonNull and propagate deadness. NFC.Sean Silva2016-07-021-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
* Revert "[ValueTracking] Teach computeKnownBits for PHI nodes to compute sign ↵Craig Topper2016-06-291-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
* [ValueTracking] Teach computeKnownBits for PHI nodes to compute sign bit for ↵Craig Topper2016-06-291-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
* [ValueTracking] simplify logic in ComputeNumSignBits (NFCI)Sanjay Patel2016-06-231-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
* [ValueTracking] improve ComputeNumSignBits for vector constantsSanjay Patel2016-06-221-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
* [ValueTracking] Calls to @llvm.assume always returnSanjoy Das2016-06-141-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
* [LICM] Make isGuaranteedToExecute more accurate.Eli Friedman2016-06-111-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
* Teach isGuarantdToTransferExecToSuccessor about debug info intrinsicsSanjoy Das2016-06-081-3/+6
| | | | | | Calls to `@llvm.dbg.*` can be assumed to terminate. llvm-svn: 272180
* Avoid copies of std::strings and APInt/APFloats where we only read from itBenjamin Kramer2016-06-081-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
* transform obscured FP sign bit ops into a fabs/fneg using TLI hookSanjay Patel2016-06-021-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
* [SCEV] See through op.with.overflow intrinsics (re-apply)Sanjoy Das2016-05-291-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
* [ValueTracking] ICmp instructions propagate poisonSanjoy Das2016-05-291-0/+5
| | | | | | | This is a stripped down version of D19211, leaving out the questionable "branching in poison is UB" bit. llvm-svn: 271150
* [ValueTracking, InstSimplify] extend isKnownNonZero() to handle vector constantsSanjay Patel2016-05-241-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
* fix formatting; NFCSanjay Patel2016-05-231-4/+2
| | | | llvm-svn: 270465
* use 'auto' with 'dyn_cast'; fix formatting; NFCSanjay Patel2016-05-221-10/+8
| | | | llvm-svn: 270370
* [ValueTracking, InstCombine] extend isKnownToBeAPowerOfTwo() to handle ↵Sanjay Patel2016-05-221-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
* [ValueTracking] Use guards to prove non-nullness of a valueSanjoy Das2016-05-101-9/+11
| | | | | | | | | | Reviewers: apilipenko, majnemer, reames Subscribers: mcrosier, llvm-commits Differential Revision: http://reviews.llvm.org/D20044 llvm-svn: 269008
* [ValueTracking] Hoist some computation out of a loop; NFCSanjoy Das2016-05-071-20/+11
| | | | | | There is no need to match the comparison instruction repeatedly. llvm-svn: 268836
* Clean up comment; NFCSanjoy Das2016-05-071-1/+1
| | | | llvm-svn: 268835
* Delete trailing whitespace; NFCSanjoy Das2016-05-071-8/+8
| | | | llvm-svn: 268834
* [ValueTracking] Early exit when further analysis won't be fruitful.Chad Rosier2016-05-051-15/+30
| | | | | | | This should have NFC in the context of codegen, but may have positive implications on compile-time. llvm-svn: 268651
* [ValueTracking] Improve isImpliedCondition for matching LHS and Imm RHSs.Chad Rosier2016-05-051-0/+29
| | | | llvm-svn: 268636
* [ConstantFolding, ValueTracking] Fold constants involving bitcasts of ↵David Majnemer2016-05-041-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
* [ValueTracking] Make the code in lookThroughCastDavid Majnemer2016-04-291-16/+9
| | | | | | No functionality change is intended. llvm-svn: 268108
* [InstCombine] Determine the result of a select based on a dominating condition.Chad Rosier2016-04-291-1/+4
| | | | | | Differential Revision: http://reviews.llvm.org/D19550 llvm-svn: 268104
* [ValueTracking] matchSelectPattern needs to be more careful around FPDavid Majnemer2016-04-291-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
* [TLI] Unify LibFunc signature checking. NFCI.Ahmed Bougacha2016-04-271-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
* [ValueTracking] Improve isImpliedCondition when the dominating cond is false.Chad Rosier2016-04-251-3/+6
| | | | llvm-svn: 267430
* Have isKnownNotFullPoison be smarter around control flowSanjoy Das2016-04-221-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
* Address Philip's post-commit feedback for r266987. NFC.Chad Rosier2016-04-211-2/+2
| | | | llvm-svn: 266998
* Refactor implied condition logic from ValueTracking directly into CmpInst. NFC.Chad Rosier2016-04-211-52/+2
| | | | | | Differential Revision: http://reviews.llvm.org/D19330 llvm-svn: 266987
* Add optimization for 'icmp slt (or A, B), A' and some related idioms based ↵Nick Lewycky2016-04-211-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
* [ValueTracking] Make isImpliedCondition return an Optional<bool>. NFC.Chad Rosier2016-04-201-61/+52
| | | | | | Phabricator Revision: http://reviews.llvm.org/D19277 llvm-svn: 266904
* [ValueTracking, VectorUtils] Refactor getIntrinsicIDForCallDavid Majnemer2016-04-191-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
* [ValueTracking] Improve isImpliedCondition for conditions with matching ↵Chad Rosier2016-04-191-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
* Simplify strlen to a subtraction for certain cases.David L Kreitzer2016-04-131-13/+21
| | | | | | | | Patch by Li Huang (li1.huang@intel.com) Differential Revision: http://reviews.llvm.org/D18230 llvm-svn: 266200
OpenPOWER on IntegriCloud