summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ValueTracking.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [ValueTracking] remove stale comments; NFCSanjay Patel2017-01-021-6/+0
| | | | | | | The checks were improved with: https://reviews.llvm.org/rL290194 llvm-svn: 290826
* Fix an issue with isGuaranteedToTransferExecutionToSuccessorSanjoy Das2016-12-311-6/+20
| | | | | | | | | | | | | | I'm not sure if this was intentional, but today isGuaranteedToTransferExecutionToSuccessor returns true for readonly and argmemonly calls that may throw. This commit changes the function to not implicitly infer nounwind this way. Even if we eventually specify readonly calls as not throwing, isGuaranteedToTransferExecutionToSuccessor is not the best place to infer that. We should instead teach FunctionAttrs or some other such pass to tag readonly functions / calls as nounwind instead. llvm-svn: 290794
* Avoid const_cast; NFCSanjoy Das2016-12-311-2/+3
| | | | llvm-svn: 290793
* [ValueTracking] make dominator tree requirement explicit for ↵Sanjay Patel2016-12-311-1/+6
| | | | | | | | | | | | | | | | | isKnownNonNullFromDominatingCondition(); NFCI I don't think this hole is currently exposed, but I crashed regression tests for jump-threading and loop-vectorize after I added calls to isKnownNonNullAt() in InstSimplify as part of trying to solve PR28430: https://llvm.org/bugs/show_bug.cgi?id=28430 That's because they call into value tracking with a context instruction, but no other parts of the query structure filled in. For more background, see the discussion in: https://reviews.llvm.org/D27855 llvm-svn: 290786
* Use MaxDepth instead of repeating its valueMatt Arsenault2016-12-201-3/+3
| | | | llvm-svn: 290194
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-104/+127
| | | | | | | This creates non-linear behavior in the inliner (see more details in r289755's commit thread). llvm-svn: 290086
* Remove the AssumptionCacheHal Finkel2016-12-151-71/+51
| | | | | | | | | After r289755, the AssumptionCache is no longer needed. Variables affected by assumptions are now found by using the new operand-bundle-based scheme. This new scheme is more computationally efficient, and also we need much less code... llvm-svn: 289756
* Make processing @llvm.assume more efficient by using operand bundlesHal Finkel2016-12-151-56/+53
| | | | | | | | | | | | | | | | | | | | | | | | | | | There was an efficiency problem with how we processed @llvm.assume in ValueTracking (and other places). The AssumptionCache tracked all of the assumptions in a given function. In order to find assumptions relevant to computing known bits, etc. we searched every assumption in the function. For ValueTracking, that means that we did O(#assumes * #values) work in InstCombine and other passes (with a constant factor that can be quite large because we'd repeat this search at every level of recursion of the analysis). Several of us discussed this situation at the last developers' meeting, and this implements the discussed solution: Make the values that an assume might affect operands of the assume itself. To avoid exposing this detail to frontends and passes that need not worry about it, I've used the new operand-bundle feature to add these extra call "operands" in a way that does not affect the intrinsic's signature. I think this solution is relatively clean. InstCombine adds these extra operands based on what ValueTracking, LVI, etc. will need and then those passes need only search the users of the values under consideration. This should fix the computational-complexity problem. At this point, no passes depend on the AssumptionCache, and so I'll remove that as a follow-up change. Differential Revision: https://reviews.llvm.org/D27259 llvm-svn: 289755
* IR, X86: Understand !absolute_symbol metadata on global variables.Peter Collingbourne2016-12-081-4/+4
| | | | | | | | | | | | | | | | | Summary: Attaching !absolute_symbol to a global variable does two things: 1) Marks it as an absolute symbol reference. 2) Specifies the value range of that symbol's address. Teach the X86 backend to allow absolute symbols to appear in place of immediates by extending the relocImm and mov64imm32 matchers. Start using relocImm in more places where it is legal. As previously proposed on llvm-dev: http://lists.llvm.org/pipermail/llvm-dev/2016-October/105800.html Differential Revision: https://reviews.llvm.org/D25878 llvm-svn: 289087
* IR: Change the gep_type_iterator API to avoid always exposing the "current" ↵Peter Collingbourne2016-12-021-2/+2
| | | | | | | | | | | | | type. Instead, expose whether the current type is an array or a struct, if an array what the upper bound is, and if a struct the struct type itself. This is in preparation for a later change which will make PointerType derive from Type rather than SequentialType. Differential Revision: https://reviews.llvm.org/D26594 llvm-svn: 288458
* Fix known zero bits for addrspacecast.Yaxun Liu2016-11-211-1/+0
| | | | | | | | | | Currently LLVM assumes that a pointer addrspacecasted to a different addr space is equivalent to trunc or zext bitwise, which is not true. For example, in amdgcn target, when a null pointer is addrspacecasted from addr space 4 to 0, its value is changed from i64 0 to i32 -1. This patch teaches LLVM not to assume known bits of addrspacecast instruction to its operand. Differential Revision: https://reviews.llvm.org/D26803 llvm-svn: 287545
* [ValueTracking] recognize even more variants of smin/smaxSanjay Patel2016-11-131-0/+20
| | | | | | | | | | | | | | | | Similar to: https://reviews.llvm.org/rL285499 https://reviews.llvm.org/rL286318 We can't minimally expose this in IR tests because we don't have min/max intrinsics, but the difference is visible in codegen because SelectionDAGBuilder::visitSelect() uses matchSelectPattern(). We're not canonicalizing these patterns in IR (yet), so I don't expect there to be any regressions as noted here: http://lists.llvm.org/pipermail/llvm-dev/2016-November/106868.html llvm-svn: 286776
* [ValueTracking] move min/max matching to helper function; NFCISanjay Patel2016-11-131-46/+59
| | | | llvm-svn: 286772
* [ValueTracking] recognize obfuscated variants of umin/umaxSanjay Patel2016-11-091-1/+25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | The smallest tests that expose this are codegen tests (because SelectionDAGBuilder::visitSelect() uses matchSelectPattern to create UMAX/UMIN nodes), but it's also possible to see the effects in IR alone with folds of min/max pairs. If these were written as unsigned compares in IR, InstCombine canonicalizes the unsigned compares to signed compares. Ie, running the optimizer pessimizes the codegen for this case without this patch: define <4 x i32> @umax_vec(<4 x i32> %x) { %cmp = icmp ugt <4 x i32> %x, <i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647> %sel = select <4 x i1> %cmp, <4 x i32> %x, <4 x i32> <i32 2147483647, i32 2147483647, i32 2147483647, i32 2147483647> ret <4 x i32> %sel } $ ./opt umax.ll -S | ./llc -o - -mattr=avx vpmaxud LCPI0_0(%rip), %xmm0, %xmm0 $ ./opt -instcombine umax.ll -S | ./llc -o - -mattr=avx vpxor %xmm1, %xmm1, %xmm1 vpcmpgtd %xmm0, %xmm1, %xmm1 vmovaps LCPI0_0(%rip), %xmm2 ## xmm2 = [2147483647,2147483647,2147483647,2147483647] vblendvps %xmm1, %xmm0, %xmm2, %xmm0 Differential Revision: https://reviews.llvm.org/D26096 llvm-svn: 286318
* [ValueTracking] remove TODO comment; NFCSanjay Patel2016-11-011-2/+0
| | | | | | | | | | InstCombine should always canonicalize patterns like the one shown in the comment when visiting 'select' insts in adjustMinMax(). Scalars were already handled there, and vector splats are handled after: https://reviews.llvm.org/rL285732 llvm-svn: 285744
* [ValueTracking] recognize more variants of smin/smaxSanjay Patel2016-10-291-10/+18
| | | | | | | | | | | | | Try harder to detect obfuscated min/max patterns: the initial pattern was added with D9352 / rL236202. There was a bug fix for PR27137 at rL264996, but I think we can do better by folding the corresponding smax pattern and commuted variants. The codegen tests demonstrate the effect of ValueTracking on the backend via SelectionDAGBuilder. We can't expose these differences minimally in IR because we don't have smin/smax intrinsics for IR. Differential Revision: https://reviews.llvm.org/D26091 llvm-svn: 285499
* [ValueTracking] fix matchSelectPattern to allow vector splat folds of ↵Sanjay Patel2016-10-271-6/+8
| | | | | | min/max/abs/nabs llvm-svn: 285303
* Analysis: Move llvm::getConstantRangeFromMetadata to IR library.Peter Collingbourne2016-10-211-22/+0
| | | | | | | | We're about to start using it there. Differential Revision: https://reviews.llvm.org/D25877 llvm-svn: 284865
* Test commit. (NFC)Li Huang2016-10-151-1/+1
| | | | llvm-svn: 284307
* [ValueTracking] An improvement to IR ValueTracking on Non-negative IntegersArtur Pilipenko2016-10-121-3/+46
| | | | | | | | | | Since this change is known to cause performance degradations in some cases it's commited under a temporary flag which is turned off by default. Patch by Li Huang Differential Revision: https://reviews.llvm.org/D18777 llvm-svn: 284022
* [ValueTracking] Fix crash in GetPointerBaseWithConstantOffset()Tom Stellard2016-10-071-9/+10
| | | | | | | | | | | | | | | | | | | Summary: While walking defs of pointer operands we were assuming that the pointer size would remain constant. This is not true, because addresspacecast instructions may cast the pointer to an address space with a different pointer width. This partial reverts r282612, which was a more conservative solution to this problem. Reviewers: reames, sanjoy, apilipenko Subscribers: wdng, llvm-commits Differential Revision: https://reviews.llvm.org/D24772 llvm-svn: 283557
* [ValueTracking] Teach computeKnownBits and ComputeNumSignBits to look ↵Bjorn Pettersson2016-10-061-0/+14
| | | | | | | | | | | | | | | through ExtractElement. Summary: The computeKnownBits and ComputeNumSignBits functions in ValueTracking can now do a simple look-through of ExtractElement. Reviewers: majnemer, spatel Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D24955 llvm-svn: 283434
* Don't look through addrspacecast in GetPointerBaseWithConstantOffsetArtur Pilipenko2016-09-281-2/+7
| | | | | | | | | | | | Pointers in different addrspaces can have different sizes, so it's not valid to look through addrspace cast calculating base and offset for a value. This is similar to D13008. Reviewed By: reames Differential Revision: https://reviews.llvm.org/D24729 llvm-svn: 282612
* Analysis: Return early for UndefValue in computeKnownBitsDuncan P. N. Exon Smith2016-09-241-0/+8
| | | | | | | | | There is no benefit in looking through assumptions on UndefValue to guess known bits. Return early to avoid walking their use-lists, and assert that all instances of ConstantData are handled here for similar reasons (UndefValue was the only integer/pointer holdout). llvm-svn: 282337
* Analysis: Return early in isKnownNonNullAt for ConstantDataDuncan P. N. Exon Smith2016-09-241-0/+4
| | | | | | | | | | | | | Check and return early for ConstantPointerNull and UndefValue specifically in isKnownNonNullAt, and assert that ConstantData never make it to isKnownNonNullFromDominatingCondition. This confirms that isKnownNonNullFromDominatingCondition never walks through the use-list of an instance of ConstantData. Given that such use-lists cross module boundaries, it never really made sense to do so, and was potentially very expensive. llvm-svn: 282333
* [InstCombine] allow vector types for constant folding / computeKnownBits ↵Sanjay Patel2016-09-161-3/+4
| | | | | | | | | | | | | | | | (PR24942) computeKnownBits() already works for integer vectors, so allow vector types when calling that from InstCombine. I don't think the change to use m_APInt in computeKnownBits is strictly necessary because we do check for ConstantVector later, but it's more efficient to handle the splat case without needing to loop on vector elements. This should work with InstSimplify, but doesn't yet, so I made that a FIXME comment on the test for PR24942: https://llvm.org/bugs/show_bug.cgi?id=24942 Differential Revision: https://reviews.llvm.org/D24677 llvm-svn: 281777
* The patch improves ValueTracking on left shift with nsw flag.Evgeny Stupachenko2016-08-241-5/+23
| | | | | | | | | | | | Summary: The patch fixes PR28946. Reviewers: majnemer, sanjoy Differential Revision: http://reviews.llvm.org/D23296 From: Li Huang llvm-svn: 279684
* [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
OpenPOWER on IntegriCloud