summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Transforms/InstCombine/InstCombineCompares.cpp
Commit message (Collapse)AuthorAgeFilesLines
* [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
* InstCombine: Optimize (1 << X) Pred CstP2 to X Pred Log2(CstP2)David Majnemer2013-06-281-2/+72
| | | | | | | | | | | | | | We may, after other optimizations, find ourselves with IR that looks like: %shl = shl i32 1, %y %cmp = icmp ult i32 %shl, 32 Instead, we should just compare the shift count: %cmp = icmp ult i32 %y, 5 llvm-svn: 185242
* Revert "Revert "[APFloat] Removed APFloat constructor which initialized to ↵Michael Gottesman2013-06-271-4/+4
| | | | | | | | | | | | | | | | | | | | either zero/NaN but allowed you to arbitrarily set the category of the float."" This reverts commit r185099. Looks like both the ppc-64 and mips bots are still failing after I reverted this change. Since: 1. The mips bot always performs a clean build, 2. The ppc64-bot failed again after a clean build (I asked the ppc-64 maintainers to clean the bot which they did... Thanks Will!), I think it is safe to assume that this change was not the cause of the failures that said builders were seeing. Thus I am recomitting. llvm-svn: 185111
* Revert "[APFloat] Removed APFloat constructor which initialized to either ↵Michael Gottesman2013-06-271-4/+4
| | | | | | | | | | | | zero/NaN but allowed you to arbitrarily set the category of the float." This reverts commit r185095. This is causing a FileCheck failure on the 3dnow intrinsics on at least the mips/ppc bots but not on the x86 bots. Reverting while I figure out what is going on. llvm-svn: 185099
* [APFloat] Removed APFloat constructor which initialized to either zero/NaN ↵Michael Gottesman2013-06-271-4/+4
| | | | | | | | | | | | | | but allowed you to arbitrarily set the category of the float. The category which an APFloat belongs to should be dependent on the actual value that the APFloat has, not be arbitrarily passed in by the user. This will prevent inconsistency bugs where the category and the actual value in APFloat differ. I also fixed up all of the references to this constructor (which were only in LLVM). llvm-svn: 185095
* Re-apply "Use IRBuilder instead of ConstantInt methods." with the fixed issues.Jakub Staszak2013-06-061-68/+55
| | | | llvm-svn: 183439
* Revert "Use IRBuilder instead of ConstantInt methods. It simplifies code a ↵Rafael Espindola2013-06-061-56/+70
| | | | | | | | little bit." This reverts commit 183328. It caused pr16244 and broke the bots. llvm-svn: 183422
* Use IRBuilder instead of ConstantInt methods. It simplifies code a little bit.Jakub Staszak2013-06-051-70/+56
| | | | llvm-svn: 183328
* Simplify (A & ~B) in icmp if A is a power of 2David Majnemer2013-04-121-0/+9
| | | | | | | | The transform will execute like so: (A & ~B) == 0 --> (A & B) != 0 (A & ~B) != 0 --> (A & B) == 0 llvm-svn: 179386
* Optimize icmp involving addition betterDavid Majnemer2013-04-111-0/+49
| | | | | | | | | | | | | | | | | | | | | | | | Allows LLVM to optimize sequences like the following: %add = add nsw i32 %x, 1 %cmp = icmp sgt i32 %add, %y into: %cmp = icmp sge i32 %x, %y as well as: %add1 = add nsw i32 %x, 20 %add2 = add nsw i32 %y, 57 %cmp = icmp sge i32 %add1, %add2 into: %add = add nsw i32 %y, 37 %cmp = icmp sle i32 %cmp, %x llvm-svn: 179316
* Tidy up a bit. No functional change.Jim Grosbach2013-04-051-1/+1
| | | | llvm-svn: 178915
* Address issues found by Duncan during post-commit review of r177856.Arnaud A. de Grandmaison2013-03-251-32/+19
| | | | llvm-svn: 177863
* InstCombine: simplify comparisons to zero of (shl %x, Cst) or (mul %x, Cst)Arnaud A. de Grandmaison2013-03-251-0/+83
| | | | | | | | This simplification happens at 2 places : - using the nsw attribute when the shl / mul is used by a sign test - when the shl / mul is compared for (in)equality to zero llvm-svn: 177856
* InstCombine: Improve the result bitvect type when folding (cmp pred (load ↵Arnaud A. de Grandmaison2013-03-221-11/+20
| | | | | | | | | | | | | | | (gep GV, i)) C) to a bit test. The original code used i32, and i64 if legal. This introduced unneeded casts when they aren't legal, or when the index variable i has another type. In order of preference: try to use i's type; use the smallest fitting legal type (using an added DataLayout method); default to i32. A testcase checks that this works when the index gep operand is i16. Patch by : Ahmed Bougacha <ahmed.bougacha@gmail.com> Reviewed by : Duncan llvm-svn: 177712
* Fix a performance regression when combining to smaller types in icmp (shl ↵Arnaud A. de Grandmaison2013-03-131-3/+4
| | | | | | | | %v, C1), C2 : Only combine when the shl is only used by the icmp llvm-svn: 176950
* Fix refactoring mistake in "Teach InstCombine to work with smaller legal ↵Arnaud A. de Grandmaison2013-02-151-1/+1
| | | | | | types..." llvm-svn: 175273
* Teach InstCombine to work with smaller legal types in icmp (shl %v, C1), C2Arnaud A. de Grandmaison2013-02-151-0/+19
| | | | | | | | | It enables to work with a smaller constant, which is target friendly for those which can compare to immediates. It also avoids inserting a shift in favor of a trunc, which can be free on some targets. This used to work until LLVM-3.1, but regressed with the 3.2 release. llvm-svn: 175270
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-2/+2
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Transform (x&C)>V into (x&C)!=0 where possiblePaul Redmond2012-12-191-0/+10
| | | | | | | | | | | | When the least bit of C is greater than V, (x&C) must be greater than V if it is not zero, so the comparison can be simplified. Although this was suggested in Target/X86/README.txt, it benefits any architecture with a directly testable form of AND. Patch by Kevin Schoedel llvm-svn: 170576
OpenPOWER on IntegriCloud