summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/InstructionSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [ValueTracking] Add parameters to isImpliedCondition; NFCSanjoy Das2015-11-061-3/+3
| | | | | | | | | | | | | | | | Summary: This change makes the `isImpliedCondition` interface similar to the rest of the functions in ValueTracking (in that it takes a DataLayout, AssumptionCache etc.). This is an NFC, intended to make a later diff less noisy. Depends on D14369 Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D14391 llvm-svn: 252333
* [InstSimplify] sgt on i1s also encodes implicationPhilip Reames2015-10-291-0/+11
| | | | | | | | | | | | | | | Follow on to http://reviews.llvm.org/D13074, implementing something pointed out by Sanjoy. His truth table from his comment on that bug summarizes things well: LHS | RHS | LHS >=s RHS | LHS implies RHS 0 | 0 | 1 (0 >= 0) | 1 0 | 1 | 1 (0 >= -1) | 1 1 | 0 | 0 (-1 >= 0) | 0 1 | 1 | 1 (-1 >= -1) | 1 The key point is that an "i1 1" is the value "-1", not "1". Differential Revision: http://reviews.llvm.org/D13756 llvm-svn: 251597
* [ValueTracking] Expose `implies` via ValueTracking, NFCSanjoy Das2015-10-281-50/+2
| | | | | | | | | | | | Summary: This will allow a later patch to `JumpThreading` use this functionality. Reviewers: reames Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13971 llvm-svn: 251488
* Extract out getConstantRangeFromMetadata; NFCSanjoy Das2015-10-241-31/+5
| | | | | | | | | | | | The loop idiom creating a ConstantRange is repeated twice in the codebase, time to give it a name and a home. The loop is also repeated in `rangeMetadataExcludesValue`, but using `getConstantRangeFromMetadata` there would not be an NFC -- the range returned by `getConstantRangeFromMetadata` may contain a value that none of the subranges did. llvm-svn: 251180
* Fix whitespace issues in two places; NFCSanjoy Das2015-10-241-1/+2
| | | | llvm-svn: 251179
* Handle non-constant shifts in computeKnownBits, and use computeKnownBits for ↵Hal Finkel2015-10-231-0/+11
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | constant folding in InstCombine/Simplify First, the motivation: LLVM currently does not realize that: ((2072 >> (L == 0)) >> 7) & 1 == 0 where L is some arbitrary value. Whether you right-shift 2072 by 7 or by 8, the lowest-order bit is always zero. There are obviously several ways to go about fixing this, but the generic solution pursued in this patch is to teach computeKnownBits something about shifts by a non-constant amount. Previously, we would give up completely on these. Instead, in cases where we know something about the low-order bits of the shift-amount operand, we can combine (and together) the associated restrictions for all shift amounts consistent with that knowledge. As a further generalization, I refactored all of the logic for all three kinds of shifts to have this capability. This works well in the above case, for example, because the dynamic shift amount can only be 0 or 1, and thus we can say a lot about the known bits of the result. This brings us to the second part of this change: Even when we know all of the bits of a value via computeKnownBits, nothing used to constant-fold the result. This introduces the necessary code into InstCombine and InstSimplify. I've added it into both because: 1. InstCombine won't automatically pick up the associated logic in InstSimplify (InstCombine uses InstSimplify, but not via the API that passes in the original instruction). 2. Putting the logic in InstCombine allows the resulting simplifications to become part of the iterative worklist 3. Putting the logic in InstSimplify allows the resulting simplifications to be used by everywhere else that calls SimplifyInstruction (inlining, unrolling, and many others). And this requires a small change to our definition of an ephemeral value so that we don't break the rest case from r246696 (where the icmp feeding the @llvm.assume, is also feeding a br). Under the old definition, the icmp would not be considered ephemeral (because it is used by the br), but this causes the assume to remove itself (in addition to simplifying the branch structure), and it seems more-useful to prevent that from happening. llvm-svn: 251146
* [ValueTracking] Add a new predicate: isKnownNonEqual()James Molloy2015-10-221-0/+8
| | | | | | | | | | | | | | isKnownNonEqual(A, B) returns true if it can be determined that A != B. At the moment it only knows two facts, that a non-wrapping add of nonzero to a value cannot be that value: A + B != A [where B != 0, addition is nsw or nuw] and that contradictory known bits imply two values are not equal. This patch also hooks this up to InstSimplify; InstSimplify had a peephole for the first fact but not the second so this teaches InstSimplify a new trick too (alas no measured performance impact!) llvm-svn: 251012
* Fix pr25040 - Handle vectors of i1s in recently added implication codePhilip Reames2015-10-061-4/+11
| | | | | | | | As mentioned in the bug, I'd missed the presence of a getScalarType in the caller of the new implies method. As a result, when we ended up with a implication over two vectors, we'd trip an assert and crash. Differential Revision: http://reviews.llvm.org/D13441 llvm-svn: 249442
* [InstSimplify] Fold simple known implications to truePhilip Reames2015-09-281-0/+47
| | | | | | | | | | This was split off of http://reviews.llvm.org/D13040 to make it easier to test the correctness of the implication logic. For the moment, this only handles a single easy case which shows up when eliminating and combining range checks. In the (near) future, I plan to extend this for other cases which show up in range checks, but I wanted to make those changes incrementally once the framework was in place. At the moment, the implication logic will be used by three places. One in InstSimplify (this review) and two in SimplifyCFG (http://reviews.llvm.org/D13040 & http://reviews.llvm.org/D13070). Can anyone think of other locations this style of reasoning would make sense? Differential Revision: http://reviews.llvm.org/D13074 llvm-svn: 248719
* [Bug 24848] Use range metadata to constant fold comparisons between two valuesChen Li2015-09-261-0/+26
| | | | | | | | | | | | | | | Summary: This is the second part of fixing bug 24848 https://llvm.org/bugs/show_bug.cgi?id=24848. If both operands of a comparison have range metadata, they should be used to constant fold the comparison. Reviewers: sanjoy, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D13177 llvm-svn: 248650
* [Bug 24848] Use range metadata to constant fold comparisons with constant valuesChen Li2015-09-231-2/+32
| | | | | | | | | | | | | | | Summary: This is the first part of fixing bug 24848 https://llvm.org/bugs/show_bug.cgi?id=24848. When range metadata is provided, it should be used to constant fold comparisons with constant values. Reviewers: sanjoy, hfinkel Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D12988 llvm-svn: 248402
* [InstSimplify] add nuw %x, C2 must be at least C2David Majnemer2015-08-201-0/+3
| | | | | | | Use the fact that add nuw always creates a larger bit pattern when trying to simplify comparisons. llvm-svn: 245638
* [InstSimplify] Remove unused variableDavid Majnemer2015-08-181-6/+2
| | | | | | No functionality change is intended. llvm-svn: 245369
* [InstSimplify] Don't assume getAggregateElement will succeedDavid Majnemer2015-08-181-5/+0
| | | | | | | It isn't always possible to get a value from getAggregateElement. This fixes PR24488. llvm-svn: 245365
* [IR] Give catchret an optional 'return value' operandDavid Majnemer2015-08-151-2/+2
| | | | | | | | | | | Some personality routines require funclet exit points to be clearly marked, this is done by producing a token at the funclet pad and consuming it at the corresponding ret instruction. CleanupReturnInst already had a spot for this operand but CatchReturnInst did not. Other personality routines don't need to use this which is why it has been made optional. llvm-svn: 245149
* [InstSimplify] Teach InstSimplify how to simplify extractelementDavid Majnemer2015-07-131-0/+48
| | | | llvm-svn: 242008
* [InstSimplify] Teach InstSimplify how to simplify extractvalueDavid Majnemer2015-07-131-0/+41
| | | | llvm-svn: 242007
* [InstSimplify] Fold away ord/uno fcmps when nnan is present.Benjamin Kramer2015-07-101-8/+17
| | | | | | | This is important to fold away the slow case of complex multiplies emitted by clang. llvm-svn: 241911
* [InstSimplify] Allow folding of fdiv X, X with just NaNs ignoredBenjamin Kramer2015-06-161-3/+3
| | | | | | | | Any combination of +-inf/+-inf is NaN so it's already ignored with nnan and we can skip checking for ninf. Also rephrase logic in comments a bit. llvm-svn: 239821
* [InstSimplify] fsub nnan x, x -> 0.0 is valid without ninfBenjamin Kramer2015-06-141-2/+2
| | | | | | | Both inf - inf and (-inf) - (-inf) are NaN, so it's already covered by nnan. llvm-svn: 239702
* [InstSimplify] Add self-fdiv identities for -ffinite-math-only.Benjamin Kramer2015-06-141-0/+15
| | | | | | | | | When NaNs and Infs are ignored we can fold X / X -> 1.0 -X / X -> -1.0 X / -X -> -1.0 llvm-svn: 239701
* [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
OpenPOWER on IntegriCloud