summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineAddSub.cpp
Commit message (Collapse)AuthorAgeFilesLines
* 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
* Added instruction combine to transform few more negative values addition to ↵Dinesh Dwivedi2014-06-191-0/+45
| | | | | | | | | | | | subtraction (Part 1) This patch enables transforms for following patterns. (x + (~(y & c) + 1) --> x - (y & c) (x + (~((y >> z) & c) + 1) --> x - ((y>>z) & c) Differential Revision: http://reviews.llvm.org/D3733 llvm-svn: 211266
* Refactored and updated SimplifyUsingDistributiveLaws() to Dinesh Dwivedi2014-06-191-52/+0
| | | | | | | | | | | | * Find factorization opportunities using identity values. * Find factorization opportunities by treating shl(X, C) as mul (X, shl(C)) * Keep NSW flag while simplifying instruction using factorization. This fixes PR19263. Differential Revision: http://reviews.llvm.org/D3799 llvm-svn: 211261
* [InstCombine] mark ADD with nuw if no unsigned overflowJingyue Wu2014-06-171-0/+22
| | | | | | | | | | | | | | | | | | | | | | Summary: As a starting step, we only use one simple heuristic: if the sign bits of both a and b are zero, we can prove "add a, b" do not unsigned overflow, and thus convert it to "add nuw a, b". Updated all affected tests and added two new tests (@zero_sign_bit and @zero_sign_bit2) in AddOverflow.ll Test Plan: make check-all Reviewers: eliben, rafael, meheff, chandlerc Reviewed By: chandlerc Subscribers: chandlerc, llvm-commits Differential Revision: http://reviews.llvm.org/D4144 llvm-svn: 211084
* InstCombine: Improvement to check if signed addition overflows.Rafael Espindola2014-06-041-7/+46
| | | | | | | | | | | | | | | | | | This patch implements two things: 1. If we know one number is positive and another is negative, we return true as signed addition of two opposite signed numbers will never overflow. 2. Implemented TODO : If one of the operands only has one non-zero bit, and if the other operand has a known-zero bit in a more significant place than it (not including the sign bit) the ripple may go up to and fill the zero, but won't change the sign. e.x - (x & ~4) + 1 We make sure that we are ignoring 0 at MSB. Patch by Suyog Sarda. llvm-svn: 210186
* Add back commit r210029.Rafael Espindola2014-06-021-4/+19
| | | | | | | | The code was actually correct. Sorry for the confusion. I have expanded the comment saying why the analysis is valid to avoid me misunderstaning it again in the future. llvm-svn: 210052
* Revert "Add the nsw flag when we detect that an add will not signed overflow."Rafael Espindola2014-06-021-5/+0
| | | | | | | | | This reverts commit r210029. It was not correctly handling cases where LHS and RHS had multiple but different sign bits. llvm-svn: 210048
* Add the nsw flag when we detect that an add will not signed overflow.Rafael Espindola2014-06-021-0/+5
| | | | | | | We already had a function for checking this, we were just using it only in specialized cases. llvm-svn: 210029
* Revert "Revert "Revert "InstCombine: Improvement to check if signed addition ↵Rafael Espindola2014-05-291-44/+6
| | | | | | | | | | overflows.""" This reverts commit r209776. It was miscompiling llvm::SelectionDAGISel::MorphNode. llvm-svn: 209817
* Revert "Revert "InstCombine: Improvement to check if signed addition ↵Rafael Espindola2014-05-281-6/+44
| | | | | | | | overflows."" This reverts commit r209762, bringing back r209746. It was not responsible for the libc++ build failure llvm-svn: 209776
* Revert "InstCombine: Improvement to check if signed addition overflows."Rafael Espindola2014-05-281-44/+6
| | | | | | | | | This reverts commit r209746. It looks it is causing a crash while building libcxx. I am trying to get a reduced testcase. llvm-svn: 209762
* InstCombine: Improvement to check if signed addition overflows.Rafael Espindola2014-05-281-6/+44
| | | | | | | | | | | | | | | | | | This patch implements two things: 1. If we know one number is positive and another is negative, we return true as signed addition of two opposite signed numbers will never overflow. 2. Implemented TODO : If one of the operands only has one non-zero bit, and if the other operand has a known-zero bit in a more significant place than it (not including the sign bit) the ripple may go up to and fill the zero, but won't change the sign. e.x - (x & ~4) + 1 We make sure that we are ignoring 0 at MSB. Patch by Suyog Sarda. llvm-svn: 209746
* Rename ComputeMaskedBits to computeKnownBits. "Masked" has beenJay Foad2014-05-141-3/+3
| | | | | | inappropriate since it lost its Mask parameter in r154011. llvm-svn: 208811
* Reorder shuffle and binary operation.Serge Pavlov2014-05-111-0/+12
| | | | | | | | | | | | | This patch enables transformations: BinOp(shuffle(v1), shuffle(v2)) -> shuffle(BinOp(v1, v2)) BinOp(shuffle(v1), const1) -> shuffle(BinOp, const2) They allow to eliminate extra shuffles in some cases. Differential Revision: http://reviews.llvm.org/D3525 llvm-svn: 208488
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-41/+41
| | | | llvm-svn: 207196
* [Modules] Fix potential ODR violations by sinking the DEBUG_TYPEChandler Carruth2014-04-221-1/+2
| | | | | | | | | | | | | | | | | definition below all of the header #include lines, lib/Transforms/... edition. This one is tricky for two reasons. We again have a couple of passes that define something else before the includes as well. I've sunk their name macros with the DEBUG_TYPE. Also, InstCombine contains headers that need DEBUG_TYPE, so now those headers #define and #undef DEBUG_TYPE around their code, leaving them well formed modular headers. Fixing these headers was a large motivation for all of these changes, as "leaky" macros of this form are hard on the modules implementation. llvm-svn: 206844
* [Modules] Sink all the DEBUG_TYPE defines for InstCombine out of theChandler Carruth2014-04-211-0/+1
| | | | | | | | | | | header files and into the cpp files. These files will require more touches as the header files actually use DEBUG(). Eventually, I'll have to introduce a matched #define and #undef of DEBUG_TYPE for the header files, but that comes as step N of many to clean all of this up. llvm-svn: 206777
* [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-6/+6
| | | | | | | | | 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
* Fix all the remaining lost-fast-math-flags bugs I've been able to find. The ↵Owen Anderson2014-01-201-8/+26
| | | | | | | | most important of these are cases in the generic logic for combining BinaryOperators. This logic hadn't been updated to handle FastMathFlags, and it took me a while to detect it because it doesn't show up in a simple search for CreateFAdd. llvm-svn: 199629
* InstCombine: Hoist 3 copies of AddOne/SubOne into a header.Benjamin Kramer2014-01-191-11/+0
| | | | llvm-svn: 199605
* InstCombine: Teach most integer add/sub/mul/div combines how to deal with ↵Benjamin Kramer2014-01-191-55/+60
| | | | | | vectors. llvm-svn: 199602
* Fix two cases where we could lose fast math flags when optimizing FADD ↵Owen Anderson2014-01-161-4/+10
| | | | | | expressions. llvm-svn: 199427
* Preserve fast-math flags when folding (fsub x, (fneg y)) to (fadd x, y).Owen Anderson2013-07-301-4/+11
| | | | llvm-svn: 187462
* Fix variable name.Owen Anderson2013-07-261-2/+2
| | | | llvm-svn: 187253
* When InstCombine tries to fold away (fsub x, (fneg y)) into (fadd x, y), it isOwen Anderson2013-07-261-1/+13
| | | | | | | also worthwhile for it to look through FP extensions and truncations, whose application commutes with fneg. llvm-svn: 187249
* InstCombine: call FoldOpIntoSelect for all floating binops, not just fmulStephen Lin2013-07-201-3/+14
| | | | llvm-svn: 186759
* Restore r181216, which was partially reverted in r182499.Stephen Lin2013-07-171-43/+0
| | | | llvm-svn: 186533
* Use llvm::array_lengthof to replace sizeof(array)/sizeof(array[0]).Craig Topper2013-07-151-1/+2
| | | | llvm-svn: 186301
* Don't use a potentially expensive shift if all we want is one set bit.Benjamin Kramer2013-07-111-1/+1
| | | | | | No functionality change. llvm-svn: 186095
* In InstCombine{AddSub,MulDivRem} convert APFloat.isFiniteNonZero() && ↵Michael Gottesman2013-06-261-1/+1
| | | | | | !APFloat.isDenormal => APFloat.isNormal. llvm-svn: 185037
* [APFloat] Converted all references to APFloat::isNormal => ↵Michael Gottesman2013-06-191-1/+1
| | | | | | | | APFloat::isFiniteNonZero. Turns out all the references were in llvm and not in clang. llvm-svn: 184356
* This is an update to a previous commit (r181216).Jean-Luc Duprat2013-05-221-0/+43
| | | | | | | | | | | | | | | | | | | | | | | The earlier change list introduced the following inst combines: B * (uitofp i1 C) —> select C, B, 0 A * (1 - uitofp i1 C) —> select C, 0, A select C, 0, B + select C, A, 0 —> select C, A, B Together these 3 changes would simplify : A * (1 - uitofp i1 C) + B * uitofp i1 C down to : select C, B, A In practice we found that the first two substitutions can have a negative effect on performance, because they reduce opportunities to use FMA contractions; between the two options FMAs are often the better choice. This change list amends the previous one to enable just these inst combines: select C, B, 0 + select C, 0, A —> select C, B, A A * (1 - uitofp i1 C) + B * uitofp i1 C —> select C, B, A llvm-svn: 182499
* InstCombine: (X ^ signbit) + C -> X + (signbit ^ C)David Majnemer2013-05-061-0/+5
| | | | llvm-svn: 181249
* Provide InstCombines for the following 3 cases:Jean-Luc Duprat2013-05-061-0/+25
| | | | | | | | | | | | | A * (1 - (uitofp i1 C)) -> select C, 0, A B * (uitofp i1 C) -> select C, B, 0 select C, 0, A + select C, B, 0 -> select C, B, A These come up in code that has been hand-optimized from a select to a linear blend, on platforms where that may have mattered. We want to undo such changes with the following transform: A*(1 - uitofp i1 C) + B*(uitofp i1 C) -> select C, A, B llvm-svn: 181216
* Tidy up a bit. No functional change.Jim Grosbach2013-04-051-58/+60
| | | | llvm-svn: 178915
OpenPOWER on IntegriCloud