summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [InstCombine] add a wrapper for a common pair of transforms; NFCISanjay Patel2017-01-101-9/+3
| | | | | | | Some of the callers are artificially limiting this transform to integer types; this should make it easier to incrementally remove that restriction. llvm-svn: 291620
* [InstCombine] Combine adds across a zextDavid Majnemer2017-01-041-0/+12
| | | | | | | | | We can perform the following: (add (zext (add nuw X, C1)), C2) -> (zext (add nuw X, C1+C2)) This is only possible if C2 is negative and C2 is greater than or equal to negative C1. llvm-svn: 290927
* [InstCombine] Address post-commit feedbackDavid Majnemer2016-12-301-1/+2
| | | | llvm-svn: 290741
* [InstCombine] More thoroughly canonicalize the position of zextsDavid Majnemer2016-12-301-9/+47
| | | | | | | | We correctly canonicalized (add (sext x), (sext y)) to (sext (add x, y)) where possible. However, we didn't perform the same canonicalization for zexts or for muls. llvm-svn: 290733
* Revert @llvm.assume with operator bundles (r289755-r289757)Daniel Jasper2016-12-191-5/+5
| | | | | | | 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-5/+5
| | | | | | | | | 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
* [InstCombine] use m_APInt to allow sub with constant folds for splat vectorsSanjay Patel2016-10-141-18/+19
| | | | llvm-svn: 284247
* [InstCombine] sub X, sext(bool Y) -> add X, zext(bool Y)Sanjay Patel2016-10-141-0/+11
| | | | | | | | | | | | Prefer add/zext because they are better supported in terms of value-tracking. Note that the backend should be prepared for this IR canonicalization (including vector types) after: https://reviews.llvm.org/rL284015 Differential Revision: https://reviews.llvm.org/D25135 llvm-svn: 284241
* InstCombine: Replace some never-null pointers with references. NFCJustin Bogner2016-08-051-5/+5
| | | | llvm-svn: 277792
* [InstCombine] fold add(zext(xor X, C), C) --> sext X when C is INT_MIN in ↵Sanjay Patel2016-07-191-0/+10
| | | | | | | | | | | | | | | | | | | the source type The pattern may look more obviously like a sext if written as: define i32 @g(i16 %x) { %zext = zext i16 %x to i32 %xor = xor i32 %zext, 32768 %add = add i32 %xor, -32768 ret i32 %add } We already have that fold in visitAdd(). Differential Revision: https://reviews.llvm.org/D22477 llvm-svn: 276035
* [InstCombine] allow X + signbit --> X ^ signbit for vector splatsSanjay Patel2016-07-161-3/+10
| | | | llvm-svn: 275691
* Apply clang-tidy's modernize-loop-convert to most of lib/Transforms.Benjamin Kramer2016-06-261-6/+3
| | | | | | Only minor manual fixes. No functionality change intended. llvm-svn: 273808
* Delete more dead code.Rafael Espindola2016-06-221-22/+0
| | | | | | Found by gcc 6. llvm-svn: 273402
* Remove uses of builtin comma operator.Richard Trieu2016-02-181-5/+12
| | | | | | Cleanup for upcoming Clang warning -Wcomma. No functionality change intended. llvm-svn: 261270
* Fix Clang-tidy readability-redundant-control-flow warnings; other minor fixes.Eugene Zelenko2016-02-021-2/+0
| | | | | | Differential revision: http://reviews.llvm.org/D16793 llvm-svn: 259539
* function names start with a lowercase letter; NFCSanjay Patel2016-02-011-15/+15
| | | | llvm-svn: 259425
* [InstCombine] Fix indentation. NFC.Craig Topper2015-12-211-2/+2
| | | | llvm-svn: 256131
* Fix some Clang-tidy modernize warnings, other minor fixes.Eugene Zelenko2015-11-041-14/+12
| | | | | | | | Fixed warnings are: modernize-use-override, modernize-use-nullptr and modernize-redundant-void-arg. Differential revision: http://reviews.llvm.org/D14312 llvm-svn: 252087
* don't repeat function names in comments; NFCSanjay Patel2015-09-091-1/+1
| | | | llvm-svn: 247154
* [InstCombine] Generalize sub of selects optimization to all BinaryOperatorsDavid Majnemer2015-07-141-26/+0
| | | | | | | This exposes further optimization opportunities if the selects are correlated. llvm-svn: 242235
* Revert r240137 (Fixed/added namespace ending comments using clang-tidy. NFC)Alexander Kornienko2015-06-231-1/+1
| | | | | | Apparently, the style needs to be agreed upon first. llvm-svn: 240390
* [InstCombine] Optimize subtract of selects into a select of a subDavid Majnemer2015-06-231-0/+26
| | | | | | | This came up when examining some code generated by clang's IRGen for certain member pointers. llvm-svn: 240369
* Fixed/added namespace ending comments using clang-tidy. NFCAlexander Kornienko2015-06-191-1/+1
| | | | | | | | | | | | | The patch is generated using this command: tools/clang/tools/extra/clang-tidy/tool/run-clang-tidy.py -fix \ -checks=-*,llvm-namespace-comment -header-filter='llvm/.*|clang/.*' \ llvm/lib/ Thanks to Eugene Kosov for the original patch! llvm-svn: 240137
* [ValueTracking] refactor: extract method haveNoCommonBitsSetJingyue Wu2015-05-141-14/+2
| | | | | | | | | | | | | | | | | | | | | Summary: Extract method haveNoCommonBitsSet so that we don't have to duplicate this logic in InstCombine and SeparateConstOffsetFromGEP. This patch also makes SeparateConstOffsetFromGEP more precise by passing DominatorTree to computeKnownBits. Test Plan: value-tracking-domtree.ll that tests ValueTracking indeed leverages dominating conditions Reviewers: broune, meheff, majnemer Reviewed By: majnemer Subscribers: jholewinski, llvm-commits Differential Revision: http://reviews.llvm.org/D9734 llvm-svn: 237407
* InstCombine: Move Sub->Xor rule from SimplifyDemanded to InstCombineMatthias Braun2015-04-301-0/+13
| | | | | | | | | | The rule that turns a sub to xor if the LHS is 2^n-1 and the remaining bits are known zero, does not use the demanded bits at all: Move it to the normal InstCombine code path. Differential Revision: http://reviews.llvm.org/D9417 llvm-svn: 236268
* DataLayout is mandatory, update the API to reflect it with references.Mehdi Amini2015-03-101-44/+44
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* [PM] Rename InstCombine.h to InstCombineInternal.h in preparation forChandler Carruth2015-01-221-1/+1
| | | | | | | | | | | | | | | | creating a non-internal header file for the InstCombine pass. I thought about calling this InstCombiner.h or in some way more clearly associating it with the InstCombiner clas that it is primarily defining, but there are several other utility interfaces defined within this for InstCombine. If, in the course of refactoring, those end up moving elsewhere or going away, it might make more sense to make this the combiner's header alone. Naturally, this is a bikeshed to a certain degree, so feel free to lobby for a different shade of paint if this name just doesn't suit you. llvm-svn: 226783
* Analysis: Reformulate WillNotOverflowUnsignedAdd for reusabilityDavid Majnemer2015-01-071-17/+3
| | | | | | | | WillNotOverflowUnsignedAdd's smarts will live in ValueTracking as computeOverflowForUnsignedAdd. It now returns a tri-state result: never overflows, always overflows and sometimes overflows. llvm-svn: 225329
* [PM] Split the AssumptionTracker immutable pass into two separate APIs:Chandler Carruth2015-01-041-6/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* InstCombine: fsub nsz 0, X ==> fsub nsz -0.0, XSanjay Patel2014-12-311-0/+8
| | | | | | | | | | | | | Some day the backend may handle instruction-level fast math flags and make this transform unnecessary, but it's still better practice to use the canonical representation of fneg when possible (use a -0.0). This is a partial fix for PR20870 ( http://llvm.org/bugs/show_bug.cgi?id=20870 ). See also http://reviews.llvm.org/D6723. Differential Revision: http://reviews.llvm.org/D6731 llvm-svn: 225050
* InstCombe: Infer nsw for multipliesDavid Majnemer2014-12-261-87/+38
| | | | | | | We already utilize this logic for reducing overflow intrinsics, it makes sense to reuse it for normal multiplies as well. llvm-svn: 224847
* use -0.0 when creating an fneg instructionSanjay Patel2014-12-191-1/+1
| | | | | | | | | | | | | | | | | | | Backends recognize (-0.0 - X) as the canonical form for fneg and produce better code. Eg, ppc64 with 0.0: lis r2, ha16(LCPI0_0) lfs f0, lo16(LCPI0_0)(r2) fsubs f1, f0, f1 blr vs. -0.0: fneg f1, f1 blr Differential Revision: http://reviews.llvm.org/D6723 llvm-svn: 224583
* fix formatting; NFCSanjay Patel2014-12-181-8/+4
| | | | llvm-svn: 224542
* Strength reduce intrinsics with overflow into regular arithmetic operations ↵Erik Eckstein2014-12-171-0/+45
| | | | | | | | | | if possible. Some intrinsics, like s/uadd.with.overflow and umul.with.overflow, are already strength reduced. This change adds other arithmetic intrinsics: s/usub.with.overflow, smul.with.overflow. It completes the work on PR20194. llvm-svn: 224417
* InstCombine: Combine (X | Y) - X to (~X & Y)David Majnemer2014-11-031-6/+15
| | | | | | | | This implements the transformation from (X | Y) - X to (~X & Y). Differential Revision: http://reviews.llvm.org/D5791 llvm-svn: 221129
* InstCombine: (sub (or A B) (xor A B)) --> (and A B)David Majnemer2014-10-191-0/+9
| | | | | | | | | | | The following implements the transformation: (sub (or A B) (xor A B)) --> (and A B). Patch by Ankur Garg! Differential Revision: http://reviews.llvm.org/D5719 llvm-svn: 220163
* Format spacing and remove extra lines to comply with standards. NFC.Suyog Sarda2014-10-081-5/+6
| | | | | | | Differential Revision: http://reviews.llvm.org/D5649 llvm-svn: 219286
* Make use of @llvm.assume in ValueTracking (computeKnownBits, etc.)Hal Finkel2014-09-071-30/+38
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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
* InstCombine: sub nsw %x, C -> add nsw %x, -C if C isn't INT_MINDavid Majnemer2014-08-221-1/+4
| | | | | | We can preserve nsw during this transform if -C won't overflow. llvm-svn: 216269
* InstCombine: Annotate sub with nuw when we prove it's safeDavid Majnemer2014-08-201-0/+18
| | | | | | | We can prove that a 'sub' can be a 'sub nuw' if the left-hand side is negative and the right-hand side is non-negative. llvm-svn: 216045
* InstCombine: Annotate sub with nsw when we prove it's safeDavid Majnemer2014-08-191-1/+39
| | | | | | | | | | We can prove that a 'sub' can be a 'sub nsw' under certain conditions: - The sign bits of the operands is the same. - Both operands have more than 1 sign bit. The subtraction cannot be a signed overflow in either case. llvm-svn: 216037
* InstCombine: Fix a potential bug in 0 - (X sdiv C) -> (X sdiv -C)David Majnemer2014-08-161-1/+1
| | | | | | | | | | | | | | | While *most* (X sdiv 1) operations will get caught by InstSimplify, it is still possible for a sdiv to appear in the worklist which hasn't been simplified yet. This means that it is possible for 0 - (X sdiv 1) to get transformed into (X sdiv -1); dividing by -1 can make the transform produce undef values instead of the proper result. Sorry for the lack of testcase, it's a bit problematic because it relies on the exact order of operations in the worklist. llvm-svn: 215818
* InstCombine: Combine (add (and %a, %b) (or %a, %b)) to (add %a, %b)David Majnemer2014-08-111-1/+23
| | | | | | | | | | | | | | What follows bellow is a correctness proof of the transform using CVC3. $ < t.cvc A, B : BITVECTOR(32); QUERY BVPLUS(32, A & B, A | B) = BVPLUS(32, A, B); $ cvc3 < t.cvc Valid. llvm-svn: 215400
* InstCombine: Correctly propagate NSW/NUW for x-(-A) -> x+ADavid Majnemer2014-07-311-3/+9
| | | | | | | | | | | | We can only propagate the nsw bits if both subtraction instructions are marked with the appropriate bit. N.B. We only propagate the nsw bit in InstCombine because the nuw case is already handled in InstSimplify. This fixes PR20189. llvm-svn: 214385
* Fix Typo (first commit to test commit access)Suyog Sarda2014-07-171-1/+1
| | | | llvm-svn: 213228
* Make helper functions static.Benjamin Kramer2014-07-071-2/+2
| | | | llvm-svn: 212460
* InstCombine: Don't turn -(x/INT_MIN) -> x/INT_MINDavid Majnemer2014-07-021-3/+3
| | | | | | | | | It is not safe to negate the smallest signed integer, doing so yields the same number back. This fixes PR20186. llvm-svn: 212164
* Added instruction combine to transform few more negative values addition to ↵Dinesh Dwivedi2014-06-271-48/+62
| | | | | | | | | | | | subtraction (Part 3) This patch enables transforms for (x + (~(y | c) + 1) --> x - (y | c) if c is odd Differential Revision: http://reviews.llvm.org/D4210 llvm-svn: 211881
* This patch removed duplicate code for matching patterns Dinesh Dwivedi2014-06-261-36/+0
| | | | | | | | | which are now handled in SimplifyUsingDistributiveLaws() (after r211261) Differential Revision: http://reviews.llvm.org/D4253 llvm-svn: 211768
* Added instruction combine to transform few more negative values addition to ↵Dinesh Dwivedi2014-06-261-49/+54
| | | | | | | | | | | | subtraction (Part 2) This patch enables transforms for (x + (~(y | c) + 1) --> x - (y | c) if c is even Differential Revision: http://reviews.llvm.org/D4209 llvm-svn: 211765
OpenPOWER on IntegriCloud