summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
* Annotate APInt methods where it's not clear whether they are in place with ↵Benjamin Kramer2013-11-161-6/+6
| | | | | | | | warn_unused_result. Fix ScalarEvolution bugs uncovered by this. llvm-svn: 194928
* add more comments around the delinearization of arraysSebastian Pop2013-11-131-12/+68
| | | | llvm-svn: 194612
* delinearization of arraysSebastian Pop2013-11-121-0/+471
| | | | llvm-svn: 194527
* Change data structure to memorize computed result in ScalarEvolutionWan Xiaofei2013-11-121-22/+42
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | Replace std::map with SmallVector to memorize the cached result since SCEV usually belongs to little Loop/BB Linear scan on SmallVector is faster than std::map. Code reviewer : Andrew Trick. Test result : Pass Unit Test & LLVM Test Suite 401.bzip2 0.425721 0.419981 101.37% 403.gcc 24.53855 24.2667 101.12% 429.mcf 0.060847 0.059944 101.51% 433.milc 0.646009 0.636119 101.55% 444.namd 1.383928 1.370614 100.97% 445.gobmk 5.836575 5.800225 100.63% 450.soplex 1.911257 1.895963 100.81% 456.hmmer 1.039565 1.032534 100.68% 458.sjeng 0.897401 0.885567 101.34% 464.h264ref 3.645908 3.577991 101.90% 470.lbm 0.049456 0.048398 102.19% 471.omnetpp 5.638575 5.60435 100.61% bitmnp01 0.045738 0.045291 100.99% cjpegv2data 0.304359 0.302833 100.50% idctrn01 0.046433 0.045763 101.46% quake2 4.534416 4.4952 100.87% quake 2.688566 2.659208 101.10% xcsoar 12.42545 12.30385 100.99% linpack 0.038739 0.03803 101.86% matrix01 0.053564 0.0528 101.45% nbench 0.402867 0.395803 101.78% tblook01 0.021265 0.021015 101.19% ttsprk01 0.066384 0.065566 101.25% llvm-svn: 194459
* Rewrite SCEV's backedge taken count computation.Andrew Trick2013-11-061-163/+207
| | | | | | | | | | | | | | | | | | | | | | | | | | | | Patch by Michele Scandale! Rewrite of the functions used to compute the backedge taken count of a loop on LT and GT comparisons. I decided to split the handling of LT and GT cases becasue the trick "a > b == -a < -b" in some cases prevents the trip count computation due to the multiplication by -1 on the two operands of the comparison. This issue comes from the conservative computation of value range of SCEVs: taking the negative SCEV of an expression that have a small positive range (e.g. [0,31]), we would have a SCEV with a fullset as value range. Indeed, in the new rewritten function I tried to better handle the maximum backedge taken count computation when MAX/MIN expression are used to handle the cases where no entry guard is found. Some test have been modified in order to check the new value correctly (I manually check them and reasoning on possible overflow the new values seem correct). I finally added a new test case related to the multiplication by -1 issue on GT comparisons. llvm-svn: 194116
* SCEV: Make the final add of an inbounds GEP nuw if we know that the index is ↵Benjamin Kramer2013-10-281-4/+9
| | | | | | | | | | | | | | | | | | | | | | | positive. We can't do this for the general case as saying a GEP with a negative index doesn't have unsigned wrap isn't valid for negative indices. %gep = getelementptr inbounds i32* %p, i64 -1 But an inbounds GEP cannot run past the end of address space. So we check for the very common case of a positive index and make GEPs derived from that NUW. Together with Andy's recent non-unit stride work this lets us analyze loops like void foo3(int *a, int *b) { for (; a < b; a++) {} } PR12375, PR12376. Differential Revision: http://llvm-reviews.chandlerc.com/D2033 llvm-svn: 193514
* Clarify SCEV comments.Andrew Trick2013-10-221-8/+11
| | | | | | We handle for(i=n; i>0; i -= s) by canonicalizing within SCEV to for(i=-n; i<0; i += s). llvm-svn: 193147
* Use more type helper functionsMatt Arsenault2013-10-211-1/+1
| | | | llvm-svn: 193109
* Fix creating bitcasts between address spaces in SCEV.Matt Arsenault2013-10-211-5/+10
| | | | | | | | The test before wasn't successfully testing this since it was missing the datalayout piece to change the size of the second address space. llvm-svn: 193102
* Remove unused SCEV functionsMatt Arsenault2013-10-211-20/+1
| | | | llvm-svn: 193097
* SCEV should use NSW to get trip count for positive nonunit stride loops.Andrew Trick2013-10-181-18/+21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | SCEV currently fails to compute loop counts for nonunit stride loops. This comes up frequently. It prevents loop optimization and forces vectorization to insert extra loop checks. For example: void foo(int n, int *x) { for (int i = 0; i < n; i += 3) { x[i] = i; x[i+1] = i+1; x[i+2] = i+2; } } We need to properly handle the case in which limit > INT_MAX-stride. In the above case: n > INT_MAX-3. In this case the loop counter will step beyond the limit and overflow at the same time. However, knowing that signed integer overlow in undefined, we can assume the loop test behavior is arbitrary after overflow. This obeys both C undefined behavior rules, and the more strict LLVM poison value rules. I'm finally fixing this in response to Hal Finkel's persistence. The most probable reason that we never optimized this before is that we were being careful to handle case where the developer expected a side-effect free infinite loop relying on overflow: for (int i = 0; i < n; i += s) { ++j; } return j; If INT_MAX+1 is a multiple of s and n > INT_MAX-s, then we might expect an infinite loop. However there are plenty of ways to achieve this effect without relying on undefined behavior of signed overflow. llvm-svn: 193015
* Minor code simplificationMatt Arsenault2013-09-271-11/+8
| | | | llvm-svn: 191579
* Teach ScalarEvolution about pointer address spacesMatt Arsenault2013-09-101-11/+17
| | | | llvm-svn: 190425
* Fix a severe compile time problem when forming large SCEV expressions.Andrew Trick2013-07-311-0/+3
| | | | | | | | | | | | This fix is very lightweight. The same fix already existed for AddRec but was missing for NAry expressions. This is obviously an improvement and I'm unsure how to test compile time problems. Patch by Xiaoyi Guo! llvm-svn: 187475
* Stylistic change.Shuxin Yang2013-07-121-2/+2
| | | | | | Thank Nick for figuring out these problems. llvm-svn: 186146
* Use SmallVectorImpl& instead of SmallVector to avoid repeating small vector ↵Craig Topper2013-07-111-1/+1
| | | | | | size. llvm-svn: 186098
* Don't use a potentially expensive shift if all we want is one set bit.Benjamin Kramer2013-07-111-3/+3
| | | | | | No functionality change. llvm-svn: 186095
* Don't crash in SE dealing with ashr x, -1Hal Finkel2013-07-091-1/+1
| | | | | | | | | | | | | | ScalarEvolution::getSignedRange uses ComputeNumSignBits from ValueTracking on ashr instructions. ComputeNumSignBits can return zero, but this case was not handled correctly by the code in getSignedRange which was calling: APInt::getSignedMinValue(BitWidth).ashr(NS - 1) with NS = 0, resulting in an assertion failure in APInt::ashr. Now, we just return the conservative result (as with NS == 1). Another bug found by llvm-stress. llvm-svn: 185955
* Fix a SCEV update problem.Shuxin Yang2013-07-081-2/+40
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The symptom is seg-fault, and the root cause is that a SCEV contains a SCEVUnknown which has null-pointer to a llvm::Value. This is how the problem take place: =================================== 1). In the pristine input IR, there are two relevant instrutions Op1 and Op2, Op1's corresponding SCEV (denoted as SCEV(op1)) is a SCEVUnknown, and SCEV(Op2) contains SCEV(Op1). None of these instructions are dead. Op1 : V1 = ... ... Op2 : V2 = ... // directly or indirectly (data-flow) depends on Op1 2) Optimizer (LSR in my case) generates an instruction holding the equivalent value of Op1, making Op1 dead. Op1': V1' = ... Op1: V1 = ... ; now dead) Op2 : V2 = ... //Now deps on Op1', but the SCEV(Op2) still contains SCEV(Op1) 3) Op1 is deleted, and call-back function is called to reset SCEV(Op1) to indicate it is invalid. However, SCEV(Op2) is not invalidated as well. 4) Following pass get the cached, invalid SCEV(Op2), and try to manipulate it, and cause segfault. The fix: ======== It seems there is no clean yet inexpensive fix. I write to dev-list soliciting good solution, unforunately no ack. So, I decide to fix this problem in a brute-force way: When ScalarEvolution::getSCEV is called, check if the cached SCEV contains a invalid SCEVUnknow, if yes, remove the cached SCEV, and re-evaluate the SCEV from scratch. I compile buch of big *.c and *.cpp, fortunately, I don't see any increase in compile time. Misc: ===== The reduced test-case has 2357 lines of code+other-stuff, too big to commit. rdar://14283433 llvm-svn: 185843
* Use SmallVectorImpl::iterator/const_iterator instead of SmallVector to avoid ↵Craig Topper2013-07-031-1/+1
| | | | | | specifying the vector size. llvm-svn: 185540
* Silencing an MSVC warning about */ being found outside of a comment.Aaron Ballman2013-06-041-2/+2
| | | | llvm-svn: 183175
* Prevent loop-unroll from making assumptions about undefined behavior.Andrew Trick2013-05-311-5/+14
| | | | | | | | | | | | | | Fixes rdar:14036816, PR16130. There is an opportunity to compute precise trip counts for 'or' expressions and multi-exit loops. rdar:14038809: Optimize trip count computation for multi-exit loops. To do this we need to record the fact that ExitLimit assumes NSW. When it does not we can safely assume that the loop trip count is the minimum ExitLimt across all subexpressions and loop exits. llvm-svn: 183060
* Fix ScalarEvolution::ComputeExitLimitFromCond for 'or' conditions.Andrew Trick2013-05-311-32/+54
| | | | | | | | | | | | | | | | Fixes PR16130 - clang produces incorrect code with loop/expression at -O2. This is a 2+ year old bug that's now holding up the release. It's a case where we knowingly made aggressive assumptions about undefined behavior. These assumptions are wrong when SCEV is computing a subexpression that does not directly control the branch. With this fix, we avoid making assumptions in those cases but still optimize the common case. SCEV's trip count computation for exits controlled by 'or' expressions is now analagous to the trip count computation for loops with multiple exits. I had already fixed the multiple exit case to be conservative. llvm-svn: 182989
* Fix SCEV forgetMemoizedResults should search and destroy backedge exprs.Andrew Trick2013-03-261-0/+30
| | | | | | | | | | | | | | | Fixes PR15570: SEGV: SCEV back-edge info invalid after dead code removal. Indvars creates a SCEV expression for the loop's back edge taken count, then determines that the comparison is always true and removes it. When loop-unroll asks for the expression, it contains a NULL SCEVUnknkown (as a CallbackVH). forgetMemoizedResults should invalidate the loop back edges expression. llvm-svn: 177986
* Move all of the header files which are involved in modelling the LLVM IRChandler Carruth2013-01-021-8/+8
| | | | | | | | | | | | | | | | | | | | | into their new header subdirectory: include/llvm/IR. This matches the directory structure of lib, and begins to correct a long standing point of file layout clutter in LLVM. There are still more header files to move here, but I wanted to handle them in separate commits to make tracking what files make sense at each layer easier. The only really questionable files here are the target intrinsic tablegen files. But that's a battle I'd rather not fight today. I've updated both CMake and Makefile build systems (I think, and my tests think, but I may have missed something). I've also re-sorted the includes throughout the project. I'll be committing updates to Clang, DragonEgg, and Polly momentarily. llvm-svn: 171366
* Use the new script to sort the includes of every file under lib.Chandler Carruth2012-12-031-12/+13
| | | | | | | | | | | | | | | | | Sooooo many of these had incorrect or strange main module includes. I have manually inspected all of these, and fixed the main module include to be the nearest plausible thing I could find. If you own or care about any of these source files, I encourage you to take some time and check that these edits were sensible. I can't have broken anything (I strictly added headers, and reordered them, never removed), but they may not be the headers you'd really like to identify as containing the API being implemented. Many forward declarations and missing includes were added to a header files to allow them to parse cleanly when included first. The main module rule does in fact have its merits. =] llvm-svn: 169131
* Follow up to 168711: It's safe to base this analysis on the found compare, ↵Benjamin Kramer2012-11-291-4/+3
| | | | | | | | just return the value for the right predicate. Thanks to Andy for catching this. llvm-svn: 168921
* Improve isImpliedCond comment a bit.Andrew Trick2012-11-291-2/+2
| | | | llvm-svn: 168914
* SCEV: Even if the latch terminator is foldable we can't deduce the result of ↵Benjamin Kramer2012-11-271-3/+4
| | | | | | | | an unrelated condition with it. Fixes PR14432. llvm-svn: 168711
* Revert the series of commits starting with r166578 which introduced theChandler Carruth2012-11-011-7/+8
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | getIntPtrType support for multiple address spaces via a pointer type, and also introduced a crasher bug in the constant folder reported in PR14233. These commits also contained several problems that should really be addressed before they are re-committed. I have avoided reverting various cleanups to the DataLayout APIs that are reasonable to have moving forward in order to reduce the amount of churn, and minimize the number of commits that were reverted. I've also manually updated merge conflicts and manually arranged for the getIntPtrType function to stay in DataLayout and to be defined in a plausible way after this revert. Thanks to Duncan for working through this exact strategy with me, and Nick Lewycky for tracking down the really annoying crasher this triggered. (Test case to follow in its own commit.) After discussing with Duncan extensively, and based on a note from Micah, I'm going to continue to back out some more of the more problematic patches in this series in order to ensure we go into the LLVM 3.2 branch with a reasonable story here. I'll send a note to llvmdev explaining what's going on and why. Summary of reverted revisions: r166634: Fix a compiler warning with an unused variable. r166607: Add some cleanup to the DataLayout changes requested by Chandler. r166596: Revert "Back out r166591, not sure why this made it through since I cancelled the command. Bleh, sorry about this! r166591: Delete a directory that wasn't supposed to be checked in yet. r166578: Add in support for getIntPtrType to get the pointer type based on the address space. llvm-svn: 167221
* SCEV validator: Ignore CouldNotCompute/undef on both sides. This is mostly ↵Benjamin Kramer2012-10-271-3/+6
| | | | | | noise and blocks finding more severe bugs. llvm-svn: 166873
* SCEV validator: Add workarounds for some common false positives due to the ↵Benjamin Kramer2012-10-271-0/+18
| | | | | | way it handles strings. llvm-svn: 166872
* Add a basic verifier for SCEV's backedge taken counts.Benjamin Kramer2012-10-261-0/+68
| | | | | | | | | | | Enabled with -verify-scev. This could be extended significantly but hopefully catches the common cases now. Note that it's not enabled by default in any configuration because the way it tries to distinguish SCEVs is still fragile and may produce false positives. Also the test-suite isn't clean yet, one example is that it fails if a pass drops an NSW bit but it's still present in SCEV's cached. Cleaning up all those cases will take some time. llvm-svn: 166786
* getSmallConstantTripMultiple should never return zero.Hal Finkel2012-10-241-2/+5
| | | | | | | | | When the trip count is -1, getSmallConstantTripMultiple could return zero, and this would cause runtime loop unrolling to assert. Instead of returning zero, one is now returned (consistent with the existing overflow cases). Fixes PR14167. llvm-svn: 166612
* Add in support for getIntPtrType to get the pointer type based on the ↵Micah Villmow2012-10-241-8/+7
| | | | | | | | | address space. This checkin also adds in some tests that utilize these paths and updates some of the clients. llvm-svn: 166578
* Move TargetData to DataLayout.Micah Villmow2012-10-081-8/+8
| | | | llvm-svn: 165402
* Revert 'Fix a typo 'iff' => 'if''. iff is an abreviation of if and only if. ↵Sylvestre Ledru2012-09-271-2/+2
| | | | | | See: http://en.wikipedia.org/wiki/If_and_only_if Commit 164767 llvm-svn: 164768
* Fix a typo 'iff' => 'if'Sylvestre Ledru2012-09-271-2/+2
| | | | llvm-svn: 164767
* Release build: guard dump functions withManman Ren2012-09-121-1/+1
| | | | | | | | "#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)" No functional change. Update r163344. llvm-svn: 163679
* Release build: guard dump functions with "ifndef NDEBUG"Manman Ren2012-09-061-0/+2
| | | | | | No functional change. llvm-svn: 163344
* Stay rational; don't assert trying to take the square root of a negative value.Nick Lewycky2012-08-011-0/+6
| | | | | | If it's negative, the loop is already proven to be infinite. Fixes PR13489! llvm-svn: 161107
* Factor SCEV traversal code so I can use it elsewhere. No functionality.Andrew Trick2012-07-131-51/+19
| | | | llvm-svn: 160203
* Delete code for folding undefs in ScalarEvolution. It's invalid inDan Gohman2012-07-091-14/+0
| | | | | | obscure ways, and it isn't actually important in the real world. llvm-svn: 159969
* Reduce use list thrashing by using DenseMap's find_as for maps with ↵Benjamin Kramer2012-06-301-6/+8
| | | | | | | | ValueHandle keys. No functionality change. llvm-svn: 159497
* If the step value is a constant zero, the loop isn't going to terminate. FixesNick Lewycky2012-06-281-1/+1
| | | | | | the assert reported in PR13228! llvm-svn: 159393
* Fix typos found by http://github.com/lyda/misspell-checkBenjamin Kramer2012-06-021-1/+1
| | | | llvm-svn: 157885
* Make sure that we're dealing with a binary SCEVExpr when simplifying.Benjamin Kramer2012-05-301-1/+2
| | | | llvm-svn: 157704
* Teach SCEV's icmp simplification logic that a-b == 0 is equivalent to a == b.Benjamin Kramer2012-05-301-1/+20
| | | | | | | | | | | | | | | This also required making recursive simplifications until nothing changes or a hard limit (currently 3) is hit. With the simplification in place indvars can canonicalize loops of the form for (unsigned i = 0; i < a-b; ++i) into for (unsigned i = 0; i != a-b; ++i) which used to fail because SCEV created a weird umax expr for the backedge taken count. llvm-svn: 157701
* SCEV: Handle a corner case reducing AddRecExpr * AddRecExprAndrew Trick2012-05-301-1/+4
| | | | | | | | | If integer overflow causes one of the terms to reach zero, that can force the entire expression to zero. Fixes PR12929: cast<Ty>() argument of incompatible type llvm-svn: 157673
* Reformat the loop that does AddRecExpr * AddRecExpr reduction.Andrew Trick2012-05-301-55/+56
| | | | | | No functionality. llvm-svn: 157672
OpenPOWER on IntegriCloud