aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis
AgeCommit message (Collapse)Author
2011-01-26Separate out the constant bonus from the size reduction metrics. ReworkEric Christopher
a few loops accordingly. Should be no functional change. This is a step for more accurate cost/benefit analysis of devirt/inlining bonuses. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124275 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-26Coding style formatting changes.Eric Christopher
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124260 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-25In which I discover that zero+zero is zero, d'oh!Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124188 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-25See if this fixes llvm-gcc bootstrap.Duncan Sands
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124184 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-25Reorganize this so that the early exit and special cases come earlyEric Christopher
rather than interspersed. No functional change. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124168 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-24Give GetUnderlyingObject a TargetData, to keep it in syncDan Gohman
with BasicAA's DecomposeGEPExpression, which recently began using a TargetData. This fixes PR8968, though the testcase is awkward to reduce. Also, update several off GetUnderlyingObject's users which happen to have a TargetData handy to pass it in. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124134 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-24fix PR8928 by clearing a stale map, patch by Jakub Staszak!Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124132 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-24Add a comment.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124126 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Simplify some code with no functionality change. Make the test a lot moreNick Lewycky
robust against smarter optimizations, using the power of FileCheck. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124081 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Null initialize a few variables flagged byTed Kremenek
clang's -Wuninitialized-experimental warning. While these don't look like real bugs, clang's -Wuninitialized-experimental analysis is stricter than GCC's, and these fixes have the benefit of being general nice cleanups. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124073 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-23Use value ranges to fold ext(trunc) in SCEV when possible.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124062 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-22Have SCEV turn sext(x) into zext(x) when x is s>= 0. This applies many times inNick Lewycky
"make check" alone. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124046 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-22Add a FIXME explaining the move to a single indirect call bonus per functionEric Christopher
that we can change from indirect to direct. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124045 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-22Only apply the devirtualization bonus once instead of per-call site in theEric Christopher
target function. Fixes part of rdar://8546196 git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@124044 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-19Similarly, analyze truncate through multiply.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123842 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-19Add a missed SCEV fold that is required to continue analyzing the IR producedNick Lewycky
by indvars through the scev expander. trunc(add x, y) --> add(trunc x, y). Currently SCEV largely folds the other way which is probably wrong, but preserved to minimize churn. Instcombine doesn't do this fold either, demonstrating a missed optz'n opportunity on code doing add+trunc+add. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123838 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-19Add a missing SCEV simplification sext(zext x) --> zext x.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123832 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-18Teach BasicAA to return PartialAlias in cases where both pointersDan Gohman
are pointing to the same object, one pointer is accessing the entire object, and the other is access has a non-zero size. This prevents TBAA from kicking in and saying NoAlias in such cases. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123775 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-18Move DominanceFrontier from VMCore to Analysis.Cameron Zwarich
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123747 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-16fix PR8983, a broken assertion.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123562 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-15Teach LazyValueInfo that allocas aren't NULL. Over all of llvm-test, this savesNick Lewycky
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
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-13Add single entry / single exit accessors.Tobias Grosser
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
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-11some comment improvements.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123243 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Temporarily revert 123133, it's causing some regressions and I'm tryingEric Christopher
to get a testcase. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123225 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11the GEP faq says that only inbounds geps are guaranteed to not overflow.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123218 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Revert r123207: "Turn on memdep's verifyRemoved() in an attempt to smoke out ↵Jakob Stoklund Olesen
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
2011-01-11Turn on memdep's verifyRemoved() in an attempt to smoke out the cause of our ↵Jakob Stoklund Olesen
gcc bootstrap miscompare. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123207 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-11Teach constant folding to perform conversions from constant floatingChandler Carruth
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
2011-01-10Cleanup some of the constant folding code to consistently test intrinsicChandler Carruth
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
2011-01-09add a fixme: ir isn't expressive enough.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123139 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-09Step #4 in improving trip count analysis: HowFarToZero can analyzeChris Lattner
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
2011-01-09rearrange some code, no functionality change.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123136 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-09Step #3 to improving trip count analysis: If we foldChris Lattner
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
2011-01-09Step #2 to improve trip count analysis for loops like this:Chris Lattner
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
2011-01-09teach SCEV analysis of PHI nodes that PHI recurences formedChris Lattner
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
2011-01-09reduce indentation. Print <nuw> and <nsw> when dumping SCEV AddRec'sChris Lattner
that have the bit set. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@123104 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-06use isNullValue() to simplify code, add an assert.Chris Lattner
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122977 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-06implement constant folding support for an exotic constant expr:Chris Lattner
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
2011-01-05Reorder, rename, and document some members to make this easier to follow.Owen Anderson
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@122929 91177308-0d34-0410-b5e6-96231b3b80d8
2011-01-05When computing the value on an edge, in certain cases LVI would fail to ↵Owen Anderson
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
2011-01-05Re-convert several of LazyValueInfo's internal maps to Dense{Map|Set}, and ↵Owen Anderson
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
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-10 02:53:17 +0000