aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis/InstructionSimplify.cpp
AgeCommit message (Collapse)Author
2011-03-09Fix two cases I forgot to update when doing a mental "getSwappedPredicate".Nick Lewycky
Thanks Duncan Sands! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127323 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-09Add another micro-optimization. Apologies for the lack of refactoring, but INick Lewycky
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
2011-03-05Thread comparisons over udiv/sdiv/ashr/lshr exact and lshr nuw/nsw wheneverNick Lewycky
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
2011-03-04Revert broken srem logic from r126991.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@127021 91177308-0d34-0410-b5e6-96231b3b80d8
2011-03-04Fold "icmp pred (srem X, Y), Y" like we do for urem. Handle signed comparisonsNick Lewycky
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
2011-03-04Teach instruction simplify to use constant ranges to solve problems of the formNick Lewycky
"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
2011-03-01Optimize "icmp pred (urem X, Y), Y" --> true/false depending on pred. There'sNick Lewycky
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
2011-02-20Move "A | ~(A & ?) -> -1" from InstCombine to InstructionSimplify.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@126082 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-13Remove pointless blank line.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125463 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-13Teach instsimplify that X+Y>=X+Z is the same as Y>=Z if neither side overflows,Duncan Sands
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
2011-02-09Formatting and comment tweaks.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@125200 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-09Teach instsimplify some tricks about exact/nuw/nsw shifts.Chris Lattner
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
2011-02-09Rework InstrTypes.h so to reduce the repetition around the NSW/NUW/ExactChris Lattner
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
2011-02-07Add an m_Div pattern for matching either a udiv or an sdiv and use itDuncan Sands
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
2011-02-06teach instsimplify to transform (X / Y) * Y to XChris Lattner
when the div is an exact udiv. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124994 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-05Fix another warning.Anders Carlsson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124961 91177308-0d34-0410-b5e6-96231b3b80d8
2011-02-03Improve threading of comparisons over select instructions (spotted by myDuncan Sands
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
2011-02-02Reenable the transform "(X*Y)/Y->X" when the multiplication is known not toDuncan Sands
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
2011-02-01Add a m_Undef pattern for convenience. This is so that code that usesDuncan Sands
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
2011-02-01Have m_One also match constant vectors for which every element is 1.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124655 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-30Commit 124487 broke 254.gap. See if disabling the part that might be triggeredDuncan Sands
by PR9088 fixes things. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124561 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-30Transform (X/Y)*Y into X if the division is exact. Instcombine already ↵Duncan Sands
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
2011-01-29Fix comment.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124544 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-29Move InstCombine's knowledge of fdiv to SimplifyInstruction().Frits van Bommel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124534 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-28This dyn_cast should be a cast. Pointed out by Frits van Bommel.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124497 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-28Thread divisions over selects and phis. This doesn't fire much and has ↵Duncan Sands
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
2011-01-28My auto-simplifier noticed that ((X/Y)*Y)/Y occurs several times in SPECDuncan Sands
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
2011-01-25According to my auto-simplifier the most common missed simplifications inDuncan Sands
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
2011-01-20At -O123 the early-cse pass is run before instcombine has run. According to myDuncan Sands
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
2011-01-18For completeness, generalize the (X + Y) - Y -> X transform and add X - (X + ↵Duncan Sands
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
2011-01-18Simplify (X<<1)-X into X. According to my auto-simplier this is the most ↵Duncan Sands
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
2011-01-14Turn X-(X-Y) into Y. According to my auto-simplifier this is the most commonDuncan Sands
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
2011-01-14Factorize common code out of the InstructionSimplify shift logic. Add inDuncan Sands
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
2011-01-14Move some shift transforms out of instcombine and into InstructionSimplify.Duncan Sands
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
2011-01-13Remove some wrong code which fortunately was never executed (as explained inDuncan Sands
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
2011-01-13The most common simplification missed by instsimplify in unoptimized bitcodeDuncan Sands
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
2011-01-01Revert commit 122654 at the request of Chris, who reckons that instsimplifyDuncan Sands
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
2011-01-01Fix a README item by having InstructionSimplify do a mild form of valueDuncan Sands
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
2010-12-28Cast away "comparison between signed and unsigned integer" warnings.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122598 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-22When determining whether the new instruction was already present inDuncan Sands
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
2010-12-22Add some statistics, good for understanding how much more powerfulDuncan Sands
instcombine is compared to instsimplify. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122397 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21While I don't think any later transforms can fire, it seems cleaner toDuncan Sands
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
2010-12-21Fix inverted condition noticed by Frits van Bommel.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122331 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21Pull a few more simplifications out of instcombine (there are stillDuncan Sands
plenty left though!), in particular for multiplication. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122330 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21Teach InstructionSimplify about distributive laws. These transforms fireDuncan Sands
quite often, but don't make much difference in practice presumably because instcombine also knows them and more. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122328 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21Move checking of the recursion limit into the various Thread methods.Duncan Sands
No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122327 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-21Add generic simplification of associative operations, generalizingDuncan Sands
a couple of existing transforms. This fires surprisingly often, for example when compiling gcc "(X+(-1))+1->X" fires quite a lot as well as various "and" simplifications (usually with a phi node operand). Most of the time this doesn't make a real difference since the same thing would have been done elsewhere anyway, eg: by instcombine, but there are a few places where this results in simplifications that we were not doing before. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122326 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-20Have SimplifyBinOp dispatch Xor, Add and Sub to the corresponding methodsDuncan Sands
(they had just been forgotten before). Adding Xor causes "main" in the existing testcase 2010-11-01-lshr-mask.ll to be hugely more simplified. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122245 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-15Move Sub simplifications and additional Add simplifications out ofDuncan Sands
instcombine and into InstructionSimplify. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121861 91177308-0d34-0410-b5e6-96231b3b80d8
2010-12-15If we detect that the instruction we are simplifying is unreachable, arrange forDuncan Sands
it to be replaced by undef rather than not replaced at all, the idea being that this may reduce the amount of work done by whoever called InstructionSimplify. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@121860 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-04-30 11:54:54 +0000