summaryrefslogtreecommitdiffstats
path: root/llvm/lib/Analysis/ScalarEvolution.cpp
Commit message (Collapse)AuthorAgeFilesLines
...
* [C++11] More 'nullptr' conversion. In some cases just using a boolean check ↵Craig Topper2014-04-151-63/+66
| | | | | | instead of comparing to nullptr. llvm-svn: 206243
* divide by the result of the gcdSebastian Pop2014-04-081-1/+1
| | | | | | used to fail with 'Step should divide Start with no remainder.' llvm-svn: 205802
* handle special cases when findGCD returns 1Sebastian Pop2014-04-081-1/+6
| | | | | | used to fail with 'Step should divide Start with no remainder.' llvm-svn: 205801
* in findGCD of multiply expr return the gcdSebastian Pop2014-04-081-2/+4
| | | | | | we used to return 1 instead of the gcd llvm-svn: 205800
* ScalarEvolution: Compute exit counts for loops with a power-of-2 step.Benjamin Kramer2014-03-251-0/+10
| | | | | | | | | | | | | If we have a loop of the form for (unsigned n = 0; n != (k & -32); n += 32) {} then we know that n is always divisible by 32 and the loop must terminate. Even if we have a condition where the loop counter will overflow it'll always hold this invariant. PR19183. Our loop vectorizer creates this pattern and it's also occasionally formed by loop counters derived from pointers. llvm-svn: 204728
* Remove some dead assignements found by scan-buildArnaud A. de Grandmaison2014-03-151-6/+1
| | | | llvm-svn: 204013
* [C++11] Add range based accessors for the Use-Def chain of a Value.Chandler Carruth2014-03-091-10/+4
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This requires a number of steps. 1) Move value_use_iterator into the Value class as an implementation detail 2) Change it to actually be a *Use* iterator rather than a *User* iterator. 3) Add an adaptor which is a User iterator that always looks through the Use to the User. 4) Wrap these in Value::use_iterator and Value::user_iterator typedefs. 5) Add the range adaptors as Value::uses() and Value::users(). 6) Update *all* of the callers to correctly distinguish between whether they wanted a use_iterator (and to explicitly dig out the User when needed), or a user_iterator which makes the Use itself totally opaque. Because #6 requires churning essentially everything that walked the Use-Def chains, I went ahead and added all of the range adaptors and switched them to range-based loops where appropriate. Also because the renaming requires at least churning every line of code, it didn't make any sense to split these up into multiple commits -- all of which would touch all of the same lies of code. The result is still not quite optimal. The Value::use_iterator is a nice regular iterator, but Value::user_iterator is an iterator over User*s rather than over the User objects themselves. As a consequence, it fits a bit awkwardly into the range-based world and it has the weird extra-dereferencing 'operator->' that so many of our iterators have. I think this could be fixed by providing something which transforms a range of T&s into a range of T*s, but that *can* be separated into another patch, and it isn't yet 100% clear whether this is the right move. However, this change gets us most of the benefit and cleans up a substantial amount of code around Use and User. =] llvm-svn: 203364
* Add missing parenthesis in SCEV commentTobias Grosser2014-03-051-1/+1
| | | | | Contributed-by: Michael Zolutukin <mzolotukhin@apple.com> llvm-svn: 202963
* [Modules] Move the ConstantRange class into the IR library. This isChandler Carruth2014-03-041-1/+1
| | | | | | | | | | a bit surprising, as the class is almost entirely abstracted away from any particular IR, however it encodes the comparsion predicates which mutate ranges as ICmp predicate codes. This is reasonable as they're used for both instructions and constants. Thus, it belongs in the IR library with instructions and constants. llvm-svn: 202838
* [Modules] Move GetElementPtrTypeIterator into the IR library. As itsChandler Carruth2014-03-041-1/+1
| | | | | | | | | name might indicate, it is an iterator over the types in an instruction in the IR.... You see where this is going. Another step of modularizing the support library. llvm-svn: 202815
* [Modules] Move InstIterator out of the Support library, where it had noChandler Carruth2014-03-041-1/+1
| | | | | | | | | | | | | business. This header includes Function and BasicBlock and directly uses the interfaces of both classes. It has to do with the IR, it even has that in the name. =] Put it in the library it belongs to. This is one step toward making LLVM's Support library survive a C++ modules bootstrap. llvm-svn: 202814
* [C++11] Replace llvm::next and llvm::prior with std::next and std::prev.Benjamin Kramer2014-03-021-2/+2
| | | | | | Remove the old functions. llvm-svn: 202636
* Make DataLayout a plain object, not a pass.Rafael Espindola2014-02-251-1/+2
| | | | | | | Instead, have a DataLayoutPass that holds one. This will allow parts of LLVM don't don't handle passes to also use DataLayout. llvm-svn: 202168
* fix a corner case in delinearizationSebastian Pop2014-02-211-24/+15
| | | | | | handle special cases Step==1, Step==-1, GCD==1, and GCD==-1 llvm-svn: 201868
* Rename some member variables from TD to DL.Rafael Espindola2014-02-181-28/+28
| | | | | | TargetData was renamed DataLayout back in r165242. llvm-svn: 201581
* SCEV: Cast switched values to make -Wswitch more useful.Benjamin Kramer2014-02-111-16/+16
| | | | llvm-svn: 201170
* ScalarEvolution: Analyze trip count of loops with a switch guarding the exit.Benjamin Kramer2014-02-111-15/+53
| | | | llvm-svn: 201159
* Fix crasher introduced in r200203 and caught by a libc++ buildbot. Don't ↵Nick Lewycky2014-01-271-1/+3
| | | | | | assume that getMulExpr returns a SCEVMulExpr, it may have simplified it to something else! llvm-svn: 200210
* Teach SCEV to handle more cases of 'and X, CST', specifically where CST is ↵Nick Lewycky2014-01-271-22/+84
| | | | | | | | | | any number of contiguous 1 bits in a row, with any number of leading and trailing 0 bits. Unfortunately, this in turn led to some lower quality SCEVs due to some different paths through expression simplification, so add getUDivExactExpr and use it. This fixes all instances of the problems that I found, but we can make that function smarter as necessary. Merge test "xor-and.ll" into "and-xor.ll" since I needed to update it anyways. Test 'nsw-offset.ll' analyzes a little deeper, %n now gets a scev in terms of %no instead of a SCEVUnknown. llvm-svn: 200203
* Fix known typosAlp Toker2014-01-241-4/+4
| | | | | | | Sweep the codebase for common typos. Includes some changes to visible function names that were misspelt. llvm-svn: 200018
* Fix PR18449: SCEV needs more precise max BECount for multi-exit loop.Andrew Trick2014-01-151-14/+30
| | | | llvm-svn: 199299
* [PM] Split DominatorTree into a concrete analysis result object whichChandler Carruth2014-01-131-3/+3
| | | | | | | | | | | | | | | | | | | | | | | can be used by both the new pass manager and the old. This removes it from any of the virtual mess of the pass interfaces and lets it derive cleanly from the DominatorTreeBase<> template. In turn, tons of boilerplate interface can be nuked and it turns into a very straightforward extension of the base DominatorTree interface. The old analysis pass is now a simple wrapper. The names and style of this split should match the split between CallGraph and CallGraphWrapperPass. All of the users of DominatorTree have been updated to match using many of the same tricks as with CallGraph. The goal is that the common type remains the resulting DominatorTree rather than the pass. This will make subsequent work toward the new pass manager significantly easier. Also in numerous places things became cleaner because I switched from re-running the pass (!!! mid way through some other passes run!!!) to directly recomputing the domtree. llvm-svn: 199104
* [cleanup] Move the Dominators.h and Verifier.h headers into the IRChandler Carruth2014-01-131-1/+1
| | | | | | | | | | | | | | | | | | directory. These passes are already defined in the IR library, and it doesn't make any sense to have the headers in Analysis. Long term, I think there is going to be a much better way to divide these matters. The dominators code should be fully separated into the abstract graph algorithm and have that put in Support where it becomes obvious that evn Clang's CFGBlock's can use it. Then the verifier can manually construct dominance information from the Support-driven interface while the Analysis library can provide a pass which both caches, reconstructs, and supports a nice update API. But those are very long term, and so I don't want to leave the really confusing structure until that day arrives. llvm-svn: 199082
* Fixed old typo in ScalarEvolution, that caused wrong SCEVs zext operation.Stepan Dyatkovskiy2014-01-091-1/+1
| | | | | | | | | Detailed description is here: http://llvm.org/bugs/show_bug.cgi?id=18000#c16 For participation in bugfix process special thanks to David Wiberg. llvm-svn: 198863
* Put the functionality for printing a value to a raw_ostream as anChandler Carruth2014-01-091-9/+8
| | | | | | | | | | | | operand into the Value interface just like the core print method is. That gives a more conistent organization to the IR printing interfaces -- they are all attached to the IR objects themselves. Also, update all the users. This removes the 'Writer.h' header which contained only a single function declaration. llvm-svn: 198836
* Move the LLVM IR asm writer header files into the IR directory, as theyChandler Carruth2014-01-071-1/+1
| | | | | | | | | | | | | | | | | are part of the core IR library in order to support dumping and other basic functionality. Rename the 'Assembly' include directory to 'AsmParser' to match the library name and the only functionality left their -- printing has been in the core IR library for quite some time. Update all of the #includes to match. All of this started because I wanted to have the layering in good shape before I started adding support for printing LLVM IR using the new pass infrastructure, and commandline support for the new pass infrastructure. llvm-svn: 198688
* 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
OpenPOWER on IntegriCloud