aboutsummaryrefslogtreecommitdiffstats
path: root/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
* fix PR8983, a broken assertion.Chris Lattner2011-01-161-1/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123562 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach LazyValueInfo that allocas aren't NULL. Over all of llvm-test, this savesNick Lewycky2011-01-151-5/+27
| | | | | | | | | | | | half a million non-local queries, each of which would otherwise have triggered a linear scan over a basic block. Also fix a fixme for memory intrinsics which dereference pointers. With this, we prove that a pointer is non-null because it was dereferenced by an intrinsic 112 times in llvm-test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123533 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
* Add single entry / single exit accessors.Tobias Grosser2011-01-131-23/+32
| | | | | | | | | | | Add methods for accessing the (single) entry / exit edge of a region. If no such edge exists, null is returned. Both accessors return the start block of the corresponding edge. The edge can finally be formed by utilizing Region::getEntry() or Region::getExit(); Contributed by: Andreas Simbuerger <simbuerg@fim.uni-passau.de> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123410 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
* some comment improvements.Chris Lattner2011-01-111-3/+4
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123243 91177308-0d34-0410-b5e6-96231b3b80d8
* Temporarily revert 123133, it's causing some regressions and I'm tryingEric Christopher2011-01-111-8/+4
| | | | | | | to get a testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123225 91177308-0d34-0410-b5e6-96231b3b80d8
* the GEP faq says that only inbounds geps are guaranteed to not overflow.Chris Lattner2011-01-111-2/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123218 91177308-0d34-0410-b5e6-96231b3b80d8
* Revert r123207: "Turn on memdep's verifyRemoved() in an attempt to smoke out ↵Jakob Stoklund Olesen2011-01-111-3/+1
| | | | | | | | the cause of our gcc bootstrap miscompare." It didn't. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123215 91177308-0d34-0410-b5e6-96231b3b80d8
* Turn on memdep's verifyRemoved() in an attempt to smoke out the cause of our ↵Jakob Stoklund Olesen2011-01-111-1/+3
| | | | | | gcc bootstrap miscompare. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123207 91177308-0d34-0410-b5e6-96231b3b80d8
* Teach constant folding to perform conversions from constant floatingChandler Carruth2011-01-111-0/+56
| | | | | | | | point values to their integer representation through the SSE intrinsic calls. This is the last part of a README.txt entry for which I have real world examples. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123206 91177308-0d34-0410-b5e6-96231b3b80d8
* Cleanup some of the constant folding code to consistently test intrinsicChandler Carruth2011-01-101-16/+18
| | | | | | | IDs when available rather than using a mixture of IDs and textual name comparisons. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123165 91177308-0d34-0410-b5e6-96231b3b80d8
* add a fixme: ir isn't expressive enough.Chris Lattner2011-01-091-0/+1
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123139 91177308-0d34-0410-b5e6-96231b3b80d8
* Step #4 in improving trip count analysis: HowFarToZero can analyzeChris Lattner2011-01-091-2/+11
| | | | | | | | NUW AddRec's much more aggressively. We now get a trip count for @test2 in nsw.ll git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123138 91177308-0d34-0410-b5e6-96231b3b80d8
* rearrange some code, no functionality change.Chris Lattner2011-01-091-41/+45
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123136 91177308-0d34-0410-b5e6-96231b3b80d8
* Step #3 to improving trip count analysis: If we foldChris Lattner2011-01-091-4/+8
| | | | | | | | | | a + {b,+,stride} into {a+b,+,stride} (because a is LIV), then the resultant AddRec is NUW/NSW if the client says it is. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123133 91177308-0d34-0410-b5e6-96231b3b80d8
* Step #2 to improve trip count analysis for loops like this:Chris Lattner2011-01-091-6/+105
| | | | | | | | | | | | | | | | | | | | | void f(int* begin, int* end) { std::fill(begin, end, 0); } which turns into a != exit expression where one pointer is strided and (thanks to step #1) known to not overflow, and the other is loop invariant. The observation here is that, though the IV is strided by 4 in this case, that the IV *has* to become equal to the end value. It cannot "miss" the end value by stepping over it, because if it did, the strided IV expression would eventually wrap around. Handle this by turning A != B into "A-B != 0" where the A-B part is known to be NUW. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123131 91177308-0d34-0410-b5e6-96231b3b80d8
* teach SCEV analysis of PHI nodes that PHI recurences formedChris Lattner2011-01-091-0/+5
| | | | | | | | with GEP instructions are always NUW, because PHIs cannot wrap the end of the address space. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123105 91177308-0d34-0410-b5e6-96231b3b80d8
* reduce indentation. Print <nuw> and <nsw> when dumping SCEV AddRec'sChris Lattner2011-01-091-49/+54
| | | | | | | that have the bit set. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123104 91177308-0d34-0410-b5e6-96231b3b80d8
* use isNullValue() to simplify code, add an assert.Chris Lattner2011-01-061-5/+6
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122977 91177308-0d34-0410-b5e6-96231b3b80d8
* implement constant folding support for an exotic constant expr:Chris Lattner2011-01-061-1/+19
| | | | | | | | | | | | ret i64 ptrtoint (i8* getelementptr ([1000 x i8]* @X, i64 1, i64 sub (i64 0, i64 ptrtoint ([1000 x i8]* @X to i64))) to i64) to "ret i64 1000". This allows us to correctly compute the trip count on a loop in PR8883, which occurs with std::fill on a char array. This allows us to transform it into a memset with a constant size. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122950 91177308-0d34-0410-b5e6-96231b3b80d8
* Reorder, rename, and document some members to make this easier to follow.Owen Anderson2011-01-051-20/+23
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122929 91177308-0d34-0410-b5e6-96231b3b80d8
* When computing the value on an edge, in certain cases LVI would fail to ↵Owen Anderson2011-01-051-0/+5
| | | | | | | | | compute the value range in the predecessor block, leading to an incorrect conclusion for the edge value. Found by inspection. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122908 91177308-0d34-0410-b5e6-96231b3b80d8
* Re-convert several of LazyValueInfo's internal maps to Dense{Map|Set}, and ↵Owen Anderson2011-01-051-33/+93
| | | | | | | | | | fix the issue in hasBlockValue() that was causing iterator invalidations. Many thanks to Dimitry Andric for tracking down those invalidations! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122906 91177308-0d34-0410-b5e6-96231b3b80d8
* fix an off-by-one bug that caused a crash analyzingChris Lattner2011-01-041-1/+1
| | | | | | | ashr's with huge shift amounts, PR8896 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122814 91177308-0d34-0410-b5e6-96231b3b80d8
* Use the new addEscapingValue callback to update GlobalsModRef when GVN adds ↵Owen Anderson2011-01-032-0/+12
| | | | | | | | | PHIs of GEPs. For the moment, have GlobalsModRef handle this conservatively by simply removing the value from its maps. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122787 91177308-0d34-0410-b5e6-96231b3b80d8
* Stub out a new updating interface to AliasAnalysis, allowing stateful ↵Owen Anderson2011-01-031-0/+6
| | | | | | | | | | analyses to be informed when a pointer value has potentially become escaping. Implementations can choose to either fall back to conservative responses for that value, or may recompute their analysis to accomodate the change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122777 91177308-0d34-0410-b5e6-96231b3b80d8
* fix rdar://8813415 - a miscompilation of 164.gzip that loop-idiomChris Lattner2011-01-031-0/+2
| | | | | | | exposed. It turns out to be a latent bug in basicaa, scary. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122772 91177308-0d34-0410-b5e6-96231b3b80d8
* Add spliceFunction to the CallGraph interface. This allows users to efficientlyNick Lewycky2011-01-031-1/+15
| | | | | | | | | | | update a callGraph when performing the common operation of splicing the body to a new function and updating all callers (such as via RAUW). No users yet, though this is intended for DeadArgumentElimination as part of PR8887. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122728 91177308-0d34-0410-b5e6-96231b3b80d8
* split dom frontier handling stuff out to its own DominanceFrontier header,Chris Lattner2011-01-027-3/+6
| | | | | | | | so that Dominators.h is *just* domtree. Also prune #includes a bit. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122714 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
* move isBytewiseValue out to ValueTracking.h/cppChris Lattner2010-12-261-0/+69
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122565 91177308-0d34-0410-b5e6-96231b3b80d8
* Change all self assignments X=X to (void)X, so that we can turn on aJeffrey Yasskin2010-12-232-3/+2
| | | | | | | | | new gcc warning that complains on self-assignments and self-initializations. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122458 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
* Fix inverted condition noticed by Frits van Bommel.Duncan Sands2010-12-211-3/+3
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122331 91177308-0d34-0410-b5e6-96231b3b80d8
* Pull a few more simplifications out of instcombine (there are stillDuncan Sands2010-12-211-5/+86
| | | | | | | plenty left though!), in particular for multiplication. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122330 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122328 91177308-0d34-0410-b5e6-96231b3b80d8
* Move checking of the recursion limit into the various Thread methods.Duncan Sands2010-12-211-20/+36
| | | | | | | No functionality change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122327 91177308-0d34-0410-b5e6-96231b3b80d8
* 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. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122326 91177308-0d34-0410-b5e6-96231b3b80d8
* Speculatively revert the use of DenseMap in LazyValueInfo, which may be ↵Owen Anderson2010-12-201-42/+16
| | | | | | causing Linux self-host failures. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122291 91177308-0d34-0410-b5e6-96231b3b80d8
* Attempt to appease the DragonEgg buildbots.Owen Anderson2010-12-201-22/+24
| | | | git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122288 91177308-0d34-0410-b5e6-96231b3b80d8
* Convert one of LVI's primary maps to a DenseMap, now that we know are more ↵Owen Anderson2010-12-201-16/+40
| | | | | | assured of iterator stability. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122273 91177308-0d34-0410-b5e6-96231b3b80d8
* More LVI cleanups, including trying to simplify the process of maintaining ↵Owen Anderson2010-12-201-25/+41
| | | | | | the OverDefinedCache. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122256 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.1 at 2025-08-04 12:03:10 +0000