summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/InstructionSimplify.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* Fix comment.Nick Lewycky2011-01-291-1/+1
| | | | llvm-svn: 124544
* Move InstCombine's knowledge of fdiv to SimplifyInstruction().Frits van Bommel2011-01-291-2/+24
| | | | llvm-svn: 124534
* This dyn_cast should be a cast. Pointed out by Frits van Bommel.Duncan Sands2011-01-281-1/+1
| | | | llvm-svn: 124497
* 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). llvm-svn: 124496
* 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. llvm-svn: 124487
* 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. llvm-svn: 124183
* 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. llvm-svn: 123911
* 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. llvm-svn: 123755
* 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). llvm-svn: 123754
* 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. llvm-svn: 123442
* 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. llvm-svn: 123441
* 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. llvm-svn: 123417
* 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. llvm-svn: 123373
* 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. llvm-svn: 123372
* 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. llvm-svn: 122661
* 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. llvm-svn: 122654
* Cast away "comparison between signed and unsigned integer" warnings.Benjamin Kramer2010-12-281-3/+6
| | | | llvm-svn: 122598
* 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. llvm-svn: 122414
* Add some statistics, good for understanding how much more powerfulDuncan Sands2010-12-221-14/+48
| | | | | | instcombine is compared to instsimplify. llvm-svn: 122397
* 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. llvm-svn: 122332
* Fix inverted condition noticed by Frits van Bommel.Duncan Sands2010-12-211-3/+3
| | | | llvm-svn: 122331
* Pull a few more simplifications out of instcombine (there are stillDuncan Sands2010-12-211-5/+86
| | | | | | plenty left though!), in particular for multiplication. llvm-svn: 122330
* Teach InstructionSimplify about distributive laws. These transforms fireDuncan Sands2010-12-211-11/+159
| | | | | | | quite often, but don't make much difference in practice presumably because instcombine also knows them and more. llvm-svn: 122328
* Move checking of the recursion limit into the various Thread methods.Duncan Sands2010-12-211-20/+36
| | | | | | No functionality change. llvm-svn: 122327
* Add generic simplification of associative operations, generalizingDuncan Sands2010-12-211-28/+118
| | | | | | | | | | | | 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. llvm-svn: 122326
* Have SimplifyBinOp dispatch Xor, Add and Sub to the corresponding methodsDuncan Sands2010-12-201-5/+27
| | | | | | | (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. llvm-svn: 122245
* Move Sub simplifications and additional Add simplifications out ofDuncan Sands2010-12-151-10/+67
| | | | | | instcombine and into InstructionSimplify. llvm-svn: 121861
* If we detect that the instruction we are simplifying is unreachable, arrange forDuncan Sands2010-12-151-3/+3
| | | | | | | 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. llvm-svn: 121860
* Add some dead stores to pacify my least favorite GCC warning: may beChandler Carruth2010-11-291-3/+3
| | | | | | | | | | | uninitialized. The warning is terrible, has incorrect source locations, and has a huge false positive rate such as *all* of these. If anyone has a better solution, please let me know. Alternatively, I'll happily add -Wno-uninitialized to the -Werror build mode. Maybe I can even do it *only* when building with GCC instead of Clang. llvm-svn: 120281
* Expand a little on the description of what InstructionSimplify does.Duncan Sands2010-11-231-2/+4
| | | | llvm-svn: 120016
* If a GEP index simply advances by multiples of a type of zero size,Duncan Sands2010-11-221-1/+1
| | | | | | then replace the index with zero. llvm-svn: 119974
* Move the "gep undef" -> "undef" transform from instcombine toDuncan Sands2010-11-221-4/+11
| | | | | | InstructionSimplify. llvm-svn: 119970
* Add a rather pointless InstructionSimplify transform, inspired by recent ↵Duncan Sands2010-11-211-2/+10
| | | | | | | | | | constant folding improvements: if P points to a type of size zero, turn "gep P, N" into "P". More generally, if a gep index type has size zero, instcombine could replace the index with zero, but that is not done here. llvm-svn: 119942
* Remove threading of Xor over selects and phis, with an explanationDuncan Sands2010-11-191-13/+18
| | | | | | of why such threading is pointless. llvm-svn: 119798
* Move some those Xor simplifications which don't require creating newDuncan Sands2010-11-171-30/+78
| | | | | | | | instructions out of InstCombine and into InstructionSimplify. While there, introduce an m_AllOnes pattern to simplify matching with integers and vectors with all bits equal to one. llvm-svn: 119536
* Previously SimplifyInstruction could report that an instructionDuncan Sands2010-11-171-15/+31
| | | | | | | | simplified to itself (this can only happen in unreachable blocks). Change it to return null instead. Hopefully this will fix some buildbot failures. llvm-svn: 119490
* Fix a layering violation: hasConstantValue, which is part of the PHINodeDuncan Sands2010-11-171-3/+37
| | | | | | | | | | | | | | class, uses DominatorTree which is an analysis. This change moves all of the tricky hasConstantValue logic to SimplifyInstruction, and replaces it with a very simple literal implementation. I already taught users of hasConstantValue that need tricky stuff to use SimplifyInstruction instead. I didn't update InlineFunction because the IR looks like it might be in a funky state at the point it calls hasConstantValue, which makes calling SimplifyInstruction dangerous since it can in theory do a lot of tricky reasoning. This may be a pessimization, for example in the case where all phi node operands are either undef or a fixed constant. llvm-svn: 119459
* In which I discover the existence of loops. Threading an operationDuncan Sands2010-11-161-60/+102
| | | | | | | | | | | over a phi node by applying it to each operand may be wrong if the operation and the phi node are mutually interdependent (the testcase has a simple example of this). So only do this transform if it would be correct to perform the operation in each predecessor of the block containing the phi, i.e. if the other operands all dominate the phi. This should fix the FFMPEG snow.c regression reported by İsmail Dönmez. llvm-svn: 119347
* Teach InstructionSimplify the trick of skipping incoming phiDuncan Sands2010-11-151-4/+9
| | | | | | values that are equal to the phi itself. llvm-svn: 119161
* If dom tree information is available, make it possible to passDuncan Sands2010-11-141-5/+7
| | | | | | it to get better phi node simplification. llvm-svn: 119055
* Teach InstructionSimplify about phi nodes. I chose to have it simplyDuncan Sands2010-11-141-0/+2
| | | | | | | | | | offload the work to hasConstantValue rather than do something more complicated (such handling mutually recursive phis) because (1) it is not clear it is worth it; and (2) if it is worth it, maybe such logic would be better placed in hasConstantValue. Adjust some GVN tests which are now cleaned up much further (eg: all phi nodes are removed). llvm-svn: 119043
* Strip trailing whitespace.Duncan Sands2010-11-141-50/+49
| | | | llvm-svn: 119038
* Reduce the maximum recursion depth, 5 seems pointlessly too much.Duncan Sands2010-11-101-1/+1
| | | | | | Probably it should just be 1, but compromise with 3. llvm-svn: 118718
* Teach InstructionSimplify how to look through PHI nodes. Since PHIDuncan Sands2010-11-101-32/+163
| | | | | | | | | nodes can be used in loops, this could result in infinite looping if there is no recursion limit, so add such a limit. It is also used for the SelectInst case because in theory there could be an infinite loop there too if the basic block is unreachable. llvm-svn: 118694
* Simplify binary operations where one operand is a select instruction.Duncan Sands2010-11-101-28/+113
| | | | | | | | | | | | | | | | | The simplifications performed here never create new instructions, they only return existing instructions (or a constant), and so are always a win. In theory they should transform (for example) %z = and i32 %x, %y %s = select i1 %cond, i32 %y, i32 %z %r = and i32 %x, %s into %r = and i32 %x, y but in practice they get into a fight with instcombine, and lose. Unfortunately instcombine does a poor job in this case. Nonetheless I'm committing this transform to make it easier to discuss what to do to make peace with instcombine. llvm-svn: 118679
* Factorize code, no functionality change.Duncan Sands2010-11-091-34/+31
| | | | llvm-svn: 118516
* Add simplification of floating point comparisons with the resultDuncan Sands2010-11-071-0/+20
| | | | | | | of a select instruction, the same as already exists for integer comparisons. llvm-svn: 118379
* Fix a README item: when doing a comparison with the resultDuncan Sands2010-11-071-2/+21
| | | | | | | | of a select instruction, see if doing the compare with the true and false values of the select gives the same result. If so, that can be used as the value of the comparison. llvm-svn: 118378
* Revert r114097, adding back in the assertion against replacing an ↵Owen Anderson2010-09-161-24/+11
| | | | | | | | | Instruction by itself. Now that CorrelatedValuePropagation is more careful not to call SimplifyInstructionsInBlock() on an unreachable block, the issue has been fixed at a higher level. Add a big warning to SimplifyInstructionsInBlock() to hopefully prevent this in the future. llvm-svn: 114117
* Fix PR8161, in which an unreachable loop causes recursive instruction ↵Owen Anderson2010-09-161-11/+24
| | | | | | | | simplification to try to replace an instruction with itself. Add a predicate to the simplifier to prevent this case. llvm-svn: 114097
OpenPOWER on IntegriCloud