summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis
Commit message (Collapse)AuthorAgeFilesLines
...
* LSR: handle the expansion of phi operands that use postinc forms of the IV.Andrew Trick2011-11-301-36/+68
| | | | | | Fixes PR11431: SCEVExpander::expandAddRecExprLiterally(const llvm::SCEVAddRecExpr*): Assertion `(!isa<Instruction>(Result) || SE.DT->dominates(cast<Instruction>(Result), Builder.GetInsertPoint())) && "postinc expansion does not dominate use"' failed. llvm-svn: 145482
* build/CMake: Finish removal of add_llvm_library_dependencies.Daniel Dunbar2011-11-292-12/+0
| | | | llvm-svn: 145420
* Fix a theoretical problem (not seen in the wild): if different instances of aDuncan Sands2011-11-291-1/+1
| | | | | | | | | | | | | | | weak variable are compiled by different compilers, such as GCC and LLVM, while LLVM may increase the alignment to the preferred alignment there is no reason to think that GCC will use anything more than the ABI alignment. Since it is the GCC version that might end up in the final program (as the linkage is weak), it is wrong to increase the alignment of loads from the global up to the preferred alignment as the alignment might only be the ABI alignment. Increasing alignment up to the ABI alignment might be OK, but I'm not totally convinced that it is. It seems better to just leave the alignment of weak globals alone. llvm-svn: 145413
* SCEV fix. In general, Add/Mul expressions should not inherit NSW/NUW.Andrew Trick2011-11-291-8/+8
| | | | | | | This reverts r139450, fixes r139453, and adds much needed comments and a unit test. llvm-svn: 145367
* Make SCEV print <nsw><nuw> for Add/MulExpr.Andrew Trick2011-11-291-0/+8
| | | | llvm-svn: 145364
* Make SelectionDAG::InferPtrAlignment use llvm::ComputeMaskedBits instead of ↵Eli Friedman2011-11-281-8/+10
| | | | | | duplicating the logic for globals. Make llvm::ComputeMaskedBits handle GlobalVariables slightly more aggressively, to match what InferPtrAlignment knew how to do. llvm-svn: 145304
* Remove the temporary flag -disable-unroll-scev and dead code.Andrew Trick2011-11-281-93/+0
| | | | | | SCEV should now be used for trip count analysis, not LoopInfo. llvm-svn: 145262
* Move code into anonymous namespaces.Benjamin Kramer2011-11-261-1/+1
| | | | llvm-svn: 145154
* Validate the return type when checking if a function is malloc.Benjamin Kramer2011-11-231-4/+4
| | | | | | Fixes PR11426. Not sure if a test case with a "wrong" malloc would be useful. llvm-svn: 145106
* Fix a crash in which a multiplication was being reported as being both negativeDuncan Sands2011-11-231-2/+7
| | | | | | | | and positive: positive, because it could be directly computed to be positive; negative, because the nsw flags means it is either negative or undefined (the multiplication always overflowed). llvm-svn: 145104
* Fix crasher in GVN due to my recent capture tracking changes.Nick Lewycky2011-11-212-1/+4
| | | | llvm-svn: 145047
* Add virtual destructor. Whoops!Nick Lewycky2011-11-211-0/+2
| | | | llvm-svn: 145044
* Less template, more virtual! Refactoring suggested by Chris in code review.Nick Lewycky2011-11-202-4/+109
| | | | llvm-svn: 145014
* Refactor code to use new attribute getters on CallSite for NoCapture and ByVal.Nick Lewycky2011-11-202-4/+2
| | | | | | | | Suggested in code review by Eli. That code in InstCombine looks kinda suspicious. llvm-svn: 145013
* SCEV: Actually set overflow flags on add expressions.Benjamin Kramer2011-11-201-2/+2
| | | | | | setFlags doesn't modify its arguments. llvm-svn: 145007
* Fix a corner case in updating LoopInfo after fully unrolling an outer loop.Andrew Trick2011-11-181-11/+9
| | | | | | | | | | | The loop tree's inclusive block lists are painful and expensive to update. (I have no idea why they're inclusive). The design was supposed to handle this case but the implementation missed it and my unit tests weren't thorough enough. Fixes PR11335: loop unroll update. llvm-svn: 144970
* Fix SCEV overly optimistic back edge taken count for multi-exit loops.Andrew Trick2011-11-161-9/+22
| | | | | | Fixes PR11375: Different results for 'clang++ huh.cpp'... llvm-svn: 144746
* Missed some users of Value::getNameStr.Benjamin Kramer2011-11-151-4/+2
| | | | llvm-svn: 144656
* Remove all remaining uses of Value::getNameStr().Benjamin Kramer2011-11-158-27/+27
| | | | llvm-svn: 144648
* Twinify GraphWriter a little bit.Benjamin Kramer2011-11-151-2/+2
| | | | llvm-svn: 144647
* Refactor capture tracking (which already had a couple flags for whether returnsNick Lewycky2011-11-142-117/+110
| | | | | | | | | | 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! llvm-svn: 144580
* Don't try to loop on iterators that are potentially invalidated inside the ↵Nick Lewycky2011-11-121-0/+18
| | | | | | loop. Fixes PR11361! llvm-svn: 144454
* Fix typo in comment.Nick Lewycky2011-11-091-1/+1
| | | | llvm-svn: 144236
* Don't forget to check FlagNW when determining whether an AddRecExpr will wrapNick Lewycky2011-11-091-2/+3
| | | | | | or not. Patch by Brendon Cahoon! llvm-svn: 144173
* Fix code to match comment. Fixes PR11340, a regression from r143209.Eli Friedman2011-11-081-1/+1
| | | | llvm-svn: 144121
* Teach instsimplify to simplify calls to undef.Dan Gohman2011-11-041-0/+11
| | | | llvm-svn: 143719
* build: Add initial cut at LLVMBuild.txt files.Daniel Dunbar2011-11-032-0/+47
| | | | llvm-svn: 143634
* Reapply commit 143214 with a fix: m_ICmp doesn't match conditionsDuncan Sands2011-10-301-29/+65
| | | | | | | | | | | | 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. llvm-svn: 143318
* Revert r143214; it's breaking a bunch of stuff.Eli Friedman2011-10-291-45/+29
| | | | llvm-svn: 143265
* The expression icmp eq (select (icmp eq x, 0), 1, x), 0 folds to false.Duncan Sands2011-10-281-29/+45
| | | | | | | | | 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. llvm-svn: 143214
* A shift of a power of two is a power of two or zero.Duncan Sands2011-10-281-1/+6
| | | | | | For completeness - not spotted in the wild. llvm-svn: 143211
* Fold icmp ugt (udiv X, Y), X to false. Spotted by my super-optimizerDuncan Sands2011-10-281-0/+12
| | | | | | in 186.crafty. llvm-svn: 143209
* Reapply commit 143028 with a fix: the problem was casting a ConstantExpr MulDuncan Sands2011-10-272-9/+52
| | | | | | | | | | | 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. llvm-svn: 143125
* Revert Duncan's r143028 expression folding which appears to be the culpritBob Wilson2011-10-271-46/+4
| | | | | | behind a compile failure on 483.xalancbmk. llvm-svn: 143102
* The maximum power of 2 dividing a power of 2 is itself. This occursDuncan Sands2011-10-262-10/+36
| | | | | | in 403.gcc and was spotted by my super-optimizer. llvm-svn: 143054
* My super-optimizer noticed that we weren't folding this expression toDuncan Sands2011-10-261-4/+46
| | | | | | true: (x *nsw x) sgt 0, where x = (y | 1). This occurs in 464.h264ref. llvm-svn: 143028
* Restore commits 142790 and 142843 - they weren't breaking the buildDuncan Sands2011-10-251-26/+46
| | | | | | | | | | | | | | | | | | | | | | | | | | 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! llvm-svn: 142919
* Fix the API usage in loop probability heuristics. It was incorrectlyChandler Carruth2011-10-251-15/+8
| | | | | | | | | | | | | | | 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. llvm-svn: 142917
* Speculatively revert commits 142790 and 142843 to see if it fixesDuncan Sands2011-10-251-46/+26
| | | | | | | | | | | | | | | | | | | | | | | | | | | 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! llvm-svn: 142916
* Now that we look at all the header PHIs, we need to consider all the header PHIsNick Lewycky2011-10-241-6/+14
| | | | | | | when deciding that the loop has stopped evolving. Fixes miscompile in the gcc torture testsuite! llvm-svn: 142843
* Remove return heuristics from the static branch probabilities, andChandler Carruth2011-10-241-73/+76
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | 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. llvm-svn: 142793
* Reapply r142781 with fix. Original message:Nick Lewycky2011-10-241-20/+32
| | | | | | | | | | | | | | | | | | | 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; } llvm-svn: 142790
* PHI nodes not in the loop header aren't part of the loop iteration initialNick Lewycky2011-10-241-1/+1
| | | | | | | state. Furthermore, they might not have two operands. This fixes the underlying issue behind the crashes introduced in r142781. llvm-svn: 142788
* Speculatively revert r142781. Bots are showingNick Lewycky2011-10-241-32/+20
| | | | | | | Assertion `i_nocapture < OperandTraits<PHINode>::operands(this) && "getOperand() out of range!"' failed. coming out of indvars. llvm-svn: 142786
* Simplify the design of BranchProbabilityInfo by collapsing it intoChandler Carruth2011-10-241-135/+90
| | | | | | | | | | | | | 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. llvm-svn: 142783
* Enhance SCEV's brute force loop analysis to handle multiple PHI nodes in theNick Lewycky2011-10-231-20/+32
| | | | | | | | | | | | | | | | | | 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; } llvm-svn: 142781
* Tidy up a loop to be more idiomatic for LLVM's codebase, and remove someChandler Carruth2011-10-231-18/+9
| | | | | | | extraneous whitespace. Trying to clean-up this pass as much as I can before I start making functional changes. llvm-svn: 142780
* Teach the BranchProbabilityInfo pass to print its results, and use thatChandler Carruth2011-10-231-2/+20
| | | | | | | | | | 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. llvm-svn: 142778
* Add compare operators to BranchProbability and use it to determine if an ↵Benjamin Kramer2011-10-231-8/+4
| | | | | | edge is hot. llvm-svn: 142751
* Make SCEV's brute force analysis stronger in two ways. Firstly, we should beNick Lewycky2011-10-221-26/+145
| | | | | | | | | | | | | | | | 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; } llvm-svn: 142731
OpenPOWER on IntegriCloud