summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/InstructionSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [InstCombine, InstSimplify] Move xforms from Combine to SimplifyDavid Majnemer2015-06-061-11/+138
| | | | | | | | There were several SelectInst combines that always returned an existing instruction instead of modifying an old one or creating a new one. These are prime candidates for moving to InstSimplify. llvm-svn: 239229
* [InstSimplify] Handle some overflow intrinsics in InstSimplifyDavid Majnemer2015-05-221-5/+43
| | | | | | | | | This change does a few things: - Move some InstCombine transforms to InstSimplify - Run SimplifyCall from within InstCombine::visitCallInst - Teach InstSimplify to fold [us]mul_with_overflow(X, undef) to 0. llvm-svn: 237995
* Change Function::getIntrinsicID() to return an Intrinsic::ID. NFC.Pete Cooper2015-05-201-2/+2
| | | | | | | | Now that Intrinsic::ID is a typed enum, we can forward declare it and so return it from this method. This updates all users which were either using an unsigned to store it, or had a now unnecessary cast. llvm-svn: 237810
* Convert PHI getIncomingValue() to foreach over incoming_values(). NFC.Pete Cooper2015-05-121-6/+3
| | | | | | | | We already had a method to iterate over all the incoming values of a PHI. This just changes all eligible code to use it. Ineligible code included anything which cared about the index, or was also trying to get the i'th incoming BB. llvm-svn: 237169
* [opaque pointer type] API migration for GEP constant factoriesDavid Blaikie2015-04-021-10/+15
| | | | | | | | | | | | | Require the pointee type to be passed explicitly and assert that it is correct. For now it's possible to pass nullptr here (and I've done so in a few places in this patch) but eventually that will be disallowed once all clients have been updated or removed. It'll be a long road to get all the way there... but if you have the cahnce to update your callers to pass the type explicitly without depending on a pointer's element type, that would be a good thing to do soon and a necessary thing to do eventually. llvm-svn: 233938
* [opaque pointer type] Change GetElementPtrInst::getIndexedType to take the ↵David Blaikie2015-03-301-1/+2
| | | | | | | | | | pointee type This pushes the use of PointerType::getElementType up into several callers - I'll essentially just have to keep pushing that up the stack until I can eliminate every call to it... llvm-svn: 233604
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-58/+53
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | Summary: Now that the DataLayout is a mandatory part of the module, let's start cleaning the codebase. This patch is a first attempt at doing that. This patch is not exactly NFC as for instance some places were passing a nullptr instead of the DataLayout, possibly just because there was a default value on the DataLayout argument to many functions in the API. Even though it is not purely NFC, there is no change in the validation. I turned as many pointer to DataLayout to references, this helped figuring out all the places where a nullptr could come up. I had initially a local version of this patch broken into over 30 independant, commits but some later commit were cleaning the API and touching part of the code modified in the previous commits, so it seemed cleaner without the intermediate state. Test Plan: Reviewers: echristo Subscribers: llvm-commits From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231740
* InstCombine: fix fold "fcmp x, undef" to account for NaNMehdi Amini2015-03-091-2/+7
| | | | | | | | | | | | | | | | | | | | | | | | Summary: See the two test cases. ; Can fold fcmp with undef on one side by choosing NaN for the undef ; Can fold fcmp with undef on both side ; fcmp u_pred undef, undef -> true ; fcmp o_pred undef, undef -> false ; because whatever you choose for the first undef ; you can choose NaN for the other undef Reviewers: hfinkel, chandlerc, majnemer Reviewed By: majnemer Subscribers: majnemer, llvm-commits Differential Revision: http://reviews.llvm.org/D7617 From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 231626
* InstSimplify: simplify 0 / X if nnan and nszMehdi Amini2015-02-231-14/+30
| | | | | From: Fiona Glaser <fglaser@apple.com> llvm-svn: 230238
* InstCombine: cleanup redundant dyn_cast<> (NFC)Mehdi Amini2015-02-131-44/+43
| | | | | From: Mehdi Amini <mehdi.amini@apple.com> llvm-svn: 229075
* [InstSimplify] Add SimplifyFPBinOp function.Michael Zolotukhin2015-02-061-0/+30
| | | | | | | | | | | | | | | | | | | | | | | | | | It is a variation of SimplifyBinOp, but it takes into account FastMathFlags. It is needed in inliner and loop-unroller to accurately predict the transformation's outcome (previously we dropped the flags and were too conservative in some cases). Example: float foo(float *a, float b) { float r; if (a[1] * b) r = /* a lot of expensive computations */; else r = 1; return r; } float boo(float *a) { return foo(a, 0.0); } Without this patch, we don't inline 'foo' into 'boo'. llvm-svn: 228432
* Fold fcmp in cases where value is provably non-negative. By Arch Robison.Elena Demikhovsky2015-01-281-0/+14
| | | | | | | | | | | | This patch folds fcmp in some cases of interest in Julia. The patch adds a function CannotBeOrderedLessThanZero that returns true if a value is provably not less than zero. I.e. the function returns true if the value is provably -0, +0, positive, or a NaN. The patch extends InstructionSimplify.cpp to fold instances of fcmp where: - the predicate is olt or uge - the first operand is provably not less than zero - the second operand is zero The motivation for handling these cases optimizing away domain checks for sqrt in Julia for common idioms such as sqrt(x*x+y*y).. http://reviews.llvm.org/D6972 llvm-svn: 227298
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-041-182/+163
| | | | | | | | | | | | | | | | | | | | | | | | | | | | a cache of assumptions for a single function, and an immutable pass that manages those caches. The motivation for this change is two fold. Immutable analyses are really hacks around the current pass manager design and don't exist in the new design. This is usually OK, but it requires that the core logic of an immutable pass be reasonably partitioned off from the pass logic. This change does precisely that. As a consequence it also paves the way for the *many* utility functions that deal in the assumptions to live in both pass manager worlds by creating an separate non-pass object with its own independent API that they all rely on. Now, the only bits of the system that deal with the actual pass mechanics are those that actually need to deal with the pass mechanics. Once this separation is made, several simplifications become pretty obvious in the assumption cache itself. Rather than using a set and callback value handles, it can just be a vector of weak value handles. The callers can easily skip the handles that are null, and eventually we can wrap all of this up behind a filter iterator. For now, this adds boiler plate to the various passes, but this kind of boiler plate will end up making it possible to port these passes to the new pass manager, and so it will end up factored away pretty reasonably. llvm-svn: 225131
* InstSimplify: Don't bother if getScalarSizeInBits returns zeroDavid Majnemer2014-12-201-4/+5
| | | | | | | getScalarSizeInBits returns zero when the comparison operands are not integral. No functionality change intended. llvm-svn: 224675
* Simplify the codeDavid Majnemer2014-12-201-41/+25
| | | | | | No functionality change intended. llvm-svn: 224673
* InstSimplify: Optimize away pointless comparisonsDavid Majnemer2014-12-201-2/+38
| | | | | | | | | (X & INT_MIN) ? X & INT_MAX : X into X & INT_MAX (X & INT_MIN) ? X : X & INT_MAX into X (X & INT_MIN) ? X | INT_MIN : X into X (X & INT_MIN) ? X : X | INT_MIN into X | INT_MIN llvm-svn: 224669
* InstSimplify: shl nsw/nuw undef, %V -> undefDavid Majnemer2014-12-171-13/+7
| | | | | | | | | | We can always choose an value for undef which might cause %V to shift out an important bit except for one case, when %V is zero. However, shl behaves like an identity function when the right hand side is zero. llvm-svn: 224405
* ConstantFold, InstSimplify: undef >>a x can be either -1 or 0, choose 0David Majnemer2014-12-101-2/+2
| | | | | | Zero is usually a nicer constant to have than -1. llvm-svn: 223969
* InstSimplify: [al]shr exact undef, %X -> undefDavid Majnemer2014-12-101-2/+6
| | | | | | | Exact shifts always keep the non-zero bits of their input. This means it keeps it's undef bits. llvm-svn: 223923
* InstSimplify: div %X, 0 -> undefDavid Majnemer2014-12-101-0/+4
| | | | | | We already optimized rem %X, 0 to undef, we should do the same for div. llvm-svn: 223919
* InstSimplify: Try to bring back the rest of r223583David Majnemer2014-12-081-2/+7
| | | | | | | This reverts r223624 with a small tweak, hopefully this will make stage3 equivalent. llvm-svn: 223679
* Revert a part of r223583, for now. It seems causing different emission ↵NAKAMURA Takumi2014-12-081-5/+0
| | | | | | between stage2(gcc-clang) and stage3 clang. Investigating. llvm-svn: 223624
* InstSimplify: Optimize away useless unsigned comparisonsDavid Majnemer2014-12-061-0/+49
| | | | | | Code like X < Y && Y == 0 should always be folded away to false. llvm-svn: 223583
* Revert "r223364 - Revert r223347 which has caused crashes on bootstrap bots."Hal Finkel2014-12-041-3/+14
| | | | | | | | | | | | | | | | | | | | Reapply r223347, with a fix to not crash on uninserted instructions (or more precisely, instructions in uninserted blocks). bugpoint was able to reduce the test case somewhat, but it is still somewhat large (and relies on setting things up to be simplified during inlining), so I've not included it here. Nevertheless, it is clear what is going on and why. Original commit message: Restrict somewhat the memory-allocation pointer cmp opt from r223093 Based on review comments from Richard Smith, restrict this optimization from applying to globals that might resolve lazily to other dynamically-loaded modules, and also from dynamic allocas (which might be transformed into malloc calls). In short, take extra care that the compared-to pointer is really simultaneously live with the memory allocation. llvm-svn: 223371
* Revert r223347 which has caused crashes on bootstrap bots.Alexander Potapenko2014-12-041-13/+3
| | | | llvm-svn: 223364
* Restrict somewhat the memory-allocation pointer cmp opt from r223093Hal Finkel2014-12-041-3/+13
| | | | | | | | | | Based on review comments from Richard Smith, restrict this optimization from applying to globals that might resolve lazily to other dynamically-loaded modules, and also from dynamic allocas (which might be transformed into malloc calls). In short, take extra care that the compared-to pointer is really simultaneously live with the memory allocation. llvm-svn: 223347
* Simplify pointer comparisons involving memory allocation functionsHal Finkel2014-12-011-0/+35
| | | | | | | | | | | | | System memory allocation functions, which are identified at the IR level by the noalias attribute on the return value, must return a pointer into a memory region disjoint from any other memory accessible to the caller. We can use this property to simplify pointer comparisons between allocated memory and local stack addresses and the addresses of global variables. Neither the stack nor global variables can overlap with the region used by the memory allocator. Fixes PR21556. llvm-svn: 223093
* InstSimplify: Restore optimizations lost in r210006David Majnemer2014-11-271-0/+34
| | | | | | | | | | This restores our ability to optimize: (X & C) ? X & ~C : X into X & ~C (X & C) ? X : X & ~C into X (X & C) ? X | C : X into X (X & C) ? X : X | C into X | C llvm-svn: 222868
* InstSimplify: Handle some simple tautological comparisonsDavid Majnemer2014-11-251-0/+34
| | | | | | | | This handles cases where we are comparing a masked value against itself. The analysis could be further improved by making it recursive but such expense is not currently justified. llvm-svn: 222716
* 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
OpenPOWER on IntegriCloud