aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis/InstructionSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Improve constant folding of undef for cmp and select operators.Dan Gohman2011-07-011-4/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@134223 91177308-0d34-0410-b5e6-96231b3b80d8
* The comparision "max(x,y)==x" is equivalent to "x>=y". Since the max isDuncan Sands2011-05-071-10/+56
| | | | | | | | often expressed as "x >= y ? x : y", there is a good chance we can extract the existing "x >= y" from it and use that as a replacement for "max(x,y)==x". git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@131049 91177308-0d34-0410-b5e6-96231b3b80d8
* PR9838: Fix transform introduced in r127064 to not trigger when only one ↵Eli Friedman2011-05-051-1/+1
| | | | | | side of the icmp is an exact shift. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130954 91177308-0d34-0410-b5e6-96231b3b80d8
* Add variations on: max(x,y) >= min(x,z) folds to true. This isn't that common,Duncan Sands2011-05-041-2/+46
| | | | | | | | | but according to my super-optimizer there are only two missed simplifications of -instsimplify kind when compiling bzip2, and this is one of them. It amuses me to have bzip2 be perfectly optimized as far as instsimplify goes! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130840 91177308-0d34-0410-b5e6-96231b3b80d8
* Implement some basic simplifications involving min/max, for exampleDuncan Sands2011-05-031-0/+118
| | | | | | | | | max(a,b) >= a -> true. According to my super-optimizer, these are by far the most common simplifications (of the -instsimplify kind) that occur in the testsuite and aren't caught by -std-compile-opts. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130780 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix PR9579: when simplifying a compare to "true" or "false", and it wasDuncan Sands2011-05-021-18/+22
| | | | | | | a vector compare, generate a vector result rather than i1 (and crashing). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130706 91177308-0d34-0410-b5e6-96231b3b80d8
* Move some rem transforms out of instcombine and into instsimplify.Duncan Sands2011-05-021-0/+117
| | | | | | | | This automagically provides a transform noticed by my super-optimizer as occurring quite often: "rem x, (select cond, x, 1)" -> 0. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@130694 91177308-0d34-0410-b5e6-96231b3b80d8
* Don't include Operator.h from InstrTypes.h.Jay Foad2011-04-111-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@129271 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix two cases I forgot to update when doing a mental "getSwappedPredicate".Nick Lewycky2011-03-091-2/+2
| | | | | | | Thanks Duncan Sands! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127323 91177308-0d34-0410-b5e6-96231b3b80d8
* Add another micro-optimization. Apologies for the lack of refactoring, but INick Lewycky2011-03-091-2/+28
| | | | | | | | | | gave up when I realized I couldn't come up with a good name for what the refactored function would be, to describe what it does. This is PR9343 test12, which is test3 with arguments reordered. Whoops! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127318 91177308-0d34-0410-b5e6-96231b3b80d8
* Thread comparisons over udiv/sdiv/ashr/lshr exact and lshr nuw/nsw wheneverNick Lewycky2011-03-051-1/+33
| | | | | | | | | | possible. This goes into instcombine and instsimplify because instsimplify doesn't need to check hasOneUse since it returns (almost exclusively) constants. This fixes PR9343 #4 #5 and #8! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127064 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert broken srem logic from r126991.Nick Lewycky2011-03-041-15/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127021 91177308-0d34-0410-b5e6-96231b3b80d8
* Fold "icmp pred (srem X, Y), Y" like we do for urem. Handle signed comparisonsNick Lewycky2011-03-041-1/+30
| | | | | | | | in the urem case, though not the other way around. This is enough to get #3 from PR9343! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126991 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach instruction simplify to use constant ranges to solve problems of the formNick Lewycky2011-03-041-37/+61
| | | | | | | | | | "icmp pred %X, CI" and a number of examples where "%X = binop %Y, CI2". Some of these cases (div and rem) used to make it through opt -O2, but the others are probably now making code elsewhere redundant (probably instcombine). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126988 91177308-0d34-0410-b5e6-96231b3b80d8
* Optimize "icmp pred (urem X, Y), Y" --> true/false depending on pred. There'sNick Lewycky2011-03-011-0/+18
| | | | | | | | more work to do here, "icmp ult (urem X, 10), 11" doesn't optimize away yet. Fixes example 3 from PR9343! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126741 91177308-0d34-0410-b5e6-96231b3b80d8
* Move "A | ~(A & ?) -> -1" from InstCombine to InstructionSimplify.Benjamin Kramer2011-02-201-0/+10
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126082 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove pointless blank line.Duncan Sands2011-02-131-1/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125463 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach instsimplify that X+Y>=X+Z is the same as Y>=Z if neither side overflows,Duncan Sands2011-02-131-2/+49
| | | | | | | | | plus some variations of this. According to my auto-simplifier this occurs a lot but usually in combination with max/min idioms. Because max/min aren't handled yet this unfortunately doesn't have much effect in the testsuite. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125462 91177308-0d34-0410-b5e6-96231b3b80d8
* Formatting and comment tweaks.Duncan Sands2011-02-091-5/+5
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125200 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach instsimplify some tricks about exact/nuw/nsw shifts.Chris Lattner2011-02-091-39/+69
| | | | | | | | improve interfaces to instsimplify to take this info. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125196 91177308-0d34-0410-b5e6-96231b3b80d8
* Rework InstrTypes.h so to reduce the repetition around the NSW/NUW/ExactChris Lattner2011-02-091-2/+2
| | | | | | | | | | | | | | | | | | | | versions of creation functions. Eventually, the "insertion point" versions of these should just be removed, we do have IRBuilder afterall. Do a massive rewrite of much of pattern match. It is now shorter and less redundant and has several other widgets I will be using in other patches. Among other changes, m_Div is renamed to m_IDiv (since it only matches integer divides) and m_Shift is gone (it used to match all binops!!) and we now have m_LogicalShift for the one client to use. Enhance IRBuilder to have "isExact" arguments to things like CreateUDiv and reduce redundancy within IRbuilder by having these methods chain to each other more instead of duplicating code. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125194 91177308-0d34-0410-b5e6-96231b3b80d8
* Add an m_Div pattern for matching either a udiv or an sdiv and use itDuncan Sands2011-02-071-4/+2
| | | | | | | to simplify the "(X/Y)*Y->X when the division is exact" transform. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125004 91177308-0d34-0410-b5e6-96231b3b80d8
* teach instsimplify to transform (X / Y) * Y to XChris Lattner2011-02-061-3/+5
| | | | | | | when the div is an exact udiv. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124994 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix another warning.Anders Carlsson2011-02-051-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124961 91177308-0d34-0410-b5e6-96231b3b80d8
* Improve threading of comparisons over select instructions (spotted by myDuncan Sands2011-02-031-3/+25
| | | | | | | | | | | auto-simplifier). This has a big impact on Ada code, but not much else. Unfortunately the impact is mostly negative! This is due to PR9004 (aka SCCP failing to resolve conditional branch conditions in the destination blocks of the branch), in which simple correlated expressions are not resolved but complicated ones are, so simplifying has a bad effect! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124788 91177308-0d34-0410-b5e6-96231b3b80d8
* Reenable the transform "(X*Y)/Y->X" when the multiplication is known not toDuncan Sands2011-02-021-5/+5
| | | | | | | | | overflow (nsw flag), which was disabled because it breaks 254.gap. I have informed the GAP authors of the mistake in their code, and arranged for the testsuite to use -fwrapv when compiling this benchmark. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124746 91177308-0d34-0410-b5e6-96231b3b80d8
* Add a m_Undef pattern for convenience. This is so that code that usesDuncan Sands2011-02-011-16/+16
| | | | | | | | pattern matching can also pattern match undef, creating a more uniform style. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124657 91177308-0d34-0410-b5e6-96231b3b80d8
* Have m_One also match constant vectors for which every element is 1.Duncan Sands2011-02-011-6/+0
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124655 91177308-0d34-0410-b5e6-96231b3b80d8
* Commit 124487 broke 254.gap. See if disabling the part that might be triggeredDuncan Sands2011-01-301-5/+5
| | | | | | | by PR9088 fixes things. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124561 91177308-0d34-0410-b5e6-96231b3b80d8
* Transform (X/Y)*Y into X if the division is exact. Instcombine already ↵Duncan Sands2011-01-301-0/+9
| | | | | | | | | | | | | knows how to do this and more, but would only do it if X/Y had only one use. Spotted as the most common missed simplification in SPEC by my auto-simplifier, now that it knows about nuw/nsw/exact flags. This removes a bunch of multiplications from 447.dealII and 483.xalancbmk. It also removes a lot from tramp3d-v4, which results in much more inlining. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124560 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix comment.Nick Lewycky2011-01-291-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124544 91177308-0d34-0410-b5e6-96231b3b80d8
* Move InstCombine's knowledge of fdiv to SimplifyInstruction().Frits van Bommel2011-01-291-2/+24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124534 91177308-0d34-0410-b5e6-96231b3b80d8
* This dyn_cast should be a cast. Pointed out by Frits van Bommel.Duncan Sands2011-01-281-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124497 91177308-0d34-0410-b5e6-96231b3b80d8
* Thread divisions over selects and phis. This doesn't fire much and has ↵Duncan Sands2011-01-281-9/+19
| | | | | | | | | basically zero effect on the testsuite (it improves two Ada testcases). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124496 91177308-0d34-0410-b5e6-96231b3b80d8
* My auto-simplifier noticed that ((X/Y)*Y)/Y occurs several times in SPECDuncan Sands2011-01-281-0/+107
| | | | | | | | | | | | | | | | | | benchmarks, and that it can be simplified to X/Y. (In general you can only simplify (Z*Y)/Y to Z if the multiplication did not overflow; if Z has the form "X/Y" then this is the case). This patch implements that transform and moves some Div logic out of instcombine and into InstructionSimplify. Unfortunately instcombine gets in the way somewhat, since it likes to change (X/Y)*Y into X-(X rem Y), so I had to teach instcombine about this too. Finally, thanks to the NSW/NUW flags, sometimes we know directly that "Z*Y" does not overflow, because the flag says so, so I added that logic too. This eliminates a bunch of divisions and subtractions in 447.dealII, and has good effects on some other benchmarks too. It seems to have quite an effect on tramp3d-v4 but it's hard to say if it's good or bad because inlining decisions changed, resulting in massive changes all over. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124487 91177308-0d34-0410-b5e6-96231b3b80d8
* According to my auto-simplifier the most common missed simplifications inDuncan Sands2011-01-251-12/+64
| | | | | | | | | | | | optimized code are: (non-negative number)+(power-of-two) != 0 -> true and (x | 1) != 0 -> true Instcombine knows about the second one of course, but only does it if X|1 has only one use. These fire thousands of times in the testsuite. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124183 91177308-0d34-0410-b5e6-96231b3b80d8
* At -O123 the early-cse pass is run before instcombine has run. According to myDuncan Sands2011-01-201-0/+162
| | | | | | | | | | | | | | | | | auto-simplier the transform most missed by early-cse is (zext X) != 0 -> X != 0. This patch adds this transform and some related logic to InstructionSimplify and removes some of the logic from instcombine (unfortunately not all because there are several situations in which instcombine can improve things by making new instructions, whereas instsimplify is not allowed to do this). At -O2 this often results in more than 15% more simplifications by early-cse, and results in hundreds of lines of bitcode being eliminated from the testsuite. I did see some small negative effects in the testsuite, for example a few additional instructions in three programs. One program, 483.xalancbmk, got an additional 35 instructions, which seems to be due to a function getting an additional instruction and then being inlined all over the place. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123911 91177308-0d34-0410-b5e6-96231b3b80d8
* For completeness, generalize the (X + Y) - Y -> X transform and add X - (X + ↵Duncan Sands2011-01-181-15/+57
| | | | | | | | | | | 1) -> -1. These were not recommended by my auto-simplifier since they don't fire often enough. However they do fire from time to time, for example they remove one subtraction from the final bitcode for 483.xalancbmk. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123755 91177308-0d34-0410-b5e6-96231b3b80d8
* Simplify (X<<1)-X into X. According to my auto-simplier this is the most ↵Duncan Sands2011-01-181-0/+6
| | | | | | | | | | | | | | common missed simplification in fully optimized code. It occurs sporadically in the testsuite, and many times in 403.gcc: the final bitcode has 131 fewer subtractions after this change. The reason that the multiplies are not eliminated is the same reason that instcombine did not catch this: they are used by other instructions (instcombine catches this with a more general transform which in general is only profitable if the operands have only one use). git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123754 91177308-0d34-0410-b5e6-96231b3b80d8
* Turn X-(X-Y) into Y. According to my auto-simplifier this is the most commonDuncan Sands2011-01-141-1/+15
| | | | | | | | | | simplification present in fully optimized code (I think instcombine fails to transform some of these when "X-Y" has more than one use). Fires here and there all over the test-suite, for example it eliminates 8 subtractions in the final IR for 445.gobmk, 2 subs in 447.dealII, 2 in paq8p etc. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123442 91177308-0d34-0410-b5e6-96231b3b80d8
* Factorize common code out of the InstructionSimplify shift logic. Add inDuncan Sands2011-01-141-62/+38
| | | | | | | | | | | | threading of shifts over selects and phis while there. This fires here and there in the testsuite, to not much effect. For example when compiling spirit it fires 5 times, during early-cse, resulting in 6 more cse simplifications, and 3 more terminators being folded by jump threading, but the final bitcode doesn't change in any interesting way: other optimizations would have caught the opportunity anyway, only later. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123441 91177308-0d34-0410-b5e6-96231b3b80d8
* Move some shift transforms out of instcombine and into InstructionSimplify.Duncan Sands2011-01-141-0/+142
| | | | | | | | | | | | | While there, I noticed that the transform "undef >>a X -> undef" was wrong. For example if X is 2 then the top two bits must be equal, so the result can not be anything. I fixed this in the constant folder as well. Also, I made the transform for "X << undef" stronger: it now folds to undef always, even though X might be zero. This is in accordance with the LangRef, but I must admit that it is fairly aggressive. Also, I added "i32 X << 32 -> undef" following the LangRef and the constant folder, likewise fairly aggressive. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123417 91177308-0d34-0410-b5e6-96231b3b80d8
* Remove some wrong code which fortunately was never executed (as explained inDuncan Sands2011-01-131-6/+9
| | | | | | | the comment I added): an extern weak global may have a null address. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123373 91177308-0d34-0410-b5e6-96231b3b80d8
* The most common simplification missed by instsimplify in unoptimized bitcodeDuncan Sands2011-01-131-19/+70
| | | | | | | | | is "X != 0 -> X" when X is a boolean. This occurs a lot because of the way llvm-gcc converts gcc's conditional expressions. Add this, and a few other similar transforms for completeness. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123372 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert commit 122654 at the request of Chris, who reckons that instsimplifyDuncan Sands2011-01-011-124/+52
| | | | | | | is the wrong hammer for this nail, and is probably right. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122661 91177308-0d34-0410-b5e6-96231b3b80d8
* Fix a README item by having InstructionSimplify do a mild form of valueDuncan Sands2011-01-011-52/+124
| | | | | | | | | | | | numbering, in which it considers (for example) "%a = add i32 %x, %y" and "%b = add i32 %x, %y" to be equal because the operands are equal and the result of the instructions only depends on the values of the operands. This has almost no effect (it removes 4 instructions from gcc-as-one-file), and perhaps slows down compilation: I measured a 0.4% slowdown on the large gcc-as-one-file testcase, but it wasn't statistically significant. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122654 91177308-0d34-0410-b5e6-96231b3b80d8
* Cast away "comparison between signed and unsigned integer" warnings.Benjamin Kramer2010-12-281-3/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122598 91177308-0d34-0410-b5e6-96231b3b80d8
* When determining whether the new instruction was already present inDuncan Sands2010-12-221-6/+8
| | | | | | | | | the original instruction, half the cases were missed (making it not wrong but suboptimal). Also correct a typo (A <-> B) in the second chunk. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122414 91177308-0d34-0410-b5e6-96231b3b80d8
* Add some statistics, good for understanding how much more powerfulDuncan Sands2010-12-221-14/+48
| | | | | | | instcombine is compared to instsimplify. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122397 91177308-0d34-0410-b5e6-96231b3b80d8
* While I don't think any later transforms can fire, it seems cleaner toDuncan Sands2010-12-211-3/+6
| | | | | | | | not assume this (for example in case more transforms get added below it). Suggested by Frits van Bommel. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122332 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-02-13 05:12:24 +0000