aboutsummaryrefslogtreecommitdiff
path: root/lib/Analysis
AgeCommit message (Collapse)Author
2011-11-15Twinify GraphWriter a little bit.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144647 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-14Refactor capture tracking (which already had a couple flags for whether returnsNick Lewycky
and stores capture) to permit the caller to see each capture point and decide whether to continue looking. Use this inside memdep to do an analysis that basicaa won't do. This lets us solve another devirtualization case, fixing PR8908! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144580 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-12Don't try to loop on iterators that are potentially invalidated inside the ↵Nick Lewycky
loop. Fixes PR11361! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144454 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-09Fix typo in comment.Nick Lewycky
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144236 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-09Don't forget to check FlagNW when determining whether an AddRecExpr will wrapNick Lewycky
or not. Patch by Brendon Cahoon! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144173 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-08Fix code to match comment. Fixes PR11340, a regression from r143209.Eli Friedman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@144121 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-04Teach instsimplify to simplify calls to undef.Dan Gohman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143719 91177308-0d34-0410-b5e6-96231b3b80d8
2011-11-03build: Add initial cut at LLVMBuild.txt files.Daniel Dunbar
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143634 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-30Reapply commit 143214 with a fix: m_ICmp doesn't match conditionsDuncan Sands
with the given predicate, it matches any condition and returns the predicate - d'oh! Original commit message: The expression icmp eq (select (icmp eq x, 0), 1, x), 0 folds to false. Spotted by my super-optimizer in 186.crafty and 450.soplex. We really need a proper infrastructure for handling generalizations of this kind of thing (which occur a lot), however this case is so simple that I decided to go ahead and implement it directly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143318 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-29Revert r143214; it's breaking a bunch of stuff.Eli Friedman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143265 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-28The expression icmp eq (select (icmp eq x, 0), 1, x), 0 folds to false.Duncan Sands
Spotted by my super-optimizer in 186.crafty and 450.soplex. We really need a proper infrastructure for handling generalizations of this kind of thing (which occur a lot), however this case is so simple that I decided to go ahead and implement it directly. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143214 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-28A shift of a power of two is a power of two or zero.Duncan Sands
For completeness - not spotted in the wild. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143211 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-28Fold icmp ugt (udiv X, Y), X to false. Spotted by my super-optimizerDuncan Sands
in 186.crafty. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143209 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-27Reapply commit 143028 with a fix: the problem was casting a ConstantExpr MulDuncan Sands
using BinaryOperator (which only works for instructions) when it should have been a cast to OverflowingBinaryOperator (which also works for constants). While there, correct a few other dubious looking uses of BinaryOperator. Thanks to Chad Rosier for the testcase. Original commit message: My super-optimizer noticed that we weren't folding this expression to true: (x *nsw x) sgt 0, where x = (y | 1). This occurs in 464.h264ref. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143125 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-27Revert Duncan's r143028 expression folding which appears to be the culpritBob Wilson
behind a compile failure on 483.xalancbmk. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143102 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-26The maximum power of 2 dividing a power of 2 is itself. This occursDuncan Sands
in 403.gcc and was spotted by my super-optimizer. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143054 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-26My super-optimizer noticed that we weren't folding this expression toDuncan Sands
true: (x *nsw x) sgt 0, where x = (y | 1). This occurs in 464.h264ref. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@143028 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-25Restore commits 142790 and 142843 - they weren't breaking the buildDuncan Sands
bots. Original commit messages: - Reapply r142781 with fix. Original message: Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142919 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-25Fix the API usage in loop probability heuristics. It was incorrectlyChandler Carruth
classifying many edges as exiting which were in fact not. These mainly formed edges into sub-loops. It was also not correctly classifying all returning edges out of loops as leaving the loop. With this match most of the loop heuristics are more rational. Several serious regressions on loop-intesive benchmarks like perlbench's loop tests when built with -enable-block-placement are fixed by these updated heuristics. Unfortunately they in turn uncover some other regressions. There are still several improvemenst that should be made to loop heuristics including trip-count, and early back-edge management. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142917 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-25Speculatively revert commits 142790 and 142843 to see if it fixesDuncan Sands
the dragonegg and llvm-gcc self-host buildbots. Original commit messages: - Reapply r142781 with fix. Original message: Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } - Now that we look at all the header PHIs, we need to consider all the header PHIs when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142916 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-24Now that we look at all the header PHIs, we need to consider all the header PHIsNick Lewycky
when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142843 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-24Remove return heuristics from the static branch probabilities, andChandler Carruth
introduce no-return or unreachable heuristics. The return heuristics from the Ball and Larus paper don't work well in practice as they pessimize early return paths. The only good hitrate return heuristics are those for: - NULL return - Constant return - negative integer return Only the last of these three can possibly require significant code for the returning block, and even the last is fairly rare and usually also a constant. As a consequence, even for the cold return paths, there is little code on that return path, and so little code density to be gained by sinking it. The places where sinking these blocks is valuable (inner loops) will already be weighted appropriately as the edge is a loop-exit branch. All of this aside, early returns are nearly as common as all three of these return categories, and should actually be predicted as taken! Rather than muddy the waters of the static predictions, just remain silent on returns and let the CFG itself dictate any layout or other issues. However, the return heuristic was flagging one very important case: unreachable. Unfortunately it still gave a 1/4 chance of the branch-to-unreachable occuring. It also didn't do a rigorous job of finding those blocks which post-dominate an unreachable block. This patch builds a more powerful analysis that should flag all branches to blocks known to then reach unreachable. It also has better worst-case runtime complexity by not looping through successors for each block. The previous code would perform an N^2 walk in the event of a single entry block branching to N successors with a switch where each successor falls through to the next and they finally fall through to a return. Test case added for noreturn heuristics. Also doxygen comments improved along the way. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142793 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-24Reapply r142781 with fix. Original message:Nick Lewycky
Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in the loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142790 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-24PHI nodes not in the loop header aren't part of the loop iteration initialNick Lewycky
state. Furthermore, they might not have two operands. This fixes the underlying issue behind the crashes introduced in r142781. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142788 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-24Speculatively revert r142781. Bots are showingNick Lewycky
Assertion `i_nocapture < OperandTraits<PHINode>::operands(this) && "getOperand() out of range!"' failed. coming out of indvars. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142786 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-24Simplify the design of BranchProbabilityInfo by collapsing it intoChandler Carruth
a single class. Previously it was split between two classes, one internal and one external. The concern seemed to center around exposing the weights used, but those can remain confined to the implementation file. Having a single class to maintain the state and analyses in use will also simplify several of the enhancements I want to make to our static heuristics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142783 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-23Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in theNick Lewycky
loop header when computing the trip count. With this, we now constant evaluate: struct ListNode { const struct ListNode *next; int i; }; static const struct ListNode node1 = {0, 1}; static const struct ListNode node2 = {&node1, 2}; static const struct ListNode node3 = {&node2, 3}; int test() { int sum = 0; for (const struct ListNode *n = &node3; n != 0; n = n->next) sum += n->i; return sum; } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142781 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-23Tidy up a loop to be more idiomatic for LLVM's codebase, and remove someChandler Carruth
extraneous whitespace. Trying to clean-up this pass as much as I can before I start making functional changes. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142780 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-23Teach the BranchProbabilityInfo pass to print its results, and use thatChandler Carruth
to bring it under direct test instead of merely indirectly testing it in the BlockFrequencyInfo pass. The next step is to start adding tests for the various heuristics employed, and to start fixing those heuristics once they're under test. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142778 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-23Add compare operators to BranchProbability and use it to determine if an ↵Benjamin Kramer
edge is hot. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142751 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-22Make SCEV's brute force analysis stronger in two ways. Firstly, we should beNick Lewycky
able to constant fold load instructions where the argument is a constant. Second, we should be able to watch multiple PHI nodes through the loop; this patch only supports PHIs in loop headers, more can be done here. With this patch, we now constant evaluate: static const int arr[] = {1, 2, 3, 4, 5}; int test() { int sum = 0; for (int i = 0; i < 5; ++i) sum += arr[i]; return sum; } git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142731 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-21Extend the floating point heuristic to consider NaN checks unlikely.Benjamin Kramer
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142687 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-21BranchProbabilityInfo: floating point equality is unlikely.Benjamin Kramer
This is from the same paper from Ball and Larus as the rest of the currently implemented heuristics. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142677 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-20A FIXME about block addresses and indirectbr.Eli Friedman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142569 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-20Simplify; no intended functional change.Eli Friedman
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142567 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-20"@string = constant i8 0" is a value i8* string of length zero. Analyze thatNick Lewycky
correctly in GetStringLength, fixing PR11181! git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142558 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-19Generalize the reading of probability metadata to work for both branchesChandler Carruth
and switches, with arbitrary numbers of successors. Still optimized for the common case of 2 successors for a conditional branch. Add a test case for switch metadata showing up in the BlockFrequencyInfo pass. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142493 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-19Teach the BranchProbabilityInfo analysis pass to read any metadataChandler Carruth
encoding of probabilities. In the absense of metadata, it continues to fall back on static heuristics. This allows __builtin_expect, after lowering through llvm.expect a branch instruction's metadata, to actually enter the branch probability model. This is one component of resolving PR2577. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142492 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-19Add pass printing support to BlockFrequencyInfo pass. The implementationChandler Carruth
layer already had support for printing the results of this analysis, but the wiring was missing. Now that printing the analysis works, actually bring some of this analysis, and the BranchProbabilityInfo analysis that it wraps, under test! I'm planning on fixing some bugs and doing other work here, so having a nice place to add regression tests and a way to observe the results is really useful. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142491 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-17Update DebugInfoFinder to match recent debug info encoding changes.Devang Patel
git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142295 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-17Correct over-zealous removal of hack.Bill Wendling
Some code want to check that *any* call within a function has the 'returns twice' attribute, not just that the current function has one. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142221 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-17Now that we have the ReturnsTwice function attribute, this method isBill Wendling
obsolete. Check the attribute instead. <rdar://problem/8031714> git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142212 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-16Delete a dead member. Dunno if this was ever used, but the current codeChandler Carruth
directly manipulates the weights inside of the BranchProbabilityInfo that is passed in. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142163 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-15Fix SCEVExpander assert during LSR: "argument of incompatible type".Andrew Trick
Just because we're dealing with a GEP doesn't mean we can assert the SCEV has a pointer type. The fix is simply to ignore the SCEV pointer type, which we really didn't need. Fixes PR11138 webkit crash. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@142058 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-14An instruction's operands aren't necessarily instructions or constants. TheyNick Lewycky
could be arguments, for example. No testcase because this is a bug-fix broken out of a larger optimization patch. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141951 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-13Enhance the memdep interface so that users can tell the difference between a ↵Eli Friedman
dependency which cannot be calculated and a path reaching the entry point of the function. This patch introduces isNonFuncLocal, which replaces isUnknown in some cases. Patch by Xiaoyi Guo. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141896 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-13Reapply r141870, SCEV expansion of post-inc.Andrew Trick
Speculatively reapply to see if this test case still crashes on linux. I may have fixed it in my last checkin. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141895 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-13Fix memory corruption I introduced a few checkins ago.Andrew Trick
Self-review easily caught this obvious bug. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141880 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-13Revert r141870. The test case crashes on linux with data corruption. A ↵Andrew Trick
deeper issue was exposed. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141873 91177308-0d34-0410-b5e6-96231b3b80d8
2011-10-13LSR: Reuse the post-inc expansion of expressions.Andrew Trick
This avoids unnecessary expansion of expressions and allows the SCEV expander to work on expression DAGs, not just trees. Fixes PR11090. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@141870 91177308-0d34-0410-b5e6-96231b3b80d8
generated by cgit v1.2.3-18-g5258 (git 2.32.0) at 2025-07-01 06:23:41 +0000