summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
Commit message (Collapse)AuthorAgeFilesLines
* This patch implements optimization as mentioned in PR19753: Optimize ↵Suyog Sarda2014-07-221-0/+93
| | | | | | | | | | | | | | | | | comparisons with "ashr/lshr exact" of a constanst. It handles the errors which were seen in PR19958 where wrong code was being emitted due to earlier patch. Added code for lshr as well as non-exact right shifts. It implements : (icmp eq/ne (ashr/lshr const2, A), const1)" -> (icmp eq/ne A, Log2(const2/const1)) -> (icmp eq/ne A, Log2(const2) - Log2(const1)) Differential Revision: http://reviews.llvm.org/D4068 llvm-svn: 213678
* InstCombine: Simplify code, no functionality change.Benjamin Kramer2014-07-071-16/+2
| | | | llvm-svn: 212449
* InstCombine: Disable umul.with.overflow recognition for vectors.Benjamin Kramer2014-06-241-1/+5
| | | | | | It doesn't make a lot on most targets and the code isn't ready for it. PR20113. llvm-svn: 211583
* Look through addrspacecasts when turning ptr comparisons intoMatt Arsenault2014-06-091-5/+21
| | | | | | index comparisons. llvm-svn: 210488
* Revert 209903 and 210040.Rafael Espindola2014-06-071-40/+0
| | | | | | | | | | | | The messages were "PR19753: Optimize comparisons with "ashr exact" of a constanst." "Added support to optimize comparisons with "lshr exact" of a constant." They were not correctly handling signed/unsigned operation differences, causing pr19958. llvm-svn: 210393
* Added support to optimize comparisons with "lshr exact" of a constant.Rafael Espindola2014-06-021-6/+29
| | | | | | Patch by Rahul Jain. llvm-svn: 210040
* Added inst combine tarnsform for (1 << X) & C pattrens where C is (some ↵Dinesh Dwivedi2014-06-021-8/+24
| | | | | | | | | | | | PowerOf2 - 1) This patch can handles following cases from http://nondot.org/sabre/LLVMNotes/InstCombine.txt "((1 << X) & 7) == 0" ==> "X > 2" "((1 << X) & 7) != 0" ==> "X < 3". Differential Revision: http://reviews.llvm.org/D3678 llvm-svn: 210007
* PR19753: Optimize comparisons with "ashr exact" of a constanst.Rafael Espindola2014-05-301-0/+17
| | | | | | Patch by suyog sarda. llvm-svn: 209903
* InstCombine: Optimize -x s< cstDavid Majnemer2014-05-151-0/+10
| | | | | | | | | | | | | | Summary: This gets rid of a sub instruction by moving the negation to the constant when valid. Reviewers: nicholas Subscribers: llvm-commits Differential Revision: http://reviews.llvm.org/D3773 llvm-svn: 208827
* Rename ComputeMaskedBits to computeKnownBits. "Masked" has beenJay Foad2014-05-141-1/+1
| | | | | | inappropriate since it lost its Mask parameter in r154011. llvm-svn: 208811
* [C++] Use 'nullptr'. Transforms edition.Craig Topper2014-04-251-79/+79
| | | | 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
* Use APInt arithmetic, fixed typo. Thanks to Benjamin Kramer for noticing that.Serge Pavlov2014-04-141-2/+2
| | | | llvm-svn: 206144
* Recognize test for overflow in integer multiplication.Serge Pavlov2014-04-131-0/+240
| | | | | | | | | | | | | | | | | | If multiplication involves zero-extended arguments and the result is compared as in the patterns: %mul32 = trunc i64 %mul64 to i32 %zext = zext i32 %mul32 to i64 %overflow = icmp ne i64 %mul64, %zext or %overflow = icmp ugt i64 %mul64 , 0xffffffff then the multiplication may be replaced by call to umul.with.overflow. This change fixes PR4917 and PR4918. Differential Revision: http://llvm-reviews.chandlerc.com/D2814 llvm-svn: 206137
* Revert "InstCombine: merge constants in both operands of icmp."Erik Verbruggen2014-03-281-14/+0
| | | | | | | | | This reverts commit r204912, and follow-up commit r204948. This introduced a performance regression, and the fix is not completely clear yet. llvm-svn: 205010
* InstCombine: Don't combine constants on unsigned icmpsReid Kleckner2014-03-271-1/+2
| | | | | | | | | Fixes a miscompile introduced in r204912. It would miscompile code like (unsigned)(a + -49) <= 5U. The transform would turn this into (unsigned)a < 55U, which would return true for values in [0, 49], when it should not. llvm-svn: 204948
* InstCombine: merge constants in both operands of icmp.Erik Verbruggen2014-03-271-0/+13
| | | | | | | | | | Transform: icmp X+Cst2, Cst into: icmp X, Cst-Cst2 when Cst-Cst2 does not overflow, and the add has nsw. llvm-svn: 204912
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-7/+6
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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 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
* Make some DataLayout pointers const.Rafael Espindola2014-02-241-1/+1
| | | | | | No functionality change. Just reduces the noise of an upcoming patch. llvm-svn: 202087
* Rename many DataLayout variables from TD to DL.Rafael Espindola2014-02-211-23/+23
| | | | | | | | | 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
* Remove a very old instcombine where we would turn sequences of selects intoOwen Anderson2014-02-121-25/+0
| | | | | | | | | | | | | logical operations on the i1's driving them. This is a bad idea for every target I can think of (confirmed with micro tests on all of: x86-64, ARM, AArch64, Mips, and PowerPC) because it forces the i1 to be materialized into a general purpose register, whereas consuming it directly into a select generally allows it to exist only transiently in a predicate or flags register. Chandler ran a set of performance tests with this change, and reported no measurable change on x86-64. llvm-svn: 201275
* Fix known typosAlp Toker2014-01-241-2/+2
| | | | | | | Sweep the codebase for common typos. Includes some changes to visible function names that were misspelt. llvm-svn: 200018
* InstCombine: Hoist 3 copies of AddOne/SubOne into a header.Benjamin Kramer2014-01-191-9/+0
| | | | llvm-svn: 199605
* Stay classy (and legal) LLVM. Remove links to 3rd party SMT solver whose ↵Kay Tiong Khoo2013-12-191-4/+2
| | | | | | links may not be permanent. llvm-svn: 197713
* Improved fix for PR17827 (instcombine of shift/and/compare).Kay Tiong Khoo2013-12-191-22/+32
| | | | | | | | | This change fixes the case of arithmetic shift right - do not attempt to fold that case. This change also relaxes the conditions when attempting to fold the logical shift right and shift left cases. No additional IR-level test cases included at this time. See http://llvm.org/bugs/show_bug.cgi?id=17827 for proofs that these are correct transformations. llvm-svn: 197705
* Use local variable for repeated use rather than 'get' method. No functional ↵Kay Tiong Khoo2013-12-021-4/+3
| | | | | | change intended. llvm-svn: 196164
* Move variables to where they are used and give them better names. No ↵Kay Tiong Khoo2013-12-021-6/+8
| | | | | | functional change intended. llvm-svn: 196163
* Rename variables to be consistent (CST -> Cst). No functional change intended.Kay Tiong Khoo2013-12-021-30/+30
| | | | llvm-svn: 196161
* Conservative fix for PR17827 - don't optimize a shift + and + compare ↵Kay Tiong Khoo2013-12-021-4/+12
| | | | | | sequence where the shift is logical unless the comparison is unsigned llvm-svn: 196129
* InstCombine: fold (A >> C) == (B >> C) --> (A^B) < (1 << C) for constant Cs.Benjamin Kramer2013-11-161-0/+18
| | | | | | This is common in bitfield code. llvm-svn: 194925
* Use right address space size in InstCombineComparesMatt Arsenault2013-09-301-3/+6
| | | | | | | The test's output doesn't change, but this ensures this is actually hit with a different address space. llvm-svn: 191701
* Constant fold ptrtoint + compare with address spacesMatt Arsenault2013-09-301-1/+1
| | | | llvm-svn: 191699
* Use type helper functionsMatt Arsenault2013-09-271-2/+1
| | | | llvm-svn: 191574
* InstCombine: Remove unused argument. No functionality change.Benjamin Kramer2013-09-201-10/+4
| | | | llvm-svn: 191112
* [InstCombiner] Expose opportunities to merge subtract and comparison.Quentin Colombet2013-09-091-1/+46
| | | | | | | | | | | | | | | | | | | | | Several architectures use the same instruction to perform both a comparison and a subtract. The instruction selection framework does not allow to consider different basic blocks to expose such fusion opportunities. Therefore, these instructions are “merged” by CSE at MI IR level. To increase the likelihood of CSE to apply in such situation, we reorder the operands of the comparison, when they have the same complexity, so that they matches the order of the most frequent subtract. E.g., icmp A, B ... sub B, A <rdar://problem/14514580> llvm-svn: 190352
* Teach InstCombine about address spacesMatt Arsenault2013-08-211-4/+5
| | | | llvm-svn: 188926
* Revert non-test parts of r188507Matt Arsenault2013-08-191-1/+9
| | | | | | Re-add the inboundsless tests I didn't add originally llvm-svn: 188710
* Don't do FoldCmpLoadFromIndexedGlobal for non inbounds GEPsMatt Arsenault2013-08-151-9/+2
| | | | | | | This path wasn't tested before without a datalayout, so add some more tests and re-run with and without one. llvm-svn: 188507
* InstCombine: Fix typo in comment for visitICmpInstWithInstAndIntCstDavid Majnemer2013-07-091-2/+2
| | | | llvm-svn: 185916
* InstCombine: variations on 0xffffffff - x >= 4David Majnemer2013-07-091-0/+12
| | | | | | | | | | The following transforms are valid if -C is a power of 2: (icmp ugt (xor X, C), ~C) -> (icmp ult X, C) (icmp ult (xor X, C), -C) -> (icmp uge X, C) These are nice, they get rid of the xor. llvm-svn: 185915
* InstCombine: X & -C != -C -> X <= u ~CDavid Majnemer2013-07-091-0/+9
| | | | | | Tests were added in r185910 somehow. llvm-svn: 185912
* Commit r185909 was a misapplied patch, fix itDavid Majnemer2013-07-091-21/+13
| | | | llvm-svn: 185910
* InstCombine: add more transformsDavid Majnemer2013-07-091-0/+42
| | | | | | | | | C1-X <u C2 -> (X|(C2-1)) == C1 C1-X >u C2 -> (X|C2) == C1 X-C1 <u C2 -> (X & -C2) == C1 X-C1 >u C2 -> (X & ~C2) == C1 llvm-svn: 185909
* InstCombine: Fold X-C1 <u 2 -> (X & -2) == C1David Majnemer2013-07-081-0/+8
| | | | | | | | | | | Back in r179493 we determined that two transforms collided with each other. The fix back then was to reorder the transforms so that the preferred transform would give it a try and then we would try the secondary transform. However, it was noted that the best approach would canonicalize one transform into the other, removing the collision and allowing us to optimize IR given to us in that form. llvm-svn: 185808
* InstCombine: FoldGEPICmp shouldn't change sign of base pointer comparisonDavid Majnemer2013-06-291-2/+1
| | | | | | | | | | | | | | | | | | | | | | | | Changing the sign when comparing the base pointer would introduce all sorts of unexpected things like: %gep.i = getelementptr inbounds [1 x i8]* %a, i32 0, i32 0 %gep2.i = getelementptr inbounds [1 x i8]* %b, i32 0, i32 0 %cmp.i = icmp ult i8* %gep.i, %gep2.i %cmp.i1 = icmp ult [1 x i8]* %a, %b %cmp = icmp ne i1 %cmp.i, %cmp.i1 ret i1 %cmp into: %cmp.i = icmp slt [1 x i8]* %a, %b %cmp.i1 = icmp ult [1 x i8]* %a, %b %cmp = xor i1 %cmp.i, %cmp.i1 ret i1 %cmp By preserving the original sign, we now get: ret i1 false This fixes PR16483. llvm-svn: 185259
* InstCombine: Small whitespace cleanup in FoldGEPICmpDavid Majnemer2013-06-291-1/+1
| | | | llvm-svn: 185258
OpenPOWER on IntegriCloud