summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ValueTracking.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [InstCombine] Provide a way to calculate KnownZero/One for Add/Sub in ↵Craig Topper2017-03-241-21/+35
| | | | | | | | SimplifyDemandedUseBits without recursing into ComputeKnownBits SimplifyDemandedUseBits for Add/Sub already recursed down LHS and RHS for simplifying bits. If that didn't provide any simplifications we fall back to calling computeKnownBits which will recurse again. Instead just take the known bits for LHS and RHS we already have and call into a new function in ValueTracking that can calculate the known bits given the LHS/RHS bits. llvm-svn: 298711
* [ValueTracking] Use uint64_t for CarryIn in computeKnownBitsAddSub instead ↵Craig Topper2017-03-241-2/+2
| | | | | | of a creating a temporary APInt. NFC llvm-svn: 298688
* [ValueTracking] Convert more places to use ↵Craig Topper2017-03-241-7/+6
| | | | | | setHighBits/setLowBits/setSignBit. NFCI llvm-svn: 298683
* [ValueTracking] Use APInt::isNegative instead of using operator[BitWidth-1]. ↵Craig Topper2017-03-231-7/+7
| | | | | | NFCI llvm-svn: 298584
* [ValueTracking] Use setAllBits/setSignBit/setLowBits/setHighBits. NFCICraig Topper2017-03-231-20/+22
| | | | llvm-svn: 298583
* [ValueTracking] Make sure we keep range metadata information when ↵Craig Topper2017-03-221-2/+2
| | | | | | calculating known bits for calls to bitreverse intrinsic. llvm-svn: 298488
* [ValueTracking] use setLowBits/setHighBits/setBitsFrom to replace |= ↵Craig Topper2017-03-221-16/+13
| | | | | | getHighBits/getLowBits. NFCI llvm-svn: 298486
* [ValueTracking] Remove deadish code from computeKnownBitsAddSub.Craig Topper2017-03-181-24/+0
| | | | | | The code assigned to KnownZero, but later code unconditionally assigned over it. I'm pretty sure the later code can handle the same cases and more equally well. llvm-svn: 298190
* [ValueTracking] Add APInt::setSignBit and use it to replace ORing with ↵Craig Topper2017-03-181-6/+6
| | | | | | getSignBit which will malloc if the bit width is larger than 64. llvm-svn: 298180
* [ValueTracking] Out of range shifts might be undefOliver Stannard2017-03-141-0/+8
| | | | | | | | | | | | | | If it is possible for the RHS of a shift operation to be greater than or equal to the bit-width, then the result might be undef, and we can't report any known bits. In some cases, this was allowing a transformation in instcombine which widened an undef value from i1 to i32, increasing the range of values that a function could return. Differential revision: https://reviews.llvm.org/D30781 llvm-svn: 297724
* Handle UnreachableInst in isGuaranteedToTransferExecutionToSuccessorSebastian Pop2017-03-081-0/+2
| | | | | | | | | | | A block with an UnreachableInst does not transfer execution to a successor. The problem was exposed by GVN-hoist. This patch fixes bug 32153. Patch by Aditya Kumar. Differential Revision: https://reviews.llvm.org/D30667 llvm-svn: 297254
* [ValueTracking] Don't do an unchecked shift in ComputeNumSignBitsSanjoy Das2017-02-251-2/+21
| | | | | | | | | | | | | | | | | | | | | | Summary: Previously we used to return a bogus result, 0, for IR like `ashr %val, -1`. I've also added an assert checking that `ComputeNumSignBits` at least returns 1. That assert found an already checked in test case where we were returning a bad result for `ashr %val, -1`. Fixes PR32045. Reviewers: spatel, majnemer Reviewed By: spatel, majnemer Subscribers: efriedma, mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D30311 llvm-svn: 296273
* [ValueTracking] Make poison propagation more aggressiveSanjoy Das2017-02-221-49/+3
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Motivation: fix PR31181 without regression (the actual fix is still in progress). However, the actual content of PR31181 is not relevant here. This change makes poison propagation more aggressive in the following cases: 1. poision * Val == poison, for any Val. In particular, this changes existing intentional and documented behavior in these two cases: a. Val is 0 b. Val is 2^k * N 2. poison << Val == poison, for any Val 3. getelementptr is poison if any input is poison I think all of these are justified (and are axiomatically true in the new poison / undef model): 1a: we need poison * 0 to be poison to allow transforms like these: A * (B + C) ==> A * B + A * C If poison * 0 were 0 then the above transform could not be allowed since e.g. we could have A = poison, B = 1, C = -1, making the LHS poison * (1 + -1) = poison * 0 = 0 and the RHS poison * 1 + poison * -1 = poison + poison = poison 1b: we need e.g. poison * 4 to be poison since we want to allow A * 4 ==> A + A + A + A If poison * 4 were a value with all of their bits poison except the last four; then we'd not be able to do this transform since then if A were poison the LHS would only be "partially" poison while the RHS would be "full" poison. 2: Same reasoning as (1b), we'd like have the following kinds transforms be legal: A << 1 ==> A + A Reviewers: majnemer, efriedma Subscribers: mcrosier, llvm-commits Differential Revision: https://reviews.llvm.org/D30185 llvm-svn: 295809
* [ValueTracking] clang-format a section I'm about to touch; NFCSanjoy Das2017-02-211-64/+64
| | | | | | (Whitespace only change) llvm-svn: 295690
* [ValueTracking] use nonnull argument attribute to eliminate null checksSanjay Patel2017-02-121-5/+17
| | | | | | | | | | | Enhancing value tracking's analysis of null-ness was suggested in D27855, so here's a first attempt at that. This is part of solving: https://llvm.org/bugs/show_bug.cgi?id=28430 Differential Revision: https://reviews.llvm.org/D28204 llvm-svn: 294897
* [ValueTracking] emit a remark when we detect a conflicting assumption (PR31809)Sanjay Patel2017-02-061-12/+23
| | | | | | | | | | | | This is a follow-up to D29395 where we try to be good citizens and let the user know that we've probably gone off the rails. This should allow us to resolve: https://llvm.org/bugs/show_bug.cgi?id=31809 Differential Revision: https://reviews.llvm.org/D29404 llvm-svn: 294208
* [ValueTracking] remove a FIXME for something we don't want to do; NFCSanjay Patel2017-02-011-4/+0
| | | | | | | | The comment was added with: https://reviews.llvm.org/rL293773 ...but there would be a cost to implement this and possibly no payoff. llvm-svn: 293823
* [ValueTracking] avoid crashing from bad assumptions (PR31809)Sanjay Patel2017-02-011-0/+17
| | | | | | | | | | | | | A program may contain llvm.assume info that disagrees with other analysis. This may be caused by UB in the program, so we must not crash because of that. As noted in the code comments: https://llvm.org/bugs/show_bug.cgi?id=31809 ...we can do better, but this at least avoids the assert/crash in the bug report. Differential Revision: https://reviews.llvm.org/D29395 llvm-svn: 293773
* [ValueTracking] clean up lookThroughCast; NFCISanjay Patel2017-01-291-42/+48
| | | | | | | | | 1. Use auto with dyn_cast. 2. Don't use else after return. 3. Convert chain of 'else if' to switch. 4. Improve variable names. llvm-svn: 293432
* [ValueTracking] Add comment that CannotBeOrderedLessThanZero does the wrong ↵Justin Lebar2017-01-271-0/+19
| | | | | | | | | | | | | | | | | | | | | | | | thing for powi. Summary: CannotBeOrderedLessThanZero(powi(x, exp)) returns true if CannotBeOrderedLessThanZero(x). But powi(-0, exp) is negative if exp is odd, so we actually want to return SignBitMustBeZero(x). Except that also isn't right, because we want to return true if x is NaN, even if x has a negative sign bit. What we really need in order to fix this is a consistent approach in this function to handling the sign bit of NaNs. Without this it's very difficult to say what the correct behavior here is. Reviewers: hfinkel, efriedma, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28927 llvm-svn: 293243
* [ValueTracking] Implement SignBitMustBeZero correctly for sqrt.Justin Lebar2017-01-261-4/+12
| | | | | | | | | | | | | | Summary: Previously we assumed that the result of sqrt(x) always had 0 as its sign bit. But sqrt(-0) == -0. Reviewers: hfinkel, efriedma, sanjoy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28928 llvm-svn: 293115
* Mark @llvm.powi.* as safe to speculatively execute.whitequark2017-01-251-0/+4
| | | | | | | | | | | | Floating point intrinsics in LLVM are generally not speculatively executed, since most of them are defined to behave the same as libm functions, which set errno. However, the @llvm.powi.* intrinsics do not correspond to any libm function, and lacks any defined error handling semantics in LangRef. It most certainly does not alter errno. llvm-svn: 293041
* [Analysis] Add LibFunc_ prefix to enums in TargetLibraryInfo. (NFC)David L. Jones2017-01-231-58/+58
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: The LibFunc::Func enum holds enumerators named for libc functions. Unfortunately, there are real situations, including libc implementations, where function names are actually macros (musl uses "#define fopen64 fopen", for example; any other transitively visible macro would have similar effects). Strictly speaking, a conforming C++ Standard Library should provide any such macros as functions instead (via <cstdio>). However, there are some "library" functions which are not part of the standard, and thus not subject to this rule (fopen64, for example). So, in order to be both portable and consistent, the enum should not use the bare function names. The old enum naming used a namespace LibFunc and an enum Func, with bare enumerators. This patch changes LibFunc to be an enum with enumerators prefixed with "LibFFunc_". (Unfortunately, a scoped enum is not sufficient to override macros.) There are additional changes required in clang. Reviewers: rsmith Subscribers: mehdi_amini, mzolotukhin, nemanjai, llvm-commits Differential Revision: https://reviews.llvm.org/D28476 llvm-svn: 292848
* [ValueTracking] tighten up matchMinMax(); NFCISanjay Patel2017-01-211-40/+14
| | | | | | | | | This is similar to what the caller (matchSelectPattern()) does. In all cases where we succeed in matching a min/max pattern, the values in that pattern will be the values of the 'select', so hoist that and remove a bunch of duplicated code. llvm-svn: 292725
* [ValueTracking] recognize variations of 'clamp' to improve codegen (PR31693)Sanjay Patel2017-01-201-1/+39
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | By enhancing value tracking, we allow an existing min/max canonicalization to kick in and improve codegen for several targets that have min/max instructions. Unfortunately, recognizing min/max in value tracking may cause us to hit a hack in InstCombiner::visitICmpInst() more often: http://lists.llvm.org/pipermail/llvm-dev/2017-January/109340.html ...but I'm hoping we can remove that soon. Correctness proofs based on Alive: Name: smaxmin Pre: C1 < C2 %cmp2 = icmp slt i8 %x, C2 %min = select i1 %cmp2, i8 %x, i8 C2 %cmp3 = icmp slt i8 %x, C1 %r = select i1 %cmp3, i8 C1, i8 %min => %cmp2 = icmp slt i8 %x, C2 %min = select i1 %cmp2, i8 %x, i8 C2 %cmp1 = icmp sgt i8 %min, C1 %r = select i1 %cmp1, i8 %min, i8 C1 Name: sminmax Pre: C1 > C2 %cmp2 = icmp sgt i8 %x, C2 %max = select i1 %cmp2, i8 %x, i8 C2 %cmp3 = icmp sgt i8 %x, C1 %r = select i1 %cmp3, i8 C1, i8 %max => %cmp2 = icmp sgt i8 %x, C2 %max = select i1 %cmp2, i8 %x, i8 C2 %cmp1 = icmp slt i8 %max, C1 %r = select i1 %cmp1, i8 %max, i8 C1 ---------------------------------------- Optimization: smaxmin Done: 1 Optimization is correct! ---------------------------------------- Optimization: sminmax Done: 1 Optimization is correct! Name: umaxmin Pre: C1 u< C2 %cmp2 = icmp ult i8 %x, C2 %min = select i1 %cmp2, i8 %x, i8 C2 %cmp3 = icmp ult i8 %x, C1 %r = select i1 %cmp3, i8 C1, i8 %min => %cmp2 = icmp ult i8 %x, C2 %min = select i1 %cmp2, i8 %x, i8 C2 %cmp1 = icmp ugt i8 %min, C1 %r = select i1 %cmp1, i8 %min, i8 C1 Name: uminmax Pre: C1 u> C2 %cmp2 = icmp ugt i8 %x, C2 %max = select i1 %cmp2, i8 %x, i8 C2 %cmp3 = icmp ugt i8 %x, C1 %r = select i1 %cmp3, i8 C1, i8 %max => %cmp2 = icmp ugt i8 %x, C2 %max = select i1 %cmp2, i8 %x, i8 C2 %cmp1 = icmp ult i8 %max, C1 %r = select i1 %cmp1, i8 %max, i8 C1 ---------------------------------------- Optimization: umaxmin Done: 1 Optimization is correct! ---------------------------------------- Optimization: uminmax Done: 1 Optimization is correct! llvm-svn: 292660
* [ValueTracking] recognize a 'not' of an assumed condition as falseSanjay Patel2017-01-171-0/+7
| | | | | | | | Also, add the corresponding match to the AssumptionCache's 'Affected Values' list. Differential Revision: https://reviews.llvm.org/D28485 llvm-svn: 292239
* [ValueTracking] Extend known bits to understand @llvm.bitreverse.Chad Rosier2017-01-171-0/+5
| | | | | | Differential Revision: https://reviews.llvm.org/D28780 llvm-svn: 292233
* Remove unused lambda captures. NFCMalcolm Parsons2017-01-131-3/+3
| | | | llvm-svn: 291916
* Make processing @llvm.assume more efficient - Add affected values to the ↵Hal Finkel2017-01-111-1/+4
| | | | | | | | | | | | | | | | | | | | | | | | assumption cache Here's my second try at making @llvm.assume processing more efficient. My previous attempt, which leveraged operand bundles, r289755, didn't end up working: it did make assume processing more efficient but eliminating the assumption cache made ephemeral value computation too expensive. This is a more-targeted change. We'll keep the assumption cache, but extend it to keep a map of affected values (i.e. values about which an assumption might provide some information) to the corresponding assumption intrinsics. This allows ValueTracking and LVI to find assumptions relevant to the value being queried without scanning all assumptions in the function. The fact that ValueTracking started doing O(number of assumptions in the function) work, for every known-bits query, has become prohibitively expensive in some cases. As discussed during the review, this is a pragmatic fix that, longer term, will likely be replaced by a more-principled solution (perhaps based on an extended SSA form). Differential Revision: https://reviews.llvm.org/D28459 llvm-svn: 291671
* InstSimplify: Eliminate fabs on known positiveMatt Arsenault2017-01-111-20/+51
| | | | llvm-svn: 291624
* Intrinsic::Bitreverse is safe to speculateXin Tong2017-01-091-0/+1
| | | | | | | | | | | | Summary: Intrinsic::Bitreverse is safe to speculate Reviewers: hfinkel, mkuper, arsenm, jmolloy Subscribers: llvm-commits Differential Revision: https://reviews.llvm.org/D28471 llvm-svn: 291456
* [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
OpenPOWER on IntegriCloud