summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ValueTracking.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [APInt] Use isSubsetOf, intersects, and bit counting methods to reduce ↵Craig Topper2017-04-251-4/+4
| | | | | | | | | | | | | | temporary APInts This patch uses various APInt methods to reduce temporary APInt creation. This should be all of the unrelated cleanups that got buried in D32376(creating a KnownBits struct) as well as some pointed out by Simon during the review of that. Plus a few improvements to use counting instead of masking. I've left out any places where we do something like (KnownZero & KnownOne) != 0 as I plan to add a helper method to KnownBits to ask that question and didn't want to thrash that code an additional time. Differential Revision: https://reviews.llvm.org/D32495 llvm-svn: 301338
* [ValueTracking] Use APInt::operator|=(uint64_t) instead of creating a ↵Craig Topper2017-04-251-2/+2
| | | | | | temporary APInt. NFC llvm-svn: 301325
* [ValueTracking] Use APInt instead of auto. NFCCraig Topper2017-04-251-1/+1
| | | | | | This is a pre-commit for a patch I'm working on to turn KnownZero/One into a struct. Once I do that the type here will be less obvious. llvm-svn: 301324
* [ValueTracking] Use BitWidth local variable instead of re-reading it from ↵Craig Topper2017-04-251-1/+1
| | | | | | | | KnownZero. NFC This is a pre-commit for a patch that I'm working on to merge KnownZero/KnownOne into a KnownBits struct which would have had to touch this line. llvm-svn: 301323
* [ValueTracking] Use APInt::setAllBits and APInt::intersects to simplify some ↵Craig Topper2017-04-211-3/+4
| | | | | | code. NFC llvm-svn: 300997
* [APInt] Rename getSignBit to getSignMaskCraig Topper2017-04-201-3/+3
| | | | | | | | getSignBit is a static function that creates an APInt with only the sign bit set. getSignMask seems like a better name to convey its functionality. In fact several places use it and then store in an APInt named SignMask. Differential Revision: https://reviews.llvm.org/D32108 llvm-svn: 300856
* [APInt] Cast calls to add/sub/mul overflow methods to void if only their ↵Craig Topper2017-04-191-2/+2
| | | | | | | | | | overflow bool out param is used. This is preparation for a clang change to improve the [[nodiscard]] warning to not be ignored on methods that return a class marked [[nodiscard]] that are defined in the class itself. See D32207. We should consider adding wrapper methods to APInt that return the overflow flag directly and discard the APInt result. This would eliminate the void casts and the need to create a bool before the call to pass to the out param. llvm-svn: 300758
* [APInt] Use lshrInPlace to replace lshr where possibleCraig Topper2017-04-181-8/+13
| | | | | | | | | | This patch uses lshrInPlace to replace code where the object that lshr is called on is being overwritten with the result. This adds an lshrInPlace(const APInt &) version as well. Differential Revision: https://reviews.llvm.org/D32155 llvm-svn: 300566
* Introduce APInt::isSignBitSet/isSignBitClear. Use in place isSignBitSet in ↵Craig Topper2017-04-171-34/+34
| | | | | | | | place of isNegative in known bits tracking. This makes statements like KnownZero.isNegative() (which means the value we're tracking is positive) less confusing. llvm-svn: 300457
* [InstCombine][ValueTracking] When computing known bits for Srem make sure we ↵Craig Topper2017-04-161-8/+5
| | | | | | | | don't compute known bits for the LHS twice. If we already called computeKnownBits for the RHS being a constant power of 2, we've already computed everything we can and should just stop. I think previously we would still recurse if we had determined the result was negative or had not determined the sign bit at all. llvm-svn: 300432
* [ValueTracking] Calculate the KnownZeros for Intrinsic::ctpop without using ↵Craig Topper2017-04-141-5/+2
| | | | | | | | a temporary APInt to count leading zeros on. The APInt was created from an 'unsigned' and we just wanted to know how many bits the value needed to represent it. We can just use Log2_32 from MathExtras.h to get the info. llvm-svn: 300309
* [ValueTracking] Use APInt::isNegative(). NFCCraig Topper2017-04-141-1/+1
| | | | llvm-svn: 300308
* [ValueTracking] Use APInt::sext instead of zext and setBitsFrom. NFCCraig Topper2017-04-141-7/+2
| | | | llvm-svn: 300307
* [ValueTracking] Remove duplicate call to computeKnownBits for the operands ↵Craig Topper2017-04-131-5/+1
| | | | | | | | of Select. We call it unconditionally on the operands of the select. Then decide if its a min/max and call it on the min/max operands or on the select operands again. Either of those second calls will overwrite the results of the initial call so we can just delete the first call. llvm-svn: 300256
* [ValueTracking] Prevent a call to computeKnownBits if we already know the ↵Craig Topper2017-04-131-7/+8
| | | | | | state of the bit we would calculate. Also reuse a temporary APInt instead of creating a new one. llvm-svn: 300239
* [ValueTracking] Move a temporary APInt instead of copying it.Craig Topper2017-04-131-1/+1
| | | | llvm-svn: 300233
* [ValueTracking] Teach GetUnderlyingObject to stop when it reachs an alloca ↵Craig Topper2017-04-121-0/+3
| | | | | | | | instruction. Previously it tried to call SimplifyInstruction which doesn't know anything about alloca so defers to constant folding which also doesn't do anything with alloca. This results in wasted cycles making calls that won't do anything. Given the frequency with which this function is called this time adds up. llvm-svn: 300118
* [APInt] Remove shift functions from APIntOps namespace. Replace the few ↵Craig Topper2017-03-311-4/+4
| | | | | | users with the APInt class methods. NFCI llvm-svn: 299248
* Revert r298711 "[InstCombine] Provide a way to calculate KnownZero/One for ↵Craig Topper2017-03-241-35/+21
| | | | | | | | Add/Sub in SimplifyDemandedUseBits without recursing into ComputeKnownBits" Tsan bot is failing. llvm-svn: 298745
* [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
OpenPOWER on IntegriCloud