summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/InstructionSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* InstSimplify: Simplify (sub 0, X) -> X if it's NUWDavid Majnemer2014-11-221-11/+3
| | | | | | This is a generalization of the X - (0 - Y) -> X transform. llvm-svn: 222611
* Update SetVector to rely on the underlying set's insert to return a ↵David Blaikie2014-11-191-1/+1
| | | | | | | | | | | | | pair<iterator, bool> This is to be consistent with StringSet and ultimately with the standard library's associative container insert function. This lead to updating SmallSet::insert to return pair<iterator, bool>, and then to update SmallPtrSet::insert to return pair<iterator, bool>, and then to update all the existing users of those functions... llvm-svn: 222334
* InstSimplify: Optimize ICmpInst xform that uses computeKnownBitsDavid Majnemer2014-11-161-21/+17
| | | | | | | | | | | | A few things: - computeKnownBits is relatively expensive, let's delay its use as long as we can. - Don't create two APInt values just to run computeKnownBits on a ConstantInt, we already know the exact value! - Avoid creating a temporary APInt value in order to calculate unary negation. llvm-svn: 222092
* InstSimplify: Exact shifts of X by Y are X if X has the lsb setDavid Majnemer2014-11-051-11/+31
| | | | | | | | | Exact shifts may not shift out any non-zero bits. Use computeKnownBits to determine when this occurs and just return the left hand side. This fixes PR21477. llvm-svn: 221325
* InstSimplify: Fold a hasNoSignedWrap() call into a match() expressionDavid Majnemer2014-11-041-2/+1
| | | | | | No functionality change intended, it's just a little more concise. llvm-svn: 221281
* InstSimplify: Fold a hasNoUnsignedWrap() call into a match() expressionDavid Majnemer2014-11-041-2/+1
| | | | | | No functionality change intended, it's just a little more concise. llvm-svn: 221280
* InstCombine, InstSimplify: (%X /s C1) /s C2 isn't always 0 when C1 * C2 overflowDavid Majnemer2014-10-111-0/+10
| | | | | | | | | | | | | | | | | | consider: C1 = INT_MIN C2 = -1 C1 * C2 overflows without a doubt but consider the following: %x = i32 INT_MIN This means that (%X /s C1) is 1 and (%X /s C1) /s C2 is -1. N. B. Move the unsigned version of this transform to InstSimplify, it doesn't create any new instructions. This fixes PR21243. llvm-svn: 219567
* InstSimplify: Don't allow (x srem y) urem y -> x srem yDavid Majnemer2014-09-171-3/+5
| | | | | | | | | | | Let's consider the case where: %x i16 = 32768 %y i16 = 384 %x srem %y = 65408 (%x srem %y) urem %y = 128 llvm-svn: 217939
* InstSimplify: ((X % Y) % Y) -> (X % Y)David Majnemer2014-09-171-0/+5
| | | | | | | | Patch by Sonam Kumari! Differential Revision: http://reviews.llvm.org/D5350 llvm-svn: 217937
* InstSimplify: Simplify trivial and/or of icmpsDavid Majnemer2014-09-151-0/+114
| | | | | | | | | | | | | Some ICmpInsts when anded/ored with another ICmpInst trivially reduces to true or false depending on whether or not all integers or no integers satisfy the intersected/unioned range. This sort of trivial looking code can come about when InstCombine performs a range reduction-type operation on sdiv and the like. This fixes PR20916. llvm-svn: 217750
* Fix an ODR violation consisting of two 'struct Query' in the global namespace.Benjamin Kramer2014-09-121-0/+2
| | | | | | Put them in their own anonymous namespaces. Found by GCC's new -Wodr (PR20915). llvm-svn: 217662
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-071-115/+210
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This change, which allows @llvm.assume to be used from within computeKnownBits (and other associated functions in ValueTracking), adds some (optional) parameters to computeKnownBits and friends. These functions now (optionally) take a "context" instruction pointer, an AssumptionTracker pointer, and also a DomTree pointer, and most of the changes are just to pass this new information when it is easily available from InstSimplify, InstCombine, etc. As explained below, the significant conceptual change is that known properties of a value might depend on the control-flow location of the use (because we care that the @llvm.assume dominates the use because assumptions have control-flow dependencies). This means that, when we ask if bits are known in a value, we might get different answers for different uses. The significant changes are all in ValueTracking. Two main changes: First, as with the rest of the code, new parameters need to be passed around. To make this easier, I grouped them into a structure, and I made internal static versions of the relevant functions that take this structure as a parameter. The new code does as you might expect, it looks for @llvm.assume calls that make use of the value we're trying to learn something about (often indirectly), attempts to pattern match that expression, and uses the result if successful. By making use of the AssumptionTracker, the process of finding @llvm.assume calls is not expensive. Part of the structure being passed around inside ValueTracking is a set of already-considered @llvm.assume calls. This is to prevent a query using, for example, the assume(a == b), to recurse on itself. The context and DT params are used to find applicable assumptions. An assumption needs to dominate the context instruction, or come after it deterministically. In this latter case we only handle the specific case where both the assumption and the context instruction are in the same block, and we need to exclude assumptions from being used to simplify their own ephemeral values (those which contribute only to the assumption) because otherwise the assumption would prove its feeding comparison trivial and would be removed. This commit adds the plumbing and the logic for a simple masked-bit propagation (just enough to write a regression test). Future commits add more patterns (and, correspondingly, more regression tests). llvm-svn: 217342
* InstSimplify: Move a transform from InstCombine to InstSimplifyDavid Majnemer2014-08-281-0/+35
| | | | | | | | Several combines involving icmp (shl C2, %X) C1 can be simplified without introducing any new instructions. Move them to InstSimplify; while we are at it, make them more powerful. llvm-svn: 216642
* InstSimplify: Don't simplify gep X, (Y-X) to Y if types differDavid Majnemer2014-08-271-1/+2
| | | | | | | | | It's incorrect to perform this simplification if the types differ. A bitcast would need to be inserted for this to work. This fixes PR20771. llvm-svn: 216597
* Reland r216439 215441, majnemer has a real fix for PR20771.Nico Weber2014-08-271-11/+53
| | | | llvm-svn: 216586
* Revert r216439 (and r216441, else the former doesn't revert cleanly).Nico Weber2014-08-271-53/+11
| | | | | | It caused PR 20771. I'll land a test on the clang side. llvm-svn: 216582
* InstSimplify: Compute comparison ranges for left shift instructionsDavid Majnemer2014-08-271-0/+16
| | | | | | | | 'shl nuw CI, x' produces [CI, CI << CLZ(CI)] 'shl nsw CI, x' produces [CI << CLO(CI)-1, CI] if CI is negative 'shl nsw CI, x' produces [CI, CI << CLZ(CI)-1] if CI is non-negative llvm-svn: 216570
* InstSimplify: Fold gep X, (sub 0, ptrtoint(X)) to nullDavid Majnemer2014-08-261-21/+32
| | | | | | | Save InstCombine some work if we can perform this fold during InstSimplify. llvm-svn: 216441
* InstSimplify: Simplify trivial pointer expressions like b + (e - b)David Majnemer2014-08-261-5/+36
| | | | | | | | | | | | | | | | | | | | | | | | consider: long long *f(long long *b, long long *e) { return b + (e - b); } we would lower this to something like: define i64* @f(i64* %b, i64* %e) { %1 = ptrtoint i64* %e to i64 %2 = ptrtoint i64* %b to i64 %3 = sub i64 %1, %2 %4 = ashr exact i64 %3, 3 %5 = getelementptr inbounds i64* %b, i64 %4 ret i64* %5 } This should fold away to just 'e'. N.B. This adds m_SpecificInt as a convenient way to match against a particular 64-bit integer when using LLVM's match interface. llvm-svn: 216439
* InstSimplify: Simplify (X - (0 - Y)) if the second sub is NUWDavid Majnemer2014-07-311-0/+12
| | | | | | | | | | | If the NUW bit is set for 0 - Y, we know that all values for Y other than 0 would produce a poison value. This allows us to replace (0 - Y) with 0 in the expression (X - (0 - Y)) which will ultimately leave us with X. This partially fixes PR20189. llvm-svn: 214384
* Rectify r213231. Use proper version of 'ComputeNumSignBits'.Suyog Sarda2014-07-171-1/+1
| | | | | | | | | Earlier when the code was in InstCombine, we were calling the version of ComputeNumSignBits in InstCombine.h that automatically added the DataLayout* before calling into ValueTracking. When the code moved to InstSimplify, we are calling into ValueTracking directly without passing in the DataLayout*. This patch rectifies the same by passing DataLayout in ComputeNumSignBits. llvm-svn: 213295
* Move ashr optimization from InstCombineShift to InstSimplify.Suyog Sarda2014-07-171-0/+5
| | | | | | | | | Refactor code, no functionality change, test case moved from instcombine to instsimplify. Differential Revision: http://reviews.llvm.org/D4102 llvm-svn: 213231
* InstSimplify: Correct sdiv x / -1David Majnemer2014-07-141-11/+13
| | | | | | | | | | | Determining the bounds of x/ -1 would start off with us dividing it by INT_MIN. Suffice to say, this would not work very well. Instead, handle it upfront by checking for -1 and mapping it to the range: [INT_MIN + 1, INT_MAX. This means that the result of our division can be any value other than INT_MIN. llvm-svn: 212981
* InstSimplify: The upper bound of X / C was missing a rounding stepDavid Majnemer2014-07-141-1/+9
| | | | | | | | | | | | | | | | | | Summary: When calculating the upper bound of X / -8589934592, we would perform the following calculation: Floor[INT_MAX / 8589934592] However, flooring the result would make us wrongly come to the conclusion that 1073741824 was not in the set of possible values. Instead, use the ceiling of the result. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D4502 llvm-svn: 212976
* InstSimplify: Fix a bug when INT_MIN is in a sdivDavid Majnemer2014-07-041-3/+9
| | | | | | | | | | | | | When INT_MIN is the numerator in a sdiv, we would not properly handle overflow when calculating the bounds of possible values; abs(INT_MIN) is not a meaningful number. Instead, check and handle INT_MIN by reasoning that the largest value is INT_MIN/-2 and the smallest value is INT_MIN. This fixes PR20199. llvm-svn: 212307
* This patch removed duplicate code for matching patterns Dinesh Dwivedi2014-06-261-106/+1
| | | | | | | | | which are now handled in SimplifyUsingDistributiveLaws() (after r211261) Differential Revision: http://reviews.llvm.org/D4253 llvm-svn: 211768
* Move optimization of some cases of (A & C1)|(B & C2) from instcombine to ↵Nick Lewycky2014-06-191-0/+32
| | | | | | instsimplify. Patch by Rahul Jain, plus some last minute changes by me -- you can blame me for any bugs. llvm-svn: 211252
* Make instsimplify's analysis of icmp eq/ne use computeKnownBits to determine ↵Nick Lewycky2014-06-191-0/+19
| | | | | | whether the icmp is always true or false. Patch by Suyog Sarda! llvm-svn: 211251
* InstSimplify: Improve handling of ashr/lshrDavid Majnemer2014-05-161-1/+21
| | | | | | | | | | | | | | Summary: Analyze the range of values produced by ashr/lshr cst, %V when it is being used in an icmp. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3774 llvm-svn: 209000
* InstSimplify: Optimize using dividend in sdivDavid Majnemer2014-05-161-0/+4
| | | | | | | | | | | | | | | Summary: The dividend in an sdiv tells us the largest and smallest possible results. Use this fact to optimize comparisons against an sdiv with a constant dividend. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3795 llvm-svn: 208999
* InstSimplify: Optimize signed icmp of -(zext V)David Majnemer2014-05-141-0/+22
| | | | | | | | | | | | | | | | Summary: We know that -(zext V) will always be <= zero, simplify signed icmps that have these. Uncovered using http://www.cs.utah.edu/~regehr/souper/ Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3754 llvm-svn: 208809
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | definition below all the header #include lines, lib/Analysis/... edition. This one has a bit extra as there were *other* #define's before #include lines in addition to DEBUG_TYPE. I've sunk all of them as a block. llvm-svn: 206843
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-151-76/+76
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-7/+5
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* [Modules] Move the ConstantRange class into the IR library. This isChandler Carruth2014-03-041-1/+1
| | | | | | | | | | a bit surprising, as the class is almost entirely abstracted away from any particular IR, however it encodes the comparsion predicates which mutate ranges as ICmp predicate codes. This is reasonable as they're used for both instructions and constants. Thus, it belongs in the IR library with instructions and constants. llvm-svn: 202838
* [Modules] Move ValueHandle into the IR library where Value itself lives.Chandler Carruth2014-03-041-1/+1
| | | | | | | | | | | Move the test for this class into the IR unittests as well. This uncovers that ValueMap too is in the IR library. Ironically, the unittest for ValueMap is useless in the Support library (honestly, so was the ValueHandle test) and so it already lives in the IR unittests. Mmmm, tasty layering. llvm-svn: 202821
* [Modules] Move the LLVM IR pattern match header into the IR library, itChandler Carruth2014-03-041-1/+1
| | | | | | obviously is coupled to the IR. llvm-svn: 202818
* [Modules] Move GetElementPtrTypeIterator into the IR library. As itsChandler Carruth2014-03-041-1/+1
| | | | | | | | | name might indicate, it is an iterator over the types in an instruction in the IR.... You see where this is going. Another step of modularizing the support library. llvm-svn: 202815
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-211-141/+141
| | | | | | | | | I am really sorry for the noise, but the current state where some parts of the code use TD (from the old name: TargetData) and other parts use DL makes it hard to write a patch that changes where those variables come from and how they are passed along. llvm-svn: 201827
* InstSimplify: Make shift, select and GEP simplifications vector-aware.Benjamin Kramer2014-01-241-18/+41
| | | | llvm-svn: 200016
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
* Re-sort all of the includes with ./utils/sort_includes.py so thatChandler Carruth2014-01-071-1/+1
| | | | | | | | | | subsequent changes are easier to review. About to fix some layering issues, and wanted to separate out the necessary churn. Also comment and sink the include of "Windows.h" in three .inc files to match the usage in Memory.inc. llvm-svn: 198685
* Teach MemoryBuiltins and InstructionSimplify that operator new never returns ↵Benjamin Kramer2013-09-241-1/+1
| | | | | | | | | | | | NULL. This is safe per C++11 18.6.1.1p3: [operator new returns] a non-null pointer to suitably aligned storage (3.7.4), or else throw a bad_alloc exception. This requirement is binding on a replacement version of this function. Brings us a tiny bit closer to eliminating more vector push_backs. llvm-svn: 191310
* InstSimplify: Fold equality comparisons between non-inbounds GEPs.Benjamin Kramer2013-09-231-2/+15
| | | | | | | | | Overflow doesn't affect the correctness of equalities. Computing this is cheap, we just reuse the computation for the inbounds case and try to peel of more non-inbounds GEPs. This pattern is unlikely to ever appear in code generated by Clang, but SCEV occasionally produces it. llvm-svn: 191200
* Add ISD::FROUND for libm round()Hal Finkel2013-08-071-0/+1
| | | | | | | | | | | | | | | All libm floating-point rounding functions, except for round(), had their own ISD nodes. Recent PowerPC cores have an instruction for round(), and so here I'm adding ISD::FROUND so that round() can be custom lowered as well. For the most part, this is straightforward. I've added an intrinsic and a matching ISD node just like those for nearbyint() and friends. The SelectionDAG pattern I've named frnd (because ISD::FP_ROUND has already claimed fround). This will be used by the PowerPC backend in a follow-up commit. llvm-svn: 187926
* Minor address space code simplification.Matt Arsenault2013-08-031-9/+3
| | | | | | Remove assertion that the verifier should catch. llvm-svn: 187692
* Teach InstructionSimplify about pointer address spacesMatt Arsenault2013-08-021-4/+9
| | | | llvm-svn: 187635
* Fix logic error optimizing "icmp pred (urem X, Y), Y" where pred is signed.Nick Lewycky2013-07-121-4/+7
| | | | | | Fixes PR16605. llvm-svn: 186229
* InstSimplify: X >> X -> 0David Majnemer2013-07-091-0/+8
| | | | llvm-svn: 185973
* InstructionSimplify.cpp: Fix a ligature, "fi", to get rid of utf8 in comment.NAKAMURA Takumi2013-04-081-1/+1
| | | | llvm-svn: 179066
OpenPOWER on IntegriCloud